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