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
  19 /********************************************************************/
  20 /* apply optimizations of iropt to all nodes.                       */
  21
  22 void
  23 optimize_in_place_wrapper (ir_node *n, void *env) {
  24   int i;
  25   ir_node *optimized;
  26
  27   /* optimize all sons after recursion, i.e., the sons' sons are
  28      optimized already. */
  29   for (i = -1; i < get_irn_arity(n); i++) {
  30     optimized = optimize_in_place(get_irn_n(n, i));
  31     set_irn_n(n, i, optimized);
  32   }
  33 }
  34
  35 void
  36 local_optimize_graph (ir_graph *irg) {
  37   ir_graph *rem = current_ir_graph;
  38   current_ir_graph = irg;
  39
  40   /* walk over the graph */
  41   irg_walk(irg->end, NULL, optimize_in_place_wrapper, NULL);
  42
  43   current_ir_graph = rem;
  44 }
  45
  46 /********************************************************************/
  47 /* Routines for dead node elimination / copying garbage collection  */
  48 /* of the obstack.                                                  */
  49
  50 /* Remeber the new node in the old node by using a field all nodes have. */
  51 inline void
  52 set_new_node (ir_node *old, ir_node *new)
  53 {
  54   old->link = new;
  55 }
  56
  57 /* Get this new node, before the old node is forgotton.*/
  58 inline ir_node *
  59 get_new_node (ir_node * n)
  60 {
  61   return n->link;
  62 }
  63
  64 /* Copies the node to the new obstack. In's point to the predecessors
  65    on the old obstack.  n->link points to the new node. */
  66 inline void
  67 copy_node (ir_node *n, void *env) {
  68   ir_node *nn, *block;
  69
  70   if (get_irn_opcode(n) == iro_Block) {
  71     block = NULL;
  72   } else {
  73     block = get_nodes_Block(n);
  74   }
  75   nn = new_ir_node(current_ir_graph,
  76                    block,
  77                    get_irn_op(n),
  78                    get_irn_mode(n),
  79                    get_irn_arity(n),
  80                    get_irn_in(n));
  81   copy_attrs(n, nn);
  82   set_new_node(n, nn);
  83 }
  84
  85 /* Copies new predecessors of old node to new node remembered in link. */
  86 inline void
  87 copy_preds (ir_node *n, void *env) {
  88   ir_node *nn;
  89   int start, i;
  90
  91   nn = get_new_node(n);
  92   if (get_irn_opcode(n) == iro_Block) start = 0; else start = -1;
  93   for (i = start; i < get_irn_arity(n); i++)
  94     set_irn_n (nn, i, get_new_node(get_irn_n(n, i)));
  95 }
  96
  97 /* To break the recursion of the graph walk if there are loops in
  98    the graph we have to allocate new nodes for Phis and blocks
  99    before descending.  Here we use the old predecessors for the
 100    new nodes.  These are replaced by the proper predecessors in
 101    copy_node.
 102    It turned out that it is not sufficient to just break loops
 103    for Phi and Block nodes, as the walker can hit visited but
 104    not copied nodes at any point in the graph.
 105    A simple fix would be allocating Id's for every node and then
 106    exchanging them, but this will cause new dead nodes on the new
 107    obstack.
 108    So now there is a different implementation more based on the
 109    view on the graph as a graph than as a represented program. */
 110 void
 111 create_dummy (ir_node *n, void *env) {
 112   assert (n);
 113
 114   /* Assure link is set to NULL so we can test whether there is a
 115      new node by checking link.
 116      set_irn_link(n, NULL); */
 117
 118   switch (get_irn_opcode(n)) {
 119   case iro_Block:
 120       set_new_node(n, new_ir_node(current_ir_graph, NULL, op_Block, mode_R,
 121                                   get_irn_arity(n), get_irn_in(n)));
 122     break;
 123   case iro_Phi:
 124       set_new_node(n, new_ir_node(current_ir_graph, NULL, op_Phi,
 125                                   get_irn_mode(n),
 126                                   get_irn_arity(n), get_irn_in(n)));
 127     break;
 128   default: {}
 129   } /* end switch (get_irn_opcode(n)) */
 130 }
 131
 132 /* Create a copy of this node on a new obstack. */
 133 void
 134 copy_node2 (ir_node *n, void *env) {
 135   ir_node *res = NULL;
 136   ir_node *a = NULL;
 137   ir_node *b = NULL;
 138   int i = 0;
 139
 140   assert (n);
 141   DDMSG2(n);
 142
 143   if (is_binop(n)) {
 144     a = get_binop_left(n);
 145     b = get_binop_right(n);
 146   } else if (is_unop(n)) {
 147     a = get_unop_op(n);
 148   }
 149
 150   switch (get_irn_opcode(n)) {
 151   case iro_Block:
 152     {
 153       res = get_new_node(n);
 154       assert(res);
 155       for (i = 0; i < get_Block_n_cfgpreds(n); i++)
 156         set_Block_cfgpred(res, i, get_new_node(get_Block_cfgpred(n, i)));
 157       set_Block_matured(res, 1);
 158     }
 159     break;
 160   case iro_Start:
 161     res = new_r_Start (current_ir_graph, get_new_node(get_nodes_Block(n)));
 162     break;
 163   case iro_End:
 164     res = new_r_End (current_ir_graph, get_new_node(get_nodes_Block(n)));
 165     current_ir_graph -> end = res;
 166     current_ir_graph -> end_block = get_nodes_Block(res);
 167     break;
 168   case iro_Jmp:
 169     res = new_r_Jmp (current_ir_graph, get_new_node(get_nodes_Block(n)));
 170     break;
 171   case iro_Cond:
 172     res = new_r_Cond (current_ir_graph, get_new_node(get_nodes_Block(n)),
 173                       get_new_node(get_Cond_selector(n)));
 174     break;
 175   case iro_Return:
 176     {
 177       ir_node **in;
 178       in = get_Return_res_arr(n);
 179       for (i = 0; i < get_Return_n_res(n); i++)
 180         set_Return_res(n, i, get_new_node(get_Return_res(n, i)));
 181       res = new_r_Return (current_ir_graph,
 182                           get_new_node(get_nodes_Block(n)),
 183                           get_new_node(get_Return_mem(n)),
 184                           get_Return_n_res(n), in);
 185     }
 186     break;
 187   case iro_Raise:
 188     res = new_r_Raise (current_ir_graph,
 189                        get_new_node(get_nodes_Block(n)),
 190                        get_new_node(get_Raise_mem(n)),
 191                        get_new_node(get_Raise_exo_ptr(n)));
 192     break;
 193   case iro_Const:
 194     res = new_r_Const (current_ir_graph, get_new_node(get_nodes_Block(n)),
 195                        get_irn_mode(n), get_Const_tarval(n));
 196     break;
 197   case iro_SymConst:
 198     {
 199       type_or_id_p value = NULL;
 200
 201       if ((get_SymConst_kind(n)==type_tag) || (get_SymConst_kind(n)==size))
 202         {
 203
 204            value = (type_or_id_p) get_SymConst_type(n);
 205         }
 206       else
 207         {
 208           if (get_SymConst_kind(n)==linkage_ptr_info)
 209           {
 210             value = (type_or_id_p) get_SymConst_ptrinfo(n);
 211           }
 212         }
 213     res = new_r_SymConst (current_ir_graph, get_new_node(get_nodes_Block(n)),
 214                           value, get_SymConst_kind (n));
 215     }
 216     break;
 217   case iro_Sel:
 218     {
 219       ir_node **in = get_Sel_index_arr(n);
 220       for (i = 0; i < get_Sel_n_index(n); i++)
 221         set_Sel_index(n, i, get_new_node(get_Sel_index(n, i)));
 222       res = new_r_Sel (current_ir_graph, get_new_node(get_nodes_Block(n)),
 223                        get_new_node(get_Sel_mem(n)),
 224                        get_new_node(get_Sel_ptr(n)), get_Sel_n_index(n),
 225                        in, get_Sel_entity(n));
 226     }
 227     break;
 228   case  iro_Call:
 229     {
 230       ir_node **in;
 231       in = get_Call_param_arr(n);
 232
 233       for (i = 0; i < get_Call_arity(n); i++)
 234         set_Call_param(n, i, get_new_node(get_Call_param(n, i)));
 235       res = new_r_Call (current_ir_graph,
 236                         get_new_node(get_nodes_Block(n)),
 237                         get_new_node(get_Call_mem(n)),
 238                         get_new_node(get_Call_ptr(n)),
 239                         get_Call_arity(n), in,
 240                         get_Call_type (n));
 241     }
 242     break;
 243   case iro_Add:
 244     res = new_r_Add (current_ir_graph, get_new_node(get_nodes_Block(n)),
 245                      get_new_node(a), get_new_node(b), get_irn_mode(n));
 246     break;
 247   case iro_Sub:
 248     {
 249       res = new_r_Sub (current_ir_graph, get_new_node(get_nodes_Block(n)),
 250                        get_new_node(a), get_new_node(b), get_irn_mode(n));
 251     }
 252     break;
 253   case iro_Minus:
 254     res = new_r_Minus (current_ir_graph, get_new_node(get_nodes_Block(n)),
 255                        get_new_node(a), get_irn_mode(n));
 256     break;
 257   case iro_Mul:
 258     res = new_r_Mul (current_ir_graph, get_new_node(get_nodes_Block(n)),
 259                      get_new_node(a), get_new_node(b), get_irn_mode(n));
 260     break;
 261   case iro_Quot:
 262     res = new_r_Quot (current_ir_graph, get_new_node(get_nodes_Block(n)),
 263                       get_new_node(get_Quot_mem(n)), get_new_node(a),
 264                       get_new_node(b));
 265     break;
 266   case iro_DivMod:
 267     res = new_r_DivMod (current_ir_graph, get_new_node(get_nodes_Block(n)),
 268                         get_new_node(get_DivMod_mem(n)), get_new_node(a),
 269                         get_new_node(b));
 270     break;
 271   case iro_Div:
 272     res = new_r_Div (current_ir_graph, get_new_node(get_nodes_Block(n)),
 273                      get_new_node(get_Div_mem(n)), get_new_node(a),
 274                      get_new_node(b));
 275     break;
 276   case iro_Mod:
 277     res = new_r_Mod (current_ir_graph, get_new_node(get_nodes_Block(n)),
 278                      get_new_node(get_Mod_mem(n)), get_new_node(a),
 279                      get_new_node(b));
 280     break;
 281   case iro_Abs:
 282     res = new_r_Abs (current_ir_graph, get_new_node(get_nodes_Block(n)),
 283                      get_new_node(get_Abs_op(n)), get_irn_mode(n));
 284     break;
 285   case iro_And:
 286     res = new_r_And (current_ir_graph, get_new_node(get_nodes_Block(n)),
 287                      get_new_node(a), get_new_node(b), get_irn_mode(n));
 288     break;
 289   case iro_Or:
 290     res = new_r_Or (current_ir_graph, get_new_node(get_nodes_Block(n)),
 291                     get_new_node(a), get_new_node(b), get_irn_mode(n));
 292     break;
 293   case iro_Eor:
 294     res = new_r_Eor (current_ir_graph, get_new_node(get_nodes_Block(n)),
 295                      get_new_node(a), get_new_node(b), get_irn_mode(n));
 296     break;
 297   case iro_Not:
 298     res = new_r_Not (current_ir_graph, get_new_node(get_nodes_Block(n)),
 299                      get_new_node(get_Not_op(n)), get_irn_mode(n));
 300     break;
 301   case iro_Cmp:
 302     res = new_r_Cmp (current_ir_graph,
 303                      get_new_node(get_nodes_Block(n)),
 304                      get_new_node(get_Cmp_left(n)),
 305                      get_new_node(get_Cmp_right(n)));
 306     break;
 307   case iro_Shl:
 308     res = new_r_Shl (current_ir_graph, get_new_node(get_nodes_Block(n)),
 309                      get_new_node(get_Shl_left(n)),
 310                      get_new_node(get_Shl_right(n)), get_irn_mode(n));
 311     break;
 312   case iro_Shr:
 313     res = new_r_Shr (current_ir_graph, get_new_node(get_nodes_Block(n)),
 314                      get_new_node(get_Shr_left(n)),
 315                      get_new_node(get_Shr_right(n)), get_irn_mode(n));
 316     break;
 317   case iro_Shrs:
 318     res = new_r_Shrs (current_ir_graph, get_new_node(get_nodes_Block(n)),
 319                       get_new_node(get_Shrs_left(n)),
 320                       get_new_node(get_Shrs_right(n)), get_irn_mode(n));
 321     break;
 322   case iro_Rot:
 323     res = new_r_Rot (current_ir_graph, get_new_node(get_nodes_Block(n)),
 324                      get_new_node(get_Rot_left(n)),
 325                      get_new_node(get_Rot_right(n)), get_irn_mode(n));
 326     break;
 327   case iro_Conv:
 328     res = new_r_Conv (current_ir_graph, get_new_node(get_nodes_Block(n)),
 329                       get_new_node(get_Conv_op(n)),
 330                       get_irn_mode(n));
 331     break;
 332   case iro_Phi:
 333     {
 334       res = get_new_node(n);
 335       for (i = 0; i < get_Phi_n_preds(n); i++)
 336         set_Phi_pred(res, i, get_new_node(get_Phi_pred(n, i)));
 337       set_nodes_Block(res, get_new_node(get_nodes_Block(n)));
 338     }
 339     break;
 340   case iro_Load:
 341     res = new_r_Load (current_ir_graph, get_new_node(get_nodes_Block(n)),
 342                       get_new_node(get_Load_mem(n)),
 343                       get_new_node(get_Load_ptr(n)));
 344     break;
 345   case iro_Store:
 346     res = new_r_Store (current_ir_graph, get_new_node(get_nodes_Block(n)),
 347                        get_new_node(get_Store_mem(n)),
 348                        get_new_node(get_Store_ptr(n)),
 349                        get_new_node(get_Store_value(n)));
 350     break;
 351   case iro_Alloc:
 352     res = new_r_Alloc (current_ir_graph, get_new_node(get_nodes_Block(n)),
 353                        get_new_node(get_Alloc_mem(n)),
 354                        get_new_node(get_Alloc_size(n)),
 355                        get_Alloc_type(n), get_Alloc_where(n));
 356
 357     break;
 358   case iro_Free:
 359     res = new_r_Free (current_ir_graph, get_new_node(get_nodes_Block(n)),
 360                       get_new_node(get_Free_mem(n)),
 361                       get_new_node(get_Free_ptr(n)),
 362                       get_new_node(get_Free_size(n)), get_Free_type(n));
 363     break;
 364   case iro_Sync:
 365     {
 366       ir_node **in = get_Sync_preds_arr(n);
 367       for (i = 0; i < get_Sync_n_preds(n); i++)
 368         set_Sync_pred(n, i, get_new_node(get_Sync_pred(n, i)));
 369       res = new_r_Sync (current_ir_graph, get_new_node(get_nodes_Block(n)),
 370                         get_Sync_n_preds(n), in);
 371     }
 372     break;
 373   case iro_Proj: {
 374     res = new_r_Proj (current_ir_graph, get_new_node(get_nodes_Block(n)),
 375                       get_new_node(get_Proj_pred(n)), get_irn_mode(n),
 376                       get_Proj_proj(n));
 377   }
 378     break;
 379   case iro_Tuple:
 380     {
 381       ir_node **in = get_Tuple_preds_arr(n);
 382       for (i = 0; i < get_Tuple_n_preds(n); i++)
 383         set_Tuple_pred(n, i, get_new_node(get_Tuple_pred(n, i)));
 384       res = new_r_Tuple (current_ir_graph, get_new_node(get_nodes_Block(n)),
 385                          get_Tuple_n_preds(n), in);
 386     }
 387     break;
 388   case iro_Id:
 389     res = get_new_node(get_Id_pred(n));
 390     break;
 391   case iro_Bad:
 392     res = new_r_Bad ();
 393     break;
 394   }
 395   /* @@@ Here we could call optimize()!! Not necessary, called in constructor anyways. */
 396   set_new_node(n, res);
 397   printf(" "); DDMSG2(res);
 398 }
 399
 400 /* Copies the graph reachable from current_ir_graph->end to the obstack
 401    in current_ir_graph.
 402    Then fixes the fields in current_ir_graph containing nodes of the
 403    graph.  */
 404 void
 405 copy_graph () {
 406   /* Not all nodes remembered in current_ir_graph might be reachable
 407      from the end node.  Assure their link is set to NULL so that
 408      we can test whether new nodes have been computed. */
 409   set_irn_link(get_irg_frame  (current_ir_graph), NULL);
 410   set_irn_link(get_irg_globals(current_ir_graph), NULL);
 411   set_irn_link(get_irg_args   (current_ir_graph), NULL);
 412
 413   /* copy the graph */
 414   irg_walk(get_irg_end(current_ir_graph), copy_node, copy_preds, NULL);
 415
 416   /* fix the fields in current_ir_graph */
 417   set_irg_end        (current_ir_graph, get_new_node(get_irg_end(current_ir_graph)));
 418   set_irg_end_block  (current_ir_graph, get_new_node(get_irg_end_block(current_ir_graph)));
 419   if (get_irn_link(get_irg_frame(current_ir_graph)) == NULL)
 420     irg_walk(get_irg_frame(current_ir_graph), copy_node, copy_preds, NULL);
 421   if (get_irn_link(get_irg_globals(current_ir_graph)) == NULL)
 422     irg_walk(get_irg_globals(current_ir_graph), copy_node, copy_preds, NULL);
 423   if (get_irn_link(get_irg_args(current_ir_graph)) == NULL)
 424     irg_walk(get_irg_args(current_ir_graph), copy_node, copy_preds, NULL);
 425   set_irg_start  (current_ir_graph, get_new_node(get_irg_start(current_ir_graph)));
 426   set_irg_start_block(current_ir_graph,
 427                       get_new_node(get_irg_start_block(current_ir_graph)));
 428   set_irg_frame  (current_ir_graph, get_new_node(get_irg_frame(current_ir_graph)));
 429   set_irg_globals(current_ir_graph, get_new_node(get_irg_globals(current_ir_graph)));
 430   set_irg_args   (current_ir_graph, get_new_node(get_irg_args(current_ir_graph)));
 431   if (get_irn_link(get_irg_bad(current_ir_graph)) == NULL) {
 432     copy_node(get_irg_bad(current_ir_graph), NULL);
 433     copy_preds(get_irg_bad(current_ir_graph), NULL);
 434   }
 435   set_irg_bad(current_ir_graph, get_new_node(get_irg_bad(current_ir_graph)));
 436 }
 437
 438 void
 439 copy_graph2 () {
 440   ir_node *old_node, *new_node, *projX;
 441   ir_graph *irg = current_ir_graph;
 442
 443   /*CS*/
 444   printf("Before starting the DEAD NODE ELIMINATION !\n");
 445
 446   /* Copy nodes remembered in irg fields first.
 447      The optimization contains tests against these fields, e.g., not
 448      to optimize the start block away.  Therefore these fields have to
 449      be fixed first.
 450      Further setting these fields in copy_node would impose additional
 451      tests for all nodes of a kind.
 452      Predict the visited flag the walker will use! */
 453   /* Copy the start Block node.  Get the ProjX of the Start node, that is
 454      predecessor of the start Block.  We have to break the cycle and fix it
 455      later.  We use the old in array as placeholder. */
 456   old_node = irg->start_block;
 457   new_node = new_r_Block (current_ir_graph, get_Block_n_cfgpreds(old_node),
 458                           get_Block_cfgpred_arr(old_node));
 459   /* new_r_Block calls no optimization --> save */
 460   projX = get_Block_cfgpred(old_node, 0);
 461   irg->start_block = new_node;
 462   set_new_node (old_node, new_node);
 463   set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
 464   /* Copy the Start node */
 465   old_node = irg->start;
 466   new_node = new_r_Start (current_ir_graph, irg->start_block);
 467   irg->start = new_node;
 468   set_new_node (old_node, new_node);
 469   set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
 470   /* Copy the Bad node */
 471   old_node = irg->bad;
 472   new_node = new_ir_node (irg, irg->start_block, op_Bad, mode_T, 0, NULL);
 473   irg->bad = new_node;
 474   set_new_node (old_node, new_node);
 475   set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
 476   /* Copy the Projs for the Start's results. */
 477   old_node = projX;
 478   new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_X, pns_initial_exec);
 479   set_Block_cfgpred(irg->start_block, 0, new_node);
 480   set_new_node (old_node, new_node);
 481   set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
 482
 483   old_node = irg->frame;
 484   new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_p, pns_frame_base);
 485   irg->frame = new_node;
 486   set_new_node (old_node, new_node);
 487   set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
 488
 489   old_node = irg->globals;
 490   new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_p, pns_globals);
 491   irg->globals = new_node;
 492   set_new_node (old_node, new_node);
 493   set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
 494
 495   old_node = irg->args;
 496   new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_T, pns_args);
 497   irg->args = new_node;
 498   set_new_node (old_node, new_node);
 499   set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
 500
 501   /* Walks the graph once, and at the recursive way do the copy thing.
 502      all reachable nodes will be copied to a new obstack. */
 503   irg_walk(irg->end, create_dummy, copy_node2, NULL);
 504
 505   /*CS*/
 506   printf("After DEAD NODE ELIMINATION !\n");
 507 }
 508
 509 /* Amroq call this emigrate() */
 510 void
 511 dead_node_elimination(ir_graph *irg) {
 512   ir_graph *rem;
 513   struct obstack *graveyard_obst = NULL;
 514   struct obstack *rebirth_obst   = NULL;
 515
 516   /* Remember external state of current_ir_graph. */
 517   rem = current_ir_graph;
 518   current_ir_graph = irg;
 519
 520   if (get_optimize() && get_opt_dead_node_elimination()) {
 521
 522     /* A quiet place, where the old obstack can rest in peace,
 523        until it will be cremated. */
 524     graveyard_obst = irg->obst;
 525
 526     /* A new obstack, where the reachable nodes will be copied to. */
 527     rebirth_obst = (struct obstack *) xmalloc (sizeof (struct obstack));
 528     current_ir_graph->obst = rebirth_obst;
 529     obstack_init (current_ir_graph->obst);
 530
 531     /* Copy the graph from the old to the new obstack */
 532     copy_graph();
 533
 534     /* Free memory from old unoptimized obstack */
 535     //    obstack_free(graveyard_obst, 0);  /* First empty the obstack ... */
 536     //xfree (graveyard_obst);           /* ... then free it.           */
 537   }
 538
 539   current_ir_graph = rem;
 540 }