From 9785eb583134ca36e24eda808b1734d5afe8851c Mon Sep 17 00:00:00 2001 From: =?utf8?q?G=C3=B6tz=20Lindenmaier?= Date: Wed, 7 Aug 2002 13:21:45 +0000 Subject: [PATCH] Implemented scc algorithm. Added datastructure to mark backedges (ana/backedge.h) and to represent loops (ana/irloop.h). The scc algorithm (ana/irscc.c) builds both datastructures. The algorithm does not yet work properly for interprocedural graphs. Finds more loops than only recursions. [r455] --- ir/ana/Makefile.in | 6 +- ir/ana/irbackedge.c | 93 +++++++ ir/ana/irbackedge_t.h | 13 + ir/ana/irdom.c | 1 - ir/ana/irloop.h | 93 +++++++ ir/ana/irloop_t.h | 39 +++ ir/ana/irscc.c | 625 ++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 866 insertions(+), 4 deletions(-) create mode 100644 ir/ana/irbackedge.c create mode 100644 ir/ana/irbackedge_t.h create mode 100644 ir/ana/irloop.h create mode 100644 ir/ana/irloop_t.h create mode 100644 ir/ana/irscc.c diff --git a/ir/ana/Makefile.in b/ir/ana/Makefile.in index 6609bf7c1..a8e53dfc6 100644 --- a/ir/ana/Makefile.in +++ b/ir/ana/Makefile.in @@ -10,13 +10,13 @@ srcdir = @srcdir@ topdir = ../.. subdir := ir/ana -INSTALL_HEADERS = irouts.h irdom.h cgana.h +INSTALL_HEADERS = irouts.h irdom.h cgana.h irloop.h SOURCES = $(INSTALL_HEADERS) SOURCES += Makefile.in \ - irouts.c irdom_t.h irdom.c cgana.c - + irouts.c irdom_t.h irdom.c cgana.c \ + irloop_t.h irbackedge.c irbackedge_t.h irscc.c include $(topdir)/MakeRules diff --git a/ir/ana/irbackedge.c b/ir/ana/irbackedge.c new file mode 100644 index 000000000..5d6a1c0cd --- /dev/null +++ b/ir/ana/irbackedge.c @@ -0,0 +1,93 @@ +/* Copyright (C) 2002 by Universitaet Karlsruhe +** All rights reserved. +** +** Authors: Goetz Lindenmaier +** +** irbackedges.c Access function for backedges. +** +*/ + +/* $Id$ */ + +#include "irnode_t.h" + +/**********************************************************************/ +/** Backedge information. **/ +/**********************************************************************/ + + +/* Returns backarray if the node can have backedges. Else returns + NULL. */ +inline int *get_backarray(ir_node *n) { + switch(get_irn_opcode(n)) { + case iro_Block: + if (interprocedural_view && n->attr.block.in_cg) { + assert(n->attr.block.cg_backedge && "backedge array not allocated!"); + return n->attr.block.cg_backedge; + } else { + assert(n->attr.block.backedge && "backedge array not allocated!"); + return n->attr.block.backedge; + } + break; + case iro_Phi: + assert(n->attr.phi_backedge && "backedge array not allocated!"); + return n->attr.phi_backedge; + break; + case iro_Filter: + if (interprocedural_view) { + assert(n->attr.filter.backedge && "backedge array not allocated!"); + return n->attr.filter.backedge; + } + break; + default: ; + } + return NULL; +} + +/* Returns true if the predesessor pos is a backedge. */ +bool is_backedge (ir_node *n, int pos) { + int *ba = get_backarray (n); + if (ba) return ba[pos]; + return false; +} + +/* Remarks that edge pos is a backedge. */ +void set_backedge (ir_node *n, int pos) { + int *ba = get_backarray (n); + assert(ba && "can only set backedges at Phi, Filter, Block nodes."); + ba[pos] = 1; +} + +/* Remarks that edge pos is a backedge. */ +void set_not_backedge (ir_node *n, int pos) { + int *ba = get_backarray (n); + assert(ba && "can only set backedges at Phi, Filter, Block nodes."); + ba[pos] = 0; +} + +/* Returns true if n has backedges. */ +bool has_backedges (ir_node *n) { + int i; + int *ba = get_backarray (n); + if (ba) + for (i = 0; i < get_irn_arity(n); i++) + if (ba[i]) return true; + return false; +} + +/* Sets all backedge information to zero. */ +void clear_backedges (ir_node *n) { + int i, rem = interprocedural_view; + int *ba; + interprocedural_view = 0; + ba = get_backarray (n); + if (ba) + for (i = 0; i < get_irn_arity(n); i++) + ba[i] = 0; + interprocedural_view = 1; + ba = get_backarray (n); + if (ba) + for (i = 0; i < get_irn_arity(n); i++) + ba[i] = 0; + interprocedural_view = rem; +} diff --git a/ir/ana/irbackedge_t.h b/ir/ana/irbackedge_t.h new file mode 100644 index 000000000..cfabf3578 --- /dev/null +++ b/ir/ana/irbackedge_t.h @@ -0,0 +1,13 @@ +#ifndef _IRBACKEDGE_T_H_ +#define _IRBACKEDGE_T_H_ + +# include "string.h" + +static INLINE int * new_backedge_arr(struct obstack *obst, int size) { + int *res = NEW_ARR_D (int, obst, size); + memset(res, 0, sizeof(int) * size); + return res; +} + + +#endif /* _IRBACKEDGE_T_H_ */ diff --git a/ir/ana/irdom.c b/ir/ana/irdom.c index 7fc31fee6..a66d209f9 100644 --- a/ir/ana/irdom.c +++ b/ir/ana/irdom.c @@ -136,7 +136,6 @@ void init_tmp_dom_info(ir_node *bl, tmp_dom_info *parent, } } - static void dom_compress (tmp_dom_info *v) { diff --git a/ir/ana/irloop.h b/ir/ana/irloop.h new file mode 100644 index 000000000..71f0b80fb --- /dev/null +++ b/ir/ana/irloop.h @@ -0,0 +1,93 @@ +/* Copyright (C) 2002 by Universitaet Karlsruhe +** All rights reserved. +** +** Authors: Goetz Lindenmaier +** +** irloops.h: Computes backedges in the control and data flow. +** Only Block and Phi/Filter nodes can have incoming backedges. +** Constructs loops data structure: indicates loop nesting. +*/ + +/* $Id$ */ + +# ifndef _IRLOOP_H_ +# define _IRLOOP_H_ + +# include "irgraph.h" +# include "irnode.h" + + +/** @@@ Interprocedural backedges ... ???? **/ + +/**********************************************************************/ +/** Backedge information. **/ +/** **/ +/** Predecessors of Block, Phi and interprocedural Filter nodes can **/ +/** have backedges. If loop information is computed, this **/ +/** information is computed, too. **/ +/** The backedge information can only be used if the graph is not in **/ +/** phase phase_building. **/ +/**********************************************************************/ + +/* Returns true if the predesessor pos is a backedge. */ +bool is_backedge (ir_node *n, int pos); +/* Remarks that edge pos is a backedge. */ +void set_backedge (ir_node *n, int pos); +/* Remarks that edge pos is not a backedge. */ +void set_not_backedge (ir_node *n, int pos); +/* Returns true if n has backedges. */ +bool has_backedges (ir_node *n); +/* Sets backedge information to zero. */ +void clear_backedges (ir_node *n); + +/**********************************************************************/ +/** The loops datastructure **/ +/** **/ +/** The loops datastructure represents circles in the intermediate **/ +/** representation. It does not represent loops in the terms of a **/ +/** source program. **/ +/** Each ir_graph can contain one outermost loop datastructure. **/ +/** loop is the entry point to the nested loops. **/ +/** The loop datastructure contains a field indicating the depth of **/ +/** the loop within the nesting. Further it contains a list of the **/ +/** loops with nesting depth -1. Finally it contains a list of all **/ +/** nodes in the loop. **/ +/* @@@ We could add a field pointing from a node to the containing loop, + this would cost a lot of memory, though. */ +/**********************************************************************/ + +typedef struct ir_loop ir_loop; + +void set_irg_loop(ir_graph *irg, ir_loop *l); +ir_loop *get_irg_loop(ir_graph *irg); + +/* Returns the loop n is contained in. + assumes current_ir_graph set properly. */ +ir_loop *get_irn_loop(ir_node *n); + +/* Returns outer loop, itself if outermost. */ +ir_loop *get_loop_outer_loop (ir_loop *loop); +/* Returns nesting depth of this loop */ +int get_loop_depth (ir_loop *loop); + +/* Sons are the inner loops contained in this loop. */ +/* Returns the number of inner loops */ +int get_loop_n_sons (ir_loop *loop); +ir_loop *get_loop_son (ir_loop *loop, int pos); +/* Returns the number of nodes contained in loop. */ +int get_loop_n_nodes (ir_loop *loop); +ir_node *get_loop_node (ir_loop *loop, int pos); + + +/**********************************************************************/ +/* Constructing and destructing the loop/backedge information. **/ +/**********************************************************************/ + +/* Constructs backedge information for irg. In interprocedural view constructs + backedges for all methods called by irg, too. + @@@ I'm not sure what happens if irg is within a recursion in iterproc_view. + @@@ Interprocedural backedge construction is not yet functioning!!! +*/ +void construct_backedges(ir_graph *irg); + +#endif /* _IRLOOP_H_ */ diff --git a/ir/ana/irloop_t.h b/ir/ana/irloop_t.h new file mode 100644 index 000000000..3e196c16f --- /dev/null +++ b/ir/ana/irloop_t.h @@ -0,0 +1,39 @@ +/* Copyright (C) 2002 by Universitaet Karlsruhe +** All rights reserved. +** +** Authors: Goetz Lindenmaier +** +** irloops_t.h: +*/ + +/* $Id$ */ + +#include "common.h" +#include "irloop.h" + +#ifndef _IRLOOP_T_H_ +#define _IRLOOP_T_H_ + +struct ir_loop { + firm_kind kind; /* A type tag, set to k_ir_loop. */ + + struct ir_loop *outer_loop; /* The outer loop */ + struct ir_loop **sons; /* Inner loops */ + struct ir_node **nodes; /* Nodes in loop. */ + int depth; /* Nesting depth */ + /* + struct state_entry *mem_phis; + struct state_entry *states; + + struct obset **oval; + struct loop_node *link; + */ +}; + +static INLINE void +add_loop_son(ir_loop *loop, ir_loop *son); + +static INLINE void +add_loop_node(ir_loop *loop, ir_node *n); + +#endif /* _IRLOOP_T_H_ */ diff --git a/ir/ana/irscc.c b/ir/ana/irscc.c new file mode 100644 index 000000000..dfb51c301 --- /dev/null +++ b/ir/ana/irscc.c @@ -0,0 +1,625 @@ +/* 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$ */ + +#include "irloop_t.h" +#include "irnode.h" +#include "irgraph_t.h" +#include "array.h" + +ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed + for */ +static ir_loop *current_loop; /* Current loop construction is working + on. */ +static int loop_node_cnt = 0; /* Counts the number of allocated loop nodes. + Each loop node gets a unique number. + What for? ev. remove. @@@ */ +static int current_dfn = 1; /* Counter to generate depth first numbering + of visited nodes. */ + +/**********************************************************************/ +/* Node attributes needed for the construction. **/ +/**********************************************************************/ + +typedef struct scc_info { + bool in_stack; /* Marks whether node is on the stack. */ + int dfn; /* Depth first search number. */ + int uplink; /* dfn number of ancestor. */ + ir_loop *loop; /* Refers to the containing loop. */ + /* + struct section *section; + xset def; + xset use; + */ +} scc_info; + +static INLINE scc_info* new_scc_info() { + scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info)); + memset (info, 0, sizeof (scc_info)); + return info; +} + +static INLINE void +mark_irn_in_stack (ir_node *n) { + assert(get_irn_link(n)); + ((scc_info *)get_irn_link(n))->in_stack = true; +} + +static INLINE void +mark_irn_not_in_stack (ir_node *n) { + assert(get_irn_link(n)); + ((scc_info *)get_irn_link(n))->in_stack = false; +} + +static INLINE bool +irn_is_in_stack (ir_node *n) { + assert(get_irn_link(n)); + return ((scc_info *)get_irn_link(n))->in_stack; +} + +static INLINE void +set_irn_uplink (ir_node *n, int uplink) { + assert(get_irn_link(n)); + ((scc_info *)get_irn_link(n))->uplink = uplink; +} + +static INLINE int +get_irn_uplink (ir_node *n) { + assert(get_irn_link(n)); + return ((scc_info *)get_irn_link(n))->uplink; +} + +static INLINE void +set_irn_dfn (ir_node *n, int dfn) { + if (! get_irn_link(n)) { DDMN(n); DDME(get_irg_ent(current_ir_graph));} + assert(get_irn_link(n)); + ((scc_info *)get_irn_link(n))->dfn = dfn; +} + +static INLINE int +get_irn_dfn (ir_node *n) { + assert(get_irn_link(n)); + return ((scc_info *)get_irn_link(n))->dfn; +} + +/* Uses temporary information to set the loop */ +static INLINE void +set_irn_loop_tmp (ir_node *n, ir_loop* loop) { + assert(get_irn_link(n)); + ((scc_info *)get_irn_link(n))->loop = loop; +} + +/* 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; +} + +ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) { + int i; + ir_loop *res = NULL; + + /* Test whether n is contained in this loop. */ + for (i = 0; i < get_loop_n_nodes(l); i++) + if (n == get_loop_node(l, i)) return l; + + /* Is this a leave in the loop tree? If so loop not found. */ + if (get_loop_n_sons(l) == 0) return NULL; + + /* Else descend in the loop tree. */ + for (i = 0; i < get_loop_n_sons(l); i++) { + res = find_nodes_loop(n, get_loop_son(l, i)); + if (res) break; + } + return res; +} + +/* @@@ temporary implementation, costly!!! */ +ir_loop * get_irn_loop(ir_node *n) { + ir_loop *l = get_irg_loop(current_ir_graph); + l = find_nodes_loop(n, l); + return l; +} + +/**********************************************************************/ +/* A stack. **/ +/**********************************************************************/ + +static ir_node **stack = NULL; +static int tos = 0; /* top of stack */ + +static INLINE void init_stack() { + if (stack) { + ARR_RESIZE (ir_node *, stack, 1000); + } else { + stack = NEW_ARR_F (ir_node *, 1000); + } + tos = 0; +} + +static INLINE void free_stack() { + DEL_ARR_F(stack); + stack = NULL; + tos = 0; +} + +static INLINE void +push (ir_node *n) +{ + //DDMN(n); + + if (tos == ARR_LEN (stack)) { + int nlen = ARR_LEN (stack) * 2; + ARR_RESIZE (ir_node *, stack, nlen); + } + stack [tos++] = n; + mark_irn_in_stack(n); +} + +static INLINE ir_node * +pop (void) +{ + ir_node *n = stack[--tos]; + mark_irn_not_in_stack(n); + return n; +} + +/* The nodes up to n belong to the current loop. + Removes them from the stack and adds them to the current loop. */ +static INLINE void +pop_scc_to_loop (ir_node *n) +{ + ir_node *m; + + for (;;) { + m = pop(); + set_irn_dfn(m, loop_node_cnt); + loop_node_cnt++; + add_loop_node(current_loop, m); + set_irn_loop_tmp(m, current_loop); + if (m==n) break; + } +} + +/* Removes and unmarks all nodes up to n from the stack. + The nodes must be visited once more to assign them to a scc. */ +static INLINE void +pop_scc_unmark_visit (ir_node *n) +{ + ir_node *m = NULL; + + while (m != n) { + m = pop(); + set_irn_visited(m, 0); + } +} + +/**********************************************************************/ +/* The loop datastructure. **/ +/**********************************************************************/ + +/* 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) { + 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->nodes = NEW_ARR_F (ir_node *, 0); + if (father) { + son->outer_loop = father; + add_loop_son(father, son); + son->depth = father->depth+1; + } else { /* The root loop */ + son->outer_loop = son; + son->depth = 0; + } + + current_loop = son; + return father; +} + +/* Finishes the datastructures, copies the arrays to the obstack + of current_ir_graph. */ +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; +} + +/* Returns outer loop, itself if outermost. */ +ir_loop *get_loop_outer_loop (ir_loop *loop) { + assert(loop && loop->kind == k_ir_loop); + return loop->outer_loop; +} + +/* Returns nesting depth of this loop */ +int get_loop_depth (ir_loop *loop) { + assert(loop); assert(loop->kind == k_ir_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); +} +ir_loop *get_loop_son (ir_loop *loop, int pos) { + assert(loop && loop->kind == k_ir_loop); + return loop->sons[pos]; +} +static INLINE void +add_loop_son(ir_loop *loop, ir_loop *son) { + assert(loop && loop->kind == k_ir_loop); + ARR_APP1 (ir_loop *, loop->sons, son); +} + +/* 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); +} +ir_node *get_loop_node (ir_loop *loop, int pos) { + assert(loop && loop->kind == k_ir_loop); + return loop->nodes[pos]; +} +static INLINE void +add_loop_node(ir_loop *loop, ir_node *n) { + assert(loop && loop->kind == k_ir_loop); + ARR_APP1 (ir_node *, loop->nodes, n); +} + +/* The outermost loop is remarked in the surrounding graph. */ +void set_irg_loop(ir_graph *irg, ir_loop *loop) { + assert(irg); + irg->loop = loop; +} +ir_loop *get_irg_loop(ir_graph *irg) { + assert(irg); + return irg->loop; +} + +/**********************************************************************/ +/* Constructing and destructing the loop/backedge information. **/ +/**********************************************************************/ + +/* Initialization steps. **********************************************/ + +static INLINE void +init_node (ir_node *n, void *env) { + set_irn_link (n, new_scc_info()); + clear_backedges(n); +} + +static INLINE void +init_scc (ir_graph *irg) { + current_dfn = 1; + loop_node_cnt = 0; + init_stack(); + irg_walk_graph (irg, init_node, NULL, NULL); + /* + irg_walk (irg, link_to_reg_end, NULL, NULL); + */ +} + +/* Condition for breaking the recursion. */ +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) && + (n == get_irg_start_block(current_ir_graph))) { + if ((!interprocedural_view) || + (current_ir_graph == outermost_ir_graph)) + return true; + } + return false; +} + +/* Don't walk from nodes to blocks except for Control flow operations. */ +static INLINE int +get_start_index(ir_node *n) { + if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start) + return -1; + else + return 0; +} + +/* Returns current_ir_graph and set it to the irg of predecessor index + of node n. */ +static INLINE ir_graph * +switch_irg (ir_node *n, int index) { + ir_graph *old_current = current_ir_graph; + + if (interprocedural_view) { + /* Only Filter and Block nodes can have predecessors in other graphs. */ + if (get_irn_op(n) == op_Filter) + n = get_nodes_Block(n); + if (get_irn_op(n) == op_Block) { + ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index)); + if (is_ip_cfop(cfop)) { + current_ir_graph = get_irn_irg(cfop); + set_irg_visited(current_ir_graph, get_max_irg_visited()); + } + } + } + + return old_current; +} + +/* Walks up the stack passing n and then finding the node + where we walked into the irg n is contained in. + Here we switch the irg. */ +static ir_graph * +find_irg_on_stack (ir_node *n) { + ir_node *m; + ir_graph *old_current = current_ir_graph; + int i; + + if (interprocedural_view) { + for (i = tos; i >= 0; i--) { + if (stack[i] == n) break; + } + if (i < 0) i = tos; + + //printf(" Here\n"); + + assert (i >= 0); + for (; i >= 0; i--) { + m = stack[i]; + //printf(" Visiting %d ", i); DDMN(m); + if (is_ip_cfop(m)) { + current_ir_graph = get_irn_irg(m); + break; + } + if (get_irn_op(m) == op_Filter) { + /* Find the corresponding ip_cfop */ + ir_node *pred = stack[i+1]; + int j; + for (j = 0; j < get_Filter_n_cg_preds(m); j++) + if (get_Filter_cg_pred(m, j) == pred) break; + if (j >= get_Filter_n_cg_preds(m)) + /* It is a filter we didn't pass as the predecessors are marked. */ + continue; + assert(get_Filter_cg_pred(m, j) == pred); + switch_irg(m, j); + break; + } + } + } + + return old_current; +} + +/* 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. */ +static bool +is_head (ir_node *n, ir_node *root) +{ + int i; + int some_outof_loop = 0, some_in_loop = 0; + + /* Test for legal loop header */ + if (!((get_irn_op(n) == op_Block) || + (get_irn_op(n) == op_Phi) || + ((get_irn_op(n) == op_Filter) && interprocedural_view))) + return false; + + if (!is_outermost_Start(n)) { + for (i = get_start_index(n); i < get_irn_arity(n); i++) { + ir_node *pred = get_irn_n(n, i); + assert(pred); + if (is_backedge(n, i)) continue; + if (!irn_is_in_stack(pred)) { + some_outof_loop = 1; + } else { + assert(get_irn_uplink(pred) >= get_irn_uplink(root)); + some_in_loop = 1; + } + } + } + return some_outof_loop && some_in_loop; +} + +/* Returns index of the predecessor with the smallest dfn number + greater-equal than limit. */ +static int +smallest_dfn_pred (ir_node *n, int limit) +{ + int i, index = -2, min = -1; + + if (!is_outermost_Start(n)) { + for (i = get_start_index(n); i < get_irn_arity(n); i++) { + ir_node *pred = get_irn_n(n, i); + assert(pred); + if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue; + if (get_irn_dfn(pred) >= limit + && (min == -1 || get_irn_dfn(pred) < min)) { + index = i; + min = get_irn_dfn(pred); + } + } + } + return index; +} + +/* Returns index of the predecessor with the largest dfn number. */ +static int +largest_dfn_pred (ir_node *n) +{ + int i, index = -2, max = -1; + + if (!is_outermost_Start(n)) { + for (i = get_start_index(n); i < get_irn_arity(n); i++) { + ir_node *pred = get_irn_n(n, i); + if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue; + if (get_irn_dfn(pred) > max) { + index = i; + max = get_irn_dfn(pred); + } + } + } + return index; +} + +/* Searches the stack for possible loop heads. Tests these for backedges. + If it finds a head with an unmarked backedge it marks this edge and + returns the tail of the loop. + If it finds no backedge returns NULL. */ +static ir_node * +find_tail (ir_node *n) { + ir_node *m; + int i, res_index = -2; + + /* + if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL; + */ + + m = stack[tos-1]; + if (is_head (m, n)) { + res_index = smallest_dfn_pred(m, 0); + if ((res_index == -2) && /* no smallest dfn pred found. */ + (n == m)) + return NULL; + } else { + if (m == n) return NULL; + for (i = tos-2; ; --i) { + m = stack[i]; + if (is_head (m, n)) { + res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1); + if (res_index == -2) /* no smallest dfn pred found. */ + res_index = largest_dfn_pred (m); + break; + } + } + } + assert (res_index > -2); + + set_backedge (m, res_index); + return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index); +} + + +/* The core algorithm. *****************************************/ + +void scc (ir_node *n) { + int i; + ir_graph *rem; + + if (irn_visited(n)) return; + mark_irn_visited(n); + + /* Initialize the node */ + set_irn_dfn(n, current_dfn); /* Depth first number for this node */ + set_irn_uplink(n, current_dfn); /* ... is default uplink. */ + set_irn_loop_tmp(n, NULL); + current_dfn ++; + + /* What's this good for? + n->ana.scc.section = NULL; + */ + + push(n); + + if (!is_outermost_Start(n)) { + for (i = get_start_index(n); i < get_irn_arity(n); i++) { + ir_node *m; + if (is_backedge(n, i)) continue; + + m = get_irn_ip_pred(n, i); + if (!m) continue; + scc (m); + return_recur(n, i); + + if (irn_is_in_stack(m)) { + /* Uplink of m is smaller if n->m is a backedge. + Propagate the uplink to mark the loop. */ + if (get_irn_uplink(m) < get_irn_uplink(n)) + set_irn_uplink(n, get_irn_uplink(m)); + } + } + } + if (get_irn_dfn(n) == get_irn_uplink(n)) { + /* This condition holds for the node with the incoming backedge. */ + ir_node *tail = find_tail(n); + if (tail) { + /* We found a new loop! */ + ir_loop *l = new_loop(); + /* Remove the loop from the stack ... */ + pop_scc_unmark_visit (n); + /* and recompute it in a better order; and so that it goes into + the new loop. */ + rem = find_irg_on_stack(tail); + scc (tail); + current_ir_graph = rem; + + assert (irn_visited(n)); + + current_loop = l; + } else { + pop_scc_to_loop(n); + } + } +} + +/* Constructs backedge information for irg. In interprocedural view constructs + backedges for all methods called by irg, too. */ +void construct_backedges(ir_graph *irg) { + ir_graph *rem = current_ir_graph; + ir_loop *head_rem; + int i; + + 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; +} -- 2.20.1