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