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