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