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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       This file implements the mapping of 64Bit intrinsic
  23  *              functions to code or library calls.
  24  * @author      Michael Beck
  25  * @version     $Id$
  26  */
  27 #include "config.h"
  28
  29 #include "iredges.h"
  30 #include "irgmod.h"
  31 #include "irop.h"
  32 #include "irnode_t.h"
  33 #include "ircons.h"
  34 #include "irprog_t.h"
  35 #include "lowering.h"
  36 #include "array.h"
  37 #include "error.h"
  38
  39 #include "ia32_new_nodes.h"
  40 #include "bearch_ia32_t.h"
  41 #include "gen_ia32_regalloc_if.h"
  42
  43 /** The array of all intrinsics that must be mapped. */
  44 static i_record *intrinsics;
  45
  46 /** An array to cache all entities. */
  47 static ir_entity *i_ents[iro_Last + 1];
  48
  49 /*
  50  * Maps all intrinsic calls that the backend support
  51  * and map all instructions the backend did not support
  52  * to runtime calls.
  53  */
  54 void ia32_handle_intrinsics(void) {
  55         if (intrinsics && ARR_LEN(intrinsics) > 0) {
  56                 lower_intrinsics(intrinsics, ARR_LEN(intrinsics), /*part_block_used=*/1);
  57         }
  58 }
  59
  60 #define BINOP_Left_Low   0
  61 #define BINOP_Left_High  1
  62 #define BINOP_Right_Low  2
  63 #define BINOP_Right_High 3
  64
  65 /**
  66  * Reroute edges from the pn_Call_T_result proj of a call.
  67  *
  68  * @param proj   the pn_Call_T_result Proj
  69  * @param l_res  the lower 32 bit result
  70  * @param h_res  the upper 32 bit result or NULL
  71  * @param irg    the graph to replace on
  72  */
  73 static void reroute_result(ir_node *proj, ir_node *l_res, ir_node *h_res, ir_graph *irg) {
  74         const ir_edge_t *edge, *next;
  75
  76         foreach_out_edge_safe(proj, edge, next) {
  77                 ir_node *proj = get_edge_src_irn(edge);
  78                 long    pn    = get_Proj_proj(proj);
  79
  80                 if (pn == 0) {
  81                         edges_reroute(proj, l_res, irg);
  82                 } else if (pn == 1 && h_res != NULL) {
  83                         edges_reroute(proj, h_res, irg);
  84                 } else {
  85                         panic("Unsupported Result-Proj from Call found");
  86                 }
  87         }
  88 }
  89
  90 /**
  91  * Replace a call be a tuple of l_res, h_res.
  92  *
  93  * @param call   the call node to replace
  94  * @param l_res  the lower 32 bit result
  95  * @param h_res  the upper 32 bit result or NULL
  96  * @param irg    the graph to replace on
  97  * @param block  the block to replace on (always the call block)
  98  */
  99 static void resolve_call(ir_node *call, ir_node *l_res, ir_node *h_res, ir_graph *irg, ir_node *block) {
 100         ir_node *jmp, *res, *in[2];
 101         ir_node *bad   = get_irg_bad(irg);
 102         ir_node *nomem = get_irg_no_mem(irg);
 103         int     old_cse;
 104
 105         if (edges_activated(irg)) {
 106                 /* use rerouting to prevent some warning in the backend */
 107                 const ir_edge_t *edge, *next;
 108
 109                 foreach_out_edge_safe(call, edge, next) {
 110                         ir_node *proj = get_edge_src_irn(edge);
 111                         pn_Call pn    = get_Proj_proj(proj);
 112
 113                         switch (pn) {
 114                         case pn_Call_X_regular:
 115                                 /* Beware:
 116                                  * We do not check here if this call really has exception and regular Proj's.
 117                                  * new_r_Jmp might than be CSEd with the real exit jmp and then bad things happen
 118                                  * (in movgen.c from 186.crafty for example).
 119                                  * So be sure the newly created Jmp cannot CSE.
 120                                  */
 121                                 old_cse = get_opt_cse();
 122                                 set_opt_cse(0);
 123                                 jmp = new_r_Jmp(block);
 124                                 set_opt_cse(old_cse);
 125                                 edges_reroute(proj, jmp, irg);
 126                                 break;
 127
 128                         case pn_Call_X_except:
 129                         case pn_Call_P_value_res_base:
 130                                 /* should not happen here */
 131                                 edges_reroute(proj, bad, irg);
 132                                 break;
 133                         case pn_Call_M:
 134                                 /* should not happen here */
 135                                 edges_reroute(proj, nomem, irg);
 136                                 break;
 137                         case pn_Call_T_result:
 138                                 reroute_result(proj, l_res, h_res, irg);
 139                                 break;
 140                         default:
 141                                 panic("Wrong Proj from Call");
 142                         }
 143                         kill_node(proj);
 144                 }
 145                 kill_node(call);
 146         } else {
 147                 /* no edges, build Tuple */
 148                 if (h_res == NULL)
 149                         res = l_res;
 150                 else {
 151                         in[0] = l_res;
 152                         in[1] = h_res;
 153                         res = new_r_Tuple(block, 2, in);
 154                 }
 155
 156                 turn_into_tuple(call, pn_Call_max);
 157                 /*
 158                  * Beware:
 159                  * We do not check here if this call really has exception and regular Proj's.
 160                  * new_r_Jmp might than be CSEd with the real exit jmp and then bad things happen
 161                  * (in movgen.c from 186.crafty for example).
 162                  * So be sure the newly created Jmp cannot CSE.
 163                  */
 164                 old_cse = get_opt_cse();
 165                 set_opt_cse(0);
 166                 jmp = new_r_Jmp(block);
 167                 set_opt_cse(old_cse);
 168
 169                 set_Tuple_pred(call, pn_Call_M,                nomem);
 170                 set_Tuple_pred(call, pn_Call_X_regular,        jmp);
 171                 set_Tuple_pred(call, pn_Call_X_except,         bad);
 172                 set_Tuple_pred(call, pn_Call_T_result,         res);
 173                 set_Tuple_pred(call, pn_Call_P_value_res_base, bad);
 174         }
 175 }
 176
 177 /**
 178  * Map an Add (a_l, a_h, b_l, b_h)
 179  */
 180 static int map_Add(ir_node *call, void *ctx) {
 181         dbg_info *dbg        = get_irn_dbg_info(call);
 182         ir_node  *block      = get_nodes_block(call);
 183         ir_node  **params    = get_Call_param_arr(call);
 184         ir_type  *method     = get_Call_type(call);
 185         ir_node  *a_l        = params[BINOP_Left_Low];
 186         ir_node  *a_h        = params[BINOP_Left_High];
 187         ir_node  *b_l        = params[BINOP_Right_Low];
 188         ir_node  *b_h        = params[BINOP_Right_High];
 189         ir_mode  *l_mode     = get_type_mode(get_method_res_type(method, 0));
 190         ir_mode  *h_mode     = get_type_mode(get_method_res_type(method, 1));
 191         ir_mode  *mode_flags = ia32_reg_classes[CLASS_ia32_flags].mode;
 192         ir_node  *add_low, *add_high, *flags;
 193         ir_node  *l_res, *h_res;
 194         (void) ctx;
 195
 196         /* l_res = a_l + b_l */
 197         /* h_res = a_h + b_h + carry */
 198
 199         add_low  = new_bd_ia32_l_Add(dbg, block, a_l, b_l, mode_T);
 200         flags    = new_r_Proj(block, add_low, mode_flags, pn_ia32_flags);
 201         add_high = new_bd_ia32_l_Adc(dbg, block, a_h, b_h, flags, h_mode);
 202
 203         l_res = new_r_Proj(block, add_low, l_mode, pn_ia32_res);
 204         h_res = add_high;
 205
 206         resolve_call(call, l_res, h_res, current_ir_graph, block);
 207         return 1;
 208 }
 209
 210 /**
 211  * Map a Sub (a_l, a_h, b_l, b_h)
 212  */
 213 static int map_Sub(ir_node *call, void *ctx)
 214 {
 215         dbg_info *dbg        = get_irn_dbg_info(call);
 216         ir_node  *block      = get_nodes_block(call);
 217         ir_node  **params    = get_Call_param_arr(call);
 218         ir_type  *method     = get_Call_type(call);
 219         ir_node  *a_l        = params[BINOP_Left_Low];
 220         ir_node  *a_h        = params[BINOP_Left_High];
 221         ir_node  *b_l        = params[BINOP_Right_Low];
 222         ir_node  *b_h        = params[BINOP_Right_High];
 223         ir_mode  *l_mode     = get_type_mode(get_method_res_type(method, 0));
 224         ir_mode  *h_mode     = get_type_mode(get_method_res_type(method, 1));
 225         ir_mode  *mode_flags = ia32_reg_classes[CLASS_ia32_flags].mode;
 226         ir_node  *sub_low, *sub_high, *flags;
 227         ir_node  *l_res, *h_res;
 228         (void) ctx;
 229
 230         /* l_res = a_l - b_l */
 231         /* h_res = a_h - b_h - carry */
 232
 233         sub_low  = new_bd_ia32_l_Sub(dbg, block, a_l, b_l, mode_T);
 234         flags    = new_r_Proj(block, sub_low, mode_flags, pn_ia32_flags);
 235         sub_high = new_bd_ia32_l_Sbb(dbg, block, a_h, b_h, flags, h_mode);
 236
 237         l_res = new_r_Proj( block, sub_low, l_mode, pn_ia32_res);
 238         h_res = sub_high;
 239
 240         resolve_call(call, l_res, h_res, current_ir_graph, block);
 241         return 1;
 242 }
 243
 244 /**
 245  * Map a Shl (a_l, a_h, count)
 246  */
 247 static int map_Shl(ir_node *call, void *ctx) {
 248         ir_graph *irg     = current_ir_graph;
 249         dbg_info *dbg     = get_irn_dbg_info(call);
 250         ir_node  *block   = get_nodes_block(call);
 251         ir_node  **params = get_Call_param_arr(call);
 252         ir_type  *method  = get_Call_type(call);
 253         ir_node  *a_l     = params[BINOP_Left_Low];
 254         ir_node  *a_h     = params[BINOP_Left_High];
 255         ir_node  *cnt     = params[BINOP_Right_Low];
 256         ir_mode  *l_mode  = get_type_mode(get_method_res_type(method, 0));
 257         ir_mode  *h_mode  = get_type_mode(get_method_res_type(method, 1));
 258         ir_mode  *c_mode;
 259         ir_node  *l_res, *h_res, *irn, *cond, *upper, *n_block, *l1, *l2, *h1, *h2, *in[2];
 260         (void) ctx;
 261
 262         if (is_Const(cnt)) {
 263                 /* the shift count is a const, create better code */
 264                 tarval *tv = get_Const_tarval(cnt);
 265
 266                 if (tarval_cmp(tv, new_tarval_from_long(32, l_mode)) & (pn_Cmp_Gt|pn_Cmp_Eq)) {
 267                         /* simplest case: shift only the lower bits. Note that there is no
 268                            need to reduce the constant here, this is done by the hardware.  */
 269                         ir_node *conv = new_rd_Conv(dbg, block, a_l, h_mode);
 270                         h_res = new_rd_Shl(dbg, block, conv, cnt, h_mode);
 271                         l_res = new_rd_Const(dbg, irg, get_mode_null(l_mode));
 272
 273                 } else {
 274                         /* h_res = SHLD a_h, a_l, cnt */
 275                         h_res = new_bd_ia32_l_ShlD(dbg, block, a_h, a_l, cnt, h_mode);
 276
 277                         /* l_res = SHL a_l, cnt */
 278                         l_res = new_bd_ia32_l_ShlDep(dbg, block, a_l, cnt, h_res, l_mode);
 279                 }
 280
 281                 resolve_call(call, l_res, h_res, irg, block);
 282                 return 1;
 283         }
 284
 285         part_block(call);
 286         upper = get_nodes_block(call);
 287
 288         /* h_res = SHLD a_h, a_l, cnt */
 289         h1 = new_bd_ia32_l_ShlD(dbg, upper, a_h, a_l, cnt, h_mode);
 290
 291         /* l_res = SHL a_l, cnt */
 292         l1 = new_bd_ia32_l_ShlDep(dbg, upper, a_l, cnt, h1, l_mode);
 293
 294         c_mode = get_irn_mode(cnt);
 295         irn    = new_r_Const_long(irg, c_mode, 32);
 296         irn    = new_rd_And(dbg, upper, cnt, irn, c_mode);
 297         irn    = new_rd_Cmp(dbg, upper, irn, new_r_Const(irg, get_mode_null(c_mode)));
 298         irn    = new_r_Proj(upper, irn, mode_b, pn_Cmp_Eq);
 299         cond   = new_rd_Cond(dbg, upper, irn);
 300
 301         in[0]  = new_r_Proj(upper, cond, mode_X, pn_Cond_true);
 302         in[1]  = new_r_Proj(upper, cond, mode_X, pn_Cond_false);
 303
 304         /* the block for cnt >= 32 */
 305         n_block = new_rd_Block(dbg, irg, 1, &in[1]);
 306         h2      = new_rd_Conv(dbg, n_block, l1, h_mode);
 307         l2      = new_r_Const(irg, get_mode_null(l_mode));
 308         in[1]   = new_r_Jmp(n_block);
 309
 310         set_irn_in(block, 2, in);
 311
 312         in[0] = l1;
 313         in[1] = l2;
 314         l_res = new_r_Phi(block, 2, in, l_mode);
 315         set_Block_phis(block, l_res);
 316
 317         in[0] = h1;
 318         in[1] = h2;
 319         h_res = new_r_Phi(block, 2, in, h_mode);
 320         set_Phi_next(l_res, h_res);
 321         set_Phi_next(h_res, NULL);
 322
 323         /* move it down */
 324         set_nodes_block(call, block);
 325         for (irn = get_irn_link(call); irn != NULL; irn = get_irn_link(irn))
 326                 set_nodes_block(irn, block);
 327
 328         resolve_call(call, l_res, h_res, irg, block);
 329         return 1;
 330 }
 331
 332 /**
 333  * Map a Shr (a_l, a_h, count)
 334  */
 335 static int map_Shr(ir_node *call, void *ctx) {
 336         ir_graph *irg     = current_ir_graph;
 337         dbg_info *dbg     = get_irn_dbg_info(call);
 338         ir_node  *block   = get_nodes_block(call);
 339         ir_node  **params = get_Call_param_arr(call);
 340         ir_type  *method  = get_Call_type(call);
 341         ir_node  *a_l     = params[BINOP_Left_Low];
 342         ir_node  *a_h     = params[BINOP_Left_High];
 343         ir_node  *cnt     = params[BINOP_Right_Low];
 344         ir_mode  *l_mode  = get_type_mode(get_method_res_type(method, 0));
 345         ir_mode  *h_mode  = get_type_mode(get_method_res_type(method, 1));
 346         ir_mode  *c_mode;
 347         ir_node  *l_res, *h_res, *irn, *cond, *upper, *n_block, *l1, *l2, *h1, *h2, *in[2];
 348         (void) ctx;
 349
 350         if (is_Const(cnt)) {
 351                 /* the shift count is a const, create better code */
 352                 tarval *tv = get_Const_tarval(cnt);
 353
 354                 if (tarval_cmp(tv, new_tarval_from_long(32, l_mode)) & (pn_Cmp_Gt|pn_Cmp_Eq)) {
 355                         /* simplest case: shift only the higher bits. Note that there is no
 356                            need to reduce the constant here, this is done by the hardware.  */
 357                         ir_node *conv = new_rd_Conv(dbg, block, a_h, l_mode);
 358                         h_res = new_rd_Const(dbg, irg, get_mode_null(h_mode));
 359                         l_res = new_rd_Shr(dbg, block, conv, cnt, l_mode);
 360                 } else {
 361                         /* l_res = SHRD a_h:a_l, cnt */
 362                         l_res = new_bd_ia32_l_ShrD(dbg, block, a_l, a_h, cnt, l_mode);
 363
 364                         /* h_res = SHR a_h, cnt */
 365                         h_res = new_bd_ia32_l_ShrDep(dbg, block, a_h, cnt, l_res, h_mode);
 366                 }
 367                 resolve_call(call, l_res, h_res, irg, block);
 368                 return 1;
 369         }
 370
 371         part_block(call);
 372         upper = get_nodes_block(call);
 373
 374         /* l_res = SHRD a_h:a_l, cnt */
 375         l1 = new_bd_ia32_l_ShrD(dbg, upper, a_l, a_h, cnt, l_mode);
 376
 377         /* h_res = SHR a_h, cnt */
 378         h1 = new_bd_ia32_l_ShrDep(dbg, upper, a_h, cnt, l1, h_mode);
 379
 380         c_mode = get_irn_mode(cnt);
 381         irn    = new_r_Const_long(irg, c_mode, 32);
 382         irn    = new_rd_And(dbg, upper, cnt, irn, c_mode);
 383         irn    = new_rd_Cmp(dbg, upper, irn, new_r_Const(irg, get_mode_null(c_mode)));
 384         irn    = new_r_Proj(upper, irn, mode_b, pn_Cmp_Eq);
 385         cond   = new_rd_Cond(dbg, upper, irn);
 386
 387         in[0]  = new_r_Proj(upper, cond, mode_X, pn_Cond_true);
 388         in[1]  = new_r_Proj(upper, cond, mode_X, pn_Cond_false);
 389
 390         /* the block for cnt >= 32 */
 391         n_block = new_rd_Block(dbg, irg, 1, &in[1]);
 392         l2      = new_rd_Conv(dbg, n_block, h1, l_mode);
 393         h2      = new_r_Const(irg, get_mode_null(h_mode));
 394         in[1]   = new_r_Jmp(n_block);
 395
 396         set_irn_in(block, 2, in);
 397
 398         in[0] = l1;
 399         in[1] = l2;
 400         l_res = new_r_Phi(block, 2, in, l_mode);
 401         set_Block_phis(block, l_res);
 402
 403         in[0] = h1;
 404         in[1] = h2;
 405         h_res = new_r_Phi(block, 2, in, h_mode);
 406         set_Phi_next(l_res, h_res);
 407         set_Phi_next(h_res, NULL);
 408
 409         /* move it down */
 410         set_nodes_block(call, block);
 411         for (irn = get_irn_link(call); irn != NULL; irn = get_irn_link(irn))
 412                 set_nodes_block(irn, block);
 413
 414         resolve_call(call, l_res, h_res, irg, block);
 415         return 1;
 416 }
 417
 418 /**
 419  * Map a Shrs (a_l, a_h, count)
 420  */
 421 static int map_Shrs(ir_node *call, void *ctx) {
 422         ir_graph *irg     = current_ir_graph;
 423         dbg_info *dbg     = get_irn_dbg_info(call);
 424         ir_node  *block   = get_nodes_block(call);
 425         ir_node  **params = get_Call_param_arr(call);
 426         ir_type  *method  = get_Call_type(call);
 427         ir_node  *a_l     = params[BINOP_Left_Low];
 428         ir_node  *a_h     = params[BINOP_Left_High];
 429         ir_node  *cnt     = params[BINOP_Right_Low];
 430         ir_mode  *l_mode  = get_type_mode(get_method_res_type(method, 0));
 431         ir_mode  *h_mode  = get_type_mode(get_method_res_type(method, 1));
 432         ir_mode  *c_mode;
 433         ir_node  *l_res, *h_res, *irn, *cond, *upper, *n_block, *l1, *l2, *h1, *h2, *in[2];
 434         (void) ctx;
 435
 436         if (is_Const(cnt)) {
 437                 /* the shift count is a const, create better code */
 438                 tarval *tv = get_Const_tarval(cnt);
 439
 440                 if (tarval_cmp(tv, new_tarval_from_long(32, l_mode)) & (pn_Cmp_Gt|pn_Cmp_Eq)) {
 441                         /* simplest case: shift only the higher bits. Note that there is no
 442                            need to reduce the constant here, this is done by the hardware.  */
 443                         ir_node *conv    = new_rd_Conv(dbg, block, a_h, l_mode);
 444                         ir_mode *c_mode  = get_irn_mode(cnt);
 445
 446                         h_res = new_rd_Shrs(dbg, block, a_h, new_r_Const_long(irg, c_mode, 31), h_mode);
 447                         l_res = new_rd_Shrs(dbg, block, conv, cnt, l_mode);
 448                 } else {
 449                         /* l_res = SHRD a_h:a_l, cnt */
 450                         l_res = new_bd_ia32_l_ShrD(dbg, block, a_l, a_h, cnt, l_mode);
 451
 452                         /* h_res = SAR a_h, cnt */
 453                         h_res = new_bd_ia32_l_SarDep(dbg, block, a_h, cnt, l_res, h_mode);
 454                 }
 455                 resolve_call(call, l_res, h_res, irg, block);
 456                 return 1;
 457         }
 458
 459         part_block(call);
 460         upper = get_nodes_block(call);
 461
 462         /* l_res = SHRD a_h:a_l, cnt */
 463         l1 = new_bd_ia32_l_ShrD(dbg, upper, a_l, a_h, cnt, l_mode);
 464
 465         /* h_res = SAR a_h, cnt */
 466         h1 = new_bd_ia32_l_SarDep(dbg, upper, a_h, cnt, l1, h_mode);
 467
 468         c_mode = get_irn_mode(cnt);
 469         irn    = new_r_Const_long(irg, c_mode, 32);
 470         irn    = new_rd_And(dbg, upper, cnt, irn, c_mode);
 471         irn    = new_rd_Cmp(dbg, upper, irn, new_r_Const(irg, get_mode_null(c_mode)));
 472         irn    = new_r_Proj(upper, irn, mode_b, pn_Cmp_Eq);
 473         cond   = new_rd_Cond(dbg, upper, irn);
 474
 475         in[0]  = new_r_Proj(upper, cond, mode_X, pn_Cond_true);
 476         in[1]  = new_r_Proj(upper, cond, mode_X, pn_Cond_false);
 477
 478         /* the block for cnt >= 32 */
 479         n_block = new_rd_Block(dbg, irg, 1, &in[1]);
 480         l2      = new_rd_Conv(dbg, n_block, h1, l_mode);
 481         h2      = new_rd_Shrs(dbg, n_block, a_h, new_r_Const_long(irg, c_mode, 31), h_mode);
 482         in[1]   = new_r_Jmp(n_block);
 483
 484         set_irn_in(block, 2, in);
 485
 486         in[0] = l1;
 487         in[1] = l2;
 488         l_res = new_r_Phi(block, 2, in, l_mode);
 489         set_Block_phis(block, l_res);
 490
 491         in[0] = h1;
 492         in[1] = h2;
 493         h_res = new_r_Phi(block, 2, in, h_mode);
 494         set_Phi_next(l_res, h_res);
 495         set_Phi_next(h_res, NULL);
 496
 497         /* move it down */
 498         set_nodes_block(call, block);
 499         for (irn = get_irn_link(call); irn != NULL; irn = get_irn_link(irn))
 500                 set_nodes_block(irn, block);
 501
 502         resolve_call(call, l_res, h_res, irg, block);
 503         return 1;
 504 }
 505
 506 /**
 507  * Checks where node high is a sign extension of low.
 508  */
 509 static int is_sign_extend(ir_node *low, ir_node *high)
 510 {
 511         if (is_Shrs(high)) {
 512                 ir_node *high_l;
 513                 ir_node *high_r;
 514                 tarval  *shift_count;
 515
 516                 high_r = get_Shrs_right(high);
 517                 if (!is_Const(high_r)) return 0;
 518
 519                 shift_count = get_Const_tarval(high_r);
 520                 if (!tarval_is_long(shift_count))       return 0;
 521                 if (get_tarval_long(shift_count) != 31) return 0;
 522
 523                 high_l = get_Shrs_left(high);
 524
 525                 if (is_Conv(low)    && get_Conv_op(low)    == high_l) return 1;
 526                 if (is_Conv(high_l) && get_Conv_op(high_l) == low)    return 1;
 527         } else if (is_Const(low) && is_Const(high)) {
 528                 tarval *tl = get_Const_tarval(low);
 529                 tarval *th = get_Const_tarval(high);
 530
 531                 if (tarval_is_long(th) && tarval_is_long(tl)) {
 532                         long l = get_tarval_long(tl);
 533                         long h = get_tarval_long(th);
 534
 535                         return (h == 0  && l >= 0) || (h == -1 && l <  0);
 536                 }
 537         }
 538
 539         return 0;
 540 }
 541
 542 /**
 543  * Map a Mul (a_l, a_h, b_l, b_h)
 544  */
 545 static int map_Mul(ir_node *call, void *ctx) {
 546         dbg_info *dbg     = get_irn_dbg_info(call);
 547         ir_node  *block   = get_nodes_block(call);
 548         ir_node  **params = get_Call_param_arr(call);
 549         ir_type  *method  = get_Call_type(call);
 550         ir_node  *a_l     = params[BINOP_Left_Low];
 551         ir_node  *a_h     = params[BINOP_Left_High];
 552         ir_node  *b_l     = params[BINOP_Right_Low];
 553         ir_node  *b_h     = params[BINOP_Right_High];
 554         ir_mode  *l_mode  = get_type_mode(get_method_res_type(method, 0));
 555         ir_mode  *h_mode  = get_type_mode(get_method_res_type(method, 1));
 556         ir_node  *l_res, *h_res, *mul, *pEDX, *add;
 557         (void) ctx;
 558
 559         /*
 560                 EDX:EAX = a_l * b_l
 561                 l_res   = EAX
 562
 563                 t1 = b_l * a_h
 564                 t2 = t1 + EDX
 565                 t3 = a_l * b_h
 566                 h_res = t2 + t3
 567         */
 568
 569         /* handle the often used case of 32x32=64 mul */
 570         if (is_sign_extend(a_l, a_h) && is_sign_extend(b_l, b_h)) {
 571                 mul   = new_bd_ia32_l_IMul(dbg, block, a_l, b_l);
 572                 h_res = new_rd_Proj(dbg, block, mul, h_mode, pn_ia32_l_IMul_res_high);
 573                 l_res = new_rd_Proj(dbg, block, mul, l_mode, pn_ia32_l_IMul_res_low);
 574         } else {
 575                 /* note that zero extension is handled hare efficiently */
 576                 mul   = new_bd_ia32_l_Mul(dbg, block, a_l, b_l);
 577                 pEDX  = new_rd_Proj(dbg, block, mul, h_mode, pn_ia32_l_Mul_res_high);
 578                 l_res = new_rd_Proj(dbg, block, mul, l_mode, pn_ia32_l_Mul_res_low);
 579
 580                 b_l   = new_rd_Conv(dbg, block, b_l, h_mode);
 581                 mul   = new_rd_Mul( dbg, block, a_h, b_l, h_mode);
 582                 add   = new_rd_Add( dbg, block, mul, pEDX, h_mode);
 583                 a_l   = new_rd_Conv(dbg, block, a_l, h_mode);
 584                 mul   = new_rd_Mul( dbg, block, a_l, b_h, h_mode);
 585                 h_res = new_rd_Add( dbg, block, add, mul, h_mode);
 586         }
 587         resolve_call(call, l_res, h_res, current_ir_graph, block);
 588
 589         return 1;
 590 }
 591
 592 /**
 593  * Map a Minus (a_l, a_h)
 594  */
 595 static int map_Minus(ir_node *call, void *ctx) {
 596         dbg_info *dbg     = get_irn_dbg_info(call);
 597         ir_node  *block   = get_nodes_block(call);
 598         ir_node  **params = get_Call_param_arr(call);
 599         ir_type  *method  = get_Call_type(call);
 600         ir_node  *a_l     = params[BINOP_Left_Low];
 601         ir_node  *a_h     = params[BINOP_Left_High];
 602         ir_mode  *l_mode  = get_type_mode(get_method_res_type(method, 0));
 603         ir_mode  *h_mode  = get_type_mode(get_method_res_type(method, 1));
 604         ir_node  *l_res, *h_res, *res;
 605         (void) ctx;
 606
 607         res   = new_bd_ia32_Minus64Bit(dbg, block, a_l, a_h);
 608         l_res = new_r_Proj(block, res, l_mode, pn_ia32_Minus64Bit_low_res);
 609         h_res = new_r_Proj(block, res, h_mode, pn_ia32_Minus64Bit_high_res);
 610
 611         resolve_call(call, l_res, h_res, current_ir_graph, block);
 612
 613         return 1;
 614 }
 615
 616 /**
 617  * Map a Abs (a_l, a_h)
 618  */
 619 static int map_Abs(ir_node *call, void *ctx) {
 620         dbg_info *dbg        = get_irn_dbg_info(call);
 621         ir_node  *block      = get_nodes_block(call);
 622         ir_node  **params    = get_Call_param_arr(call);
 623         ir_type  *method     = get_Call_type(call);
 624         ir_node  *a_l        = params[BINOP_Left_Low];
 625         ir_node  *a_h        = params[BINOP_Left_High];
 626         ir_mode  *l_mode     = get_type_mode(get_method_res_type(method, 0));
 627         ir_mode  *h_mode     = get_type_mode(get_method_res_type(method, 1));
 628         ir_mode  *mode_flags = ia32_reg_classes[CLASS_ia32_flags].mode;
 629         ir_node  *l_res, *h_res, *sign, *sub_l, *sub_h;
 630         ir_node  *sign_l;
 631         ir_node  *l_sub;
 632         ir_node  *flags;
 633         (void) ctx;
 634
 635         /*
 636                 Code inspired by gcc output :) (although gcc doubles the
 637                 operation for t1 as t2 and uses t1 for operations with low part
 638                 and t2 for operations with high part which is actually unnecessary
 639                 because t1 and t2 represent the same value)
 640
 641                 t1    = SHRS a_h, 31
 642                 t2    = a_l ^ t1
 643                 t3    = a_h ^ t1
 644                 l_res = t2 - t1
 645                 h_res = t3 - t1 - carry
 646
 647         */
 648
 649         /* TODO: give a hint to the backend somehow to not create a cltd here... */
 650         sign   = new_rd_Shrs(dbg, block, a_h, new_Const_long(l_mode, 31), h_mode);
 651         sign_l = new_rd_Conv(dbg, block, sign, l_mode);
 652         sub_l  = new_rd_Eor(dbg, block, a_l, sign_l, l_mode);
 653         sub_h  = new_rd_Eor(dbg, block, a_h, sign,   h_mode);
 654
 655         l_sub  = new_bd_ia32_l_Sub(dbg, block, sub_l, sign_l, mode_T);
 656         l_res  = new_r_Proj(block, l_sub, l_mode,     pn_ia32_res);
 657         flags  = new_r_Proj(block, l_sub, mode_flags, pn_ia32_flags);
 658         h_res  = new_bd_ia32_l_Sbb(dbg, block, sub_h, sign, flags, h_mode);
 659
 660         resolve_call(call, l_res, h_res, current_ir_graph, block);
 661
 662         return 1;
 663 }
 664
 665 #define ID(x) new_id_from_chars(x, sizeof(x)-1)
 666
 667 /**
 668  * Maps a Div. Change into a library call.
 669  */
 670 static int map_Div(ir_node *call, void *ctx) {
 671         ia32_intrinsic_env_t *env = ctx;
 672         ir_type   *method    = get_Call_type(call);
 673         ir_mode   *h_mode    = get_type_mode(get_method_res_type(method, 1));
 674         ir_node   *ptr;
 675         ir_entity *ent;
 676         ir_graph  *irg = get_irn_irg(call);
 677         symconst_symbol sym;
 678
 679         if (mode_is_signed(h_mode)) {
 680                 /* 64bit signed Division */
 681                 ent = env->divdi3;
 682                 if (ent == NULL) {
 683                         /* create library entity */
 684                         ent = env->divdi3 = new_entity(get_glob_type(), ID("__divdi3"), method);
 685                         set_entity_visibility(ent, visibility_external_allocated);
 686                         set_entity_ld_ident(ent, ID("__divdi3"));
 687                 }
 688         } else {
 689                 /* 64bit unsigned Division */
 690                 ent = env->udivdi3;
 691                 if (ent == NULL) {
 692                         /* create library entity */
 693                         ent = env->udivdi3 = new_entity(get_glob_type(), ID("__udivdi3"), method);
 694                         set_entity_visibility(ent, visibility_external_allocated);
 695                         set_entity_ld_ident(ent, ID("__udivdi3"));
 696                 }
 697         }
 698
 699         ptr = get_Call_ptr(call);
 700         sym.entity_p = ent;
 701         ptr = new_r_SymConst(irg, get_irn_mode(ptr), sym, symconst_addr_ent);
 702         set_Call_ptr(call, ptr);
 703
 704         return 1;
 705 }
 706
 707 /**
 708  * Maps a Mod. Change into a library call
 709  */
 710 static int map_Mod(ir_node *call, void *ctx) {
 711         ia32_intrinsic_env_t *env = ctx;
 712         ir_type   *method    = get_Call_type(call);
 713         ir_mode   *h_mode    = get_type_mode(get_method_res_type(method, 1));
 714         ir_node   *ptr;
 715         ir_entity *ent;
 716         ir_graph  *irg = get_irn_irg(call);
 717         symconst_symbol sym;
 718
 719         if (mode_is_signed(h_mode)) {
 720                 /* 64bit signed Modulo */
 721                 ent = env->moddi3;
 722                 if (ent == NULL) {
 723                         /* create library entity */
 724                         ent = env->moddi3 = new_entity(get_glob_type(), ID("__moddi3"), method);
 725                         set_entity_visibility(ent, visibility_external_allocated);
 726                         set_entity_ld_ident(ent, ID("__moddi3"));
 727                 }
 728         } else {
 729                 /* 64bit signed Modulo */
 730                 ent = env->umoddi3;
 731                 if (ent == NULL) {
 732                         /* create library entity */
 733                         ent = env->umoddi3 = new_entity(get_glob_type(), ID("__umoddi3"), method);
 734                         set_entity_visibility(ent, visibility_external_allocated);
 735                         set_entity_ld_ident(ent, ID("__umoddi3"));
 736                 }
 737         }
 738
 739         ptr = get_Call_ptr(call);
 740         sym.entity_p = ent;
 741         ptr = new_r_SymConst(irg, get_irn_mode(ptr), sym, symconst_addr_ent);
 742         set_Call_ptr(call, ptr);
 743
 744         return 1;
 745 }
 746
 747 /**
 748  * Maps a Conv.
 749  */
 750 static int map_Conv(ir_node *call, void *ctx) {
 751         ir_graph  *irg     = current_ir_graph;
 752         dbg_info  *dbg     = get_irn_dbg_info(call);
 753         ir_node   *block   = get_nodes_block(call);
 754         ir_node   **params = get_Call_param_arr(call);
 755         ir_type   *method  = get_Call_type(call);
 756         int       n        = get_Call_n_params(call);
 757         ir_node   *l_res, *h_res;
 758         (void) ctx;
 759
 760         if (n == 1) {
 761                 ir_node *float_to_ll;
 762
 763                 /* We have a Conv float -> long long here */
 764                 ir_node *a_f        = params[0];
 765                 ir_mode *l_res_mode = get_type_mode(get_method_res_type(method, 0));
 766                 ir_mode *h_res_mode = get_type_mode(get_method_res_type(method, 1));
 767
 768                 assert(mode_is_float(get_irn_mode(a_f)) && "unexpected Conv call");
 769
 770                 if (mode_is_signed(h_res_mode)) {
 771                         /* convert from float to signed 64bit */
 772                         float_to_ll = new_bd_ia32_l_FloattoLL(dbg, block, a_f);
 773
 774                         l_res = new_r_Proj(block, float_to_ll, l_res_mode,
 775                                                            pn_ia32_l_FloattoLL_res_low);
 776                         h_res = new_r_Proj(block, float_to_ll, h_res_mode,
 777                                                            pn_ia32_l_FloattoLL_res_high);
 778                 } else {
 779                         /* convert from float to signed 64bit */
 780                         ir_mode *flt_mode = get_irn_mode(a_f);
 781                         tarval  *flt_tv   = new_tarval_from_str("9223372036854775808", 19, flt_mode);
 782                         ir_node *flt_corr = new_Const(flt_tv);
 783                         ir_node *lower_blk = block;
 784                         ir_node *upper_blk;
 785                         ir_node *cmp, *proj, *cond, *blk, *int_phi, *flt_phi;
 786                         ir_node *in[2];
 787
 788                         part_block(call);
 789                         upper_blk = get_nodes_block(call);
 790
 791                         cmp   = new_rd_Cmp(dbg, upper_blk, a_f, flt_corr);
 792                         proj  = new_r_Proj(upper_blk, cmp, mode_b, pn_Cmp_Lt);
 793                         cond  = new_rd_Cond(dbg, upper_blk, proj);
 794                         in[0] = new_r_Proj(upper_blk, cond, mode_X, pn_Cond_true);
 795                         in[1] = new_r_Proj(upper_blk, cond, mode_X, pn_Cond_false);
 796                         blk   = new_r_Block(irg, 1, &in[1]);
 797                         in[1] = new_r_Jmp(blk);
 798
 799                         set_irn_in(lower_blk, 2, in);
 800
 801                         /* create to Phis */
 802                         in[0] = new_Const(get_mode_null(h_res_mode));
 803                         in[1] = new_Const_long(h_res_mode, 0x80000000);
 804
 805                         int_phi = new_r_Phi(lower_blk, 2, in, h_res_mode);
 806
 807                         in[0] = a_f;
 808                         in[1] = new_rd_Sub(dbg, upper_blk, a_f, flt_corr, flt_mode);
 809
 810                         flt_phi = new_r_Phi(lower_blk, 2, in, flt_mode);
 811
 812                         /* fix Phi links for next part_block() */
 813                         set_Block_phis(lower_blk, int_phi);
 814                         set_Phi_next(int_phi, flt_phi);
 815                         set_Phi_next(flt_phi, NULL);
 816
 817                         float_to_ll = new_bd_ia32_l_FloattoLL(dbg, lower_blk, flt_phi);
 818
 819                         l_res = new_r_Proj(lower_blk, float_to_ll, l_res_mode,
 820                                                            pn_ia32_l_FloattoLL_res_low);
 821                         h_res = new_r_Proj(lower_blk, float_to_ll, h_res_mode,
 822                                                            pn_ia32_l_FloattoLL_res_high);
 823
 824                         h_res = new_rd_Add(dbg, lower_blk, h_res, int_phi, h_res_mode);
 825
 826                         /* move the call and its Proj's to the lower block */
 827                         set_nodes_block(call, lower_blk);
 828
 829                         for (proj = get_irn_link(call); proj != NULL; proj = get_irn_link(proj))
 830                                 set_nodes_block(proj, lower_blk);
 831                         block = lower_blk;
 832                 }
 833                 /* lower the call */
 834                 resolve_call(call, l_res, h_res, irg, block);
 835         } else if (n == 2) {
 836                 ir_node *ll_to_float;
 837
 838                 /* We have a Conv long long -> float here */
 839                 ir_node *a_l       = params[BINOP_Left_Low];
 840                 ir_node *a_h       = params[BINOP_Left_High];
 841                 ir_mode *fres_mode = get_type_mode(get_method_res_type(method, 0));
 842
 843                 assert(! mode_is_float(get_irn_mode(a_l))
 844                                 && ! mode_is_float(get_irn_mode(a_h)));
 845
 846                 ll_to_float = new_bd_ia32_l_LLtoFloat(dbg, block, a_h, a_l, fres_mode);
 847
 848                 /* lower the call */
 849                 resolve_call(call, ll_to_float, NULL, irg, block);
 850         } else {
 851                 panic("unexpected Conv call %+F", call);
 852         }
 853
 854         return 1;
 855 }
 856
 857 /* Ia32 implementation of intrinsic mapping. */
 858 ir_entity *ia32_create_intrinsic_fkt(ir_type *method, const ir_op *op,
 859                                      const ir_mode *imode, const ir_mode *omode,
 860                                      void *context)
 861 {
 862         i_record      elt;
 863         ir_entity     **ent = NULL;
 864         i_mapper_func mapper;
 865
 866         if (! intrinsics)
 867                 intrinsics = NEW_ARR_F(i_record, 0);
 868
 869         switch (get_op_code(op)) {
 870         case iro_Add:
 871                 ent    = &i_ents[iro_Add];
 872                 mapper = map_Add;
 873                 break;
 874         case iro_Sub:
 875                 ent    = &i_ents[iro_Sub];
 876                 mapper = map_Sub;
 877                 break;
 878         case iro_Shl:
 879                 ent    = &i_ents[iro_Shl];
 880                 mapper = map_Shl;
 881                 break;
 882         case iro_Shr:
 883                 ent    = &i_ents[iro_Shr];
 884                 mapper = map_Shr;
 885                 break;
 886         case iro_Shrs:
 887                 ent    = &i_ents[iro_Shrs];
 888                 mapper = map_Shrs;
 889                 break;
 890         case iro_Mul:
 891                 ent    = &i_ents[iro_Mul];
 892                 mapper = map_Mul;
 893                 break;
 894         case iro_Minus:
 895                 ent    = &i_ents[iro_Minus];
 896                 mapper = map_Minus;
 897                 break;
 898         case iro_Abs:
 899                 ent    = &i_ents[iro_Abs];
 900                 mapper = map_Abs;
 901                 break;
 902         case iro_Div:
 903                 ent    = &i_ents[iro_Div];
 904                 mapper = map_Div;
 905                 break;
 906         case iro_Mod:
 907                 ent    = &i_ents[iro_Mod];
 908                 mapper = map_Mod;
 909                 break;
 910         case iro_Conv:
 911                 ent    = &i_ents[iro_Conv];
 912                 mapper = map_Conv;
 913                 break;
 914         default:
 915                 fprintf(stderr, "FIXME: unhandled op for ia32 intrinsic function %s\n", get_id_str(op->name));
 916                 return def_create_intrinsic_fkt(method, op, imode, omode, context);
 917         }
 918
 919         if (ent && ! *ent) {
 920 #define IDENT(s)  new_id_from_chars(s, sizeof(s)-1)
 921
 922                 ident *id = id_mangle(IDENT("L"), get_op_ident(op));
 923                 *ent = new_entity(get_glob_type(), id, method);
 924         }
 925
 926         elt.i_call.kind     = INTRINSIC_CALL;
 927         elt.i_call.i_ent    = *ent;
 928         elt.i_call.i_mapper = mapper;
 929         elt.i_call.ctx      = context;
 930         elt.i_call.link     = NULL;
 931
 932         ARR_APP1(i_record, intrinsics, elt);
 933         return *ent;
 934 }