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

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