+
+/**
+ * walks over the graph and collects all blocks and all block entries
+ */
+static void collect_walk(ir_node *node, blk_collect_data_t *env)
+{
+ int i, is_phi;
+ block_entry_t *entry;
+ ir_node *block;
+
+ mark_irn_visited(node);
+
+ if (node->op == op_Block) {
+ /* predecessors of a block are control flow nodes */
+ for (i = get_irn_arity(node) - 1; i >= 0; --i) {
+ ir_node *pred = get_irn_n(node, i);
+ ir_node *blk = get_nodes_block(pred);
+
+ if (irn_not_visited(pred)) {
+ collect_walk(pred, env);
+
+ /* control flow predecessors are always block inputs */
+ entry = block_find_entry(blk, env);
+ ARR_APP1(ir_node *, entry->entry_list, pred);
+ }
+ }
+
+ /* it's a block, put it into the block list */
+ if (node == get_irg_end_block(current_ir_graph)) {
+ /* Put the end block always last. If we don't do it here,
+ * it might be placed elsewhere if the graph contains
+ * endless loops.
+ */
+ }
+ else {
+ ARR_APP1(ir_node *, env->blk_list, node);
+ }
+ }
+ else {
+ block = get_nodes_block(node);
+
+ if (irn_not_visited(block))
+ collect_walk(block, env);
+
+ is_phi = is_Phi(node);
+ for (i = get_irn_arity(node) - 1; i >= 0; --i) {
+ ir_node *pred = get_irn_n(node, i);
+
+ if (irn_not_visited(pred)) {
+ collect_walk(pred, env);
+
+ /* BEWARE: predecessors of End nodes might be blocks */
+ if (is_no_Block(pred)) {
+ ir_node *blk = get_nodes_block(pred);
+
+ /*
+ * Note that Phi predecessors are always block entries
+ * because Phi edges are always "outside" a block
+ */
+ if (block != blk || is_phi) {
+ entry = block_find_entry(blk, env);
+ ARR_APP1(ir_node *, entry->entry_list, pred);
+ }
+ }
+ }
+ }
+ }
+}
+
+/**
+ * walks over the nodes of a block
+ * and collects them into the right list
+ */
+static void collect_blks_lists(ir_node *node, ir_node *block,
+ block_entry_t *entry, blk_collect_data_t *env)
+{
+ int i;
+
+ mark_irn_visited(node);
+
+ /*
+ * Do not descent into Phi predecessors, these are always
+ * outside the current block because Phi edges are always
+ * "outside".
+ */
+ if (! is_Phi(node)) {
+ for (i = get_irn_arity(node) - 1; i >= 0; --i) {
+ ir_node *pred = get_irn_n(node, i);
+
+ /* BEWARE: predecessors of End nodes might be blocks */
+ if (is_no_Block(pred)) {
+ ir_node *blk = get_nodes_block(pred);
+
+ if (irn_not_visited(pred)) {
+ if (block != blk)
+ continue;
+ collect_blks_lists(pred, block, entry, env);
+ }
+ }
+ }
+ }
+ else {
+ ARR_APP1(ir_node *, entry->phi_list, node);
+ return;
+ }
+
+ if (get_irn_mode(node) == mode_X) {
+ ARR_APP1(ir_node *, entry->cf_list, node);
+ }
+ else {
+ ARR_APP1(ir_node *, entry->df_list, node);
+ }
+}
+
+/**
+ * walk over the graph and collect all lists
+ */
+static void collect_lists(blk_collect_data_t *env)
+{
+ int i, j;
+ ir_node *block, *node;
+ block_entry_t *entry;
+
+ inc_irg_visited(current_ir_graph);
+
+ for (i = ARR_LEN(env->blk_list) - 1; i >= 0; --i) {
+ block = env->blk_list[i];
+ entry = block_find_entry(block, env);
+
+ for (j = ARR_LEN(entry->entry_list) - 1; j >= 0; --j) {
+ node = entry->entry_list[j];
+
+ /* a entry might already be visited due to Phi loops */
+ if (node->visited < current_ir_graph->visited)
+ collect_blks_lists(node, block, entry, env);
+ }
+ }
+}
+