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

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