/*
- * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
- *
* This file is part of libFirm.
- *
- * This file may be distributed and/or modified under the terms of the
- * GNU General Public License version 2 as published by the Free Software
- * Foundation and appearing in the file LICENSE.GPL included in the
- * packaging of this file.
- *
- * Licensees holding valid libFirm Professional Edition licenses may use
- * this file in accordance with the libFirm Commercial License.
- * Agreement provided with the Software.
- *
- * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
- * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE.
+ * Copyright (C) 2012 University of Karlsruhe.
*/
/**
#include "pmap.h"
#include "ircons.h"
-/* A variant of the loop tree that avoids loops without head.
- This reduces the depth of the loop tree. */
-#define NO_LOOPS_WITHOUT_HEAD 1
-
/** The outermost graph the scc is computed for. */
static ir_graph *outermost_ir_graph;
/** Current loop construction is working on. */
/** Counter to generate depth first numbering of visited nodes. */
static int current_dfn = 1;
-static unsigned max_loop_depth = 0;
-
-void link_to_reg_end(ir_node *n, void *env);
-void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
-ir_node *get_projx_link(ir_node *cb_projx);
-
-/**********************************************************************/
-/* Node attributes **/
-/**********************************************************************/
-
/**********************************************************************/
/* Node attributes needed for the construction. **/
/**********************************************************************/
int 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;
/**
return scc->dfn;
}
-#if 0
-static 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;
-}
-#endif
-
/**********************************************************************/
/* A stack. **/
/**********************************************************************/
static ir_loop *new_loop(void)
{
ir_loop *father = current_loop;
- ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
+ ir_loop *son = alloc_loop(father, get_irg_obstack(outermost_ir_graph));
- if (son->depth > max_loop_depth) max_loop_depth = son->depth;
current_loop = son;
return father;
}
{
init_scc_common();
irg_walk_graph(irg, init_node, NULL, obst);
- /*
- irg_walk (irg, link_to_reg_end, NULL, NULL);
- */
}
static inline void finish_scc(void)
/* When to walk from nodes to blocks. Only for Control flow operations? */
static inline int get_start_index(ir_node *n)
{
-#undef BLOCK_BEFORE_NODE
-#define BLOCK_BEFORE_NODE 1
-
-#if BLOCK_BEFORE_NODE
-
/* This version assures, that all nodes are ordered absolutely. This allows
to undef all nodes in the heap analysis if the block is false, which
means not reachable.
return 0;
else
return -1;
-
-#else
-
- /* This version causes deeper loop trees (at least we verified this
- for Polymor).
- But it guarantees that Blocks are analysed before nodes contained in the
- block. If so, we can set the value to undef if the block is not \
- executed. */
- if (is_cfop(n) || is_fragile_op(n) || is_Start(n))
- return -1;
- else
- return 0;
-
-#endif
}
/**
ir_node *m;
int i, res_index = -2;
- /*
- if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
- */
m = stack[tos-1]; /* tos = top of stack */
if (is_head(m, n)) {
res_index = smallest_dfn_pred(m, 0);
Next actions: Open a new loop on the loop tree and
try to find inner loops */
-#if NO_LOOPS_WITHOUT_HEAD
/* This is an adaption of the algorithm from fiasco / optscc to
* avoid loops without Block or Phi as first node. This should
* severely reduce the number of evaluations of nodes to detect
l = current_loop;
close = 0;
}
-#else
- ir_loop *l = new_loop();
-#endif
/* Remove the loop from the stack ... */
pop_scc_unmark_visit(n);
scc(tail);
assert(irn_visited(n));
-#if NO_LOOPS_WITHOUT_HEAD
if (close)
-#endif
close_loop(l);
} else {
/* No loop head was found, that is we have straight line code.
}
}
-int construct_backedges(ir_graph *irg)
+void construct_backedges(ir_graph *irg)
{
ir_graph *rem = current_ir_graph;
ir_loop *head_rem;
struct obstack temp;
- max_loop_depth = 0;
current_ir_graph = irg;
outermost_ir_graph = irg;
obstack_free(&temp, NULL);
assert(head_rem == current_loop);
- mature_loops(current_loop, irg->obst);
+ mature_loops(current_loop, get_irg_obstack(irg));
set_irg_loop(irg, current_loop);
add_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);
assert(get_irg_loop(irg)->kind == k_ir_loop);
current_ir_graph = rem;
- return max_loop_depth;
}
static void reset_backedges(ir_node *n)
}
}
-/*
-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;
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);
clear_irg_properties(current_ir_graph, IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);