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