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