+ * Allocate a new DAG entry.
+ */
+static dag_entry_t *new_dag_entry(dag_env_t *dag_env, ir_node *node) {
+ dag_entry_t *entry = obstack_alloc(&dag_env->obst, sizeof(*entry));
+
+ entry->num_nodes = 1;
+ entry->num_roots = 1;
+ entry->num_inner_nodes = 0;
+ entry->root = node;
+ entry->is_dead = 0;
+ entry->is_tree = 1;
+ entry->is_ext_ref = 0;
+ entry->next = dag_env->list_of_dags;
+ entry->link = NULL;
+
+ ++dag_env->num_of_dags;
+ dag_env->list_of_dags = entry;
+
+ set_irn_dag_entry(node, entry);
+ return entry;
+} /* new_dag_entry */
+
+/**
+ * Post-walker to detect DAG roots that are referenced form other blocks
+ */
+static void find_dag_roots(ir_node *node, void *env)
+{
+ dag_env_t *dag_env = env;
+ int i, arity;
+ dag_entry_t *entry;
+ ir_node *block;
+
+ if (is_Block(node))
+ return;
+
+ block = get_nodes_block(node);
+
+ /* ignore start end end blocks */
+ if (block == get_irg_start_block(current_ir_graph) ||
+ block == get_irg_end_block(current_ir_graph)) {
+ return;
+ } /* if */
+
+ /* Phi nodes always references nodes from "other" block */
+ if (is_Phi(node)) {
+ if (get_irn_mode(node) != mode_M) {
+ for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
+ ir_node *prev = get_irn_n(node, i);
+
+ if (is_Phi(prev))
+ continue;
+
+ if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
+ if (is_irn_constlike(prev))
+ continue;
+ } /* if */
+
+ entry = get_irn_dag_entry(prev);
+
+ if (! entry) {
+ /* found an unassigned node, a new root */
+ entry = new_dag_entry(dag_env, node);
+ entry->is_ext_ref = 1;
+ } /* if */
+ } /* for */
+ } /* if */
+ } else {
+
+ for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
+ ir_node *prev = get_irn_n(node, i);
+ ir_mode *mode = get_irn_mode(prev);
+
+ if (mode == mode_X || mode == mode_M)
+ continue;
+
+ if (is_Phi(prev))
+ continue;
+
+ if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
+ if (is_irn_constlike(prev))
+ continue;
+ } /* if */
+
+ if (get_nodes_block(prev) != block) {
+ /* The predecessor is from another block. It forms
+ a root. */
+ entry = get_irn_dag_entry(prev);
+ if (! entry) {
+ /* found an unassigned node, a new root */
+ entry = new_dag_entry(dag_env, node);
+ entry->is_ext_ref = 1;
+ } /* if */
+ } /* if */
+ } /* for */
+ } /* if */
+} /* find_dag_roots */
+
+/**
+ * Pre-walker for connecting DAGs and counting.