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