-void construct_backedges(ir_graph *irg) {
- ir_graph *rem = current_ir_graph;
- ir_loop *head_rem;
- int i;
-
- assert(!interprocedural_view &&
- "not implemented, use construct_ip_backedges");
-
- current_ir_graph = irg;
- outermost_ir_graph = irg;
-
- init_scc(irg);
-
- current_loop = NULL;
- new_loop(); /* sets current_loop */
- head_rem = current_loop; /* Just for assertion */
-
- if (interprocedural_view) {
- set_irg_visited(irg, inc_max_irg_visited());
- init_ip_walk ();
- } else {
- inc_irg_visited(irg);
- }
-
- scc(get_irg_end(irg));
- for (i = 0; i < get_End_n_keepalives(get_irg_end(irg)); i++)
- scc(get_End_keepalive(get_irg_end(irg), i));
-
- if (interprocedural_view) finish_ip_walk();
-
- assert(head_rem == current_loop);
- set_irg_loop(irg, current_loop);
- assert(get_irg_loop(irg)->kind == k_ir_loop);
- /*
- irg->loops = current_loop;
- if (icfg == 1) {
- int count = 0;
- int depth = 0;
- count_loop (the_loop, &count, &depth);
- }
- }
- */
- current_ir_graph = rem;
-}
-
-
-
-void construct_ip_backedges () {
- ir_graph *rem = current_ir_graph;
- int rem_ipv = interprocedural_view;
- int i, j;
-
- outermost_ir_graph = get_irp_main_irg();
-
- init_ip_scc();
-
- current_loop = NULL;
- new_loop(); /* sets current_loop */
- interprocedural_view = 1;
-
- inc_max_irg_visited();
- for (i = 0; i < get_irp_n_irgs(); i++)
- set_irg_visited(get_irp_irg(i), get_max_irg_visited());
-
- for (i = 0; i < get_irp_n_irgs(); i++) {
- ir_node *sb;
- current_ir_graph = get_irp_irg(i);
- //DDME(get_irg_ent(current_ir_graph));
- /* Find real entry points */
- sb = get_irg_start_block(current_ir_graph);
- if ((get_Block_n_cfgpreds(sb) > 1) ||
- (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
- // printf("running scc for "); DDME(get_irg_ent(current_ir_graph));
- /* Compute scc for this graph */
- outermost_ir_graph = current_ir_graph;
- set_irg_visited(outermost_ir_graph, get_max_irg_visited());
- scc(get_irg_end(current_ir_graph));
- for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
- scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
- }
-
- set_irg_loop(outermost_ir_graph, current_loop);
- assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
-
- current_ir_graph = rem;
- interprocedural_view = rem_ipv;
+int construct_backedges(ir_graph *irg) {
+ ir_graph *rem = current_ir_graph;
+ ir_loop *head_rem;
+ struct obstack temp;
+
+ assert(!get_interprocedural_view() &&
+ "not implemented, use construct_ip_backedges()");
+
+ max_loop_depth = 0;
+ current_ir_graph = irg;
+ outermost_ir_graph = irg;
+
+ obstack_init(&temp);
+ init_scc(irg, &temp);
+
+ current_loop = NULL;
+ new_loop(); /* sets current_loop */
+ head_rem = current_loop; /* Just for assertion */
+
+ inc_irg_visited(irg);
+
+ scc(get_irg_end(irg));
+
+ finish_scc();
+ obstack_free(&temp, NULL);
+
+ assert(head_rem == current_loop);
+ mature_loops(current_loop, irg->obst);
+ set_irg_loop(irg, current_loop);
+ set_irg_loopinfo_state(irg, loopinfo_consistent);
+ assert(get_irg_loop(irg)->kind == k_ir_loop);
+ current_ir_graph = rem;
+ return max_loop_depth;
+}
+
+
+#ifdef INTERPROCEDURAL_VIEW
+int construct_ip_backedges(void) {
+ ir_graph *rem = current_ir_graph;
+ int rem_ipv = get_interprocedural_view();
+ int i;
+ strcut obstack temp;
+
+ max_loop_depth = 0;
+ assert(get_irp_ip_view_state() == ip_view_valid);
+
+ outermost_ir_graph = get_irp_main_irg();
+
+ obstack_init(&temp);
+ init_ip_scc(&temp);
+
+ current_loop = NULL;
+ new_loop(); /* sets current_loop */
+ set_interprocedural_view(1);
+
+ inc_max_irg_visited();
+ for (i = 0; i < get_irp_n_irgs(); i++)
+ set_irg_visited(get_irp_irg(i), get_max_irg_visited());
+
+ /** We have to start the walk at the same nodes as cg_walk. **/
+ /* Walk starting at unreachable procedures. Only these
+ * have End blocks visible in interprocedural view. */
+ for (i = 0; i < get_irp_n_irgs(); i++) {
+ ir_node *sb;
+ current_ir_graph = get_irp_irg(i);
+
+ sb = get_irg_start_block(current_ir_graph);
+
+ if ((get_Block_n_cfgpreds(sb) > 1) ||
+ (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb))
+ continue;
+
+ scc(get_irg_end(current_ir_graph));
+ }
+
+ /* Check whether we walked all procedures: there could be procedures
+ with cyclic calls but no call from the outside. */
+ for (i = 0; i < get_irp_n_irgs(); i++) {
+ ir_node *sb;
+ current_ir_graph = get_irp_irg(i);
+
+ /* Test start block: if inner procedure end and end block are not
+ * visible and therefore not marked. */
+ sb = get_irg_start_block(current_ir_graph);
+ if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
+ }
+
+ /* Walk all endless loops in inner procedures.
+ * We recognize an inner procedure if the End node is not visited. */
+ for (i = 0; i < get_irp_n_irgs(); i++) {
+ ir_node *e;
+ current_ir_graph = get_irp_irg(i);
+
+ e = get_irg_end(current_ir_graph);
+ if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
+ int j;
+ /* Don't visit the End node. */
+ for (j = 0; j < get_End_n_keepalives(e); j++)
+ scc(get_End_keepalive(e, j));
+ }
+ }
+
+ set_irg_loop(outermost_ir_graph, current_loop);
+ set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
+ assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
+
+ obstack_free(&temp, NULL);
+ current_ir_graph = rem;
+ set_interprocedural_view(rem_ipv);
+ return max_loop_depth;
+}
+
+void my_construct_ip_backedges(void) {
+ ir_graph *rem = current_ir_graph;
+ int rem_ipv = get_interprocedural_view();
+ int i;
+
+ assert(get_irp_ip_view_state() == ip_view_valid);
+
+ outermost_ir_graph = get_irp_main_irg();
+
+ init_ip_scc();
+
+ current_loop = NULL;
+ new_loop(); /* sets current_loop */
+ set_interprocedural_view(1);
+
+ inc_max_irg_visited();
+ for (i = 0; i < get_irp_n_irgs(); i++)
+ set_irg_visited(get_irp_irg(i), get_max_irg_visited());
+
+ /** We have to start the walk at the same nodes as cg_walk. **/
+ /* Walk starting at unreachable procedures. Only these
+ * have End blocks visible in interprocedural view. */
+ for (i = 0; i < get_irp_n_irgs(); i++) {
+ ir_node *sb;
+ current_ir_graph = get_irp_irg(i);
+
+ sb = get_irg_start_block(current_ir_graph);
+
+ if ((get_Block_n_cfgpreds(sb) > 1) ||
+ (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
+
+ my_scc(get_irg_end(current_ir_graph));
+ }
+
+ /* Check whether we walked all procedures: there could be procedures
+ with cyclic calls but no call from the outside. */
+ for (i = 0; i < get_irp_n_irgs(); i++) {
+ ir_node *sb;
+ current_ir_graph = get_irp_irg(i);
+
+ /* Test start block: if inner procedure end and end block are not
+ * visible and therefore not marked. */
+ sb = get_irg_start_block(current_ir_graph);
+ if (get_irn_visited(sb) < get_irg_visited(current_ir_graph))
+ scc(sb);
+ }
+
+ /* Walk all endless loops in inner procedures.
+ * We recognize an inner procedure if the End node is not visited. */
+ for (i = 0; i < get_irp_n_irgs(); i++) {
+ ir_node *e;
+ current_ir_graph = get_irp_irg(i);
+
+ e = get_irg_end(current_ir_graph);
+ if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
+ int j;
+ /* Don't visit the End node. */
+ for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
+ }
+ }
+
+ set_irg_loop(outermost_ir_graph, current_loop);
+ set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
+ assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
+
+ current_ir_graph = rem;
+ set_interprocedural_view(rem_ipv);
+}
+#endif
+
+static void reset_backedges(ir_node *n) {
+ if (is_possible_loop_head(n)) {
+#ifdef INTERPROCEDURAL_VIEW
+ int rem = get_interprocedural_view();
+
+ set_interprocedural_view(1);
+ clear_backedges(n);
+ set_interprocedural_view(1);
+ clear_backedges(n);
+ set_interprocedural_view(rem);
+#else
+ clear_backedges(n);
+#endif
+ }
+}
+
+
+/*
+static void loop_reset_backedges(ir_loop *l) {
+ int i;
+ reset_backedges(get_loop_node(l, 0));
+ for (i = 0; i < get_loop_n_nodes(l); ++i)
+ set_irn_loop(get_loop_node(l, i), NULL);
+ for (i = 0; i < get_loop_n_sons(l); ++i) {
+ loop_reset_backedges(get_loop_son(l, i));
+ }
+}
+*/
+
+static void loop_reset_node(ir_node *n, void *env) {
+ (void) env;
+ set_irn_loop(n, NULL);
+ reset_backedges(n);
+}
+
+
+/** Removes all loop information.
+ Resets all backedges */
+void free_loop_information(ir_graph *irg) {
+ /* We can not use this recursion, as the loop might contain
+ illegal nodes by now. Why else would we throw away the
+ representation?
+ if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
+ */
+ irg_walk_graph(irg, loop_reset_node, NULL, NULL);
+ set_irg_loop(irg, NULL);
+ set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
+ /* We cannot free the loop nodes, they are on the obstack. */
+}
+
+
+void free_all_loop_information(void) {
+ int i;
+#ifdef INTERPROCEDURAL_VIEW
+ int rem = get_interprocedural_view();
+ set_interprocedural_view(1); /* To visit all filter nodes */
+#endif
+ for (i = 0; i < get_irp_n_irgs(); i++) {
+ free_loop_information(get_irp_irg(i));
+ }
+#ifdef INTERPROCEDURAL_VIEW
+ set_interprocedural_view(rem);
+#endif
+}
+
+
+
+
+
+/* Debug stuff *************************************************/
+
+static int test_loop_node(ir_loop *l) {
+ int i, has_node = 0, found_problem = 0;
+ loop_element le;
+
+ assert(l && l->kind == k_ir_loop);
+
+ if (get_loop_n_elements(l) == 0) {
+ found_problem = 1;
+ dump_loop(l, "-ha");
+ }
+
+ le = get_loop_element(l, 0);
+ if (*(le.kind) != k_ir_node) {
+ assert(le.kind && *(le.kind) == k_ir_loop);
+
+ found_problem = 1;
+ dump_loop(l, "-ha");
+ }
+
+ if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
+ found_problem = 1;
+ dump_loop(l, "-ha");
+ }
+
+ if ((get_loop_depth(l) != 0) &&
+ (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
+ found_problem = 1;
+ dump_loop(l, "-ha");
+ }
+
+ /* Recur */
+ has_node = 0;
+ for (i = 0; i < get_loop_n_elements(l); ++i) {
+ le = get_loop_element(l, i);
+ if (*(le.kind) == k_ir_node)
+ has_node++;
+ else
+ if (test_loop_node(le.son)) found_problem = 1;
+ }
+
+ if (has_node == 0) {
+ found_problem = 1;
+ dump_loop(l, "-ha");
+ }
+
+ return found_problem;
+}
+
+/** Prints all loop nodes that
+ * - do not have any firm nodes, only loop sons
+ * - the header is not a Phi, Block or Filter.
+ */
+void find_strange_loop_nodes(ir_loop *l) {
+ int found_problem = 0;
+ found_problem = test_loop_node(l);
+ printf("Finished Test\n\n");
+ if (found_problem) exit(0);
+
+}
+
+/* ------------------------------------------------------------------- */
+/* Simple analyses based on the loop information */
+/* ------------------------------------------------------------------- */
+
+int is_loop_variant(ir_loop *l, ir_loop *b) {
+ int i, n_elems;
+
+ if (l == b) return 1;
+
+ n_elems = get_loop_n_elements(l);
+ for (i = 0; i < n_elems; ++i) {
+ loop_element e = get_loop_element(l, i);
+ if (is_ir_loop(e.kind))
+ if (is_loop_variant(e.son, b))
+ return 1;
+ }
+
+ return 0;
+}
+
+/* Test whether a value is loop invariant.
+ *
+ * @param n The node to be tested.
+ * @param block A block node. We pass the block, not the loop as we must
+ * start off with a block loop to find all proper uses.
+ *
+ * Returns non-zero, if the node n is not changed in the loop block
+ * belongs to or in inner loops of this blocks loop. */
+int is_loop_invariant(const ir_node *n, const ir_node *block) {
+ ir_loop *l = get_irn_loop(block);
+ const ir_node *b = is_Block(n) ? n : get_nodes_block(n);
+ return !is_loop_variant(l, get_irn_loop(b));