-/* Copyright (C) 2002 by Universitaet Karlsruhe
-** All rights reserved.
-**
-** Authors: Goetz Lindenmaier
-**
-** irscc.c Computing the strongly connected regions and building
-** backedge/loop datastructures.
-**
-*/
-
-/* $Id$ */
+/*
+ * Project: libFIRM
+ * File name: ir/ana/irscc.c
+ * Purpose: Compute the strongly connected regions and build
+ * backedge/loop datastructures.
+ * Author: Goetz Lindenmaier
+ * Modified by:
+ * Created: 7.2002
+ * CVS-ID: $Id$
+ * Copyright: (c) 2002-2003 Universität Karlsruhe
+ * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
+ */
#include <string.h>
#include "irnode.h"
#include "irgraph_t.h"
#include "array.h"
-#include "xprintf.h"
#include "irgwalk.h"
-
+#include "irprog.h"
ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
for */
*/
} scc_info;
-static INLINE scc_info* new_scc_info() {
+static INLINE scc_info* new_scc_info(void) {
scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
memset (info, 0, sizeof (scc_info));
return info;
((scc_info *)get_irn_link(n))->loop = loop;
}
+#if 0
/* Uses temporary information to get the loop */
static INLINE ir_loop *
get_irn_loop_tmp (ir_node *n) {
assert(get_irn_link(n));
return ((scc_info *)get_irn_link(n))->loop;
}
+#endif
-ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
+static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
int i;
ir_loop *res = NULL;
static ir_node **stack = NULL;
static int tos = 0; /* top of stack */
-static INLINE void init_stack() {
+static INLINE void init_stack(void) {
if (stack) {
ARR_RESIZE (ir_node *, stack, 1000);
} else {
tos = 0;
}
-static INLINE void free_stack() {
+#if 0
+static INLINE void free_stack(void) {
DEL_ARR_F(stack);
stack = NULL;
tos = 0;
}
+#endif
static INLINE void
push (ir_node *n)
{
- //DDMN(n);
+ /*DDMN(n);*/
if (tos == ARR_LEN (stack)) {
int nlen = ARR_LEN (stack) * 2;
/* Allocates a new loop as son of current_loop. Sets current_loop
to the new loop and returns the father. */
-ir_loop *new_loop (void) {
+static ir_loop *new_loop (void) {
ir_loop *father, *son;
father = current_loop;
son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
memset (son, 0, sizeof (ir_loop));
son->kind = k_ir_loop;
- son->sons = NEW_ARR_F (ir_loop *, 0);
+/* son->sons = NEW_ARR_F (ir_loop *, 0);
son->nodes = NEW_ARR_F (ir_node *, 0);
+ A. Schoesser: Removed, because array children was introduced,
+ which contains both, nodes AND sons.
+ This comment may be removed after beeing read by all important persons :) */
+ son->children = NEW_ARR_F (loop_element, 0);
+ son->n_nodes = 0;
+ son->n_sons=0;
if (father) {
son->outer_loop = father;
add_loop_son(father, son);
return father;
}
+#if 0
/* Finishes the datastructures, copies the arrays to the obstack
- of current_ir_graph. */
-void mature_loop (ir_loop *loop) {
+ of current_ir_graph.
+ A. Schoesser: Caution: loop -> sons is gone. */
+static void mature_loop (ir_loop *loop) {
ir_loop **new_sons;
- ir_node **new_nods;
new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
DEL_ARR_F(loop->sons);
loop->sons = new_sons;
}
+#endif
/* Returns outer loop, itself if outermost. */
ir_loop *get_loop_outer_loop (ir_loop *loop) {
return loop->depth;
}
-/* @@@ sons are the inner loops _and_ all nodes within them. */
/* Returns the number of inner loops */
int get_loop_n_sons (ir_loop *loop) {
assert(loop && loop->kind == k_ir_loop);
- return ARR_LEN(loop->sons);
+ return(loop -> n_sons);
}
+
+/* Returns the pos`th loop_node-child *
+ * TODO: This method isn`t very efficient ! *
+ * Returns NULL if there isnt`t a pos`th loop_node */
ir_loop *get_loop_son (ir_loop *loop, int pos) {
+ int child_nr = 0, loop_nr = -1;
+
assert(loop && loop->kind == k_ir_loop);
- return loop->sons[pos];
+ while(child_nr < ARR_LEN(loop->children))
+ {
+ if(*(loop -> children[child_nr].kind) == k_ir_loop)
+ loop_nr++;
+ if(loop_nr == pos)
+ return(loop -> children[child_nr].son);
+ child_nr++;
+ }
+ return NULL;
}
+
+/* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
+ is invalid! */
+
static INLINE void
add_loop_son(ir_loop *loop, ir_loop *son) {
+ loop_element lson;
+ lson.son = son;
assert(loop && loop->kind == k_ir_loop);
- ARR_APP1 (ir_loop *, loop->sons, son);
+ assert(get_kind(son) == k_ir_loop);
+ ARR_APP1 (loop_element, loop->children, lson);
+ loop -> n_sons++;
}
/* Returns the number of nodes in the loop */
int get_loop_n_nodes (ir_loop *loop) {
assert(loop); assert(loop->kind == k_ir_loop);
- return ARR_LEN(loop->nodes);
+ return loop -> n_nodes;
+/* return ARR_LEN(loop->nodes); */
}
+
+/* Returns the pos`th ir_node-child *
+ * TODO: This method isn`t very efficient ! *
+ * Returns NULL if there isnt`t a pos`th ir_node */
ir_node *get_loop_node (ir_loop *loop, int pos) {
+ int child_nr, node_nr = -1;
+
assert(loop && loop->kind == k_ir_loop);
- return loop->nodes[pos];
+ assert(pos < get_loop_n_nodes(loop));
+
+ for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
+ if(*(loop -> children[child_nr].kind) == k_ir_node)
+ node_nr++;
+ if(node_nr == pos)
+ return(loop -> children[child_nr].node);
+ }
+ assert(0 && "no child at pos found");
+ return NULL;
}
+
+/* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
+ is invalid! */
+
static INLINE void
add_loop_node(ir_loop *loop, ir_node *n) {
+ loop_element ln;
+ ln.node=n;
+ assert(loop && loop->kind == k_ir_loop);
+ assert(get_kind(n) == k_ir_node);
+ ARR_APP1 (loop_element, loop->children, ln);
+ loop->n_nodes++;
+}
+
+/** Returns the number of elements contained in loop. */
+int get_loop_n_elements (ir_loop *loop) {
assert(loop && loop->kind == k_ir_loop);
- ARR_APP1 (ir_node *, loop->nodes, n);
+ return(ARR_LEN(loop->children));
+}
+
+/*
+ Returns the pos`th loop element.
+ This may be a loop_node or a ir_node. The caller of this function has
+ to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
+ and then select the apropriate "loop_element.node" or "loop_element.son".
+*/
+
+loop_element get_loop_element (ir_loop *loop, int pos) {
+ assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
+
+ return(loop -> children[pos]);
}
/* The outermost loop is remarked in the surrounding graph. */
init_node (ir_node *n, void *env) {
set_irn_link (n, new_scc_info());
clear_backedges(n);
+#if 0
+ /* Also init nodes not visible in intraproc_view. */
+ /* @@@ init_node is called for too many nodes -- this wastes memory!.
+ The mem is not lost as its on the obstack. */
+ if (get_irn_op(n) == op_Filter) {
+ for (i = 0; i < get_Filter_n_cg_preds(n); i++)
+ init_node(get_Filter_cg_pred(n, i), NULL);
+ }
+ if (get_irn_op(n) == op_Block) {
+ for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
+ init_node(get_Block_cg_cfgpred(n, i), NULL);
+ }
+ }
+ /* The following pattern matches only after a call from above pattern. */
+ if ((get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
+ /* @@@ init_node is called for every proj -- this wastes memory!.
+ The mem is not lost as its on the obstack. */
+ ir_node *cb = get_Proj_pred(n);
+ if ((get_irn_op(cb) == op_CallBegin) ||
+ (get_irn_op(cb) == op_EndReg) ||
+ (get_irn_op(cb) == op_EndExcept)) {
+ init_node(cb, NULL);
+ init_node(get_nodes_Block(cb), NULL);
+ }
+#endif
}
static INLINE void
*/
}
+static INLINE void
+init_ip_scc (void) {
+ current_dfn = 1;
+ loop_node_cnt = 0;
+ init_stack();
+ cg_walk (init_node, NULL, NULL);
+}
+
+#if 0
+Works, but is inefficient.
+static INLINE void
+init_ip_scc (void) {
+ int i;
+ interprocedural_view = 1;
+ current_dfn = 1;
+ loop_node_cnt = 0;
+ init_stack();
+ for (i = 0; i < get_irp_n_irgs(); i++) {
+ current_ir_graph = get_irp_irg(i);
+ irg_walk_graph (current_ir_graph, init_node, NULL, NULL);
+ /* @@@ decrease max_visited to avoide double walks */
+ }
+}
+#endif
+
/* Condition for breaking the recursion. */
-bool is_outermost_Start(ir_node *n) {
+static bool is_outermost_Start(ir_node *n) {
/* Test whether this is the outermost Start node. If so
recursion must end. */
+ if ((get_irn_op(n) == op_Block) &&
+ (get_Block_n_cfgpreds(n) == 1) &&
+ (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
+ (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
+ return true;
+ }
+#if 0
+ /* @@@ Bad condition:
+ not possible in interprocedural view as outermost_graph is
+ not necessarily the only with a dead-end start block.
+ Besides current_ir_graph is not set properly. */
if ((get_irn_op(n) == op_Block) &&
(n == get_irg_start_block(current_ir_graph))) {
if ((!interprocedural_view) ||
(current_ir_graph == outermost_ir_graph))
return true;
}
+#endif
return false;
}
}
if (i < 0) i = tos;
- //printf(" Here\n");
-
assert (i >= 0);
for (; i >= 0; i--) {
m = stack[i];
- //printf(" Visiting %d ", i); DDMN(m);
+ /*printf(" Visiting %d ", i); DDMN(m);*/
if (is_ip_cfop(m)) {
current_ir_graph = get_irn_irg(m);
break;
return old_current;
}
+#if 0
+static void test(ir_node *pred, ir_node *root, ir_node *this) {
+ int i;
+ if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
+
+ printf("this: %d ", get_irn_uplink(this)); DDMN(this);
+ printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
+ printf("root: %d ", get_irn_uplink(root)); DDMN(root);
+
+ printf("tos: %d\n", tos);
+
+ for (i = tos; i >= 0; i--) {
+ ir_node *n = stack[i];
+ if (!n) continue;
+ printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
+ }
+}
+#endif
+
/* Returns true if n is a loop header, i.e., it is a Block, Phi
or Filter node and has predecessors within the loop and out
of the loop. */
/* The core algorithm. *****************************************/
-void scc (ir_node *n) {
+static void scc (ir_node *n) {
int i;
ir_graph *rem;
if (irn_visited(n)) return;
mark_irn_visited(n);
+ /*printf("mark: %d ", get_irn_visited(n)); DDMN(n);
+ DDME(get_irg_ent(current_ir_graph));*/
/* Initialize the node */
set_irn_dfn(n, current_dfn); /* Depth first number for this node */
ir_node *m;
if (is_backedge(n, i)) continue;
- m = get_irn_ip_pred(n, i);
- if (!m) continue;
+ m = get_irn_n(n, i); /*get_irn_ip_pred(n, i);*/
+ if ((!m) || (get_irn_op(m) == op_Unknown)) continue;
scc (m);
- return_recur(n, i);
+ /*return_recur(n, i);*/
if (irn_is_in_stack(m)) {
/* Uplink of m is smaller if n->m is a backedge.
ir_loop *head_rem;
int i;
+ assert(!interprocedural_view &&
+ "not implemented, use construct_ip_backedges");
+
current_ir_graph = irg;
outermost_ir_graph = irg;
*/
current_ir_graph = rem;
}
+
+
+
+void construct_ip_backedges (void) {
+ 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;
+}