nsz Git - libfirm/blob - ir/be/ia32/ia32_optimize.c

   1 /**
   2  * Project:     libFIRM
   3  * File name:   ir/be/ia32/ia32_optimize.c
   4  * Purpose:     Implements several optimizations for IA32
   5  * Author:      Christian Wuerdig
   6  * CVS-ID:      $Id$
   7  * Copyright:   (c) 2006 Universitaet Karlsruhe
   8  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   9  */
  10 #ifdef HAVE_CONFIG_H
  11 #include <config.h>
  12 #endif
  13
  14 #include "irnode.h"
  15 #include "irprog_t.h"
  16 #include "ircons.h"
  17 #include "firm_types.h"
  18 #include "iredges.h"
  19 #include "tv.h"
  20 #include "irgmod.h"
  21 #include "irgwalk.h"
  22 #include "height.h"
  23 #include "irbitset.h"
  24
  25 #include "../be_t.h"
  26 #include "../beabi.h"
  27 #include "../benode_t.h"
  28 #include "../besched_t.h"
  29
  30 #include "ia32_new_nodes.h"
  31 #include "bearch_ia32_t.h"
  32 #include "gen_ia32_regalloc_if.h"     /* the generated interface (register type and class defenitions) */
  33 #include "ia32_transform.h"
  34 #include "ia32_dbg_stat.h"
  35 #include "ia32_util.h"
  36
  37 #define AGGRESSIVE_AM
  38
  39 typedef enum {
  40         IA32_AM_CAND_NONE  = 0,  /**< no addressmode possible with irn inputs */
  41         IA32_AM_CAND_LEFT  = 1,  /**< addressmode possible with left input */
  42         IA32_AM_CAND_RIGHT = 2,  /**< addressmode possible with right input */
  43         IA32_AM_CAND_BOTH  = 3   /**< addressmode possible with both inputs */
  44 } ia32_am_cand_t;
  45
  46 typedef int is_op_func_t(const ir_node *n);
  47 typedef ir_node *load_func_t(dbg_info *db, ir_graph *irg, ir_node *block, ir_node *base, ir_node *index, ir_node *mem);
  48
  49 /**
  50  * checks if a node represents the NOREG value
  51  */
  52 static INLINE int be_is_NoReg(ia32_code_gen_t *cg, const ir_node *irn) {
  53         return irn == cg->noreg_gp || irn == cg->noreg_xmm || irn == cg->noreg_vfp;
  54 }
  55
  56 void ia32_pre_transform_phase(ia32_code_gen_t *cg) {
  57         /*
  58                 We need to transform the consts twice:
  59                 - the psi condition tree transformer needs existing constants to be ia32 constants
  60                 - the psi condition tree transformer inserts new firm constants which need to be transformed
  61         */
  62         //ia32_transform_all_firm_consts(cg);
  63         irg_walk_graph(cg->irg, NULL, ia32_transform_psi_cond_tree, cg);
  64         //ia32_transform_all_firm_consts(cg);
  65 }
  66
  67 /********************************************************************************************************
  68  *  _____                _           _         ____        _   _           _          _   _
  69  * |  __ \              | |         | |       / __ \      | | (_)         (_)        | | (_)
  70  * | |__) |__  ___ _ __ | |__   ___ | | ___  | |  | |_ __ | |_ _ _ __ ___  _ ______ _| |_ _  ___  _ __
  71  * |  ___/ _ \/ _ \ '_ \| '_ \ / _ \| |/ _ \ | |  | | '_ \| __| | '_ ` _ \| |_  / _` | __| |/ _ \| '_ \
  72  * | |  |  __/  __/ |_) | | | | (_) | |  __/ | |__| | |_) | |_| | | | | | | |/ / (_| | |_| | (_) | | | |
  73  * |_|   \___|\___| .__/|_| |_|\___/|_|\___|  \____/| .__/ \__|_|_| |_| |_|_/___\__,_|\__|_|\___/|_| |_|
  74  *                | |                               | |
  75  *                |_|                               |_|
  76  ********************************************************************************************************/
  77
  78 /**
  79  * NOTE: THESE PEEPHOLE OPTIMIZATIONS MUST BE CALLED AFTER SCHEDULING AND REGISTER ALLOCATION.
  80  */
  81
  82 static int ia32_const_equal(const ir_node *n1, const ir_node *n2) {
  83         if(get_ia32_immop_type(n1) != get_ia32_immop_type(n2))
  84                 return 0;
  85
  86         if(get_ia32_immop_type(n1) == ia32_ImmConst) {
  87                 return get_ia32_Immop_tarval(n1) == get_ia32_Immop_tarval(n2);
  88         } else if(get_ia32_immop_type(n1) == ia32_ImmSymConst) {
  89                 return get_ia32_Immop_symconst(n1) == get_ia32_Immop_symconst(n2);
  90         }
  91
  92         assert(get_ia32_immop_type(n1) == ia32_ImmNone);
  93         return 1;
  94 }
  95
  96 /**
  97  * Checks for potential CJmp/CJmpAM optimization candidates.
  98  */
  99 static ir_node *ia32_determine_cjmp_cand(ir_node *irn, is_op_func_t *is_op_func) {
 100         ir_node *cand = NULL;
 101         ir_node *prev = sched_prev(irn);
 102
 103         if (is_Block(prev)) {
 104                 if (get_Block_n_cfgpreds(prev) == 1)
 105                         prev = get_Block_cfgpred(prev, 0);
 106                 else
 107                         prev = NULL;
 108         }
 109
 110         /* The predecessor must be a ProjX. */
 111         if (prev && is_Proj(prev) && get_irn_mode(prev) == mode_X) {
 112                 prev = get_Proj_pred(prev);
 113
 114                 if (is_op_func(prev))
 115                         cand = prev;
 116         }
 117
 118         return cand;
 119 }
 120
 121 static int is_TestJmp_cand(const ir_node *irn) {
 122         return is_ia32_TestJmp(irn) || is_ia32_And(irn);
 123 }
 124
 125 /**
 126  * Checks if two consecutive arguments of cand matches
 127  * the two arguments of irn (TestJmp).
 128  */
 129 static int is_TestJmp_replacement(ir_node *cand, ir_node *irn) {
 130         ir_node *in1       = get_irn_n(irn, 0);
 131         ir_node *in2       = get_irn_n(irn, 1);
 132         int      i, n      = get_irn_arity(cand);
 133         int      same_args = 0;
 134
 135         for (i = 0; i < n - 1; i++) {
 136                 if (get_irn_n(cand, i)     == in1 &&
 137                         get_irn_n(cand, i + 1) == in2)
 138                 {
 139                         same_args = 1;
 140                         break;
 141                 }
 142         }
 143
 144         if (!same_args)
 145                 return 0;
 146
 147         return ia32_const_equal(cand, irn);
 148 }
 149
 150 /**
 151  * Tries to replace a TestJmp by a CJmp or CJmpAM (in case of And)
 152  */
 153 static void ia32_optimize_TestJmp(ir_node *irn, ia32_code_gen_t *cg) {
 154         ir_node *cand    = ia32_determine_cjmp_cand(irn, is_TestJmp_cand);
 155         int      replace = 0;
 156
 157         /* we found a possible candidate */
 158         replace = cand ? is_TestJmp_replacement(cand, irn) : 0;
 159
 160         if (replace) {
 161                 DBG((cg->mod, LEVEL_1, "replacing %+F by ", irn));
 162
 163                 if (is_ia32_And(cand))
 164                         set_irn_op(irn, op_ia32_CJmpAM);
 165                 else
 166                         set_irn_op(irn, op_ia32_CJmp);
 167
 168                 DB((cg->mod, LEVEL_1, "%+F\n", irn));
 169         }
 170 }
 171
 172 static int is_CondJmp_cand(const ir_node *irn) {
 173         return is_ia32_CondJmp(irn) || is_ia32_Sub(irn);
 174 }
 175
 176 /**
 177  * Checks if the arguments of cand are the same of irn.
 178  */
 179 static int is_CondJmp_replacement(ir_node *cand, ir_node *irn) {
 180         int i, arity;
 181
 182         arity = get_irn_arity(cand);
 183         for (i = 0; i < arity; i++) {
 184                 if (get_irn_n(cand, i) != get_irn_n(irn, i)) {
 185                         return 0;
 186                 }
 187         }
 188
 189         return ia32_const_equal(cand, irn);
 190 }
 191
 192 /**
 193  * Tries to replace a CondJmp by a CJmpAM
 194  */
 195 static void ia32_optimize_CondJmp(ir_node *irn, ia32_code_gen_t *cg) {
 196         ir_node *cand    = ia32_determine_cjmp_cand(irn, is_CondJmp_cand);
 197         int      replace = 0;
 198
 199         /* we found a possible candidate */
 200         replace = cand ? is_CondJmp_replacement(cand, irn) : 0;
 201
 202         if (replace) {
 203                 DBG((cg->mod, LEVEL_1, "replacing %+F by ", irn));
 204                 DBG_OPT_CJMP(irn);
 205
 206                 set_irn_op(irn, op_ia32_CJmpAM);
 207
 208                 DB((cg->mod, LEVEL_1, "%+F\n", irn));
 209         }
 210 }
 211
 212 // only optimize up to 48 stores behind IncSPs
 213 #define MAXPUSH_OPTIMIZE        48
 214
 215 /**
 216  * Tries to create pushs from IncSP,Store combinations
 217  */
 218 static void ia32_create_Pushs(ir_node *irn, ia32_code_gen_t *cg) {
 219         int i;
 220         int offset;
 221         ir_node *node;
 222         ir_node *stores[MAXPUSH_OPTIMIZE];
 223         ir_node *block = get_nodes_block(irn);
 224         ir_graph *irg = cg->irg;
 225         ir_node *curr_sp;
 226         ir_mode *spmode = get_irn_mode(irn);
 227
 228         memset(stores, 0, sizeof(stores));
 229
 230         assert(be_is_IncSP(irn));
 231
 232         offset = be_get_IncSP_offset(irn);
 233         if(offset < 4)
 234                 return;
 235
 236         /*
 237          * We first walk the schedule after the IncSP node as long as we find
 238          * suitable stores that could be transformed to a push.
 239          * We save them into the stores array which is sorted by the frame offset/4
 240          * attached to the node
 241          */
 242         for(node = sched_next(irn); !sched_is_end(node); node = sched_next(node)) {
 243                 ir_node *mem;
 244                 int offset;
 245                 int storeslot;
 246
 247                 // it has to be a store
 248                 if(!is_ia32_Store(node))
 249                         break;
 250
 251                 // it has to use our sp value
 252                 if(get_irn_n(node, 0) != irn)
 253                         continue;
 254                 // store has to be attached to NoMem
 255                 mem = get_irn_n(node, 3);
 256                 if(!is_NoMem(mem)) {
 257                         continue;
 258                 }
 259
 260                 if( (get_ia32_am_flavour(node) & ia32_am_IS) != 0)
 261                         break;
 262
 263                 offset = get_ia32_am_offs_int(node);
 264
 265                 storeslot = offset / 4;
 266                 if(storeslot >= MAXPUSH_OPTIMIZE)
 267                         continue;
 268
 269                 // storing into the same slot twice is bad (and shouldn't happen...)
 270                 if(stores[storeslot] != NULL)
 271                         break;
 272
 273                 // storing at half-slots is bad
 274                 if(offset % 4 != 0)
 275                         break;
 276
 277                 stores[storeslot] = node;
 278         }
 279
 280         curr_sp = get_irn_n(irn, 0);
 281
 282         // walk the stores in inverse order and create pushs for them
 283         i = (offset / 4) - 1;
 284         if(i >= MAXPUSH_OPTIMIZE) {
 285                 i = MAXPUSH_OPTIMIZE - 1;
 286         }
 287
 288         for( ; i >= 0; --i) {
 289                 const arch_register_t *spreg;
 290                 ir_node *push;
 291                 ir_node *val, *mem, *mem_proj;
 292                 ir_node *store = stores[i];
 293                 ir_node *noreg = ia32_new_NoReg_gp(cg);
 294
 295                 if(store == NULL || is_Bad(store))
 296                         break;
 297
 298                 val = get_irn_n(store, 2);
 299                 mem = get_irn_n(store, 3);
 300                 spreg = arch_get_irn_register(cg->arch_env, curr_sp);
 301
 302                 // create a push
 303                 push = new_rd_ia32_Push(NULL, irg, block, noreg, noreg, val, curr_sp, mem);
 304
 305                 set_ia32_am_support(push, ia32_am_Source);
 306                 copy_ia32_Immop_attr(push, store);
 307
 308                 sched_add_before(irn, push);
 309
 310                 // create stackpointer proj
 311                 curr_sp = new_r_Proj(irg, block, push, spmode, pn_ia32_Push_stack);
 312                 arch_set_irn_register(cg->arch_env, curr_sp, spreg);
 313                 sched_add_before(irn, curr_sp);
 314
 315                 // create memory proj
 316                 mem_proj = new_r_Proj(irg, block, push, mode_M, pn_ia32_Push_M);
 317                 sched_add_before(irn, mem_proj);
 318
 319                 // use the memproj now
 320                 exchange(store, mem_proj);
 321
 322                 // we can remove the store now
 323                 sched_remove(store);
 324
 325                 offset -= 4;
 326         }
 327
 328         be_set_IncSP_offset(irn, offset);
 329
 330         // can we remove the IncSP now?
 331         if(offset == 0) {
 332                 const ir_edge_t *edge, *next;
 333
 334                 foreach_out_edge_safe(irn, edge, next) {
 335                         ir_node *arg = get_edge_src_irn(edge);
 336                         int pos = get_edge_src_pos(edge);
 337
 338                         set_irn_n(arg, pos, curr_sp);
 339                 }
 340
 341                 set_irn_n(irn, 0, new_Bad());
 342                 sched_remove(irn);
 343         } else {
 344                 set_irn_n(irn, 0, curr_sp);
 345         }
 346 }
 347
 348 #if 0
 349 /**
 350  * Tries to optimize two following IncSP.
 351  */
 352 static void ia32_optimize_IncSP(ir_node *irn, ia32_code_gen_t *cg) {
 353         ir_node *prev = be_get_IncSP_pred(irn);
 354         int real_uses = get_irn_n_edges(prev);
 355
 356         if (be_is_IncSP(prev) && real_uses == 1) {
 357                 /* first IncSP has only one IncSP user, kill the first one */
 358                 int prev_offs = be_get_IncSP_offset(prev);
 359                 int curr_offs = be_get_IncSP_offset(irn);
 360
 361                 be_set_IncSP_offset(prev, prev_offs + curr_offs);
 362
 363                 /* Omit the optimized IncSP */
 364                 be_set_IncSP_pred(irn, be_get_IncSP_pred(prev));
 365
 366                 set_irn_n(prev, 0, new_Bad());
 367                 sched_remove(prev);
 368         }
 369 }
 370 #endif
 371
 372 /**
 373  * Performs Peephole Optimizations.
 374  */
 375 static void ia32_peephole_optimize_node(ir_node *irn, void *env) {
 376         ia32_code_gen_t *cg = env;
 377
 378         /* AMD CPUs want explicit compare before conditional jump  */
 379         if (! ARCH_AMD(cg->opt_arch)) {
 380                 if (is_ia32_TestJmp(irn))
 381                         ia32_optimize_TestJmp(irn, cg);
 382                 else if (is_ia32_CondJmp(irn))
 383                         ia32_optimize_CondJmp(irn, cg);
 384         }
 385
 386         if (be_is_IncSP(irn)) {
 387                 // optimize_IncSP doesn't respect dependency edges yet...
 388                 //ia32_optimize_IncSP(irn, cg);
 389
 390                 if (cg->opt & IA32_OPT_PUSHARGS)
 391                         ia32_create_Pushs(irn, cg);
 392         }
 393 }
 394
 395 void ia32_peephole_optimization(ir_graph *irg, ia32_code_gen_t *cg) {
 396         irg_walk_graph(irg, ia32_peephole_optimize_node, NULL, cg);
 397 }
 398
 399 /******************************************************************
 400  *              _     _                   __  __           _
 401  *     /\      | |   | |                 |  \/  |         | |
 402  *    /  \   __| | __| |_ __ ___  ___ ___| \  / | ___   __| | ___
 403  *   / /\ \ / _` |/ _` | '__/ _ \/ __/ __| |\/| |/ _ \ / _` |/ _ \
 404  *  / ____ \ (_| | (_| | | |  __/\__ \__ \ |  | | (_) | (_| |  __/
 405  * /_/    \_\__,_|\__,_|_|  \___||___/___/_|  |_|\___/ \__,_|\___|
 406  *
 407  ******************************************************************/
 408
 409 typedef struct {
 410         ia32_code_gen_t *cg;
 411         heights_t       *h;
 412 } ia32_am_opt_env_t;
 413
 414 static int node_is_ia32_comm(const ir_node *irn) {
 415         return is_ia32_irn(irn) ? is_ia32_commutative(irn) : 0;
 416 }
 417
 418 static int ia32_get_irn_n_edges(const ir_node *irn) {
 419         const ir_edge_t *edge;
 420         int cnt = 0;
 421
 422         foreach_out_edge(irn, edge) {
 423                 cnt++;
 424         }
 425
 426         return cnt;
 427 }
 428
 429 /**
 430  * Determines if pred is a Proj and if is_op_func returns true for it's predecessor.
 431  *
 432  * @param pred       The node to be checked
 433  * @param is_op_func The check-function
 434  * @return 1 if conditions are fulfilled, 0 otherwise
 435  */
 436 static int pred_is_specific_node(const ir_node *pred, is_op_func_t *is_op_func) {
 437         return is_op_func(pred);
 438 }
 439
 440 /**
 441  * Determines if pred is a Proj and if is_op_func returns true for it's predecessor
 442  * and if the predecessor is in block bl.
 443  *
 444  * @param bl         The block
 445  * @param pred       The node to be checked
 446  * @param is_op_func The check-function
 447  * @return 1 if conditions are fulfilled, 0 otherwise
 448  */
 449 static int pred_is_specific_nodeblock(const ir_node *bl, const ir_node *pred,
 450         int (*is_op_func)(const ir_node *n))
 451 {
 452         if (is_Proj(pred)) {
 453                 pred = get_Proj_pred(pred);
 454                 if ((bl == get_nodes_block(pred)) && is_op_func(pred)) {
 455                         return 1;
 456                 }
 457         }
 458
 459         return 0;
 460 }
 461
 462 /**
 463  * Checks if irn is a candidate for address calculation. We avoid transforming
 464  * adds to leas if they have a load as pred, because then we can use AM mode
 465  * for the add later.
 466  *
 467  * - none of the operand must be a Load  within the same block OR
 468  * - all Loads must have more than one user                    OR
 469  *
 470  * @param block   The block the Loads must/mustnot be in
 471  * @param irn     The irn to check
 472  * return 1 if irn is a candidate, 0 otherwise
 473  */
 474 static int is_addr_candidate(const ir_node *irn) {
 475 #ifndef AGGRESSIVE_AM
 476         const ir_node *block = get_nodes_block(irn);
 477         ir_node *left, *right;
 478         int      n;
 479
 480         left  = get_irn_n(irn, 2);
 481         right = get_irn_n(irn, 3);
 482
 483         if (pred_is_specific_nodeblock(block, left, is_ia32_Ld)) {
 484                 n         = ia32_get_irn_n_edges(left);
 485                 /* load with only one user: don't create LEA */
 486                 if(n == 1)
 487                         return 0;
 488         }
 489
 490         if (pred_is_specific_nodeblock(block, right, is_ia32_Ld)) {
 491                 n         = ia32_get_irn_n_edges(right);
 492                 if(n == 1)
 493                         return 0;
 494         }
 495 #endif
 496
 497         return 1;
 498 }
 499
 500 /**
 501  * Checks if irn is a candidate for address mode.
 502  *
 503  * address mode (AM):
 504  * - at least one operand has to be a Load within the same block AND
 505  * - the load must not have other users than the irn             AND
 506  * - the irn must not have a frame entity set
 507  *
 508  * @param cg          The ia32 code generator
 509  * @param h           The height information of the irg
 510  * @param block       The block the Loads must/mustnot be in
 511  * @param irn         The irn to check
 512  * return 0 if irn is no candidate, 1 if left load can be used, 2 if right one, 3 for both
 513  */
 514 static ia32_am_cand_t is_am_candidate(ia32_code_gen_t *cg, heights_t *h, const ir_node *block, ir_node *irn) {
 515         ir_node *in, *load, *other, *left, *right;
 516         int      is_cand = 0, cand;
 517         int arity;
 518
 519         if (is_ia32_Ld(irn) || is_ia32_St(irn) || is_ia32_Store8Bit(irn) || is_ia32_vfild(irn) || is_ia32_vfist(irn) ||
 520                 is_ia32_GetST0(irn) || is_ia32_SetST0(irn) || is_ia32_xStoreSimple(irn))
 521                 return 0;
 522
 523         left  = get_irn_n(irn, 2);
 524         arity = get_irn_arity(irn);
 525         assert(arity == 5 || arity == 4);
 526         if(arity == 5) {
 527                 /* binary op */
 528                 right = get_irn_n(irn, 3);
 529         } else {
 530                 /* unary op */
 531                 right = left;
 532         }
 533
 534         in = left;
 535
 536         if (pred_is_specific_nodeblock(block, in, is_ia32_Ld)) {
 537 #ifndef AGGRESSIVE_AM
 538                 int n;
 539                 n         = ia32_get_irn_n_edges(in);
 540                 is_cand   = (n == 1) ? 1 : is_cand;  /* load with more than one user: no AM */
 541 #else
 542                 is_cand   = 1;
 543 #endif
 544
 545                 load  = get_Proj_pred(in);
 546                 other = right;
 547
 548                 /* 8bit Loads are not supported (for binary ops),
 549                  * they cannot be used with every register */
 550                 if (get_irn_arity(irn) != 4 && get_mode_size_bits(get_ia32_ls_mode(load)) < 16) {
 551                         assert(get_irn_arity(irn) == 5);
 552                         is_cand = 0;
 553                 }
 554
 555                 /* If there is a data dependency of other irn from load: cannot use AM */
 556                 if (is_cand && get_nodes_block(other) == block) {
 557                         other   = skip_Proj(other);
 558                         is_cand = heights_reachable_in_block(h, other, load) ? 0 : is_cand;
 559                         /* this could happen in loops */
 560                         is_cand = heights_reachable_in_block(h, load, irn) ? 0 : is_cand;
 561                 }
 562         }
 563
 564         cand    = is_cand ? IA32_AM_CAND_LEFT : IA32_AM_CAND_NONE;
 565         in      = right;
 566         is_cand = 0;
 567
 568         if (pred_is_specific_nodeblock(block, in, is_ia32_Ld)) {
 569 #ifndef AGGRESSIVE_AM
 570                 int n;
 571                 n         = ia32_get_irn_n_edges(in);
 572                 is_cand   = (n == 1) ? 1 : is_cand;  /* load with more than one user: no AM */
 573 #else
 574                 is_cand = 1;
 575 #endif
 576
 577                 load  = get_Proj_pred(in);
 578                 other = left;
 579
 580                 /* 8bit Loads are not supported, they cannot be used with every register */
 581                 if (get_mode_size_bits(get_ia32_ls_mode(load)) < 16)
 582                         is_cand = 0;
 583
 584                 /* If there is a data dependency of other irn from load: cannot use load */
 585                 if (is_cand && get_nodes_block(other) == block) {
 586                         other   = skip_Proj(other);
 587                         is_cand = heights_reachable_in_block(h, other, load) ? 0 : is_cand;
 588                         /* this could happen in loops */
 589                         is_cand = heights_reachable_in_block(h, load, irn) ? 0 : is_cand;
 590                 }
 591         }
 592
 593         cand = is_cand ? (cand | IA32_AM_CAND_RIGHT) : cand;
 594
 595         /* if the irn has a frame entity: we do not use address mode */
 596         return get_ia32_frame_ent(irn) ? IA32_AM_CAND_NONE : cand;
 597 }
 598
 599 /**
 600  * Compares the base and index addr and the load/store entities
 601  * and returns 1 if they are equal.
 602  */
 603 static int load_store_addr_is_equal(const ir_node *load, const ir_node *store,
 604                                                                         const ir_node *addr_b, const ir_node *addr_i)
 605 {
 606         if(get_irn_n(load, 0) != addr_b)
 607                 return 0;
 608         if(get_irn_n(load, 1) != addr_i)
 609                 return 0;
 610
 611         if(get_ia32_frame_ent(load) != get_ia32_frame_ent(store))
 612                 return 0;
 613
 614         if(get_ia32_am_sc(load) != get_ia32_am_sc(store))
 615                 return 0;
 616         if(is_ia32_am_sc_sign(load) != is_ia32_am_sc_sign(store))
 617                 return 0;
 618         if(get_ia32_am_offs_int(load) != get_ia32_am_offs_int(store))
 619                 return 0;
 620         if(get_ia32_ls_mode(load) != get_ia32_ls_mode(store))
 621                 return 0;
 622
 623         return 1;
 624 }
 625
 626 typedef enum _ia32_take_lea_attr {
 627         IA32_LEA_ATTR_NONE  = 0,
 628         IA32_LEA_ATTR_BASE  = (1 << 0),
 629         IA32_LEA_ATTR_INDEX = (1 << 1),
 630         IA32_LEA_ATTR_OFFS  = (1 << 2),
 631         IA32_LEA_ATTR_SCALE = (1 << 3),
 632         IA32_LEA_ATTR_AMSC  = (1 << 4),
 633         IA32_LEA_ATTR_FENT  = (1 << 5)
 634 } ia32_take_lea_attr;
 635
 636 /**
 637  * Decides if we have to keep the LEA operand or if we can assimilate it.
 638  */
 639 static int do_new_lea(ir_node *irn, ir_node *base, ir_node *index, ir_node *lea,
 640                 int have_am_sc, ia32_code_gen_t *cg)
 641 {
 642         ir_entity *irn_ent  = get_ia32_frame_ent(irn);
 643         ir_entity *lea_ent  = get_ia32_frame_ent(lea);
 644         int        ret_val  = 0;
 645         int        is_noreg_base  = be_is_NoReg(cg, base);
 646         int        is_noreg_index = be_is_NoReg(cg, index);
 647         ia32_am_flavour_t am_flav = get_ia32_am_flavour(lea);
 648
 649         /* If the Add and the LEA both have a different frame entity set: keep */
 650         if (irn_ent && lea_ent && (irn_ent != lea_ent))
 651                 return IA32_LEA_ATTR_NONE;
 652         else if (! irn_ent && lea_ent)
 653                 ret_val |= IA32_LEA_ATTR_FENT;
 654
 655         /* If the Add and the LEA both have already an address mode symconst: keep */
 656         if (have_am_sc && get_ia32_am_sc(lea))
 657                 return IA32_LEA_ATTR_NONE;
 658         else if (get_ia32_am_sc(lea))
 659                 ret_val |= IA32_LEA_ATTR_AMSC;
 660
 661         /* Check the different base-index combinations */
 662
 663         if (! is_noreg_base && ! is_noreg_index) {
 664                 /* Assimilate if base is the lea and the LEA is just a Base + Offset calculation */
 665                 if ((base == lea) && ! (am_flav & ia32_I ? 1 : 0)) {
 666                         if (am_flav & ia32_O)
 667                                 ret_val |= IA32_LEA_ATTR_OFFS;
 668
 669                         ret_val |= IA32_LEA_ATTR_BASE;
 670                 }
 671                 else
 672                         return IA32_LEA_ATTR_NONE;
 673         }
 674         else if (! is_noreg_base && is_noreg_index) {
 675                 /* Base is set but index not */
 676                 if (base == lea) {
 677                         /* Base points to LEA: assimilate everything */
 678                         if (am_flav & ia32_O)
 679                                 ret_val |= IA32_LEA_ATTR_OFFS;
 680                         if (am_flav & ia32_S)
 681                                 ret_val |= IA32_LEA_ATTR_SCALE;
 682                         if (am_flav & ia32_I)
 683                                 ret_val |= IA32_LEA_ATTR_INDEX;
 684
 685                         ret_val |= IA32_LEA_ATTR_BASE;
 686                 }
 687                 else if (am_flav & ia32_B ? 0 : 1) {
 688                         /* Base is not the LEA but the LEA is an index only calculation: assimilate */
 689                         if (am_flav & ia32_O)
 690                                 ret_val |= IA32_LEA_ATTR_OFFS;
 691                         if (am_flav & ia32_S)
 692                                 ret_val |= IA32_LEA_ATTR_SCALE;
 693
 694                         ret_val |= IA32_LEA_ATTR_INDEX;
 695                 }
 696                 else
 697                         return IA32_LEA_ATTR_NONE;
 698         }
 699         else if (is_noreg_base && ! is_noreg_index) {
 700                 /* Index is set but not base */
 701                 if (index == lea) {
 702                         /* Index points to LEA: assimilate everything */
 703                         if (am_flav & ia32_O)
 704                                 ret_val |= IA32_LEA_ATTR_OFFS;
 705                         if (am_flav & ia32_S)
 706                                 ret_val |= IA32_LEA_ATTR_SCALE;
 707                         if (am_flav & ia32_B)
 708                                 ret_val |= IA32_LEA_ATTR_BASE;
 709
 710                         ret_val |= IA32_LEA_ATTR_INDEX;
 711                 }
 712                 else if (am_flav & ia32_I ? 0 : 1) {
 713                         /* Index is not the LEA but the LEA is a base only calculation: assimilate */
 714                         if (am_flav & ia32_O)
 715                                 ret_val |= IA32_LEA_ATTR_OFFS;
 716                         if (am_flav & ia32_S)
 717                                 ret_val |= IA32_LEA_ATTR_SCALE;
 718
 719                         ret_val |= IA32_LEA_ATTR_BASE;
 720                 }
 721                 else
 722                         return IA32_LEA_ATTR_NONE;
 723         }
 724         else {
 725                 assert(0 && "There must have been set base or index");
 726         }
 727
 728         return ret_val;
 729 }
 730
 731 /**
 732  * Adds res before irn into schedule if irn was scheduled.
 733  * @param irn  The schedule point
 734  * @param res  The node to be scheduled
 735  */
 736 static INLINE void try_add_to_sched(ir_node *irn, ir_node *res) {
 737         if (sched_is_scheduled(irn))
 738                 sched_add_before(irn, res);
 739 }
 740
 741 /**
 742  * Removes node from schedule if it is not used anymore. If irn is a mode_T node
 743  * all it's Projs are removed as well.
 744  * @param irn  The irn to be removed from schedule
 745  */
 746 static INLINE void try_remove_from_sched(ir_node *node) {
 747         int i, arity;
 748
 749         if(get_irn_mode(node) == mode_T) {
 750                 const ir_edge_t *edge;
 751                 foreach_out_edge(node, edge) {
 752                         ir_node *proj = get_edge_src_irn(edge);
 753                         try_remove_from_sched(proj);
 754                 }
 755         }
 756
 757         if(get_irn_n_edges(node) != 0)
 758                 return;
 759
 760         if (sched_is_scheduled(node)) {
 761                 sched_remove(node);
 762         }
 763
 764         arity = get_irn_arity(node);
 765         for(i = 0; i < arity; ++i) {
 766                 set_irn_n(node, i, new_Bad());
 767         }
 768 }
 769
 770 /**
 771  * Folds Add or Sub to LEA if possible
 772  */
 773 static ir_node *fold_addr(ia32_code_gen_t *cg, ir_node *irn) {
 774         ir_graph   *irg        = get_irn_irg(irn);
 775         dbg_info   *dbg        = get_irn_dbg_info(irn);
 776         ir_node    *block      = get_nodes_block(irn);
 777         ir_node    *res        = irn;
 778         ir_node    *shift      = NULL;
 779         ir_node    *lea_o      = NULL;
 780         ir_node    *lea        = NULL;
 781         long        offs       = 0;
 782         long        offs_cnst  = 0;
 783         long        offs_lea   = 0;
 784         int         scale      = 0;
 785         int         isadd      = 0;
 786         int         dolea      = 0;
 787         int         have_am_sc = 0;
 788         int         am_sc_sign = 0;
 789         ident      *am_sc      = NULL;
 790         ir_entity  *lea_ent    = NULL;
 791         ir_node    *noreg      = ia32_new_NoReg_gp(cg);
 792         ir_node    *left, *right, *temp;
 793         ir_node    *base, *index;
 794         int consumed_left_shift;
 795         ia32_am_flavour_t am_flav;
 796         DEBUG_ONLY(firm_dbg_module_t *mod = cg->mod;)
 797
 798         if (is_ia32_Add(irn))
 799                 isadd = 1;
 800
 801         left  = get_irn_n(irn, 2);
 802         right = get_irn_n(irn, 3);
 803
 804         /* "normalize" arguments in case of add with two operands */
 805         if  (isadd && ! be_is_NoReg(cg, right)) {
 806                 /* put LEA == ia32_am_O as right operand */
 807                 if (is_ia32_Lea(left) && get_ia32_am_flavour(left) == ia32_am_O) {
 808                         set_irn_n(irn, 2, right);
 809                         set_irn_n(irn, 3, left);
 810                         temp  = left;
 811                         left  = right;
 812                         right = temp;
 813                 }
 814
 815                 /* put LEA != ia32_am_O as left operand */
 816                 if (is_ia32_Lea(right) && get_ia32_am_flavour(right) != ia32_am_O) {
 817                         set_irn_n(irn, 2, right);
 818                         set_irn_n(irn, 3, left);
 819                         temp  = left;
 820                         left  = right;
 821                         right = temp;
 822                 }
 823
 824                 /* put SHL as left operand iff left is NOT a LEA */
 825                 if (! is_ia32_Lea(left) && pred_is_specific_node(right, is_ia32_Shl)) {
 826                         set_irn_n(irn, 2, right);
 827                         set_irn_n(irn, 3, left);
 828                         temp  = left;
 829                         left  = right;
 830                         right = temp;
 831                 }
 832         }
 833
 834         base    = left;
 835         index   = noreg;
 836         offs    = 0;
 837         scale   = 0;
 838         am_flav = 0;
 839
 840         /* check for operation with immediate */
 841         if (is_ia32_ImmConst(irn)) {
 842                 tarval *tv = get_ia32_Immop_tarval(irn);
 843
 844                 DBG((mod, LEVEL_1, "\tfound op with imm const"));
 845
 846                 offs_cnst = get_tarval_long(tv);
 847                 dolea     = 1;
 848         }
 849         else if (isadd && is_ia32_ImmSymConst(irn)) {
 850                 DBG((mod, LEVEL_1, "\tfound op with imm symconst"));
 851
 852                 have_am_sc = 1;
 853                 dolea      = 1;
 854                 am_sc      = get_ia32_Immop_symconst(irn);
 855                 am_sc_sign = is_ia32_am_sc_sign(irn);
 856         }
 857
 858         /* determine the operand which needs to be checked */
 859         temp = be_is_NoReg(cg, right) ? left : right;
 860
 861         /* check if right operand is AMConst (LEA with ia32_am_O)  */
 862         /* but we can only eat it up if there is no other symconst */
 863         /* because the linker won't accept two symconsts           */
 864         if (! have_am_sc && is_ia32_Lea(temp) && get_ia32_am_flavour(temp) == ia32_am_O) {
 865                 DBG((mod, LEVEL_1, "\tgot op with LEA am_O"));
 866
 867                 offs_lea   = get_ia32_am_offs_int(temp);
 868                 am_sc      = get_ia32_am_sc(temp);
 869                 am_sc_sign = is_ia32_am_sc_sign(temp);
 870                 have_am_sc = 1;
 871                 dolea      = 1;
 872                 lea_o      = temp;
 873
 874                 if (temp == base)
 875                         base = noreg;
 876                 else if (temp == right)
 877                         right = noreg;
 878         }
 879
 880         if (isadd) {
 881                 /* default for add -> make right operand to index */
 882                 index               = right;
 883                 dolea               = 1;
 884                 consumed_left_shift = -1;
 885
 886                 DBG((mod, LEVEL_1, "\tgot LEA candidate with index %+F\n", index));
 887
 888                 /* determine the operand which needs to be checked */
 889                 temp = left;
 890                 if (is_ia32_Lea(left)) {
 891                         temp = right;
 892                         consumed_left_shift = 0;
 893                 }
 894
 895                 /* check for SHL 1,2,3 */
 896                 if (pred_is_specific_node(temp, is_ia32_Shl)) {
 897
 898                         if (is_ia32_ImmConst(temp)) {
 899                                 long shiftval = get_tarval_long(get_ia32_Immop_tarval(temp));
 900
 901                                 if (shiftval <= 3) {
 902                                         index               = get_irn_n(temp, 2);
 903                                         consumed_left_shift = consumed_left_shift < 0 ? 1 : 0;
 904                                         shift = temp;
 905                                         scale = shiftval;
 906
 907                                         DBG((mod, LEVEL_1, "\tgot scaled index %+F\n", index));
 908                                 }
 909                         }
 910                 }
 911
 912                 /* fix base */
 913                 if (! be_is_NoReg(cg, index)) {
 914                         /* if we have index, but left == right -> no base */
 915                         if (left == right) {
 916                                 base = noreg;
 917                         }
 918                         else if (consumed_left_shift == 1) {
 919                                 /* -> base is right operand  */
 920                                 base = (right == lea_o) ? noreg : right;
 921                         }
 922                 }
 923         }
 924
 925         /* Try to assimilate a LEA as left operand */
 926         if (is_ia32_Lea(left) && (get_ia32_am_flavour(left) != ia32_am_O)) {
 927                 /* check if we can assimilate the LEA */
 928                 int take_attr = do_new_lea(irn, base, index, left, have_am_sc, cg);
 929
 930                 if (take_attr == IA32_LEA_ATTR_NONE) {
 931                         DBG((mod, LEVEL_1, "\tleave old LEA, creating new one\n"));
 932                 }
 933                 else {
 934                         DBG((mod, LEVEL_1, "\tgot LEA as left operand ... assimilating\n"));
 935                         lea = left; /* for statistics */
 936
 937                         if (take_attr & IA32_LEA_ATTR_OFFS)
 938                                 offs = get_ia32_am_offs_int(left);
 939
 940                         if (take_attr & IA32_LEA_ATTR_AMSC) {
 941                                 am_sc      = get_ia32_am_sc(left);
 942                                 have_am_sc = 1;
 943                                 am_sc_sign = is_ia32_am_sc_sign(left);
 944                         }
 945
 946                         if (take_attr & IA32_LEA_ATTR_SCALE)
 947                                 scale = get_ia32_am_scale(left);
 948
 949                         if (take_attr & IA32_LEA_ATTR_BASE)
 950                                 base = get_irn_n(left, 0);
 951
 952                         if (take_attr & IA32_LEA_ATTR_INDEX)
 953                                 index = get_irn_n(left, 1);
 954
 955                         if (take_attr & IA32_LEA_ATTR_FENT)
 956                                 lea_ent = get_ia32_frame_ent(left);
 957                 }
 958         }
 959
 960         /* ok, we can create a new LEA */
 961         if (dolea) {
 962                 res = new_rd_ia32_Lea(dbg, irg, block, base, index);
 963
 964                 /* add the old offset of a previous LEA */
 965                 add_ia32_am_offs_int(res, offs);
 966
 967                 /* add the new offset */
 968                 if (isadd) {
 969                         add_ia32_am_offs_int(res, offs_cnst);
 970                         add_ia32_am_offs_int(res, offs_lea);
 971                 } else {
 972                         /* either lea_O-cnst, -cnst or -lea_O  */
 973                         if (offs_cnst != 0) {
 974                                 add_ia32_am_offs_int(res, offs_lea);
 975                                 add_ia32_am_offs_int(res, -offs_cnst);
 976                         } else {
 977                                 add_ia32_am_offs_int(res, offs_lea);
 978                         }
 979                 }
 980
 981                 /* set the address mode symconst */
 982                 if (have_am_sc) {
 983                         set_ia32_am_sc(res, am_sc);
 984                         if (am_sc_sign)
 985                                 set_ia32_am_sc_sign(res);
 986                 }
 987
 988                 /* copy the frame entity (could be set in case of Add */
 989                 /* which was a FrameAddr) */
 990                 if (lea_ent != NULL) {
 991                         set_ia32_frame_ent(res, lea_ent);
 992                         set_ia32_use_frame(res);
 993                 } else {
 994                         set_ia32_frame_ent(res, get_ia32_frame_ent(irn));
 995                         if(is_ia32_use_frame(irn))
 996                                 set_ia32_use_frame(res);
 997                 }
 998
 999                 /* set scale */
1000                 set_ia32_am_scale(res, scale);
1001
1002                 am_flav = ia32_am_N;
1003                 /* determine new am flavour */
1004                 if (offs || offs_cnst || offs_lea || have_am_sc) {
1005                         am_flav |= ia32_O;
1006                 }
1007                 if (! be_is_NoReg(cg, base)) {
1008                         am_flav |= ia32_B;
1009                 }
1010                 if (! be_is_NoReg(cg, index)) {
1011                         am_flav |= ia32_I;
1012                 }
1013                 if (scale > 0) {
1014                         am_flav |= ia32_S;
1015                 }
1016                 set_ia32_am_flavour(res, am_flav);
1017
1018                 set_ia32_op_type(res, ia32_AddrModeS);
1019
1020                 SET_IA32_ORIG_NODE(res, ia32_get_old_node_name(cg, irn));
1021
1022                 DBG((mod, LEVEL_1, "\tLEA [%+F + %+F * %d + %d]\n", base, index, scale, get_ia32_am_offs_int(res)));
1023
1024                 /* we will exchange it, report here before the Proj is created */
1025                 if (shift && lea && lea_o) {
1026                         try_remove_from_sched(shift);
1027                         try_remove_from_sched(lea);
1028                         try_remove_from_sched(lea_o);
1029                         DBG_OPT_LEA4(irn, lea_o, lea, shift, res);
1030                 }
1031                 else if (shift && lea) {
1032                         try_remove_from_sched(shift);
1033                         try_remove_from_sched(lea);
1034                         DBG_OPT_LEA3(irn, lea, shift, res);
1035                 }
1036                 else if (shift && lea_o) {
1037                         try_remove_from_sched(shift);
1038                         try_remove_from_sched(lea_o);
1039                         DBG_OPT_LEA3(irn, lea_o, shift, res);
1040                 }
1041                 else if (lea && lea_o) {
1042                         try_remove_from_sched(lea);
1043                         try_remove_from_sched(lea_o);
1044                         DBG_OPT_LEA3(irn, lea_o, lea, res);
1045                 }
1046                 else if (shift) {
1047                         try_remove_from_sched(shift);
1048                         DBG_OPT_LEA2(irn, shift, res);
1049                 }
1050                 else if (lea) {
1051                         try_remove_from_sched(lea);
1052                         DBG_OPT_LEA2(irn, lea, res);
1053                 }
1054                 else if (lea_o) {
1055                         try_remove_from_sched(lea_o);
1056                         DBG_OPT_LEA2(irn, lea_o, res);
1057                 }
1058                 else
1059                         DBG_OPT_LEA1(irn, res);
1060
1061                 /* get the result Proj of the Add/Sub */
1062                 try_add_to_sched(irn, res);
1063                 try_remove_from_sched(irn);
1064
1065                 assert(irn && "Couldn't find result proj");
1066
1067                 /* exchange the old op with the new LEA */
1068                 exchange(irn, res);
1069         }
1070
1071         return res;
1072 }
1073
1074
1075 /**
1076  * Merges a Load/Store node with a LEA.
1077  * @param irn The Load/Store node
1078  * @param lea The LEA
1079  */
1080 static void merge_loadstore_lea(ir_node *irn, ir_node *lea) {
1081         ir_entity *irn_ent = get_ia32_frame_ent(irn);
1082         ir_entity *lea_ent = get_ia32_frame_ent(lea);
1083
1084         /* If the irn and the LEA both have a different frame entity set: do not merge */
1085         if (irn_ent != NULL && lea_ent != NULL && (irn_ent != lea_ent))
1086                 return;
1087         else if (irn_ent == NULL && lea_ent != NULL) {
1088                 set_ia32_frame_ent(irn, lea_ent);
1089                 set_ia32_use_frame(irn);
1090         }
1091
1092         /* get the AM attributes from the LEA */
1093         add_ia32_am_offs_int(irn, get_ia32_am_offs_int(lea));
1094         set_ia32_am_scale(irn, get_ia32_am_scale(lea));
1095         set_ia32_am_flavour(irn, get_ia32_am_flavour(lea));
1096
1097         set_ia32_am_sc(irn, get_ia32_am_sc(lea));
1098         if (is_ia32_am_sc_sign(lea))
1099                 set_ia32_am_sc_sign(irn);
1100
1101         set_ia32_op_type(irn, is_ia32_Ld(irn) ? ia32_AddrModeS : ia32_AddrModeD);
1102
1103         /* set base and index */
1104         set_irn_n(irn, 0, get_irn_n(lea, 0));
1105         set_irn_n(irn, 1, get_irn_n(lea, 1));
1106
1107         try_remove_from_sched(lea);
1108
1109         /* clear remat flag */
1110         set_ia32_flags(irn, get_ia32_flags(irn) & ~arch_irn_flags_rematerializable);
1111
1112         if (is_ia32_Ld(irn))
1113                 DBG_OPT_LOAD_LEA(lea, irn);
1114         else
1115                 DBG_OPT_STORE_LEA(lea, irn);
1116
1117 }
1118
1119 /**
1120  * Sets new_right index of irn to right and new_left index to left.
1121  * Also exchange left and right
1122  */
1123 static void exchange_left_right(ir_node *irn, ir_node **left, ir_node **right, int new_left, int new_right) {
1124         ir_node *temp;
1125
1126         set_irn_n(irn, new_right, *right);
1127         set_irn_n(irn, new_left, *left);
1128
1129         temp   = *left;
1130         *left  = *right;
1131         *right = temp;
1132
1133         /* this is only needed for Compares, but currently ALL nodes
1134          * have this attribute :-) */
1135         set_ia32_pncode(irn, get_inversed_pnc(get_ia32_pncode(irn)));
1136 }
1137
1138 /**
1139  * Performs address calculation optimization (create LEAs if possible)
1140  */
1141 static void optimize_lea(ir_node *irn, void *env) {
1142         ia32_code_gen_t *cg  = env;
1143
1144         if (! is_ia32_irn(irn))
1145                 return;
1146
1147         /* Following cases can occur:                                  */
1148         /* - Sub (l, imm) -> LEA [base - offset]                       */
1149         /* - Sub (l, r == LEA with ia32_am_O)   -> LEA [base - offset] */
1150         /* - Add (l, imm) -> LEA [base + offset]                       */
1151         /* - Add (l, r == LEA with ia32_am_O)  -> LEA [base + offset]  */
1152         /* - Add (l == LEA with ia32_am_O, r)  -> LEA [base + offset]  */
1153         /* - Add (l, r) -> LEA [base + index * scale]                  */
1154         /*              with scale > 1 iff l/r == shl (1,2,3)          */
1155         if (is_ia32_Sub(irn) || is_ia32_Add(irn)) {
1156                 ir_node *res;
1157
1158                 if(!is_addr_candidate(irn))
1159                         return;
1160
1161                 DBG((cg->mod, LEVEL_1, "\tfound address calculation candidate %+F ... ", irn));
1162                 res = fold_addr(cg, irn);
1163
1164                 if (res != irn)
1165                         DB((cg->mod, LEVEL_1, "transformed into %+F\n", res));
1166                 else
1167                         DB((cg->mod, LEVEL_1, "not transformed\n"));
1168         } else if (is_ia32_Ld(irn) || is_ia32_St(irn) || is_ia32_Store8Bit(irn)) {
1169                 /* - Load  -> LEA into Load  } TODO: If the LEA is used by more than one Load/Store */
1170                 /* - Store -> LEA into Store }       it might be better to keep the LEA             */
1171                 ir_node *left = get_irn_n(irn, 0);
1172
1173                 if (is_ia32_Lea(left)) {
1174                         const ir_edge_t *edge, *ne;
1175                         ir_node *src;
1176
1177                         /* merge all Loads/Stores connected to this LEA with the LEA */
1178                         foreach_out_edge_safe(left, edge, ne) {
1179                                 src = get_edge_src_irn(edge);
1180
1181                                 if (src && (get_edge_src_pos(edge) == 0) && (is_ia32_Ld(src) || is_ia32_St(src) || is_ia32_Store8Bit(src))) {
1182                                         DBG((cg->mod, LEVEL_1, "\nmerging %+F into %+F\n", left, irn));
1183                                         if (! is_ia32_got_lea(src))
1184                                                 merge_loadstore_lea(src, left);
1185                                         set_ia32_got_lea(src);
1186                                 }
1187                         }
1188                 }
1189         }
1190 }
1191
1192 /**
1193  * Checks for address mode patterns and performs the
1194  * necessary transformations.
1195  * This function is called by a walker.
1196  */
1197 static void optimize_am(ir_node *irn, void *env) {
1198         ia32_am_opt_env_t *am_opt_env = env;
1199         ia32_code_gen_t   *cg         = am_opt_env->cg;
1200         ir_graph          *irg        = get_irn_irg(irn);
1201         heights_t         *h          = am_opt_env->h;
1202         ir_node           *block, *left, *right;
1203         ir_node           *store, *load, *mem_proj;
1204         ir_node           *addr_b, *addr_i;
1205         int               need_exchange_on_fail = 0;
1206         ia32_am_type_t    am_support;
1207         ia32_am_cand_t cand;
1208         ia32_am_cand_t orig_cand;
1209         int               dest_possible;
1210         int               source_possible;
1211         DEBUG_ONLY(firm_dbg_module_t *mod = cg->mod;)
1212
1213         if (!is_ia32_irn(irn) || is_ia32_Ld(irn) || is_ia32_St(irn) || is_ia32_Store8Bit(irn))
1214                 return;
1215         if (is_ia32_Lea(irn))
1216                 return;
1217
1218         am_support = get_ia32_am_support(irn);
1219         block = get_nodes_block(irn);
1220
1221         DBG((mod, LEVEL_1, "checking for AM\n"));
1222
1223         /* fold following patterns:                                                         */
1224         /* - op -> Load into AMop with am_Source                                            */
1225         /*   conditions:                                                                    */
1226         /*     - op is am_Source capable AND                                                */
1227         /*     - the Load is only used by this op AND                                       */
1228         /*     - the Load is in the same block                                              */
1229         /* - Store -> op -> Load  into AMop with am_Dest                                    */
1230         /*   conditions:                                                                    */
1231         /*     - op is am_Dest capable AND                                                  */
1232         /*     - the Store uses the same address as the Load AND                            */
1233         /*     - the Load is only used by this op AND                                       */
1234         /*     - the Load and Store are in the same block AND                               */
1235         /*     - nobody else uses the result of the op                                      */
1236         if (get_ia32_am_support(irn) == ia32_am_None)
1237                 return;
1238
1239         cand = is_am_candidate(cg, h, block, irn);
1240         if (cand == IA32_AM_CAND_NONE)
1241                 return;
1242
1243         orig_cand = cand;
1244         DBG((mod, LEVEL_1, "\tfound address mode candidate %+F ... ", irn));
1245
1246         left  = get_irn_n(irn, 2);
1247         if (get_irn_arity(irn) == 4) {
1248                 /* it's an "unary" operation */
1249                 right = left;
1250                 assert(cand == IA32_AM_CAND_BOTH);
1251         } else {
1252                 right = get_irn_n(irn, 3);
1253         }
1254
1255         dest_possible = am_support & ia32_am_Dest ? 1 : 0;
1256         source_possible = am_support & ia32_am_Source ? 1 : 0;
1257
1258         if (dest_possible) {
1259                 addr_b = NULL;
1260                 addr_i = NULL;
1261                 store  = NULL;
1262
1263                 /* we should only have 1 user which is a store */
1264                 if (ia32_get_irn_n_edges(irn) == 1) {
1265                         ir_node *succ = get_edge_src_irn(get_irn_out_edge_first(irn));
1266
1267                         if (is_ia32_xStore(succ) || is_ia32_Store(succ)) {
1268                                 store  = succ;
1269                                 addr_b = get_irn_n(store, 0);
1270                                 addr_i = get_irn_n(store, 1);
1271                         }
1272                 }
1273
1274                 if (store == NULL) {
1275                         dest_possible = 0;
1276                 }
1277         }
1278
1279         if (dest_possible) {
1280                 /* normalize nodes, we need the interesting load on the left side */
1281                 if (cand & IA32_AM_CAND_RIGHT) {
1282                         load = get_Proj_pred(right);
1283                         if (load_store_addr_is_equal(load, store, addr_b, addr_i)) {
1284                                 exchange_left_right(irn, &left, &right, 3, 2);
1285                                 need_exchange_on_fail ^= 1;
1286                                 if (cand == IA32_AM_CAND_RIGHT)
1287                                         cand = IA32_AM_CAND_LEFT;
1288                         }
1289                 }
1290         }
1291
1292         if (dest_possible) {
1293                 if(cand & IA32_AM_CAND_LEFT && is_Proj(left)) {
1294                         load = get_Proj_pred(left);
1295
1296 #ifndef AGGRESSIVE_AM
1297                         /* we have to be the only user of the load */
1298                         if (get_irn_n_edges(left) > 1) {
1299                                 dest_possible = 0;
1300                         }
1301 #endif
1302                 } else {
1303                         dest_possible = 0;
1304                 }
1305         }
1306
1307         if (dest_possible) {
1308                 /* the store has to use the loads memory or the same memory
1309                  * as the load */
1310                 ir_node *loadmem = get_irn_n(load, 2);
1311                 ir_node *storemem = get_irn_n(store, 3);
1312                 assert(get_irn_mode(loadmem) == mode_M);
1313                 assert(get_irn_mode(storemem) == mode_M);
1314                 if(storemem != loadmem || !is_Proj(storemem)
1315                                 || get_Proj_pred(storemem) != load) {
1316                         dest_possible = 0;
1317                 }
1318         }
1319
1320         if (dest_possible) {
1321                 /* Compare Load and Store address */
1322                 if (!load_store_addr_is_equal(load, store, addr_b, addr_i))
1323                         dest_possible = 0;
1324         }
1325
1326         if (dest_possible) {
1327                 /* all conditions fullfilled, do the transformation */
1328                 assert(cand & IA32_AM_CAND_LEFT);
1329
1330                 /* set new base, index and attributes */
1331                 set_irn_n(irn, 0, addr_b);
1332                 set_irn_n(irn, 1, addr_i);
1333                 add_ia32_am_offs_int(irn, get_ia32_am_offs_int(load));
1334                 set_ia32_am_scale(irn, get_ia32_am_scale(load));
1335                 set_ia32_am_flavour(irn, get_ia32_am_flavour(load));
1336                 set_ia32_op_type(irn, ia32_AddrModeD);
1337                 set_ia32_frame_ent(irn, get_ia32_frame_ent(load));
1338                 set_ia32_ls_mode(irn, get_ia32_ls_mode(load));
1339
1340                 set_ia32_am_sc(irn, get_ia32_am_sc(load));
1341                 if (is_ia32_am_sc_sign(load))
1342                         set_ia32_am_sc_sign(irn);
1343
1344                 /* connect to Load memory and disconnect Load */
1345                 if (get_irn_arity(irn) == 5) {
1346                         /* binary AMop */
1347                         set_irn_n(irn, 4, get_irn_n(load, 2));
1348                         set_irn_n(irn, 2, ia32_get_admissible_noreg(cg, irn, 2));
1349                 } else {
1350                         /* unary AMop */
1351                         set_irn_n(irn, 3, get_irn_n(load, 2));
1352                         set_irn_n(irn, 2, ia32_get_admissible_noreg(cg, irn, 2));
1353                 }
1354
1355                 set_irn_mode(irn, mode_M);
1356
1357                 /* connect the memory Proj of the Store to the op */
1358                 mem_proj = ia32_get_proj_for_mode(store, mode_M);
1359                 edges_reroute(mem_proj, irn, irg);
1360
1361                 /* clear remat flag */
1362                 set_ia32_flags(irn, get_ia32_flags(irn) & ~arch_irn_flags_rematerializable);
1363
1364                 try_remove_from_sched(load);
1365                 try_remove_from_sched(store);
1366                 DBG_OPT_AM_D(load, store, irn);
1367
1368                 DB((mod, LEVEL_1, "merged with %+F and %+F into dest AM\n", load, store));
1369                 need_exchange_on_fail = 0;
1370                 source_possible = 0;
1371         }
1372
1373         if (source_possible) {
1374                 /* normalize ops, we need the load on the right */
1375                 if(cand == IA32_AM_CAND_LEFT) {
1376                         if(node_is_ia32_comm(irn)) {
1377                                 exchange_left_right(irn, &left, &right, 3, 2);
1378                                 need_exchange_on_fail ^= 1;
1379                                 cand = IA32_AM_CAND_RIGHT;
1380                         } else {
1381                                 source_possible = 0;
1382                         }
1383                 }
1384         }
1385
1386         if (source_possible) {
1387                 /* all conditions fullfilled, do transform */
1388                 assert(cand & IA32_AM_CAND_RIGHT);
1389                 load = get_Proj_pred(right);
1390
1391                 if(get_irn_n_edges(load) > 1) {
1392                         source_possible = 0;
1393                 }
1394         }
1395
1396         if (source_possible) {
1397                 addr_b = get_irn_n(load, 0);
1398                 addr_i = get_irn_n(load, 1);
1399
1400                 /* set new base, index and attributes */
1401                 set_irn_n(irn, 0, addr_b);
1402                 set_irn_n(irn, 1, addr_i);
1403                 add_ia32_am_offs_int(irn, get_ia32_am_offs_int(load));
1404                 set_ia32_am_scale(irn, get_ia32_am_scale(load));
1405                 set_ia32_am_flavour(irn, get_ia32_am_flavour(load));
1406                 set_ia32_op_type(irn, ia32_AddrModeS);
1407                 set_ia32_frame_ent(irn, get_ia32_frame_ent(load));
1408                 set_ia32_ls_mode(irn, get_ia32_ls_mode(load));
1409
1410                 set_ia32_am_sc(irn, get_ia32_am_sc(load));
1411                 if (is_ia32_am_sc_sign(load))
1412                         set_ia32_am_sc_sign(irn);
1413
1414                 /* clear remat flag */
1415                 set_ia32_flags(irn, get_ia32_flags(irn) & ~arch_irn_flags_rematerializable);
1416
1417                 if (is_ia32_use_frame(load)) {
1418                         if(get_ia32_frame_ent(load) == NULL) {
1419                                 set_ia32_need_stackent(irn);
1420                         }
1421                         set_ia32_use_frame(irn);
1422                 }
1423
1424                 /* connect to Load memory and disconnect Load */
1425                 if (get_irn_arity(irn) == 5) {
1426                         /* binary AMop */
1427                         set_irn_n(irn, 3, ia32_get_admissible_noreg(cg, irn, 3));
1428                         set_irn_n(irn, 4, get_irn_n(load, 2));
1429                 } else {
1430                         assert(get_irn_arity(irn) == 4);
1431                         /* unary AMop */
1432                         set_irn_n(irn, 2, ia32_get_admissible_noreg(cg, irn, 2));
1433                         set_irn_n(irn, 3, get_irn_n(load, 2));
1434                 }
1435
1436                 DBG_OPT_AM_S(load, irn);
1437
1438                 /* If Load has a memory Proj, connect it to the op */
1439                 mem_proj = ia32_get_proj_for_mode(load, mode_M);
1440                 if (mem_proj != NULL) {
1441                         ir_node *res_proj;
1442                         ir_mode *mode = get_irn_mode(irn);
1443
1444                         res_proj = new_rd_Proj(get_irn_dbg_info(irn), irg,
1445                                                get_nodes_block(irn), new_Unknown(mode_T),
1446                                                                    mode, 0);
1447                         set_irn_mode(irn, mode_T);
1448                         edges_reroute(irn, res_proj, irg);
1449                         set_Proj_pred(res_proj, irn);
1450
1451                         set_Proj_pred(mem_proj, irn);
1452                         set_Proj_proj(mem_proj, 1);
1453
1454                         if(sched_is_scheduled(irn)) {
1455                                 sched_add_after(irn, res_proj);
1456                                 sched_add_after(irn, mem_proj);
1457                         }
1458                 }
1459
1460                 if(get_irn_n_edges(load) == 0) {
1461                         try_remove_from_sched(load);
1462                 }
1463                 need_exchange_on_fail = 0;
1464
1465                 DB((mod, LEVEL_1, "merged with %+F into source AM\n", load));
1466         }
1467
1468         /* was exchanged but optimize failed: exchange back */
1469         if (need_exchange_on_fail) {
1470                 exchange_left_right(irn, &left, &right, 3, 2);
1471         }
1472 }
1473
1474 /**
1475  * Performs address mode optimization.
1476  */
1477 void ia32_optimize_addressmode(ia32_code_gen_t *cg) {
1478         /* if we are supposed to do AM or LEA optimization: recalculate edges */
1479         if (cg->opt & (IA32_OPT_DOAM | IA32_OPT_LEA)) {
1480                 edges_deactivate(cg->irg);
1481                 edges_activate(cg->irg);
1482         }
1483         else {
1484                 /* no optimizations at all */
1485                 return;
1486         }
1487
1488         /* beware: we cannot optimize LEA and AM in one run because */
1489         /*         LEA optimization adds new nodes to the irg which */
1490         /*         invalidates the phase data                       */
1491
1492         if (cg->opt & IA32_OPT_LEA) {
1493                 irg_walk_blkwise_graph(cg->irg, NULL, optimize_lea, cg);
1494         }
1495
1496         if (cg->dump)
1497                 be_dump(cg->irg, "-lea", dump_ir_block_graph_sched);
1498
1499         if (cg->opt & IA32_OPT_DOAM) {
1500                 /* we need height information for am optimization */
1501                 heights_t *h = heights_new(cg->irg);
1502                 ia32_am_opt_env_t env;
1503
1504                 env.cg = cg;
1505                 env.h  = h;
1506
1507                 irg_walk_blkwise_graph(cg->irg, NULL, optimize_am, &env);
1508
1509                 heights_free(h);
1510         }
1511 }