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