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 **  dead node elemination
   7 **  walks one time through the whole graph and copies it into another graph,
   8 **  so unreachable nodes will be lost.
   9 */
  10
  11 # include "irgopt.h"
  12 # include "irnode.h"
  13 # include "iropt.h"
  14 # include "irgwalk.h"
  15 # include "irgraph.h"
  16 # include "ircons.h"
  17
  18 /********************************************************************/
  19 /* apply optimizations of iropt to all nodes.                       */
  20 void
  21 optimize_in_place_wrapper (ir_node *n, void *env) {
  22   int i;
  23   ir_node *optimized;
  24
  25   /* optimize all sons after recursion, i.e., the sons' sons are
  26      optimized already. */
  27   for (i = -1; i < get_irn_arity(n); i++) {
  28     optimized = optimize_in_place(get_irn_n(n, i));
  29     set_irn_n(n, i, optimized);
  30   }
  31 }
  32
  33
  34 void
  35 local_optimize_graph (ir_graph *irg) {
  36   ir_graph *rem = current_ir_graph;
  37   current_ir_graph = irg;
  38
  39   /* walk over the graph */
  40   irg_walk(irg->end, NULL, optimize_in_place_wrapper, NULL);
  41
  42   current_ir_graph = rem;
  43 }
  44
  45 /********************************************************************/
  46 /* Routines for dead node elimination / copying garbage collection  */
  47 /* of the obstack.                                                  */
  48
  49 /* Remeber the new node in the old node,
  50    by using a field that all nodes have. */
  51 void *
  52 set_new_node (ir_node *old, ir_node *new)
  53 {
  54   old->in[0] = new;
  55   return old;
  56 }
  57
  58 /* Get this new node, before the old node is forgotton.*/
  59 ir_node *
  60 get_new_node (ir_node * n)
  61 {
  62   ir_node *new;
  63   new = n->in[0];
  64   assert(new);
  65
  66   return n->in[0];
  67
  68 }
  69
  70 /* Create this node on a new obstack. */
  71 void
  72 copy_node (ir_node *n, void *env) {
  73   ir_node *res = NULL;
  74   ir_node *a = NULL;
  75   ir_node *b = NULL;
  76   int i;
  77
  78   assert (n);
  79
  80   if (is_binop(n)) {
  81     a = get_binop_left(n);
  82     b = get_binop_right(n);
  83   } else if (is_unop(n)) {
  84     a = get_unop_op(n);
  85   }
  86
  87   switch (get_irn_opcode(n)) {
  88   case iro_Block:
  89     {
  90       ir_node **in = get_Block_cfgpred_arr(n);
  91       for (i = 0; i < get_Block_n_cfgpreds(n); i++)
  92         set_Block_cfgpred(n, i, get_new_node(get_Block_cfgpred(n, i)));
  93       res = new_r_Block (current_ir_graph, get_Block_n_cfgpreds(n), in);
  94     }
  95     break;
  96   case iro_Start:
  97     res = new_r_Start (current_ir_graph, get_new_node(get_nodes_Block(n)));
  98     break;
  99   case iro_End:
 100     res = new_r_End (current_ir_graph, get_new_node(get_nodes_Block(n)));
 101     current_ir_graph -> end = res;
 102     current_ir_graph -> end_block = get_new_node(get_nodes_Block(n));
 103     break;
 104   case iro_Jmp:
 105     res = new_r_Jmp (current_ir_graph, get_new_node(get_nodes_Block(n)));
 106     break;
 107   case iro_Cond:
 108     res = new_r_Cond (current_ir_graph, get_new_node(get_nodes_Block(n)),
 109                       get_new_node(get_Cond_selector(n)));
 110     break;
 111   case iro_Return:
 112     {
 113       ir_node **in ;
 114       in = get_Return_res_arr(n);
 115       for (i = 0; i < get_Return_n_res(n); i++)
 116         set_Return_res(n, i, get_new_node(get_Return_res(n, i)));
 117       res = new_r_Return (current_ir_graph, get_new_node(get_nodes_Block(n)),
 118                           get_new_node(get_Return_mem(n)),
 119                           get_Return_n_res(n), in);
 120     }
 121     break;
 122   case iro_Raise:
 123     res = new_r_Raise (current_ir_graph, get_new_node(get_nodes_Block(n)),
 124                        get_new_node(get_Raise_mem(n)),
 125                        get_new_node(get_Raise_exo_ptr(n)));
 126     break;
 127   case iro_Const:
 128     res = new_r_Const (current_ir_graph, get_new_node(get_nodes_Block(n)),
 129                        get_irn_mode(n), get_Const_tarval(n));
 130     break;
 131   case iro_SymConst:
 132     {
 133       type_or_id *value = NULL;
 134
 135       if ((get_SymConst_kind(n)==type_tag) || (get_SymConst_kind(n)==size))
 136         {
 137
 138            value = (type_or_id *) get_SymConst_type(n);
 139         }
 140       else
 141         {
 142           if (get_SymConst_kind(n)==linkage_ptr_info)
 143           {
 144             value = (type_or_id *) get_SymConst_ptrinfo(n);
 145           }
 146         }
 147     res = new_r_SymConst (current_ir_graph, get_new_node(get_nodes_Block(n)),
 148                           value, get_SymConst_kind (n));
 149     }
 150     break;
 151   case iro_Sel:
 152     {
 153       ir_node **in = get_Sel_index_arr(n);
 154       res = new_r_Sel (current_ir_graph, get_new_node(get_nodes_Block(n)),
 155                        get_new_node(get_Sel_mem(n)),
 156                        get_new_node(get_Sel_ptr(n)), get_Sel_n_index(n),
 157                        in, get_Sel_entity(n));
 158     }
 159     break;
 160   case  iro_Call:
 161     {
 162       ir_node **in = get_Call_param_arr(n);
 163       res = new_r_Call (current_ir_graph, get_new_node(get_nodes_Block(n)),
 164                         get_new_node(get_Call_mem(n)),
 165                         get_new_node(get_Call_ptr(n)), get_Call_arity(n),
 166                         in, get_Call_type (n));
 167     }
 168     break;
 169   case iro_Add:
 170     res = new_r_Add (current_ir_graph, get_new_node(get_nodes_Block(n)),
 171                      get_new_node(a), get_new_node(b), get_irn_mode(n));
 172     break;
 173   case iro_Sub:
 174     {
 175       res = new_r_Sub (current_ir_graph, get_new_node(get_nodes_Block(n)),
 176                        get_new_node(a), get_new_node(b), get_irn_mode(n));
 177     }
 178     break;
 179   case iro_Minus:
 180     res = new_r_Minus (current_ir_graph, get_new_node(get_nodes_Block(n)),
 181                        get_new_node(a), get_irn_mode(n));
 182     break;
 183   case iro_Mul:
 184     res = new_r_Mul (current_ir_graph, get_new_node(get_nodes_Block(n)),
 185                      get_new_node(a), get_new_node(b), get_irn_mode(n));
 186     break;
 187   case iro_Quot:
 188     res = new_r_Quot (current_ir_graph, get_new_node(get_nodes_Block(n)),
 189                       get_new_node(get_Quot_mem(n)), get_new_node(a),
 190                       get_new_node(b));
 191     break;
 192   case iro_DivMod:
 193     res = new_r_DivMod (current_ir_graph, get_new_node(get_nodes_Block(n)),
 194                         get_new_node(get_DivMod_mem(n)), get_new_node(a),
 195                         get_new_node(b));
 196     break;
 197   case iro_Div:
 198     res = new_r_Div (current_ir_graph, get_new_node(get_nodes_Block(n)),
 199                      get_new_node(get_Div_mem(n)), get_new_node(a),
 200                      get_new_node(b));
 201     break;
 202   case iro_Mod:
 203     res = new_r_Mod (current_ir_graph, get_new_node(get_nodes_Block(n)),
 204                      get_new_node(get_Mod_mem(n)), get_new_node(a),
 205                      get_new_node(b));
 206     break;
 207   case iro_Abs:
 208     res = new_r_Abs (current_ir_graph, get_new_node(get_nodes_Block(n)),
 209                      get_new_node(get_Abs_op(n)), get_irn_mode(n));
 210     break;
 211   case iro_And:
 212     res = new_r_And (current_ir_graph, get_new_node(get_nodes_Block(n)),
 213                      get_new_node(a), get_new_node(b), get_irn_mode(n));
 214     break;
 215   case iro_Or:
 216     res = new_r_Or (current_ir_graph, get_new_node(get_nodes_Block(n)),
 217                     get_new_node(a), get_new_node(b), get_irn_mode(n));
 218     break;
 219   case iro_Eor:
 220     res = new_r_Eor (current_ir_graph, get_new_node(get_nodes_Block(n)),
 221                      get_new_node(a), get_new_node(b), get_irn_mode(n));
 222     break;
 223   case iro_Not:
 224     res = new_r_Not (current_ir_graph, get_new_node(get_nodes_Block(n)),
 225                      get_new_node(get_Not_op(n)), get_irn_mode(n));
 226     break;
 227   case iro_Cmp:
 228     res = new_r_Cmp (current_ir_graph, get_new_node(get_nodes_Block(n)),
 229                      get_new_node(get_Cmp_left(n)),
 230                      get_new_node(get_Cmp_right(n)));
 231     break;
 232   case iro_Shl:
 233     res = new_r_Shl (current_ir_graph, get_new_node(get_nodes_Block(n)),
 234                      get_new_node(get_Shl_left(n)),
 235                      get_new_node(get_Shl_right(n)), get_irn_mode(n));
 236     break;
 237   case iro_Shr:
 238     res = new_r_Shr (current_ir_graph, get_new_node(get_nodes_Block(n)),
 239                      get_new_node(get_Shr_left(n)),
 240                      get_new_node(get_Shr_right(n)), get_irn_mode(n));
 241     break;
 242   case iro_Shrs:
 243     res = new_r_Shrs (current_ir_graph, get_new_node(get_nodes_Block(n)),
 244                       get_new_node(get_Shrs_left(n)),
 245                       get_new_node(get_Shrs_right(n)), get_irn_mode(n));
 246     break;
 247   case iro_Rot:
 248     res = new_r_Rot (current_ir_graph, get_new_node(get_nodes_Block(n)),
 249                      get_new_node(get_Rot_left(n)),
 250                      get_new_node(get_Rot_right(n)), get_irn_mode(n));
 251     break;
 252   case iro_Conv:
 253     res = new_r_Conv (current_ir_graph, get_new_node(get_nodes_Block(n)),
 254                       get_new_node(get_Conv_op(n)),
 255                       get_irn_mode(n));
 256     break;
 257   case iro_Phi:
 258     {
 259       ir_node **in = get_Phi_preds_arr(n);
 260       res = new_r_Phi (current_ir_graph, get_new_node(get_nodes_Block(n)),
 261                        get_Phi_n_preds(n), in, get_irn_mode(n));
 262     }
 263     break;
 264   case iro_Load:
 265     res = new_r_Load (current_ir_graph, get_new_node(get_nodes_Block(n)),
 266                       get_new_node(get_Load_mem(n)),
 267                       get_new_node(get_Load_ptr(n)));
 268     break;
 269   case iro_Store:
 270     res = new_r_Store (current_ir_graph, get_new_node(get_nodes_Block(n)),
 271                        get_new_node(get_Store_mem(n)),
 272                        get_new_node(get_Store_ptr(n)),
 273                        get_new_node(get_Store_value(n)));
 274     break;
 275   case iro_Alloc:
 276     res = new_r_Alloc (current_ir_graph, get_new_node(get_nodes_Block(n)),
 277                        get_new_node(get_Alloc_mem(n)),
 278                        get_new_node(get_Alloc_size(n)),
 279                        get_Alloc_type(n), get_Alloc_where(n));
 280
 281     break;
 282   case iro_Free:
 283     res = new_r_Free (current_ir_graph, get_new_node(get_nodes_Block(n)),
 284                       get_new_node(get_Free_mem(n)),
 285                       get_new_node(get_Free_ptr(n)),
 286                       get_new_node(get_Free_size(n)), get_Free_type(n));
 287     break;
 288   case iro_Sync:
 289     {
 290       ir_node **in = get_Sync_preds_arr(n);
 291       res = new_r_Sync (current_ir_graph, get_new_node(get_nodes_Block(n)),
 292                         get_Sync_n_preds(n), in);
 293     }
 294     break;
 295   case iro_Proj:
 296     res = new_r_Proj (current_ir_graph, get_new_node(get_nodes_Block(n)),
 297                       get_new_node(get_Proj_pred(n)), get_irn_mode(n),
 298                       get_Proj_proj(n));
 299     break;
 300   case iro_Tuple:
 301     {
 302       ir_node **in = get_Tuple_preds_arr(n);
 303       res = new_r_Tuple (current_ir_graph, get_new_node(get_nodes_Block(n)),
 304                          get_Tuple_n_preds(n), in);
 305     }
 306     break;
 307   case iro_Id:
 308     res = new_r_Id (current_ir_graph, get_new_node(get_nodes_Block(n)),
 309                     get_new_node(get_Id_pred(n)), get_irn_mode(n));
 310     break;
 311   case iro_Bad:
 312     res = new_r_Bad (get_new_node(get_nodes_Block(n)));
 313     break;
 314   }
 315   set_new_node(n, res);
 316 }
 317
 318
 319 void
 320 dead_node_elimination(ir_graph *irg) {
 321   struct obstack *graveyard_obst=NULL;
 322   struct obstack *rebirth_obst;
 323
 324   ir_node *old_node, *new_node;
 325   ir_graph *rem = current_ir_graph;
 326   current_ir_graph = irg;
 327
 328   if (get_opt_dead_node_elimination()) {
 329
 330     /* A quiet place, where the old obstack can rest in peace,
 331        until it will be cremated. */
 332     graveyard_obst = irg->obst;
 333
 334     /* A new obstack, where the reachable nodes will be copied to. */
 335     rebirth_obst = (struct obstack *) xmalloc (sizeof (struct obstack));
 336     current_ir_graph->obst = rebirth_obst;
 337     obstack_init (current_ir_graph->obst);
 338
 339     /* Walks the graph once, and at the recursive way do the copy thing.
 340        all reachable nodes will be copied to a new obstack. */
 341
 342     /*CS*/
 343     printf("Before starting the DEAD NODE ELIMINATION !\n");
 344
 345     old_node = irg->start_block;
 346     new_node = new_r_Block (current_ir_graph, 0, NULL);
 347     irg->start_block = new_node;                       ;
 348     set_new_node (old_node, new_node);
 349     set_irn_visited (new_node, get_irg_visited(current_ir_graph)+1);
 350     /*CS  Start node und alle Proj nodes muessen hier per hand eingetragen
 351        werden! */
 352
 353     irg_walk(irg->end, NULL, copy_node, NULL);
 354     /*CS*/
 355     printf("After the DEAD NODE ELIMINATION !\n");
 356
 357     /* Free memory from old unoptimized obstack */
 358     xfree (graveyard_obst);
 359   }
 360
 361   /* Free memory from old unoptimized obstack */
 362   xfree (graveyard_obst);
 363
 364   current_ir_graph = rem;
 365 }