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