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

   1 /**
   2  * This is the main ia32 firm backend driver.
   3  * @author Christian Wuerdig
   4  * $Id$
   5  */
   6
   7 #ifdef HAVE_CONFIG_H
   8 #include "config.h"
   9 #endif
  10
  11 #ifdef HAVE_MALLOC_H
  12 #include <malloc.h>
  13 #endif
  14
  15 #ifdef HAVE_ALLOCA_H
  16 #include <alloca.h>
  17 #endif
  18
  19 #ifdef WITH_LIBCORE
  20 #include <libcore/lc_opts.h>
  21 #include <libcore/lc_opts_enum.h>
  22 #endif /* WITH_LIBCORE */
  23
  24 #include "pseudo_irg.h"
  25 #include "irgwalk.h"
  26 #include "irprog.h"
  27 #include "irprintf.h"
  28 #include "iredges_t.h"
  29 #include "ircons.h"
  30 #include "irgmod.h"
  31 #include "irgopt.h"
  32 #include "irbitset.h"
  33 #include "pdeq.h"
  34 #include "debug.h"
  35
  36 #include "../beabi.h"                 /* the general register allocator interface */
  37 #include "../benode_t.h"
  38 #include "../belower.h"
  39 #include "../besched_t.h"
  40 #include "../be.h"
  41 #include "bearch_ia32_t.h"
  42
  43 #include "ia32_new_nodes.h"           /* ia32 nodes interface */
  44 #include "gen_ia32_regalloc_if.h"     /* the generated interface (register type and class defenitions) */
  45 #include "ia32_gen_decls.h"           /* interface declaration emitter */
  46 #include "ia32_transform.h"
  47 #include "ia32_emitter.h"
  48 #include "ia32_map_regs.h"
  49 #include "ia32_optimize.h"
  50 #include "ia32_x87.h"
  51 #include "ia32_dbg_stat.h"
  52 #include "ia32_finish.h"
  53 #include "ia32_util.h"
  54
  55 #define DEBUG_MODULE "firm.be.ia32.isa"
  56
  57 /* TODO: ugly */
  58 static set *cur_reg_set = NULL;
  59
  60 #undef is_Start
  61 #define is_Start(irn) (get_irn_opcode(irn) == iro_Start)
  62
  63 /* Creates the unique per irg GP NoReg node. */
  64 ir_node *ia32_new_NoReg_gp(ia32_code_gen_t *cg) {
  65         return be_abi_get_callee_save_irn(cg->birg->abi, &ia32_gp_regs[REG_GP_NOREG]);
  66 }
  67
  68 /* Creates the unique per irg FP NoReg node. */
  69 ir_node *ia32_new_NoReg_fp(ia32_code_gen_t *cg) {
  70         return be_abi_get_callee_save_irn(cg->birg->abi,
  71                 USE_SSE2(cg) ? &ia32_xmm_regs[REG_XMM_NOREG] : &ia32_vfp_regs[REG_VFP_NOREG]);
  72 }
  73
  74 /**************************************************
  75  *                         _ _              _  __
  76  *                        | | |            (_)/ _|
  77  *  _ __ ___  __ _    __ _| | | ___   ___   _| |_
  78  * | '__/ _ \/ _` |  / _` | | |/ _ \ / __| | |  _|
  79  * | | |  __/ (_| | | (_| | | | (_) | (__  | | |
  80  * |_|  \___|\__, |  \__,_|_|_|\___/ \___| |_|_|
  81  *            __/ |
  82  *           |___/
  83  **************************************************/
  84
  85 static ir_node *my_skip_proj(const ir_node *n) {
  86         while (is_Proj(n))
  87                 n = get_Proj_pred(n);
  88         return (ir_node *)n;
  89 }
  90
  91
  92 /**
  93  * Return register requirements for an ia32 node.
  94  * If the node returns a tuple (mode_T) then the proj's
  95  * will be asked for this information.
  96  */
  97 static const arch_register_req_t *ia32_get_irn_reg_req(const void *self, arch_register_req_t *req, const ir_node *irn, int pos) {
  98         const ia32_irn_ops_t      *ops = self;
  99         const ia32_register_req_t *irn_req;
 100         long                       node_pos = pos == -1 ? 0 : pos;
 101         ir_mode                   *mode     = is_Block(irn) ? NULL : get_irn_mode(irn);
 102         FIRM_DBG_REGISTER(firm_dbg_module_t *mod, DEBUG_MODULE);
 103
 104         if (is_Block(irn) || mode == mode_M || mode == mode_X) {
 105                 DBG((mod, LEVEL_1, "ignoring Block, mode_M, mode_X node %+F\n", irn));
 106                 return NULL;
 107         }
 108
 109         if (mode == mode_T && pos < 0) {
 110                 DBG((mod, LEVEL_1, "ignoring request OUT requirements for node %+F\n", irn));
 111                 return NULL;
 112         }
 113
 114         DBG((mod, LEVEL_1, "get requirements at pos %d for %+F ... ", pos, irn));
 115
 116         if (is_Proj(irn)) {
 117                 if (pos == -1) {
 118                         node_pos = ia32_translate_proj_pos(irn);
 119                 }
 120                 else {
 121                         node_pos = pos;
 122                 }
 123
 124                 irn = my_skip_proj(irn);
 125
 126                 DB((mod, LEVEL_1, "skipping Proj, going to %+F at pos %d ... ", irn, node_pos));
 127         }
 128
 129         if (is_ia32_irn(irn)) {
 130                 if (pos >= 0) {
 131                         irn_req = get_ia32_in_req(irn, pos);
 132                 }
 133                 else {
 134                         irn_req = get_ia32_out_req(irn, node_pos);
 135                 }
 136
 137                 DB((mod, LEVEL_1, "returning reqs for %+F at pos %d\n", irn, pos));
 138
 139                 memcpy(req, &(irn_req->req), sizeof(*req));
 140
 141                 if (arch_register_req_is(&(irn_req->req), should_be_same)) {
 142                         assert(irn_req->same_pos >= 0 && "should be same constraint for in -> out NYI");
 143                         req->other_same = get_irn_n(irn, irn_req->same_pos);
 144                 }
 145
 146                 if (arch_register_req_is(&(irn_req->req), should_be_different)) {
 147                         assert(irn_req->different_pos >= 0 && "should be different constraint for in -> out NYI");
 148                         req->other_different = get_irn_n(irn, irn_req->different_pos);
 149                 }
 150         }
 151         else {
 152                 /* treat Unknowns like Const with default requirements */
 153                 if (is_Unknown(irn)) {
 154                         DB((mod, LEVEL_1, "returning UKNWN reqs for %+F\n", irn));
 155                         if (mode_is_float(mode)) {
 156                                 if (USE_SSE2(ops->cg))
 157                                         memcpy(req, &(ia32_default_req_ia32_xmm_xmm_UKNWN), sizeof(*req));
 158                                 else
 159                                         memcpy(req, &(ia32_default_req_ia32_vfp_vfp_UKNWN), sizeof(*req));
 160                         }
 161                         else if (mode_is_int(mode) || mode_is_reference(mode))
 162                                 memcpy(req, &(ia32_default_req_ia32_gp_gp_UKNWN), sizeof(*req));
 163                         else if (mode == mode_T || mode == mode_M) {
 164                                 DBG((mod, LEVEL_1, "ignoring Unknown node %+F\n", irn));
 165                                 return NULL;
 166                         }
 167                         else
 168                                 assert(0 && "unsupported Unknown-Mode");
 169                 }
 170                 else {
 171                         DB((mod, LEVEL_1, "returning NULL for %+F (not ia32)\n", irn));
 172                         req = NULL;
 173                 }
 174         }
 175
 176         return req;
 177 }
 178
 179 static void ia32_set_irn_reg(const void *self, ir_node *irn, const arch_register_t *reg) {
 180         int                   pos = 0;
 181         const ia32_irn_ops_t *ops = self;
 182
 183         if (get_irn_mode(irn) == mode_X) {
 184                 return;
 185         }
 186
 187         DBG((ops->cg->mod, LEVEL_1, "ia32 assigned register %s to node %+F\n", reg->name, irn));
 188
 189         if (is_Proj(irn)) {
 190                 pos = ia32_translate_proj_pos(irn);
 191                 irn = my_skip_proj(irn);
 192         }
 193
 194         if (is_ia32_irn(irn)) {
 195                 const arch_register_t **slots;
 196
 197                 slots      = get_ia32_slots(irn);
 198                 slots[pos] = reg;
 199         }
 200         else {
 201                 ia32_set_firm_reg(irn, reg, cur_reg_set);
 202         }
 203 }
 204
 205 static const arch_register_t *ia32_get_irn_reg(const void *self, const ir_node *irn) {
 206         int pos = 0;
 207         const arch_register_t *reg = NULL;
 208
 209         if (is_Proj(irn)) {
 210
 211                 if (get_irn_mode(irn) == mode_X) {
 212                         return NULL;
 213                 }
 214
 215                 pos = ia32_translate_proj_pos(irn);
 216                 irn = my_skip_proj(irn);
 217         }
 218
 219         if (is_ia32_irn(irn)) {
 220                 const arch_register_t **slots;
 221                 slots = get_ia32_slots(irn);
 222                 reg   = slots[pos];
 223         }
 224         else {
 225                 reg = ia32_get_firm_reg(irn, cur_reg_set);
 226         }
 227
 228         return reg;
 229 }
 230
 231 static arch_irn_class_t ia32_classify(const void *self, const ir_node *irn) {
 232         irn = my_skip_proj(irn);
 233         if (is_cfop(irn))
 234                 return arch_irn_class_branch;
 235         else if (is_ia32_Cnst(irn))
 236                 return arch_irn_class_const;
 237         else if (is_ia32_Ld(irn))
 238                 return arch_irn_class_load;
 239         else if (is_ia32_St(irn) || is_ia32_Store8Bit(irn))
 240                 return arch_irn_class_store;
 241         else if (is_ia32_irn(irn))
 242                 return arch_irn_class_normal;
 243         else
 244                 return 0;
 245 }
 246
 247 static arch_irn_flags_t ia32_get_flags(const void *self, const ir_node *irn) {
 248         irn = my_skip_proj(irn);
 249         if (is_ia32_irn(irn))
 250                 return get_ia32_flags(irn);
 251         else {
 252                 if (is_Unknown(irn))
 253                         return arch_irn_flags_ignore;
 254                 return 0;
 255         }
 256 }
 257
 258 static entity *ia32_get_frame_entity(const void *self, const ir_node *irn) {
 259         return is_ia32_irn(irn) ? get_ia32_frame_ent(irn) : NULL;
 260 }
 261
 262 static void ia32_set_stack_bias(const void *self, ir_node *irn, int bias) {
 263         char buf[64];
 264         const ia32_irn_ops_t *ops = self;
 265
 266         if (get_ia32_frame_ent(irn)) {
 267                 ia32_am_flavour_t am_flav = get_ia32_am_flavour(irn);
 268
 269                 DBG((ops->cg->mod, LEVEL_1, "stack biased %+F with %d\n", irn, bias));
 270                 snprintf(buf, sizeof(buf), "%d", bias);
 271
 272                 if (get_ia32_op_type(irn) == ia32_Normal) {
 273                         set_ia32_cnst(irn, buf);
 274                 }
 275                 else {
 276                         add_ia32_am_offs(irn, buf);
 277                         am_flav |= ia32_O;
 278                         set_ia32_am_flavour(irn, am_flav);
 279                 }
 280         }
 281 }
 282
 283 typedef struct {
 284         be_abi_call_flags_bits_t flags;
 285         const arch_isa_t *isa;
 286         const arch_env_t *aenv;
 287         ir_graph *irg;
 288 } ia32_abi_env_t;
 289
 290 static void *ia32_abi_init(const be_abi_call_t *call, const arch_env_t *aenv, ir_graph *irg)
 291 {
 292         ia32_abi_env_t *env    = xmalloc(sizeof(env[0]));
 293         be_abi_call_flags_t fl = be_abi_call_get_flags(call);
 294         env->flags = fl.bits;
 295         env->irg   = irg;
 296         env->aenv  = aenv;
 297         env->isa   = aenv->isa;
 298         return env;
 299 }
 300
 301 /**
 302  * Put all registers which are saved by the prologue/epilogue in a set.
 303  *
 304  * @param self  The callback object.
 305  * @param s     The result set.
 306  */
 307 static void ia32_abi_dont_save_regs(void *self, pset *s)
 308 {
 309         ia32_abi_env_t *env = self;
 310         if(env->flags.try_omit_fp)
 311                 pset_insert_ptr(s, env->isa->bp);
 312 }
 313
 314 /**
 315  * Generate the routine prologue.
 316  *
 317  * @param self    The callback object.
 318  * @param mem     A pointer to the mem node. Update this if you define new memory.
 319  * @param reg_map A map mapping all callee_save/ignore/parameter registers to their defining nodes.
 320  *
 321  * @return        The register which shall be used as a stack frame base.
 322  *
 323  * All nodes which define registers in @p reg_map must keep @p reg_map current.
 324  */
 325 static const arch_register_t *ia32_abi_prologue(void *self, ir_node **mem, pmap *reg_map)
 326 {
 327         ia32_abi_env_t *env              = self;
 328
 329         if (!env->flags.try_omit_fp) {
 330                 ir_node *bl          = get_irg_start_block(env->irg);
 331                 ir_node *curr_sp     = be_abi_reg_map_get(reg_map, env->isa->sp);
 332                 ir_node *curr_bp     = be_abi_reg_map_get(reg_map, env->isa->bp);
 333                 ir_node *push;
 334
 335                 /* push ebp */
 336                 push    = new_rd_ia32_Push(NULL, env->irg, bl, curr_sp, curr_bp, *mem);
 337                 curr_sp = new_r_Proj(env->irg, bl, push, get_irn_mode(curr_sp), pn_ia32_Push_stack);
 338                 *mem    = new_r_Proj(env->irg, bl, push, mode_M, pn_ia32_Push_M);
 339
 340                 /* the push must have SP out register */
 341                 arch_set_irn_register(env->aenv, curr_sp, env->isa->sp);
 342                 set_ia32_flags(push, arch_irn_flags_ignore);
 343
 344                 /* move esp to ebp */
 345                 curr_bp  = be_new_Copy(env->isa->bp->reg_class, env->irg, bl, curr_sp);
 346                 be_set_constr_single_reg(curr_bp, BE_OUT_POS(0), env->isa->bp);
 347                 arch_set_irn_register(env->aenv, curr_bp, env->isa->bp);
 348                 be_node_set_flags(curr_bp, BE_OUT_POS(0), arch_irn_flags_ignore);
 349
 350                 /* beware: the copy must be done before any other sp use */
 351                 curr_sp = be_new_CopyKeep_single(env->isa->sp->reg_class, env->irg, bl, curr_sp, curr_bp, get_irn_mode(curr_sp));
 352                 be_set_constr_single_reg(curr_sp, BE_OUT_POS(0), env->isa->sp);
 353                 arch_set_irn_register(env->aenv, curr_sp, env->isa->sp);
 354                 be_node_set_flags(curr_sp, BE_OUT_POS(0), arch_irn_flags_ignore);
 355
 356                 be_abi_reg_map_set(reg_map, env->isa->sp, curr_sp);
 357                 be_abi_reg_map_set(reg_map, env->isa->bp, curr_bp);
 358
 359                 return env->isa->bp;
 360         }
 361
 362         return env->isa->sp;
 363 }
 364
 365 /**
 366  * Generate the routine epilogue.
 367  * @param self    The callback object.
 368  * @param bl      The block for the epilog
 369  * @param mem     A pointer to the mem node. Update this if you define new memory.
 370  * @param reg_map A map mapping all callee_save/ignore/parameter registers to their defining nodes.
 371  * @return        The register which shall be used as a stack frame base.
 372  *
 373  * All nodes which define registers in @p reg_map must keep @p reg_map current.
 374  */
 375 static void ia32_abi_epilogue(void *self, ir_node *bl, ir_node **mem, pmap *reg_map)
 376 {
 377         ia32_abi_env_t *env  = self;
 378         ir_node *curr_sp     = be_abi_reg_map_get(reg_map, env->isa->sp);
 379         ir_node *curr_bp     = be_abi_reg_map_get(reg_map, env->isa->bp);
 380
 381         if (env->flags.try_omit_fp) {
 382                 /* simply remove the stack frame here */
 383                 curr_sp = be_new_IncSP(env->isa->sp, env->irg, bl, curr_sp, *mem, BE_STACK_FRAME_SIZE, be_stack_dir_shrink);
 384         }
 385         else {
 386                 const ia32_isa_t *isa = (ia32_isa_t *)env->isa;
 387                 ir_mode *mode_bp = env->isa->bp->reg_class->mode;
 388
 389                 /* gcc always emits a leave at the end of a routine */
 390                 if (1 || ARCH_AMD(isa->opt_arch)) {
 391                         ir_node *leave;
 392
 393                         /* leave */
 394                         leave = new_rd_ia32_Leave(NULL, env->irg, bl, curr_sp, *mem);
 395                         set_ia32_flags(leave, arch_irn_flags_ignore);
 396                         curr_bp = new_r_Proj(current_ir_graph, bl, leave, mode_bp, pn_ia32_Leave_frame);
 397                         curr_sp = new_r_Proj(current_ir_graph, bl, leave, get_irn_mode(curr_sp), pn_ia32_Leave_stack);
 398                         *mem    = new_r_Proj(current_ir_graph, bl, leave, mode_M, pn_ia32_Leave_M);
 399                 }
 400                 else {
 401                         ir_node *pop;
 402
 403                         /* copy ebp to esp */
 404                         curr_sp = be_new_SetSP(env->isa->sp, env->irg, bl, curr_sp, curr_bp, *mem);
 405
 406                         /* pop ebp */
 407                         pop = new_rd_ia32_Pop(NULL, env->irg, bl, curr_sp, *mem);
 408                         set_ia32_flags(pop, arch_irn_flags_ignore);
 409                         curr_bp = new_r_Proj(current_ir_graph, bl, pop, mode_bp, pn_ia32_Pop_res);
 410                         curr_sp = new_r_Proj(current_ir_graph, bl, pop, get_irn_mode(curr_sp), pn_ia32_Pop_stack);
 411                         *mem    = new_r_Proj(current_ir_graph, bl, pop, mode_M, pn_ia32_Pop_M);
 412                 }
 413                 arch_set_irn_register(env->aenv, curr_sp, env->isa->sp);
 414                 arch_set_irn_register(env->aenv, curr_bp, env->isa->bp);
 415         }
 416
 417         be_abi_reg_map_set(reg_map, env->isa->sp, curr_sp);
 418         be_abi_reg_map_set(reg_map, env->isa->bp, curr_bp);
 419 }
 420
 421 /**
 422  * Produces the type which sits between the stack args and the locals on the stack.
 423  * it will contain the return address and space to store the old base pointer.
 424  * @return The Firm type modeling the ABI between type.
 425  */
 426 static ir_type *ia32_abi_get_between_type(void *self)
 427 {
 428 #define IDENT(s) new_id_from_chars(s, sizeof(s)-1)
 429         static ir_type *omit_fp_between_type = NULL;
 430         static ir_type *between_type         = NULL;
 431
 432         ia32_abi_env_t *env = self;
 433
 434         if ( !between_type) {
 435                 entity *old_bp_ent;
 436                 entity *ret_addr_ent;
 437                 entity *omit_fp_ret_addr_ent;
 438
 439                 ir_type *old_bp_type   = new_type_primitive(IDENT("bp"), mode_P);
 440                 ir_type *ret_addr_type = new_type_primitive(IDENT("return_addr"), mode_P);
 441
 442                 between_type           = new_type_struct(IDENT("ia32_between_type"));
 443                 old_bp_ent             = new_entity(between_type, IDENT("old_bp"), old_bp_type);
 444                 ret_addr_ent           = new_entity(between_type, IDENT("ret_addr"), ret_addr_type);
 445
 446                 set_entity_offset_bytes(old_bp_ent, 0);
 447                 set_entity_offset_bytes(ret_addr_ent, get_type_size_bytes(old_bp_type));
 448                 set_type_size_bytes(between_type, get_type_size_bytes(old_bp_type) + get_type_size_bytes(ret_addr_type));
 449                 set_type_state(between_type, layout_fixed);
 450
 451                 omit_fp_between_type = new_type_struct(IDENT("ia32_between_type_omit_fp"));
 452                 omit_fp_ret_addr_ent = new_entity(omit_fp_between_type, IDENT("ret_addr"), ret_addr_type);
 453
 454                 set_entity_offset_bytes(omit_fp_ret_addr_ent, 0);
 455                 set_type_size_bytes(omit_fp_between_type, get_type_size_bytes(ret_addr_type));
 456                 set_type_state(omit_fp_between_type, layout_fixed);
 457         }
 458
 459         return env->flags.try_omit_fp ? omit_fp_between_type : between_type;
 460 #undef IDENT
 461 }
 462
 463 /**
 464  * Get the estimated cycle count for @p irn.
 465  *
 466  * @param self The this pointer.
 467  * @param irn  The node.
 468  *
 469  * @return     The estimated cycle count for this operation
 470  */
 471 static int ia32_get_op_estimated_cost(const void *self, const ir_node *irn)
 472 {
 473         int cost;
 474
 475         if(is_Proj(irn))
 476           return 0;
 477
 478         switch (get_ia32_irn_opcode(irn)) {
 479         case iro_ia32_xDiv:
 480         case iro_ia32_DivMod:
 481                 cost = 8;
 482                 break;
 483
 484         case iro_ia32_xLoad:
 485         case iro_ia32_l_Load:
 486         case iro_ia32_Load:
 487                 cost = 25;
 488                 break;
 489
 490         case iro_ia32_Push:
 491         case iro_ia32_Pop:
 492                 cost = 5;
 493                 break;
 494
 495         case iro_ia32_xStore:
 496         case iro_ia32_l_Store:
 497         case iro_ia32_Store:
 498         case iro_ia32_Store8Bit:
 499                 cost = 50;
 500                 break;
 501
 502         case iro_ia32_MulS:
 503         case iro_ia32_Mul:
 504         case iro_ia32_Mulh:
 505         case iro_ia32_xMul:
 506         case iro_ia32_l_MulS:
 507         case iro_ia32_l_Mul:
 508                 cost = 2;
 509                 break;
 510
 511         default:
 512                 cost = 1;
 513         }
 514
 515         return cost;
 516 }
 517
 518 /**
 519  * Returns the inverse operation if @p irn, recalculating the argument at position @p i.
 520  *
 521  * @param irn       The original operation
 522  * @param i         Index of the argument we want the inverse operation to yield
 523  * @param inverse   struct to be filled with the resulting inverse op
 524  * @param obstack   The obstack to use for allocation of the returned nodes array
 525  * @return          The inverse operation or NULL if operation invertible
 526  */
 527 static arch_inverse_t *ia32_get_inverse(const void *self, const ir_node *irn, int i, arch_inverse_t *inverse, struct obstack *obst) {
 528         ir_graph *irg;
 529         ir_mode  *mode;
 530         ir_node  *block, *noreg, *nomem;
 531         int      pnc;
 532
 533         /* we cannot invert non-ia32 irns */
 534         if (! is_ia32_irn(irn))
 535                 return NULL;
 536
 537         /* operand must always be a real operand (not base, index or mem) */
 538         if (i != 2 && i != 3)
 539                 return NULL;
 540
 541         /* we don't invert address mode operations */
 542         if (get_ia32_op_type(irn) != ia32_Normal)
 543                 return NULL;
 544
 545         irg   = get_irn_irg(irn);
 546         block = get_nodes_block(irn);
 547         mode  = get_ia32_res_mode(irn);
 548         noreg = get_irn_n(irn, 0);
 549         nomem = new_r_NoMem(irg);
 550
 551         /* initialize structure */
 552         inverse->nodes = obstack_alloc(obst, 2 * sizeof(inverse->nodes[0]));
 553         inverse->costs = 0;
 554         inverse->n     = 2;
 555
 556         switch (get_ia32_irn_opcode(irn)) {
 557                 case iro_ia32_Add:
 558                         if (get_ia32_immop_type(irn) == ia32_ImmConst) {
 559                                 /* we have an add with a const here */
 560                                 /* invers == add with negated const */
 561                                 inverse->nodes[0] = new_rd_ia32_Add(NULL, irg, block, noreg, noreg, get_irn_n(irn, i), noreg, nomem);
 562                                 pnc               = pn_ia32_Add_res;
 563                                 inverse->costs   += 1;
 564                                 copy_ia32_Immop_attr(inverse->nodes[0], (ir_node *)irn);
 565                                 set_ia32_Immop_tarval(inverse->nodes[0], tarval_neg(get_ia32_Immop_tarval(irn)));
 566                                 set_ia32_commutative(inverse->nodes[0]);
 567                         }
 568                         else if (get_ia32_immop_type(irn) == ia32_ImmSymConst) {
 569                                 /* we have an add with a symconst here */
 570                                 /* invers == sub with const */
 571                                 inverse->nodes[0] = new_rd_ia32_Sub(NULL, irg, block, noreg, noreg, get_irn_n(irn, i), noreg, nomem);
 572                                 pnc               = pn_ia32_Sub_res;
 573                                 inverse->costs   += 2;
 574                                 copy_ia32_Immop_attr(inverse->nodes[0], (ir_node *)irn);
 575                         }
 576                         else {
 577                                 /* normal add: inverse == sub */
 578                                 ir_node *proj = ia32_get_res_proj(irn);
 579                                 assert(proj);
 580
 581                                 inverse->nodes[0] = new_rd_ia32_Sub(NULL, irg, block, noreg, noreg, proj, get_irn_n(irn, i ^ 1), nomem);
 582                                 pnc               = pn_ia32_Sub_res;
 583                                 inverse->costs   += 2;
 584                         }
 585                         break;
 586                 case iro_ia32_Sub:
 587                         if (get_ia32_immop_type(irn) != ia32_ImmNone) {
 588                                 /* we have a sub with a const/symconst here */
 589                                 /* invers == add with this const */
 590                                 inverse->nodes[0] = new_rd_ia32_Add(NULL, irg, block, noreg, noreg, get_irn_n(irn, i), noreg, nomem);
 591                                 pnc               = pn_ia32_Add_res;
 592                                 inverse->costs   += (get_ia32_immop_type(irn) == ia32_ImmSymConst) ? 5 : 1;
 593                                 copy_ia32_Immop_attr(inverse->nodes[0], (ir_node *)irn);
 594                         }
 595                         else {
 596                                 /* normal sub */
 597                                 ir_node *proj = ia32_get_res_proj(irn);
 598                                 assert(proj);
 599
 600                                 if (i == 2) {
 601                                         inverse->nodes[0] = new_rd_ia32_Add(NULL, irg, block, noreg, noreg, proj, get_irn_n(irn, 3), nomem);
 602                                 }
 603                                 else {
 604                                         inverse->nodes[0] = new_rd_ia32_Sub(NULL, irg, block, noreg, noreg, get_irn_n(irn, 2), proj, nomem);
 605                                 }
 606                                 pnc             = pn_ia32_Sub_res;
 607                                 inverse->costs += 1;
 608                         }
 609                         break;
 610                 case iro_ia32_Eor:
 611                         if (get_ia32_immop_type(irn) != ia32_ImmNone) {
 612                                 /* xor with const: inverse = xor */
 613                                 inverse->nodes[0] = new_rd_ia32_Eor(NULL, irg, block, noreg, noreg, get_irn_n(irn, i), noreg, nomem);
 614                                 pnc               = pn_ia32_Eor_res;
 615                                 inverse->costs   += (get_ia32_immop_type(irn) == ia32_ImmSymConst) ? 5 : 1;
 616                                 copy_ia32_Immop_attr(inverse->nodes[0], (ir_node *)irn);
 617                         }
 618                         else {
 619                                 /* normal xor */
 620                                 inverse->nodes[0] = new_rd_ia32_Eor(NULL, irg, block, noreg, noreg, (ir_node *)irn, get_irn_n(irn, i), nomem);
 621                                 pnc               = pn_ia32_Eor_res;
 622                                 inverse->costs   += 1;
 623                         }
 624                         break;
 625                 case iro_ia32_Not: {
 626                         ir_node *proj = ia32_get_res_proj(irn);
 627                         assert(proj);
 628
 629                         inverse->nodes[0] = new_rd_ia32_Not(NULL, irg, block, noreg, noreg, proj, nomem);
 630                         pnc = pn_ia32_Not_res;
 631                         inverse->costs   += 1;
 632                         break;
 633                 }
 634                 case iro_ia32_Minus: {
 635                         ir_node *proj = ia32_get_res_proj(irn);
 636                         assert(proj);
 637
 638                         inverse->nodes[0] = new_rd_ia32_Minus(NULL, irg, block, noreg, noreg, proj, nomem);
 639                         pnc               = pn_ia32_Minus_res;
 640                         inverse->costs   += 1;
 641                         break;
 642                 }
 643                 default:
 644                         /* inverse operation not supported */
 645                         return NULL;
 646         }
 647
 648         set_ia32_res_mode(inverse->nodes[0], mode);
 649         inverse->nodes[1] = new_r_Proj(irg, block, inverse->nodes[0], mode, pnc);
 650
 651         return inverse;
 652 }
 653
 654 /**
 655  * Check if irn can load it's operand at position i from memory (source addressmode).
 656  * @param self   Pointer to irn ops itself
 657  * @param irn    The irn to be checked
 658  * @param i      The operands position
 659  * @return Non-Zero if operand can be loaded
 660  */
 661 static int ia32_possible_memory_operand(const void *self, const ir_node *irn, unsigned int i) {
 662         if (! is_ia32_irn(irn)                            ||  /* must be an ia32 irn */
 663                 get_irn_arity(irn) != 5                       ||  /* must be a binary operation */
 664                 get_ia32_op_type(irn) != ia32_Normal          ||  /* must not already be a addressmode irn */
 665                 ! (get_ia32_am_support(irn) & ia32_am_Source) ||  /* must be capable of source addressmode */
 666         (i != 2 && i != 3)                            ||  /* a "real" operand position must be requested */
 667                 (i == 2 && ! is_ia32_commutative(irn))        ||  /* if first operand requested irn must be commutative */
 668                 is_ia32_use_frame(irn))                           /* must not already use frame */
 669                 return 0;
 670
 671         return 1;
 672 }
 673
 674 static void ia32_perform_memory_operand(const void *self, ir_node *irn, ir_node *reload, unsigned int i) {
 675         assert(ia32_possible_memory_operand(self, irn, i) && "Cannot perform memory operand change");
 676         assert(get_nodes_block(reload) == get_nodes_block(irn) && "Reload must be in same block as irn.");
 677
 678         if (get_irn_n_edges(reload) > 1)
 679                 return;
 680
 681         if (i == 2) {
 682                 ir_node *tmp = get_irn_n(irn, 3);
 683                 set_irn_n(irn, 3, get_irn_n(irn, 2));
 684                 set_irn_n(irn, 2, tmp);
 685         }
 686
 687         set_ia32_am_support(irn, ia32_am_Source);
 688         set_ia32_op_type(irn, ia32_AddrModeS);
 689         set_ia32_am_flavour(irn, ia32_B);
 690         set_ia32_ls_mode(irn, get_irn_mode(reload));
 691         set_ia32_frame_ent(irn, be_get_frame_entity(reload));
 692         set_ia32_use_frame(irn);
 693
 694         set_irn_n(irn, 0, be_get_Reload_frame(reload));
 695         set_irn_n(irn, 4, be_get_Reload_mem(reload));
 696
 697         /*
 698                 Input at position one is index register, which is NoReg.
 699                 We would need cg object to get a real noreg, but we cannot
 700                 access it from here.
 701          */
 702         set_irn_n(irn, 3, get_irn_n(irn, 1));
 703
 704         DBG_OPT_AM_S(reload, irn);
 705 }
 706
 707 static const be_abi_callbacks_t ia32_abi_callbacks = {
 708         ia32_abi_init,
 709         free,
 710         ia32_abi_get_between_type,
 711         ia32_abi_dont_save_regs,
 712         ia32_abi_prologue,
 713         ia32_abi_epilogue,
 714 };
 715
 716 /* fill register allocator interface */
 717
 718 static const arch_irn_ops_if_t ia32_irn_ops_if = {
 719         ia32_get_irn_reg_req,
 720         ia32_set_irn_reg,
 721         ia32_get_irn_reg,
 722         ia32_classify,
 723         ia32_get_flags,
 724         ia32_get_frame_entity,
 725         ia32_set_stack_bias,
 726         ia32_get_inverse,
 727         ia32_get_op_estimated_cost,
 728         ia32_possible_memory_operand,
 729         ia32_perform_memory_operand,
 730 };
 731
 732 ia32_irn_ops_t ia32_irn_ops = {
 733         &ia32_irn_ops_if,
 734         NULL
 735 };
 736
 737
 738
 739 /**************************************************
 740  *                _                         _  __
 741  *               | |                       (_)/ _|
 742  *   ___ ___   __| | ___  __ _  ___ _ __    _| |_
 743  *  / __/ _ \ / _` |/ _ \/ _` |/ _ \ '_ \  | |  _|
 744  * | (_| (_) | (_| |  __/ (_| |  __/ | | | | | |
 745  *  \___\___/ \__,_|\___|\__, |\___|_| |_| |_|_|
 746  *                        __/ |
 747  *                       |___/
 748  **************************************************/
 749
 750 /**
 751  * Transforms the standard firm graph into
 752  * an ia32 firm graph
 753  */
 754 static void ia32_prepare_graph(void *self) {
 755         ia32_code_gen_t *cg = self;
 756         dom_front_info_t *dom;
 757         DEBUG_ONLY(firm_dbg_module_t *old_mod = cg->mod;)
 758
 759         FIRM_DBG_REGISTER(cg->mod, "firm.be.ia32.transform");
 760
 761         /* 1st: transform constants and psi condition trees */
 762         ia32_pre_transform_phase(cg);
 763
 764         /* 2nd: transform all remaining nodes */
 765         ia32_register_transformers();
 766         dom = be_compute_dominance_frontiers(cg->irg);
 767         irg_walk_blkwise_graph(cg->irg, NULL, ia32_transform_node, cg);
 768         be_free_dominance_frontiers(dom);
 769
 770         if (cg->dump)
 771                 be_dump(cg->irg, "-transformed", dump_ir_block_graph_sched);
 772
 773         /* 3rd: optimize address mode */
 774         FIRM_DBG_REGISTER(cg->mod, "firm.be.ia32.am");
 775         ia32_optimize_addressmode(cg);
 776
 777         if (cg->dump)
 778                 be_dump(cg->irg, "-am", dump_ir_block_graph_sched);
 779
 780         DEBUG_ONLY(cg->mod = old_mod;)
 781 }
 782
 783 /**
 784  * Dummy functions for hooks we don't need but which must be filled.
 785  */
 786 static void ia32_before_sched(void *self) {
 787 }
 788
 789 static void remove_unused_nodes(ir_node *irn, bitset_t *already_visited) {
 790         int i;
 791         ir_mode *mode;
 792         ir_node *mem_proj;
 793
 794         if (is_Block(irn))
 795                 return;
 796
 797         mode = get_irn_mode(irn);
 798
 799         /* check if we already saw this node or the node has more than one user */
 800         if (bitset_contains_irn(already_visited, irn) || get_irn_n_edges(irn) > 1)
 801                 return;
 802
 803         /* mark irn visited */
 804         bitset_add_irn(already_visited, irn);
 805
 806         /* non-Tuple nodes with one user: ok, return */
 807         if (get_irn_n_edges(irn) >= 1 && mode != mode_T)
 808                 return;
 809
 810         /* tuple node has one user which is not the mem proj-> ok */
 811         if (mode == mode_T && get_irn_n_edges(irn) == 1) {
 812                 mem_proj = ia32_get_proj_for_mode(irn, mode_M);
 813                 if (! mem_proj)
 814                         return;
 815         }
 816
 817         for (i = get_irn_arity(irn) - 1; i >= 0; i--) {
 818                 ir_node *pred = get_irn_n(irn, i);
 819
 820                 /* do not follow memory edges or we will accidentally remove stores */
 821                 if (is_Proj(pred) && get_irn_mode(pred) == mode_M)
 822                         continue;
 823
 824                 set_irn_n(irn, i, new_Bad());
 825
 826                 /*
 827                         The current node is about to be removed: if the predecessor
 828                         has only this node as user, it need to be removed as well.
 829                 */
 830                 if (get_irn_n_edges(pred) <= 1)
 831                         remove_unused_nodes(pred, already_visited);
 832         }
 833
 834         if (sched_is_scheduled(irn))
 835                 sched_remove(irn);
 836 }
 837
 838 static void remove_unused_loads_walker(ir_node *irn, void *env) {
 839         bitset_t *already_visited = env;
 840         if (is_ia32_Ld(irn) && ! bitset_contains_irn(already_visited, irn))
 841                 remove_unused_nodes(irn, env);
 842 }
 843
 844 /**
 845  * Called before the register allocator.
 846  * Calculate a block schedule here. We need it for the x87
 847  * simulator and the emitter.
 848  */
 849 static void ia32_before_ra(void *self) {
 850         ia32_code_gen_t *cg              = self;
 851         bitset_t        *already_visited = bitset_irg_malloc(cg->irg);
 852
 853         cg->blk_sched = sched_create_block_schedule(cg->irg);
 854
 855         /*
 856                 Handle special case:
 857                 There are sometimes unused loads, only pinned by memory.
 858                 We need to remove those Loads and all other nodes which won't be used
 859                 after removing the Load from schedule.
 860         */
 861         irg_walk_graph(cg->irg, remove_unused_loads_walker, NULL, already_visited);
 862         bitset_free(already_visited);
 863 }
 864
 865
 866 /**
 867  * Transforms a be node into a Load.
 868  */
 869 static void transform_to_Load(ia32_transform_env_t *env) {
 870         ir_node *irn         = env->irn;
 871         entity  *ent         = be_get_frame_entity(irn);
 872         ir_mode *mode        = env->mode;
 873         ir_node *noreg       = ia32_new_NoReg_gp(env->cg);
 874         ir_node *nomem       = new_rd_NoMem(env->irg);
 875         ir_node *sched_point = NULL;
 876         ir_node *ptr         = get_irn_n(irn, 0);
 877         ir_node *mem         = be_is_Reload(irn) ? get_irn_n(irn, 1) : nomem;
 878         ir_node *new_op, *proj;
 879         const arch_register_t *reg;
 880
 881         if (sched_is_scheduled(irn)) {
 882                 sched_point = sched_prev(irn);
 883         }
 884
 885         if (mode_is_float(mode)) {
 886                 if (USE_SSE2(env->cg))
 887                         new_op = new_rd_ia32_xLoad(env->dbg, env->irg, env->block, ptr, noreg, mem);
 888                 else
 889                         new_op = new_rd_ia32_vfld(env->dbg, env->irg, env->block, ptr, noreg, mem);
 890         }
 891         else {
 892                 new_op = new_rd_ia32_Load(env->dbg, env->irg, env->block, ptr, noreg, mem);
 893         }
 894
 895         set_ia32_am_support(new_op, ia32_am_Source);
 896         set_ia32_op_type(new_op, ia32_AddrModeS);
 897         set_ia32_am_flavour(new_op, ia32_B);
 898         set_ia32_ls_mode(new_op, mode);
 899         set_ia32_frame_ent(new_op, ent);
 900         set_ia32_use_frame(new_op);
 901
 902         DBG_OPT_RELOAD2LD(irn, new_op);
 903
 904         proj = new_rd_Proj(env->dbg, env->irg, env->block, new_op, mode, pn_Load_res);
 905
 906         if (sched_point) {
 907                 sched_add_after(sched_point, new_op);
 908                 sched_add_after(new_op, proj);
 909
 910                 sched_remove(irn);
 911         }
 912
 913         /* copy the register from the old node to the new Load */
 914         reg = arch_get_irn_register(env->cg->arch_env, irn);
 915         arch_set_irn_register(env->cg->arch_env, new_op, reg);
 916
 917         SET_IA32_ORIG_NODE(new_op, ia32_get_old_node_name(env->cg, irn));
 918
 919         exchange(irn, proj);
 920 }
 921
 922 /**
 923  * Transforms a be node into a Store.
 924  */
 925 static void transform_to_Store(ia32_transform_env_t *env) {
 926         ir_node *irn   = env->irn;
 927         entity  *ent   = be_get_frame_entity(irn);
 928         ir_mode *mode  = env->mode;
 929         ir_node *noreg = ia32_new_NoReg_gp(env->cg);
 930         ir_node *nomem = new_rd_NoMem(env->irg);
 931         ir_node *ptr   = get_irn_n(irn, 0);
 932         ir_node *val   = get_irn_n(irn, 1);
 933         ir_node *new_op, *proj;
 934         ir_node *sched_point = NULL;
 935
 936         if (sched_is_scheduled(irn)) {
 937                 sched_point = sched_prev(irn);
 938         }
 939
 940         if (mode_is_float(mode)) {
 941                 if (USE_SSE2(env->cg))
 942                         new_op = new_rd_ia32_xStore(env->dbg, env->irg, env->block, ptr, noreg, val, nomem);
 943                 else
 944                         new_op = new_rd_ia32_vfst(env->dbg, env->irg, env->block, ptr, noreg, val, nomem);
 945         }
 946         else if (get_mode_size_bits(mode) == 8) {
 947                 new_op = new_rd_ia32_Store8Bit(env->dbg, env->irg, env->block, ptr, noreg, val, nomem);
 948         }
 949         else {
 950                 new_op = new_rd_ia32_Store(env->dbg, env->irg, env->block, ptr, noreg, val, nomem);
 951         }
 952
 953         set_ia32_am_support(new_op, ia32_am_Dest);
 954         set_ia32_op_type(new_op, ia32_AddrModeD);
 955         set_ia32_am_flavour(new_op, ia32_B);
 956         set_ia32_ls_mode(new_op, mode);
 957         set_ia32_frame_ent(new_op, ent);
 958         set_ia32_use_frame(new_op);
 959
 960         DBG_OPT_SPILL2ST(irn, new_op);
 961
 962         proj = new_rd_Proj(env->dbg, env->irg, env->block, new_op, mode_M, pn_ia32_Store_M);
 963
 964         if (sched_point) {
 965                 sched_add_after(sched_point, new_op);
 966                 sched_remove(irn);
 967         }
 968
 969         SET_IA32_ORIG_NODE(new_op, ia32_get_old_node_name(env->cg, irn));
 970
 971         exchange(irn, proj);
 972 }
 973
 974 static ir_node *create_push(ia32_transform_env_t *env, ir_node *schedpoint, ir_node **sp, ir_node *mem, entity *ent, const char *offset) {
 975         ir_node *noreg = ia32_new_NoReg_gp(env->cg);
 976         ir_mode *spmode = get_irn_mode(*sp);
 977         const arch_register_t *spreg = arch_get_irn_register(env->cg->arch_env, *sp);
 978
 979         ir_node *push = new_rd_ia32_Push(env->dbg, env->irg, env->block, *sp, noreg, mem);
 980
 981         set_ia32_frame_ent(push, ent);
 982         set_ia32_use_frame(push);
 983         set_ia32_op_type(push, ia32_AddrModeS);
 984         set_ia32_am_flavour(push, ia32_B);
 985         set_ia32_ls_mode(push, mode_Is);
 986         if(offset != NULL)
 987                 add_ia32_am_offs(push, offset);
 988
 989         sched_add_before(schedpoint, push);
 990
 991         *sp = new_rd_Proj(env->dbg, env->irg, env->block, push, spmode, 0);
 992         sched_add_before(schedpoint, *sp);
 993         arch_set_irn_register(env->cg->arch_env, *sp, spreg);
 994
 995         return push;
 996 }
 997
 998 static ir_node *create_pop(ia32_transform_env_t *env, ir_node *schedpoint, ir_node **sp, entity *ent, const char *offset) {
 999         ir_mode *spmode = get_irn_mode(*sp);
1000         const arch_register_t *spreg = arch_get_irn_register(env->cg->arch_env, *sp);
1001
1002         ir_node *pop = new_rd_ia32_Pop(env->dbg, env->irg, env->block, *sp, new_NoMem());
1003
1004         set_ia32_frame_ent(pop, ent);
1005         set_ia32_use_frame(pop);
1006         set_ia32_op_type(pop, ia32_AddrModeD);
1007         set_ia32_am_flavour(pop, ia32_B);
1008         set_ia32_ls_mode(pop, mode_Is);
1009         if(offset != NULL)
1010                 add_ia32_am_offs(pop, offset);
1011
1012         sched_add_before(schedpoint, pop);
1013
1014         *sp = new_rd_Proj(env->dbg, env->irg, env->block, pop, spmode, 0);
1015         arch_set_irn_register(env->cg->arch_env, *sp, spreg);
1016         sched_add_before(schedpoint, *sp);
1017
1018         return pop;
1019 }
1020
1021 static void transform_MemPerm(ia32_transform_env_t *env) {
1022         /*
1023          * Transform memperm, currently we do this the ugly way and produce
1024          * push/pop into/from memory cascades. This is possible without using
1025          * any registers.
1026          */
1027         ir_node *node = env->irn;
1028         int i, arity;
1029         ir_node *noreg = ia32_new_NoReg_gp(env->cg);
1030         ir_node *sp = get_irn_n(node, 0);
1031         const arch_register_t *spreg = arch_get_irn_register(env->cg->arch_env, sp);
1032         const ir_edge_t *edge;
1033         const ir_edge_t *next;
1034         ir_node **pops;
1035         ir_mode *spmode = get_irn_mode(sp);
1036
1037         arity = be_get_MemPerm_entity_arity(node);
1038         pops = alloca(arity * sizeof(pops[0]));
1039
1040         // create pushs
1041         for(i = 0; i < arity; ++i) {
1042                 entity *ent = be_get_MemPerm_in_entity(node, i);
1043                 ir_type *enttype = get_entity_type(ent);
1044                 int entbits = get_type_size_bits(enttype);
1045                 ir_node *mem = get_irn_n(node, i + 1);
1046
1047                 assert( (entbits == 32 || entbits == 64) && "spillslot on x86 should be 32 or 64 bit");
1048
1049                 create_push(env, node, &sp, mem, ent, NULL);
1050                 if(entbits == 64) {
1051                         // add another push after the first one
1052                         create_push(env, node, &sp, mem, ent, "4");
1053                 }
1054
1055                 set_irn_n(node, i, new_Bad());
1056         }
1057
1058         // create pops
1059         for(i = arity - 1; i >= 0; --i) {
1060                 entity *ent = be_get_MemPerm_out_entity(node, i);
1061                 ir_type *enttype = get_entity_type(ent);
1062                 int entbits = get_type_size_bits(enttype);
1063
1064                 ir_node *pop;
1065
1066                 assert( (entbits == 32 || entbits == 64) && "spillslot on x86 should be 32 or 64 bit");
1067
1068                 pop = create_pop(env, node, &sp, ent, NULL);
1069                 if(entbits == 64) {
1070                         // add another push after the first one
1071                         pop = create_pop(env, node, &sp, ent, "4");
1072                 }
1073
1074                 pops[i] = pop;
1075         }
1076
1077         // exchange memprojs
1078         foreach_out_edge_safe(node, edge, next) {
1079                 ir_node *proj = get_edge_src_irn(edge);
1080                 int p = get_Proj_proj(proj);
1081
1082                 assert(p < arity);
1083
1084                 set_Proj_pred(proj, pops[p]);
1085                 set_Proj_proj(proj, 3);
1086         }
1087
1088         sched_remove(node);
1089 }
1090
1091 /**
1092  * Fix the mode of Spill/Reload
1093  */
1094 static ir_mode *fix_spill_mode(ia32_code_gen_t *cg, ir_mode *mode)
1095 {
1096         if (mode_is_float(mode)) {
1097                 if (USE_SSE2(cg))
1098                         mode = mode_D;
1099                 else
1100                         mode = mode_E;
1101         }
1102         else
1103                 mode = mode_Is;
1104         return mode;
1105 }
1106
1107 /**
1108  * Block-Walker: Calls the transform functions Spill and Reload.
1109  */
1110 static void ia32_after_ra_walker(ir_node *block, void *env) {
1111         ir_node *node, *prev;
1112         ia32_code_gen_t *cg = env;
1113         ia32_transform_env_t tenv;
1114
1115         tenv.block = block;
1116         tenv.irg   = current_ir_graph;
1117         tenv.cg    = cg;
1118         DEBUG_ONLY(tenv.mod = cg->mod;)
1119
1120         /* beware: the schedule is changed here */
1121         for (node = sched_last(block); !sched_is_begin(node); node = prev) {
1122                 prev = sched_prev(node);
1123                 if (be_is_Reload(node)) {
1124                         /* we always reload the whole register  */
1125                         tenv.dbg  = get_irn_dbg_info(node);
1126                         tenv.irn  = node;
1127                         tenv.mode = fix_spill_mode(cg, get_irn_mode(node));
1128                         transform_to_Load(&tenv);
1129                 }
1130                 else if (be_is_Spill(node)) {
1131                         ir_node *spillval = get_irn_n(node, be_pos_Spill_val);
1132                         /* we always spill the whole register  */
1133                         tenv.dbg  = get_irn_dbg_info(node);
1134                         tenv.irn  = node;
1135                         tenv.mode = fix_spill_mode(cg, get_irn_mode(spillval));
1136                         transform_to_Store(&tenv);
1137                 }
1138                 else if(be_is_MemPerm(node)) {
1139                         tenv.dbg = get_irn_dbg_info(node);
1140                         tenv.irn = node;
1141                         transform_MemPerm(&tenv);
1142                 }
1143         }
1144 }
1145
1146 /**
1147  * We transform Spill and Reload here. This needs to be done before
1148  * stack biasing otherwise we would miss the corrected offset for these nodes.
1149  *
1150  * If x87 instruction should be emitted, run the x87 simulator and patch
1151  * the virtual instructions. This must obviously be done after register allocation.
1152  */
1153 static void ia32_after_ra(void *self) {
1154         ia32_code_gen_t *cg = self;
1155
1156         irg_block_walk_graph(cg->irg, NULL, ia32_after_ra_walker, self);
1157
1158         /* if we do x87 code generation, rewrite all the virtual instructions and registers */
1159         if (cg->used_fp == fp_x87 || cg->force_sim) {
1160                 x87_simulate_graph(cg->arch_env, cg->irg, cg->blk_sched);
1161         }
1162 }
1163
1164 /**
1165  * Last touchups for the graph before emit
1166  */
1167 static void ia32_finish(void *self) {
1168         ia32_code_gen_t *cg = self;
1169         ir_graph        *irg = cg->irg;
1170
1171         ia32_finish_irg(irg, cg);
1172 }
1173
1174 /**
1175  * Emits the code, closes the output file and frees
1176  * the code generator interface.
1177  */
1178 static void ia32_codegen(void *self) {
1179         ia32_code_gen_t *cg = self;
1180         ir_graph        *irg = cg->irg;
1181
1182         ia32_gen_routine(cg->isa->out, irg, cg);
1183
1184         cur_reg_set = NULL;
1185
1186         /* remove it from the isa */
1187         cg->isa->cg = NULL;
1188
1189         /* de-allocate code generator */
1190         del_set(cg->reg_set);
1191         free(self);
1192 }
1193
1194 static void *ia32_cg_init(const be_irg_t *birg);
1195
1196 static const arch_code_generator_if_t ia32_code_gen_if = {
1197         ia32_cg_init,
1198         NULL,                /* before abi introduce hook */
1199         ia32_prepare_graph,
1200         ia32_before_sched,   /* before scheduling hook */
1201         ia32_before_ra,      /* before register allocation hook */
1202         ia32_after_ra,       /* after register allocation hook */
1203         ia32_finish,         /* called before codegen */
1204         ia32_codegen         /* emit && done */
1205 };
1206
1207 /**
1208  * Initializes a IA32 code generator.
1209  */
1210 static void *ia32_cg_init(const be_irg_t *birg) {
1211         ia32_isa_t      *isa = (ia32_isa_t *)birg->main_env->arch_env->isa;
1212         ia32_code_gen_t *cg  = xcalloc(1, sizeof(*cg));
1213
1214         cg->impl      = &ia32_code_gen_if;
1215         cg->irg       = birg->irg;
1216         cg->reg_set   = new_set(ia32_cmp_irn_reg_assoc, 1024);
1217         cg->arch_env  = birg->main_env->arch_env;
1218         cg->isa       = isa;
1219         cg->birg      = birg;
1220         cg->blk_sched = NULL;
1221         cg->fp_to_gp  = NULL;
1222         cg->gp_to_fp  = NULL;
1223         cg->fp_kind   = isa->fp_kind;
1224         cg->used_fp   = fp_none;
1225         cg->dump      = (birg->main_env->options->dump_flags & DUMP_BE) ? 1 : 0;
1226
1227         FIRM_DBG_REGISTER(cg->mod, "firm.be.ia32.cg");
1228
1229         /* copy optimizations from isa for easier access */
1230         cg->opt      = isa->opt;
1231         cg->arch     = isa->arch;
1232         cg->opt_arch = isa->opt_arch;
1233
1234         /* enter it */
1235         isa->cg = cg;
1236
1237 #ifndef NDEBUG
1238         if (isa->name_obst_size) {
1239                 //printf("freed %d bytes from name obst\n", isa->name_obst_size);
1240                 isa->name_obst_size = 0;
1241                 obstack_free(isa->name_obst, NULL);
1242                 obstack_init(isa->name_obst);
1243         }
1244 #endif /* NDEBUG */
1245
1246         cur_reg_set = cg->reg_set;
1247
1248         ia32_irn_ops.cg = cg;
1249
1250         return (arch_code_generator_t *)cg;
1251 }
1252
1253
1254
1255 /*****************************************************************
1256  *  ____             _                  _   _____  _____
1257  * |  _ \           | |                | | |_   _|/ ____|  /\
1258  * | |_) | __ _  ___| | _____ _ __   __| |   | | | (___   /  \
1259  * |  _ < / _` |/ __| |/ / _ \ '_ \ / _` |   | |  \___ \ / /\ \
1260  * | |_) | (_| | (__|   <  __/ | | | (_| |  _| |_ ____) / ____ \
1261  * |____/ \__,_|\___|_|\_\___|_| |_|\__,_| |_____|_____/_/    \_\
1262  *
1263  *****************************************************************/
1264
1265 /**
1266  * Set output modes for GCC
1267  */
1268 static const tarval_mode_info mo_integer = {
1269         TVO_DECIMAL,
1270         NULL,
1271         NULL,
1272 };
1273
1274 /*
1275 * set the tarval output mode to C-semantics
1276 */
1277 static void set_tarval_output_modes(void)
1278 {
1279         set_tarval_mode_output_option(get_modeLs(), &mo_integer);
1280         set_tarval_mode_output_option(get_modeLu(), &mo_integer);
1281         set_tarval_mode_output_option(get_modeIs(), &mo_integer);
1282         set_tarval_mode_output_option(get_modeIu(), &mo_integer);
1283         set_tarval_mode_output_option(get_modeHs(), &mo_integer);
1284         set_tarval_mode_output_option(get_modeHu(), &mo_integer);
1285         set_tarval_mode_output_option(get_modeBs(), &mo_integer);
1286         set_tarval_mode_output_option(get_modeBu(), &mo_integer);
1287         set_tarval_mode_output_option(get_modeC(),  &mo_integer);
1288         set_tarval_mode_output_option(get_modeU(),  &mo_integer);
1289         set_tarval_mode_output_option(get_modeIu(), &mo_integer);
1290 }
1291
1292
1293 /**
1294  * The template that generates a new ISA object.
1295  * Note that this template can be changed by command line
1296  * arguments.
1297  */
1298 static ia32_isa_t ia32_isa_template = {
1299         {
1300                 &ia32_isa_if,            /* isa interface implementation */
1301                 &ia32_gp_regs[REG_ESP],  /* stack pointer register */
1302                 &ia32_gp_regs[REG_EBP],  /* base pointer register */
1303                 -1,                      /* stack direction */
1304         },
1305         NULL,                    /* 16bit register names */
1306         NULL,                    /* 8bit register names */
1307         NULL,                    /* types */
1308         NULL,                    /* tv_ents */
1309         (0                 |
1310         IA32_OPT_INCDEC    |     /* optimize add 1, sub 1 into inc/dec               default: on  */
1311         IA32_OPT_DOAM      |     /* optimize address mode                            default: on  */
1312         IA32_OPT_LEA       |     /* optimize for LEAs                                default: on  */
1313         IA32_OPT_PLACECNST |     /* place constants immediately before instructions, default: on  */
1314         IA32_OPT_IMMOPS    |     /* operations can use immediates,                   default: on  */
1315         IA32_OPT_EXTBB),         /* use extended basic block scheduling,             default: on  */
1316         arch_pentium_4,          /* instruction architecture */
1317         arch_pentium_4,          /* optimize for architecture */
1318         fp_sse2,                 /* use sse2 unit */
1319         NULL,                    /* current code generator */
1320 #ifndef NDEBUG
1321         NULL,                    /* name obstack */
1322         0                        /* name obst size */
1323 #endif
1324 };
1325
1326 /**
1327  * Initializes the backend ISA.
1328  */
1329 static void *ia32_init(FILE *file_handle) {
1330         static int inited = 0;
1331         ia32_isa_t *isa;
1332
1333         if (inited)
1334                 return NULL;
1335
1336         set_tarval_output_modes();
1337
1338         isa = xmalloc(sizeof(*isa));
1339         memcpy(isa, &ia32_isa_template, sizeof(*isa));
1340
1341         ia32_register_init(isa);
1342         ia32_create_opcodes();
1343
1344         if ((ARCH_INTEL(isa->arch) && isa->arch < arch_pentium_4) ||
1345             (ARCH_AMD(isa->arch) && isa->arch < arch_athlon))
1346                 /* no SSE2 for these cpu's */
1347                 isa->fp_kind = fp_x87;
1348
1349         if (ARCH_INTEL(isa->opt_arch) && isa->opt_arch >= arch_pentium_4) {
1350                 /* Pentium 4 don't like inc and dec instructions */
1351                 isa->opt &= ~IA32_OPT_INCDEC;
1352         }
1353
1354         isa->regs_16bit = pmap_create();
1355         isa->regs_8bit  = pmap_create();
1356         isa->types      = pmap_create();
1357         isa->tv_ent     = pmap_create();
1358         isa->out        = file_handle;
1359
1360         ia32_build_16bit_reg_map(isa->regs_16bit);
1361         ia32_build_8bit_reg_map(isa->regs_8bit);
1362
1363         /* patch register names of x87 registers */
1364         if (USE_x87(isa)) {
1365                 ia32_st_regs[0].name = "st";
1366                 ia32_st_regs[1].name = "st(1)";
1367                 ia32_st_regs[2].name = "st(2)";
1368                 ia32_st_regs[3].name = "st(3)";
1369                 ia32_st_regs[4].name = "st(4)";
1370                 ia32_st_regs[5].name = "st(5)";
1371                 ia32_st_regs[6].name = "st(6)";
1372                 ia32_st_regs[7].name = "st(7)";
1373         }
1374
1375 #ifndef NDEBUG
1376         isa->name_obst = xmalloc(sizeof(*isa->name_obst));
1377         obstack_init(isa->name_obst);
1378         isa->name_obst_size = 0;
1379 #endif /* NDEBUG */
1380
1381         ia32_handle_intrinsics();
1382         ia32_switch_section(NULL, NO_SECTION);
1383         fprintf(isa->out, "\t.intel_syntax\n");
1384
1385         inited = 1;
1386
1387         return isa;
1388 }
1389
1390
1391
1392 /**
1393  * Closes the output file and frees the ISA structure.
1394  */
1395 static void ia32_done(void *self) {
1396         ia32_isa_t *isa = self;
1397
1398         /* emit now all global declarations */
1399         ia32_gen_decls(isa->out);
1400
1401         pmap_destroy(isa->regs_16bit);
1402         pmap_destroy(isa->regs_8bit);
1403         pmap_destroy(isa->tv_ent);
1404         pmap_destroy(isa->types);
1405
1406 #ifndef NDEBUG
1407         //printf("name obst size = %d bytes\n", isa->name_obst_size);
1408         obstack_free(isa->name_obst, NULL);
1409 #endif /* NDEBUG */
1410
1411         free(self);
1412 }
1413
1414
1415 /**
1416  * Return the number of register classes for this architecture.
1417  * We report always these:
1418  *  - the general purpose registers
1419  *  - the SSE floating point register set
1420  *  - the virtual floating point registers
1421  */
1422 static int ia32_get_n_reg_class(const void *self) {
1423         return 3;
1424 }
1425
1426 /**
1427  * Return the register class for index i.
1428  */
1429 static const arch_register_class_t *ia32_get_reg_class(const void *self, int i) {
1430         assert(i >= 0 && i < 3 && "Invalid ia32 register class requested.");
1431         if (i == 0)
1432                 return &ia32_reg_classes[CLASS_ia32_gp];
1433         else if (i == 1)
1434                 return &ia32_reg_classes[CLASS_ia32_xmm];
1435         else
1436                 return &ia32_reg_classes[CLASS_ia32_vfp];
1437 }
1438
1439 /**
1440  * Get the register class which shall be used to store a value of a given mode.
1441  * @param self The this pointer.
1442  * @param mode The mode in question.
1443  * @return A register class which can hold values of the given mode.
1444  */
1445 const arch_register_class_t *ia32_get_reg_class_for_mode(const void *self, const ir_mode *mode) {
1446         const ia32_isa_t *isa = self;
1447         if (mode_is_float(mode)) {
1448                 return USE_SSE2(isa) ? &ia32_reg_classes[CLASS_ia32_xmm] : &ia32_reg_classes[CLASS_ia32_vfp];
1449         }
1450         else
1451                 return &ia32_reg_classes[CLASS_ia32_gp];
1452 }
1453
1454 /**
1455  * Get the ABI restrictions for procedure calls.
1456  * @param self        The this pointer.
1457  * @param method_type The type of the method (procedure) in question.
1458  * @param abi         The abi object to be modified
1459  */
1460 static void ia32_get_call_abi(const void *self, ir_type *method_type, be_abi_call_t *abi) {
1461         const ia32_isa_t *isa = self;
1462         ir_type  *tp;
1463         ir_mode  *mode;
1464         unsigned  cc        = get_method_calling_convention(method_type);
1465         int       n         = get_method_n_params(method_type);
1466         int       biggest_n = -1;
1467         int       stack_idx = 0;
1468         int       i, ignore_1, ignore_2;
1469         ir_mode **modes;
1470         const arch_register_t *reg;
1471         be_abi_call_flags_t call_flags = be_abi_call_get_flags(abi);
1472
1473         unsigned use_push = !IS_P6_ARCH(isa->opt_arch);
1474
1475         /* set abi flags for calls */
1476         call_flags.bits.left_to_right         = 0;  /* always last arg first on stack */
1477         call_flags.bits.store_args_sequential = use_push;
1478         /* call_flags.bits.try_omit_fp                 not changed: can handle both settings */
1479         call_flags.bits.fp_free               = 0;  /* the frame pointer is fixed in IA32 */
1480         call_flags.bits.call_has_imm          = 1;  /* IA32 calls can have immediate address */
1481
1482         /* set stack parameter passing style */
1483         be_abi_call_set_flags(abi, call_flags, &ia32_abi_callbacks);
1484
1485         /* collect the mode for each type */
1486         modes = alloca(n * sizeof(modes[0]));
1487
1488         for (i = 0; i < n; i++) {
1489                 tp       = get_method_param_type(method_type, i);
1490                 modes[i] = get_type_mode(tp);
1491         }
1492
1493         /* set register parameters  */
1494         if (cc & cc_reg_param) {
1495                 /* determine the number of parameters passed via registers */
1496                 biggest_n = ia32_get_n_regparam_class(n, modes, &ignore_1, &ignore_2);
1497
1498                 /* loop over all parameters and set the register requirements */
1499                 for (i = 0; i <= biggest_n; i++) {
1500                         reg = ia32_get_RegParam_reg(n, modes, i, cc);
1501                         assert(reg && "kaputt");
1502                         be_abi_call_param_reg(abi, i, reg);
1503                 }
1504
1505                 stack_idx = i;
1506         }
1507
1508
1509         /* set stack parameters */
1510         for (i = stack_idx; i < n; i++) {
1511                 be_abi_call_param_stack(abi, i, 1, 0, 0);
1512         }
1513
1514
1515         /* set return registers */
1516         n = get_method_n_ress(method_type);
1517
1518         assert(n <= 2 && "more than two results not supported");
1519
1520         /* In case of 64bit returns, we will have two 32bit values */
1521         if (n == 2) {
1522                 tp   = get_method_res_type(method_type, 0);
1523                 mode = get_type_mode(tp);
1524
1525                 assert(!mode_is_float(mode) && "two FP results not supported");
1526
1527                 tp   = get_method_res_type(method_type, 1);
1528                 mode = get_type_mode(tp);
1529
1530                 assert(!mode_is_float(mode) && "two FP results not supported");
1531
1532                 be_abi_call_res_reg(abi, 0, &ia32_gp_regs[REG_EAX]);
1533                 be_abi_call_res_reg(abi, 1, &ia32_gp_regs[REG_EDX]);
1534         }
1535         else if (n == 1) {
1536                 const arch_register_t *reg;
1537
1538                 tp   = get_method_res_type(method_type, 0);
1539                 assert(is_atomic_type(tp));
1540                 mode = get_type_mode(tp);
1541
1542                 reg = mode_is_float(mode) ?
1543                         (USE_SSE2(isa) ? &ia32_xmm_regs[REG_XMM0] : &ia32_vfp_regs[REG_VF0]) :
1544                         &ia32_gp_regs[REG_EAX];
1545
1546                 be_abi_call_res_reg(abi, 0, reg);
1547         }
1548 }
1549
1550
1551 static const void *ia32_get_irn_ops(const arch_irn_handler_t *self, const ir_node *irn) {
1552         return &ia32_irn_ops;
1553 }
1554
1555 const arch_irn_handler_t ia32_irn_handler = {
1556         ia32_get_irn_ops
1557 };
1558
1559 const arch_irn_handler_t *ia32_get_irn_handler(const void *self) {
1560         return &ia32_irn_handler;
1561 }
1562
1563 int ia32_to_appear_in_schedule(void *block_env, const ir_node *irn) {
1564         return is_ia32_irn(irn) ? 1 : -1;
1565 }
1566
1567 /**
1568  * Initializes the code generator interface.
1569  */
1570 static const arch_code_generator_if_t *ia32_get_code_generator_if(void *self) {
1571         return &ia32_code_gen_if;
1572 }
1573
1574 list_sched_selector_t ia32_sched_selector;
1575
1576 /**
1577  * Returns the reg_pressure scheduler with to_appear_in_schedule() overloaded
1578  */
1579 static const list_sched_selector_t *ia32_get_list_sched_selector(const void *self) {
1580 //      memcpy(&ia32_sched_selector, reg_pressure_selector, sizeof(list_sched_selector_t));
1581         memcpy(&ia32_sched_selector, trivial_selector, sizeof(list_sched_selector_t));
1582         ia32_sched_selector.to_appear_in_schedule = ia32_to_appear_in_schedule;
1583         return &ia32_sched_selector;
1584 }
1585
1586 /**
1587  * Returns the necessary byte alignment for storing a register of given class.
1588  */
1589 static int ia32_get_reg_class_alignment(const void *self, const arch_register_class_t *cls) {
1590         ir_mode *mode = arch_register_class_mode(cls);
1591         int bytes     = get_mode_size_bytes(mode);
1592
1593         if (mode_is_float(mode) && bytes > 8)
1594                 return 16;
1595         return bytes;
1596 }
1597
1598 static ia32_intrinsic_env_t intrinsic_env = { NULL, NULL };
1599
1600 /**
1601  * Returns the libFirm configuration parameter for this backend.
1602  */
1603 static const backend_params *ia32_get_libfirm_params(void) {
1604         static const arch_dep_params_t ad = {
1605                 1, /* also use subs */
1606                 4, /* maximum shifts */
1607                 31, /* maximum shift amount */
1608
1609                 1, /* allow Mulhs */
1610                 1, /* allow Mulus */
1611                 32  /* Mulh allowed up to 32 bit */
1612         };
1613         static backend_params p = {
1614                 NULL,  /* no additional opcodes */
1615                 NULL,  /* will be set later */
1616                 1,     /* need dword lowering */
1617                 ia32_create_intrinsic_fkt,
1618                 &intrinsic_env,  /* context for ia32_create_intrinsic_fkt */
1619         };
1620
1621         p.dep_param = &ad;
1622         return &p;
1623 }
1624 #ifdef WITH_LIBCORE
1625
1626 /* instruction set architectures. */
1627 static const lc_opt_enum_int_items_t arch_items[] = {
1628         { "386",        arch_i386, },
1629         { "486",        arch_i486, },
1630         { "pentium",    arch_pentium, },
1631         { "586",        arch_pentium, },
1632         { "pentiumpro", arch_pentium_pro, },
1633         { "686",        arch_pentium_pro, },
1634         { "pentiummmx", arch_pentium_mmx, },
1635         { "pentium2",   arch_pentium_2, },
1636         { "p2",         arch_pentium_2, },
1637         { "pentium3",   arch_pentium_3, },
1638         { "p3",         arch_pentium_3, },
1639         { "pentium4",   arch_pentium_4, },
1640         { "p4",         arch_pentium_4, },
1641         { "pentiumm",   arch_pentium_m, },
1642         { "pm",         arch_pentium_m, },
1643         { "core",       arch_core, },
1644         { "k6",         arch_k6, },
1645         { "athlon",     arch_athlon, },
1646         { "athlon64",   arch_athlon_64, },
1647         { "opteron",    arch_opteron, },
1648         { NULL,         0 }
1649 };
1650
1651 static lc_opt_enum_int_var_t arch_var = {
1652         &ia32_isa_template.arch, arch_items
1653 };
1654
1655 static lc_opt_enum_int_var_t opt_arch_var = {
1656         &ia32_isa_template.opt_arch, arch_items
1657 };
1658
1659 static const lc_opt_enum_int_items_t fp_unit_items[] = {
1660         { "x87" ,    fp_x87 },
1661         { "sse2",    fp_sse2 },
1662         { NULL,      0 }
1663 };
1664
1665 static lc_opt_enum_int_var_t fp_unit_var = {
1666         &ia32_isa_template.fp_kind, fp_unit_items
1667 };
1668
1669 static const lc_opt_enum_int_items_t gas_items[] = {
1670         { "linux",   ASM_LINUX_GAS },
1671         { "mingw",   ASM_MINGW_GAS },
1672         { NULL,      0 }
1673 };
1674
1675 static lc_opt_enum_int_var_t gas_var = {
1676         (int *)&asm_flavour, gas_items
1677 };
1678
1679 static const lc_opt_table_entry_t ia32_options[] = {
1680         LC_OPT_ENT_ENUM_INT("arch",      "select the instruction architecture", &arch_var),
1681         LC_OPT_ENT_ENUM_INT("opt",       "optimize for instruction architecture", &opt_arch_var),
1682         LC_OPT_ENT_ENUM_INT("fpunit",    "select the floating point unit", &fp_unit_var),
1683         LC_OPT_ENT_NEGBIT("noaddrmode",  "do not use address mode", &ia32_isa_template.opt, IA32_OPT_DOAM),
1684         LC_OPT_ENT_NEGBIT("nolea",       "do not optimize for LEAs", &ia32_isa_template.opt, IA32_OPT_LEA),
1685         LC_OPT_ENT_NEGBIT("noplacecnst", "do not place constants", &ia32_isa_template.opt, IA32_OPT_PLACECNST),
1686         LC_OPT_ENT_NEGBIT("noimmop",     "no operations with immediates", &ia32_isa_template.opt, IA32_OPT_IMMOPS),
1687         LC_OPT_ENT_NEGBIT("noextbb",     "do not use extended basic block scheduling", &ia32_isa_template.opt, IA32_OPT_EXTBB),
1688         LC_OPT_ENT_ENUM_INT("gasmode",   "set the GAS compatibility mode", &gas_var),
1689         { NULL }
1690 };
1691
1692 /**
1693  * Register command line options for the ia32 backend.
1694  *
1695  * Options so far:
1696  *
1697  * ia32-arch=arch    create instruction for arch
1698  * ia32-opt=arch     optimize for run on arch
1699  * ia32-fpunit=unit  select floating point unit (x87 or SSE2)
1700  * ia32-incdec       optimize for inc/dec
1701  * ia32-noaddrmode   do not use address mode
1702  * ia32-nolea        do not optimize for LEAs
1703  * ia32-noplacecnst  do not place constants,
1704  * ia32-noimmop      no operations with immediates
1705  * ia32-noextbb      do not use extended basic block scheduling
1706  * ia32-gasmode      set the GAS compatibility mode
1707  */
1708 static void ia32_register_options(lc_opt_entry_t *ent)
1709 {
1710         lc_opt_entry_t *be_grp_ia32 = lc_opt_get_grp(ent, "ia32");
1711         lc_opt_add_table(be_grp_ia32, ia32_options);
1712 }
1713 #endif /* WITH_LIBCORE */
1714
1715 const arch_isa_if_t ia32_isa_if = {
1716         ia32_init,
1717         ia32_done,
1718         ia32_get_n_reg_class,
1719         ia32_get_reg_class,
1720         ia32_get_reg_class_for_mode,
1721         ia32_get_call_abi,
1722         ia32_get_irn_handler,
1723         ia32_get_code_generator_if,
1724         ia32_get_list_sched_selector,
1725         ia32_get_reg_class_alignment,
1726         ia32_get_libfirm_params,
1727 #ifdef WITH_LIBCORE
1728         ia32_register_options
1729 #endif
1730 };