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