+ * @param irn the node
+ * @param ctx the environment
+ */
+static void block_info_walker(ir_node *irn, void *ctx)
+{
+ if (is_Block(irn)) {
+ pre_env *env = (pre_env*)ctx;
+ alloc_block_info(irn, env);
+ }
+}
+
+/**
+ * Returns the block info of a block.
+ */
+static block_info *get_block_info(ir_node *block)
+{
+ return (block_info*)get_irn_link(block);
+}
+
+/* --------------------------------------------------------
+ * Infinite loop analysis
+ * --------------------------------------------------------
+ */
+
+/**
+ * Walker to set block marks and loop links to 0.
+ */
+static void clear_block_mark_loop_link(ir_node *block, void *env)
+{
+ (void) env;
+
+ if (is_Block(block)) {
+ set_Block_mark(block, 0);
+ set_loop_link(get_irn_loop(block), NULL);
+ }
+}
+
+/**
+ * Returns non-zero if block is part of real loop loop.
+ */
+
+static unsigned in_loop(ir_node *block, ir_loop *loop)
+{
+ ir_loop *l = get_irn_loop(block);
+ ir_loop *outer = get_irg_loop(environ->graph);
+
+ while (l != loop) {
+ /* loop tree root is not a loop */
+ if (l == NULL || l == outer)
+ return 0;
+ l = get_loop_outer_loop(l);
+ }
+ return 1;
+}
+
+/**
+ * Returns the outermost real loop of loop.
+ */
+static ir_loop *get_loop_outermost(ir_loop *loop)
+{
+ ir_loop *outer = get_irg_loop(environ->graph);
+ ir_loop *l = loop;
+ ir_loop *last = NULL;
+
+ while(l != outer) {
+ last = l;
+ l = get_loop_outer_loop(l);
+ }
+ return last;
+}
+
+/**
+ * Topologic bottom-up walker sets links of infinite loops to non-zero.
+ * Block marks are used to flag blocks reachable (from end) on the one hand,
+ * on the other hand they are set if the block is not part of an infinite loop.
+ */
+static void infinite_loop_walker(ir_node *block, void *env)
+{
+ int arity;
+ int i;
+ (void) env;
+
+ if (! is_Block(block))
+ return;
+
+ /* start block has no predecessors */
+ if (block == environ->start_block)
+ return;
+
+ arity = get_irn_arity(block);
+
+ /* block not part of a real loop: no infinite loop */
+ if (get_irn_loop(block) == get_irg_loop(environ->graph))
+ set_Block_mark(block, 1);
+
+ if (get_Block_mark(block)) {
+ /* reachable block: mark all cf predecessors */
+ for (i = 0; i < arity; ++i) {
+ ir_node *pred = get_Block_cfgpred_block(block, i);
+ if (is_Bad(pred))
+ continue;
+ set_Block_mark(pred, 1);
+ }
+ } else {
+ /* We are in a real loop and see an unreachable block. */
+ ir_loop *outermost_loop = get_loop_outermost(get_irn_loop(block));
+
+ /* flag loop as infinite */
+ set_loop_link(outermost_loop, outermost_loop);
+ DEBUG_ONLY(inc_stats(gvnpre_stats->infinite_loops);)
+
+ /* The cf predecessors are unreachable, but can never be part of
+ an infinite loop, because we just reached them. So we set the
+ blockmark to prevent triggering the infinite loop detection. */
+
+ /* passing information to the cf predecessors */
+ for (i = 0; i < arity; ++i) {
+ ir_node *pred = get_Block_cfgpred_block(block, i);
+
+ if (is_Bad(pred))
+ continue;
+
+ /* If our cf predecessor is in the same endless loop,
+ it is also unreachable. */
+ if (in_loop(pred, outermost_loop)) {
+ set_Block_mark(pred, 0);
+ } else {
+ /* When we leave the unreachable loop, we artificially
+ declare the cf predecessor reachable. */
+ set_Block_mark(pred, 1);
+ }
+ }
+ }
+}
+
+/**
+ * Sets loop links of outermost infinite loops to non-zero.
+ */
+static void analyse_loops(ir_graph *irg)
+{
+ ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK);
+
+ /* reset block mark and loop links */
+ irg_walk_blkwise_graph(irg, clear_block_mark_loop_link, NULL, NULL);
+
+ /* mark end block reachable */
+ set_Block_mark(get_irg_end_block(irg), 1);
+ irg_walk_blkwise_graph(irg, infinite_loop_walker, NULL, NULL);
+
+ ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK);
+}
+
+#if IGNORE_INF_LOOPS || NO_INF_LOOPS
+/**
+ * Returns non-zero if block is part of an infinite loop.
+ */
+static unsigned is_in_infinite_loop(ir_node *block)
+{
+ ir_loop *loop;
+
+ assert(is_Block(block));
+ loop = get_irn_loop(block);
+ assert(loop);
+
+ loop = get_loop_outermost(loop);
+ if (loop)
+ return (get_loop_link(loop) != NULL);
+ else
+ return 0;
+}
+#endif
+
+/* --------------------------------------------------------
+ * GVN-PRE Exp_gen
+ * --------------------------------------------------------
+ */
+
+/**
+ * Returns non-zero if a node is movable and a possible candidate for PRE.