nsz Git - libfirm/blob - ir/opt/dead_code_elimination.c

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief    Dead node elimination
   9  * @author   Michael Beck, Goetz Lindenmaier
  10  *
  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
  15  * the old one.
  16  */
  17 #include "config.h"
  18
  19 #include "iroptimize.h"
  20 #include "irnode_t.h"
  21 #include "irgraph_t.h"
  22 #include "iredges_t.h"
  23 #include "irhooks.h"
  24 #include "irtools.h"
  25 #include "irgwalk.h"
  26 #include "cgana.h"
  27 #include "irouts.h"
  28 #include "trouts.h"
  29 #include "iropt_t.h"
  30 #include "irpass.h"
  31 #include "pmap.h"
  32
  33 /**
  34  * Reroute the inputs of a node from nodes in the old graph to copied nodes in
  35  * the new graph
  36  */
  37 static void rewire_inputs(ir_node *node, void *env)
  38 {
  39         (void) env;
  40         irn_rewire_inputs(node);
  41 }
  42
  43 static void copy_node_dce(ir_node *node, void *env)
  44 {
  45         ir_node  *new_node = exact_copy(node);
  46         (void) env;
  47
  48         /* preserve the node numbers for easier debugging */
  49         new_node->node_nr = node->node_nr;
  50
  51         set_irn_link(node, new_node);
  52 }
  53
  54 /**
  55  * Copies the graph reachable from the End node to the obstack
  56  * in irg. Then fixes the fields containing nodes of the graph.
  57  *
  58  * @param copy_node_nr  If non-zero, the node number will be copied
  59  */
  60 static void copy_graph_env(ir_graph *irg)
  61 {
  62         ir_node *anchor = irg->anchor;
  63         ir_node *new_anchor;
  64
  65         /* copy nodes */
  66         irg_walk_in_or_dep(anchor, copy_node_dce, rewire_inputs, NULL);
  67
  68         /* fix the anchor */
  69         new_anchor = (ir_node*)get_irn_link(anchor);
  70         assert(new_anchor != NULL);
  71         irg->anchor = new_anchor;
  72 }
  73
  74 /**
  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
  78  * 1-input Phis.
  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.
  81  */
  82 void dead_node_elimination(ir_graph *irg)
  83 {
  84         edges_deactivate(irg);
  85
  86         /* inform statistics that we started a dead-node elimination run */
  87         hook_dead_node_elim(irg, 1);
  88
  89         /* Handle graph state */
  90         free_callee_info(irg);
  91         free_irg_outs(irg);
  92         free_trouts();
  93         free_loop_information(irg);
  94         free_vrp_data(irg);
  95         clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
  96
  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;
 100
 101         /* A new obstack, where the reachable nodes will be copied to. */
 102         obstack_init(&irg->obst);
 103         irg->last_node_idx = 0;
 104
 105         /* We also need a new value table for CSE */
 106         new_identities(irg);
 107
 108         /* Copy the graph from the old to the new obstack */
 109         copy_graph_env(irg);
 110
 111         /* Free memory from old unoptimized obstack */
 112         obstack_free(&graveyard_obst, 0);  /* First empty the obstack ... */
 113
 114         /* inform statistics that the run is over */
 115         hook_dead_node_elim(irg, 0);
 116 }
 117
 118 ir_graph_pass_t *dead_node_elimination_pass(const char *name)
 119 {
 120         return def_graph_pass(name ? name : "dce", dead_node_elimination);
 121 }