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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Dataflow driven Load/Store optimizations, uses some ideas from
  23  *          VanDrunen's LEPRE
  24  * @author  Michael Beck
  25  * @version $Id$
  26  */
  27 #include "config.h"
  28
  29 #include "irnode_t.h"
  30 #include "irflag_t.h"
  31 #include "array_t.h"
  32 #include "ircons.h"
  33 #include "irdom.h"
  34 #include "irgmod.h"
  35 #include "irgwalk.h"
  36 #include "irouts.h"
  37 #include "irgraph.h"
  38 #include "irgopt.h"
  39 #include "iropt.h"
  40 #include "iroptimize.h"
  41 #include "irnodemap.h"
  42 #include "raw_bitset.h"
  43 #include "debug.h"
  44 #include "error.h"
  45
  46 /* maximum number of output Proj's */
  47 #define MAX_PROJ (pn_Load_max > pn_Store_max ? pn_Load_max : pn_Store_max)
  48
  49 /**
  50  * Mapping an address to an dense ID.
  51  */
  52 typedef struct address_entry_t {
  53         unsigned id;          /**< The ID */
  54 } address_entry;
  55
  56 /**
  57  * Memop-flags.
  58  */
  59 enum memop_flags {
  60         FLAG_KILL_ALL    = 1, /**< KILL all addresses */
  61         FLAG_KILLED_NODE = 2, /**< this node was killed */
  62         FLAG_EXCEPTION   = 4, /**< this node has exception flow */
  63         FLAG_IGNORE      = 8, /**< ignore this node (volatile or other) */
  64 };
  65
  66 /**
  67  * A value: This represents a value stored at a given address in
  68  * memory. Do not confuse with values from value numbering.
  69  */
  70 typedef struct value_t value_t;
  71 struct value_t {
  72         ir_node  *address;    /**< the address of this value */
  73         ir_node  *value;      /**< the value itself */
  74         ir_mode  *mode;       /**< the mode of the value */
  75         unsigned id;          /**< address id */
  76 };
  77
  78 /**
  79  * A memop describes an memory-related operation.
  80  * These are Loads/Store and all other ops that might modify
  81  * memory (Calls, CopyB) or causing exceptions.
  82  */
  83 typedef struct memop_t memop_t;
  84 struct memop_t {
  85         value_t  value;      /**< the value of this memop: only defined for Load/Store */
  86         ir_node  *node;      /**< the memory op itself */
  87         ir_node  *mem;       /**< the memory FROM this node */
  88         ir_node  *replace;   /**< the replacement node if this memop is replaced */
  89         memop_t  *next;      /**< links to the next memory op in the block in forward order. */
  90         memop_t  *prev;      /**< links to the previous memory op in the block in forward order. */
  91         unsigned flags;      /**< memop flags */
  92         ir_node  *projs[MAX_PROJ]; /**< Projs of this memory op */
  93 };
  94
  95 /**
  96  * Additional data for every basic block.
  97  */
  98 typedef struct block_t block_t;
  99 struct block_t {
 100         memop_t  *memop_forward;     /**< topologically sorted list of memory ops in this block */
 101         memop_t  *memop_backward;    /**< last memop in the list */
 102         unsigned *avail_out;         /**< out-set of available addresses */
 103         memop_t  **id_2_memop_avail; /**< maps avail address ids to memops */
 104         unsigned *anticL_in;         /**< in-set of anticipated Load addresses */
 105         memop_t  **id_2_memop_antic; /**< maps anticipated address ids to memops */
 106         ir_node  *block;             /**< the associated block */
 107         block_t  *forward_next;      /**< next block entry for forward iteration */
 108         block_t  *backward_next;     /**< next block entry for backward iteration */
 109         memop_t  *avail;             /**< used locally for the avail map */
 110         memop_t  **trans_results;    /**< used to cached translated nodes due antic calculation. */
 111 };
 112
 113 /**
 114  * Metadata for this pass.
 115  */
 116 typedef struct ldst_env_t {
 117         struct obstack  obst;              /**< obstack for temporary data */
 118         ir_nodemap_t    adr_map;           /**< Map addresses to */
 119         block_t         *forward;          /**< Inverse post-order list of all blocks Start->End */
 120         block_t         *backward;         /**< Inverse post-order list of all blocks End->Start */
 121         ir_node         *start_bl;         /**< start block of the current graph */
 122         ir_node         *end_bl;           /**< end block of the current graph */
 123         unsigned        *curr_set;         /**< current set of addresses */
 124         memop_t         **curr_id_2_memop; /**< current map of address ids to memops */
 125         unsigned        curr_adr_id;       /**< number for address mapping */
 126         unsigned        n_mem_ops;         /**< number of memory operations (Loads/Stores) */
 127         unsigned        rbs_size;          /**< size of all bitsets in bytes */
 128         int             max_cfg_preds;     /**< maximum number of block cfg predecessors */
 129         int             changed;           /**< Flags for changed graph state */
 130 #ifdef DEBUG_libfirm
 131         ir_node         **id_2_address;    /**< maps an id to the used address */
 132 #endif
 133 } ldst_env;
 134
 135 /* the one and only environment */
 136 static ldst_env env;
 137
 138 #ifdef DEBUG_libfirm
 139
 140 static firm_dbg_module_t *dbg;
 141
 142 /**
 143  * Dumps the block list.
 144  *
 145  * @param ldst environment
 146  */
 147 static void dump_block_list(ldst_env *env) {
 148         block_t *entry;
 149         memop_t *op;
 150         int     i;
 151
 152         for (entry = env->forward; entry != NULL; entry = entry->forward_next) {
 153                 DB((dbg, LEVEL_2, "%+F {", entry->block));
 154
 155                 i = 0;
 156                 for (op = entry->memop_forward; op != NULL; op = op->next) {
 157                         if (i == 0) {
 158                                 DB((dbg, LEVEL_2, "\n\t"));
 159                         }                       DB((dbg, LEVEL_2, "%+F", op->node));
 160                         if ((op->flags & FLAG_KILL_ALL) == FLAG_KILL_ALL)
 161                                 DB((dbg, LEVEL_2, "X"));
 162                         else if (op->flags & FLAG_KILL_ALL)
 163                                 DB((dbg, LEVEL_2, "K"));
 164                         DB((dbg, LEVEL_2, ", "));
 165
 166                         i = (i + 1) & 3;
 167                 }
 168                 DB((dbg, LEVEL_2, "\n}\n\n"));
 169         }
 170 }  /* dump_block_list */
 171
 172 /**
 173  * Dumps the current set.
 174  *
 175  * @param bl   current block
 176  * @param s    name of the set
 177  */
 178 static void dump_curr(block_t *bl, const char *s) {
 179         unsigned end = env.rbs_size - 1;
 180         unsigned pos;
 181         int      i;
 182
 183         DB((dbg, LEVEL_2, "%s[%+F] = {", s, bl->block));
 184         i = 0;
 185         for (pos = rbitset_next(env.curr_set, 0, 1); pos < end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
 186                 memop_t *op = env.curr_id_2_memop[pos];
 187
 188                 if (i == 0) {
 189                         DB((dbg, LEVEL_2, "\n\t"));
 190                 }
 191
 192                 DB((dbg, LEVEL_2, "<%+F, %+F>, ", op->value.address, op->value.value));
 193                 i = (i + 1) & 3;
 194         }
 195         DB((dbg, LEVEL_2, "\n}\n"));
 196 }  /* dump_curr */
 197
 198 #else
 199 static void dump_block_list(ldst_env *env) {
 200         (void) env;
 201 }
 202 static void dump_curr(block_t *bl, const char *s) {
 203         (void) bl;
 204         (void) s;
 205 }
 206 #endif /* DEBUG_libfirm */
 207
 208 /** Get the block entry for a block node */
 209 static block_t *get_block_entry(const ir_node *block) {
 210         assert(is_Block(block));
 211
 212         return get_irn_link(block);
 213 }  /* get_block_entry */
 214
 215 /** Get the memop entry for a memory operation node */
 216 static memop_t *get_irn_memop(const ir_node *irn) {
 217         assert(! is_Block(irn));
 218         return get_irn_link(irn);
 219 }  /* get_irn_memop */
 220
 221 /**
 222  * Walk over the memory edges from definition to users.
 223  * This ensures, that even operation without memory output are found.
 224  *
 225  * @param irn   start node
 226  * @param pre   pre walker function
 227  * @param post  post walker function
 228  * @param ctx   context parameter for the walker functions
 229  */
 230 static void walk_memory(ir_node *irn, irg_walk_func *pre, irg_walk_func *post, void *ctx) {
 231         int     i;
 232         ir_mode *mode;
 233
 234         mark_irn_visited(irn);
 235
 236         if (pre)
 237                 pre(irn, ctx);
 238
 239         mode = get_irn_mode(irn);
 240         if (mode == mode_M) {
 241                 /* every successor uses memory */
 242                 for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) {
 243                         ir_node *succ = get_irn_out(irn, i);
 244
 245                         if (! irn_visited(succ))
 246                                 walk_memory(succ, pre, post, ctx);
 247                 }
 248         } else if (mode == mode_T) {
 249                 /* only some Proj's uses memory */
 250                 for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) {
 251                         ir_node *proj = get_irn_out(irn, i);
 252
 253                         if (get_irn_mode(proj) == mode_M && ! irn_visited(proj))
 254                                 walk_memory(proj, pre, post, ctx);
 255                 }
 256         }
 257         if (post)
 258                 post(irn, ctx);
 259 }  /* walk_memory */
 260
 261 /**
 262  * Walks over all memory nodes of a graph.
 263  *
 264  * @param irg   a graph
 265  * @param pre   pre walker function
 266  * @param post  post walker function
 267  * @param ctx   context parameter for the walker functions
 268  */
 269 static void walk_memory_irg(ir_graph *irg, irg_walk_func pre, irg_walk_func post, void *ctx) {
 270         inc_irg_visited(irg);
 271
 272         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 273
 274         /*
 275          * there are two possible sources for memory: initial_mem and nomem
 276          * we ignore nomem as this should NOT change the memory
 277          */
 278         walk_memory(get_irg_initial_mem(irg), pre, post, ctx);
 279
 280         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 281 }  /* walk_memory_irg */
 282
 283 /**
 284  * Register an address and allocate a (sparse, 0..n) ID for it.
 285  *
 286  * @param adr  the IR-node representing the address
 287  *
 288  * @return the allocated id
 289  */
 290 static unsigned register_address(ir_node *adr) {
 291         address_entry *entry;
 292
 293         /* skip Confirms and Casts */
 294 restart:
 295         if (is_Confirm(adr)) {
 296                 adr = get_Confirm_value(adr);
 297                 goto restart;
 298         }
 299         if (is_Cast(adr)) {
 300                 adr = get_Cast_op(adr);
 301                 goto restart;
 302         }
 303
 304         entry = ir_nodemap_get(&env.adr_map, adr);
 305
 306         if (entry == NULL) {
 307                 /* new address */
 308                 entry = obstack_alloc(&env.obst, sizeof(*entry));
 309
 310                 entry->id = env.curr_adr_id++;
 311                 ir_nodemap_insert(&env.adr_map, adr, entry);
 312
 313                 DB((dbg, LEVEL_3, "ADDRESS %+F has ID %u\n", adr, entry->id));
 314 #ifdef DEBUG_libfirm
 315                 ARR_APP1(ir_node *, env.id_2_address, adr);
 316 #endif
 317         }
 318         return entry->id;
 319 }  /* register_address */
 320
 321
 322 /**
 323  * translate an address through a Phi node into a given predecessor
 324  * block.
 325  *
 326  * @param address  the address
 327  * @param block    the block
 328  * @param pos      the position of the predecessor in block
 329  */
 330 static ir_node *phi_translate(ir_node *address, const ir_node *block, int pos) {
 331         if (is_Phi(address) && get_nodes_block(address) == block)
 332                 address = get_Phi_pred(address, pos);
 333         return address;
 334 }  /* phi_translate */
 335
 336 /**
 337  * Walker: allocate an block entry for every block
 338  * and register all potential addresses.
 339  */
 340 static void prepare_blocks(ir_node *irn, void *ctx) {
 341         (void)ctx;
 342
 343         if (is_Block(irn)) {
 344                 block_t *entry = obstack_alloc(&env.obst, sizeof(*entry));
 345                 int     n;
 346
 347                 entry->memop_forward    = NULL;
 348                 entry->memop_backward   = NULL;
 349                 entry->avail_out        = NULL;
 350                 entry->id_2_memop_avail = NULL;
 351                 entry->anticL_in        = NULL;
 352                 entry->id_2_memop_antic = NULL;
 353                 entry->block            = irn;
 354                 entry->forward_next     = NULL;
 355                 entry->backward_next    = NULL;
 356                 entry->avail            = NULL;
 357                 entry->trans_results    = NULL;
 358                 set_irn_link(irn, entry);
 359
 360                 set_Block_phis(irn, NULL);
 361
 362                 /* use block marks to track unreachable blocks */
 363                 set_Block_mark(irn, 0);
 364
 365                 n = get_Block_n_cfgpreds(irn);
 366                 if (n > env.max_cfg_preds)
 367                         env.max_cfg_preds = n;
 368         } else {
 369                 ir_mode *mode = get_irn_mode(irn);
 370
 371                 if (mode_is_reference(mode)) {
 372                         /*
 373                          * Register ALL possible addresses: this is overkill yet but
 374                          * simpler then doing it for all possible translated addresses
 375                          * (which would be sufficient in the moment.
 376                          */
 377                         (void)register_address(irn);
 378                 }
 379         }
 380 }  /* prepare_blocks */
 381
 382 /**
 383  * Post-Walker, link in all Phi's
 384  */
 385 static void link_phis(ir_node *irn, void *ctx) {
 386         (void)ctx;
 387
 388         if (is_Phi(irn)) {
 389                 ir_node *block = get_nodes_block(irn);
 390                 add_Block_phi(block, irn);
 391         }
 392 }  /* link_phis */
 393
 394 /**
 395  * Block walker: creates the inverse post-order list for the CFG.
 396  */
 397 static void inverse_post_order(ir_node *block, void *ctx) {
 398         block_t *entry = get_block_entry(block);
 399
 400         (void)ctx;
 401
 402         /* mark this block IS reachable from start */
 403         set_Block_mark(block, 1);
 404
 405         /* create the list in inverse order */
 406         entry->forward_next = env.forward;
 407         env.forward         = entry;
 408
 409         /* remember the first visited (last in list) entry, needed for later */
 410         if (env.backward == NULL)
 411                 env.backward = entry;
 412 }  /* inverse_post_order */
 413
 414 /**
 415  * Block walker: create backward links for the memops of a block.
 416  */
 417 static void collect_backward(ir_node *block, void *ctx) {
 418         block_t *entry = get_block_entry(block);
 419         memop_t *last, *op;
 420
 421         (void)ctx;
 422
 423         /*
 424          * Do NOT link in the end block yet. We want it to be
 425          * the first in the list. This is NOT guaranteed by the walker
 426          * if we have endless loops.
 427          */
 428         if (block != env.end_bl) {
 429                 entry->backward_next = env.backward;
 430
 431                 /* create the list in inverse order */
 432                 env.backward = entry;
 433         }
 434
 435         /* create backward links for all memory ops */
 436         last = NULL;
 437         for (op = entry->memop_forward; op != NULL; op = op->next) {
 438                 op->prev = last;
 439                 last     = op;
 440         }
 441         entry->memop_backward = last;
 442 }  /* collect_backward */
 443
 444 /**
 445  * Allocate a memop.
 446  *
 447  * @param irn  the IR-node representing the memop or NULL
 448  *             if this is a translated (virtual) memop
 449  *
 450  * @return the allocated memop
 451  */
 452 static memop_t *alloc_memop(ir_node *irn) {
 453         memop_t *m = obstack_alloc(&env.obst, sizeof(*m));
 454
 455         m->value.address = NULL;
 456         m->value.value   = NULL;
 457         m->value.mode    = NULL;
 458
 459         m->node          = irn;
 460         m->mem           = NULL;
 461         m->replace       = NULL;
 462         m->next          = NULL;
 463         m->flags         = 0;
 464
 465         memset(m->projs, 0, sizeof(m->projs));
 466
 467         if (irn != NULL)
 468                 set_irn_link(irn, m);
 469         return m;
 470 }  /* alloc_memop */
 471
 472 /**
 473  * Create a memop for a Phi-replacement.
 474  *
 475  * @param op   the memop to clone
 476  * @param phi  the Phi-node representing the new value
 477  */
 478 static memop_t *clone_memop_phi(memop_t *op, ir_node *phi) {
 479         memop_t *m = obstack_alloc(&env.obst, sizeof(*m));
 480
 481         m->value         = op->value;
 482         m->value.value   = phi;
 483
 484         m->node          = phi;
 485         m->replace       = NULL;
 486         m->next          = NULL;
 487         m->flags         = 0;
 488
 489         set_irn_link(phi, m);
 490         return m;
 491 }  /* clone_memop_phi */
 492
 493 /**
 494  * Return the memory properties of a call node.
 495  *
 496  * @param call  the call node
 497  *
 498  * return a bitset of mtp_property_const and mtp_property_pure
 499  */
 500 static unsigned get_Call_memory_properties(ir_node *call) {
 501         ir_type *call_tp = get_Call_type(call);
 502         unsigned prop = get_method_additional_properties(call_tp);
 503
 504         /* check first the call type */
 505         if ((prop & (mtp_property_const|mtp_property_pure)) == 0) {
 506                 /* try the called entity */
 507                 ir_node *ptr = get_Call_ptr(call);
 508
 509                 if (is_Global(ptr)) {
 510                         ir_entity *ent = get_Global_entity(ptr);
 511
 512                         prop = get_entity_additional_properties(ent);
 513                 }
 514         }
 515         return prop & (mtp_property_const|mtp_property_pure);
 516 }  /* get_Call_memory_properties */
 517
 518 /**
 519  * Returns an entity if the address ptr points to a constant one.
 520  *
 521  * @param ptr  the address
 522  *
 523  * @return an entity or NULL
 524  */
 525 static ir_entity *find_constant_entity(ir_node *ptr) {
 526         for (;;) {
 527                 if (is_SymConst(ptr) && get_SymConst_kind(ptr) == symconst_addr_ent) {
 528                         return get_SymConst_entity(ptr);
 529                 } else if (is_Sel(ptr)) {
 530                         ir_entity *ent = get_Sel_entity(ptr);
 531                         ir_type   *tp  = get_entity_owner(ent);
 532
 533                         /* Do not fiddle with polymorphism. */
 534                         if (is_Class_type(get_entity_owner(ent)) &&
 535                                 ((get_entity_n_overwrites(ent)    != 0) ||
 536                                 (get_entity_n_overwrittenby(ent) != 0)   ) )
 537                                 return NULL;
 538
 539                         if (is_Array_type(tp)) {
 540                                 /* check bounds */
 541                                 int i, n;
 542
 543                                 for (i = 0, n = get_Sel_n_indexs(ptr); i < n; ++i) {
 544                                         ir_node *bound;
 545                                         tarval *tlower, *tupper;
 546                                         ir_node *index = get_Sel_index(ptr, i);
 547                                         tarval *tv     = computed_value(index);
 548
 549                                         /* check if the index is constant */
 550                                         if (tv == tarval_bad)
 551                                                 return NULL;
 552
 553                                         bound  = get_array_lower_bound(tp, i);
 554                                         tlower = computed_value(bound);
 555                                         bound  = get_array_upper_bound(tp, i);
 556                                         tupper = computed_value(bound);
 557
 558                                         if (tlower == tarval_bad || tupper == tarval_bad)
 559                                                 return NULL;
 560
 561                                         if (tarval_cmp(tv, tlower) & pn_Cmp_Lt)
 562                                                 return NULL;
 563                                         if (tarval_cmp(tupper, tv) & pn_Cmp_Lt)
 564                                                 return NULL;
 565
 566                                         /* ok, bounds check finished */
 567                                 }
 568                         }
 569
 570                         if (variability_constant == get_entity_variability(ent))
 571                                 return ent;
 572
 573                         /* try next */
 574                         ptr = get_Sel_ptr(ptr);
 575                 } else if (is_Add(ptr)) {
 576                         ir_node *l = get_Add_left(ptr);
 577                         ir_node *r = get_Add_right(ptr);
 578
 579                         if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r))
 580                                 ptr = l;
 581                         else if (get_irn_mode(r) == get_irn_mode(ptr) && is_Const(l))
 582                                 ptr = r;
 583                         else
 584                                 return NULL;
 585
 586                         /* for now, we support only one addition, reassoc should fold all others */
 587                         if (! is_SymConst(ptr) && !is_Sel(ptr))
 588                                 return NULL;
 589                 } else if (is_Sub(ptr)) {
 590                         ir_node *l = get_Sub_left(ptr);
 591                         ir_node *r = get_Sub_right(ptr);
 592
 593                         if (get_irn_mode(l) == get_irn_mode(ptr) &&     is_Const(r))
 594                                 ptr = l;
 595                         else
 596                                 return NULL;
 597                         /* for now, we support only one subtraction, reassoc should fold all others */
 598                         if (! is_SymConst(ptr) && !is_Sel(ptr))
 599                                 return NULL;
 600                 } else
 601                         return NULL;
 602         }
 603 }  /* find_constant_entity */
 604
 605 /**
 606  * Return the Selection index of a Sel node from dimension n
 607  */
 608 static long get_Sel_array_index_long(ir_node *n, int dim) {
 609         ir_node *index = get_Sel_index(n, dim);
 610         assert(is_Const(index));
 611         return get_tarval_long(get_Const_tarval(index));
 612 }  /* get_Sel_array_index_long */
 613
 614 /**
 615  * Returns the accessed component graph path for an
 616  * node computing an address.
 617  *
 618  * @param ptr    the node computing the address
 619  * @param depth  current depth in steps upward from the root
 620  *               of the address
 621  */
 622 static compound_graph_path *rec_get_accessed_path(ir_node *ptr, int depth) {
 623         compound_graph_path *res = NULL;
 624         ir_entity           *root, *field, *ent;
 625         int                 path_len, pos, idx;
 626         tarval              *tv;
 627         ir_type             *tp;
 628
 629         if (is_SymConst(ptr)) {
 630                 /* a SymConst. If the depth is 0, this is an access to a global
 631                  * entity and we don't need a component path, else we know
 632                  * at least its length.
 633                  */
 634                 assert(get_SymConst_kind(ptr) == symconst_addr_ent);
 635                 root = get_SymConst_entity(ptr);
 636                 res = (depth == 0) ? NULL : new_compound_graph_path(get_entity_type(root), depth);
 637         } else if (is_Sel(ptr)) {
 638                 /* it's a Sel, go up until we find the root */
 639                 res = rec_get_accessed_path(get_Sel_ptr(ptr), depth+1);
 640                 if (res == NULL)
 641                         return NULL;
 642
 643                 /* fill up the step in the path at the current position */
 644                 field    = get_Sel_entity(ptr);
 645                 path_len = get_compound_graph_path_length(res);
 646                 pos      = path_len - depth - 1;
 647                 set_compound_graph_path_node(res, pos, field);
 648
 649                 if (is_Array_type(get_entity_owner(field))) {
 650                         assert(get_Sel_n_indexs(ptr) == 1 && "multi dim arrays not implemented");
 651                         set_compound_graph_path_array_index(res, pos, get_Sel_array_index_long(ptr, 0));
 652                 }
 653         } else if (is_Add(ptr)) {
 654                 ir_node *l    = get_Add_left(ptr);
 655                 ir_node *r    = get_Add_right(ptr);
 656                 ir_mode *mode = get_irn_mode(ptr);
 657                 tarval  *tmp;
 658
 659                 if (is_Const(r) && get_irn_mode(l) == mode) {
 660                         ptr = l;
 661                         tv  = get_Const_tarval(r);
 662                 } else {
 663                         ptr = r;
 664                         tv  = get_Const_tarval(l);
 665                 }
 666 ptr_arith:
 667                 mode = get_tarval_mode(tv);
 668                 tmp  = tv;
 669
 670                 /* ptr must be a Sel or a SymConst, this was checked in find_constant_entity() */
 671                 if (is_Sel(ptr)) {
 672                         field = get_Sel_entity(ptr);
 673                 } else {
 674                         field = get_SymConst_entity(ptr);
 675                 }
 676                 idx = 0;
 677                 for (ent = field;;) {
 678                         unsigned size;
 679                         tarval   *sz, *tv_index, *tlower, *tupper;
 680                         ir_node  *bound;
 681
 682                         tp = get_entity_type(ent);
 683                         if (! is_Array_type(tp))
 684                                 break;
 685                         ent = get_array_element_entity(tp);
 686                         size = get_type_size_bytes(get_entity_type(ent));
 687                         sz   = new_tarval_from_long(size, mode);
 688
 689                         tv_index = tarval_div(tmp, sz);
 690                         tmp      = tarval_mod(tmp, sz);
 691
 692                         if (tv_index == tarval_bad || tmp == tarval_bad)
 693                                 return NULL;
 694
 695                         assert(get_array_n_dimensions(tp) == 1 && "multiarrays not implemented");
 696                         bound  = get_array_lower_bound(tp, 0);
 697                         tlower = computed_value(bound);
 698                         bound  = get_array_upper_bound(tp, 0);
 699                         tupper = computed_value(bound);
 700
 701                         if (tlower == tarval_bad || tupper == tarval_bad)
 702                                 return NULL;
 703
 704                         if (tarval_cmp(tv_index, tlower) & pn_Cmp_Lt)
 705                                 return NULL;
 706                         if (tarval_cmp(tupper, tv_index) & pn_Cmp_Lt)
 707                                 return NULL;
 708
 709                         /* ok, bounds check finished */
 710                         ++idx;
 711                 }
 712                 if (! tarval_is_null(tmp)) {
 713                         /* access to some struct/union member */
 714                         return NULL;
 715                 }
 716
 717                 /* should be at least ONE array */
 718                 if (idx == 0)
 719                         return NULL;
 720
 721                 res = rec_get_accessed_path(ptr, depth + idx);
 722                 if (res == NULL)
 723                         return NULL;
 724
 725                 path_len = get_compound_graph_path_length(res);
 726                 pos      = path_len - depth - idx;
 727
 728                 for (ent = field;;) {
 729                         unsigned size;
 730                         tarval   *sz, *tv_index;
 731                         long     index;
 732
 733                         tp = get_entity_type(ent);
 734                         if (! is_Array_type(tp))
 735                                 break;
 736                         ent = get_array_element_entity(tp);
 737                         set_compound_graph_path_node(res, pos, ent);
 738
 739                         size = get_type_size_bytes(get_entity_type(ent));
 740                         sz   = new_tarval_from_long(size, mode);
 741
 742                         tv_index = tarval_div(tv, sz);
 743                         tv       = tarval_mod(tv, sz);
 744
 745                         /* worked above, should work again */
 746                         assert(tv_index != tarval_bad && tv != tarval_bad);
 747
 748                         /* bounds already checked above */
 749                         index = get_tarval_long(tv_index);
 750                         set_compound_graph_path_array_index(res, pos, index);
 751                         ++pos;
 752                 }
 753         } else if (is_Sub(ptr)) {
 754                 ir_node *l = get_Sub_left(ptr);
 755                 ir_node *r = get_Sub_right(ptr);
 756
 757                 ptr = l;
 758                 tv  = get_Const_tarval(r);
 759                 tv  = tarval_neg(tv);
 760                 goto ptr_arith;
 761         }
 762         return res;
 763 }  /* rec_get_accessed_path */
 764
 765 /**
 766  * Returns an access path or NULL.  The access path is only
 767  * valid, if the graph is in phase_high and _no_ address computation is used.
 768  */
 769 static compound_graph_path *get_accessed_path(ir_node *ptr) {
 770         compound_graph_path *gr = rec_get_accessed_path(ptr, 0);
 771         return gr;
 772 }  /* get_accessed_path */
 773
 774 typedef struct path_entry {
 775         ir_entity         *ent;
 776         struct path_entry *next;
 777         long              index;
 778 } path_entry;
 779
 780 static ir_node *rec_find_compound_ent_value(ir_node *ptr, path_entry *next) {
 781         path_entry       entry, *p;
 782         ir_entity        *ent, *field;
 783         ir_initializer_t *initializer;
 784         tarval           *tv;
 785         ir_type          *tp;
 786         unsigned         n;
 787
 788         entry.next = next;
 789         if (is_SymConst(ptr)) {
 790                 /* found the root */
 791                 ent         = get_SymConst_entity(ptr);
 792                 initializer = get_entity_initializer(ent);
 793                 for (p = next; p != NULL;) {
 794                         if (initializer->kind != IR_INITIALIZER_COMPOUND)
 795                                 return NULL;
 796                         n  = get_initializer_compound_n_entries(initializer);
 797                         tp = get_entity_type(ent);
 798
 799                         if (is_Array_type(tp)) {
 800                                 ent = get_array_element_entity(tp);
 801                                 if (ent != p->ent) {
 802                                         /* a missing [0] */
 803                                         if (0 >= n)
 804                                                 return NULL;
 805                                         initializer = get_initializer_compound_value(initializer, 0);
 806                                         continue;
 807                                 }
 808                         }
 809                         if (p->index >= (int) n)
 810                                 return NULL;
 811                         initializer = get_initializer_compound_value(initializer, p->index);
 812
 813                         ent = p->ent;
 814                         p   = p->next;
 815                 }
 816                 tp = get_entity_type(ent);
 817                 while (is_Array_type(tp)) {
 818                         ent = get_array_element_entity(tp);
 819                         tp = get_entity_type(ent);
 820                         /* a missing [0] */
 821                         n  = get_initializer_compound_n_entries(initializer);
 822                         if (0 >= n)
 823                                 return NULL;
 824                         initializer = get_initializer_compound_value(initializer, 0);
 825                 }
 826
 827                 switch (initializer->kind) {
 828                 case IR_INITIALIZER_CONST:
 829                         return get_initializer_const_value(initializer);
 830                 case IR_INITIALIZER_TARVAL:
 831                 case IR_INITIALIZER_NULL:
 832                 default:
 833                         return NULL;
 834                 }
 835         } else if (is_Sel(ptr)) {
 836                 entry.ent = field = get_Sel_entity(ptr);
 837                 tp = get_entity_owner(field);
 838                 if (is_Array_type(tp)) {
 839                         assert(get_Sel_n_indexs(ptr) == 1 && "multi dim arrays not implemented");
 840                         entry.index = get_Sel_array_index_long(ptr, 0) - get_array_lower_bound_int(tp, 0);
 841                 } else {
 842                         int i, n_members = get_compound_n_members(tp);
 843                         for (i = 0; i < n_members; ++i) {
 844                                 if (get_compound_member(tp, i) == field)
 845                                         break;
 846                         }
 847                         if (i >= n_members) {
 848                                 /* not found: should NOT happen */
 849                                 return NULL;
 850                         }
 851                         entry.index = i;
 852                 }
 853                 return rec_find_compound_ent_value(get_Sel_ptr(ptr), &entry);
 854         }  else if (is_Add(ptr)) {
 855                 ir_node  *l = get_Add_left(ptr);
 856                 ir_node  *r = get_Add_right(ptr);
 857                 ir_mode  *mode;
 858                 unsigned pos;
 859
 860                 if (is_Const(r)) {
 861                         ptr = l;
 862                         tv  = get_Const_tarval(r);
 863                 } else {
 864                         ptr = r;
 865                         tv  = get_Const_tarval(l);
 866                 }
 867 ptr_arith:
 868                 mode = get_tarval_mode(tv);
 869
 870                 /* ptr must be a Sel or a SymConst, this was checked in find_constant_entity() */
 871                 if (is_Sel(ptr)) {
 872                         field = get_Sel_entity(ptr);
 873                 } else {
 874                         field = get_SymConst_entity(ptr);
 875                 }
 876
 877                 /* count needed entries */
 878                 pos = 0;
 879                 for (ent = field;;) {
 880                         tp = get_entity_type(ent);
 881                         if (! is_Array_type(tp))
 882                                 break;
 883                         ent = get_array_element_entity(tp);
 884                         ++pos;
 885                 }
 886                 /* should be at least ONE entry */
 887                 if (pos == 0)
 888                         return NULL;
 889
 890                 /* allocate the right number of entries */
 891                 NEW_ARR_A(path_entry, p, pos);
 892
 893                 /* fill them up */
 894                 pos = 0;
 895                 for (ent = field;;) {
 896                         unsigned size;
 897                         tarval   *sz, *tv_index, *tlower, *tupper;
 898                         long     index;
 899                         ir_node  *bound;
 900
 901                         tp = get_entity_type(ent);
 902                         if (! is_Array_type(tp))
 903                                 break;
 904                         ent = get_array_element_entity(tp);
 905                         p[pos].ent  = ent;
 906                         p[pos].next = &p[pos + 1];
 907
 908                         size = get_type_size_bytes(get_entity_type(ent));
 909                         sz   = new_tarval_from_long(size, mode);
 910
 911                         tv_index = tarval_div(tv, sz);
 912                         tv       = tarval_mod(tv, sz);
 913
 914                         if (tv_index == tarval_bad || tv == tarval_bad)
 915                                 return NULL;
 916
 917                         assert(get_array_n_dimensions(tp) == 1 && "multiarrays not implemented");
 918                         bound  = get_array_lower_bound(tp, 0);
 919                         tlower = computed_value(bound);
 920                         bound  = get_array_upper_bound(tp, 0);
 921                         tupper = computed_value(bound);
 922
 923                         if (tlower == tarval_bad || tupper == tarval_bad)
 924                                 return NULL;
 925
 926                         if (tarval_cmp(tv_index, tlower) & pn_Cmp_Lt)
 927                                 return NULL;
 928                         if (tarval_cmp(tupper, tv_index) & pn_Cmp_Lt)
 929                                 return NULL;
 930
 931                         /* ok, bounds check finished */
 932                         index = get_tarval_long(tv_index);
 933                         p[pos].index = index;
 934                         ++pos;
 935                 }
 936                 if (! tarval_is_null(tv)) {
 937                         /* hmm, wrong access */
 938                         return NULL;
 939                 }
 940                 p[pos - 1].next = next;
 941                 return rec_find_compound_ent_value(ptr, p);
 942         } else if (is_Sub(ptr)) {
 943                 ir_node *l = get_Sub_left(ptr);
 944                 ir_node *r = get_Sub_right(ptr);
 945
 946                 ptr = l;
 947                 tv  = get_Const_tarval(r);
 948                 tv  = tarval_neg(tv);
 949                 goto ptr_arith;
 950         }
 951         return NULL;
 952 }  /* rec_find_compound_ent_value */
 953
 954 static ir_node *find_compound_ent_value(ir_node *ptr) {
 955         return rec_find_compound_ent_value(ptr, NULL);
 956 }  /* find_compound_ent_value */
 957
 958 /**
 959  * Mark a Load memop to be replace by a definition
 960  *
 961  * @param op  the Load memop
 962  */
 963 static void mark_replace_load(memop_t *op, ir_node *def) {
 964         op->replace = def;
 965         op->flags |= FLAG_KILLED_NODE;
 966         env.changed = 1;
 967 }  /* mark_replace_load */
 968
 969 /**
 970  * Mark a Store memop to be removed.
 971  *
 972  * @param op  the Store memop
 973  */
 974 static void mark_remove_store(memop_t *op) {
 975         op->flags |= FLAG_KILLED_NODE;
 976         env.changed = 1;
 977 }  /* mark_remove_store */
 978
 979 /**
 980  * Update a memop for a Load.
 981  *
 982  * @param m  the memop
 983  */
 984 static void update_Load_memop(memop_t *m) {
 985         int       i;
 986         ir_node   *load = m->node;
 987         ir_node   *ptr;
 988         ir_entity *ent;
 989
 990         if (get_Load_volatility(load) == volatility_is_volatile)
 991                 m->flags |= FLAG_IGNORE;
 992
 993         ptr = get_Load_ptr(load);
 994
 995         m->value.address = ptr;
 996
 997         for (i = get_irn_n_outs(load) - 1; i >= 0; --i) {
 998                 ir_node *proj = get_irn_out(load, i);
 999                 long    pn;
1000
1001                 /* beware of keep edges */
1002                 if (is_End(proj))
1003                         continue;
1004
1005                 pn = get_Proj_proj(proj);
1006                 m->projs[pn] = proj;
1007                 switch (pn) {
1008                 case pn_Load_res:
1009                         m->value.value = proj;
1010                         m->value.mode  = get_irn_mode(proj);
1011                         break;
1012                 case pn_Load_X_except:
1013                         m->flags |= FLAG_EXCEPTION;
1014                         break;
1015                 case pn_Load_M:
1016                         m->mem = proj;
1017                         break;
1018                 case pn_Load_X_regular:
1019                         break;
1020                 default:
1021                         panic("Unsupported Proj from Load %+F", proj);
1022                 }
1023         }
1024
1025         /* check if we can determine the entity that will be loaded */
1026         ent = find_constant_entity(ptr);
1027
1028         if (ent != NULL                                     &&
1029                 allocation_static == get_entity_allocation(ent) &&
1030                 visibility_external_allocated != get_entity_visibility(ent)) {
1031                 /* a static allocation that is not external: there should be NO exception
1032                  * when loading even if we cannot replace the load itself. */
1033                 ir_node *value = NULL;
1034
1035                 /* no exception, clear the m fields as it might be checked later again */
1036                 if (m->projs[pn_Load_X_except]) {
1037                         exchange(m->projs[pn_Load_X_except], new_Bad());
1038                         m->projs[pn_Load_X_except] = NULL;
1039                         m->flags &= ~FLAG_EXCEPTION;
1040                         env.changed = 1;
1041                 }
1042                 if (m->projs[pn_Load_X_regular]) {
1043                         exchange(m->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
1044                         m->projs[pn_Load_X_regular] = NULL;
1045                         env.changed = 1;
1046                 }
1047
1048                 if (variability_constant == get_entity_variability(ent)) {
1049                         if (is_atomic_entity(ent)) {
1050                                 /* Might not be atomic after lowering of Sels.  In this case we
1051                                  * could also load, but it's more complicated. */
1052                                 /* more simpler case: we load the content of a constant value:
1053                                  * replace it by the constant itself */
1054                                 value = get_atomic_ent_value(ent);
1055                         } else if (ent->has_initializer) {
1056                                 /* new style initializer */
1057                                 value = find_compound_ent_value(ptr);
1058                         } else {
1059                                 /* old style initializer */
1060                                 compound_graph_path *path = get_accessed_path(ptr);
1061
1062                                 if (path != NULL) {
1063                                         assert(is_proper_compound_graph_path(path, get_compound_graph_path_length(path)-1));
1064
1065                                         value = get_compound_ent_value_by_path(ent, path);
1066                                         DB((dbg, LEVEL_1, "  Constant access at %F%F resulted in %+F\n", ent, path, value));
1067                                         free_compound_graph_path(path);
1068                                 }
1069                         }
1070                         if (value != NULL)
1071                                 value = can_replace_load_by_const(load, value);
1072                 }
1073
1074                 if (value != NULL) {
1075                         /* we completely replace the load by this value */
1076                         DB((dbg, LEVEL_1, "Replacing Load %+F by constant %+F\n", m->node, value));
1077                         mark_replace_load(m, value);
1078                         return;
1079                 }
1080         }
1081
1082         if (m->value.value != NULL && !(m->flags & FLAG_IGNORE)) {
1083                 /* only create an address if this node is NOT killed immediately or ignored */
1084                 m->value.id = register_address(ptr);
1085                 ++env.n_mem_ops;
1086         } else {
1087                 /* no user, KILL it */
1088                 mark_replace_load(m, NULL);
1089         }
1090 }  /* update_Load_memop */
1091
1092 /**
1093  * Update a memop for a Store.
1094  *
1095  * @param m  the memop
1096  */
1097 static void update_Store_memop(memop_t *m) {
1098         int     i;
1099         ir_node *store = m->node;
1100         ir_node *adr   = get_Store_ptr(store);
1101
1102         if (get_Store_volatility(store) == volatility_is_volatile) {
1103                 m->flags |= FLAG_IGNORE;
1104         } else {
1105                 /* only create an address if this node is NOT ignored */
1106                 m->value.id = register_address(adr);
1107                 ++env.n_mem_ops;
1108         }
1109
1110         m->value.address = adr;
1111
1112         for (i = get_irn_n_outs(store) - 1; i >= 0; --i) {
1113                 ir_node *proj = get_irn_out(store, i);
1114                 long    pn;
1115
1116                 /* beware of keep edges */
1117                 if (is_End(proj))
1118                         continue;
1119
1120                 pn = get_Proj_proj(proj);
1121                 m->projs[pn] = proj;
1122                 switch (pn) {
1123                 case pn_Store_X_except:
1124                         m->flags |= FLAG_EXCEPTION;
1125                         break;
1126                 case pn_Store_M:
1127                         m->mem = proj;
1128                         break;
1129                 case pn_Store_X_regular:
1130                         break;
1131                 default:
1132                         panic("Unsupported Proj from Store %+F", proj);
1133                 }
1134         }
1135         m->value.value = get_Store_value(store);
1136         m->value.mode  = get_irn_mode(m->value.value);
1137 }  /* update_Store_memop */
1138
1139 /**
1140  * Update a memop for a Call.
1141  *
1142  * @param m  the memop
1143  */
1144 static void update_Call_memop(memop_t *m) {
1145         ir_node  *call = m->node;
1146         unsigned prop  = get_Call_memory_properties(call);
1147         int      i;
1148
1149         if (prop & mtp_property_const) {
1150                 /* A constant call did NOT use memory at all, we
1151                    can kick it from the list. */
1152         } else if (prop & mtp_property_pure) {
1153                 /* pure calls READ memory */
1154                 m->flags = 0;
1155         } else
1156                 m->flags = FLAG_KILL_ALL;
1157
1158         for (i = get_irn_n_outs(call) - 1; i >= 0; --i) {
1159                 ir_node *proj = get_irn_out(call, i);
1160
1161                 /* beware of keep edges */
1162                 if (is_End(proj))
1163                         continue;
1164
1165                 switch (get_Proj_proj(proj)) {
1166                 case pn_Call_X_except:
1167                         m->flags |= FLAG_EXCEPTION;
1168                         break;
1169                 case pn_Call_M_regular:
1170                         m->mem = proj;
1171                         break;
1172                 }
1173         }
1174 }  /* update_Call_memop */
1175
1176 /**
1177  * Update a memop for a Div/Mod/Quot/DivMod.
1178  *
1179  * @param m  the memop
1180  */
1181 static void update_DivOp_memop(memop_t *m) {
1182         ir_node *div = m->node;
1183         int     i;
1184
1185         for (i = get_irn_n_outs(div) - 1; i >= 0; --i) {
1186                 ir_node *proj = get_irn_out(div, i);
1187
1188                 /* beware of keep edges */
1189                 if (is_End(proj))
1190                         continue;
1191
1192                 switch (get_Proj_proj(proj)) {
1193                 case pn_Generic_X_except:
1194                         m->flags |= FLAG_EXCEPTION;
1195                         break;
1196                 case pn_Generic_M_regular:
1197                         m->mem = proj;
1198                         break;
1199                 }
1200         }
1201 }  /* update_DivOp_memop */
1202
1203 /**
1204  * Update a memop for a Phi.
1205  *
1206  * @param m  the memop
1207  */
1208 static void update_Phi_memop(memop_t *m) {
1209         /* the Phi is it's own mem */
1210         m->mem = m->node;
1211 }  /* update_Phi_memop */
1212
1213 /**
1214  * Memory walker: collect all memory ops and build topological lists.
1215  */
1216 static void collect_memops(ir_node *irn, void *ctx) {
1217         memop_t  *op;
1218         ir_node  *block;
1219         block_t  *entry;
1220
1221         (void) ctx;
1222         if (is_Proj(irn)) {
1223                 /* we can safely ignore ProjM's except the initial memory */
1224                 if (irn != get_irg_initial_mem(current_ir_graph))
1225                         return;
1226         }
1227
1228         op    = alloc_memop(irn);
1229         block = get_nodes_block(irn);
1230         entry = get_block_entry(block);
1231
1232         if (is_Phi(irn)) {
1233                 update_Phi_memop(op);
1234                 /* Phis must be always placed first */
1235                 op->next = entry->memop_forward;
1236                 entry->memop_forward = op;
1237                 if (entry->memop_backward == NULL)
1238                         entry->memop_backward = op;
1239         } else {
1240                 switch (get_irn_opcode(irn)) {
1241                 case iro_Load:
1242                         update_Load_memop(op);
1243                         break;
1244                 case iro_Store:
1245                         update_Store_memop(op);
1246                         break;
1247                 case iro_Call:
1248                         update_Call_memop(op);
1249                         break;
1250                 case iro_Sync:
1251                 case iro_Pin:
1252                         op->mem = irn;
1253                         break;
1254                 case iro_Proj:
1255                         /* initial memory */
1256                         op->mem = irn;
1257                         break;
1258                 case iro_Return:
1259                 case iro_End:
1260                         /* we can those to find the memory edge */
1261                         break;
1262                 case iro_Div:
1263                 case iro_DivMod:
1264                 case iro_Quot:
1265                 case iro_Mod:
1266                         update_DivOp_memop(op);
1267                         break;
1268
1269                 case iro_Builtin:
1270                         /* TODO: handle some builtins */
1271                 default:
1272                         /* unsupported operation */
1273                         op->flags = FLAG_KILL_ALL;
1274                 }
1275
1276
1277                 /* all other should be placed last */
1278                 if (entry->memop_backward == NULL) {
1279                         entry->memop_forward = entry->memop_backward = op;
1280                 } else {
1281                         entry->memop_backward->next = op;
1282                         entry->memop_backward       = op;
1283                 }
1284         }
1285 }  /* collect_memops */
1286
1287 /**
1288  * Find an address in the current set.
1289  *
1290  * @param value  the value to be searched for
1291  *
1292  * @return a memop for the value or NULL if the value does
1293  *         not exists in the set or cannot be converted into
1294  *         the requested mode
1295  */
1296 static memop_t *find_address(const value_t *value) {
1297         if (rbitset_is_set(env.curr_set, value->id)) {
1298                 memop_t *res = env.curr_id_2_memop[value->id];
1299
1300                 if (res->value.mode == value->mode)
1301                         return res;
1302                 /* allow hidden casts */
1303                 if (get_mode_arithmetic(res->value.mode) == irma_twos_complement &&
1304                     get_mode_arithmetic(value->mode) == irma_twos_complement &&
1305                     get_mode_size_bits(res->value.mode) == get_mode_size_bits(value->mode))
1306                         return res;
1307         }
1308         return NULL;
1309 }  /* find_address */
1310
1311 /**
1312  * Find an address in the avail_out set.
1313  *
1314  * @param bl     the block
1315  */
1316 static memop_t *find_address_avail(const block_t *bl, unsigned id, const ir_mode *mode) {
1317         if (rbitset_is_set(bl->avail_out, id)) {
1318                 memop_t *res = bl->id_2_memop_avail[id];
1319
1320                 if (res->value.mode == mode)
1321                         return res;
1322                 /* allow hidden casts */
1323                 if (get_mode_arithmetic(res->value.mode) == irma_twos_complement &&
1324                     get_mode_arithmetic(mode) == irma_twos_complement &&
1325                     get_mode_size_bits(res->value.mode) == get_mode_size_bits(mode))
1326                         return res;
1327         }
1328         return NULL;
1329 }  /* find_address_avail */
1330
1331 /**
1332  * Kill all addresses from the current set.
1333  */
1334 static void kill_all(void) {
1335         rbitset_clear_all(env.curr_set, env.rbs_size);
1336
1337         /* set sentinel */
1338         rbitset_set(env.curr_set, env.rbs_size - 1);
1339 }  /* kill_all */
1340
1341 /**
1342  * Kill memops that are not alias free due to a Store value from the current set.
1343  *
1344  * @param value  the Store value
1345  */
1346 static void kill_memops(const value_t *value) {
1347         unsigned end = env.rbs_size - 1;
1348         unsigned pos;
1349
1350         for (pos = rbitset_next(env.curr_set, 0, 1); pos < end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
1351                 memop_t *op = env.curr_id_2_memop[pos];
1352
1353                 if (ir_no_alias != get_alias_relation(current_ir_graph, value->address, value->mode,
1354                                                           op->value.address, op->value.mode)) {
1355                         rbitset_clear(env.curr_set, pos);
1356                         env.curr_id_2_memop[pos] = NULL;
1357                         DB((dbg, LEVEL_2, "KILLING %+F because of possible alias address %+F\n", op->node, value->address));
1358                 }
1359         }
1360 }  /* kill_memops */
1361
1362 /**
1363  * Add the value of a memop to the current set.
1364  *
1365  * @param op  the memory op
1366  */
1367 static void add_memop(memop_t *op) {
1368         rbitset_set(env.curr_set, op->value.id);
1369         env.curr_id_2_memop[op->value.id] = op;
1370 }  /* add_memop */
1371
1372 /**
1373  * Add the value of a memop to the avail_out set.
1374  *
1375  * @param bl  the block
1376  * @param op  the memory op
1377  */
1378 static void add_memop_avail(block_t *bl, memop_t *op) {
1379         rbitset_set(bl->avail_out, op->value.id);
1380         bl->id_2_memop_avail[op->value.id] = op;
1381 }  /* add_memop_avail */
1382
1383 /**
1384  * Check, if we can convert a value of one mode to another mode
1385  * without changing the representation of bits.
1386  *
1387  * @param from  the original mode
1388  * @param to    the destination mode
1389  */
1390 static int can_convert_to(const ir_mode *from, const ir_mode *to) {
1391         if (get_mode_arithmetic(from) == irma_twos_complement &&
1392             get_mode_arithmetic(to) == irma_twos_complement &&
1393             get_mode_size_bits(from) == get_mode_size_bits(to))
1394                 return 1;
1395         return 0;
1396 }  /* can_convert_to */
1397
1398 /**
1399  * Add a Conv to the requested mode if needed.
1400  *
1401  * @param irn   the IR-node to convert
1402  * @param mode  the destination mode
1403  *
1404  * @return the possible converted node or NULL
1405  *         if the conversion is not possible
1406  */
1407 static ir_node *conv_to(ir_node *irn, ir_mode *mode) {
1408         ir_mode *other = get_irn_mode(irn);
1409         if (other != mode) {
1410                 /* different modes: check if conversion is possible without changing the bits */
1411                 if (can_convert_to(other, mode)) {
1412                         ir_node *block = get_nodes_block(irn);
1413                         return new_r_Conv(block, irn, mode);
1414                 }
1415                 /* otherwise not possible ... yet */
1416                 return NULL;
1417         }
1418         return irn;
1419 }  /* conv_to */
1420
1421 /**
1422  * Update the address of an value if this address was a load result
1423  * and the load is killed now.
1424  *
1425  * @param value  the value whose address is updated
1426  */
1427 static void update_address(value_t *value) {
1428         if (is_Proj(value->address)) {
1429                 ir_node *load = get_Proj_pred(value->address);
1430
1431                 if (is_Load(load)) {
1432                         const memop_t *op = get_irn_memop(load);
1433
1434                         if (op->flags & FLAG_KILLED_NODE)
1435                                 value->address = op->replace;
1436                 }
1437         }
1438 }  /* update_address */
1439
1440 /**
1441  * Do forward dataflow analysis on the given block and calculate the
1442  * GEN and KILL in the current (avail) set.
1443  *
1444  * @param bl  the block
1445  */
1446 static void calc_gen_kill_avail(block_t *bl) {
1447         memop_t *op;
1448         ir_node *def;
1449
1450         for (op = bl->memop_forward; op != NULL; op = op->next) {
1451                 switch (get_irn_opcode(op->node)) {
1452                 case iro_Phi:
1453                         /* meet */
1454                         break;
1455                 case iro_Sync:
1456                         /* join */
1457                         break;
1458                 case iro_Load:
1459                         if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) {
1460                                 /* do we have this already? */
1461                                 memop_t *other;
1462
1463                                 update_address(&op->value);
1464                                 other = find_address(&op->value);
1465                                 if (other != NULL && other != op) {
1466                                         def = conv_to(other->value.value, op->value.mode);
1467                                         if (def != NULL) {
1468 #ifdef DEBUG_libfirm
1469                                                 if (is_Store(other->node)) {
1470                                                         /* RAW */
1471                                                         DB((dbg, LEVEL_1, "RAW %+F <- %+F(%+F)\n", op->node, def, other->node));
1472                                                 } else {
1473                                                         /* RAR */
1474                                                         DB((dbg, LEVEL_1, "RAR %+F <- %+F(%+F)\n", op->node, def, other->node));
1475                                                 }
1476 #endif
1477                                                 mark_replace_load(op, def);
1478                                                 /* do NOT change the memop table */
1479                                                 continue;
1480                                         }
1481                                 }
1482                                 /* add this value */
1483                                 add_memop(op);
1484                         }
1485                         break;
1486                 case iro_Store:
1487                         if (! (op->flags & FLAG_KILLED_NODE)) {
1488                                 /* do we have this store already */
1489                                 memop_t *other;
1490
1491                                 update_address(&op->value);
1492                                 other = find_address(&op->value);
1493                                 if (other != NULL) {
1494                                         if (is_Store(other->node)) {
1495                                                 if (op != other && !(other->flags & FLAG_IGNORE) &&
1496                                                     get_nodes_block(other->node) == get_nodes_block(op->node)) {
1497                                                         /*
1498                                                          * A WAW in the same block we can kick the first store.
1499                                                          * This is a shortcut: we know that the second Store will be anticipated
1500                                                          * then in an case.
1501                                                          */
1502                                                         DB((dbg, LEVEL_1, "WAW %+F <- %+F\n", other->node, op->node));
1503                                                         mark_remove_store(other);
1504                                                         /* FIXME: a Load might be get freed due to this killed store */
1505                                                 }
1506                                         } else if (other->value.value == op->value.value && !(op->flags & FLAG_IGNORE)) {
1507                                                 /* WAR */
1508                                                 DB((dbg, LEVEL_1, "WAR %+F <- %+F\n", op->node, other->node));
1509                                                 mark_remove_store(op);
1510                                                 /* do NOT change the memop table */
1511                                                 continue;
1512                                         }
1513                                 }
1514                                 /* KILL all possible aliases */
1515                                 kill_memops(&op->value);
1516                                 /* add this value */
1517                                 add_memop(op);
1518                         }
1519                         break;
1520                 default:
1521                         if (op->flags & FLAG_KILL_ALL)
1522                                 kill_all();
1523                 }
1524         }
1525 }  /* calc_gen_kill_avail */
1526
1527 #define BYTE_SIZE(x)  (((x) + 7) >> 3)
1528
1529 /**
1530  * Do forward dataflow analysis on a given block to calculate the avail_out set
1531  * for this block only.
1532  *
1533  * @param block  the block
1534  */
1535 static void forward_avail(block_t *bl) {
1536         /* fill the data from the current block */
1537         env.curr_id_2_memop = bl->id_2_memop_avail;
1538         env.curr_set        = bl->avail_out;
1539
1540         calc_gen_kill_avail(bl);
1541         dump_curr(bl, "Avail_out");
1542 }  /* forward_avail */
1543
1544 /**
1545  * Do backward dataflow analysis on a given block to calculate the antic set
1546  * of Loaded addresses.
1547  *
1548  * @param bl  the block
1549  *
1550  * @return non-zero if the set has changed since last iteration
1551  */
1552 static int backward_antic(block_t *bl) {
1553         memop_t *op;
1554         ir_node *block = bl->block;
1555         int     n = get_Block_n_cfg_outs(block);
1556
1557         if (n == 1) {
1558                 ir_node  *succ    = get_Block_cfg_out(block, 0);
1559                 block_t  *succ_bl = get_block_entry(succ);
1560                 int      pred_pos = get_Block_cfgpred_pos(succ, block);
1561                 unsigned end      = env.rbs_size - 1;
1562                 unsigned pos;
1563
1564                 kill_all();
1565
1566                 if (bl->trans_results == NULL) {
1567                         /* allocate the translate cache */
1568                         unsigned size = env.curr_adr_id * sizeof(bl->trans_results[0]);
1569                         bl->trans_results = obstack_alloc(&env.obst, size);
1570                         memset(bl->trans_results, 0, size);
1571                 }
1572
1573                 /* check for partly redundant values */
1574                 for (pos = rbitset_next(succ_bl->anticL_in, 0, 1);
1575                      pos < end;
1576                      pos = rbitset_next(succ_bl->anticL_in, pos + 1, 1)) {
1577                         /*
1578                          * do Phi-translation here: Note that at this point the nodes are
1579                          * not changed, so we can safely cache the results.
1580                          * However: Loads of Load results ARE bad, because we have no way
1581                           to translate them yet ...
1582                          */
1583                         memop_t *op = bl->trans_results[pos];
1584                         if (op == NULL) {
1585                                 /* not yet translated */
1586                                 ir_node *adr, *trans_adr;
1587
1588                                 op  = succ_bl->id_2_memop_antic[pos];
1589                                 adr = op->value.address;
1590
1591                                 trans_adr = phi_translate(adr, succ, pred_pos);
1592                                 if (trans_adr != adr) {
1593                                         /* create a new entry for the translated one */
1594                                         memop_t *new_op;
1595
1596                                         new_op = alloc_memop(NULL);
1597                                         new_op->value.address = trans_adr;
1598                                         new_op->value.id      = register_address(trans_adr);
1599                                         new_op->value.mode    = op->value.mode;
1600                                         new_op->node          = op->node; /* we need the node to decide if Load/Store */
1601                                         new_op->flags         = op->flags;
1602
1603                                         bl->trans_results[pos] = new_op;
1604                                         op = new_op;
1605                                 }
1606                         }
1607                         env.curr_id_2_memop[op->value.id] = op;
1608                         rbitset_set(env.curr_set, op->value.id);
1609                 }
1610         } else if (n > 1) {
1611                 ir_node *succ    = get_Block_cfg_out(block, 0);
1612                 block_t *succ_bl = get_block_entry(succ);
1613                 int i;
1614
1615                 rbitset_copy(env.curr_set, succ_bl->anticL_in, env.rbs_size);
1616                 memcpy(env.curr_id_2_memop, succ_bl->id_2_memop_antic, env.rbs_size * sizeof(env.curr_id_2_memop[0]));
1617
1618                 /* Hmm: probably we want kill merges of Loads ans Stores here */
1619                 for (i = n - 1; i > 0; --i) {
1620                         ir_node *succ    = get_Block_cfg_out(bl->block, i);
1621                         block_t *succ_bl = get_block_entry(succ);
1622
1623                         rbitset_and(env.curr_set, succ_bl->anticL_in, env.rbs_size);
1624                 }
1625         } else {
1626                 /* block ends with a noreturn call */
1627                 kill_all();
1628         }
1629
1630         dump_curr(bl, "AnticL_out");
1631
1632         for (op = bl->memop_backward; op != NULL; op = op->prev) {
1633                 switch (get_irn_opcode(op->node)) {
1634                 case iro_Phi:
1635                         /* meet */
1636                         break;
1637                 case iro_Sync:
1638                         /* join */
1639                         break;
1640                 case iro_Load:
1641                         if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) {
1642                                 /* always add it */
1643                                 add_memop(op);
1644                         }
1645                         break;
1646                 case iro_Store:
1647                         if (! (op->flags & FLAG_KILLED_NODE)) {
1648                                 /* a Store: check which memops must be killed */
1649                                 kill_memops(&op->value);
1650                         }
1651                         break;
1652                 default:
1653                         if (op->flags & FLAG_KILL_ALL)
1654                                 kill_all();
1655                 }
1656         }
1657
1658         memcpy(bl->id_2_memop_antic, env.curr_id_2_memop, env.rbs_size * sizeof(env.curr_id_2_memop[0]));
1659         if (! rbitset_equal(bl->anticL_in, env.curr_set, env.rbs_size)) {
1660                 /* changed */
1661                 rbitset_copy(bl->anticL_in, env.curr_set, env.rbs_size);
1662                 dump_curr(bl, "AnticL_in*");
1663                 return 1;
1664         }
1665         dump_curr(bl, "AnticL_in");
1666         return 0;
1667 }  /* backward_antic */
1668
1669 /**
1670  * Replace a Load memop by a already known value.
1671  *
1672  * @param op  the Load memop
1673  */
1674 static void replace_load(memop_t *op) {
1675         ir_node *load = op->node;
1676         ir_node *def  = skip_Id(op->replace);
1677         ir_node *proj;
1678         ir_mode *mode;
1679
1680         if (def != NULL)
1681                 DB((dbg, LEVEL_1, "Replacing %+F by definition %+F\n", load, is_Proj(def) ? get_Proj_pred(def) : def));
1682         else {
1683                 if (op->flags & FLAG_EXCEPTION) {
1684                         /* bad: this node is unused and executed for exception only */
1685                         DB((dbg, LEVEL_1, "Unused %+F executed for exception only ...\n", load));
1686                         return;
1687                 }
1688                 DB((dbg, LEVEL_1, "Killing unused %+F\n", load));
1689         }
1690
1691         if (op->mem != NULL) {
1692                 /* in rare cases a Load might have NO memory */
1693                 exchange(op->mem, get_Load_mem(load));
1694         }
1695         proj = op->projs[pn_Load_res];
1696         if (proj != NULL) {
1697                 mode = get_irn_mode(proj);
1698                 if (get_irn_mode(def) != mode) {
1699                         /* a hidden cast */
1700                         dbg_info *db    = get_irn_dbg_info(load);
1701                         ir_node  *block = get_nodes_block(proj);
1702                         def = new_rd_Conv(db, block, def, mode);
1703                 }
1704                 exchange(proj, def);
1705         }
1706         proj = op->projs[pn_Load_X_except];
1707         if (proj != NULL) {
1708                 exchange(proj, new_Bad());
1709         }
1710         proj = op->projs[pn_Load_X_regular];
1711         if (proj != NULL) {
1712                 exchange(proj, new_r_Jmp(get_nodes_block(load)));
1713         }
1714 }  /* replace_load */
1715
1716 /**
1717  * Remove a Store memop.
1718  *
1719  * @param op  the Store memop
1720  */
1721 static void remove_store(memop_t *op) {
1722         ir_node *store = op->node;
1723         ir_node *proj;
1724
1725         DB((dbg, LEVEL_1, "Removing %+F\n", store));
1726
1727         if (op->mem != NULL) {
1728                 /* in rare cases a Store might have no memory */
1729                 exchange(op->mem, get_Store_mem(store));
1730         }
1731         proj = op->projs[pn_Store_X_except];
1732         if (proj != NULL) {
1733                 exchange(proj, new_Bad());
1734         }
1735         proj = op->projs[pn_Store_X_regular];
1736         if (proj != NULL) {
1737                 exchange(proj, new_r_Jmp(get_nodes_block(store)));
1738         }
1739 }  /* remove_store */
1740
1741
1742 /**
1743  * Do all necessary replacements for a given block.
1744  *
1745  * @param bl  the block
1746  */
1747 static void do_replacements(block_t *bl) {
1748         memop_t *op;
1749
1750         for (op = bl->memop_forward; op != NULL; op = op->next) {
1751                 if (op->flags & FLAG_KILLED_NODE) {
1752                         switch (get_irn_opcode(op->node)) {
1753                         case iro_Load:
1754                                 replace_load(op);
1755                                 break;
1756                         case iro_Store:
1757                                 remove_store(op);
1758                                 break;
1759                         }
1760                 }
1761         }
1762 }  /* do_replacements */
1763
1764 /**
1765  * Calculate the Avail_out sets for all basic blocks.
1766  */
1767 static void calcAvail(void) {
1768         memop_t  **tmp_memop = env.curr_id_2_memop;
1769         unsigned *tmp_set    = env.curr_set;
1770         block_t  *bl;
1771
1772         /* calculate avail_out */
1773         DB((dbg, LEVEL_2, "Calculate Avail_out\n"));
1774
1775         /* iterate over all blocks in in any order, skip the start block */
1776         for (bl = env.forward->forward_next; bl != NULL; bl = bl->forward_next) {
1777                 forward_avail(bl);
1778         }
1779
1780         /* restore the current sets */
1781         env.curr_id_2_memop = tmp_memop;
1782         env.curr_set        = tmp_set;
1783 }  /* calcAvail */
1784
1785 /**
1786  * Calculate the Antic_in sets for all basic blocks.
1787  */
1788 static void calcAntic(void) {
1789         int i, need_iter;
1790
1791         /* calculate antic_out */
1792         DB((dbg, LEVEL_2, "Calculate Antic_in\n"));
1793         i = 0;
1794         do {
1795                 block_t *bl;
1796
1797                 DB((dbg, LEVEL_2, "Iteration %d:\n=========\n", i));
1798
1799                 need_iter = 0;
1800
1801                 /* over all blocks in reverse post order */
1802                 for (bl = env.backward->backward_next; bl != NULL; bl = bl->backward_next) {
1803                         need_iter |= backward_antic(bl);
1804                 }
1805                 ++i;
1806         } while (need_iter);
1807         DB((dbg, LEVEL_2, "Get anticipated Load set after %d iterations\n", i));
1808 }  /* calcAntic */
1809
1810 /**
1811  * Return the node representing the last memory in a block.
1812  *
1813  * @param bl  the block
1814  */
1815 static ir_node *find_last_memory(block_t *bl) {
1816         for (;;) {
1817                 if (bl->memop_backward != NULL) {
1818                         return bl->memop_backward->mem;
1819                 }
1820                 /* if there is NO memory in this block, go to the dominator */
1821                 bl = get_block_entry(get_Block_idom(bl->block));
1822         }
1823 }  /* find_last_memory */
1824
1825 /**
1826  * Reroute all memory users of old memory
1827  * to a new memory IR-node.
1828  *
1829  * @param omem  the old memory IR-node
1830  * @param nmem  the new memory IR-node
1831  */
1832 static void reroute_all_mem_users(ir_node *omem, ir_node *nmem) {
1833         int i;
1834
1835         for (i = get_irn_n_outs(omem) - 1; i >= 0; --i) {
1836                 int     n_pos;
1837                 ir_node *user = get_irn_out_ex(omem, i, &n_pos);
1838
1839                 set_irn_n(user, n_pos, nmem);
1840         }
1841
1842         /* all edges previously point to omem now point to nmem */
1843         nmem->out = omem->out;
1844 }  /* reroute_all_mem_users */
1845
1846 /**
1847  * Reroute memory users of old memory that are dominated by a given block
1848  * to a new memory IR-node.
1849  *
1850  * @param omem     the old memory IR-node
1851  * @param nmem     the new memory IR-node
1852  * @param pass_bl  the block the memory must pass
1853  */
1854 static void reroute_mem_through(ir_node *omem, ir_node *nmem, ir_node *pass_bl) {
1855         int             i, j, n = get_irn_n_outs(omem);
1856         ir_def_use_edge *edges = NEW_ARR_D(ir_def_use_edge, &env.obst, n + 1);
1857
1858         for (i = j = 0; i < n; ++i) {
1859                 int     n_pos;
1860                 ir_node *user   = get_irn_out_ex(omem, i, &n_pos);
1861                 ir_node *use_bl = get_nodes_block(user);
1862
1863
1864                 if (is_Phi(user)) {
1865                         use_bl = get_Block_cfgpred_block(use_bl, n_pos);
1866                 }
1867                 if (block_dominates(pass_bl, use_bl)) {
1868                         /* found an user that is dominated */
1869                         ++j;
1870                         edges[j].pos = n_pos;
1871                         edges[j].use = user;
1872
1873                         set_irn_n(user, n_pos, nmem);
1874                 }
1875         }
1876
1877         /* Modify the out structure: we create a new out edge array on our
1878            temporary obstack here. This should be no problem, as we invalidate the edges
1879            at the end either. */
1880         /* first entry is used for the length */
1881         edges[0].pos = j;
1882         nmem->out = edges;
1883 }  /* reroute_mem_through */
1884
1885 /**
1886  * insert Loads, making partly redundant Loads fully redundant
1887  */
1888 static int insert_Load(block_t *bl) {
1889         ir_node  *block = bl->block;
1890         int      i, n = get_Block_n_cfgpreds(block);
1891         unsigned end = env.rbs_size - 1;
1892         unsigned pos;
1893
1894         DB((dbg, LEVEL_3, "processing %+F\n", block));
1895
1896         if (n == 0) {
1897                 /* might still happen for an unreachable block (end for instance) */
1898                 return 0;
1899         }
1900
1901         if (n > 1) {
1902                 ir_node **ins;
1903                 int     pos;
1904
1905                 NEW_ARR_A(ir_node *, ins, n);
1906
1907                 rbitset_set_all(env.curr_set, env.rbs_size);
1908
1909                 /* More than one predecessors, calculate the join for all avail_outs ignoring unevaluated
1910                    Blocks. These put in Top anyway. */
1911                 for (i = n - 1; i >= 0; --i) {
1912                         ir_node *pred = skip_Proj(get_Block_cfgpred(block, i));
1913                         ir_node *blk  = get_nodes_block(pred);
1914                         block_t *pred_bl;
1915
1916                         pred_bl = get_block_entry(blk);
1917                         rbitset_and(env.curr_set, pred_bl->avail_out, env.rbs_size);
1918
1919                         if (is_Load(pred) || is_Store(pred)) {
1920                                 /* We reached this block by an exception from a Load or Store:
1921                                  * the memop creating the exception was NOT completed than, kill it
1922                                  */
1923                                 memop_t *exc_op = get_irn_memop(pred);
1924                                 rbitset_clear(env.curr_set, exc_op->value.id);
1925                         }
1926
1927                 }
1928                 /*
1929                  * Ensure that all values are in the map: build Phi's if necessary:
1930                  * Note: the last bit is the sentinel and ALWAYS set, so start with -2.
1931                  */
1932                 for (pos = env.rbs_size - 2; pos >= 0; --pos) {
1933                         if (! rbitset_is_set(env.curr_set, pos))
1934                                 env.curr_id_2_memop[pos] = NULL;
1935                         else {
1936                                 ir_node *pred    = get_Block_cfgpred_block(bl->block, 0);
1937                                 block_t *pred_bl = get_block_entry(pred);
1938                                 int     need_phi = 0;
1939                                 memop_t *first   = NULL;
1940                                 ir_mode *mode    = NULL;
1941
1942                                 for (i = 0; i < n; ++i) {
1943                                         memop_t *mop;
1944
1945                                         pred    = get_Block_cfgpred_block(bl->block, i);
1946                                         pred_bl = get_block_entry(pred);
1947
1948                                         mop = pred_bl->id_2_memop_avail[pos];
1949                                         if (first == NULL) {
1950                                                 first = mop;
1951                                                 ins[0] = first->value.value;
1952                                                 mode = get_irn_mode(ins[0]);
1953
1954                                                 /* no Phi needed so far */
1955                                                 env.curr_id_2_memop[pos] = first;
1956                                         } else {
1957                                                 ins[i] = conv_to(mop->value.value, mode);
1958                                                 if (ins[i] != ins[0]) {
1959                                                         if (ins[i] == NULL) {
1960                                                                 /* conversion failed */
1961                                                                 env.curr_id_2_memop[pos] = NULL;
1962                                                                 rbitset_clear(env.curr_set, pos);
1963                                                                 break;
1964                                                         }
1965                                                         need_phi = 1;
1966                                                 }
1967                                         }
1968                                 }
1969                                 if (need_phi) {
1970                                         /* build a Phi  */
1971                                         ir_node *phi = new_r_Phi(bl->block, n, ins, mode);
1972                                         memop_t *phiop = alloc_memop(phi);
1973
1974                                         phiop->value = first->value;
1975                                         phiop->value.value = phi;
1976
1977                                         /* no need to link it in, as it is a DATA phi */
1978
1979                                         env.curr_id_2_memop[pos] = phiop;
1980
1981                                         DB((dbg, LEVEL_3, "Created new %+F on merging value for address %+F\n", phi, first->value.address));
1982                                 }
1983                         }
1984                 }
1985         } else {
1986                 /* only one predecessor, simply copy the map */
1987                 ir_node *pred    = get_Block_cfgpred_block(bl->block, 0);
1988                 block_t *pred_bl = get_block_entry(pred);
1989
1990                 rbitset_copy(env.curr_set, pred_bl->avail_out, env.rbs_size);
1991
1992                 memcpy(env.curr_id_2_memop, pred_bl->id_2_memop_avail, env.rbs_size * sizeof(bl->id_2_memop_avail[0]));
1993         }
1994
1995         if (n > 1) {
1996                 /* check for partly redundant values */
1997                 for (pos = rbitset_next(bl->anticL_in, 0, 1);
1998                      pos < end;
1999                      pos = rbitset_next(bl->anticL_in, pos + 1, 1)) {
2000                         memop_t *op = bl->id_2_memop_antic[pos];
2001                         int     have_some, all_same;
2002                         ir_node *first;
2003
2004                         if (rbitset_is_set(env.curr_set, pos)) {
2005                                 /* already avail */
2006                                 continue;
2007                         }
2008
2009                         assert(is_Load(op->node));
2010
2011                         DB((dbg, LEVEL_3, "anticipated %+F\n", op->node));
2012
2013                         have_some  = 0;
2014                         all_same   = 1;
2015                         first      = 0;
2016                         for (i = n - 1; i >= 0; --i) {
2017                                 ir_node *pred    = get_Block_cfgpred_block(block, i);
2018                                 block_t *pred_bl = get_block_entry(pred);
2019                                 ir_mode *mode    = op->value.mode;
2020                                 memop_t *e;
2021                                 ir_node *adr;
2022
2023                                 adr = phi_translate(op->value.address, block, i);
2024                                 DB((dbg, LEVEL_3, ".. using address %+F in pred %d\n", adr, i));
2025                                 e   = find_address_avail(pred_bl, register_address(adr), mode);
2026                                 if (e == NULL) {
2027                                         ir_node *ef_block = get_nodes_block(adr);
2028                                         if (! block_dominates(ef_block, pred)) {
2029                                                 /* cannot place a copy here */
2030                                                 have_some = 0;
2031                                                 DB((dbg, LEVEL_3, "%+F cannot be moved into predecessor %+F\n", op->node, pred));
2032                                                 break;
2033                                         }
2034                                         DB((dbg, LEVEL_3, "%+F is not available in predecessor %+F\n", op->node, pred));
2035                                         pred_bl->avail = NULL;
2036                                         all_same       = 0;
2037                                 } else {
2038                                         if (e->value.mode != mode && !can_convert_to(e->value.mode, mode)) {
2039                                                 /* cannot create a Phi due to different modes */
2040                                                 have_some = 0;
2041                                                 break;
2042                                         }
2043                                         pred_bl->avail = e;
2044                                         have_some      = 1;
2045                                         DB((dbg, LEVEL_3, "%+F is available for %+F in predecessor %+F\n", e->node, op->node, pred));
2046                                         if (first == NULL)
2047                                                 first = e->node;
2048                                         else if (first != e->node)
2049                                                 all_same = 0;
2050                                 }
2051                         }
2052                         if (have_some && !all_same) {
2053                                 ir_mode *mode = op->value.mode;
2054                                 ir_node **in, *phi;
2055                                 memop_t *phi_op;
2056
2057                                 NEW_ARR_A(ir_node *, in, n);
2058
2059                                 for (i = n - 1; i >= 0; --i) {
2060                                         ir_node *pred    = get_Block_cfgpred_block(block, i);
2061                                         block_t *pred_bl = get_block_entry(pred);
2062
2063                                         if (pred_bl->avail == NULL) {
2064                                                 /* create a new Load here and make to make it fully redundant */
2065                                                 dbg_info *db       = get_irn_dbg_info(op->node);
2066                                                 ir_node  *last_mem = find_last_memory(pred_bl);
2067                                                 ir_node  *load, *def, *adr;
2068                                                 memop_t  *new_op;
2069
2070                                                 assert(last_mem != NULL);
2071                                                 adr  = phi_translate(op->value.address, block, i);
2072                                                 load = new_rd_Load(db, pred, last_mem, adr, mode, cons_none);
2073                                                 def  = new_r_Proj(pred, load, mode, pn_Load_res);
2074                                                 DB((dbg, LEVEL_1, "Created new %+F in %+F for party redundant %+F\n", load, pred, op->node));
2075
2076                                                 new_op                = alloc_memop(load);
2077                                                 new_op->mem           = new_r_Proj(pred, load, mode_M, pn_Load_M);
2078                                                 new_op->value.address = adr;
2079                                                 new_op->value.id      = op->value.id;
2080                                                 new_op->value.mode    = mode;
2081                                                 new_op->value.value   = def;
2082
2083                                                 new_op->projs[pn_Load_M]   = new_op->mem;
2084                                                 new_op->projs[pn_Load_res] = def;
2085
2086                                                 new_op->prev = pred_bl->memop_backward;
2087                                                 if (pred_bl->memop_backward != NULL)
2088                                                         pred_bl->memop_backward->next = new_op;
2089
2090                                                 pred_bl->memop_backward = new_op;
2091
2092                                                 if (pred_bl->memop_forward == NULL)
2093                                                         pred_bl->memop_forward = new_op;
2094
2095                                                 if (get_nodes_block(last_mem) == pred) {
2096                                                         /* We have add a new last memory op in pred block.
2097                                                            If pred had already a last mem, reroute all memory
2098                                                            users. */
2099                                                         reroute_all_mem_users(last_mem, new_op->mem);
2100                                                 } else {
2101                                                         /* reroute only those memory going through the pre block */
2102                                                         reroute_mem_through(last_mem, new_op->mem, pred);
2103                                                 }
2104
2105                                                 /* we added this load at the end, so it will be avail anyway */
2106                                                 add_memop_avail(pred_bl, new_op);
2107                                                 pred_bl->avail = new_op;
2108                                         }
2109                                         in[i] = conv_to(pred_bl->avail->value.value, mode);
2110                                 }
2111                                 phi = new_r_Phi(block, n, in, mode);
2112                                 DB((dbg, LEVEL_1, "Created new %+F in %+F for now redundant %+F\n", phi, block, op->node));
2113
2114                                 phi_op = clone_memop_phi(op, phi);
2115                                 add_memop(phi_op);
2116                         }
2117                 }
2118         }
2119
2120         /* recalculate avail by gen and kill */
2121         calc_gen_kill_avail(bl);
2122
2123         /* always update the map after gen/kill, as values might have been changed due to RAR/WAR/WAW */
2124         memcpy(bl->id_2_memop_avail, env.curr_id_2_memop, env.rbs_size * sizeof(env.curr_id_2_memop[0]));
2125
2126         if (!rbitset_equal(bl->avail_out, env.curr_set, env.rbs_size)) {
2127                 /* the avail set has changed */
2128                 rbitset_copy(bl->avail_out, env.curr_set, env.rbs_size);
2129                 dump_curr(bl, "Avail_out*");
2130                 return 1;
2131         }
2132         dump_curr(bl, "Avail_out");
2133         return 0;
2134 }  /* insert_Load */
2135
2136 /**
2137  * Insert Loads upwards.
2138  */
2139 static void insert_Loads_upwards(void) {
2140         int i, need_iter;
2141         block_t *bl;
2142
2143         /* recalculate antic_out and insert Loads */
2144         DB((dbg, LEVEL_2, "Inserting Loads\n"));
2145
2146         i = 0;
2147         do {
2148                 DB((dbg, LEVEL_2, "Iteration %d:\n=========\n", i));
2149
2150                 need_iter = 0;
2151
2152                 /* over all blocks in reverse post order, skip the start block */
2153                 for (bl = env.forward->forward_next; bl != NULL; bl = bl->forward_next) {
2154                         need_iter |= insert_Load(bl);
2155                 }
2156                 ++i;
2157         } while (need_iter);
2158
2159         DB((dbg, LEVEL_2, "Finished Load inserting after %d iterations\n", i));
2160 }  /* insert_Loads_upwards */
2161
2162 /**
2163  * Kill unreachable control flow.
2164  *
2165  * @param irg  the graph to operate on
2166  */
2167 static void kill_unreachable_blocks(ir_graph *irg) {
2168         block_t *bl;
2169         ir_node **ins;
2170         int     changed = 0;
2171
2172         NEW_ARR_A(ir_node *, ins, env.max_cfg_preds);
2173
2174         for (bl = env.forward; bl != NULL; bl = bl->forward_next) {
2175                 ir_node *block = bl->block;
2176                 int     i, j, k, n;
2177
2178                 assert(get_Block_mark(block));
2179
2180                 n = get_Block_n_cfgpreds(block);
2181
2182                 for (i = j = 0; i < n; ++i) {
2183                         ir_node *pred = get_Block_cfgpred(block, i);
2184                         ir_node *pred_bl;
2185
2186                         if (is_Bad(pred))
2187                                 continue;
2188
2189                         pred_bl = get_nodes_block(skip_Proj(pred));
2190                         if (! get_Block_mark(pred_bl))
2191                                 continue;
2192
2193                         ins[j++] = pred;
2194                 }
2195                 if (j != n) {
2196                         ir_node *phi, *next;
2197
2198                         /* some unreachable blocks detected */
2199                         changed = 1;
2200
2201                         DB((dbg, LEVEL_1, "Killing dead block predecessors on %+F\n", block));
2202
2203                         set_irn_in(block, j, ins);
2204
2205                         /* shorten all Phi nodes */
2206                         for (phi = get_Block_phis(block); phi != NULL; phi = next) {
2207                                 next = get_Phi_next(phi);
2208
2209                                 for (i = k = 0; i < n; ++i) {
2210                                         ir_node *pred = get_Block_cfgpred_block(block, i);
2211
2212                                         if (is_Bad(pred))
2213                                                 continue;
2214
2215                                         if (! get_Block_mark(pred))
2216                                                 continue;
2217
2218                                         ins[k++] = get_Phi_pred(phi, i);
2219                                 }
2220                                 if (k == 1)
2221                                         exchange(phi, ins[0]);
2222                                 else
2223                                         set_irn_in(phi, k, ins);
2224                         }
2225                 }
2226
2227         }
2228
2229         if (changed) {
2230                 /* kick keep alives */
2231                 ir_node *end = get_irg_end(irg);
2232                 int     i, j, n = get_End_n_keepalives(end);
2233
2234                 NEW_ARR_A(ir_node *, ins, n);
2235
2236                 for (i = j = 0; i < n; ++i) {
2237                         ir_node *ka = get_End_keepalive(end, i);
2238                         ir_node *ka_bl;
2239
2240                         if (is_Bad(ka))
2241                                 continue;
2242                         if (is_Block(ka))
2243                                 ka_bl = ka;
2244                         else
2245                                 ka_bl = get_nodes_block(skip_Proj(ka));
2246                         if (get_Block_mark(ka_bl))
2247                                 ins[j++] = ka;
2248                 }
2249                 if (j != n)
2250                         set_End_keepalives(end, j, ins);
2251
2252                 free_irg_outs(irg);
2253
2254                 /* this transformation do NOT invalidate the dominance */
2255         }
2256 }  /* kill_unreachable_blocks */
2257
2258 int opt_ldst(ir_graph *irg) {
2259         block_t  *bl;
2260         ir_graph *rem = current_ir_graph;
2261
2262         current_ir_graph = irg;
2263
2264         FIRM_DBG_REGISTER(dbg, "firm.opt.ldst");
2265 //      firm_dbg_set_mask(dbg, -1);
2266
2267         DB((dbg, LEVEL_1, "\nDoing Load/Store optimization on %+F\n", irg));
2268
2269         /* we need landing pads */
2270         remove_critical_cf_edges(irg);
2271
2272 //      dump_ir_block_graph(irg, "-XXX");
2273
2274         if (get_opt_alias_analysis()) {
2275                 assure_irg_entity_usage_computed(irg);
2276                 assure_irp_globals_entity_usage_computed();
2277         }
2278
2279         obstack_init(&env.obst);
2280         ir_nodemap_init(&env.adr_map);
2281
2282         env.forward       = NULL;
2283         env.backward      = NULL;
2284         env.curr_adr_id   = 0;
2285         env.n_mem_ops     = 0;
2286         env.max_cfg_preds = 0;
2287         env.changed       = 0;
2288         env.start_bl      = get_irg_start_block(irg);
2289         env.end_bl        = get_irg_end_block(irg);
2290 #ifdef DEBUG_libfirm
2291         env.id_2_address  = NEW_ARR_F(ir_node *, 0);
2292 #endif
2293
2294         assure_irg_outs(irg);
2295
2296         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_BLOCK_MARK);
2297
2298         /* first step: allocate block entries. Note that some blocks might be
2299            unreachable here. Using the normal walk ensures that ALL blocks are initialized. */
2300         irg_walk_graph(irg, prepare_blocks, link_phis, NULL);
2301
2302         /* produce an inverse post-order list for the CFG: this links only reachable
2303            blocks */
2304         irg_out_block_walk(get_irg_start_block(irg), NULL, inverse_post_order, NULL);
2305
2306         if (! get_Block_mark(env.end_bl)) {
2307                 /*
2308                  * The end block is NOT reachable due to endless loops
2309                  * or no_return calls.
2310                  * Place the end block last.
2311                  * env.backward points to the last block in the list for this purpose.
2312                  */
2313                 env.backward->forward_next = get_block_entry(env.end_bl);
2314
2315                 set_Block_mark(env.end_bl, 1);
2316         }
2317
2318         /* KILL unreachable blocks: these disturb the data flow analysis */
2319         kill_unreachable_blocks(irg);
2320
2321         assure_doms(irg);
2322
2323         /* second step: find and sort all memory ops */
2324         walk_memory_irg(irg, collect_memops, NULL, NULL);
2325
2326 #ifdef DEBUG_libfirm
2327         /* check that the backward map is correct */
2328         assert((unsigned)ARR_LEN(env.id_2_address) == env.curr_adr_id);
2329 #endif
2330
2331         if (env.n_mem_ops == 0) {
2332                 /* no memory ops */
2333                 goto end;
2334         }
2335
2336         /* create the backward links. */
2337         env.backward = NULL;
2338         irg_block_walk_graph(irg, NULL, collect_backward, NULL);
2339
2340         /* link the end block in */
2341         bl = get_block_entry(env.end_bl);
2342         bl->backward_next = env.backward;
2343         env.backward      = bl;
2344
2345         /* check that we really start with the start / end block */
2346         assert(env.forward->block  == env.start_bl);
2347         assert(env.backward->block == env.end_bl);
2348
2349         /* create address sets: for now, only the existing addresses are allowed plus one
2350            needed for the sentinel */
2351         env.rbs_size = env.curr_adr_id + 1;
2352
2353         /* create the current set */
2354         env.curr_set = rbitset_obstack_alloc(&env.obst, env.rbs_size);
2355         rbitset_set(env.curr_set, env.rbs_size - 1);
2356         env.curr_id_2_memop = NEW_ARR_D(memop_t *, &env.obst, env.rbs_size);
2357         memset(env.curr_id_2_memop, 0, env.rbs_size * sizeof(env.curr_id_2_memop[0]));
2358
2359         for (bl = env.forward; bl != NULL; bl = bl->forward_next) {
2360                 /* set sentinel bits */
2361                 bl->avail_out  = rbitset_obstack_alloc(&env.obst, env.rbs_size);
2362                 rbitset_set(bl->avail_out, env.rbs_size - 1);
2363
2364                 bl->id_2_memop_avail = NEW_ARR_D(memop_t *, &env.obst, env.rbs_size);
2365                 memset(bl->id_2_memop_avail, 0, env.rbs_size * sizeof(bl->id_2_memop_avail[0]));
2366
2367                 bl->anticL_in  = rbitset_obstack_alloc(&env.obst, env.rbs_size);
2368                 rbitset_set(bl->anticL_in, env.rbs_size - 1);
2369
2370                 bl->id_2_memop_antic = NEW_ARR_D(memop_t *, &env.obst, env.rbs_size);
2371                 memset(bl->id_2_memop_antic, 0, env.rbs_size * sizeof(bl->id_2_memop_antic[0]));
2372         }
2373
2374 //      dump_block_list(&env);
2375         (void) dump_block_list;
2376
2377         calcAvail();
2378         calcAntic();
2379
2380         insert_Loads_upwards();
2381
2382         if (env.changed) {
2383                 /* over all blocks in reverse post order */
2384                 for (bl = env.forward; bl != NULL; bl = bl->forward_next) {
2385                         do_replacements(bl);
2386                 }
2387
2388                 /* not only invalidate but free them. We might allocate new out arrays
2389                    on our obstack which will be deleted yet. */
2390                 free_irg_outs(irg);
2391                 set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
2392         }
2393 end:
2394
2395         ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_BLOCK_MARK);
2396         ir_nodemap_destroy(&env.adr_map);
2397         obstack_free(&env.obst, NULL);
2398
2399 //      dump_ir_block_graph(irg, "-YYY");
2400
2401 #ifdef DEBUG_libfirm
2402         DEL_ARR_F(env.id_2_address);
2403 #endif
2404
2405         current_ir_graph = rem;
2406         return env.changed != 0;
2407 }  /* opt_ldst */