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