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