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