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