2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief This file implements the mapping of 64Bit intrinsic
23 * functions to code or library calls.
24 * @author Michael Beck
34 #include "iroptimize.h"
39 #include "ia32_new_nodes.h"
40 #include "bearch_ia32_t.h"
41 #include "gen_ia32_regalloc_if.h"
44 /** The array of all intrinsics that must be mapped. */
45 static i_record *intrinsics;
47 /** An array to cache all entities. */
48 static ir_entity *i_ents[iro_Last + 1];
51 * Maps all intrinsic calls that the backend support
52 * and map all instructions the backend did not support
55 void ia32_handle_intrinsics(void)
57 if (intrinsics && ARR_LEN(intrinsics) > 0) {
58 lower_intrinsics(intrinsics, ARR_LEN(intrinsics), /*part_block_used=*/1);
62 #define BINOP_Left_Low 0
63 #define BINOP_Left_High 1
64 #define BINOP_Right_Low 2
65 #define BINOP_Right_High 3
68 * Reroute edges from the pn_Call_T_result proj of a call.
70 * @param resproj 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
74 static void reroute_result(ir_node *resproj, ir_node *l_res, ir_node *h_res)
76 foreach_out_edge_safe(resproj, edge) {
77 ir_node *proj = get_edge_src_irn(edge);
78 long pn = get_Proj_proj(proj);
81 edges_reroute(proj, l_res);
82 } else if (pn == 1 && h_res != NULL) {
83 edges_reroute(proj, h_res);
85 panic("Unsupported Result-Proj from Call found");
91 * Replace a call be a tuple of l_res, h_res.
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)
99 static void resolve_call(ir_node *call, ir_node *l_res, ir_node *h_res, ir_graph *irg, ir_node *block)
101 ir_node *jmp, *res, *in[2];
102 ir_node *nomem = get_irg_no_mem(irg);
105 if (edges_activated(irg)) {
106 /* use rerouting to prevent some warning in the backend */
107 foreach_out_edge_safe(call, edge) {
108 ir_node *proj = get_edge_src_irn(edge);
109 pn_Call pn = (pn_Call)get_Proj_proj(proj);
112 case pn_Call_X_regular:
114 * We do not check here if this call really has exception and regular Proj's.
115 * new_r_Jmp might than be CSEd with the real exit jmp and then bad things happen
116 * (in movgen.c from 186.crafty for example).
117 * So be sure the newly created Jmp cannot CSE.
119 old_cse = get_opt_cse();
121 jmp = new_r_Jmp(block);
122 set_opt_cse(old_cse);
123 edges_reroute(proj, jmp);
126 case pn_Call_X_except:
127 /* should not happen here */
128 edges_reroute(proj, new_r_Bad(irg, mode_X));
131 /* should not happen here */
132 edges_reroute(proj, nomem);
134 case pn_Call_T_result:
135 reroute_result(proj, l_res, h_res);
138 panic("Wrong Proj from Call");
144 /* no edges, build Tuple */
150 res = new_r_Tuple(block, 2, in);
155 * We do not check here if this call really has exception and regular Proj's.
156 * new_r_Jmp might than be CSEd with the real exit jmp and then bad things happen
157 * (in movgen.c from 186.crafty for example).
158 * So be sure the newly created Jmp cannot CSE.
160 old_cse = get_opt_cse();
162 jmp = new_r_Jmp(block);
163 set_opt_cse(old_cse);
165 turn_into_tuple(call, pn_Call_max+1);
166 set_Tuple_pred(call, pn_Call_M, nomem);
167 set_Tuple_pred(call, pn_Call_X_regular, jmp);
168 set_Tuple_pred(call, pn_Call_X_except, new_r_Bad(irg, mode_X));
169 set_Tuple_pred(call, pn_Call_T_result, res);
174 * Map an Add (a_l, a_h, b_l, b_h)
176 static int map_Add(ir_node *call, void *ctx)
178 dbg_info *dbg = get_irn_dbg_info(call);
179 ir_node *block = get_nodes_block(call);
180 ir_node **params = get_Call_param_arr(call);
181 ir_type *method = get_Call_type(call);
182 ir_node *a_l = params[BINOP_Left_Low];
183 ir_node *a_h = params[BINOP_Left_High];
184 ir_node *b_l = params[BINOP_Right_Low];
185 ir_node *b_h = params[BINOP_Right_High];
186 ir_mode *l_mode = get_type_mode(get_method_res_type(method, 0));
187 ir_mode *h_mode = get_type_mode(get_method_res_type(method, 1));
188 ir_mode *mode_flags = ia32_reg_classes[CLASS_ia32_flags].mode;
189 ir_node *add_low, *add_high, *flags;
190 ir_node *l_res, *h_res;
193 /* l_res = a_l + b_l */
194 /* h_res = a_h + b_h + carry */
196 add_low = new_bd_ia32_l_Add(dbg, block, a_l, b_l, mode_T);
197 flags = new_r_Proj(add_low, mode_flags, pn_ia32_flags);
198 add_high = new_bd_ia32_l_Adc(dbg, block, a_h, b_h, flags, h_mode);
200 l_res = new_r_Proj(add_low, l_mode, pn_ia32_res);
203 resolve_call(call, l_res, h_res, current_ir_graph, block);
208 * Map a Sub (a_l, a_h, b_l, b_h)
210 static int map_Sub(ir_node *call, void *ctx)
212 dbg_info *dbg = get_irn_dbg_info(call);
213 ir_node *block = get_nodes_block(call);
214 ir_node **params = get_Call_param_arr(call);
215 ir_type *method = get_Call_type(call);
216 ir_node *a_l = params[BINOP_Left_Low];
217 ir_node *a_h = params[BINOP_Left_High];
218 ir_node *b_l = params[BINOP_Right_Low];
219 ir_node *b_h = params[BINOP_Right_High];
220 ir_mode *l_mode = get_type_mode(get_method_res_type(method, 0));
221 ir_mode *h_mode = get_type_mode(get_method_res_type(method, 1));
222 ir_mode *mode_flags = ia32_reg_classes[CLASS_ia32_flags].mode;
223 ir_node *sub_low, *sub_high, *flags;
224 ir_node *l_res, *h_res;
227 /* l_res = a_l - b_l */
228 /* h_res = a_h - b_h - carry */
230 sub_low = new_bd_ia32_l_Sub(dbg, block, a_l, b_l, mode_T);
231 flags = new_r_Proj(sub_low, mode_flags, pn_ia32_flags);
232 sub_high = new_bd_ia32_l_Sbb(dbg, block, a_h, b_h, flags, h_mode);
234 l_res = new_r_Proj(sub_low, l_mode, pn_ia32_res);
237 resolve_call(call, l_res, h_res, current_ir_graph, block);
242 * Checks where node high is a sign extension of low.
244 static int is_sign_extend(ir_node *low, ir_node *high)
249 ir_tarval *shift_count;
251 high_r = get_Shrs_right(high);
252 if (!is_Const(high_r)) return 0;
254 shift_count = get_Const_tarval(high_r);
255 if (!tarval_is_long(shift_count)) return 0;
256 if (get_tarval_long(shift_count) != 31) return 0;
258 high_l = get_Shrs_left(high);
260 if (is_Conv(low) && get_Conv_op(low) == high_l) return 1;
261 if (is_Conv(high_l) && get_Conv_op(high_l) == low) return 1;
262 } else if (is_Const(low) && is_Const(high)) {
263 ir_tarval *tl = get_Const_tarval(low);
264 ir_tarval *th = get_Const_tarval(high);
266 if (tarval_is_long(th) && tarval_is_long(tl)) {
267 long l = get_tarval_long(tl);
268 long h = get_tarval_long(th);
270 return (h == 0 && l >= 0) || (h == -1 && l < 0);
278 * Map a Mul (a_l, a_h, b_l, b_h)
280 static int map_Mul(ir_node *call, void *ctx)
282 dbg_info *dbg = get_irn_dbg_info(call);
283 ir_node *block = get_nodes_block(call);
284 ir_node **params = get_Call_param_arr(call);
285 ir_type *method = get_Call_type(call);
286 ir_node *a_l = params[BINOP_Left_Low];
287 ir_node *a_h = params[BINOP_Left_High];
288 ir_node *b_l = params[BINOP_Right_Low];
289 ir_node *b_h = params[BINOP_Right_High];
290 ir_mode *l_mode = get_type_mode(get_method_res_type(method, 0));
291 ir_mode *h_mode = get_type_mode(get_method_res_type(method, 1));
292 ir_node *l_res, *h_res, *mul, *pEDX, *add;
305 /* handle the often used case of 32x32=64 mul */
306 if (is_sign_extend(a_l, a_h) && is_sign_extend(b_l, b_h)) {
307 mul = new_bd_ia32_l_IMul(dbg, block, a_l, b_l);
308 h_res = new_rd_Proj(dbg, mul, h_mode, pn_ia32_l_IMul_res_high);
309 l_res = new_rd_Proj(dbg, mul, l_mode, pn_ia32_l_IMul_res_low);
311 /* note that zero extension is handled hare efficiently */
312 mul = new_bd_ia32_l_Mul(dbg, block, a_l, b_l);
313 pEDX = new_rd_Proj(dbg, mul, h_mode, pn_ia32_l_Mul_res_high);
314 l_res = new_rd_Proj(dbg, mul, l_mode, pn_ia32_l_Mul_res_low);
316 b_l = new_rd_Conv(dbg, block, b_l, h_mode);
317 mul = new_rd_Mul( dbg, block, a_h, b_l, h_mode);
318 add = new_rd_Add( dbg, block, mul, pEDX, h_mode);
319 a_l = new_rd_Conv(dbg, block, a_l, h_mode);
320 mul = new_rd_Mul( dbg, block, a_l, b_h, h_mode);
321 h_res = new_rd_Add( dbg, block, add, mul, h_mode);
323 resolve_call(call, l_res, h_res, current_ir_graph, block);
329 * Map a Minus (a_l, a_h)
331 static int map_Minus(ir_node *call, void *ctx)
333 dbg_info *dbg = get_irn_dbg_info(call);
334 ir_node *block = get_nodes_block(call);
335 ir_node **params = get_Call_param_arr(call);
336 ir_type *method = get_Call_type(call);
337 ir_node *a_l = params[BINOP_Left_Low];
338 ir_node *a_h = params[BINOP_Left_High];
339 ir_mode *l_mode = get_type_mode(get_method_res_type(method, 0));
340 ir_mode *h_mode = get_type_mode(get_method_res_type(method, 1));
341 ir_node *l_res, *h_res, *res;
344 res = new_bd_ia32_Minus64Bit(dbg, block, a_l, a_h);
345 l_res = new_r_Proj(res, l_mode, pn_ia32_Minus64Bit_low_res);
346 h_res = new_r_Proj(res, h_mode, pn_ia32_Minus64Bit_high_res);
348 resolve_call(call, l_res, h_res, current_ir_graph, block);
355 * Map a Abs (a_l, a_h)
357 static int map_Abs(ir_node *call, void *ctx)
359 dbg_info *dbg = get_irn_dbg_info(call);
360 ir_node *block = get_nodes_block(call);
361 ir_node **params = get_Call_param_arr(call);
362 ir_type *method = get_Call_type(call);
363 ir_node *a_l = params[BINOP_Left_Low];
364 ir_node *a_h = params[BINOP_Left_High];
365 ir_mode *l_mode = get_type_mode(get_method_res_type(method, 0));
366 ir_mode *h_mode = get_type_mode(get_method_res_type(method, 1));
367 ir_mode *mode_flags = ia32_reg_classes[CLASS_ia32_flags].mode;
368 ir_node *l_res, *h_res, *sign, *sub_l, *sub_h;
375 Code inspired by gcc output :) (although gcc doubles the
376 operation for t1 as t2 and uses t1 for operations with low part
377 and t2 for operations with high part which is actually unnecessary
378 because t1 and t2 represent the same value)
384 h_res = t3 - t1 - carry
388 /* TODO: give a hint to the backend somehow to not create a cltd here... */
389 sign = new_rd_Shrs(dbg, block, a_h, new_r_Const_long(irg, l_mode, 31), h_mode);
390 sign_l = new_rd_Conv(dbg, block, sign, l_mode);
391 sub_l = new_rd_Eor(dbg, block, a_l, sign_l, l_mode);
392 sub_h = new_rd_Eor(dbg, block, a_h, sign, h_mode);
394 l_sub = new_bd_ia32_l_Sub(dbg, block, sub_l, sign_l, mode_T);
395 l_res = new_r_Proj(l_sub, l_mode, pn_ia32_res);
396 flags = new_r_Proj(l_sub, mode_flags, pn_ia32_flags);
397 h_res = new_bd_ia32_l_Sbb(dbg, block, sub_h, sign, flags, h_mode);
399 resolve_call(call, l_res, h_res, current_ir_graph, block);
405 #define ID(x) new_id_from_chars(x, sizeof(x)-1)
408 * Maps a Div. Change into a library call.
410 static int map_Div(ir_node *call, void *ctx)
412 ia32_intrinsic_env_t *env = (ia32_intrinsic_env_t*)ctx;
413 ir_type *method = get_Call_type(call);
414 ir_mode *h_mode = get_type_mode(get_method_res_type(method, 1));
417 ir_graph *irg = get_irn_irg(call);
420 if (mode_is_signed(h_mode)) {
421 /* 64bit signed Division */
424 /* create library entity */
425 ident *id = ID("__divdi3");
426 ent = env->divdi3 = create_compilerlib_entity(id, method);
429 /* 64bit unsigned Division */
432 /* create library entity */
433 ident *id = ID("__udivdi3");
434 ent = env->udivdi3 = create_compilerlib_entity(id, method);
438 ptr = get_Call_ptr(call);
440 ptr = new_r_SymConst(irg, get_irn_mode(ptr), sym, symconst_addr_ent);
441 set_Call_ptr(call, ptr);
447 * Maps a Mod. Change into a library call
449 static int map_Mod(ir_node *call, void *ctx)
451 ia32_intrinsic_env_t *env = (ia32_intrinsic_env_t*)ctx;
452 ir_type *method = get_Call_type(call);
453 ir_mode *h_mode = get_type_mode(get_method_res_type(method, 1));
456 ir_graph *irg = get_irn_irg(call);
459 if (mode_is_signed(h_mode)) {
460 /* 64bit signed Modulo */
463 /* create library entity */
464 ident *id = ID("__moddi3");
465 ent = env->moddi3 = create_compilerlib_entity(id, method);
468 /* 64bit signed Modulo */
471 /* create library entity */
472 ident *id = ID("__umoddi3");
473 ent = env->umoddi3 = create_compilerlib_entity(id, method);
477 ptr = get_Call_ptr(call);
479 ptr = new_r_SymConst(irg, get_irn_mode(ptr), sym, symconst_addr_ent);
480 set_Call_ptr(call, ptr);
488 static int map_Conv(ir_node *call, void *ctx)
490 ir_graph *irg = current_ir_graph;
491 dbg_info *dbg = get_irn_dbg_info(call);
492 ir_node *block = get_nodes_block(call);
493 ir_node **params = get_Call_param_arr(call);
494 ir_type *method = get_Call_type(call);
495 int n = get_Call_n_params(call);
496 ir_node *l_res, *h_res;
500 ir_node *float_to_ll;
502 /* We have a Conv float -> long long here */
503 ir_node *a_f = params[0];
504 ir_mode *l_res_mode = get_type_mode(get_method_res_type(method, 0));
505 ir_mode *h_res_mode = get_type_mode(get_method_res_type(method, 1));
507 assert(mode_is_float(get_irn_mode(a_f)) && "unexpected Conv call");
509 if (mode_is_signed(h_res_mode)) {
510 /* convert from float to signed 64bit */
511 float_to_ll = new_bd_ia32_l_FloattoLL(dbg, block, a_f);
513 l_res = new_r_Proj(float_to_ll, l_res_mode,
514 pn_ia32_l_FloattoLL_res_low);
515 h_res = new_r_Proj(float_to_ll, h_res_mode,
516 pn_ia32_l_FloattoLL_res_high);
518 /* Convert from float to unsigned 64bit. */
519 ir_tarval *flt_tv = new_tarval_from_str("9223372036854775808", 19, ia32_mode_E);
520 ir_node *flt_corr = new_r_Const(irg, flt_tv);
521 ir_node *lower_blk = block;
523 ir_node *cmp, *proj, *cond, *blk, *int_phi, *flt_phi;
527 upper_blk = get_nodes_block(call);
529 a_f = new_rd_Conv(dbg, upper_blk, a_f, ia32_mode_E);
530 cmp = new_rd_Cmp(dbg, upper_blk, a_f, flt_corr, ir_relation_less);
531 cond = new_rd_Cond(dbg, upper_blk, cmp);
532 in[0] = new_r_Proj(cond, mode_X, pn_Cond_true);
533 in[1] = new_r_Proj(cond, mode_X, pn_Cond_false);
534 blk = new_r_Block(irg, 1, &in[1]);
535 in[1] = new_r_Jmp(blk);
537 set_irn_in(lower_blk, 2, in);
540 in[0] = new_r_Const(irg, get_mode_null(h_res_mode));
541 in[1] = new_r_Const_long(irg, h_res_mode, 0x80000000);
543 int_phi = new_r_Phi(lower_blk, 2, in, h_res_mode);
546 in[1] = new_rd_Sub(dbg, upper_blk, a_f, flt_corr, ia32_mode_E);
548 flt_phi = new_r_Phi(lower_blk, 2, in, ia32_mode_E);
550 /* fix Phi links for next part_block() */
552 add_Block_phi(lower_blk, int_phi);
554 add_Block_phi(lower_blk, flt_phi);
556 float_to_ll = new_bd_ia32_l_FloattoLL(dbg, lower_blk, flt_phi);
558 l_res = new_r_Proj(float_to_ll, l_res_mode,
559 pn_ia32_l_FloattoLL_res_low);
560 h_res = new_r_Proj(float_to_ll, h_res_mode,
561 pn_ia32_l_FloattoLL_res_high);
563 h_res = new_rd_Add(dbg, lower_blk, h_res, int_phi, h_res_mode);
565 /* move the call and its Proj's to the lower block */
566 set_nodes_block(call, lower_blk);
568 for (proj = (ir_node*)get_irn_link(call); proj != NULL;
569 proj = (ir_node*)get_irn_link(proj)) {
570 set_nodes_block(proj, lower_blk);
575 resolve_call(call, l_res, h_res, irg, block);
577 ir_node *ll_to_float;
579 /* We have a Conv long long -> float here */
580 ir_node *a_l = params[BINOP_Left_Low];
581 ir_node *a_h = params[BINOP_Left_High];
582 ir_mode *fres_mode = get_type_mode(get_method_res_type(method, 0));
584 assert(! mode_is_float(get_irn_mode(a_l))
585 && ! mode_is_float(get_irn_mode(a_h)));
587 ll_to_float = new_bd_ia32_l_LLtoFloat(dbg, block, a_h, a_l, fres_mode);
590 resolve_call(call, ll_to_float, NULL, irg, block);
592 panic("unexpected Conv call %+F", call);
598 /* Ia32 implementation of intrinsic mapping. */
599 ir_entity *ia32_create_intrinsic_fkt(ir_type *method, const ir_op *op,
600 const ir_mode *imode, const ir_mode *omode,
604 ir_entity **ent = NULL;
605 i_mapper_func mapper;
608 intrinsics = NEW_ARR_F(i_record, 0);
610 switch (get_op_code(op)) {
612 ent = &i_ents[iro_Add];
616 ent = &i_ents[iro_Sub];
620 ent = &i_ents[iro_Mul];
624 ent = &i_ents[iro_Minus];
628 ent = &i_ents[iro_Div];
632 ent = &i_ents[iro_Mod];
636 ent = &i_ents[iro_Conv];
640 fprintf(stderr, "FIXME: unhandled op for ia32 intrinsic function %s\n", get_id_str(op->name));
641 return def_create_intrinsic_fkt(method, op, imode, omode, context);
645 ident *id = id_mangle(ID("L"), get_op_ident(op));
646 *ent = new_entity(get_glob_type(), id, method);
647 set_entity_visibility(*ent, ir_visibility_private);
650 elt.i_call.kind = INTRINSIC_CALL;
651 elt.i_call.i_ent = *ent;
652 elt.i_call.i_mapper = mapper;
653 elt.i_call.ctx = context;
654 elt.i_call.link = NULL;
656 ARR_APP1(i_record, intrinsics, elt);