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 #ifdef HAVE_CONFIG_H
  12 # include "config.h"
  13 #endif
  14
  15 #ifdef HAVE_ALLOCA_H
  16 #include <alloca.h>
  17 #endif
  18 #ifdef HAVE_MALLOC_H
  19 #include <malloc.h>
  20 #endif
  21 #ifdef HAVE_STRING_H
  22 # include <string.h>
  23 #endif
  24
  25 # include "irnode_t.h"
  26 # include "irgraph_t.h"
  27 # include "irmode_t.h"
  28 # include "iropt_t.h"
  29 # include "ircons_t.h"
  30 # include "irgmod.h"
  31 # include "irgwalk.h"
  32 # include "irvrfy.h"
  33 # include "tv_t.h"
  34 # include "dbginfo_t.h"
  35 # include "iropt_dbg.h"
  36 # include "irflag_t.h"
  37 # include "array.h"
  38 # include "irhooks.h"
  39 # include "irtools.h"
  40 # include "opt_polymorphy.h"
  41
  42 #ifdef DO_CACHEOPT
  43 #include "cacheopt/cachesim.h"
  44 #endif
  45
  46 #undef IMAX
  47 #define IMAX(a,b)       ((a) > (b) ? (a) : (b))
  48
  49 #define MAX_PROJ        IMAX(pn_Load_max, pn_Store_max)
  50
  51 enum changes_t {
  52   DF_CHANGED = 1,       /**< data flow changed */
  53   CF_CHANGED = 2,       /**< control flow changed */
  54 };
  55
  56 /**
  57  * walker environment
  58  */
  59 typedef struct _walk_env_t {
  60   struct obstack obst;          /**< list of all stores */
  61   unsigned changes;             /**< a bitmask of graph changes */
  62 } walk_env_t;
  63
  64 /**
  65  * flags for Load/Store
  66  */
  67 enum ldst_flags_t {
  68   LDST_VISITED = 1              /**< if set, this Load/Store is already visited */
  69 };
  70
  71 /**
  72  * a Load/Store info
  73  */
  74 typedef struct _ldst_info_t {
  75   ir_node  *projs[MAX_PROJ];    /**< list of Proj's of this node */
  76   ir_node  *exc_block;          /**< the exception block if available */
  77   int      exc_idx;             /**< predecessor index in the exception block */
  78   unsigned flags;               /**< flags */
  79 } ldst_info_t;
  80
  81 /**
  82  * flags for control flow
  83  */
  84 enum block_flags_t {
  85   BLOCK_HAS_COND = 1,      /**< Block has conditional control flow */
  86   BLOCK_HAS_EXC  = 2       /**< Block has exceptional control flow */
  87 };
  88
  89 /**
  90  * a Block info
  91  */
  92 typedef struct _block_info_t {
  93   unsigned flags;               /**< flags for the block */
  94 } block_info_t;
  95
  96 /**
  97  * get the Load/Store info of a node
  98  */
  99 static ldst_info_t *get_ldst_info(ir_node *node, walk_env_t *env)
 100 {
 101   ldst_info_t *info = get_irn_link(node);
 102
 103   if (! info) {
 104     info = obstack_alloc(&env->obst, sizeof(*info));
 105
 106     memset(info, 0, sizeof(*info));
 107
 108     set_irn_link(node, info);
 109   }
 110   return info;
 111 }
 112
 113 /**
 114  * get the Block info of a node
 115  */
 116 static block_info_t *get_block_info(ir_node *node, walk_env_t *env)
 117 {
 118   block_info_t *info = get_irn_link(node);
 119
 120   if (! info) {
 121     info = obstack_alloc(&env->obst, sizeof(*info));
 122
 123     memset(info, 0, sizeof(*info));
 124
 125     set_irn_link(node, info);
 126   }
 127   return info;
 128 }
 129
 130 /**
 131  * update the projection info for a Load/Store
 132  */
 133 static unsigned update_projs(ldst_info_t *info, ir_node *proj)
 134 {
 135   long nr = get_Proj_proj(proj);
 136
 137   assert(0 <= nr && nr <= MAX_PROJ && "Wrong proj from LoadStore");
 138
 139   if (info->projs[nr]) {
 140     /* there is already one, do CSE */
 141     exchange(proj, info->projs[nr]);
 142     return DF_CHANGED;
 143   }
 144   else {
 145     info->projs[nr] = proj;
 146     return 0;
 147   }
 148 }
 149
 150 /**
 151  * update the exception block info for a Load/Store node.
 152  *
 153  * @param info   the load/store info struct
 154  * @param block  the exception handler block for this load/store
 155  * @param pos    the control flow input of the block
 156  */
 157 static unsigned update_exc(ldst_info_t *info, ir_node *block, int pos)
 158 {
 159   assert(info->exc_block == NULL && "more than one exception block found");
 160
 161   info->exc_block = block;
 162   info->exc_idx   = pos;
 163   return 0;
 164 }
 165
 166 #define get_irn_out_n(node)     (unsigned)PTR_TO_INT(get_irn_link(node))
 167 #define set_irn_out_n(node, n)  set_irn_link(adr, INT_TO_PTR(n))
 168
 169 /**
 170  * walker, collects all Load/Store/Proj nodes
 171  *
 172  * walks from Start -> End
 173  */
 174 static void collect_nodes(ir_node *node, void *env)
 175 {
 176   ir_op       *op = get_irn_op(node);
 177   ir_node     *pred, *blk, *pred_blk;
 178   ldst_info_t *ldst_info;
 179   walk_env_t  *wenv = env;
 180
 181   if (op == op_Proj) {
 182     ir_node *adr;
 183     ir_op *op;
 184
 185     pred = get_Proj_pred(node);
 186     op   = get_irn_op(pred);
 187
 188     if (op == op_Load) {
 189       ldst_info = get_ldst_info(pred, wenv);
 190
 191       wenv->changes |= update_projs(ldst_info, node);
 192
 193       if ((ldst_info->flags & LDST_VISITED) == 0) {
 194         adr = get_Load_ptr(pred);
 195         set_irn_out_n(adr, get_irn_out_n(adr) + 1);
 196
 197         ldst_info->flags |= LDST_VISITED;
 198       }
 199
 200       /*
 201        * Place the Proj's to the same block as the
 202        * predecessor Load. This is always ok and prevents
 203        * "non-SSA" form after optimizations if the Proj
 204        * is in a wrong block.
 205        */
 206       blk      = get_nodes_block(node);
 207       pred_blk = get_nodes_block(pred);
 208       if (blk != pred_blk) {
 209         wenv->changes |= DF_CHANGED;
 210         set_nodes_block(node, pred_blk);
 211       }
 212     }
 213     else if (op == op_Store) {
 214       ldst_info = get_ldst_info(pred, wenv);
 215
 216       wenv->changes |= update_projs(ldst_info, node);
 217
 218       if ((ldst_info->flags & LDST_VISITED) == 0) {
 219         adr = get_Store_ptr(pred);
 220         set_irn_out_n(adr, get_irn_out_n(adr) + 1);
 221
 222         ldst_info->flags |= LDST_VISITED;
 223       }
 224
 225       /*
 226        * Place the Proj's to the same block as the
 227        * predecessor Store. This is always ok and prevents
 228        * "non-SSA" form after optimizations if the Proj
 229        * is in a wrong block.
 230        */
 231       blk      = get_nodes_block(node);
 232       pred_blk = get_nodes_block(pred);
 233       if (blk != pred_blk) {
 234         wenv->changes |= DF_CHANGED;
 235         set_nodes_block(node, pred_blk);
 236       }
 237     }
 238   }
 239   else if (op == op_Block) { /* check, if it's an exception block */
 240     int i;
 241
 242     for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
 243       ir_node      *pred_block;
 244       block_info_t *bl_info;
 245
 246       pred = skip_Proj(get_Block_cfgpred(node, i));
 247
 248       /* ignore Bad predecessors, they will be removed later */
 249       if (is_Bad(pred))
 250         continue;
 251
 252       pred_block = get_nodes_block(pred);
 253       bl_info    = get_block_info(pred_block, wenv);
 254
 255       if (is_fragile_op(pred))
 256               bl_info->flags |= BLOCK_HAS_EXC;
 257       else if (is_irn_forking(pred))
 258         bl_info->flags |= BLOCK_HAS_COND;
 259
 260       if (get_irn_op(pred) == op_Load || get_irn_op(pred) == op_Store) {
 261         ldst_info = get_ldst_info(pred, wenv);
 262
 263         wenv->changes |= update_exc(ldst_info, node, i);
 264       }
 265     }
 266   }
 267 }
 268
 269 /**
 270  * Returns an entity if the address ptr points to a constant one.
 271  */
 272 static entity *find_constant_entity(ir_node *ptr)
 273 {
 274   for (;;) {
 275     ir_op *op = get_irn_op(ptr);
 276
 277     if (op == op_SymConst && (get_SymConst_kind(ptr) == symconst_addr_ent)) {
 278       return get_SymConst_entity(ptr);
 279     }
 280     else if (op == op_Sel) {
 281       entity *ent = get_Sel_entity(ptr);
 282       type *tp    = get_entity_owner(ent);
 283
 284       /* Do not fiddle about polymorphy. */
 285       if (is_Class_type(get_entity_owner(ent)) &&
 286           ((get_entity_n_overwrites(ent)    != 0) ||
 287            (get_entity_n_overwrittenby(ent) != 0)   ) )
 288         return NULL;
 289
 290       if (variability_constant == get_entity_variability(ent))
 291         return ent;
 292
 293       if (is_Array_type(tp)) {
 294         /* check bounds */
 295         int i, n;
 296
 297         for (i = 0, n = get_Sel_n_indexs(ptr); i < n; ++i) {
 298           ir_node *bound;
 299           tarval *tlower, *tupper;
 300           ir_node *index = get_Sel_index(ptr, i);
 301           tarval *tv     = computed_value(index);
 302
 303           /* check if the index is constant */
 304           if (tv == tarval_bad)
 305             return NULL;
 306
 307           bound  = get_array_lower_bound(tp, i);
 308           tlower = computed_value(bound);
 309           bound  = get_array_upper_bound(tp, i);
 310           tupper = computed_value(bound);
 311
 312           if (tlower == tarval_bad || tupper == tarval_bad)
 313             return NULL;
 314
 315           if (tarval_cmp(tv, tlower) & pn_Cmp_Lt)
 316             return NULL;
 317           if (tarval_cmp(tupper, tv) & pn_Cmp_Lt)
 318             return NULL;
 319
 320           /* ok, bounds check finished */
 321         }
 322       }
 323
 324       /* try next */
 325       ptr = get_Sel_ptr(ptr);
 326     }
 327     else
 328       return NULL;
 329   }
 330 }
 331
 332 /**
 333  * Return the Selection index of a Sel node from dimension n
 334  */
 335 static long get_Sel_array_index_long(ir_node *n, int dim) {
 336   ir_node *index = get_Sel_index(n, dim);
 337   assert(get_irn_op(index) == op_Const);
 338   return get_tarval_long(get_Const_tarval(index));
 339 }
 340
 341 /**
 342  * Returns the accessed component graph path for an
 343  * node computing an address.
 344  *
 345  * @param ptr    the node computing the address
 346  * @param depth  current depth in steps upward from the root
 347  *               of the address
 348  */
 349 static compound_graph_path *rec_get_accessed_path(ir_node *ptr, int depth) {
 350   compound_graph_path *res = NULL;
 351   entity              *root, *field;
 352   int                 path_len, pos;
 353
 354   if (get_irn_op(ptr) == op_SymConst) {
 355     /* a SymConst. If the depth is 0, this is an access to a global
 356      * entity and we don't need a component path, else we know
 357      * at least it's length.
 358      */
 359     assert(get_SymConst_kind(ptr) == symconst_addr_ent);
 360     root = get_SymConst_entity(ptr);
 361     res = (depth == 0) ? NULL : new_compound_graph_path(get_entity_type(root), depth);
 362   }
 363   else {
 364     assert(get_irn_op(ptr) == op_Sel);
 365     /* it's a Sel, go up until we find the root */
 366     res = rec_get_accessed_path(get_Sel_ptr(ptr), depth+1);
 367
 368     /* fill up the step in the path at the current position */
 369     field    = get_Sel_entity(ptr);
 370     path_len = get_compound_graph_path_length(res);
 371     pos      = path_len - depth - 1;
 372     set_compound_graph_path_node(res, pos, field);
 373
 374     if (is_Array_type(get_entity_owner(field))) {
 375       assert(get_Sel_n_indexs(ptr) == 1 && "multi dim arrays not implemented");
 376       set_compound_graph_path_array_index(res, pos, get_Sel_array_index_long(ptr, 0));
 377     }
 378   }
 379   return res;
 380 }
 381
 382 /** Returns an access path or NULL.  The access path is only
 383  *  valid, if the graph is in phase_high and _no_ address computation is used.
 384  */
 385 static compound_graph_path *get_accessed_path(ir_node *ptr) {
 386   return rec_get_accessed_path(ptr, 0);
 387 }
 388
 389 /**
 390  * optimize a Load
 391  */
 392 static unsigned optimize_load(ir_node *load)
 393 {
 394   ldst_info_t *info = get_irn_link(load);
 395   ir_mode *load_mode = get_Load_mode(load);
 396   ir_node *pred, *mem, *ptr, *new_node;
 397   entity *ent;
 398   unsigned res = 0;
 399
 400   /* do NOT touch volatile loads for now */
 401   if (get_Load_volatility(load) == volatility_is_volatile)
 402     return 0;
 403
 404   /* the address of the load to be optimized */
 405   ptr = get_Load_ptr(load);
 406
 407   /*
 408    * Check if we can remove the exception from a Load:
 409    * This can be done, if the address is from an Sel(Alloc) and
 410    * the Sel type is a subtype of the allocated type.
 411    *
 412    * This optimizes some often used OO constructs,
 413    * like x = new O; x->t;
 414    */
 415   if (info->projs[pn_Load_X_except]) {
 416     if (get_irn_op(ptr) == op_Sel) {
 417       ir_node *mem = get_Sel_mem(ptr);
 418
 419       if (get_irn_op(skip_Proj(mem)) == op_Alloc) {
 420         /* ok, check the types */
 421         entity *ent  = get_Sel_entity(ptr);
 422         type *s_type = get_entity_type(ent);
 423         type *a_type = get_Alloc_type(mem);
 424
 425         if (is_subclass_of(s_type, a_type)) {
 426           /* ok, condition met: there can't be an exception because
 427            * Alloc guarantees that enough memory was allocated */
 428
 429           exchange(info->projs[pn_Load_X_except], new_Bad());
 430           info->projs[pn_Load_X_except] = NULL;
 431           res |= CF_CHANGED;
 432         }
 433       }
 434     }
 435     else if ((get_irn_op(skip_Proj(ptr)) == op_Alloc) ||
 436              ((get_irn_op(ptr) == op_Cast) && (get_irn_op(skip_Proj(get_Cast_op(ptr))) == op_Alloc))) {
 437       /* simple case: a direct load after an Alloc. Firm Alloc throw
 438        * an exception in case of out-of-memory. So, there is no way for an
 439        * exception in this load.
 440        * This code is constructed by the "exception lowering" in the Jack compiler.
 441        */
 442        exchange(info->projs[pn_Load_X_except], new_Bad());
 443        info->projs[pn_Load_X_except] = NULL;
 444        res |= CF_CHANGED;
 445     }
 446   }
 447
 448   /* the mem of the Load. Must still be returned after optimization */
 449   mem  = get_Load_mem(load);
 450
 451   if (! info->projs[pn_Load_res] && ! info->projs[pn_Load_X_except]) {
 452     /* a Load which value is neither used nor exception checked, remove it */
 453     exchange(info->projs[pn_Load_M], mem);
 454
 455     return res | DF_CHANGED;
 456   }
 457
 458   /* Load from a constant polymorphic field, where we can resolve
 459      polymorphy. */
 460   new_node = transform_node_Load(load);
 461   if (new_node != load) {
 462     if (info->projs[pn_Load_M]) {
 463       exchange(info->projs[pn_Load_M], mem);
 464       info->projs[pn_Load_M] = NULL;
 465     }
 466     if (info->projs[pn_Load_X_except]) {
 467       exchange(info->projs[pn_Load_X_except], new_Bad());
 468       info->projs[pn_Load_X_except] = NULL;
 469     }
 470     if (info->projs[pn_Load_res])
 471       exchange(info->projs[pn_Load_res], new_node);
 472     return res | DF_CHANGED;
 473   }
 474
 475   /* check if we can determine the entity that will be loaded */
 476   ent = find_constant_entity(ptr);
 477   if (ent) {
 478     if ((allocation_static == get_entity_allocation(ent)) &&
 479         (visibility_external_allocated != get_entity_visibility(ent))) {
 480       /* a static allocation that is not external: there should be NO exception
 481        * when loading. */
 482
 483       /* no exception, clear the info field as it might be checked later again */
 484       if (info->projs[pn_Load_X_except]) {
 485         exchange(info->projs[pn_Load_X_except], new_Bad());
 486         info->projs[pn_Load_X_except] = NULL;
 487         res |= CF_CHANGED;
 488       }
 489
 490       if (variability_constant == get_entity_variability(ent)
 491                 && is_atomic_entity(ent)) {
 492         /* Might not be atomic after
 493            lowering of Sels.  In this
 494            case we could also load, but
 495            it's more complicated. */
 496         /* more simpler case: we load the content of a constant value:
 497          * replace it by the constant itself
 498          */
 499
 500         /* no memory */
 501         if (info->projs[pn_Load_M]) {
 502           exchange(info->projs[pn_Load_M], mem);
 503           res |= DF_CHANGED;
 504         }
 505
 506         /* no result :-) */
 507         if (info->projs[pn_Load_res]) {
 508           if (is_atomic_entity(ent)) {
 509             ir_node *c = copy_const_value(get_atomic_ent_value(ent));
 510
 511             DBG_OPT_RC(load, c);
 512             exchange(info->projs[pn_Load_res], c);
 513             return DF_CHANGED | res;
 514           }
 515         }
 516       }
 517       else if (variability_constant == get_entity_variability(ent)) {
 518         compound_graph_path *path = get_accessed_path(ptr);
 519
 520         if (path) {
 521           ir_node *c;
 522
 523           assert(is_proper_compound_graph_path(path, get_compound_graph_path_length(path)-1));
 524           /*
 525           {
 526             int j;
 527             for (j = 0; j < get_compound_graph_path_length(path); ++j) {
 528               entity *node = get_compound_graph_path_node(path, j);
 529               fprintf(stdout, ".%s", get_entity_name(node));
 530               if (is_Array_type(get_entity_owner(node)))
 531                       fprintf(stdout, "[%d]", get_compound_graph_path_array_index(path, j));
 532             }
 533             printf("\n");
 534           }
 535           */
 536
 537           c = get_compound_ent_value_by_path(ent, path);
 538           free_compound_graph_path(path);
 539
 540           /* printf("  cons: "); DDMN(c); */
 541
 542           if (info->projs[pn_Load_M]) {
 543             exchange(info->projs[pn_Load_M], mem);
 544             res |= DF_CHANGED;
 545           }
 546           if (info->projs[pn_Load_res]) {
 547             exchange(info->projs[pn_Load_res], copy_const_value(c));
 548             return res | DF_CHANGED;
 549           }
 550         }
 551         else {
 552           /*  We can not determine a correct access path.  E.g., in jack, we load
 553                     a byte from an object to generate an exception.   Happens in test program
 554                     Reflectiontest.
 555           printf(">>>>>>>>>>>>> Found access to constant entity %s in function %s\n", get_entity_name(ent),
 556            get_entity_name(get_irg_entity(current_ir_graph)));
 557           printf("  load: "); DDMN(load);
 558           printf("  ptr:  "); DDMN(ptr);
 559           */
 560         }
 561       }
 562     }
 563   }
 564
 565   /* Check, if the address of this load is used more than once.
 566    * If not, this load cannot be removed in any case. */
 567   if (get_irn_out_n(ptr) <= 1)
 568     return res;
 569
 570   /* follow the memory chain as long as there are only Loads
 571    * and try to replace current Load or Store by a previous one
 572    */
 573   for (pred = skip_Proj(mem); ; pred = skip_Proj(get_Load_mem(pred))) {
 574     /*
 575      * BEWARE: one might think that checking the modes is useless, because
 576      * if the pointers are identical, they refer to the same object.
 577      * This is only true in strong typed languages, not in C were the following
 578      * is possible a = *(type1 *)p; b = *(type2 *)p ...
 579      */
 580
 581     if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
 582         get_irn_mode(get_Store_value(pred)) == load_mode) {
 583       ldst_info_t *pred_info = get_irn_link(pred);
 584
 585       /*
 586        * a Load immediately after a Store -- a read after write.
 587        * We may remove the Load, if both Load & Store does not have an exception handler
 588        * OR they are in the same block. In the latter case the Load cannot
 589        * throw an exception when the previous Store was quiet.
 590        *
 591        * Why we need to check for Store Exception? If the Store cannot
 592        * be executed (ROM) the exception handler might simply jump into
 593        * the load block :-(
 594        * We could make it a little bit better if we would know that the exception
 595        * handler of the Store jumps directly to the end...
 596        */
 597       if ((!pred_info->projs[pn_Store_X_except] && !info->projs[pn_Load_X_except]) ||
 598           get_nodes_block(load) == get_nodes_block(pred)) {
 599         ir_node *value = get_Store_value(pred);
 600
 601         DBG_OPT_RAW(load, value);
 602         if (info->projs[pn_Load_M])
 603           exchange(info->projs[pn_Load_M], mem);
 604
 605         /* no exception */
 606         if (info->projs[pn_Load_X_except]) {
 607           exchange( info->projs[pn_Load_X_except], new_Bad());
 608           res |= CF_CHANGED;
 609         }
 610
 611         if (info->projs[pn_Load_res])
 612           exchange(info->projs[pn_Load_res], value);
 613
 614         return res | DF_CHANGED;
 615       }
 616     }
 617     else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
 618              get_Load_mode(pred) == load_mode) {
 619       /*
 620        * a Load after a Load -- a read after read.
 621        * We may remove the second Load, if it does not have an exception handler
 622        * OR they are in the same block. In the later case the Load cannot
 623        * throw an exception when the previous Load was quiet.
 624        *
 625        * Here, there is no need to check if the previous Load has an exception
 626        * hander because they would have exact the same exception...
 627        */
 628       if (! info->projs[pn_Load_X_except] || get_nodes_block(load) == get_nodes_block(pred)) {
 629         ldst_info_t *pred_info = get_irn_link(pred);
 630
 631         DBG_OPT_RAR(load, pred);
 632
 633         if (pred_info->projs[pn_Load_res]) {
 634           /* we need a data proj from the previous load for this optimization */
 635           if (info->projs[pn_Load_res])
 636             exchange(info->projs[pn_Load_res], pred_info->projs[pn_Load_res]);
 637
 638           if (info->projs[pn_Load_M])
 639             exchange(info->projs[pn_Load_M], mem);
 640         }
 641         else {
 642           if (info->projs[pn_Load_res]) {
 643             set_Proj_pred(info->projs[pn_Load_res], pred);
 644             set_nodes_block(info->projs[pn_Load_res], get_nodes_block(pred));
 645             pred_info->projs[pn_Load_res] = info->projs[pn_Load_res];
 646           }
 647           if (info->projs[pn_Load_M]) {
 648             /* Actually, this if should not be necessary.  Construct the Loads
 649                properly!!! */
 650             exchange(info->projs[pn_Load_M], mem);
 651           }
 652         }
 653
 654         /* no exception */
 655         if (info->projs[pn_Load_X_except]) {
 656           exchange(info->projs[pn_Load_X_except], new_Bad());
 657           res |= CF_CHANGED;
 658         }
 659
 660         return res |= DF_CHANGED;
 661       }
 662     }
 663
 664     /* follow only Load chains */
 665     if (get_irn_op(pred) != op_Load)
 666       break;
 667    }
 668   return res;
 669 }
 670
 671 /**
 672  * optimize a Store
 673  */
 674 static unsigned optimize_store(ir_node *store)
 675 {
 676   ldst_info_t *info = get_irn_link(store);
 677   ir_node *pred, *mem, *ptr, *value, *block;
 678   ir_mode *mode;
 679   unsigned res = 0;
 680
 681   if (get_Store_volatility(store) == volatility_is_volatile)
 682     return 0;
 683
 684   /*
 685    * BEWARE: one might think that checking the modes is useless, because
 686    * if the pointers are identical, they refer to the same object.
 687    * This is only true in strong typed languages, not is C were the following
 688    * is possible *(type1 *)p = a; *(type2 *)p = b ...
 689    */
 690
 691   ptr   = get_Store_ptr(store);
 692
 693   /* Check, if the address of this load is used more than once.
 694    * If not, this load cannot be removed in any case. */
 695   if (get_irn_out_n(ptr) <= 1)
 696     return 0;
 697
 698   block = get_nodes_block(store);
 699   mem   = get_Store_mem(store);
 700   value = get_Store_value(store);
 701   mode  = get_irn_mode(value);
 702
 703   /* follow the memory chain as long as there are only Loads */
 704   for (pred = skip_Proj(mem); ; pred = skip_Proj(get_Load_mem(pred))) {
 705     ldst_info_t *pred_info = get_irn_link(pred);
 706
 707     if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
 708         get_nodes_block(pred) == block && get_irn_mode(get_Store_value(pred)) == mode) {
 709       /*
 710        * a Store after a Store in the same block -- a write after write.
 711        * We may remove the first Store, if it does not have an exception handler.
 712        *
 713        * TODO: What, if both have the same exception handler ???
 714        */
 715       if (get_Store_volatility(pred) != volatility_is_volatile && !pred_info->projs[pn_Store_X_except]) {
 716         DBG_OPT_WAW(pred, store);
 717         exchange( pred_info->projs[pn_Store_M], get_Store_mem(pred) );
 718         return DF_CHANGED;
 719       }
 720     }
 721     else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
 722              value == pred_info->projs[pn_Load_res]) {
 723       /*
 724        * a Store of a value after a Load -- a write after read.
 725        * We may remove the second Store, if it does not have an exception handler.
 726        */
 727       if (! info->projs[pn_Store_X_except]) {
 728         DBG_OPT_WAR(store, pred);
 729         exchange( info->projs[pn_Store_M], mem );
 730         return DF_CHANGED;
 731       }
 732     }
 733
 734     /* follow only Load chains */
 735     if (get_irn_op(pred) != op_Load)
 736       break;
 737   }
 738   return res;
 739 }
 740
 741 /**
 742  * walker, optimizes Phi after Stores:
 743  * Does the following optimization:
 744  *
 745  *   val1   val2   val3          val1  val2  val3
 746  *    |      |      |               \    |    /
 747  *   Str    Str    Str               \   |   /
 748  *      \    |    /                     Phi
 749  *       \   |   /                       |
 750  *        \  |  /                       Str
 751  *          Phi
 752  *
 753  * This reduces the number of stores and allows for predicated execution.
 754  * Moves Stores back to the end of a function which may be bad.
 755  *
 756  * This is only possible if the predecessor blocks have only one successor.
 757  */
 758 static unsigned optimize_phi(ir_node *phi, void *env)
 759 {
 760   walk_env_t *wenv = env;
 761   int i, n;
 762   ir_node *store, *old_store, *ptr, *block, *phiM, *phiD, *exc, *projM;
 763   ir_mode *mode;
 764   ir_node **inM, **inD;
 765   int *idx;
 766   dbg_info *db = NULL;
 767   ldst_info_t *info;
 768   block_info_t *bl_info;
 769   unsigned res = 0;
 770
 771   /* Must be a memory Phi */
 772   if (get_irn_mode(phi) != mode_M)
 773     return 0;
 774
 775   n = get_Phi_n_preds(phi);
 776   if (n <= 0)
 777     return 0;
 778
 779   store = skip_Proj(get_Phi_pred(phi, 0));
 780   old_store = store;
 781   if (get_irn_op(store) != op_Store)
 782     return 0;
 783
 784   /* abort on dead blocks */
 785   if (is_Block_dead(get_nodes_block(store)))
 786     return 0;
 787
 788   /* check if the block has only one successor */
 789   bl_info = get_irn_link(get_nodes_block(store));
 790   if (bl_info->flags)
 791     return 0;
 792
 793   /* this is the address of the store */
 794   ptr  = get_Store_ptr(store);
 795   mode = get_irn_mode(get_Store_value(store));
 796   info = get_irn_link(store);
 797   exc  = info->exc_block;
 798
 799   for (i = 1; i < n; ++i) {
 800     ir_node *pred = skip_Proj(get_Phi_pred(phi, i));
 801
 802     if (get_irn_op(pred) != op_Store)
 803       return 0;
 804
 805     if (mode != get_irn_mode(get_Store_value(pred)) || ptr != get_Store_ptr(pred))
 806       return 0;
 807
 808     info = get_irn_link(pred);
 809
 810     /* check, if all stores have the same exception flow */
 811     if (exc != info->exc_block)
 812       return 0;
 813
 814     /* abort on dead blocks */
 815     if (is_Block_dead(get_nodes_block(store)))
 816       return 0;
 817
 818     /* check if the block has only one successor */
 819     bl_info = get_irn_link(get_nodes_block(store));
 820     if (bl_info->flags)
 821       return 0;
 822   }
 823
 824   /*
 825    * ok, when we are here, we found all predecessors of a Phi that
 826    * are Stores to the same address. That means whatever we do before
 827    * we enter the block of the Phi, we do a Store.
 828    * So, we can move the store to the current block:
 829    *
 830    *   val1    val2    val3          val1  val2  val3
 831    *    |       |       |               \    |    /
 832    * | Str | | Str | | Str |             \   |   /
 833    *      \     |     /                     Phi
 834    *       \    |    /                       |
 835    *        \   |   /                       Str
 836    *           Phi
 837    *
 838    * Is only allowed if the predecessor blocks have only one successor.
 839    */
 840
 841   /* first step: collect all inputs */
 842   NEW_ARR_A(ir_node *, inM, n);
 843   NEW_ARR_A(ir_node *, inD, n);
 844   NEW_ARR_A(int, idx, n);
 845
 846   for (i = 0; i < n; ++i) {
 847     ir_node *pred = skip_Proj(get_Phi_pred(phi, i));
 848     info = get_irn_link(pred);
 849
 850     inM[i] = get_Store_mem(pred);
 851     inD[i] = get_Store_value(pred);
 852     idx[i] = info->exc_idx;
 853   }
 854   block = get_nodes_block(phi);
 855
 856   /* second step: create a new memory Phi */
 857   phiM = new_rd_Phi(get_irn_dbg_info(phi), current_ir_graph, block, n, inM, mode_M);
 858
 859   /* third step: create a new data Phi */
 860   phiD = new_rd_Phi(get_irn_dbg_info(phi), current_ir_graph, block, n, inD, mode);
 861
 862   /* fourth step: create the Store */
 863   store = new_rd_Store(db, current_ir_graph, block, phiM, ptr, phiD);
 864 #ifdef DO_CACHEOPT
 865   co_set_irn_name(store, co_get_irn_ident(old_store));
 866 #endif
 867
 868   projM = new_rd_Proj(NULL, current_ir_graph, block, store, mode_M, pn_Store_M);
 869
 870   info = get_ldst_info(store, wenv);
 871   info->projs[pn_Store_M] = projM;
 872
 873   /* fifths step: repair exception flow */
 874   if (exc) {
 875     ir_node *projX = new_rd_Proj(NULL, current_ir_graph, block, store, mode_X, pn_Store_X_except);
 876
 877     info->projs[pn_Store_X_except] = projX;
 878     info->exc_block                = exc;
 879     info->exc_idx                  = idx[0];
 880
 881     for (i = 0; i < n; ++i) {
 882       set_Block_cfgpred(exc, idx[i], projX);
 883     }
 884
 885     if (n > 1) {
 886       /* the exception block should be optimized as some inputs are identical now */
 887     }
 888
 889     res |= CF_CHANGED;
 890   }
 891
 892   /* sixth step: replace old Phi */
 893   exchange(phi, projM);
 894
 895   return res | DF_CHANGED;
 896 }
 897
 898 /**
 899  * walker, collects all Load/Store/Proj nodes
 900  */
 901 static void do_load_store_optimize(ir_node *n, void *env)
 902 {
 903   walk_env_t *wenv = env;
 904
 905   switch (get_irn_opcode(n)) {
 906
 907   case iro_Load:
 908     wenv->changes |= optimize_load(n);
 909     break;
 910
 911   case iro_Store:
 912     wenv->changes |= optimize_store(n);
 913     break;
 914
 915   case iro_Phi:
 916     wenv->changes |= optimize_phi(n, env);
 917
 918   default:
 919     ;
 920   }
 921 }
 922
 923 /*
 924  * do the load store optimization
 925  */
 926 void optimize_load_store(ir_graph *irg)
 927 {
 928   walk_env_t env;
 929
 930   assert(get_irg_phase_state(irg) != phase_building);
 931   assert(get_irg_pinned(irg) != op_pin_state_floats &&
 932     "LoadStore optimization needs pinned graph");
 933
 934   if (!get_opt_redundant_LoadStore())
 935     return;
 936
 937   obstack_init(&env.obst);
 938   env.changes = 0;
 939
 940   /* init the links, then collect Loads/Stores/Proj's in lists */
 941   irg_walk_graph(irg, firm_clear_link, collect_nodes, &env);
 942
 943   /* now we have collected enough information, optimize */
 944   irg_walk_graph(irg, NULL, do_load_store_optimize, &env);
 945
 946   obstack_free(&env.obst, NULL);
 947
 948   /* Handle graph state */
 949   if (env.changes) {
 950     if (get_irg_outs_state(current_ir_graph) == outs_consistent)
 951       set_irg_outs_inconsistent(current_ir_graph);
 952   }
 953
 954   if (env.changes & CF_CHANGED) {
 955     /* is this really needed: Yes, control flow changed, block might get Bad. */
 956     if (get_irg_dom_state(current_ir_graph) == dom_consistent)
 957       set_irg_dom_inconsistent(current_ir_graph);
 958   }
 959 }