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];
  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         int       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_NOT_IRG_MANAGED+1; i < PHASE_LAST; i++) {
  74                 ir_phase *phase = get_irg_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 current_ir_graph->end to the obstack
  89  * in current_ir_graph and fixes the environment.
  90  * Then fixes the fields in current_ir_graph containing nodes of the
  91  * graph.
  92  *
  93  * @param copy_node_nr  If non-zero, the node number will be copied
  94  */
  95 static void copy_graph_env(ir_graph *irg)
  96 {
  97         ir_node  *new_anchor;
  98         int i;
  99
 100         /* init the new_phases array */
 101         for (i = PHASE_NOT_IRG_MANAGED+1; i < PHASE_LAST; i++) {
 102                 ir_phase *old_ph = get_irg_phase(irg, i);
 103                 if (old_ph == NULL) {
 104                         new_phases[i] = NULL;
 105                 } else {
 106                         new_phases[i] = xmalloc(sizeof(ir_phase));
 107                         phase_init(new_phases[i], "", irg, old_ph->growth_factor,
 108                                         old_ph->data_init, old_ph->priv);
 109                 }
 110         }
 111
 112         /* copy nodes */
 113         irg_walk_anchors(irg, copy_node_dce, rewire_inputs, NULL);
 114
 115         /* fix the anchor */
 116         new_anchor = get_irn_link(irg->anchor);
 117         assert(new_anchor != NULL);
 118         irg->anchor = new_anchor;
 119
 120         /* copy the new phases into the irg */
 121         for (i = PHASE_NOT_IRG_MANAGED+1; i < PHASE_LAST; i++) {
 122                 ir_phase *old_ph = get_irg_phase(irg, i);
 123                 if (old_ph == NULL)
 124                         continue;
 125
 126                 free_irg_phase(irg, i);
 127                 irg->phases[i] = new_phases[i];
 128         }
 129 }
 130
 131 /**
 132  * Copies all reachable nodes to a new obstack.  Removes bad inputs
 133  * from block nodes and the corresponding inputs from Phi nodes.
 134  * Merges single exit blocks with single entry blocks and removes
 135  * 1-input Phis.
 136  * Adds all new nodes to a new hash table for CSE.  Does not
 137  * perform CSE, so the hash table might contain common subexpressions.
 138  */
 139 void dead_node_elimination(ir_graph *irg)
 140 {
 141         ir_graph *rem;
 142 #ifdef INTERPROCEDURAL_VIEW
 143         int rem_ipview = get_interprocedural_view();
 144 #endif
 145         struct obstack *graveyard_obst = NULL;
 146         struct obstack *rebirth_obst   = NULL;
 147
 148         edges_deactivate(irg);
 149
 150         /* inform statistics that we started a dead-node elimination run */
 151         hook_dead_node_elim(irg, 1);
 152
 153         /* Remember external state of current_ir_graph. */
 154         rem = current_ir_graph;
 155         current_ir_graph = irg;
 156 #ifdef INTERPROCEDURAL_VIEW
 157         set_interprocedural_view(0);
 158 #endif
 159
 160         assert(get_irg_phase_state(irg) != phase_building);
 161
 162         /* Handle graph state */
 163         free_callee_info(irg);
 164         free_irg_outs(irg);
 165         free_trouts();
 166         free_loop_information(irg);
 167         set_irg_doms_inconsistent(irg);
 168
 169         /* A quiet place, where the old obstack can rest in peace,
 170            until it will be cremated. */
 171         graveyard_obst = irg->obst;
 172
 173         /* A new obstack, where the reachable nodes will be copied to. */
 174         rebirth_obst = XMALLOC(struct obstack);
 175         irg->obst = rebirth_obst;
 176         obstack_init(irg->obst);
 177         irg->last_node_idx = 0;
 178
 179         /* We also need a new value table for CSE */
 180         del_identities(irg->value_table);
 181         irg->value_table = new_identities();
 182
 183         /* Copy the graph from the old to the new obstack */
 184         copy_graph_env(irg);
 185
 186         /* Free memory from old unoptimized obstack */
 187         obstack_free(graveyard_obst, 0);  /* First empty the obstack ... */
 188         xfree(graveyard_obst);            /* ... then free it.           */
 189
 190         /* inform statistics that the run is over */
 191         hook_dead_node_elim(irg, 0);
 192
 193         current_ir_graph = rem;
 194 #ifdef INTERPROCEDURAL_VIEW
 195         set_interprocedural_view(rem_ipview);
 196 #endif
 197 }
 198
 199 ir_graph_pass_t *dead_node_elimination_pass(const char *name)
 200 {
 201         return def_graph_pass(name ? name : "dce", dead_node_elimination);
 202 }
 203
 204
 205 /*
 206    __                      _  __ __
 207   (_     __    o     _    | \/  |_
 208   __)|_| | \_/ | \_/(/_   |_/\__|__
 209
 210   The following stuff implements a facility that automatically patches
 211   registered ir_node pointers to the new node when a dead node elimination occurs.
 212
 213
 214   Warning: This is considered a hack - try hard to avoid this!
 215 */
 216
 217 struct _survive_dce_t {
 218         struct obstack obst;
 219         pmap *places;
 220         pmap *new_places;
 221         hook_entry_t dead_node_elim;
 222         hook_entry_t dead_node_elim_subst;
 223 };
 224
 225 typedef struct _survive_dce_list_t {
 226         struct _survive_dce_list_t *next;
 227         ir_node **place;
 228 } survive_dce_list_t;
 229
 230 static void dead_node_hook(void *context, ir_graph *irg, int start)
 231 {
 232         survive_dce_t *sd = context;
 233         (void) irg;
 234
 235         /* Create a new map before the dead node elimination is performed. */
 236         if (start) {
 237                 sd->new_places = pmap_create_ex(pmap_count(sd->places));
 238         } else {
 239                 /* Patch back all nodes if dead node elimination is over and something is to be done. */
 240                 pmap_destroy(sd->places);
 241                 sd->places     = sd->new_places;
 242                 sd->new_places = NULL;
 243         }
 244 }
 245
 246 /**
 247  * Hook called when dead node elimination replaces old by nw.
 248  */
 249 static void dead_node_subst_hook(void *context, ir_graph *irg, ir_node *old, ir_node *nw)
 250 {
 251         survive_dce_t *sd = context;
 252         survive_dce_list_t *list = pmap_get(sd->places, old);
 253         (void) irg;
 254
 255         /* If the node is to be patched back, write the new address to all registered locations. */
 256         if (list) {
 257                 survive_dce_list_t *p;
 258
 259                 for (p = list; p; p = p->next)
 260                         *(p->place) = nw;
 261
 262                 pmap_insert(sd->new_places, nw, list);
 263         }
 264 }
 265
 266 /**
 267  * Make a new Survive DCE environment.
 268  */
 269 survive_dce_t *new_survive_dce(void)
 270 {
 271         survive_dce_t *res = XMALLOC(survive_dce_t);
 272         obstack_init(&res->obst);
 273         res->places     = pmap_create();
 274         res->new_places = NULL;
 275
 276         res->dead_node_elim.hook._hook_dead_node_elim = dead_node_hook;
 277         res->dead_node_elim.context                   = res;
 278         res->dead_node_elim.next                      = NULL;
 279
 280         res->dead_node_elim_subst.hook._hook_dead_node_elim_subst = dead_node_subst_hook;
 281         res->dead_node_elim_subst.context = res;
 282         res->dead_node_elim_subst.next    = NULL;
 283
 284         register_hook(hook_dead_node_elim, &res->dead_node_elim);
 285         register_hook(hook_dead_node_elim_subst, &res->dead_node_elim_subst);
 286         return res;
 287 }
 288
 289 /**
 290  * Free a Survive DCE environment.
 291  */
 292 void free_survive_dce(survive_dce_t *sd)
 293 {
 294         obstack_free(&sd->obst, NULL);
 295         pmap_destroy(sd->places);
 296         unregister_hook(hook_dead_node_elim, &sd->dead_node_elim);
 297         unregister_hook(hook_dead_node_elim_subst, &sd->dead_node_elim_subst);
 298         xfree(sd);
 299 }
 300
 301 /**
 302  * Register a node pointer to be patched upon DCE.
 303  * When DCE occurs, the node pointer specified by @p place will be
 304  * patched to the new address of the node it is pointing to.
 305  *
 306  * @param sd    The Survive DCE environment.
 307  * @param place The address of the node pointer.
 308  */
 309 void survive_dce_register_irn(survive_dce_t *sd, ir_node **place)
 310 {
 311         if (*place != NULL) {
 312                 ir_node *irn      = *place;
 313                 survive_dce_list_t *curr = pmap_get(sd->places, irn);
 314                 survive_dce_list_t *nw   = OALLOC(&sd->obst, survive_dce_list_t);
 315
 316                 nw->next  = curr;
 317                 nw->place = place;
 318
 319                 pmap_insert(sd->places, irn, nw);
 320         }
 321 }