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

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