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