nsz Git - libfirm/blob - ir/opt/ldstopt.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/opt/ldstopt.c
   4  * Purpose:     load store optimizations
   5  * Author:
   6  * Created:
   7  * CVS-ID:      $Id$
   8  * Copyright:   (c) 1998-2004 Universit\81ät Karlsruhe
   9  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  10  */
  11 # include "irnode_t.h"
  12 # include "irgraph_t.h"
  13 # include "irmode_t.h"
  14 # include "iropt_t.h"
  15 # include "ircons_t.h"
  16 # include "irgmod.h"
  17 # include "irgwalk.h"
  18 # include "irvrfy.h"
  19 # include "tv_t.h"
  20 # include "dbginfo_t.h"
  21 # include "iropt_dbg.h"
  22 # include "irflag_t.h"
  23 # include "array.h"
  24 # include "firmstat.h"
  25
  26 #undef IMAX
  27 #define IMAX(a,b)       ((a) > (b) ? (a) : (b))
  28
  29 #define MAX_PROJ        IMAX(pn_Load_max, pn_Store_max)
  30
  31 /**
  32  * walker environment
  33  */
  34 typedef struct _walk_env_t {
  35   struct obstack obst;          /**< list of all stores */
  36   int changes;
  37 } walk_env_t;
  38
  39 /**
  40  * a Load/Store info
  41  */
  42 typedef struct _ldst_info_t {
  43   ir_node *projs[MAX_PROJ];     /**< list of Proj's of this node */
  44   ir_node *exc_block;           /**< the exception block if available */
  45   int     exc_idx;              /**< predecessor index in the exception block */
  46 } ldst_info_t;
  47
  48 /**
  49  * flags for control flow
  50  */
  51 enum block_flags_t {
  52   BLOCK_HAS_COND = 1,      /**< Block has conditional control flow */
  53   BLOCK_HAS_EXC  = 2       /**< Block has exceptionl control flow */
  54 };
  55
  56 /**
  57  * a Block info
  58  */
  59 typedef struct _block_info_t {
  60   unsigned flags;               /**< flags for the block */
  61 } block_info_t;
  62
  63 /**
  64  * walker, clears all links first
  65  */
  66 static void init_links(ir_node *n, void *env)
  67 {
  68   set_irn_link(n, NULL);
  69 }
  70
  71 /**
  72  * get the Load/Store info of a node
  73  */
  74 static ldst_info_t *get_ldst_info(ir_node *node, walk_env_t *env)
  75 {
  76   ldst_info_t *info = get_irn_link(node);
  77
  78   if (! info) {
  79     info = obstack_alloc(&env->obst, sizeof(*info));
  80
  81     memset(info, 0, sizeof(*info));
  82
  83     set_irn_link(node, info);
  84   }
  85   return info;
  86 }
  87
  88 /**
  89  * get the Block info of a node
  90  */
  91 static block_info_t *get_block_info(ir_node *node, walk_env_t *env)
  92 {
  93   block_info_t *info = get_irn_link(node);
  94
  95   if (! info) {
  96     info = obstack_alloc(&env->obst, sizeof(*info));
  97
  98     memset(info, 0, sizeof(*info));
  99
 100     set_irn_link(node, info);
 101   }
 102   return info;
 103 }
 104
 105 /**
 106  * update the projection info for a Load/Store
 107  */
 108 static int update_projs(ldst_info_t *info, ir_node *proj)
 109 {
 110   long nr = get_Proj_proj(proj);
 111
 112   assert(0 <= nr && nr <= MAX_PROJ && "Wrong proj from LoadStore");
 113
 114   if (info->projs[nr]) {
 115     /* there is already one, do CSE */
 116     exchange(proj, info->projs[nr]);
 117     return 1;
 118   }
 119   else {
 120     info->projs[nr] = proj;
 121     return 0;
 122   }
 123 }
 124
 125 /**
 126  * update the exception block info for a Load/Store
 127  */
 128 static int update_exc(ldst_info_t *info, ir_node *block, int pos)
 129 {
 130   assert(info->exc_block == NULL && "more than one exception block found");
 131
 132   info->exc_block = block;
 133   info->exc_idx   = pos;
 134   return 0;
 135 }
 136
 137 #define get_irn_out_n(node)     (unsigned)get_irn_link(node)
 138 #define set_irn_out_n(node, n)  set_irn_link(adr, (void *)(n))
 139
 140 /**
 141  * walker, collects all Load/Store/Proj nodes
 142  *
 143  * walks form Start -> End
 144  */
 145 static void collect_nodes(ir_node *node, void *env)
 146 {
 147   ir_node     *pred;
 148   ldst_info_t *ldst_info;
 149   walk_env_t  *wenv = env;
 150
 151   if (get_irn_op(node) == op_Proj) {
 152     ir_node *adr;
 153     ir_op *op;
 154
 155     pred = get_Proj_pred(node);
 156     op   = get_irn_op(pred);
 157
 158     if (op == op_Load) {
 159       adr       = get_Load_ptr(pred);
 160       ldst_info = get_ldst_info(pred, wenv);
 161
 162       wenv->changes |= update_projs(ldst_info, node);
 163
 164       set_irn_out_n(adr, get_irn_out_n(adr) + 1);
 165     }
 166     else if (op == op_Store) {
 167       adr       = get_Store_ptr(pred);
 168       ldst_info = get_ldst_info(pred, wenv);
 169
 170       wenv->changes |= update_projs(ldst_info, node);
 171
 172       set_irn_out_n(adr, get_irn_out_n(adr) + 1);
 173     }
 174   }
 175   else if (get_irn_op(node) == op_Block) { /* check, if it's an exception block */
 176     int i, n;
 177
 178     for (i = 0, n = get_Block_n_cfgpreds(node); i < n; ++i) {
 179       ir_node      *pred_block;
 180       block_info_t *bl_info;
 181
 182       pred = skip_Proj(get_Block_cfgpred(node, i));
 183
 184       /* ignore Bad predecessors, they will be removed later */
 185       if (is_Bad(pred))
 186         continue;
 187
 188       pred_block = get_nodes_block(pred);
 189       bl_info    = get_block_info(pred_block, wenv);
 190
 191       if (is_fragile_op(pred))
 192         bl_info->flags |= BLOCK_HAS_EXC;
 193       else if (is_forking_op(pred))
 194         bl_info->flags |= BLOCK_HAS_COND;
 195
 196       if (get_irn_op(pred) == op_Load || get_irn_op(pred) == op_Store) {
 197         ldst_info = get_ldst_info(pred, wenv);
 198
 199         wenv->changes |= update_exc(ldst_info, node, i);
 200       }
 201     }
 202   }
 203 }
 204
 205 /**
 206  * optimize a Load
 207  */
 208 static int optimize_load(ir_node *load)
 209 {
 210   ldst_info_t *info = get_irn_link(load);
 211   ir_mode *load_mode = get_Load_mode(load);
 212   ir_node *pred, *mem, *ptr;
 213   int res = 0;
 214
 215   /* the address of the load to be optimized */
 216   ptr = get_Load_ptr(load);
 217
 218   /*
 219    * Check if we can remove the exception form a Load:
 220    * this can be done, if the address is from an Sel(Alloc) and
 221    * the Sel type is a subtype of the alloc type.
 222    *
 223    * This optimizes some often used OO constructs,
 224    * like x = new O; x->t;
 225    */
 226   if (info->projs[pn_Load_X_except]) {
 227     if (get_irn_op(ptr) == op_Sel) {
 228       ir_node *mem = get_Sel_mem(ptr);
 229
 230       if (get_irn_op(mem) == op_Alloc) {
 231         /* ok, check the types */
 232         entity *ent  = get_Sel_entity(ptr);
 233         type *s_type = get_entity_type(ent);
 234         type *a_type = get_Alloc_type(mem);
 235
 236         if (is_subclass_of(s_type, a_type)) {
 237           /* ok, condition met: there can't be an exception because
 238            * alloc guarantees that enough memory was allocated */
 239
 240           exchange(info->projs[pn_Load_X_except], new_Bad());
 241           info->projs[pn_Load_X_except] = NULL;
 242         }
 243       }
 244     }
 245     else if (get_irn_op(ptr) == op_Alloc) {
 246       /* simple case: a direct load after an Alloc. Firm Alloc throw
 247        * an exception in case of out-of-memory. So, there is no way for an
 248        * exception in this load.
 249        * This code is constructed by the "exception lowering" in the Jack compiler.
 250        */
 251        exchange(info->projs[pn_Load_X_except], new_Bad());
 252        info->projs[pn_Load_X_except] = NULL;
 253     }
 254   }
 255
 256   /* do NOT touch volatile loads for now */
 257   if (get_Load_volatility(load) == volatility_is_volatile)
 258     return 0;
 259
 260   if (! info->projs[pn_Load_res] && ! info->projs[pn_Load_X_except]) {
 261     /* a Load which value is neither used nor exception checked, remove it */
 262     mem  = get_Load_mem(load);
 263     exchange(info->projs[pn_Load_M], mem);
 264
 265     return 1;
 266   }
 267
 268   /* the mem of the Load. Must still be returned after optimization */
 269   mem  = get_Load_mem(load);
 270
 271   if ((get_irn_opcode(ptr) == iro_SymConst) && (get_SymConst_kind(ptr) == symconst_addr_ent)) {
 272     entity *ent = get_SymConst_entity(ptr);
 273
 274     assert(mode_is_reference(get_irn_mode(ptr)));
 275
 276     if ((allocation_static == get_entity_allocation(ent)) &&
 277         (visibility_external_allocated != get_entity_visibility(ent))) {
 278       /* a static allocation that is not external: there should be NO exception
 279        * when loading. */
 280
 281       /* no exception, clear the info field as it might be checked later again */
 282       if (info->projs[pn_Load_X_except]) {
 283         exchange(info->projs[pn_Load_X_except], new_Bad());
 284         info->projs[pn_Load_X_except] = NULL;
 285       }
 286
 287       if (variability_constant == get_entity_variability(ent)
 288           && is_atomic_entity(ent)) {   /* Might not be atomic after
 289                                          lowering of Sels.  In this
 290                                          case we could also load, but
 291                                          it's more complicated. */
 292         /* more simpler case: we load the content of a constant value:
 293          * replace it by the constant itself
 294          */
 295
 296         /* no memory */
 297         if (info->projs[pn_Load_M])
 298           exchange(info->projs[pn_Load_M], mem);
 299
 300         /* no result :-) */
 301         if (info->projs[pn_Load_res])
 302           exchange(info->projs[pn_Load_res], copy_const_value(get_atomic_ent_value(ent)));
 303
 304         return 1;
 305       }
 306
 307       /* we changed the irg, but try further */
 308       res = 1;
 309     }
 310   }
 311
 312   /* Check, if the address of this load is used more than once.
 313    * If not, this load cannot be removed in any case. */
 314   if (get_irn_out_n(ptr) <= 1)
 315     return 0;
 316
 317   /* follow the memory chain as long as there are only Loads */
 318   for (pred = skip_Proj(mem); ; pred = skip_Proj(get_Load_mem(pred))) {
 319
 320     /*
 321      * BEWARE: one might think that checking the modes is useless, because
 322      * if the pointers are identical, they refer to the same object.
 323      * This is only true in strong typed languages, not is C were the following
 324      * is possible a = *(type1 *)p; b = *(type2 *)p ...
 325      */
 326
 327     if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
 328         get_irn_mode(get_Store_value(pred)) == load_mode) {
 329       ldst_info_t *pred_info = get_irn_link(pred);
 330
 331       /*
 332        * a Load immediately after a Store -- a read after write.
 333        * We may remove the Load, if both Load & Store does not have an exception handler
 334        * OR they are in the same block. In the latter case the Load cannot
 335        * throw an exception when the previous Store was quiet.
 336        *
 337        * Why we need to check for Store Exc? If the Store cannot be executed (ROM)
 338        * the exception handler might simply jump into the load block :-(
 339        * We could make it a little bit better if we would know that the exception
 340        * handler of the Store jumps directly to the end...
 341        */
 342       if ((!pred_info->projs[pn_Store_X_except] && !info->projs[pn_Load_X_except]) ||
 343           get_nodes_block(load) == get_nodes_block(pred)) {
 344         DBG_OPT_RAW(pred, load);
 345         exchange( info->projs[pn_Load_res], get_Store_value(pred) );
 346
 347         if (info->projs[pn_Load_M])
 348           exchange(info->projs[pn_Load_M], mem);
 349
 350         /* no exception */
 351         if (info->projs[pn_Load_X_except])
 352           exchange( info->projs[pn_Load_X_except], new_Bad());
 353         return 1;
 354       }
 355     }
 356     else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
 357              get_Load_mode(pred) == load_mode) {
 358       /*
 359        * a Load after a Load -- a read after read.
 360        * We may remove the second Load, if it does not have an exception handler
 361        * OR they are in the same block. In the later case the Load cannot
 362        * throw an exception when the previous Load was quiet.
 363        *
 364        * Here, there is no need to check if the previos Load has an exception hander because
 365        * they would have exact the same exception...
 366        */
 367       if (! info->projs[pn_Load_X_except] || get_nodes_block(load) == get_nodes_block(pred)) {
 368         ldst_info_t *pred_info = get_irn_link(pred);
 369
 370         DBG_OPT_RAR(pred, load);
 371
 372         if (pred_info->projs[pn_Load_res]) {
 373           /* we need a data proj from the previous load for this optimization */
 374           exchange( info->projs[pn_Load_res], pred_info->projs[pn_Load_res] );
 375           if (info->projs[pn_Load_M])
 376             exchange(info->projs[pn_Load_M], mem);
 377         }
 378         else {
 379           if (info->projs[pn_Load_res]) {
 380             set_Proj_pred(info->projs[pn_Load_res], pred);
 381             set_nodes_block(info->projs[pn_Load_res], get_nodes_block(pred));
 382           }
 383           if (info->projs[pn_Load_M]) {
 384             /* Actually, this if should not be necessary.  Construct the Loads
 385                properly!!! */
 386             exchange(info->projs[pn_Load_M], mem);
 387           }
 388         }
 389
 390         /* no exception */
 391         if (info->projs[pn_Load_X_except])
 392           exchange(info->projs[pn_Load_X_except], new_Bad());
 393
 394         return 1;
 395       }
 396     }
 397
 398     /* follow only Load chains */
 399     if (get_irn_op(pred) != op_Load)
 400       break;
 401    }
 402   return res;
 403 }
 404
 405 /**
 406  * optimize a Store
 407  */
 408 static int optimize_store(ir_node *store)
 409 {
 410   ldst_info_t *info = get_irn_link(store);
 411   ir_node *pred, *mem, *ptr, *value, *block;
 412   ir_mode *mode;
 413   int res = 0;
 414
 415   if (get_Store_volatility(store) == volatility_is_volatile)
 416     return 0;
 417
 418   /*
 419    * BEWARE: one might think that checking the modes is useless, because
 420    * if the pointers are identical, they refer to the same object.
 421    * This is only true in strong typed languages, not is C were the following
 422    * is possible *(type1 *)p = a; *(type2 *)p = b ...
 423    */
 424
 425   ptr   = get_Store_ptr(store);
 426
 427   /* Check, if the address of this load is used more than once.
 428    * If not, this load cannot be removed in any case. */
 429   if (get_irn_out_n(ptr) <= 1)
 430     return 0;
 431
 432   block = get_nodes_block(store);
 433   mem   = get_Store_mem(store);
 434   value = get_Store_value(store);
 435   mode  = get_irn_mode(value);
 436
 437   /* follow the memory chain as long as there are only Loads */
 438   for (pred = skip_Proj(mem); ; pred = skip_Proj(get_Load_mem(pred))) {
 439     ldst_info_t *pred_info = get_irn_link(pred);
 440
 441     if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
 442         get_nodes_block(pred) == block && get_irn_mode(get_Store_value(pred)) == mode) {
 443       /*
 444        * a Store after a Store in the same block -- a write after write.
 445        * We may remove the first Store, if it does not have an exception handler.
 446        *
 447        * TODO: What, if both have the same exception handler ???
 448        */
 449       if (get_Store_volatility(pred) != volatility_is_volatile && !pred_info->projs[pn_Store_X_except]) {
 450         DBG_OPT_WAW(pred, store);
 451         exchange( pred_info->projs[pn_Store_M], get_Store_mem(pred) );
 452         return 1;
 453       }
 454     }
 455     else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
 456              value == pred_info->projs[pn_Load_res]) {
 457       /*
 458        * a Store of a value after a Load -- a write after read.
 459        * We may remove the second Store, if it does not have an exception handler.
 460        */
 461       if (! info->projs[pn_Store_X_except]) {
 462         DBG_OPT_WAR(pred, store);
 463         exchange( info->projs[pn_Store_M], mem );
 464         return 1;
 465       }
 466     }
 467
 468     /* follow only Load chains */
 469     if (get_irn_op(pred) != op_Load)
 470       break;
 471   }
 472   return res;
 473 }
 474
 475 /**
 476  * walker, optimizes Phi after Stores:
 477  * Does the following optimization:
 478  *
 479  *   val1   val2   val3          val1  val2  val3
 480  *    |      |      |               \    |    /
 481  *   Str    Str    Str               \   |   /
 482  *      \    |    /                     Phi
 483  *       \   |   /                       |
 484  *        \  |  /                       Str
 485  *          Phi
 486  *
 487  * This removes the number of stores and allows for predicated execution.
 488  * Moves Stores back to the end of a function which may be bad
 489  *
 490  * Is only allowed if the predecessor blocks have only one successor.
 491  */
 492 static int optimize_phi(ir_node *phi, void *env)
 493 {
 494   walk_env_t *wenv = env;
 495   int i, n;
 496   ir_node *store, *ptr, *block, *phiM, *phiD, *exc, *projM;
 497   ir_mode *mode;
 498   ir_node **inM, **inD;
 499   int *idx;
 500   dbg_info *db = NULL;
 501   ldst_info_t *info;
 502   block_info_t *bl_info;
 503
 504   /* Must be a memory Phi */
 505   if (get_irn_mode(phi) != mode_M)
 506     return 0;
 507
 508   n = get_Phi_n_preds(phi);
 509   if (n <= 0)
 510     return 0;
 511
 512   store = skip_Proj(get_Phi_pred(phi, 0));
 513   if (get_irn_op(store) != op_Store)
 514     return 0;
 515
 516   /* abort on bad blocks */
 517   if (is_Bad(get_nodes_block(store)))
 518     return 0;
 519
 520   /* check if the block has only one output */
 521   bl_info = get_irn_link(get_nodes_block(store));
 522   if (bl_info->flags)
 523     return 0;
 524
 525   /* this is the address of the store */
 526   ptr  = get_Store_ptr(store);
 527   mode = get_irn_mode(get_Store_value(store));
 528   info = get_irn_link(store);
 529   exc  = info->exc_block;
 530
 531   for (i = 1; i < n; ++i) {
 532     ir_node *pred = skip_Proj(get_Phi_pred(phi, i));
 533
 534     if (get_irn_op(pred) != op_Store)
 535       return 0;
 536
 537     if (mode != get_irn_mode(get_Store_value(pred)) || ptr != get_Store_ptr(pred))
 538       return 0;
 539
 540     info = get_irn_link(pred);
 541
 542     /* check, if all stores have the same exception flow */
 543     if (exc != info->exc_block)
 544       return 0;
 545
 546     /* abort on bad blocks */
 547     if (is_Bad(get_nodes_block(store)))
 548       return 0;
 549
 550     /* check if the block has only one output */
 551     bl_info = get_irn_link(get_nodes_block(store));
 552     if (bl_info->flags)
 553       return 0;
 554   }
 555
 556   /*
 557    * ok, when we are here, we found all predecessors of a Phi that
 558    * are Stores to the same address. That means whatever we do before
 559    * we enter the block of the Phi, we do a Store.
 560    * So, we can move the store to the current block:
 561    *
 562    *   val1    val2    val3          val1  val2  val3
 563    *    |       |       |               \    |    /
 564    * | Str | | Str | | Str |             \   |   /
 565    *      \     |     /                     Phi
 566    *       \    |    /                       |
 567    *        \   |   /                       Str
 568    *           Phi
 569    *
 570    * Is only allowed if the predecessor blocks have only one successor.
 571    */
 572
 573   /* first step: collect all inputs */
 574   NEW_ARR_A(ir_node *, inM, n);
 575   NEW_ARR_A(ir_node *, inD, n);
 576   NEW_ARR_A(int, idx, n);
 577
 578   for (i = 0; i < n; ++i) {
 579     ir_node *pred = skip_Proj(get_Phi_pred(phi, i));
 580     info = get_irn_link(pred);
 581
 582     inM[i] = get_Store_mem(pred);
 583     inD[i] = get_Store_value(pred);
 584     idx[i] = info->exc_idx;
 585   }
 586   block = get_nodes_block(phi);
 587
 588   /* second step: create a new memory Phi */
 589   phiM = new_rd_Phi(get_irn_dbg_info(phi), current_ir_graph, block, n, inM, mode_M);
 590
 591   /* third step: create a new data Phi */
 592   phiD = new_rd_Phi(get_irn_dbg_info(phi), current_ir_graph, block, n, inD, mode);
 593
 594   /* fourth step: create the Store */
 595   store = new_rd_Store(db, current_ir_graph, block, phiM, ptr, phiD);
 596   projM = new_rd_Proj(NULL, current_ir_graph, block, store, mode_M, pn_Store_M);
 597
 598   info = get_ldst_info(store, wenv);
 599   info->projs[pn_Store_M] = projM;
 600
 601   /* fifths step: repair exception flow */
 602   if (exc) {
 603     ir_node *projX = new_rd_Proj(NULL, current_ir_graph, block, store, mode_X, pn_Store_X_except);
 604
 605     info->projs[pn_Store_X_except] = projX;
 606     info->exc_block                = exc;
 607     info->exc_idx                  = idx[0];
 608
 609     for (i = 0; i < n; ++i) {
 610       set_Block_cfgpred(exc, idx[i], projX);
 611     }
 612
 613     if (n > 1) {
 614       /* the exception block should be optimized as some inputs are identical now */
 615     }
 616   }
 617
 618   /* sixt step: replace old Phi */
 619   exchange(phi, projM);
 620
 621   return 1;
 622 }
 623
 624 /**
 625  * walker, collects all Load/Store/Proj nodes
 626  */
 627 static void do_load_store_optimize(ir_node *n, void *env)
 628 {
 629   walk_env_t *wenv = env;
 630
 631   switch (get_irn_opcode(n)) {
 632
 633   case iro_Load:
 634     wenv->changes |= optimize_load(n);
 635     break;
 636
 637   case iro_Store:
 638     wenv->changes |= optimize_store(n);
 639     break;
 640
 641   case iro_Phi:
 642     wenv->changes |= optimize_phi(n, env);
 643
 644   default:
 645     ;
 646   }
 647 }
 648
 649 /*
 650  * do the load store optimization
 651  */
 652 void optimize_load_store(ir_graph *irg)
 653 {
 654   walk_env_t env;
 655
 656   assert(get_irg_phase_state(irg) != phase_building);
 657
 658   if (!get_opt_redundant_LoadStore())
 659     return;
 660
 661   obstack_init(&env.obst);
 662   env.changes = 0;
 663
 664   /* init the links, then collect Loads/Stores/Proj's in lists */
 665   irg_walk_graph(irg, init_links, collect_nodes, &env);
 666
 667   /* now we have collected enough information, optimize */
 668   irg_walk_graph(irg, NULL, do_load_store_optimize, &env);
 669
 670   obstack_free(&env.obst, NULL);
 671
 672   /* Handle graph state */
 673   if (env.changes) {
 674     if (get_irg_outs_state(current_ir_graph) == outs_consistent)
 675       set_irg_outs_inconsistent(current_ir_graph);
 676
 677     /* is this really needed: Yes, as exception block may get bad but this might be tested */
 678     if (get_irg_dom_state(current_ir_graph) == dom_consistent)
 679       set_irg_dom_inconsistent(current_ir_graph);
 680   }
 681 }