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  *
  25  * Strictly speaking dead node elimination is unnecessary in firm - everthying
  26  * which is not used can't be found by any walker.
  27  * The only drawback is that the nodes still take up memory. This phase fixes
  28  * this by copying all (reachable) nodes to a new obstack and throwing away
  29  * the old one.
  30  */
  31 #include "config.h"
  32
  33 #include "iroptimize.h"
  34 #include "irnode_t.h"
  35 #include "irgraph_t.h"
  36 #include "iredges_t.h"
  37 #include "irhooks.h"
  38 #include "irtools.h"
  39 #include "irgwalk.h"
  40 #include "cgana.h"
  41 #include "irouts.h"
  42 #include "trouts.h"
  43 #include "iropt_t.h"
  44 #include "irpass.h"
  45 #include "pmap.h"
  46
  47 /**
  48  * Reroute the inputs of a node from nodes in the old graph to copied nodes in
  49  * the new graph
  50  */
  51 static void rewire_inputs(ir_node *node, void *env)
  52 {
  53         (void) env;
  54         irn_rewire_inputs(node);
  55 }
  56
  57 static void copy_node_dce(ir_node *node, void *env)
  58 {
  59         ir_node  *new_node = exact_copy(node);
  60         ir_graph *irg      = get_irn_irg(new_node);
  61         (void) env;
  62
  63         /* preserve the node numbers for easier debugging */
  64         new_node->node_nr = node->node_nr;
  65
  66         set_irn_link(node, new_node);
  67         hook_dead_node_elim_subst(irg, node, new_node);
  68 }
  69
  70 /**
  71  * Copies the graph reachable from the End node to the obstack
  72  * in irg. Then fixes the fields containing nodes of the graph.
  73  *
  74  * @param copy_node_nr  If non-zero, the node number will be copied
  75  */
  76 static void copy_graph_env(ir_graph *irg)
  77 {
  78         ir_node *anchor = irg->anchor;
  79         ir_node *new_anchor;
  80
  81         /* copy nodes */
  82         irg_walk_in_or_dep(anchor, copy_node_dce, rewire_inputs, NULL);
  83
  84         /* fix the anchor */
  85         new_anchor = (ir_node*)get_irn_link(anchor);
  86         assert(new_anchor != NULL);
  87         irg->anchor = new_anchor;
  88 }
  89
  90 /**
  91  * Copies all reachable nodes to a new obstack.  Removes bad inputs
  92  * from block nodes and the corresponding inputs from Phi nodes.
  93  * Merges single exit blocks with single entry blocks and removes
  94  * 1-input Phis.
  95  * Adds all new nodes to a new hash table for CSE.  Does not
  96  * perform CSE, so the hash table might contain common subexpressions.
  97  */
  98 void dead_node_elimination(ir_graph *irg)
  99 {
 100         struct obstack *graveyard_obst = NULL;
 101         struct obstack *rebirth_obst   = NULL;
 102
 103         edges_deactivate(irg);
 104
 105         /* inform statistics that we started a dead-node elimination run */
 106         hook_dead_node_elim(irg, 1);
 107
 108         assert(get_irg_phase_state(irg) != phase_building);
 109
 110         /* Handle graph state */
 111         free_callee_info(irg);
 112         free_irg_outs(irg);
 113         free_trouts();
 114         free_loop_information(irg);
 115         free_vrp_data(irg);
 116         clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
 117
 118         /* A quiet place, where the old obstack can rest in peace,
 119            until it will be cremated. */
 120         graveyard_obst = irg->obst;
 121
 122         /* A new obstack, where the reachable nodes will be copied to. */
 123         rebirth_obst = XMALLOC(struct obstack);
 124         irg->obst = rebirth_obst;
 125         obstack_init(irg->obst);
 126         irg->last_node_idx = 0;
 127
 128         /* We also need a new value table for CSE */
 129         new_identities(irg);
 130
 131         /* Copy the graph from the old to the new obstack */
 132         copy_graph_env(irg);
 133
 134         /* Free memory from old unoptimized obstack */
 135         obstack_free(graveyard_obst, 0);  /* First empty the obstack ... */
 136         xfree(graveyard_obst);            /* ... then free it.           */
 137
 138         /* inform statistics that the run is over */
 139         hook_dead_node_elim(irg, 0);
 140 }
 141
 142 ir_graph_pass_t *dead_node_elimination_pass(const char *name)
 143 {
 144         return def_graph_pass(name ? name : "dce", dead_node_elimination);
 145 }