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

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