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 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 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         entry->backward_next = env.backward;
 289
 290         /* create the list in inverse order */
 291         env.backward = entry;
 292
 293         /* create backward links for all memory ops */
 294         last = NULL;
 295         for (op = entry->memop_forward; op != NULL; op = op->next) {
 296                 op->prev = last;
 297                 last     = op;
 298         }
 299         entry->memop_backward = last;
 300 }
 301
 302 /**
 303  * Allocate a memop.
 304  *
 305  * @param irn  the IR-node representing the memop
 306  */
 307 static memop_t *alloc_memop(ir_node *irn) {
 308         memop_t *m = obstack_alloc(&env.obst, sizeof(*m));
 309
 310         m->value.address = NULL;
 311         m->value.value   = NULL;
 312         m->value.mode    = NULL;
 313
 314         m->node          = irn;
 315         m->replace       = NULL;
 316         m->next          = NULL;
 317         m->flags         = 0;
 318
 319         return m;
 320 }
 321
 322 /**
 323  * Register an address and allocate an ID for it.
 324  *
 325  * @param adr  the IR-node representing the address
 326  */
 327 static unsigned register_address(ir_node *adr) {
 328         address_entry *entry = ir_nodemap_get(&env.adr_map, adr);
 329
 330         if (entry == NULL) {
 331                 /* new address */
 332                 entry = obstack_alloc(&env.obst, sizeof(*entry));
 333
 334                 entry->id = env.curr_adr_id++;
 335                 ir_nodemap_insert(&env.adr_map, adr, entry);
 336         }
 337         return entry->id;
 338 }
 339
 340 /**
 341  * Return the memory properties of a call node.
 342  *
 343  * @param call  the call node
 344  *
 345  * return a bitset of mtp_property_const and mtp_property_pure
 346  */
 347 static unsigned get_Call_memory_properties(ir_node *call) {
 348         ir_type *call_tp = get_Call_type(call);
 349         unsigned prop = get_method_additional_properties(call_tp);
 350
 351         /* check first the call type */
 352         if ((prop & (mtp_property_const|mtp_property_pure)) == 0) {
 353                 /* try the called entity */
 354                 ir_node *ptr = get_Call_ptr(call);
 355
 356                 if (is_Global(ptr)) {
 357                         ir_entity *ent = get_Global_entity(ptr);
 358
 359                         prop = get_entity_additional_properties(ent);
 360                 }
 361         }
 362         return prop & (mtp_property_const|mtp_property_pure);
 363 }
 364
 365 /**
 366  * Update a memop for a Load.
 367  *
 368  * @param m  the memop
 369  */
 370 static void update_Load_memop(memop_t *m) {
 371         int     i;
 372         ir_node *load = m->node;
 373         ir_node *adr  = get_Load_ptr(load);
 374
 375         if (get_Load_volatility(load) == volatility_is_volatile)
 376                 m->flags |= FLAG_IGNORE;
 377
 378         m->value.address = adr;
 379
 380         for (i = get_irn_n_outs(load) - 1; i >= 0; --i) {
 381                 ir_node *proj = get_irn_out(load, i);
 382
 383                 switch (get_Proj_proj(proj)) {
 384                 case pn_Load_res:
 385                         m->value.value = proj;
 386                         m->value.mode  = get_irn_mode(proj);
 387                         break;
 388                 case pn_Load_X_except:
 389                         m->flags |= FLAG_EXCEPTION;
 390                         break;
 391                 case pn_Load_M:
 392                         m->mem = proj;
 393                         break;
 394                 }
 395         }
 396
 397         if (m->value.value != NULL && !(m->flags & FLAG_IGNORE)) {
 398                 /* only create an address if this node is NOT killed immediately or ignored */
 399                 m->value.id = register_address(adr);
 400                 ++env.n_mem_ops;
 401         } else {
 402                 /* no user, KILL it */
 403                 m->flags |= FLAG_KILLED_NODE;
 404         }
 405 }
 406
 407 /**
 408  * Update a memop for a Store.
 409  *
 410  * @param m  the memop
 411  */
 412 static void update_Store_memop(memop_t *m) {
 413         int     i;
 414         ir_node *store = m->node;
 415         ir_node *adr   = get_Store_ptr(store);
 416
 417         if (get_Store_volatility(store) == volatility_is_volatile) {
 418                 m->flags |= FLAG_IGNORE;
 419         } else {
 420                 /* only create an address if this node is NOT ignored */
 421                 m->value.id = register_address(adr);
 422                 ++env.n_mem_ops;
 423         }
 424
 425         m->value.address = adr;
 426
 427         for (i = get_irn_n_outs(store) - 1; i >= 0; --i) {
 428                 ir_node *proj = get_irn_out(store, i);
 429
 430                 switch (get_Proj_proj(proj)) {
 431                 case pn_Store_X_except:
 432                         m->flags |= FLAG_EXCEPTION;
 433                         break;
 434                 case pn_Store_M:
 435                         m->mem = proj;
 436                         break;
 437                 }
 438         }
 439         m->value.value = get_Store_value(store);
 440         m->value.mode  = get_irn_mode(m->value.value);
 441 }
 442
 443 /**
 444  * Update a memop for a Call.
 445  *
 446  * @param m  the memop
 447  */
 448 static void update_Call_memop(memop_t *m) {
 449         ir_node  *call = m->node;
 450         unsigned prop  = get_Call_memory_properties(call);
 451         int      i;
 452
 453         if (prop & mtp_property_const) {
 454                 /* A constant call did NOT use memory at all, we
 455                    can kick it from the list. */
 456         } else if (prop & mtp_property_pure) {
 457                 /* pure calls READ memory */
 458                 m->flags = FLAG_KILL_STORES;
 459         } else
 460                 m->flags = FLAG_KILL_ALL;
 461
 462         for (i = get_irn_n_outs(call) - 1; i >= 0; --i) {
 463                 ir_node *proj = get_irn_out(call, i);
 464
 465                 switch (get_Proj_proj(proj)) {
 466                 case pn_Call_X_except:
 467                         m->flags |= FLAG_EXCEPTION;
 468                         break;
 469                 case pn_Call_M_regular:
 470                         m->mem = proj;
 471                         break;
 472                 }
 473         }
 474 }
 475
 476 /**
 477  * Update a memop for a Div/Mod/Quot/DivMod.
 478  *
 479  * @param m  the memop
 480  */
 481 static void update_DivOp_memop(memop_t *m) {
 482         ir_node *div = m->node;
 483         int     i;
 484
 485         for (i = get_irn_n_outs(div) - 1; i >= 0; --i) {
 486                 ir_node *proj = get_irn_out(div, i);
 487
 488                 switch (get_Proj_proj(proj)) {
 489                 case pn_Generic_X_except:
 490                         m->flags |= FLAG_EXCEPTION;
 491                         break;
 492                 case pn_Generic_M_regular:
 493                         m->mem = proj;
 494                         break;
 495                 }
 496         }
 497 }
 498
 499 /**
 500  * Memory walker: collect all memory ops and build topological lists.
 501  */
 502 static void collect_memops(ir_node *irn, void *ctx) {
 503         memop_t  *op;
 504         ir_node  *block;
 505         block_t  *entry;
 506
 507         if (is_Proj(irn)) {
 508                 /* we can safely ignore ProjM's except the initial memory */
 509                 if (irn != get_irg_initial_mem(current_ir_graph))
 510                         return;
 511         }
 512
 513         op    = alloc_memop(irn);
 514         block = get_nodes_block(irn);
 515         entry = get_block_entry(block);
 516
 517         if (is_Phi(irn)) {
 518                 /* Phis must be always placed first */
 519                 op->next = entry->memop_forward;
 520                 entry->memop_forward = op;
 521                 if (entry->memop_backward == NULL)
 522                         entry->memop_backward = op;
 523         } else {
 524                 switch (get_irn_opcode(irn)) {
 525                 case iro_Load:
 526                         update_Load_memop(op);
 527                         break;
 528                 case iro_Store:
 529                         update_Store_memop(op);
 530                         break;
 531                 case iro_Call:
 532                         update_Call_memop(op);
 533                         break;
 534                 case iro_Sync:
 535                 case iro_Pin:
 536                         op->mem = irn;
 537                         break;
 538                 case iro_Proj:
 539                         /* initial memory */
 540                         op->mem = irn;
 541                         break;
 542                 case iro_Return:
 543                 case iro_End:
 544                         /* we can those to find the memory edge */
 545                         break;
 546                 case iro_Div:
 547                 case iro_DivMod:
 548                 case iro_Quot:
 549                 case iro_Mod:
 550                         update_DivOp_memop(op);
 551                         break;
 552
 553                 case iro_Builtin:
 554                         /* TODO: handle some builtins */
 555                 default:
 556                         /* unsupported operation */
 557                         op->flags = FLAG_KILL_ALL;
 558                 }
 559
 560
 561                 /* all other should be placed last */
 562                 if (entry->memop_backward == NULL) {
 563                         entry->memop_forward = entry->memop_backward = op;
 564                 } else {
 565                         entry->memop_backward->next = op;
 566                         entry->memop_backward       = op;
 567                 }
 568         }
 569 }
 570
 571 /**
 572  * Find an address in the current set.
 573  *
 574  * @param bl     the block
 575  * @param value  the value to be searched for
 576  */
 577 static memop_t *find_address(const block_t *bl, const value_t *value) {
 578         if (rbitset_is_set(env.curr_set, value->id)) {
 579                 memop_t *res = bl->id_2_memop[value->id];
 580
 581                 if (res->value.mode == value->mode)
 582                         return res;
 583                 /* allow hidden casts */
 584                 if (get_mode_arithmetic(res->value.mode) == irma_twos_complement &&
 585                     get_mode_arithmetic(value->mode) == irma_twos_complement &&
 586                     get_mode_size_bits(res->value.mode) == get_mode_size_bits(value->mode))
 587                         return res;
 588         }
 589         return NULL;
 590 }
 591
 592 /**
 593  * Find an address in the avail_out set.
 594  *
 595  * @param bl     the block
 596  * @param value  the value to be searched for
 597  */
 598 static memop_t *find_address_avail(const block_t *bl, const value_t *value) {
 599         if (rbitset_is_set(bl->avail_out, value->id)) {
 600                 memop_t *res = bl->id_2_memop_avail[value->id];
 601
 602                 if (res->value.mode == value->mode)
 603                         return res;
 604                 /* allow hidden casts */
 605                 if (get_mode_arithmetic(res->value.mode) == irma_twos_complement &&
 606                     get_mode_arithmetic(value->mode) == irma_twos_complement &&
 607                     get_mode_size_bits(res->value.mode) == get_mode_size_bits(value->mode))
 608                         return res;
 609         }
 610         return NULL;
 611 }
 612
 613 /**
 614  * Kill all Loads from the current set.
 615  *
 616  * @param bl  the current block
 617  */
 618 static void kill_all_loads(block_t *bl) {
 619         unsigned pos = 0;
 620         unsigned end = env.n_mem_ops * 2 - 1;
 621
 622         for (pos = rbitset_next(env.curr_set, pos, 1); pos != end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
 623                 memop_t *op = bl->id_2_memop[pos];
 624
 625                 if (! is_Store(op->node))
 626                         rbitset_clear(env.curr_set, pos);
 627         }
 628 }
 629
 630 /**
 631  * Kill all Stores from the current set.
 632  *
 633  * @param bl  the current block
 634  */
 635 static void kill_all_stores(block_t *bl) {
 636         unsigned pos = 0;
 637         unsigned end = env.n_mem_ops * 2 - 1;
 638
 639         for (pos = rbitset_next(env.curr_set, pos, 1); pos != end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
 640                 memop_t *op = bl->id_2_memop[pos];
 641
 642                 if (is_Store(op->node))
 643                         rbitset_clear(env.curr_set, pos);
 644         }
 645 }
 646
 647 /**
 648  * Kill all addresses from the current set.
 649  */
 650 static void kill_all(void) {
 651         rbitset_clear_all(env.curr_set, env.rbs_size);
 652
 653         /* set sentinel */
 654         rbitset_set(env.curr_set, env.rbs_size - 1);
 655 }
 656
 657
 658 /**
 659  * Kill Stores that are not alias free due to a Load value from the current set.
 660  *
 661  * @param bl     the block
 662  * @param value  the Load value
 663  */
 664 static void kill_stores(block_t *bl, const value_t *value) {
 665         unsigned pos = 0;
 666         unsigned end = env.n_mem_ops * 2 - 1;
 667
 668         for (pos = rbitset_next(env.curr_set, pos, 1); pos != end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
 669                 memop_t *op = bl->id_2_memop[pos];
 670
 671                 if (is_Store(op->node)) {
 672                         if (ir_no_alias != get_alias_relation(current_ir_graph, value->address, value->mode,
 673                                                               op->value.address, op->value.mode)) {
 674                                 rbitset_clear(env.curr_set, pos);
 675                                 bl->id_2_memop[pos] = NULL;
 676                         }
 677                 }
 678         }
 679 }
 680
 681 /**
 682  * Kill memops that are not alias free due to a Store value from the current set.
 683  *
 684  * @param bl     the block
 685  * @param value  the Store value
 686  */
 687 static void kill_memops(block_t *bl, const value_t *value) {
 688         unsigned pos = 0;
 689         unsigned end = env.n_mem_ops * 2 - 1;
 690
 691         for (pos = rbitset_next(env.curr_set, pos, 1); pos != end; pos = rbitset_next(env.curr_set, pos + 1, 1)) {
 692                 memop_t *op = bl->id_2_memop[pos];
 693
 694                 if (ir_no_alias != get_alias_relation(current_ir_graph, value->address, value->mode,
 695                                                           op->value.address, op->value.mode)) {
 696                         rbitset_clear(env.curr_set, pos);
 697                         bl->id_2_memop[pos] = NULL;
 698                 }
 699         }
 700 }
 701
 702 /**
 703  * Add the value of a memop to the current set.
 704  *
 705  * @param bl  the block
 706  * @param op  the memory op
 707  */
 708 static void add_memop(block_t *bl, memop_t *op) {
 709         rbitset_set(env.curr_set, op->value.id);
 710         bl->id_2_memop[op->value.id] = op;
 711 }
 712
 713 /**
 714  * Add the value of a memop to the avail_out set.
 715  *
 716  * @param bl  the block
 717  * @param op  the memory op
 718  */
 719 static void add_memop_avail(block_t *bl, memop_t *op) {
 720         rbitset_set(bl->avail_out, op->value.id);
 721         bl->id_2_memop_avail[op->value.id] = op;
 722 }
 723
 724 /**
 725  * find a definition for a value in the given block.
 726  *
 727  * @param block  the block
 728  * @param value  the value
 729  *
 730  * @return the definition
 731  */
 732 static ir_node *find_definition(ir_node *block, const value_t *value) {
 733         ir_node *def_bl = get_nodes_block(value->value);
 734         ir_node **in, *phi;
 735         int     i, n;
 736         memop_t *mop;
 737
 738         if (block_dominates(def_bl, block))
 739                 return value->value;
 740
 741         /* no: we need a new Phi */
 742         n = get_Block_n_cfgpreds(block);
 743
 744         while (n == 1) {
 745                 block = get_Block_cfgpred_block(block, 0);
 746                 n     = get_Block_n_cfgpreds(block);
 747                 mop   = find_address(get_block_entry(block), value);
 748
 749                 assert(mop != NULL);
 750                 value = &mop->value;
 751         }
 752
 753         NEW_ARR_A(ir_node *, in, n);
 754         for (i = n - 1; i >= 0; --i) {
 755                 ir_node *pred_bl = get_Block_cfgpred_block(block, i);
 756                 mop   = find_address(get_block_entry(pred_bl), value);
 757                 in[i] = find_definition(pred_bl, &mop->value);
 758         }
 759
 760         phi = new_r_Phi(current_ir_graph, block, n, in, value->mode);
 761         DB((dbg, LEVEL_2, "Created new Phi %+F for value %+F in block %+F\n", phi, value->value, block));
 762         return phi;
 763 }
 764
 765 /**
 766  * Mark a Load memop to be replace by a definition
 767  *
 768  * @param op  the Load memop
 769  */
 770 static void mark_replace_load(memop_t *op, ir_node *def) {
 771         op->replace = def;
 772         op->flags |= FLAG_KILLED_NODE;
 773         env.changed = 1;
 774 }
 775
 776 /**
 777  * Mark a Store memop to be removed.
 778  *
 779  * @param op  the Store memop
 780  */
 781 static void mark_remove_store(memop_t *op) {
 782         op->flags |= FLAG_KILLED_NODE;
 783         env.changed = 1;
 784 }
 785
 786 #define BYTE_SIZE(x)  (((x) + 7) >> 3)
 787
 788 /**
 789  * Do forward dataflow analysis on a given block to calculate the avail_out set.
 790  *
 791  * @param bl  the block
 792  *
 793  * @return non-zero if the set has changed since last iteration
 794  */
 795 static int forward_avail(block_t *bl) {
 796         memop_t *op;
 797         int     n;
 798         ir_node *def;
 799         ir_node *pred    = get_Block_cfgpred_block(bl->block, 0);
 800         block_t *pred_bl = get_block_entry(pred);
 801
 802         memcpy(env.curr_set, pred_bl->avail_out, BYTE_SIZE(env.rbs_size));
 803
 804         n = get_Block_n_cfgpreds(bl->block);
 805         if (n > 1) {
 806                 int i, pos;
 807
 808                 /* more than one predecessors, calculate the join */
 809                 for (i = n - 1; i > 0; --i) {
 810                         ir_node *pred    = get_Block_cfgpred_block(bl->block, i);
 811                         block_t *pred_bl = get_block_entry(pred);
 812
 813                         rbitset_and(env.curr_set, pred_bl->avail_out, env.rbs_size);
 814
 815                 }
 816                 /* sure that all values are in the map */
 817                 for (pos = env.rbs_size - 1; pos >= 0; --pos) {
 818                         if (! rbitset_is_set(env.curr_set, pos))
 819                                 bl->id_2_memop[pos] = NULL;
 820                         else {
 821                                 for (i = n - 1; i >= 0; --i) {
 822                                         ir_node *pred    = get_Block_cfgpred_block(bl->block, i);
 823                                         block_t *pred_bl = get_block_entry(pred);
 824
 825                                         if (pred_bl->id_2_memop[pos] != NULL) {
 826                                                 bl->id_2_memop[pos] = pred_bl->id_2_memop[pos];
 827                                                 break;
 828                                         }
 829                                 }
 830                         }
 831                 }
 832         } else {
 833                 /* only one predecessor, simply copy the map */
 834                 memcpy(bl->id_2_memop, pred_bl->id_2_memop, env.rbs_size * sizeof(bl->id_2_memop[0]));
 835         }
 836
 837         dump_curr(bl, "Avail_in");
 838
 839         for (op = bl->memop_forward; op != NULL; op = op->next) {
 840                 switch (get_irn_opcode(op->node)) {
 841                 case iro_Phi:
 842                         /* meet */
 843                         break;
 844                 case iro_Sync:
 845                         /* join */
 846                         break;
 847                 case iro_Load:
 848                         if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) {
 849                                 /* do we have this already? */
 850                                 memop_t *other = find_address(bl, &op->value);
 851                                 if (other != NULL) {
 852                                         if (is_Store(other->node)) {
 853                                                 /* RAW */
 854                                                 DB((dbg, LEVEL_1, "RAW %+F %+F\n", op->node, other->node));
 855                                         } else {
 856                                                 /* RAR */
 857                                                 DB((dbg, LEVEL_1, "RAR %+F %+F\n", op->node, other->node));
 858                                         }
 859                                         def = find_definition(bl->block, &other->value);
 860                                         mark_replace_load(op, def);
 861                                 } else {
 862                                         /* add this value */
 863                                         kill_stores(bl, &op->value);
 864                                         add_memop(bl, op);
 865                                 }
 866                         }
 867                         break;
 868                 case iro_Store:
 869                         if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) {
 870                                 /* do we have this store already */
 871                                 memop_t *other = find_address(bl, &op->value);
 872                                 if (other != NULL) {
 873                                         if (is_Store(other->node)) {
 874                                                 /* a WAW */
 875                                                 DB((dbg, LEVEL_1, "WAW %+F %+F\n", op->node, other->node));
 876                                                 mark_remove_store(other);
 877                                                 /* FIXME: a Load might be get freed due to this killed store */
 878                                         } else if (other->value.value == op->value.value) {
 879                                                 /* WAR */
 880                                                 DB((dbg, LEVEL_1, "WAR %+F %+F\n", op->node, other->node));
 881                                                 mark_remove_store(op);
 882                                         } else {
 883                                                 /* we overwrite the value that was loaded */
 884                                                 add_memop(bl, op);
 885                                         }
 886                                 } else {
 887                                         /* add this value */
 888                                         kill_memops(bl, &op->value);
 889                                         add_memop(bl, op);
 890                                 }
 891                         }
 892                         break;
 893                 default:
 894                         switch (op->flags & (FLAG_KILL_LOADS|FLAG_KILL_STORES)) {
 895                         case FLAG_KILL_LOADS|FLAG_KILL_STORES:
 896                                 kill_all();
 897                                 break;
 898                         case FLAG_KILL_LOADS:
 899                                 kill_all_loads(bl);
 900                                 break;
 901                         case FLAG_KILL_STORES:
 902                                 kill_all_stores(bl);
 903                                 break;
 904                         case 0:
 905                                 break;
 906                         }
 907                 }
 908         }
 909         dump_curr(bl, "Avail_out");
 910         if (memcmp(bl->avail_out, env.curr_set, BYTE_SIZE(env.rbs_size)) != 0) {
 911                 /* changed */
 912                 memcpy(bl->avail_out, env.curr_set, env.rbs_size);
 913                 return 1;
 914         }
 915         return 0;
 916 }
 917
 918 /**
 919  * Do backward dataflow analysis on a given block to calculate the antic set
 920  * of Loaded addresses.
 921  *
 922  * @param bl  the block
 923  *
 924  * @return non-zero if the set has changed since last iteration
 925  */
 926 static int backward_antic(block_t *bl) {
 927         memop_t *op;
 928         ir_node *succ    = get_Block_cfg_out(bl->block, 0);
 929         block_t *succ_bl = get_block_entry(succ);
 930         int     n;
 931         unsigned pos = 0;
 932         unsigned end = env.n_mem_ops * 2 - 1;
 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       = bl->id_2_memop_avail;
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         firm_dbg_set_mask(dbg, SET_LEVEL_2);
1351
1352         DB((dbg, LEVEL_1, "\nDoing Load/Store optimization on %+F\n", irg));
1353
1354         /* we need landing pads */
1355         remove_critical_cf_edges(irg);
1356
1357         if (get_opt_alias_analysis()) {
1358                 assure_irg_entity_usage_computed(irg);
1359                 assure_irp_globals_entity_usage_computed();
1360         }
1361
1362         obstack_init(&env.obst);
1363         ir_nodemap_init(&env.adr_map);
1364
1365         env.forward     = NULL;
1366         env.backward    = NULL;
1367         env.curr_adr_id = 0;
1368         env.n_mem_ops   = 0;
1369         env.changed     = 0;
1370         env.start_bl    = get_irg_start_block(irg);
1371
1372         assure_doms(irg);
1373         assure_irg_outs(irg);
1374
1375         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
1376
1377         /* first step: allocate block entries: produces an
1378            inverse post-order list for the CFG */
1379         irg_out_block_walk(get_irg_start_block(irg), NULL, prepare_blocks, NULL);
1380
1381         /* second step: find and sort all memory ops */
1382         walk_memory_irg(irg, collect_memops, NULL, NULL);
1383
1384         /* create the backward links */
1385         irg_block_walk_graph(irg, NULL, collect_backward, NULL);
1386
1387         /* check that we really start with the start / end block */
1388         assert(env.forward->block  == env.start_bl);
1389         assert(env.backward->block == get_irg_end_block(irg));
1390
1391         /* create address sets: we know that 2 * n_mem_ops - 1 is an upper bound for all possible addresses */
1392         env.rbs_size = 2 * env.n_mem_ops;
1393
1394         /* create the current set */
1395         env.curr_set = rbitset_obstack_alloc(&env.obst, env.rbs_size);
1396         rbitset_set(env.curr_set, env.rbs_size - 1);
1397
1398         for (bl = env.forward; bl != NULL; bl = bl->forward_next) {
1399                 /* set sentinel bits */
1400                 bl->avail_out  = rbitset_obstack_alloc(&env.obst, env.rbs_size);
1401                 rbitset_set(bl->avail_out, env.rbs_size - 1);
1402
1403                 bl->id_2_memop_avail = NEW_ARR_D(memop_t *, &env.obst, env.rbs_size);
1404                 memset(bl->id_2_memop_avail, 0, env.rbs_size * sizeof(bl->id_2_memop[0]));
1405
1406                 bl->anticL_in  = rbitset_obstack_alloc(&env.obst, env.rbs_size);
1407                 rbitset_set(bl->anticL_in, env.rbs_size - 1);
1408
1409                 bl->id_2_memop = NEW_ARR_D(memop_t *, &env.obst, env.rbs_size);
1410                 memset(bl->id_2_memop, 0, env.rbs_size * sizeof(bl->id_2_memop[0]));
1411         }
1412
1413 //      dump_block_list(&env);
1414
1415         calcAvail();
1416         calcAntic();
1417
1418         insert_Loads_upwards();
1419
1420         if (env.changed) {
1421                 /* over all blocks in reverse post order */
1422                 for (bl = env.forward; bl != NULL; bl = bl->forward_next) {
1423                         do_replacements(bl);
1424                 }
1425
1426                 set_irg_outs_inconsistent(irg);
1427                 set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
1428         }
1429
1430         ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
1431         ir_nodemap_destroy(&env.adr_map);
1432         obstack_free(&env.obst, NULL);
1433
1434         current_ir_graph = rem;
1435
1436         return env.changed != 0;
1437 }