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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief    Dead node elimination
  23  * @author   Michael Beck, Goetz Lindenmaier
  24  * @version  $Id: opt_inline.c 27265 2010-03-07 15:13:00Z matze $
  25  *
  26  * Strictly speaking dead node elimination is unnecessary in firm - everthying
  27  * which is not used can't be found by any walker.
  28  * The only drawback is that the nodes still take up memory. This phase fixes
  29  * this by copying all (reachable) nodes to a new obstack and throwing away
  30  * the old one.
  31  */
  32 #include "config.h"
  33
  34 #include "iroptimize.h"
  35 #include "irnode_t.h"
  36 #include "irgraph_t.h"
  37 #include "irphase_t.h"
  38 #include "iredges_t.h"
  39 #include "irhooks.h"
  40 #include "irtools.h"
  41 #include "irgwalk.h"
  42 #include "cgana.h"
  43 #include "irouts.h"
  44 #include "trouts.h"
  45 #include "iropt_t.h"
  46 #include "irpass.h"
  47 #include "pmap.h"
  48
  49 /** a pointer to the new phases */
  50 static ir_phase *new_phases[PHASE_LAST + 1];
  51
  52 /**
  53  * Reroute the inputs of a node from nodes in the old graph to copied nodes in
  54  * the new graph
  55  */
  56 static void rewire_inputs(ir_node *node, void *env)
  57 {
  58         (void) env;
  59         irn_rewire_inputs(node);
  60 }
  61
  62 static void copy_node_dce(ir_node *node, void *env)
  63 {
  64         ir_phase_id i;
  65         ir_node    *new_node = exact_copy(node);
  66         ir_graph   *irg      = get_irn_irg(new_node);
  67         (void) env;
  68
  69         /* preserve the node numbers for easier debugging */
  70         new_node->node_nr = node->node_nr;
  71
  72         /* copy phase information for this node */
  73         for (i = PHASE_FIRST; i <= PHASE_LAST; ++i) {
  74                 ir_phase *phase = irg_get_phase(irg, i);
  75                 if (phase == NULL)
  76                         continue;
  77                 if (!phase_get_irn_data(phase, node))
  78                         continue;
  79                 phase_set_irn_data(new_phases[i], new_node,
  80                                    phase_get_irn_data(phase, node));
  81         }
  82
  83         set_irn_link(node, new_node);
  84         hook_dead_node_elim_subst(irg, node, new_node);
  85 }
  86
  87 /**
  88  * Copies the graph reachable from the End node to the obstack
  89  * in irg. Then fixes the fields containing nodes of the graph.
  90  *
  91  * @param copy_node_nr  If non-zero, the node number will be copied
  92  */
  93 static void copy_graph_env(ir_graph *irg)
  94 {
  95         ir_node    *new_anchor;
  96         ir_phase_id i;
  97
  98         /* init the new_phases array */
  99         /* TODO: this is wrong, it should only allocate a new data_ptr inside
 100          * the phase! */
 101         for (i = PHASE_FIRST; i <= PHASE_LAST; ++i) {
 102                 ir_phase *old_ph = irg_get_phase(irg, i);
 103                 if (old_ph == NULL) {
 104                         new_phases[i] = NULL;
 105                 } else {
 106                         new_phases[i] = new_phase(irg, old_ph->data_init);
 107                         new_phases[i]->priv = old_ph->priv;
 108                 }
 109         }
 110
 111         /* copy nodes */
 112         irg_walk_anchors(irg, copy_node_dce, rewire_inputs, NULL);
 113
 114         /* fix the anchor */
 115         new_anchor = (ir_node*)get_irn_link(irg->anchor);
 116         assert(new_anchor != NULL);
 117         irg->anchor = new_anchor;
 118
 119         /* copy the new phases into the irg */
 120         for (i = PHASE_FIRST; i <= PHASE_LAST; ++i) {
 121                 ir_phase *old_ph = irg_get_phase(irg, i);
 122                 if (old_ph == NULL)
 123                         continue;
 124
 125                 /* Matze: commented out for now: This is a memory leak, but for a real
 126                  * fix we must not create new phases here, but reuse the old phases
 127                  * and just create a new data array */
 128                 /* phase_free(old_ph); */
 129                 irg->phases[i] = new_phases[i];
 130         }
 131 }
 132
 133 /**
 134  * Copies all reachable nodes to a new obstack.  Removes bad inputs
 135  * from block nodes and the corresponding inputs from Phi nodes.
 136  * Merges single exit blocks with single entry blocks and removes
 137  * 1-input Phis.
 138  * Adds all new nodes to a new hash table for CSE.  Does not
 139  * perform CSE, so the hash table might contain common subexpressions.
 140  */
 141 void dead_node_elimination(ir_graph *irg)
 142 {
 143         struct obstack *graveyard_obst = NULL;
 144         struct obstack *rebirth_obst   = NULL;
 145
 146         edges_deactivate(irg);
 147
 148         /* inform statistics that we started a dead-node elimination run */
 149         hook_dead_node_elim(irg, 1);
 150
 151         assert(get_irg_phase_state(irg) != phase_building);
 152
 153         /* Handle graph state */
 154         free_callee_info(irg);
 155         free_irg_outs(irg);
 156         free_trouts();
 157         free_loop_information(irg);
 158         set_irg_doms_inconsistent(irg);
 159
 160         /* A quiet place, where the old obstack can rest in peace,
 161            until it will be cremated. */
 162         graveyard_obst = irg->obst;
 163
 164         /* A new obstack, where the reachable nodes will be copied to. */
 165         rebirth_obst = XMALLOC(struct obstack);
 166         irg->obst = rebirth_obst;
 167         obstack_init(irg->obst);
 168         irg->last_node_idx = 0;
 169
 170         /* We also need a new value table for CSE */
 171         new_identities(irg);
 172
 173         /* Copy the graph from the old to the new obstack */
 174         copy_graph_env(irg);
 175
 176         /* Free memory from old unoptimized obstack */
 177         obstack_free(graveyard_obst, 0);  /* First empty the obstack ... */
 178         xfree(graveyard_obst);            /* ... then free it.           */
 179
 180         /* inform statistics that the run is over */
 181         hook_dead_node_elim(irg, 0);
 182 }
 183
 184 ir_graph_pass_t *dead_node_elimination_pass(const char *name)
 185 {
 186         return def_graph_pass(name ? name : "dce", dead_node_elimination);
 187 }