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

   1 /*
   2  * Copyright (C) 1995-2008 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  * @version $Id$
  26  */
  27 #include "config.h"
  28
  29 #include "irnode_t.h"
  30 #include "irflag_t.h"
  31 #include "array_t.h"
  32 #include "ircons.h"
  33 #include "irdom.h"
  34 #include "irgmod.h"
  35 #include "irgwalk.h"
  36 #include "irouts.h"
  37 #include "irgraph.h"
  38 #include "irgopt.h"
  39 #include "irnodemap.h"
  40 #include "raw_bitset.h"
  41 #include "debug.h"
  42 #include "error.h"
  43
  44 /**
  45  * Mapping an address to an densed ID.
  46  */
  47 typedef struct address_entry_t {
  48         unsigned id;          /**< The ID */
  49 } address_entry;
  50
  51 /**
  52  * Memop-flags.
  53  */
  54 enum memop_flags {
  55         FLAG_KILL_LOADS  =  1, /**< KILL all Loads */
  56         FLAG_KILL_STORES =  2, /**< KILL all Stores */
  57         FLAG_KILLED_NODE =  4, /**< this node was killed */
  58         FLAG_EXCEPTION   =  8, /**< this node has exception flow */
  59         FLAG_IGNORE      = 16, /**< ignore this node (volatile or other) */
  60         /** this memop KILLS all addresses */
  61         FLAG_KILL_ALL    = FLAG_KILL_LOADS|FLAG_KILL_STORES
  62 };
  63
  64 /**
  65  * A value: This represents a value stored at a given address in
  66  * memory. Do not confuse with values from value numbering.
  67  */
  68 typedef struct value_t value_t;
  69 struct value_t {
  70         ir_node  *address;    /**< the address of this value */
  71         ir_node  *value;      /**< the value itself */
  72         ir_mode  *mode;       /**< the mode of the value */
  73         unsigned id;          /**< address id */
  74 };
  75
  76 /**
  77  * A memop describes an memory-related operation.
  78  * These are Loads/Store and all other ops that might modify
  79  * memory (Calls, CopyB) or causing exceptions.
  80  */
  81 typedef struct memop_t memop_t;
  82 struct memop_t {
  83         value_t  value;      /**< the value of this memop: only defined for Load/Store */
  84         ir_node  *node;      /**< the memory op itself */
  85         ir_node  *mem;       /**< the memory FROM this node */
  86         ir_node  *replace;   /**< the replacement node if this memop is replaced */
  87         memop_t  *next;      /**< links to the next memory op in the block in forward order. */
  88         memop_t  *prev;      /**< links to the previous memory op in the block in forward order. */
  89         unsigned flags;      /**< memop flags */
  90 };
  91
  92 /**
  93  * Additional data for every basic block.
  94  */
  95 typedef struct block_t block_t;
  96 struct block_t {
  97         memop_t  *memop_forward;     /**< topologically sorted list of memory ops in this block */
  98         memop_t  *memop_backward;    /**< last memop in the list */
  99         unsigned *avail_out;         /**< out-set of available addresses */
 100         memop_t  **id_2_memop_avail; /**< maps avail address ids to memops */
 101         unsigned *anticL_in;         /**< in-set of anticipated Load addresses */
 102         memop_t  **id_2_memop;       /**< maps address ids to memops */
 103         ir_node  *block;             /**< the associated block */
 104         block_t  *forward_next;      /**< next block entry for forward iteration */
 105         block_t  *backward_next;     /**< next block entry for backward iteration */
 106         memop_t  *avail;             /**< used locally for the avail map */
 107 };
 108
 109 #define get_block_entry(block) ((block_t *)get_irn_link(block))
 110
 111 /**
 112  * Metadata for this pass.
 113  */
 114 typedef struct ldst_env_t {
 115         struct obstack  obst;         /**< obstack for temporary data */
 116         ir_nodemap_t    adr_map;      /**< Map addresses to */
 117         block_t         *forward;     /**< Inverse post-order list of all blocks Start->End */
 118         block_t         *backward;    /**< Inverse post-order list of all blocks End->Start */
 119         ir_node         *start_bl;    /**< start block of the current graph */
 120         unsigned        *curr_set;    /**< current set of addresses */
 121         unsigned        curr_adr_id;  /**< number for address mapping */
 122         unsigned        n_mem_ops;    /**< number of memory operations (Loads/Stores) */
 123         unsigned        rbs_size;     /**< size of all bitsets in bytes */
 124         int             changed;      /**< Flags for changed graph state */
 125 } ldst_env;
 126
 127 #ifdef DEBUG_libfirm
 128
 129 static firm_dbg_module_t *dbg;
 130
 131 /* the one and only environment */
 132 static ldst_env env;
 133
 134 /**
 135  * Dumps the block list.
 136  *
 137  * @param ldst environment
 138  */
 139 static void dump_block_list(ldst_env *env) {
 140         block_t *entry;
 141         memop_t *op;
 142         int     i;
 143
 144         for (entry = env->forward; entry != NULL; entry = entry->forward_next) {
 145                 DB((dbg, LEVEL_2, "%+F {", entry->block));
 146
 147                 i = 0;
 148                 for (op = entry->memop_forward; op != NULL; op = op->next) {
 149                         if (i == 0) {
 150                                 DB((dbg, LEVEL_2, "\n\t"));
 151                         }                       DB((dbg, LEVEL_2, "%+F", op->node));
 152                         if ((op->flags & FLAG_KILL_ALL) == FLAG_KILL_ALL)
 153                                 DB((dbg, LEVEL_2, "X"));
 154                         else if (op->flags & FLAG_KILL_LOADS)
 155                                 DB((dbg, LEVEL_2, "L"));
 156                         else if (op->flags & FLAG_KILL_STORES)
 157                                 DB((dbg, LEVEL_2, "S"));
 158                         DB((dbg, LEVEL_2, ", "));
 159
 160                         i = (i + 1) & 3;
 161                 }
 162                 DB((dbg, LEVEL_2, "\n}\n\n"));
 163         }
 164 }
 165
 166 /**
 167  * Dumps the current set.
 168  *
 169  * @param bl   current block
 170  * @param s    name of the set
 171  */
 172 static void dump_curr(block_t *bl, const char *s) {
 173         unsigned pos = 0;
 174         unsigned end = env.n_mem_ops * 2 - 1;
 175         int      i;
 176
 177         DB((dbg, LEVEL_2, "%s[%+F] = {", s, bl->block));
 178         i = 0;
 179         for (pos = rbitset_next(env.curr_set, pos, 1); pos != end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
 180                 memop_t *op = bl->id_2_memop[pos];
 181
 182                 if (i == 0) {
 183                         DB((dbg, LEVEL_2, "\n\t"));
 184                 }
 185                 DB((dbg, LEVEL_2, "<%+F, %+F>, ", op->value.address, op->value.value));
 186                 i = (i + 1) & 3;
 187         }
 188         DB((dbg, LEVEL_2, "\n}\n"));
 189 }
 190
 191 #else
 192 #define dump_block_list()
 193 #define dump_curr(bl, s)
 194 #endif /* DEBUG_libfirm */
 195
 196 /**
 197  * Walk over the memory edges from definition to users.
 198  *
 199  * @param irn   start node
 200  * @param pre   pre walker function
 201  * @param post  post walker function
 202  * @param ctx   context parameter for the walker functions
 203  */
 204 static void walk_memory(ir_node *irn, irg_walk_func *pre, irg_walk_func *post, void *ctx) {
 205         int     i;
 206         ir_mode *mode;
 207
 208         mark_irn_visited(irn);
 209
 210         if (pre)
 211                 pre(irn, ctx);
 212
 213         mode = get_irn_mode(irn);
 214         if (mode == mode_M) {
 215                 /* every successor uses memory */
 216                 for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) {
 217                         ir_node *succ = get_irn_out(irn, i);
 218
 219                         if (! irn_visited(succ))
 220                                 walk_memory(succ, pre, post, ctx);
 221                 }
 222         } else if (mode == mode_T) {
 223                 /* only some Proj's uses memory */
 224                 for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) {
 225                         ir_node *proj = get_irn_out(irn, i);
 226
 227                         if (get_irn_mode(proj) == mode_M && ! irn_visited(proj))
 228                                 walk_memory(proj, pre, post, ctx);
 229                 }
 230         }
 231         if (post)
 232                 post(irn, ctx);
 233 }
 234
 235 /**
 236  * Walks over all memory nodes of a graph.
 237  *
 238  * @param irg   a graph
 239  * @param pre   pre walker function
 240  * @param post  post walker function
 241  * @param ctx   context parameter for the walker functions
 242  */
 243 static void walk_memory_irg(ir_graph *irg, irg_walk_func pre, irg_walk_func post, void *ctx) {
 244         inc_irg_visited(irg);
 245
 246         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 247
 248         /*
 249          * there are two possible sources for memory: initial_mem and nomem
 250          * we ignore nomem as this should NOT change the memory
 251          */
 252         walk_memory(get_irg_initial_mem(irg), pre, post, ctx);
 253
 254         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 255 }
 256
 257 /**
 258  * Block walker: allocate an block entry for every block.
 259  */
 260 static void prepare_blocks(ir_node *block, void *ctx) {
 261         block_t *entry = obstack_alloc(&env.obst, sizeof(*entry));
 262
 263         (void) ctx;
 264
 265         entry->memop_forward    = NULL;
 266         entry->memop_backward   = NULL;
 267         entry->avail_out        = NULL;
 268         entry->id_2_memop_avail = NULL;
 269         entry->anticL_in        = NULL;
 270         entry->id_2_memop       = NULL;
 271         entry->block            = block;
 272         entry->forward_next     = env.forward;
 273         entry->backward_next    = NULL;
 274         entry->avail            = NULL;
 275         set_irn_link(block, entry);
 276
 277         /* create the list in inverse order */
 278         env.forward = entry;
 279 }
 280
 281 /**
 282  * Block walker: create backward links for the memops of a block.
 283  */
 284 static void collect_backward(ir_node *block, void *ctx) {
 285         block_t *entry = get_block_entry(block);
 286         memop_t *last, *op;
 287
 288         (void) ctx;
 289         entry->backward_next = env.backward;
 290
 291         /* create the list in inverse order */
 292         env.backward = entry;
 293
 294         /* create backward links for all memory ops */
 295         last = NULL;
 296         for (op = entry->memop_forward; op != NULL; op = op->next) {
 297                 op->prev = last;
 298                 last     = op;
 299         }
 300         entry->memop_backward = last;
 301 }
 302
 303 /**
 304  * Allocate a memop.
 305  *
 306  * @param irn  the IR-node representing the memop
 307  */
 308 static memop_t *alloc_memop(ir_node *irn) {
 309         memop_t *m = obstack_alloc(&env.obst, sizeof(*m));
 310
 311         m->value.address = NULL;
 312         m->value.value   = NULL;
 313         m->value.mode    = NULL;
 314
 315         m->node          = irn;
 316         m->replace       = NULL;
 317         m->next          = NULL;
 318         m->flags         = 0;
 319
 320         return m;
 321 }
 322
 323 /**
 324  * Register an address and allocate an ID for it.
 325  *
 326  * @param adr  the IR-node representing the address
 327  */
 328 static unsigned register_address(ir_node *adr) {
 329         address_entry *entry = ir_nodemap_get(&env.adr_map, adr);
 330
 331         if (entry == NULL) {
 332                 /* new address */
 333                 entry = obstack_alloc(&env.obst, sizeof(*entry));
 334
 335                 entry->id = env.curr_adr_id++;
 336                 ir_nodemap_insert(&env.adr_map, adr, entry);
 337         }
 338         return entry->id;
 339 }
 340
 341 /**
 342  * Return the memory properties of a call node.
 343  *
 344  * @param call  the call node
 345  *
 346  * return a bitset of mtp_property_const and mtp_property_pure
 347  */
 348 static unsigned get_Call_memory_properties(ir_node *call) {
 349         ir_type *call_tp = get_Call_type(call);
 350         unsigned prop = get_method_additional_properties(call_tp);
 351
 352         /* check first the call type */
 353         if ((prop & (mtp_property_const|mtp_property_pure)) == 0) {
 354                 /* try the called entity */
 355                 ir_node *ptr = get_Call_ptr(call);
 356
 357                 if (is_Global(ptr)) {
 358                         ir_entity *ent = get_Global_entity(ptr);
 359
 360                         prop = get_entity_additional_properties(ent);
 361                 }
 362         }
 363         return prop & (mtp_property_const|mtp_property_pure);
 364 }
 365
 366 /**
 367  * Update a memop for a Load.
 368  *
 369  * @param m  the memop
 370  */
 371 static void update_Load_memop(memop_t *m) {
 372         int     i;
 373         ir_node *load = m->node;
 374         ir_node *adr  = get_Load_ptr(load);
 375
 376         if (get_Load_volatility(load) == volatility_is_volatile)
 377                 m->flags |= FLAG_IGNORE;
 378
 379         m->value.address = adr;
 380
 381         for (i = get_irn_n_outs(load) - 1; i >= 0; --i) {
 382                 ir_node *proj = get_irn_out(load, i);
 383
 384                 switch (get_Proj_proj(proj)) {
 385                 case pn_Load_res:
 386                         m->value.value = proj;
 387                         m->value.mode  = get_irn_mode(proj);
 388                         break;
 389                 case pn_Load_X_except:
 390                         m->flags |= FLAG_EXCEPTION;
 391                         break;
 392                 case pn_Load_M:
 393                         m->mem = proj;
 394                         break;
 395                 }
 396         }
 397
 398         if (m->value.value != NULL && !(m->flags & FLAG_IGNORE)) {
 399                 /* only create an address if this node is NOT killed immediately or ignored */
 400                 m->value.id = register_address(adr);
 401                 ++env.n_mem_ops;
 402         } else {
 403                 /* no user, KILL it */
 404                 m->flags |= FLAG_KILLED_NODE;
 405         }
 406 }
 407
 408 /**
 409  * Update a memop for a Store.
 410  *
 411  * @param m  the memop
 412  */
 413 static void update_Store_memop(memop_t *m) {
 414         int     i;
 415         ir_node *store = m->node;
 416         ir_node *adr   = get_Store_ptr(store);
 417
 418         if (get_Store_volatility(store) == volatility_is_volatile) {
 419                 m->flags |= FLAG_IGNORE;
 420         } else {
 421                 /* only create an address if this node is NOT ignored */
 422                 m->value.id = register_address(adr);
 423                 ++env.n_mem_ops;
 424         }
 425
 426         m->value.address = adr;
 427
 428         for (i = get_irn_n_outs(store) - 1; i >= 0; --i) {
 429                 ir_node *proj = get_irn_out(store, i);
 430
 431                 switch (get_Proj_proj(proj)) {
 432                 case pn_Store_X_except:
 433                         m->flags |= FLAG_EXCEPTION;
 434                         break;
 435                 case pn_Store_M:
 436                         m->mem = proj;
 437                         break;
 438                 }
 439         }
 440         m->value.value = get_Store_value(store);
 441         m->value.mode  = get_irn_mode(m->value.value);
 442 }
 443
 444 /**
 445  * Update a memop for a Call.
 446  *
 447  * @param m  the memop
 448  */
 449 static void update_Call_memop(memop_t *m) {
 450         ir_node  *call = m->node;
 451         unsigned prop  = get_Call_memory_properties(call);
 452         int      i;
 453
 454         if (prop & mtp_property_const) {
 455                 /* A constant call did NOT use memory at all, we
 456                    can kick it from the list. */
 457         } else if (prop & mtp_property_pure) {
 458                 /* pure calls READ memory */
 459                 m->flags = FLAG_KILL_STORES;
 460         } else
 461                 m->flags = FLAG_KILL_ALL;
 462
 463         for (i = get_irn_n_outs(call) - 1; i >= 0; --i) {
 464                 ir_node *proj = get_irn_out(call, i);
 465
 466                 switch (get_Proj_proj(proj)) {
 467                 case pn_Call_X_except:
 468                         m->flags |= FLAG_EXCEPTION;
 469                         break;
 470                 case pn_Call_M_regular:
 471                         m->mem = proj;
 472                         break;
 473                 }
 474         }
 475 }
 476
 477 /**
 478  * Update a memop for a Div/Mod/Quot/DivMod.
 479  *
 480  * @param m  the memop
 481  */
 482 static void update_DivOp_memop(memop_t *m) {
 483         ir_node *div = m->node;
 484         int     i;
 485
 486         for (i = get_irn_n_outs(div) - 1; i >= 0; --i) {
 487                 ir_node *proj = get_irn_out(div, i);
 488
 489                 switch (get_Proj_proj(proj)) {
 490                 case pn_Generic_X_except:
 491                         m->flags |= FLAG_EXCEPTION;
 492                         break;
 493                 case pn_Generic_M_regular:
 494                         m->mem = proj;
 495                         break;
 496                 }
 497         }
 498 }
 499
 500 /**
 501  * Memory walker: collect all memory ops and build topological lists.
 502  */
 503 static void collect_memops(ir_node *irn, void *ctx) {
 504         memop_t  *op;
 505         ir_node  *block;
 506         block_t  *entry;
 507
 508         (void) ctx;
 509         if (is_Proj(irn)) {
 510                 /* we can safely ignore ProjM's except the initial memory */
 511                 if (irn != get_irg_initial_mem(current_ir_graph))
 512                         return;
 513         }
 514
 515         op    = alloc_memop(irn);
 516         block = get_nodes_block(irn);
 517         entry = get_block_entry(block);
 518
 519         if (is_Phi(irn)) {
 520                 /* Phis must be always placed first */
 521                 op->next = entry->memop_forward;
 522                 entry->memop_forward = op;
 523                 if (entry->memop_backward == NULL)
 524                         entry->memop_backward = op;
 525         } else {
 526                 switch (get_irn_opcode(irn)) {
 527                 case iro_Load:
 528                         update_Load_memop(op);
 529                         break;
 530                 case iro_Store:
 531                         update_Store_memop(op);
 532                         break;
 533                 case iro_Call:
 534                         update_Call_memop(op);
 535                         break;
 536                 case iro_Sync:
 537                 case iro_Pin:
 538                         op->mem = irn;
 539                         break;
 540                 case iro_Proj:
 541                         /* initial memory */
 542                         op->mem = irn;
 543                         break;
 544                 case iro_Return:
 545                 case iro_End:
 546                         /* we can those to find the memory edge */
 547                         break;
 548                 case iro_Div:
 549                 case iro_DivMod:
 550                 case iro_Quot:
 551                 case iro_Mod:
 552                         update_DivOp_memop(op);
 553                         break;
 554
 555                 case iro_Builtin:
 556                         /* TODO: handle some builtins */
 557                 default:
 558                         /* unsupported operation */
 559                         op->flags = FLAG_KILL_ALL;
 560                 }
 561
 562
 563                 /* all other should be placed last */
 564                 if (entry->memop_backward == NULL) {
 565                         entry->memop_forward = entry->memop_backward = op;
 566                 } else {
 567                         entry->memop_backward->next = op;
 568                         entry->memop_backward       = op;
 569                 }
 570         }
 571 }
 572
 573 /**
 574  * Find an address in the current set.
 575  *
 576  * @param bl     the block
 577  * @param value  the value to be searched for
 578  */
 579 static memop_t *find_address(const block_t *bl, const value_t *value) {
 580         if (rbitset_is_set(env.curr_set, value->id)) {
 581                 memop_t *res = bl->id_2_memop[value->id];
 582
 583                 if (res->value.mode == value->mode)
 584                         return res;
 585                 /* allow hidden casts */
 586                 if (get_mode_arithmetic(res->value.mode) == irma_twos_complement &&
 587                     get_mode_arithmetic(value->mode) == irma_twos_complement &&
 588                     get_mode_size_bits(res->value.mode) == get_mode_size_bits(value->mode))
 589                         return res;
 590         }
 591         return NULL;
 592 }
 593
 594 /**
 595  * Find an address in the avail_out set.
 596  *
 597  * @param bl     the block
 598  * @param value  the value to be searched for
 599  */
 600 static memop_t *find_address_avail(const block_t *bl, const value_t *value) {
 601         if (rbitset_is_set(bl->avail_out, value->id)) {
 602                 memop_t *res = bl->id_2_memop_avail[value->id];
 603
 604                 if (res->value.mode == value->mode)
 605                         return res;
 606                 /* allow hidden casts */
 607                 if (get_mode_arithmetic(res->value.mode) == irma_twos_complement &&
 608                     get_mode_arithmetic(value->mode) == irma_twos_complement &&
 609                     get_mode_size_bits(res->value.mode) == get_mode_size_bits(value->mode))
 610                         return res;
 611         }
 612         return NULL;
 613 }
 614
 615 /**
 616  * Kill all Loads from the current set.
 617  *
 618  * @param bl  the current block
 619  */
 620 static void kill_all_loads(block_t *bl) {
 621         unsigned pos = 0;
 622         unsigned end = env.n_mem_ops * 2 - 1;
 623
 624         for (pos = rbitset_next(env.curr_set, pos, 1); pos != end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
 625                 memop_t *op = bl->id_2_memop[pos];
 626
 627                 if (! is_Store(op->node))
 628                         rbitset_clear(env.curr_set, pos);
 629         }
 630 }
 631
 632 /**
 633  * Kill all Stores from the current set.
 634  *
 635  * @param bl  the current block
 636  */
 637 static void kill_all_stores(block_t *bl) {
 638         unsigned pos = 0;
 639         unsigned end = env.n_mem_ops * 2 - 1;
 640
 641         for (pos = rbitset_next(env.curr_set, pos, 1); pos != end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
 642                 memop_t *op = bl->id_2_memop[pos];
 643
 644                 if (is_Store(op->node))
 645                         rbitset_clear(env.curr_set, pos);
 646         }
 647 }
 648
 649 /**
 650  * Kill all addresses from the current set.
 651  */
 652 static void kill_all(void) {
 653         rbitset_clear_all(env.curr_set, env.rbs_size);
 654
 655         /* set sentinel */
 656         rbitset_set(env.curr_set, env.rbs_size - 1);
 657 }
 658
 659
 660 /**
 661  * Kill Stores that are not alias free due to a Load value from the current set.
 662  *
 663  * @param bl     the block
 664  * @param value  the Load value
 665  */
 666 static void kill_stores(block_t *bl, const value_t *value) {
 667         unsigned pos = 0;
 668         unsigned end = env.n_mem_ops * 2 - 1;
 669
 670         for (pos = rbitset_next(env.curr_set, pos, 1); pos != end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
 671                 memop_t *op = bl->id_2_memop[pos];
 672
 673                 if (is_Store(op->node)) {
 674                         if (ir_no_alias != get_alias_relation(current_ir_graph, value->address, value->mode,
 675                                                               op->value.address, op->value.mode)) {
 676                                 rbitset_clear(env.curr_set, pos);
 677                                 bl->id_2_memop[pos] = NULL;
 678                         }
 679                 }
 680         }
 681 }
 682
 683 /**
 684  * Kill memops that are not alias free due to a Store value from the current set.
 685  *
 686  * @param bl     the block
 687  * @param value  the Store value
 688  */
 689 static void kill_memops(block_t *bl, const value_t *value) {
 690         unsigned pos = 0;
 691         unsigned end = env.n_mem_ops * 2 - 1;
 692
 693         for (pos = rbitset_next(env.curr_set, pos, 1); pos != end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
 694                 memop_t *op = bl->id_2_memop[pos];
 695
 696                 if (ir_no_alias != get_alias_relation(current_ir_graph, value->address, value->mode,
 697                                                           op->value.address, op->value.mode)) {
 698                         rbitset_clear(env.curr_set, pos);
 699                         bl->id_2_memop[pos] = NULL;
 700                 }
 701         }
 702 }
 703
 704 /**
 705  * Add the value of a memop to the current set.
 706  *
 707  * @param bl  the block
 708  * @param op  the memory op
 709  */
 710 static void add_memop(block_t *bl, memop_t *op) {
 711         rbitset_set(env.curr_set, op->value.id);
 712         bl->id_2_memop[op->value.id] = op;
 713 }
 714
 715 /**
 716  * Add the value of a memop to the avail_out set.
 717  *
 718  * @param bl  the block
 719  * @param op  the memory op
 720  */
 721 static void add_memop_avail(block_t *bl, memop_t *op) {
 722         rbitset_set(bl->avail_out, op->value.id);
 723         bl->id_2_memop_avail[op->value.id] = op;
 724 }
 725
 726 /**
 727  * find a definition for a value in the given block.
 728  *
 729  * @param block  the block
 730  * @param value  the value
 731  *
 732  * @return the definition
 733  */
 734 static ir_node *find_definition(ir_node *block, const value_t *value) {
 735         ir_node *def_bl = get_nodes_block(value->value);
 736         ir_node **in, *phi;
 737         int     i, n;
 738         memop_t *mop;
 739
 740         if (block_dominates(def_bl, block))
 741                 return value->value;
 742
 743         /* no: we need a new Phi */
 744         n = get_Block_n_cfgpreds(block);
 745
 746         while (n == 1) {
 747                 block = get_Block_cfgpred_block(block, 0);
 748                 n     = get_Block_n_cfgpreds(block);
 749                 mop   = find_address(get_block_entry(block), value);
 750
 751                 assert(mop != NULL);
 752                 value = &mop->value;
 753         }
 754
 755         NEW_ARR_A(ir_node *, in, n);
 756         for (i = n - 1; i >= 0; --i) {
 757                 ir_node *pred_bl = get_Block_cfgpred_block(block, i);
 758                 mop   = find_address(get_block_entry(pred_bl), value);
 759                 in[i] = find_definition(pred_bl, &mop->value);
 760         }
 761
 762         phi = new_r_Phi(current_ir_graph, block, n, in, value->mode);
 763         DB((dbg, LEVEL_2, "Created new Phi %+F for value %+F in block %+F\n", phi, value->value, block));
 764         return phi;
 765 }
 766
 767 /**
 768  * Mark a Load memop to be replace by a definition
 769  *
 770  * @param op  the Load memop
 771  */
 772 static void mark_replace_load(memop_t *op, ir_node *def) {
 773         op->replace = def;
 774         op->flags |= FLAG_KILLED_NODE;
 775         env.changed = 1;
 776 }
 777
 778 /**
 779  * Mark a Store memop to be removed.
 780  *
 781  * @param op  the Store memop
 782  */
 783 static void mark_remove_store(memop_t *op) {
 784         op->flags |= FLAG_KILLED_NODE;
 785         env.changed = 1;
 786 }
 787
 788 #define BYTE_SIZE(x)  (((x) + 7) >> 3)
 789
 790 /**
 791  * Do forward dataflow analysis on a given block to calculate the avail_out set.
 792  *
 793  * @param bl  the block
 794  *
 795  * @return non-zero if the set has changed since last iteration
 796  */
 797 static int forward_avail(block_t *bl) {
 798         memop_t *op;
 799         int     n;
 800         ir_node *def;
 801         ir_node *pred    = get_Block_cfgpred_block(bl->block, 0);
 802         block_t *pred_bl = get_block_entry(pred);
 803
 804         memcpy(env.curr_set, pred_bl->avail_out, BYTE_SIZE(env.rbs_size));
 805
 806         n = get_Block_n_cfgpreds(bl->block);
 807         if (n > 1) {
 808                 int i, pos;
 809
 810                 /* more than one predecessors, calculate the join */
 811                 for (i = n - 1; i > 0; --i) {
 812                         ir_node *pred    = get_Block_cfgpred_block(bl->block, i);
 813                         block_t *pred_bl = get_block_entry(pred);
 814
 815                         rbitset_and(env.curr_set, pred_bl->avail_out, env.rbs_size);
 816
 817                 }
 818                 /* sure that all values are in the map */
 819                 for (pos = env.rbs_size - 1; pos >= 0; --pos) {
 820                         if (! rbitset_is_set(env.curr_set, pos))
 821                                 bl->id_2_memop[pos] = NULL;
 822                         else {
 823                                 for (i = n - 1; i >= 0; --i) {
 824                                         ir_node *pred    = get_Block_cfgpred_block(bl->block, i);
 825                                         block_t *pred_bl = get_block_entry(pred);
 826
 827                                         if (pred_bl->id_2_memop[pos] != NULL) {
 828                                                 bl->id_2_memop[pos] = pred_bl->id_2_memop[pos];
 829                                                 break;
 830                                         }
 831                                 }
 832                         }
 833                 }
 834         } else {
 835                 /* only one predecessor, simply copy the map */
 836                 memcpy(bl->id_2_memop, pred_bl->id_2_memop, env.rbs_size * sizeof(bl->id_2_memop[0]));
 837         }
 838
 839         dump_curr(bl, "Avail_in");
 840
 841         for (op = bl->memop_forward; op != NULL; op = op->next) {
 842                 switch (get_irn_opcode(op->node)) {
 843                 case iro_Phi:
 844                         /* meet */
 845                         break;
 846                 case iro_Sync:
 847                         /* join */
 848                         break;
 849                 case iro_Load:
 850                         if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) {
 851                                 /* do we have this already? */
 852                                 memop_t *other = find_address(bl, &op->value);
 853                                 if (other != NULL) {
 854                                         if (is_Store(other->node)) {
 855                                                 /* RAW */
 856                                                 DB((dbg, LEVEL_1, "RAW %+F %+F\n", op->node, other->node));
 857                                         } else {
 858                                                 /* RAR */
 859                                                 DB((dbg, LEVEL_1, "RAR %+F %+F\n", op->node, other->node));
 860                                         }
 861                                         def = find_definition(bl->block, &other->value);
 862                                         mark_replace_load(op, def);
 863                                 } else {
 864                                         /* add this value */
 865                                         kill_stores(bl, &op->value);
 866                                         add_memop(bl, op);
 867                                 }
 868                         }
 869                         break;
 870                 case iro_Store:
 871                         if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) {
 872                                 /* do we have this store already */
 873                                 memop_t *other = find_address(bl, &op->value);
 874                                 if (other != NULL) {
 875                                         if (is_Store(other->node)) {
 876                                                 /* a WAW */
 877                                                 DB((dbg, LEVEL_1, "WAW %+F %+F\n", op->node, other->node));
 878                                                 mark_remove_store(other);
 879                                                 /* FIXME: a Load might be get freed due to this killed store */
 880                                         } else if (other->value.value == op->value.value) {
 881                                                 /* WAR */
 882                                                 DB((dbg, LEVEL_1, "WAR %+F %+F\n", op->node, other->node));
 883                                                 mark_remove_store(op);
 884                                         } else {
 885                                                 /* we overwrite the value that was loaded */
 886                                                 add_memop(bl, op);
 887                                         }
 888                                 } else {
 889                                         /* add this value */
 890                                         kill_memops(bl, &op->value);
 891                                         add_memop(bl, op);
 892                                 }
 893                         }
 894                         break;
 895                 default:
 896                         switch (op->flags & (FLAG_KILL_LOADS|FLAG_KILL_STORES)) {
 897                         case FLAG_KILL_LOADS|FLAG_KILL_STORES:
 898                                 kill_all();
 899                                 break;
 900                         case FLAG_KILL_LOADS:
 901                                 kill_all_loads(bl);
 902                                 break;
 903                         case FLAG_KILL_STORES:
 904                                 kill_all_stores(bl);
 905                                 break;
 906                         case 0:
 907                                 break;
 908                         }
 909                 }
 910         }
 911         dump_curr(bl, "Avail_out");
 912         if (memcmp(bl->avail_out, env.curr_set, BYTE_SIZE(env.rbs_size)) != 0) {
 913                 /* changed */
 914                 memcpy(bl->avail_out, env.curr_set, env.rbs_size);
 915                 return 1;
 916         }
 917         return 0;
 918 }
 919
 920 /**
 921  * Do backward dataflow analysis on a given block to calculate the antic set
 922  * of Loaded addresses.
 923  *
 924  * @param bl  the block
 925  *
 926  * @return non-zero if the set has changed since last iteration
 927  */
 928 static int backward_antic(block_t *bl) {
 929         memop_t *op;
 930         ir_node *succ    = get_Block_cfg_out(bl->block, 0);
 931         block_t *succ_bl = get_block_entry(succ);
 932         int     n;
 933
 934         memcpy(env.curr_set,   succ_bl->anticL_in,  BYTE_SIZE(env.rbs_size));
 935         memcpy(bl->id_2_memop, succ_bl->id_2_memop, env.rbs_size * sizeof(bl->id_2_memop[0]));
 936
 937         n = get_Block_n_cfg_outs(bl->block);
 938         if (n > 1) {
 939                 int i;
 940
 941                 for (i = n - 1; i > 0; --i) {
 942                         ir_node *succ    = get_Block_cfg_out(bl->block, i);
 943                         block_t *succ_bl = get_block_entry(succ);
 944
 945                         rbitset_and(env.curr_set, succ_bl->anticL_in, env.rbs_size);
 946                 }
 947         }
 948
 949 #if 0
 950         /* cleanup: kill those Loads which address is not available */
 951         for (pos = rbitset_next(env.curr_set, pos, 1); pos != end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
 952                 memop_t *op     = succ_bl->id_2_memop[pos];
 953                 ir_node *ptr    = get_Load_ptr(op->node);
 954                 ir_node *ptr_bl = get_nodes_block(ptr);
 955
 956                 if (!block_dominates(ptr_bl, bl->block))
 957                         rbitset_clear(env.curr_set, pos);
 958         }
 959 #endif
 960
 961         dump_curr(bl, "AnticL_out");
 962
 963         for (op = bl->memop_backward; op != NULL; op = op->prev) {
 964                 switch (get_irn_opcode(op->node)) {
 965                 case iro_Phi:
 966                         /* meet */
 967                         break;
 968                 case iro_Sync:
 969                         /* join */
 970                         break;
 971                 case iro_Load:
 972                         if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) {
 973                                 /* always add it */
 974                                 add_memop(bl, op);
 975                         }
 976                         break;
 977                 case iro_Store:
 978                         if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) {
 979                                 /* a Store: check which memops must be killed */
 980                                 kill_memops(bl, &op->value);
 981                         }
 982                         break;
 983                 default:
 984                         switch (op->flags & (FLAG_KILL_LOADS|FLAG_KILL_STORES)) {
 985                         case FLAG_KILL_LOADS|FLAG_KILL_STORES:
 986                                 kill_all();
 987                                 break;
 988                         case FLAG_KILL_LOADS:
 989                                 kill_all_loads(bl);
 990                                 break;
 991                         case FLAG_KILL_STORES:
 992                                 kill_all_stores(bl);
 993                                 break;
 994                         case 0:
 995                                 break;
 996                         }
 997                 }
 998         }
 999         dump_curr(bl, "AnticL_in");
1000         if (memcmp(bl->anticL_in, env.curr_set, BYTE_SIZE(env.rbs_size)) != 0) {
1001                 /* changed */
1002                 memcpy(bl->anticL_in, env.curr_set, env.rbs_size);
1003                 return 1;
1004         }
1005         return 0;
1006 }
1007
1008 /**
1009  * Replace a Load memop by a already known value.
1010  *
1011  * @param op  the Load memop
1012  */
1013 static void replace_load(memop_t *op) {
1014         ir_node *load = op->node;
1015         ir_node *def  = skip_Id(op->replace);
1016         int     i;
1017         ir_mode *mode;
1018
1019         if (def != NULL)
1020                 DB((dbg, LEVEL_1, "Replacing %+F by definition %+F\n", load, def));
1021         else {
1022                 if (op->flags & FLAG_EXCEPTION) {
1023                         /* bad: this node is unused and executed for exception only */
1024                         DB((dbg, LEVEL_1, "Unused %+F executed for exception only ...\n", load));
1025                         return;
1026                 }
1027                 DB((dbg, LEVEL_1, "Killing unused %+F\n", load));
1028         }
1029         for (i = get_irn_n_outs(load) - 1; i >= 0; --i) {
1030                 ir_node *proj = get_irn_out(load, i);
1031
1032                 switch (get_Proj_proj(proj)) {
1033                 case pn_Load_M:
1034                         exchange(proj, get_Load_mem(load));
1035                         break;
1036                 case pn_Load_res:
1037                         mode = get_irn_mode(proj);
1038                         if (get_irn_mode(def) != mode) {
1039                                 /* a hidden cast */
1040                                 dbg_info *db    = get_irn_dbg_info(load);
1041                                 ir_node  *block = get_nodes_block(proj);
1042                                 def = new_rd_Conv(db, current_ir_graph, block, def, mode);
1043                         }
1044                         exchange(proj, def);
1045                         break;
1046                 case pn_Load_X_except:
1047                         exchange(proj, new_Bad());
1048                         break;
1049                 case pn_Load_X_regular:
1050                         exchange(proj, new_r_Jmp(current_ir_graph, get_nodes_block(load)));
1051                         break;
1052                 default:
1053                         panic("Unknown Proj from Load");
1054                 }
1055         }
1056 }
1057
1058 /**
1059  * Remove a Store memop.
1060  *
1061  * @param op  the Store memop
1062  */
1063 static void remove_store(memop_t *op) {
1064         ir_node *store = op->node;
1065         int     i;
1066
1067         DB((dbg, LEVEL_1, "Removing %+F\n", store));
1068         for (i = get_irn_n_outs(store) - 1; i >= 0; --i) {
1069                 ir_node *proj = get_irn_out(store, i);
1070
1071                 switch (get_Proj_proj(proj)) {
1072                 case pn_Store_M:
1073                         exchange(proj, get_Store_mem(store));
1074                         break;
1075                 case pn_Store_X_except:
1076                         exchange(proj, new_Bad());
1077                         break;
1078                 case pn_Store_X_regular:
1079                         exchange(proj, new_r_Jmp(current_ir_graph, get_nodes_block(store)));
1080                         break;
1081                 default:
1082                         panic("Unknown Proj from Store");
1083                 }
1084         }
1085 }
1086
1087
1088 /**
1089  * Do all necessary replacements for a given block.
1090  *
1091  * @param bl  the block
1092  */
1093 static void do_replacements(block_t *bl) {
1094         memop_t *op;
1095
1096         for (op = bl->memop_forward; op != NULL; op = op->next) {
1097                 if (op->flags & FLAG_KILLED_NODE) {
1098                         switch (get_irn_opcode(op->node)) {
1099                         case iro_Load:
1100                                 replace_load(op);
1101                                 break;
1102                         case iro_Store:
1103                                 remove_store(op);
1104                                 break;
1105                         }
1106                 }
1107         }
1108 }
1109
1110 /**
1111  * Calculate the Avail_out sets for all basic blocks.
1112  */
1113 static void calcAvail(void) {
1114         int i, need_iter;
1115         block_t *bl;
1116
1117         /* calculate avail_out */
1118         DB((dbg, LEVEL_2, "Calculate Avail_out\n"));
1119         i = 0;
1120         do {
1121                 DB((dbg, LEVEL_2, "Iteration %d:\n=========\n", i));
1122
1123                 need_iter = 0;
1124
1125                 /* over all blocks in reverse post order, skip the start block */
1126                 for (bl = env.forward->forward_next; bl != NULL; bl = bl->forward_next) {
1127                         need_iter |= forward_avail(bl);
1128                 }
1129                 ++i;
1130         } while (need_iter);
1131
1132         /* copy the content of the id_2_memop map into the id_2_memop_avail map
1133            as it must be preserved for later use */
1134         for (bl = env.forward->forward_next; bl != NULL; bl = bl->forward_next) {
1135                 memop_t **t = bl->id_2_memop_avail;
1136
1137                 bl->id_2_memop_avail = bl->id_2_memop;
1138                 bl->id_2_memop       = t;
1139         }
1140         DB((dbg, LEVEL_2, "Get avail set after %d iterations\n\n", i));
1141 }
1142
1143 /**
1144  * Calculate the Antic_in sets for all basic blocks.
1145  */
1146 static void calcAntic(void) {
1147         int i, need_iter;
1148
1149         /* calculate antic_out */
1150         DB((dbg, LEVEL_2, "Calculate Antic_in\n"));
1151         i = 0;
1152         do {
1153                 block_t *bl;
1154
1155                 DB((dbg, LEVEL_2, "Iteration %d:\n=========\n", i));
1156
1157                 need_iter = 0;
1158
1159                 /* over all blocks in reverse post order */
1160                 for (bl = env.backward->backward_next; bl != NULL; bl = bl->backward_next) {
1161                         need_iter |= backward_antic(bl);
1162                 }
1163                 ++i;
1164         } while (need_iter);
1165         DB((dbg, LEVEL_2, "Get anticipated Load set after %d iterations\n", i));
1166 }
1167
1168 /**
1169  * Return the node representing the last memory in a block.
1170  *
1171  * @param bl  the block
1172  */
1173 static ir_node *find_first_memory(block_t *bl) {
1174         for (;;) {
1175                 if (bl->memop_forward != NULL) {
1176                         return bl->memop_forward->node;
1177                 }
1178                 /* if there is NO memory in this block, go to the post dominator */
1179                 bl = get_block_entry(get_Block_ipostdom(bl->block));
1180         }
1181 }
1182
1183 /**
1184  * Return the node representing the last memory in a block.
1185  *
1186  * @param bl  the block
1187  */
1188 static ir_node *find_last_memory(block_t *bl) {
1189         for (;;) {
1190                 if (bl->memop_backward != NULL) {
1191                         return bl->memop_backward->mem;
1192                 }
1193                 /* if there is NO memory in this block, go to the dominator */
1194                 bl = get_block_entry(get_Block_idom(bl->block));
1195         }
1196 }
1197
1198 /**
1199  * Reroute the memory. Reroute all users of old memory
1200  * to a new memory IR-node.
1201  *
1202  * @param omem  the old memory IR-node
1203  * @param nmem  the new memory IR-node
1204  */
1205 static void reroute_mem(ir_node *omem, ir_node *nmem) {
1206         int i;
1207
1208         for (i = get_irn_n_outs(omem) - 1; i >= 0; --i) {
1209                 int     n_pos;
1210                 ir_node *succ = get_irn_out_ex(omem, i, &n_pos);
1211
1212                 set_irn_n(succ, n_pos, nmem);
1213         }
1214
1215         /* all edges formally point to omem now point to nmem */
1216         nmem->out = omem->out;
1217 }
1218
1219 /**
1220  * insert
1221  */
1222 static void insert_Load(ir_node *block, void *ctx) {
1223         int     *new_stuff = ctx;
1224         block_t *bl;
1225         int     i, n = get_Block_n_cfgpreds(block);
1226         unsigned pos = 0;
1227         unsigned end = env.n_mem_ops * 2 - 1;
1228
1229         if (n <= 1)
1230                 return;
1231
1232         bl = get_block_entry(block);
1233
1234         for (pos = rbitset_next(bl->anticL_in, pos, 1); pos != end; pos = rbitset_next(bl->anticL_in, pos + 1, 1)) {
1235                 memop_t *op = bl->id_2_memop[pos];
1236                 int     have_some;
1237
1238                 assert(is_Load(op->node));
1239
1240                 if (op->flags & FLAG_KILLED_NODE)
1241                         continue;
1242
1243                 have_some  = 0;
1244                 for (i = n - 1; i >= 0; --i) {
1245                         ir_node *pred    = get_Block_cfgpred_block(block, i);
1246                         block_t *pred_bl = get_block_entry(pred);
1247                         memop_t *e       = find_address_avail(pred_bl, &op->value);
1248
1249                         if (e == NULL) {
1250                                 ir_node *block = get_nodes_block(op->value.address);
1251                                 if (! block_dominates(block, pred)) {
1252                                         /* cannot place a copy here */
1253                                         have_some = 0;
1254                                         break;
1255                                 }
1256                                 pred_bl->avail = NULL;
1257                         } else {
1258                                 pred_bl->avail = e;
1259                                 have_some      = 1;
1260                         }
1261                 }
1262                 if (have_some) {
1263                         ir_mode *mode = op->value.mode;
1264                         ir_node **in, *phi;
1265
1266                         NEW_ARR_A(ir_node *, in, n);
1267
1268                         for (i = n - 1; i >= 0; --i) {
1269                                 ir_node *pred    = get_Block_cfgpred_block(block, i);
1270                                 block_t *pred_bl = get_block_entry(pred);
1271
1272                                 if (pred_bl->avail == NULL) {
1273                                         /* create a new Load here and make to make it fully redundant */
1274                                         dbg_info *db       = get_irn_dbg_info(op->node);
1275                                         ir_node  *last_mem = find_last_memory(pred_bl);
1276                                         ir_node  *load, *def;
1277                                         memop_t  *new_op;
1278
1279                                         load = new_rd_Load(db, current_ir_graph, pred, last_mem, op->value.address, mode, cons_none);
1280                                         def  = new_r_Proj(current_ir_graph, pred, load, mode, pn_Load_res);
1281                                         DB((dbg, LEVEL_1, "Created new %+F for party redundant %+F\n", load, op->node));
1282
1283                                         new_op                = alloc_memop(load);
1284                                         new_op->mem           = new_r_Proj(current_ir_graph, pred, load, mode_M, pn_Load_M);
1285                                         new_op->value.address = op->value.address;
1286                                         new_op->value.id      = op->value.id;
1287                                         new_op->value.mode    = mode;
1288                                         new_op->value.value   = def;
1289
1290                                         new_op->prev            = pred_bl->memop_backward;
1291                                         pred_bl->memop_backward = new_op;
1292
1293                                         reroute_mem(last_mem, new_op->mem);
1294
1295                                         /* we added this load at the end, so it will be avail anyway */
1296                                         add_memop_avail(pred_bl, new_op);
1297                                         pred_bl->avail = new_op;
1298                                 }
1299                                 in[i] = pred_bl->avail->value.value;
1300                         }
1301                         phi = new_r_Phi(current_ir_graph, block, n, in, mode);
1302                         mark_replace_load(op, phi);
1303                         *new_stuff = 1;
1304
1305                         if (get_nodes_block(op->node) == block) {
1306                                 /* The redundant node was in the current block:
1307                                    In that case, DO NOT update avail_out. If it was NOT
1308                                    avail although it is executed in this bLock, it is killed by a later
1309                                    instruction.
1310                                  */
1311                         } else {
1312                                 /* The redundant node is NOT in the current block and anticipated.
1313                                    This can only happen IFF nothings kills the Load in the current block,
1314                                    so it will be avail in the next iteration.
1315                                  */
1316                                 add_memop_avail(bl, op);
1317
1318                                 /* TODO propagate it downwards */
1319                         }
1320                 }
1321         }
1322 }
1323
1324 /**
1325  * Insert Loads upwards.
1326  */
1327 static void insert_Loads_upwards(void) {
1328         int i, need_iter;
1329
1330         /* calculate antic_out */
1331         DB((dbg, LEVEL_2, "Inserting Loads"));
1332         i = 0;
1333         do {
1334                 DB((dbg, LEVEL_2, "Iteration %d:\n=========\n", i));
1335
1336                 need_iter = 0;
1337                 dom_tree_walk_irg(current_ir_graph, insert_Load, NULL, &need_iter);
1338                 ++i;
1339         } while (need_iter);
1340         DB((dbg, LEVEL_2, "Finished Load inserting after %d iterations\n", i));
1341 }
1342
1343 int opt_ldst(ir_graph *irg) {
1344         block_t  *bl;
1345         ir_graph *rem = current_ir_graph;
1346
1347         current_ir_graph = irg;
1348
1349         FIRM_DBG_REGISTER(dbg, "firm.opt.ldst");
1350
1351         DB((dbg, LEVEL_1, "\nDoing Load/Store optimization on %+F\n", irg));
1352
1353         /* we need landing pads */
1354         remove_critical_cf_edges(irg);
1355
1356         if (get_opt_alias_analysis()) {
1357                 assure_irg_entity_usage_computed(irg);
1358                 assure_irp_globals_entity_usage_computed();
1359         }
1360
1361         obstack_init(&env.obst);
1362         ir_nodemap_init(&env.adr_map);
1363
1364         env.forward     = NULL;
1365         env.backward    = NULL;
1366         env.curr_adr_id = 0;
1367         env.n_mem_ops   = 0;
1368         env.changed     = 0;
1369         env.start_bl    = get_irg_start_block(irg);
1370
1371         assure_doms(irg);
1372         assure_irg_outs(irg);
1373
1374         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
1375
1376         /* first step: allocate block entries: produces an
1377            inverse post-order list for the CFG */
1378         irg_out_block_walk(get_irg_start_block(irg), NULL, prepare_blocks, NULL);
1379
1380         /* second step: find and sort all memory ops */
1381         walk_memory_irg(irg, collect_memops, NULL, NULL);
1382
1383         /* create the backward links */
1384         irg_block_walk_graph(irg, NULL, collect_backward, NULL);
1385
1386         /* check that we really start with the start / end block */
1387         assert(env.forward->block  == env.start_bl);
1388         assert(env.backward->block == get_irg_end_block(irg));
1389
1390         /* create address sets: we know that 2 * n_mem_ops - 1 is an upper bound for all possible addresses */
1391         env.rbs_size = 2 * env.n_mem_ops;
1392
1393         /* create the current set */
1394         env.curr_set = rbitset_obstack_alloc(&env.obst, env.rbs_size);
1395         rbitset_set(env.curr_set, env.rbs_size - 1);
1396
1397         for (bl = env.forward; bl != NULL; bl = bl->forward_next) {
1398                 /* set sentinel bits */
1399                 bl->avail_out  = rbitset_obstack_alloc(&env.obst, env.rbs_size);
1400                 rbitset_set(bl->avail_out, env.rbs_size - 1);
1401
1402                 bl->id_2_memop_avail = NEW_ARR_D(memop_t *, &env.obst, env.rbs_size);
1403                 memset(bl->id_2_memop_avail, 0, env.rbs_size * sizeof(bl->id_2_memop[0]));
1404
1405                 bl->anticL_in  = rbitset_obstack_alloc(&env.obst, env.rbs_size);
1406                 rbitset_set(bl->anticL_in, env.rbs_size - 1);
1407
1408                 bl->id_2_memop = NEW_ARR_D(memop_t *, &env.obst, env.rbs_size);
1409                 memset(bl->id_2_memop, 0, env.rbs_size * sizeof(bl->id_2_memop[0]));
1410         }
1411
1412 //      dump_block_list(&env);
1413
1414         calcAvail();
1415         calcAntic();
1416
1417         insert_Loads_upwards();
1418
1419         if (env.changed) {
1420                 /* over all blocks in reverse post order */
1421                 for (bl = env.forward; bl != NULL; bl = bl->forward_next) {
1422                         do_replacements(bl);
1423                 }
1424
1425                 set_irg_outs_inconsistent(irg);
1426                 set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
1427         }
1428
1429         ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
1430         ir_nodemap_destroy(&env.adr_map);
1431         obstack_free(&env.obst, NULL);
1432
1433         current_ir_graph = rem;
1434
1435         return env.changed != 0;
1436 }