nsz Git - libfirm/blob - ir/lower/lower_dw.c

   1 /**
   2  * @file irlwrdw.c
   3  * @date 8.10.2004
   4  * @author Michael Beck
   5  * @brief Lower Double word operations, ie Mode L -> I.
   6  *
   7  * $Id$
   8  */
   9 #ifdef HAVE_CONFIG_H
  10 # include "config.h"
  11 #endif
  12
  13 #ifdef HAVE_MALLOC_H
  14 # include <malloc.h>
  15 #endif
  16 #ifdef HAVE_ALLOCA_H
  17 # include <alloca.h>
  18 #endif
  19 #ifdef HAVE_STRING_H
  20 # include <string.h>
  21 #endif
  22 #ifdef HAVE_STDLIB_H
  23 # include <stdlib.h>
  24 #endif
  25
  26 #include <assert.h>
  27
  28 #include "irnode_t.h"
  29 #include "irgraph_t.h"
  30 #include "irmode_t.h"
  31 #include "iropt_t.h"
  32 #include "irgmod.h"
  33 #include "tv_t.h"
  34 #include "dbginfo_t.h"
  35 #include "iropt_dbg.h"
  36 #include "irflag_t.h"
  37 #include "firmstat.h"
  38 #include "irgwalk.h"
  39 #include "ircons.h"
  40 #include "lower_dw.h"
  41 #include "irflag.h"
  42 #include "irtools.h"
  43 #include "debug.h"
  44 #include "set.h"
  45 #include "pmap.h"
  46 #include "pdeq.h"
  47
  48 /** A map from ir_op to Intrinsic functions entities. */
  49 static set *intrinsic_fkt;
  50
  51 /** A map from a method type to its lowered type. */
  52 static pmap *lowered_type;
  53
  54 /** The types for the binop and unop intrinsics. */
  55 static ir_type *binop_tp_u, *binop_tp_s, *unop_tp_u, *unop_tp_s, *tp_s, *tp_u;
  56
  57 /** the debug handle */
  58 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  59
  60 /**
  61  * An entry in the (op, mode) -> entity map.
  62  */
  63 typedef struct _op_mode_entry {
  64         const ir_op   *op;    /**< the op */
  65         const ir_mode *mode;  /**< the mode */
  66         entity        *ent;   /**< the associated entity of this (op, mode) pair */
  67 } op_mode_entry_t;
  68
  69 /**
  70  * Every double word node will be replaced,
  71  * we need some store to hold the replacement:
  72  */
  73 typedef struct _node_entry_t {
  74         ir_node *low_word;        /**< the low word */
  75         ir_node *high_word;       /**< the high word */
  76 } node_entry_t;
  77
  78 enum lower_flags {
  79         MUST_BE_LOWERED = 1,   /**< graph must be lowered */
  80         CF_CHANGED      = 2,   /**< control flow was changed */
  81 };
  82
  83 /**
  84  * The lower environment.
  85  */
  86 typedef struct _lower_env_t {
  87         node_entry_t **entries;       /**< entries per node */
  88         struct obstack obst;          /**< an obstack holding the temporary data */
  89         tarval   *tv_mode_bytes;      /**< a tarval containing the number of bits in the lowered modes */
  90         pdeq     *waitq;              /**< a wait queue of all nodes that must be handled later */
  91         pmap     *proj_2_block;       /**< a map from ProjX to its destination blocks */
  92         const lwrdw_param_t *params;  /**< transformation parameter */
  93         unsigned flags;               /**< some flags */
  94         int      n_entries;           /**< number of entries */
  95 } lower_env_t;
  96
  97 /**
  98  * Add an additional control flow input to a block.
  99  * Patch all Phi nodes. The new Phi inputs are copied from
 100  * old input number nr.
 101  */
 102 static void add_block_cf_input_nr(ir_node *block, int nr, ir_node *cf)
 103 {
 104         int i, arity = get_irn_arity(block);
 105         ir_node **in, *phi;
 106
 107         assert(nr < arity);
 108
 109         NEW_ARR_A(ir_node *, in, arity + 1);
 110         for (i = 0; i < arity; ++i)
 111                 in[i] = get_irn_n(block, i);
 112         in[i] = cf;
 113
 114         set_irn_in(block, i + 1, in);
 115
 116         for (phi = get_irn_link(block); phi; phi = get_irn_link(phi)) {
 117                 for (i = 0; i < arity; ++i)
 118                         in[i] = get_irn_n(phi, i);
 119                 in[i] = in[nr];
 120                 set_irn_in(phi, i + 1, in);
 121         }
 122 }
 123
 124 /**
 125  * Add an additional control flow input to a block.
 126  * Patch all Phi nodes. The new Phi inputs are copied from
 127  * old input from cf tmpl.
 128  */
 129 static void add_block_cf_input(ir_node *block, ir_node *tmpl, ir_node *cf)
 130 {
 131         int i, arity = get_irn_arity(block);
 132         int nr = 0;
 133
 134         for (i = 0; i < arity; ++i) {
 135                 if (get_irn_n(block, i) == tmpl) {
 136                         nr = i;
 137                         break;
 138                 }
 139         }
 140         assert(i < arity);
 141         add_block_cf_input_nr(block, nr, cf);
 142 }
 143
 144 /**
 145  * Return the "operational" mode of a Firm node.
 146  */
 147 static ir_mode *get_irn_op_mode(ir_node *node)
 148 {
 149         switch (get_irn_opcode(node)) {
 150         case iro_Load:
 151                 return get_Load_mode(node);
 152
 153         case iro_Store:
 154                 return get_irn_mode(get_Store_value(node));
 155
 156         case iro_DivMod:
 157                 return get_irn_mode(get_DivMod_left(node));
 158
 159         case iro_Div:
 160                 return get_irn_mode(get_Div_left(node));
 161
 162         case iro_Mod:
 163                 return get_irn_mode(get_Mod_left(node));
 164
 165         case iro_Cmp:
 166                 return get_irn_mode(get_Cmp_left(node));
 167
 168         default:
 169                 return get_irn_mode(node);
 170         }
 171 }
 172
 173 /**
 174  * walker, prepare the node links
 175  */
 176 static void prepare_links(ir_node *node, void *env)
 177 {
 178         lower_env_t  *lenv = env;
 179         ir_mode      *mode = get_irn_op_mode(node);
 180         node_entry_t *link;
 181         int          i;
 182
 183         if (mode == lenv->params->high_signed ||
 184                 mode == lenv->params->high_unsigned) {
 185                 /* ok, found a node that will be lowered */
 186                 link = obstack_alloc(&lenv->obst, sizeof(*link));
 187
 188                 memset(link, 0, sizeof(*link));
 189
 190                 lenv->entries[get_irn_idx(node)] = link;
 191                 lenv->flags |= MUST_BE_LOWERED;
 192         }
 193         else if (get_irn_op(node) == op_Conv) {
 194                 /* Conv nodes have two modes */
 195                 ir_node *pred = get_Conv_op(node);
 196                 mode = get_irn_mode(pred);
 197
 198                 if (mode == lenv->params->high_signed ||
 199                         mode == lenv->params->high_unsigned) {
 200                         /* must lower this node either */
 201                         link = obstack_alloc(&lenv->obst, sizeof(*link));
 202
 203                         memset(link, 0, sizeof(*link));
 204
 205                         lenv->entries[get_irn_idx(node)] = link;
 206                         lenv->flags |= MUST_BE_LOWERED;
 207                 }
 208                 return;
 209         }
 210
 211         if (is_Proj(node)) {
 212                 /* link all Proj nodes to its predecessor:
 213                    Note that Tuple Proj's and its Projs are linked either. */
 214                 ir_node *pred = get_Proj_pred(node);
 215
 216                 set_irn_link(node, get_irn_link(pred));
 217                 set_irn_link(pred, node);
 218         }
 219         else if (is_Phi(node)) {
 220                 /* link all Phi nodes to its block */
 221                 ir_node *block = get_nodes_block(node);
 222
 223                 set_irn_link(node, get_irn_link(block));
 224                 set_irn_link(block, node);
 225         }
 226         else if (is_Block(node)) {
 227                 /* fill the Proj -> Block map */
 228                 for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
 229                         ir_node *pred = get_Block_cfgpred(node, i);
 230
 231                         if (is_Proj(pred))
 232                                 pmap_insert(lenv->proj_2_block, pred, node);
 233                 }
 234         }
 235 }
 236
 237 /**
 238  * Translate a Constant: create two.
 239  */
 240 static void lower_Const(ir_node *node, ir_mode *mode, lower_env_t *env) {
 241         tarval   *tv, *tv_l, *tv_h;
 242         ir_node  *low, *high;
 243         dbg_info *dbg = get_irn_dbg_info(node);
 244         ir_node  *block = get_nodes_block(node);
 245         int      idx;
 246
 247         tv   = get_Const_tarval(node);
 248
 249         tv_l = tarval_convert_to(tv, mode);
 250         low  = new_rd_Const(dbg, current_ir_graph, block, mode, tv_l);
 251
 252         tv_h = tarval_convert_to(tarval_shrs(tv, env->tv_mode_bytes), mode);
 253         high = new_rd_Const(dbg, current_ir_graph, block, mode, tv_h);
 254
 255         idx = get_irn_idx(node);
 256         assert(idx < env->n_entries);
 257         env->entries[idx]->low_word  = low;
 258         env->entries[idx]->high_word = high;
 259 }
 260
 261 /**
 262  * Translate a Load: create two.
 263  */
 264 static void lower_Load(ir_node *node, ir_mode *mode, lower_env_t *env) {
 265         ir_graph *irg = current_ir_graph;
 266         ir_node  *adr = get_Load_ptr(node);
 267         ir_node  *mem = get_Load_mem(node);
 268         ir_node  *low, *high, *proj;
 269         dbg_info *dbg;
 270         ir_node  *block = get_nodes_block(node);
 271         int      idx;
 272
 273         if (env->params->little_endian) {
 274                 low  = adr;
 275                 high = new_r_Add(irg, block, adr,
 276                         new_r_Const(irg, block, get_tarval_mode(env->tv_mode_bytes), env->tv_mode_bytes),
 277                         get_irn_mode(adr));
 278         }
 279         else {
 280                 low  = new_r_Add(irg, block, adr,
 281                         new_r_Const(irg, block, get_tarval_mode(env->tv_mode_bytes), env->tv_mode_bytes),
 282                         get_irn_mode(adr));
 283                 high = adr;
 284         }
 285
 286         /* create two loads */
 287         dbg  = get_irn_dbg_info(node);
 288         low  = new_rd_Load(dbg, irg, block, mem, low,  mode);
 289         proj = new_r_Proj(irg, block, low, mode_M, pn_Load_M);
 290         high = new_rd_Load(dbg, irg, block, proj, high, mode);
 291
 292         set_Load_volatility(low,  get_Load_volatility(node));
 293         set_Load_volatility(high, get_Load_volatility(node));
 294
 295         idx = get_irn_idx(node);
 296         assert(idx < env->n_entries);
 297         env->entries[idx]->low_word  = low;
 298         env->entries[idx]->high_word = high;
 299
 300         for (proj = get_irn_link(node); proj; proj = get_irn_link(proj)) {
 301                 idx = get_irn_idx(proj);
 302
 303                 switch (get_Proj_proj(proj)) {
 304                 case pn_Load_M:         /* Memory result. */
 305                         /* put it to the second one */
 306                         set_Proj_pred(proj, high);
 307                         break;
 308                 case pn_Load_X_except:  /* Execution result if exception occurred. */
 309                         /* put it to the first one */
 310                         set_Proj_pred(proj, low);
 311                         break;
 312                 case pn_Load_res:       /* Result of load operation. */
 313                         assert(idx < env->n_entries);
 314                         env->entries[idx]->low_word  = new_r_Proj(irg, block, low, mode, pn_Load_res);
 315                         env->entries[idx]->high_word = new_r_Proj(irg, block, high, mode, pn_Load_res);
 316                         break;
 317                 default:
 318                         assert(0 && "unexpected Proj number");
 319                 }
 320                 /* mark this proj: we have handled it already, otherwise we might fall into
 321                  * out new nodes. */
 322                 mark_irn_visited(proj);
 323         }
 324 }
 325
 326 /**
 327  * Translate a Store: create two.
 328  */
 329 static void lower_Store(ir_node *node, ir_mode *mode, lower_env_t *env) {
 330         ir_graph *irg;
 331         ir_node  *block, *adr, *mem;
 332         ir_node  *low, *high, *irn, *proj;
 333         dbg_info *dbg;
 334         int      idx;
 335         node_entry_t *entry;
 336
 337         irn = get_Store_value(node);
 338         entry = env->entries[get_irn_idx(irn)];
 339         assert(entry);
 340
 341         if (! entry->low_word) {
 342                 /* not ready yet, wait */
 343                 pdeq_putr(env->waitq, node);
 344                 return;
 345         }
 346
 347         irg = current_ir_graph;
 348         adr = get_Store_ptr(node);
 349         mem = get_Store_mem(node);
 350         block = get_nodes_block(node);
 351
 352         if (env->params->little_endian) {
 353                 low  = adr;
 354                 high = new_r_Add(irg, block, adr,
 355                         new_r_Const(irg, block, get_tarval_mode(env->tv_mode_bytes), env->tv_mode_bytes),
 356                         get_irn_mode(adr));
 357         }
 358         else {
 359                 low  = new_r_Add(irg, block, adr,
 360                         new_r_Const(irg, block, get_tarval_mode(env->tv_mode_bytes), env->tv_mode_bytes),
 361                         get_irn_mode(adr));
 362                 high = adr;
 363         }
 364
 365         /* create two Stores */
 366         dbg = get_irn_dbg_info(node);
 367         low  = new_rd_Store(dbg, irg, block, mem, low,  entry->low_word);
 368         proj = new_r_Proj(irg, block, low, mode_M, pn_Store_M);
 369         high = new_rd_Store(dbg, irg, block, proj, high, entry->high_word);
 370
 371         set_Store_volatility(low,  get_Store_volatility(node));
 372         set_Store_volatility(high, get_Store_volatility(node));
 373
 374         idx = get_irn_idx(node);
 375         assert(idx < env->n_entries);
 376         env->entries[idx]->low_word  = low;
 377         env->entries[idx]->high_word = high;
 378
 379         for (proj = get_irn_link(node); proj; proj = get_irn_link(proj)) {
 380                 idx = get_irn_idx(proj);
 381
 382                 switch (get_Proj_proj(proj)) {
 383                 case pn_Store_M:         /* Memory result. */
 384                         /* put it to the second one */
 385                         set_Proj_pred(proj, high);
 386                         break;
 387                 case pn_Store_X_except:  /* Execution result if exception occurred. */
 388                         /* put it to the first one */
 389                         set_Proj_pred(proj, low);
 390                         break;
 391                 default:
 392                         assert(0 && "unexpected Proj number");
 393                 }
 394                 /* mark this proj: we have handled it already, otherwise we might fall into
 395                  * out new nodes. */
 396                 mark_irn_visited(proj);
 397         }
 398 }
 399
 400 /**
 401  * Return a node containing the address of the intrinsic emulation function.
 402  */
 403 static ir_node *get_intrinsic_address(ir_type *method, ir_op *op, ir_mode *mode, ir_node *block, lower_env_t *env) {
 404         symconst_symbol sym;
 405         entity *ent;
 406         op_mode_entry_t key, *entry;
 407
 408         key.op   = op;
 409         key.mode = mode;
 410         key.ent  = NULL;
 411
 412         entry = set_insert(intrinsic_fkt, &key, sizeof(key), HASH_PTR(op) ^ HASH_PTR(mode));
 413         if (! entry->ent) {
 414                 /* create a new one */
 415                 ent = env->params->create_intrinsic(method, op, mode, env->params->ctx);
 416
 417                 assert(ent && "Intrinsic creator must return an entity");
 418                 entry->ent = ent;
 419         }
 420         else
 421                 ent = entry->ent;
 422
 423         sym.entity_p = ent;
 424         return new_r_SymConst(current_ir_graph, block, sym, symconst_addr_ent);
 425 }
 426
 427 /**
 428  * Translate a Div.
 429  *
 430  * Create an intrinsic Call.
 431  */
 432 static void lower_Div(ir_node *node, ir_mode *mode, lower_env_t *env) {
 433         ir_node  *block, *irn, *call, *proj;
 434         ir_node  *in[4];
 435         dbg_info *dbg;
 436         ir_type  *mtp;
 437         int      idx;
 438         node_entry_t *entry;
 439
 440         irn   = get_Div_left(node);
 441         entry = env->entries[get_irn_idx(irn)];
 442         assert(entry);
 443
 444         if (! entry->low_word) {
 445                 /* not ready yet, wait */
 446                 pdeq_putr(env->waitq, node);
 447                 return;
 448         }
 449
 450         in[0] = entry->low_word;
 451         in[1] = entry->high_word;
 452
 453         irn   = get_Div_right(node);
 454         entry = env->entries[get_irn_idx(irn)];
 455         assert(entry);
 456
 457         if (! entry->low_word) {
 458                 /* not ready yet, wait */
 459                 pdeq_putr(env->waitq, node);
 460                 return;
 461         }
 462
 463         in[2] = entry->low_word;
 464         in[3] = entry->high_word;
 465
 466         dbg = get_irn_dbg_info(node);
 467         block = get_nodes_block(node);
 468
 469         mtp = mode_is_signed(mode) ? binop_tp_s : binop_tp_u;
 470         irn = get_intrinsic_address(mtp, get_irn_op(node), get_irn_op_mode(node), block, env);
 471         call = new_rd_Call(dbg, current_ir_graph, block, get_Div_mem(node),
 472                 irn, 4, in, mtp);
 473         set_irn_pinned(call, get_irn_pinned(node));
 474         irn = new_r_Proj(current_ir_graph, block, call, mode_T, pn_Call_T_result);
 475
 476         for (proj = get_irn_link(node); proj; proj = get_irn_link(proj)) {
 477                 switch (get_Proj_proj(proj)) {
 478                 case pn_Div_M:         /* Memory result. */
 479                         /* reroute to the call */
 480                         set_Proj_pred(proj, call);
 481                         set_Proj_proj(proj, pn_Call_M_except);
 482                         break;
 483                 case pn_Div_X_except:  /* Execution result if exception occurred. */
 484                         /* reroute to the call */
 485                         set_Proj_pred(proj, call);
 486                         set_Proj_proj(proj, pn_Call_X_except);
 487                         break;
 488                 case pn_Div_res:       /* Result of computation. */
 489                         idx = get_irn_idx(proj);
 490                         assert(idx < env->n_entries);
 491                         env->entries[idx]->low_word  = new_r_Proj(current_ir_graph, block, irn, mode, 0);
 492                         env->entries[idx]->high_word = new_r_Proj(current_ir_graph, block, irn, mode, 1);
 493                         break;
 494                 default:
 495                         assert(0 && "unexpected Proj number");
 496                 }
 497                 /* mark this proj: we have handled it already, otherwise we might fall into
 498                  * out new nodes. */
 499                 mark_irn_visited(proj);
 500         }
 501 }
 502
 503 /**
 504  * Translate a Mod.
 505  *
 506  * Create an intrinsic Call.
 507  */
 508 static void lower_Mod(ir_node *node, ir_mode *mode, lower_env_t *env) {
 509         ir_node  *block, *proj, *irn, *call;
 510         ir_node  *in[4];
 511         dbg_info *dbg;
 512         ir_type  *mtp;
 513         int      idx;
 514         node_entry_t *entry;
 515
 516         irn   = get_Mod_left(node);
 517         entry = env->entries[get_irn_idx(irn)];
 518         assert(entry);
 519
 520         if (! entry->low_word) {
 521                 /* not ready yet, wait */
 522                 pdeq_putr(env->waitq, node);
 523                 return;
 524         }
 525
 526         in[0] = entry->low_word;
 527         in[1] = entry->high_word;
 528
 529         irn   = get_Mod_right(node);
 530         entry = env->entries[get_irn_idx(irn)];
 531         assert(entry);
 532
 533         if (! entry->low_word) {
 534                 /* not ready yet, wait */
 535                 pdeq_putr(env->waitq, node);
 536                 return;
 537         }
 538
 539         in[2] = entry->low_word;
 540         in[3] = entry->high_word;
 541
 542         dbg = get_irn_dbg_info(node);
 543         block = get_nodes_block(node);
 544
 545         mtp = mode_is_signed(mode) ? binop_tp_s : binop_tp_u;
 546         irn = get_intrinsic_address(mtp, get_irn_op(node), get_irn_op_mode(node), block, env);
 547         call = new_rd_Call(dbg, current_ir_graph, block, get_Mod_mem(node),
 548                 irn, 4, in, mtp);
 549         set_irn_pinned(call, get_irn_pinned(node));
 550         irn = new_r_Proj(current_ir_graph, block, call, mode_T, pn_Call_T_result);
 551
 552         for (proj = get_irn_link(node); proj; proj = get_irn_link(proj)) {
 553                 switch (get_Proj_proj(proj)) {
 554                 case pn_Mod_M:         /* Memory result. */
 555                         /* reroute to the call */
 556                         set_Proj_pred(proj, call);
 557                         set_Proj_proj(proj, pn_Call_M_except);
 558                         break;
 559                 case pn_Mod_X_except:  /* Execution result if exception occurred. */
 560                         /* reroute to the call */
 561                         set_Proj_pred(proj, call);
 562                         set_Proj_proj(proj, pn_Call_X_except);
 563                         break;
 564                 case pn_Mod_res:       /* Result of computation. */
 565                         idx = get_irn_idx(proj);
 566                         assert(idx < env->n_entries);
 567                         env->entries[idx]->low_word  = new_r_Proj(current_ir_graph, block, irn, mode, 0);
 568                         env->entries[idx]->high_word = new_r_Proj(current_ir_graph, block, irn, mode, 1);
 569                         break;
 570                 default:
 571                         assert(0 && "unexpected Proj number");
 572                 }
 573                 /* mark this proj: we have handled it already, otherwise we might fall into
 574                  * out new nodes. */
 575                 mark_irn_visited(proj);
 576         }
 577 }
 578
 579 /**
 580  * Translate a DivMod.
 581  *
 582  * Create two intrinsic Calls.
 583  */
 584 static void lower_DivMod(ir_node *node, ir_mode *mode, lower_env_t *env) {
 585         ir_node  *block, *proj, *irn, *mem, *callDiv, *callMod, *resDiv, *resMod;
 586         ir_node  *in[4];
 587         dbg_info *dbg;
 588         ir_type  *mtp;
 589         int      idx;
 590         node_entry_t *entry;
 591         unsigned flags = 0;
 592
 593         /* check if both results are needed */
 594         for (proj = get_irn_link(node); proj; proj = get_irn_link(proj)) {
 595                 switch (get_Proj_proj(proj)) {
 596                 case pn_DivMod_res_div: flags |= 1; break;
 597                 case pn_DivMod_res_mod: flags |= 2; break;
 598                 default: break;
 599                 }
 600         }
 601
 602         irn   = get_DivMod_left(node);
 603         entry = env->entries[get_irn_idx(irn)];
 604         assert(entry);
 605
 606         if (! entry->low_word) {
 607                 /* not ready yet, wait */
 608                 pdeq_putr(env->waitq, node);
 609                 return;
 610         }
 611
 612         in[0] = entry->low_word;
 613         in[1] = entry->high_word;
 614
 615         irn   = get_DivMod_right(node);
 616         entry = env->entries[get_irn_idx(irn)];
 617         assert(entry);
 618
 619         if (! entry->low_word) {
 620                 /* not ready yet, wait */
 621                 pdeq_putr(env->waitq, node);
 622                 return;
 623         }
 624
 625         in[2] = entry->low_word;
 626         in[3] = entry->high_word;
 627
 628         dbg = get_irn_dbg_info(node);
 629         block = get_nodes_block(node);
 630
 631         mem = get_DivMod_mem(node);
 632
 633         callDiv = callMod = NULL;
 634         mtp = mode_is_signed(mode) ? binop_tp_s : binop_tp_u;
 635         if (flags & 1) {
 636                 irn = get_intrinsic_address(mtp, op_Div, get_irn_op_mode(node), block, env);
 637                 callDiv = new_rd_Call(dbg, current_ir_graph, block, mem,
 638                         irn, 4, in, mtp);
 639                 set_irn_pinned(callDiv, get_irn_pinned(node));
 640                 resDiv = new_r_Proj(current_ir_graph, block, callDiv, mode_T, pn_Call_T_result);
 641         }
 642         if (flags & 2) {
 643                 if (flags & 1)
 644                         mem = new_r_Proj(current_ir_graph, block, callDiv, mode_M, pn_Call_M);
 645                 irn = get_intrinsic_address(mtp, op_Mod, get_irn_op_mode(node), block, env);
 646                 callMod = new_rd_Call(dbg, current_ir_graph, block, mem,
 647                         irn, 4, in, mtp);
 648                 set_irn_pinned(callMod, get_irn_pinned(node));
 649                 resMod = new_r_Proj(current_ir_graph, block, callMod, mode_T, pn_Call_T_result);
 650         }
 651
 652         for (proj = get_irn_link(node); proj; proj = get_irn_link(proj)) {
 653                 switch (get_Proj_proj(proj)) {
 654                 case pn_DivMod_M:         /* Memory result. */
 655                         /* reroute to the first call */
 656                         set_Proj_pred(proj, callDiv ? callDiv : (callMod ? callMod : mem));
 657                         set_Proj_proj(proj, pn_Call_M_except);
 658                         break;
 659                 case pn_DivMod_X_except:  /* Execution result if exception occurred. */
 660                         /* reroute to the first call */
 661                         set_Proj_pred(proj, callDiv ? callDiv : (callMod ? callMod : mem));
 662                         set_Proj_proj(proj, pn_Call_X_except);
 663                         break;
 664                 case pn_DivMod_res_div:   /* Result of Div. */
 665                         idx = get_irn_idx(proj);
 666                         assert(idx < env->n_entries);
 667                         env->entries[idx]->low_word  = new_r_Proj(current_ir_graph, block, resDiv, mode, 0);
 668                         env->entries[idx]->high_word = new_r_Proj(current_ir_graph, block, resDiv, mode, 1);
 669                         break;
 670                 case pn_DivMod_res_mod:   /* Result of Mod. */
 671                         idx = get_irn_idx(proj);
 672                         env->entries[idx]->low_word  = new_r_Proj(current_ir_graph, block, resMod, mode, 0);
 673                         env->entries[idx]->high_word = new_r_Proj(current_ir_graph, block, resMod, mode, 1);
 674                         break;
 675                 default:
 676                         assert(0 && "unexpected Proj number");
 677                 }
 678                 /* mark this proj: we have handled it already, otherwise we might fall into
 679                  * out new nodes. */
 680                 mark_irn_visited(proj);
 681         }
 682 }
 683
 684 /**
 685  * Translate a Binop.
 686  *
 687  * Create an intrinsic Call.
 688  */
 689 static void lower_Binop(ir_node *node, ir_mode *mode, lower_env_t *env) {
 690         ir_node  *block, *irn;
 691         ir_node  *in[4];
 692         dbg_info *dbg;
 693         ir_type  *mtp;
 694         int      idx;
 695         node_entry_t *entry;
 696
 697         irn   = get_binop_left(node);
 698         entry = env->entries[get_irn_idx(irn)];
 699         assert(entry);
 700
 701         if (! entry->low_word) {
 702                 /* not ready yet, wait */
 703                 pdeq_putr(env->waitq, node);
 704                 return;
 705         }
 706
 707         in[0] = entry->low_word;
 708         in[1] = entry->high_word;
 709
 710         irn   = get_binop_right(node);
 711         entry = env->entries[get_irn_idx(irn)];
 712         assert(entry);
 713
 714         if (! entry->low_word) {
 715                 /* not ready yet, wait */
 716                 pdeq_putr(env->waitq, node);
 717                 return;
 718         }
 719
 720         in[2] = entry->low_word;
 721         in[3] = entry->high_word;
 722
 723         dbg = get_irn_dbg_info(node);
 724         block = get_nodes_block(node);
 725
 726         mtp = mode_is_signed(mode) ? binop_tp_s : binop_tp_u;
 727         irn = get_intrinsic_address(mtp, get_irn_op(node), get_irn_mode(node), block, env);
 728         irn = new_rd_Call(dbg, current_ir_graph, block, get_irg_no_mem(current_ir_graph),
 729                 irn, 4, in, mtp);
 730         set_irn_pinned(irn, get_irn_pinned(node));
 731         irn = new_r_Proj(current_ir_graph, block, irn, mode_T, pn_Call_T_result);
 732
 733         idx = get_irn_idx(node);
 734         assert(idx < env->n_entries);
 735         env->entries[idx]->low_word  = new_r_Proj(current_ir_graph, block, irn, mode, 0);
 736         env->entries[idx]->high_word = new_r_Proj(current_ir_graph, block, irn, mode, 1);
 737 }
 738
 739 /**
 740  * Translate an Unop.
 741  *
 742  * Create an intrinsic Call.
 743  */
 744 static void lower_Unop(ir_node *node, ir_mode *mode, lower_env_t *env) {
 745         ir_node  *block, *irn;
 746         ir_node  *in[2];
 747         dbg_info *dbg;
 748         ir_type  *mtp;
 749         int      idx;
 750         node_entry_t *entry;
 751
 752         irn   = get_unop_op(node);
 753         entry = env->entries[get_irn_idx(irn)];
 754         assert(entry);
 755
 756         if (! entry->low_word) {
 757                 /* not ready yet, wait */
 758                 pdeq_putr(env->waitq, node);
 759                 return;
 760         }
 761
 762         in[0] = entry->low_word;
 763         in[1] = entry->high_word;
 764
 765         dbg = get_irn_dbg_info(node);
 766         block = get_nodes_block(node);
 767
 768         mtp = mode_is_signed(mode) ? unop_tp_s : unop_tp_u;
 769         irn = get_intrinsic_address(mtp, get_irn_op(node), get_irn_mode(node), block, env);
 770         irn = new_rd_Call(dbg, current_ir_graph, block, get_irg_no_mem(current_ir_graph),
 771                 irn, 2, in, mtp);
 772         set_irn_pinned(irn, get_irn_pinned(node));
 773         irn = new_r_Proj(current_ir_graph, block, irn, mode_T, pn_Call_T_result);
 774
 775         idx = get_irn_idx(node);
 776         assert(idx < env->n_entries);
 777         env->entries[idx]->low_word  = new_r_Proj(current_ir_graph, block, irn, mode, 0);
 778         env->entries[idx]->high_word = new_r_Proj(current_ir_graph, block, irn, mode, 1);
 779 }
 780
 781 /**
 782  * Translate a logical Binop.
 783  *
 784  * Create two logical Binops.
 785  */
 786 static void lower_Binop_logical(ir_node *node, ir_mode *mode, lower_env_t *env,
 787                                                                 ir_node *(*constr_rd)(dbg_info *db, ir_graph *irg, ir_node *block, ir_node *op1, ir_node *op2, ir_mode *mode) ) {
 788         ir_node  *block, *irn;
 789         ir_node  *lop_l, *lop_h, *rop_l, *rop_h;
 790         dbg_info *dbg;
 791         int      idx;
 792         node_entry_t *entry;
 793
 794         irn   = get_binop_left(node);
 795         entry = env->entries[get_irn_idx(irn)];
 796         assert(entry);
 797
 798         if (! entry->low_word) {
 799                 /* not ready yet, wait */
 800                 pdeq_putr(env->waitq, node);
 801                 return;
 802         }
 803
 804         lop_l = entry->low_word;
 805         lop_h = entry->high_word;
 806
 807         irn   = get_binop_right(node);
 808         entry = env->entries[get_irn_idx(irn)];
 809         assert(entry);
 810
 811         if (! entry->low_word) {
 812                 /* not ready yet, wait */
 813                 pdeq_putr(env->waitq, node);
 814                 return;
 815         }
 816
 817         rop_l = entry->low_word;
 818         rop_h = entry->high_word;
 819
 820         dbg = get_irn_dbg_info(node);
 821         block = get_nodes_block(node);
 822
 823         idx = get_irn_idx(node);
 824         assert(idx < env->n_entries);
 825         env->entries[idx]->low_word  = constr_rd(dbg, current_ir_graph, block, lop_l, rop_l, mode);
 826         env->entries[idx]->high_word = constr_rd(dbg, current_ir_graph, block, lop_h, rop_h, mode);
 827 }
 828
 829 #define lower_logical(op)                                                \
 830 static void lower_##op(ir_node *node, ir_mode *mode, lower_env_t *env) { \
 831         lower_Binop_logical(node, mode, env, new_rd_##op);                   \
 832 }
 833
 834 lower_logical(And)
 835 lower_logical(Or)
 836 lower_logical(Eor)
 837
 838 /**
 839  * Translate a Not.
 840  *
 841  * Create two logical Nots.
 842  */
 843 static void lower_Not(ir_node *node, ir_mode *mode, lower_env_t *env) {
 844         ir_node  *block, *irn;
 845         ir_node  *op_l, *op_h;
 846         dbg_info *dbg;
 847         int      idx;
 848         node_entry_t *entry;
 849
 850         irn   = get_Not_op(node);
 851         entry = env->entries[get_irn_idx(irn)];
 852         assert(entry);
 853
 854         if (! entry->low_word) {
 855                 /* not ready yet, wait */
 856                 pdeq_putr(env->waitq, node);
 857                 return;
 858         }
 859
 860         op_l = entry->low_word;
 861         op_h = entry->high_word;
 862
 863         dbg = get_irn_dbg_info(node);
 864         block = get_nodes_block(node);
 865
 866         idx = get_irn_idx(node);
 867         assert(idx < env->n_entries);
 868         env->entries[idx]->low_word  = new_rd_Not(dbg, current_ir_graph, block, op_l, mode);
 869         env->entries[idx]->high_word = new_rd_Not(dbg, current_ir_graph, block, op_h, mode);
 870 }
 871
 872 /**
 873  * Translate a Cond.
 874  */
 875 static void lower_Cond(ir_node *node, ir_mode *mode, lower_env_t *env) {
 876         ir_node *cmp, *left, *right, *block;
 877         ir_node *sel = get_Cond_selector(node);
 878         ir_mode *m = get_irn_mode(sel);
 879         int     idx;
 880
 881         if (m == mode_b) {
 882                 node_entry_t *lentry, *rentry;
 883                 ir_node  *proj, *projT = NULL, *projF = NULL;
 884                 ir_node  *new_bl, *cmpH, *cmpL, *irn;
 885                 ir_node  *projHF, *projHT;
 886                 ir_node  *dst_blk;
 887                 ir_graph *irg;
 888                 pn_Cmp   pnc;
 889                 dbg_info *dbg;
 890
 891                 cmp   = get_Proj_pred(sel);
 892                 left  = get_Cmp_left(cmp);
 893                 idx   = get_irn_idx(left);
 894                 lentry = env->entries[idx];
 895
 896                 if (! lentry)
 897                         /* a normal Cmp */
 898                         return;
 899
 900                 right = get_Cmp_right(cmp);
 901                 idx   = get_irn_idx(right);
 902                 rentry = env->entries[idx];
 903                 assert(rentry);
 904
 905                 if (! lentry->low_word || !rentry->low_word) {
 906                         /* not yet ready */
 907                         pdeq_putr(env->waitq, node);
 908                         return;
 909                 }
 910
 911                 /* all right, build the code */
 912                 for (proj = get_irn_link(node); proj; proj = get_irn_link(proj)) {
 913                         long proj_nr = get_Proj_proj(proj);
 914
 915                         if (proj_nr == pn_Cond_true) {
 916                                 assert(projT == NULL && "more than one Proj(true)");
 917                                 projT = proj;
 918                         }
 919                         else {
 920                                 assert(proj_nr == pn_Cond_false);
 921                                 assert(projF == NULL && "more than one Proj(false)");
 922                                 projF = proj;
 923                         }
 924                         mark_irn_visited(proj);
 925                 }
 926                 assert(projT && projF);
 927
 928                 /* create a new high compare */
 929                 block = get_nodes_block(cmp);
 930                 dbg   = get_irn_dbg_info(cmp);
 931                 irg   = current_ir_graph;
 932
 933                 cmpH = new_rd_Cmp(dbg, irg, block, lentry->high_word, rentry->high_word);
 934
 935                 pnc = get_Proj_proj(sel);
 936                 if (pnc == pn_Cmp_Eq) {
 937                         /* simple case:a == b <==> a_h == b_h && a_l == b_l */
 938                         pmap_entry *entry = pmap_find(env->proj_2_block, projF);
 939
 940                         assert(entry);
 941                         dst_blk = entry->value;
 942
 943                         irn = new_r_Proj(irg, block, cmpH, mode_b, pn_Cmp_Eq);
 944                         dbg = get_irn_dbg_info(node);
 945                         irn = new_rd_Cond(dbg, irg, block, irn);
 946
 947                         projHF = new_r_Proj(irg, block, irn, mode_X, pn_Cond_false);
 948                         mark_irn_visited(projHF);
 949                         exchange(projF, projHF);
 950
 951                         projHT = new_r_Proj(irg, block, irn, mode_X, pn_Cond_true);
 952                         mark_irn_visited(projHT);
 953
 954                         new_bl = new_r_Block(irg, 1, &projHT);
 955
 956                         dbg   = get_irn_dbg_info(cmp);
 957                         cmpL = new_rd_Cmp(dbg, irg, new_bl, lentry->low_word, rentry->low_word);
 958                         irn = new_r_Proj(irg, new_bl, cmpL, mode_b, pn_Cmp_Eq);
 959                         dbg = get_irn_dbg_info(node);
 960                         irn = new_rd_Cond(dbg, irg, new_bl, irn);
 961
 962                         proj = new_r_Proj(irg, new_bl, irn, mode_X, pn_Cond_false);
 963                         mark_irn_visited(proj);
 964                         add_block_cf_input(dst_blk, projHF, proj);
 965
 966                         proj = new_r_Proj(irg, new_bl, irn, mode_X, pn_Cond_true);
 967                         mark_irn_visited(proj);
 968                         exchange(projT, proj);
 969                 }
 970                 else if (pnc == pn_Cmp_Lg) {
 971                         /* simple case:a != b <==> a_h != b_h || a_l != b_l */
 972                         pmap_entry *entry = pmap_find(env->proj_2_block, projT);
 973
 974                         assert(entry);
 975                         dst_blk = entry->value;
 976
 977                         irn = new_r_Proj(irg, block, cmpH, mode_b, pn_Cmp_Lg);
 978                         dbg = get_irn_dbg_info(node);
 979                         irn = new_rd_Cond(dbg, irg, block, irn);
 980
 981                         projHT = new_r_Proj(irg, block, irn, mode_X, pn_Cond_true);
 982                         mark_irn_visited(projHT);
 983                         exchange(projT, projHT);
 984
 985                         projHF = new_r_Proj(irg, block, irn, mode_X, pn_Cond_false);
 986                         mark_irn_visited(projHF);
 987
 988                         new_bl = new_r_Block(irg, 1, &projHF);
 989
 990                         dbg   = get_irn_dbg_info(cmp);
 991                         cmpL = new_rd_Cmp(dbg, irg, new_bl, lentry->low_word, rentry->low_word);
 992                         irn = new_r_Proj(irg, new_bl, cmpL, mode_b, pn_Cmp_Lg);
 993                         dbg = get_irn_dbg_info(node);
 994                         irn = new_rd_Cond(dbg, irg, new_bl, irn);
 995
 996                         proj = new_r_Proj(irg, new_bl, irn, mode_X, pn_Cond_true);
 997                         mark_irn_visited(proj);
 998                         add_block_cf_input(dst_blk, projHT, proj);
 999
1000                         proj = new_r_Proj(irg, new_bl, irn, mode_X, pn_Cond_false);
1001                         mark_irn_visited(proj);
1002                         exchange(projF, proj);
1003                 }
1004                 else {
1005                         /* a rel b <==> a_h rel b_h || (a_h == b_h && a_l rel b_l) */
1006                         ir_node *dstT, *dstF, *newbl_eq, *newbl_l;
1007                         pmap_entry *entry;
1008
1009                         entry = pmap_find(env->proj_2_block, projT);
1010                         assert(entry);
1011                         dstT = entry->value;
1012
1013                         entry = pmap_find(env->proj_2_block, projF);
1014                         assert(entry);
1015                         dstF = entry->value;
1016
1017                         irn = new_r_Proj(irg, block, cmpH, mode_b, pnc);
1018                         dbg = get_irn_dbg_info(node);
1019                         irn = new_rd_Cond(dbg, irg, block, irn);
1020
1021                         projHT = new_r_Proj(irg, block, irn, mode_X, pn_Cond_true);
1022                         mark_irn_visited(projHT);
1023                         exchange(projT, projHT);
1024                         projT = projHT;
1025
1026                         projHF = new_r_Proj(irg, block, irn, mode_X, pn_Cond_false);
1027                         mark_irn_visited(projHF);
1028
1029                         newbl_eq = new_r_Block(irg, 1, &projHF);
1030
1031                         irn = new_r_Proj(irg, newbl_eq, cmpH, mode_b, pn_Cmp_Eq);
1032                         irn = new_rd_Cond(dbg, irg, newbl_eq, irn);
1033
1034                         proj = new_r_Proj(irg, newbl_eq, irn, mode_X, pn_Cond_false);
1035                         mark_irn_visited(proj);
1036                         exchange(projF, proj);
1037                         projF = proj;
1038
1039                         proj = new_r_Proj(irg, newbl_eq, irn, mode_X, pn_Cond_true);
1040                         mark_irn_visited(proj);
1041
1042                         newbl_l = new_r_Block(irg, 1, &proj);
1043
1044                         dbg   = get_irn_dbg_info(cmp);
1045                         cmpL = new_rd_Cmp(dbg, irg, newbl_l, lentry->low_word, rentry->low_word);
1046                         irn = new_r_Proj(irg, newbl_l, cmpL, mode_b, pnc);
1047                         dbg = get_irn_dbg_info(node);
1048                         irn = new_rd_Cond(dbg, irg, newbl_l, irn);
1049
1050                         proj = new_r_Proj(irg, newbl_l, irn, mode_X, pn_Cond_true);
1051                         mark_irn_visited(proj);
1052                         add_block_cf_input(dstT, projT, proj);
1053
1054                         proj = new_r_Proj(irg, newbl_l, irn, mode_X, pn_Cond_false);
1055                         mark_irn_visited(proj);
1056                         add_block_cf_input(dstF, projF, proj);
1057                 }
1058
1059                 /* we have changed the control flow */
1060                 env->flags |= CF_CHANGED;
1061         }
1062         else {
1063                 idx = get_irn_idx(sel);
1064
1065                 if (env->entries[idx]) {
1066                         /*
1067                            Bad, a jump-table with double-word index.
1068                            This should not happen, but if it does we handle
1069                            it like a Conv were between (in other words, ignore
1070                            the high part.
1071                          */
1072
1073                         if (! env->entries[idx]->low_word) {
1074                                 /* not ready yet, wait */
1075                                 pdeq_putr(env->waitq, node);
1076                                 return;
1077                         }
1078                         set_Cond_selector(node, env->entries[idx]->low_word);
1079                 }
1080         }
1081 }
1082
1083 /**
1084  * Translate a Conv to higher_signed
1085  */
1086 static void lower_Conv_to_Ls(ir_node *node, lower_env_t *env) {
1087         ir_node *op    = get_Conv_op(node);
1088         ir_mode *mode  = get_irn_mode(op);
1089
1090         if (mode_is_int(mode) || mode_is_reference(mode)) {
1091                 ir_node  *block = get_nodes_block(node);
1092                 dbg_info *dbg = get_irn_dbg_info(node);
1093                 int      idx = get_irn_idx(node);
1094                 ir_graph *irg = current_ir_graph;
1095                 ir_mode  *dst_mode = env->params->low_signed;
1096
1097                 assert(idx < env->n_entries);
1098
1099                 /* simple case: create a high word */
1100                 if (mode != dst_mode)
1101                         op = new_rd_Conv(dbg, irg, block, op, dst_mode);
1102
1103                 env->entries[idx]->low_word  = op;
1104                 env->entries[idx]->high_word = new_rd_Shrs(dbg, irg, block, op,
1105                         new_Const_long(mode_Iu, get_mode_size_bits(dst_mode) - 1), dst_mode);
1106         }
1107         else {
1108                 assert(0);
1109         }
1110 }
1111
1112 /**
1113  * Translate a Conv to higher_unsigned
1114  */
1115 static void lower_Conv_to_Lu(ir_node *node, lower_env_t *env) {
1116         ir_node *op    = get_Conv_op(node);
1117         ir_mode *mode  = get_irn_mode(op);
1118
1119         if (mode_is_int(mode) || mode_is_reference(mode)) {
1120                 ir_node  *block = get_nodes_block(node);
1121                 dbg_info *dbg = get_irn_dbg_info(node);
1122                 int      idx = get_irn_idx(node);
1123                 ir_graph *irg = current_ir_graph;
1124                 ir_mode  *dst_mode = env->params->low_unsigned;
1125
1126                 assert(idx < env->n_entries);
1127
1128                 /* simple case: create a high word */
1129                 if (mode != env->params->low_unsigned)
1130                         op = new_rd_Conv(dbg, irg, block, op, dst_mode);
1131
1132                 env->entries[idx]->low_word  = op;
1133                 env->entries[idx]->high_word = new_Const(dst_mode, get_mode_null(dst_mode));
1134         }
1135         else {
1136                 assert(0);
1137         }
1138 }
1139
1140 /**
1141  * Translate a Conv from higher_signed
1142  */
1143 static void lower_Conv_from_Ls(ir_node *node, lower_env_t *env) {
1144         ir_node *op    = get_Conv_op(node);
1145         ir_mode *mode  = get_irn_mode(node);
1146
1147         if (mode_is_int(mode) || mode_is_reference(mode)) {
1148                 ir_node  *block = get_nodes_block(node);
1149                 dbg_info *dbg = get_irn_dbg_info(node);
1150                 int      idx = get_irn_idx(op);
1151                 ir_graph *irg = current_ir_graph;
1152
1153                 assert(idx < env->n_entries);
1154                 op = env->entries[idx]->low_word;
1155
1156                 /* simple case: create a high word */
1157                 if (mode != env->params->low_signed)
1158                         op = new_rd_Conv(dbg, irg, block, op, mode);
1159
1160                 set_Conv_op(node, op);
1161         }
1162         else {
1163                 assert(0);
1164         }
1165 }
1166
1167 /**
1168  * Translate a Conv from higher_unsigned
1169  */
1170 static void lower_Conv_from_Lu(ir_node *node, lower_env_t *env) {
1171         ir_node *op    = get_Conv_op(node);
1172         ir_mode *mode  = get_irn_mode(node);
1173
1174         if (mode_is_int(mode) || mode_is_reference(mode)) {
1175                 ir_node  *block = get_nodes_block(node);
1176                 dbg_info *dbg = get_irn_dbg_info(node);
1177                 int      idx = get_irn_idx(op);
1178                 ir_graph *irg = current_ir_graph;
1179
1180                 assert(idx < env->n_entries);
1181                 op = env->entries[idx]->low_word;
1182
1183                 /* simple case: create a high word */
1184                 if (mode != env->params->low_unsigned)
1185                         op = new_rd_Conv(dbg, irg, block, op, mode);
1186
1187                 set_Conv_op(node, op);
1188         }
1189         else {
1190                 assert(0);
1191         }
1192 }
1193
1194 /**
1195  * Translate a Conv.
1196  */
1197 static void lower_Conv(ir_node *node, ir_mode *mode, lower_env_t *env) {
1198         mode = get_irn_mode(node);
1199
1200         if (mode == env->params->high_signed)
1201                 lower_Conv_to_Ls(node, env);
1202         else if (mode == env->params->high_unsigned)
1203                 lower_Conv_to_Lu(node, env);
1204         else {
1205                 ir_mode *mode = get_irn_mode(get_Conv_op(node));
1206
1207                 if (mode == env->params->high_signed)
1208                         lower_Conv_from_Ls(node, env);
1209                 else {
1210                         assert(mode == env->params->high_unsigned);
1211                         lower_Conv_from_Lu(node, env);
1212                 }
1213         }
1214 }
1215
1216 /**
1217  * Lower the method type.
1218  */
1219 static ir_type *lower_mtp(ir_type *mtp, lower_env_t *env) {
1220         pmap_entry *entry;
1221         ident      *id;
1222         ir_type    *res;
1223
1224         if (is_lowered_type(mtp))
1225                 return mtp;
1226
1227         entry = pmap_find(lowered_type, mtp);
1228         if (! entry) {
1229                 int i, n, r, n_param, n_res;
1230
1231                 /* count new number of params */
1232                 n_param = n = get_method_n_params(mtp);
1233                 for (i = n_param - 1; i >= 0; --i) {
1234                         ir_type *tp = get_method_param_type(mtp, i);
1235
1236                         if (is_Primitive_type(tp)) {
1237                                 ir_mode *mode = get_type_mode(tp);
1238
1239                                 if (mode == env->params->high_signed ||
1240                                         mode == env->params->high_unsigned)
1241                                         ++n_param;
1242                         }
1243                 }
1244
1245                 /* count new number of results */
1246                 n_res = r = get_method_n_ress(mtp);
1247                 for (i = n_res - 1; i >= 0; --i) {
1248                         ir_type *tp = get_method_res_type(mtp, i);
1249
1250                         if (is_Primitive_type(tp)) {
1251                                 ir_mode *mode = get_type_mode(tp);
1252
1253                                 if (mode == env->params->high_signed ||
1254                                         mode == env->params->high_unsigned)
1255                                         ++n_res;
1256                         }
1257                 }
1258
1259                 id = mangle_u(new_id_from_chars("L", 1), get_type_ident(mtp));
1260                 res = new_type_method(id, n_param, n_res);
1261
1262                 /* set param types and result types */
1263                 for (i = n_param = 0; i < n; ++i) {
1264                         ir_type *tp = get_method_param_type(mtp, i);
1265
1266                         if (is_Primitive_type(tp)) {
1267                                 ir_mode *mode = get_type_mode(tp);
1268
1269                                 if (mode == env->params->high_signed) {
1270                                         set_method_param_type(res, n_param++, tp_s);
1271                                         set_method_param_type(res, n_param++, tp_s);
1272                                 }
1273                                 else if (mode == env->params->high_unsigned) {
1274                                         set_method_param_type(res, n_param++, tp_u);
1275                                         set_method_param_type(res, n_param++, tp_u);
1276                                 }
1277                                 else
1278                                         set_method_param_type(res, n_param++, tp);
1279                         }
1280                 }
1281                 for (i = n_res = 0; i < r; ++i) {
1282                         ir_type *tp = get_method_res_type(mtp, i);
1283
1284                         if (is_Primitive_type(tp)) {
1285                                 ir_mode *mode = get_type_mode(tp);
1286
1287                                 if (mode == env->params->high_signed) {
1288                                         set_method_res_type(res, n_res++, tp_s);
1289                                         set_method_res_type(res, n_res++, tp_s);
1290                                 }
1291                                 else if (mode == env->params->high_unsigned) {
1292                                         set_method_res_type(res, n_res++, tp_u);
1293                                         set_method_res_type(res, n_res++, tp_u);
1294                                 }
1295                                 else
1296                                         set_method_res_type(res, n_res++, tp);
1297                         }
1298                 }
1299                 set_lowered_type(mtp, res);
1300                 pmap_insert(lowered_type, mtp, res);
1301         }
1302         else
1303                 res = entry->value;
1304         return res;
1305 }
1306
1307 /**
1308  * Translate a Return.
1309  */
1310 static void lower_Return(ir_node *node, ir_mode *mode, lower_env_t *env) {
1311         ir_graph *irg = current_ir_graph;
1312         entity   *ent = get_irg_entity(irg);
1313         ir_type  *mtp = get_entity_type(ent);
1314         ir_node  **in;
1315         int      i, j, n, idx;
1316         int      need_conv = 0;
1317
1318         /* check if this return must be lowered */
1319         for (i = 0, n = get_Return_n_ress(node); i < n; ++i) {
1320                 ir_node *pred = get_Return_res(node, i);
1321                 ir_mode *mode = get_irn_op_mode(pred);
1322
1323                 if (mode == env->params->high_signed ||
1324                         mode == env->params->high_unsigned) {
1325                         idx = get_irn_idx(pred);
1326                         if (! env->entries[idx]->low_word) {
1327                                 /* not ready yet, wait */
1328                                 pdeq_putr(env->waitq, node);
1329                                 return;
1330                         }
1331                         need_conv = 1;
1332                 }
1333         }
1334         if (! need_conv)
1335                 return;
1336
1337         ent = get_irg_entity(irg);
1338         mtp = get_entity_type(ent);
1339
1340         mtp = lower_mtp(mtp, env);
1341         set_entity_type(ent, mtp);
1342
1343         /* create a new in array */
1344         NEW_ARR_A(ir_node *, in, get_method_n_ress(mtp) + 1);
1345         in[0] = get_Return_mem(node);
1346
1347         for (j = i = 0, n = get_Return_n_ress(node); i < n; ++i) {
1348                 ir_node *pred = get_Return_res(node, i);
1349
1350                 idx = get_irn_idx(pred);
1351                 assert(idx < env->n_entries);
1352
1353                 if (env->entries[idx]) {
1354                         in[++j] = env->entries[idx]->low_word;
1355                         in[++j] = env->entries[idx]->high_word;
1356                 }
1357                 else
1358                         in[++j] = pred;
1359         }
1360
1361         set_irn_in(node, j+1, in);
1362 }
1363
1364 /**
1365  * Translate the parameters.
1366  */
1367 static void lower_Start(ir_node *node, ir_mode *mode, lower_env_t *env) {
1368         ir_graph *irg = current_ir_graph;
1369         entity   *ent = get_irg_entity(irg);
1370         ir_type  *tp  = get_entity_type(ent);
1371         ir_type  *mtp;
1372         long     *new_projs;
1373         int      i, j, n_params, rem;
1374         ir_node  *proj, *args;
1375
1376         if (is_lowered_type(tp))
1377                 mtp = get_associated_type(tp);
1378         else
1379                 mtp = tp;
1380
1381         assert(! is_lowered_type(mtp));
1382
1383         n_params = get_method_n_params(mtp);
1384         if (n_params <= 0)
1385                 return;
1386
1387         NEW_ARR_A(long, new_projs, n_params);
1388
1389         /* first check if we have parameters that must be fixed */
1390         for (i = j = 0; i < n_params; ++i, ++j) {
1391                 ir_type *tp = get_method_param_type(mtp, i);
1392
1393                 new_projs[i] = j;
1394                 if (is_Primitive_type(tp)) {
1395                         ir_mode *mode = get_type_mode(tp);
1396
1397                         if (mode == env->params->high_signed ||
1398                                 mode == env->params->high_unsigned)
1399                                 ++j;
1400                 }
1401         }
1402         if (i == j)
1403                 return;
1404
1405         mtp = lower_mtp(mtp, env);
1406         set_entity_type(ent, mtp);
1407
1408         /* switch off optimization for new Proj nodes or they might be CSE'ed
1409            with not patched one's */
1410         rem = get_optimize();
1411         set_optimize(0);
1412
1413         /* ok, fix all Proj's and create new ones */
1414         args = get_irg_args(irg);
1415         for (proj = get_irn_link(node); proj; proj = get_irn_link(proj)) {
1416                 ir_node *pred = get_Proj_pred(proj);
1417                 long proj_nr;
1418                 int idx;
1419                 ir_mode *mode;
1420                 dbg_info *dbg;
1421
1422                 /* do not visit this node again */
1423                 mark_irn_visited(proj);
1424
1425                 if (pred != args)
1426                         continue;
1427
1428                 proj_nr = get_Proj_proj(proj);
1429                 set_Proj_proj(proj, new_projs[proj_nr]);
1430
1431                 idx = get_irn_idx(proj);
1432                 if (env->entries[idx]) {
1433                         mode = get_irn_mode(proj);
1434
1435                         if (mode == env->params->high_signed)
1436                                 mode = env->params->low_signed;
1437                         else
1438                                 mode = env->params->high_signed;
1439
1440                         dbg = get_irn_dbg_info(proj);
1441                         env->entries[idx]->low_word  =
1442                                 new_rd_Proj(dbg, irg, get_nodes_block(proj), args, mode, new_projs[proj_nr]);
1443                         env->entries[idx]->high_word =
1444                                 new_rd_Proj(dbg, irg, get_nodes_block(proj), args, mode, new_projs[proj_nr] + 1);
1445                 }
1446         }
1447         set_optimize(rem);
1448 }
1449
1450 /**
1451  * Translate a Call.
1452  */
1453 static void lower_Call(ir_node *node, ir_mode *mode, lower_env_t *env) {
1454         ir_graph *irg = current_ir_graph;
1455         ir_type  *tp = get_Call_type(node);
1456         ir_type  *call_tp;
1457         ir_node  **in, *proj, *results;
1458         int      n_params, n_res, need_lower = 0;
1459         int      i, j;
1460         long     *res_numbers = NULL;
1461
1462         if (is_lowered_type(tp))
1463                 call_tp = get_associated_type(tp);
1464         else
1465                 call_tp = tp;
1466
1467         assert(! is_lowered_type(call_tp));
1468
1469         n_params = get_method_n_params(call_tp);
1470         for (i = 0; i < n_params; ++i) {
1471                 ir_type *tp = get_method_param_type(call_tp, i);
1472
1473                 if (is_Primitive_type(tp)) {
1474                         ir_mode *mode = get_type_mode(tp);
1475
1476                         if (mode == env->params->high_signed ||
1477                                 mode == env->params->high_unsigned) {
1478                                 need_lower = 1;
1479                                 break;
1480                         }
1481                 }
1482         }
1483         n_res = get_method_n_ress(call_tp);
1484         if (n_res > 0) {
1485                 NEW_ARR_A(long, res_numbers, n_res);
1486
1487                 for (i = j = 0; i < n_res; ++i, ++j) {
1488                         ir_type *tp = get_method_res_type(call_tp, i);
1489
1490                         res_numbers[i] = j;
1491                         if (is_Primitive_type(tp)) {
1492                                 ir_mode *mode = get_type_mode(tp);
1493
1494                                 if (mode == env->params->high_signed ||
1495                                         mode == env->params->high_unsigned) {
1496                                         need_lower = 1;
1497                                         ++j;
1498                                 }
1499                         }
1500                 }
1501         }
1502
1503         if (! need_lower)
1504                 return;
1505
1506         /* let's lower it */
1507         call_tp = lower_mtp(call_tp, env);
1508         set_Call_type(node, call_tp);
1509
1510         NEW_ARR_A(ir_node *, in, get_method_n_params(call_tp) + 2);
1511
1512         in[0] = get_Call_mem(node);
1513         in[1] = get_Call_ptr(node);
1514
1515         for (j = 2, i = 0; i < n_params; ++i) {
1516                 ir_node *pred = get_Call_param(node, i);
1517                 int     idx = get_irn_idx(pred);
1518
1519                 if (env->entries[idx]) {
1520                         if (! env->entries[idx]->low_word) {
1521                                 /* not ready yet, wait */
1522                                 pdeq_putr(env->waitq, node);
1523                                 return;
1524                         }
1525                         in[j++] = env->entries[idx]->low_word;
1526                         in[j++] = env->entries[idx]->high_word;
1527                 }
1528                 else
1529                         in[j++] = pred;
1530         }
1531
1532         set_irn_in(node, j, in);
1533
1534         /* fix the results */
1535         results = NULL;
1536         for (proj = get_irn_link(node); proj; proj = get_irn_link(proj)) {
1537                 long proj_nr = get_Proj_proj(proj);
1538
1539                 if (proj_nr == pn_Call_T_result && get_Proj_pred(proj) == node) {
1540                         /* found the result proj */
1541                         results = proj;
1542                         break;
1543                 }
1544         }
1545
1546         if (results) {          /* there are results */
1547                 int rem = get_optimize();
1548
1549                 /* switch off optimization for new Proj nodes or they might be CSE'ed
1550                    with not patched one's */
1551                 set_optimize(0);
1552                 for (i = j = 0, proj = get_irn_link(results); proj; proj = get_irn_link(proj), ++i, ++j) {
1553                         if (get_Proj_pred(proj) == results) {
1554                                 long proj_nr = get_Proj_proj(proj);
1555                                 int idx;
1556
1557                                 /* found a result */
1558                                 set_Proj_proj(proj, res_numbers[proj_nr]);
1559                                 idx = get_irn_idx(proj);
1560                                 if (env->entries[idx]) {
1561                                         ir_mode *mode = get_irn_mode(proj);
1562                                         dbg_info *dbg;
1563
1564                                         if (mode == env->params->high_signed)
1565                                                 mode = env->params->low_signed;
1566                                         else
1567                                                 mode = env->params->low_unsigned;
1568
1569                                         dbg = get_irn_dbg_info(proj);
1570                                         env->entries[idx]->low_word  =
1571                                                 new_rd_Proj(dbg, irg, get_nodes_block(proj), results, mode, res_numbers[proj_nr]);
1572                                         env->entries[idx]->high_word =
1573                                                 new_rd_Proj(dbg, irg, get_nodes_block(proj), results, mode, res_numbers[proj_nr] + 1);
1574                                 }
1575                                 mark_irn_visited(proj);
1576                         }
1577                 }
1578                 set_optimize(rem);
1579         }
1580 }
1581
1582 /**
1583  * Translate an Unknown into two.
1584  */
1585 static void lower_Unknown(ir_node *node, ir_mode *mode, lower_env_t *env) {
1586         int idx = get_irn_idx(node);
1587
1588         env->entries[idx]->low_word  =
1589         env->entries[idx]->high_word = new_r_Unknown(current_ir_graph, mode);
1590 }
1591
1592 /**
1593  * Translate a Phi.
1594  *
1595  * First step: just create two templates
1596  */
1597 static void lower_Phi(ir_node *phi, ir_mode *mode, lower_env_t *env) {
1598         ir_node  *block, *unk;
1599         ir_node  **inl, **inh;
1600         dbg_info *dbg;
1601         int      idx, i, arity = get_Phi_n_preds(phi);
1602         int      enq = 0;
1603
1604         idx = get_irn_idx(phi);
1605         if (env->entries[idx]->low_word) {
1606                 /* Phi nodes already build, check for inputs */
1607                 ir_node *phil = env->entries[idx]->low_word;
1608                 ir_node *phih = env->entries[idx]->high_word;
1609
1610                 for (i = 0; i < arity; ++i) {
1611                         ir_node *pred = get_Phi_pred(phi, i);
1612                         int     idx = get_irn_idx(pred);
1613
1614                         if (env->entries[idx]->low_word) {
1615                                 set_Phi_pred(phil, i, env->entries[idx]->low_word);
1616                                 set_Phi_pred(phil, i, env->entries[idx]->high_word);
1617                         }
1618                         else {
1619                                 /* still not ready */
1620                                 pdeq_putr(env->waitq, phi);
1621                                 return;
1622                         }
1623                 }
1624         }
1625
1626         /* first create a new in array */
1627         NEW_ARR_A(ir_node *, inl, arity);
1628         NEW_ARR_A(ir_node *, inh, arity);
1629         unk = new_r_Unknown(current_ir_graph, mode);
1630
1631         for (i = 0; i < arity; ++i) {
1632                 ir_node *pred = get_Phi_pred(phi, i);
1633                 int     idx = get_irn_idx(pred);
1634
1635                 if (env->entries[idx]->low_word) {
1636                         inl[i] = env->entries[idx]->low_word;
1637                         inh[i] = env->entries[idx]->high_word;
1638                 }
1639                 else {
1640                         inl[i] = unk;
1641                         inh[i] = unk;
1642                         enq = 1;
1643                 }
1644         }
1645
1646         dbg = get_irn_dbg_info(phi);
1647         block = get_nodes_block(phi);
1648
1649         idx = get_irn_idx(phi);
1650         assert(idx < env->n_entries);
1651         env->entries[idx]->low_word  = new_rd_Phi(dbg, current_ir_graph, block, arity, inl, mode);
1652         env->entries[idx]->high_word = new_rd_Phi(dbg, current_ir_graph, block, arity, inh, mode);
1653
1654         if (enq) {
1655                 /* not yet finished */
1656                 pdeq_putr(env->waitq, phi);
1657         }
1658 }
1659
1660 /**
1661  * check for opcodes that must always be lowered.
1662  */
1663 static int always_lower(opcode code) {
1664         switch (code) {
1665         case iro_Start:
1666         case iro_Call:
1667         case iro_Return:
1668         case iro_Cond:
1669                 return 1;
1670         default:
1671                 return 0;
1672         }
1673 }
1674
1675 /** The type of a lower function. */
1676 typedef void (*lower_func)(ir_node *node, ir_mode *mode, lower_env_t *env);
1677
1678 /**
1679  * lower a node.
1680  */
1681 static void lower_ops(ir_node *node, void *env)
1682 {
1683         lower_env_t  *lenv = env;
1684         node_entry_t *entry;
1685         int          idx = get_irn_idx(node);
1686
1687         entry = lenv->entries[idx];
1688         if (entry || always_lower(get_irn_opcode(node))) {
1689                 ir_op      *op = get_irn_op(node);
1690                 lower_func func = (lower_func)op->ops.generic;
1691
1692                 if (func) {
1693                         ir_mode *mode = get_irn_op_mode(node);
1694
1695                         if (mode == lenv->params->high_signed)
1696                                 mode = lenv->params->low_signed;
1697                         else
1698                                 mode = lenv->params->low_unsigned;
1699
1700                         DB((dbg, LEVEL_1, "  %+F\n", node));
1701                         func(node, mode, lenv);
1702                 }
1703         }
1704 }
1705
1706 #define IDENT(s)  new_id_from_chars(s, sizeof(s)-1)
1707
1708 /**
1709  * Compare two op_mode_entry_t's.
1710  */
1711 static int cmp_op_mode(const void *elt, const void *key, size_t size) {
1712         const op_mode_entry_t *e1 = elt;
1713         const op_mode_entry_t *e2 = key;
1714
1715         return (e1->op - e2->op) | (e1->mode - e2->mode);
1716 }
1717
1718 /*
1719  * Do the lowering.
1720  */
1721 void lower_dw_ops(const lwrdw_param_t *param)
1722 {
1723         lower_env_t lenv;
1724         int i;
1725
1726         if (! param)
1727                 return;
1728
1729         if (! param->enable)
1730                 return;
1731
1732         FIRM_DBG_REGISTER(dbg, "firm.lower.dw");
1733         firm_dbg_set_mask(dbg, SET_LEVEL_2);
1734
1735         assert(2 * get_mode_size_bits(param->low_signed)   == get_mode_size_bits(param->high_signed));
1736         assert(2 * get_mode_size_bits(param->low_unsigned) == get_mode_size_bits(param->high_unsigned));
1737         assert(get_mode_size_bits(param->low_signed) == get_mode_size_bits(param->low_unsigned));
1738
1739         if (! intrinsic_fkt)
1740                 intrinsic_fkt = new_set(cmp_op_mode, iro_MaxOpcode);
1741         if (! lowered_type)
1742                 lowered_type = pmap_create();
1743
1744         if (! tp_u)
1745                 tp_u = new_type_primitive(IDENT("_i_uint"), param->low_unsigned);
1746         if (! tp_s)
1747                 tp_s = new_type_primitive(IDENT("_i_int"), param->low_signed);
1748
1749         if (! binop_tp_u) {
1750                 binop_tp_u = new_type_method(IDENT("binop_u_intrinsic"), 4, 2);
1751
1752                 set_method_param_type(binop_tp_u, 0, tp_u);
1753                 set_method_param_type(binop_tp_u, 1, tp_u);
1754                 set_method_param_type(binop_tp_u, 2, tp_u);
1755                 set_method_param_type(binop_tp_u, 3, tp_u);
1756                 set_method_res_type(binop_tp_u, 0, tp_u);
1757                 set_method_res_type(binop_tp_u, 1, tp_u);
1758         }
1759         if (! binop_tp_s) {
1760                 binop_tp_s = new_type_method(IDENT("binop_s_intrinsic"), 4, 2);
1761                 set_method_param_type(binop_tp_s, 0, tp_s);
1762                 set_method_param_type(binop_tp_s, 1, tp_s);
1763                 set_method_param_type(binop_tp_s, 2, tp_s);
1764                 set_method_param_type(binop_tp_s, 3, tp_s);
1765                 set_method_res_type(binop_tp_s, 0, tp_s);
1766                 set_method_res_type(binop_tp_s, 1, tp_s);
1767         }
1768         if (! unop_tp_u) {
1769                 unop_tp_u = new_type_method(IDENT("unop_u_intrinsic"), 2, 2);
1770                 set_method_param_type(unop_tp_u, 0, tp_u);
1771                 set_method_param_type(unop_tp_u, 1, tp_u);
1772                 set_method_res_type(unop_tp_u, 0, tp_u);
1773                 set_method_res_type(unop_tp_u, 1, tp_u);
1774         }
1775         if (! unop_tp_s) {
1776                 unop_tp_s = new_type_method(IDENT("unop_s_intrinsic"), 2, 2);
1777                 set_method_param_type(unop_tp_s, 0, tp_s);
1778                 set_method_param_type(unop_tp_s, 1, tp_s);
1779                 set_method_res_type(unop_tp_s, 0, tp_s);
1780                 set_method_res_type(unop_tp_s, 1, tp_s);
1781         }
1782
1783         lenv.tv_mode_bytes = new_tarval_from_long(get_mode_size_bytes(param->low_unsigned), mode_Iu);
1784         lenv.waitq         = new_pdeq();
1785         lenv.params        = param;
1786
1787         /* first clear the generic function pointer for all ops */
1788         clear_irp_opcodes_generic_func();
1789
1790 #define LOWER2(op, fkt)   op_##op->ops.generic = (op_func)fkt
1791 #define LOWER(op)         LOWER2(op, lower_##op)
1792 #define LOWER_BIN(op)     LOWER2(op, lower_Binop)
1793 #define LOWER_UN(op)      LOWER2(op, lower_Unop)
1794
1795         LOWER(Load);
1796         LOWER(Store);
1797         LOWER(Const);
1798         LOWER(And);
1799         LOWER(Or);
1800         LOWER(Eor);
1801         LOWER(Not);
1802         LOWER(Cond);
1803         LOWER(Return);
1804         LOWER(Call);
1805         LOWER(Unknown);
1806         LOWER(Phi);
1807         LOWER(Start);
1808
1809         LOWER_BIN(Add);
1810         LOWER_BIN(Sub);
1811         LOWER_BIN(Mul);
1812         LOWER_BIN(Shl);
1813         LOWER_BIN(Shr);
1814         LOWER_BIN(Shrs);
1815         LOWER_BIN(Rot);
1816         LOWER_UN(Minus);
1817         LOWER(DivMod);
1818         LOWER(Div);
1819         LOWER(Mod);
1820         LOWER_UN(Abs);
1821
1822         LOWER(Conv);
1823
1824 #undef LOWER_UN
1825 #undef LOWER_BIN
1826 #undef LOWER
1827 #undef LOWER2
1828
1829         /* transform all graphs */
1830         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1831                 ir_graph *irg = get_irp_irg(i);
1832                 int n_idx;
1833
1834                 obstack_init(&lenv.obst);
1835
1836                 n_idx = get_irg_last_idx(irg);
1837                 lenv.n_entries = n_idx;
1838                 lenv.entries   = xmalloc(n_idx * sizeof(lenv.entries[0]));
1839                 memset(lenv.entries, 0, n_idx * sizeof(lenv.entries[0]));
1840
1841                 /* first step: link all nodes and allocate data */
1842                 lenv.flags = 0;
1843                 lenv.proj_2_block = pmap_create();
1844                 irg_walk_graph(irg, firm_clear_link, prepare_links, &lenv);
1845
1846                 if (lenv.flags & MUST_BE_LOWERED) {
1847                         DB((dbg, LEVEL_1, "Lowering graph %+F\n", irg));
1848
1849                         /* must do some work */
1850                         irg_walk_graph(irg, NULL, lower_ops, &lenv);
1851
1852                         /* last step: all waiting nodes */
1853                         DB((dbg, LEVEL_1, "finishing waiting nodes:\n"));
1854                         while (! pdeq_empty(lenv.waitq)) {
1855                                 ir_node *node = pdeq_getl(lenv.waitq);
1856
1857                                 lower_ops(node, &lenv);
1858                         }
1859
1860                         /* outs are invalid, we changed the graph */
1861                         set_irg_outs_inconsistent(irg);
1862
1863                         if (lenv.flags & CF_CHANGED) {
1864                                 /* control flow changed, dominance info is invalid */
1865                                 set_irg_doms_inconsistent(irg);
1866                                 set_irg_extblk_inconsistent(irg);
1867                                 set_irg_loopinfo_inconsistent(irg);
1868                         }
1869
1870                         dump_ir_block_graph(irg, "-dw");
1871                 }
1872                 pmap_destroy(lenv.proj_2_block);
1873                 free(lenv.entries);
1874                 obstack_free(&lenv.obst, NULL);
1875         }
1876         del_pdeq(lenv.waitq);
1877 }
1878
1879 /* Default implementation. */
1880 entity *def_create_intrinsic_fkt(ir_type *method, const ir_op *op, const ir_mode *mode, void *context)
1881 {
1882         char buf[64];
1883         ident *id;
1884
1885         snprintf(buf, sizeof(buf), "__l%s%s", get_op_name(op), get_mode_name(mode));
1886         id = new_id_from_str(buf);
1887
1888         return new_entity(get_glob_type(), id, method);
1889 }