2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Dead node elimination
9 * @author Michael Beck, Goetz Lindenmaier
11 * Strictly speaking dead node elimination is unnecessary in firm - everthying
12 * which is not used can't be found by any walker.
13 * The only drawback is that the nodes still take up memory. This phase fixes
14 * this by copying all (reachable) nodes to a new obstack and throwing away
19 #include "iroptimize.h"
21 #include "irgraph_t.h"
22 #include "iredges_t.h"
34 * Reroute the inputs of a node from nodes in the old graph to copied nodes in
37 static void rewire_inputs(ir_node *node, void *env)
40 irn_rewire_inputs(node);
43 static void copy_node_dce(ir_node *node, void *env)
45 ir_node *new_node = exact_copy(node);
48 /* preserve the node numbers for easier debugging */
49 new_node->node_nr = node->node_nr;
51 set_irn_link(node, new_node);
55 * Copies the graph reachable from the End node to the obstack
56 * in irg. Then fixes the fields containing nodes of the graph.
58 * @param copy_node_nr If non-zero, the node number will be copied
60 static void copy_graph_env(ir_graph *irg)
62 ir_node *anchor = irg->anchor;
66 irg_walk_in_or_dep(anchor, copy_node_dce, rewire_inputs, NULL);
69 new_anchor = (ir_node*)get_irn_link(anchor);
70 assert(new_anchor != NULL);
71 irg->anchor = new_anchor;
75 * Copies all reachable nodes to a new obstack. Removes bad inputs
76 * from block nodes and the corresponding inputs from Phi nodes.
77 * Merges single exit blocks with single entry blocks and removes
79 * Adds all new nodes to a new hash table for CSE. Does not
80 * perform CSE, so the hash table might contain common subexpressions.
82 void dead_node_elimination(ir_graph *irg)
84 edges_deactivate(irg);
86 /* inform statistics that we started a dead-node elimination run */
87 hook_dead_node_elim(irg, 1);
89 /* Handle graph state */
90 free_callee_info(irg);
93 free_loop_information(irg);
95 clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
97 /* A quiet place, where the old obstack can rest in peace,
98 until it will be cremated. */
99 struct obstack graveyard_obst = irg->obst;
101 /* A new obstack, where the reachable nodes will be copied to. */
102 obstack_init(&irg->obst);
103 irg->last_node_idx = 0;
105 /* We also need a new value table for CSE */
108 /* Copy the graph from the old to the new obstack */
111 /* Free memory from old unoptimized obstack */
112 obstack_free(&graveyard_obst, 0); /* First empty the obstack ... */
114 /* inform statistics that the run is over */
115 hook_dead_node_elim(irg, 0);
118 ir_graph_pass_t *dead_node_elimination_pass(const char *name)
120 return def_graph_pass(name ? name : "dce", dead_node_elimination);