-/* 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"
*/
} 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
static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
int i;
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;
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. */
+ 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) {
/* 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. */
static INLINE void
init_node (ir_node *n, void *env) {
- int i;
set_irn_link (n, new_scc_info());
clear_backedges(n);
#if 0
}
static INLINE void
-init_ip_scc () {
+init_ip_scc (void) {
current_dfn = 1;
loop_node_cnt = 0;
init_stack();
#if 0
Works, but is inefficient.
static INLINE void
-init_ip_scc () {
+init_ip_scc (void) {
int i;
interprocedural_view = 1;
current_dfn = 1;
}
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(" 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
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));
+ /*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_n(n, i); //get_irn_ip_pred(n, i);
+ 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.
-void construct_ip_backedges () {
+void construct_ip_backedges (void) {
ir_graph *rem = current_ir_graph;
int rem_ipv = interprocedural_view;
int i, j;
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));
+ /*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));
+ /* 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());