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