nsz Git - libfirm/blob - ir/ir/irgopt.c

   1 /* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
   2 ** All rights reserved.
   3 **
   4 ** Author: Christian Schaefer
   5 **
   6 ** Optimizations for a whole ir graph, i.e., a procedure.
   7 */
   8
   9 #ifdef HAVE_CONFIG_H
  10 # include <config.h>
  11 #endif
  12
  13 # include <assert.h>
  14
  15 # include "irgopt.h"
  16 # include "irnode_t.h"
  17 # include "irgraph_t.h"
  18 # include "iropt.h"
  19 # include "irgwalk.h"
  20 # include "ircons.h"
  21 # include "misc.h"
  22 # include "irgmod.h"
  23
  24 # include "pset.h"
  25 pset *new_identities (void);
  26 void  del_identities (pset *value_table);
  27 void  add_identity   (pset *value_table, ir_node *node);
  28
  29
  30 /* To fill the hash table */
  31 void
  32 add_identity (pset *value_table, ir_node *n) {
  33   /* identify_remember (value_table, n);*/
  34 }
  35
  36 /********************************************************************/
  37 /* apply optimizations of iropt to all nodes.                       */
  38 /********************************************************************/
  39
  40 void
  41 optimize_in_place_wrapper (ir_node *n, void *env) {
  42   int i;
  43   ir_node *optimized;
  44
  45   /* optimize all sons after recursion, i.e., the sons' sons are
  46      optimized already. */
  47   for (i = -1; i < get_irn_arity(n); i++) {
  48     optimized = optimize_in_place(get_irn_n(n, i));
  49     set_irn_n(n, i, optimized);
  50   }
  51 }
  52
  53 void
  54 local_optimize_graph (ir_graph *irg) {
  55   ir_graph *rem = current_ir_graph;
  56   current_ir_graph = irg;
  57
  58   /* Should we clean the value_table in irg for the cse? Better do so... */
  59   del_identities(irg->value_table);
  60   irg->value_table = new_identities();
  61
  62   /* walk over the graph */
  63   irg_walk(irg->end, NULL, optimize_in_place_wrapper, NULL);
  64
  65   current_ir_graph = rem;
  66 }
  67
  68 /********************************************************************/
  69 /* Routines for dead node elimination / copying garbage collection  */
  70 /* of the obstack.                                                  */
  71 /********************************************************************/
  72
  73 /* Remeber the new node in the old node by using a field all nodes have. */
  74 inline void
  75 set_new_node (ir_node *old, ir_node *new)
  76 {
  77   old->link = new;
  78 }
  79
  80 /* Get this new node, before the old node is forgotton.*/
  81 inline ir_node *
  82 get_new_node (ir_node * n)
  83 {
  84   return n->link;
  85 }
  86
  87
  88 /* We use the block_visited flag to mark that we have computed the
  89    number of useful predecessors for this block.
  90    Further we encode the new arity in this flag in the old blocks.
  91    Remembering the arity is useful, as it saves a lot of pointer
  92    accesses.  This function is called for all Phi and Block nodes
  93    in a Block. */
  94 inline int
  95 compute_new_arity(ir_node *b) {
  96   int i, res;
  97   int irg_v, block_v;
  98
  99   irg_v = get_irg_block_visited(current_ir_graph);
 100   block_v = get_Block_block_visited(b);
 101   if (block_v >= irg_v) {
 102     /* we computed the number of preds for this block and saved it in the
 103        block_v flag */
 104     return block_v - irg_v;
 105   } else {
 106     /* compute the number of good predecessors */
 107     res = get_irn_arity(b);
 108     for (i = 0; i < get_irn_arity(b); i++)
 109       if (get_irn_opcode(get_irn_n(b, i)) == iro_Bad) res--;
 110     /* save it in the flag. */
 111     set_Block_block_visited(b, irg_v + res);
 112     return res;
 113   }
 114 }
 115
 116 /* Copies the node to the new obstack. The Ins of the new node point to
 117    the predecessors on the old obstack.  n->link points to the new node.
 118    For Phi and Block nodes the function allocates in-arrays with an arity
 119    only for useful predecessors.  The arity is determined by counting
 120    the non-bad predecessors of the block. */
 121 inline void
 122 copy_node (ir_node *n, void *env) {
 123   ir_node *nn, *block;
 124   int new_arity;
 125
 126   if (get_irn_opcode(n) == iro_Block) {
 127     block = NULL;
 128     new_arity = compute_new_arity(n);
 129   } else {
 130     block = get_nodes_Block(n);
 131     if (get_irn_opcode(n) == iro_Phi) {
 132       new_arity = compute_new_arity(block);
 133     } else {
 134       new_arity = get_irn_arity(n);
 135     }
 136   }
 137   nn = new_ir_node(current_ir_graph,
 138                    block,
 139                    get_irn_op(n),
 140                    get_irn_mode(n),
 141                    new_arity,
 142                    get_irn_in(n));
 143   /* Copy the attributes.  These might point to additional data.  If this
 144      was allocated on the old obstack the pointers now are dangling.  This
 145      frees e.g. the memory of the graph_arr allocated in new_immBlock. */
 146   copy_attrs(n, nn);
 147   set_new_node(n, nn);
 148 }
 149
 150 /* Copies new predecessors of old node to new node remembered in link.
 151    Spare the Bad predecessors of Phi and Block nodes. */
 152 inline void
 153 copy_preds (ir_node *n, void *env) {
 154   ir_node *nn, *block, *on;
 155   int i, j;
 156
 157   nn = get_new_node(n);
 158
 159   if (get_irn_opcode(n) == iro_Block) {
 160     /* Don't copy Bad nodes. */
 161     j = 0;
 162     for (i = 0; i < get_irn_arity(n); i++)
 163       if (get_irn_opcode(get_irn_n(n, i)) != iro_Bad) {
 164         set_irn_n (nn, j, get_new_node(get_irn_n(n, i)));
 165         j++;
 166       }
 167     /* repair the block visited flag from above misuse */
 168     set_Block_block_visited(nn, 0);
 169     /* Local optimization could not merge two subsequent blocks if
 170        in array contained Bads.  Now it's possible, but don't do it for
 171        the end block!  */
 172     /* GL: this is inefficient!!
 173     if (n != current_ir_graph->end_block)  on = optimize_in_place(nn);
 174     else on = nn;
 175     if (nn != on) exchange(nn, on);
 176     better: */
 177     if (n != current_ir_graph->end_block) {
 178       on = optimize_in_place(nn);
 179       if (nn != on) exchange(nn, on);
 180       nn = on;  /* For cse ... */
 181     }
 182   } else if (get_irn_opcode(n) == iro_Phi) {
 183     /* Don't copy node if corresponding predecessor in block is Bad.
 184        The Block itself should not be Bad. */
 185     block = get_nodes_Block(n);
 186     set_irn_n (nn, -1, get_new_node(block));
 187     j = 0;
 188     for (i = 0; i < get_irn_arity(n); i++)
 189       if (get_irn_opcode(get_irn_n(block, i)) != iro_Bad) {
 190         set_irn_n (nn, j, get_new_node(get_irn_n(n, i)));
 191         j++;
 192       }
 193     /* Compacting the Phi's ins might generate Phis with only one
 194        predecessor. */
 195     if (get_irn_arity(n) == 1)
 196       exchange(n, get_irn_n(n, 0));
 197   } else {
 198     for (i = -1; i < get_irn_arity(n); i++)
 199       set_irn_n (nn, i, get_new_node(get_irn_n(n, i)));
 200   }
 201   /* Now the new node is complete.  We can add it to the hash table for cse. */
 202   add_identity (current_ir_graph->value_table, nn);
 203 }
 204
 205 /* Copies the graph reachable from current_ir_graph->end to the obstack
 206    in current_ir_graph.
 207    Then fixes the fields in current_ir_graph containing nodes of the
 208    graph.  */
 209 void
 210 copy_graph () {
 211
 212   ir_node *old, *new;
 213
 214   /* Not all nodes remembered in current_ir_graph might be reachable
 215      from the end node.  Assure their link is set to NULL, so that
 216      we can test whether new nodes have been computed. */
 217   set_irn_link(get_irg_frame  (current_ir_graph), NULL);
 218   set_irn_link(get_irg_globals(current_ir_graph), NULL);
 219   set_irn_link(get_irg_args   (current_ir_graph), NULL);
 220
 221   /* we use the block walk flag for removing Bads from Blocks ins. */
 222   inc_irg_block_visited(current_ir_graph);
 223
 224   /* copy the graph */
 225   irg_walk(get_irg_end(current_ir_graph), copy_node, copy_preds, NULL);
 226
 227   /* fix the fields in current_ir_graph */
 228   set_irg_end        (current_ir_graph, get_new_node(get_irg_end(current_ir_graph)));
 229   set_irg_end_block  (current_ir_graph, get_new_node(get_irg_end_block(current_ir_graph)));
 230   if (get_irn_link(get_irg_frame(current_ir_graph)) == NULL) {
 231     copy_node (get_irg_frame(current_ir_graph), NULL);
 232     copy_preds(get_irg_frame(current_ir_graph), NULL);
 233   }
 234   if (get_irn_link(get_irg_globals(current_ir_graph)) == NULL) {
 235     copy_node (get_irg_globals(current_ir_graph), NULL);
 236     copy_preds(get_irg_globals(current_ir_graph), NULL);
 237   }
 238   if (get_irn_link(get_irg_args(current_ir_graph)) == NULL) {
 239     copy_node (get_irg_args(current_ir_graph), NULL);
 240     copy_preds(get_irg_args(current_ir_graph), NULL);
 241   }
 242   set_irg_start  (current_ir_graph, get_new_node(get_irg_start(current_ir_graph)));
 243
 244   set_irg_start_block(current_ir_graph,
 245                       get_new_node(get_irg_start_block(current_ir_graph)));
 246   set_irg_frame  (current_ir_graph, get_new_node(get_irg_frame(current_ir_graph)));
 247   set_irg_globals(current_ir_graph, get_new_node(get_irg_globals(current_ir_graph)));
 248   set_irg_args   (current_ir_graph, get_new_node(get_irg_args(current_ir_graph)));
 249   if (get_irn_link(get_irg_bad(current_ir_graph)) == NULL) {
 250     copy_node(get_irg_bad(current_ir_graph), NULL);
 251     copy_preds(get_irg_bad(current_ir_graph), NULL);
 252   }
 253   set_irg_bad(current_ir_graph, get_new_node(get_irg_bad(current_ir_graph)));
 254 }
 255
 256 /* Copies all reachable nodes to a new obstack.  Removes bad inputs
 257    from block nodes and the corresponding inputs from Phi nodes.
 258    Merges single exit blocks with single entry blocks and removes
 259    1-input Phis.
 260    Adds all new nodes to a new hash table for cse.  Does not
 261    perform cse, so the hash table might contain common subexpressions. */
 262 /* Amroq call this emigrate() */
 263 void
 264 dead_node_elimination(ir_graph *irg) {
 265   ir_graph *rem;
 266   struct obstack *graveyard_obst = NULL;
 267   struct obstack *rebirth_obst   = NULL;
 268
 269   /* Remember external state of current_ir_graph. */
 270   rem = current_ir_graph;
 271   current_ir_graph = irg;
 272
 273   if (get_optimize() && get_opt_dead_node_elimination()) {
 274
 275     /* A quiet place, where the old obstack can rest in peace,
 276        until it will be cremated. */
 277     graveyard_obst = irg->obst;
 278
 279     /* A new obstack, where the reachable nodes will be copied to. */
 280     rebirth_obst = (struct obstack *) xmalloc (sizeof (struct obstack));
 281     current_ir_graph->obst = rebirth_obst;
 282     obstack_init (current_ir_graph->obst);
 283
 284     /* We also need a new hash table for cse */
 285     del_identities (irg->value_table);
 286     irg->value_table = new_identities ();
 287
 288     /* Copy the graph from the old to the new obstack */
 289     copy_graph();
 290
 291     /* Free memory from old unoptimized obstack */
 292     obstack_free(graveyard_obst, 0);  /* First empty the obstack ... */
 293     xfree (graveyard_obst);           /* ... then free it.           */
 294   }
 295
 296   current_ir_graph = rem;
 297 }