11 #include "pseudo_irg.h"
15 #include "iredges_t.h"
22 #include "../bearch.h" /* the general register allocator interface */
23 #include "../benode_t.h"
24 #include "../belower.h"
25 #include "../besched_t.h"
26 #include "bearch_ia32_t.h"
28 #include "ia32_new_nodes.h" /* ia32 nodes interface */
29 #include "gen_ia32_regalloc_if.h" /* the generated interface (register type and class defenitions) */
30 #include "ia32_gen_decls.h" /* interface declaration emitter */
31 #include "ia32_transform.h"
32 #include "ia32_emitter.h"
33 #include "ia32_map_regs.h"
34 #include "ia32_optimize.h"
36 #define DEBUG_MODULE "firm.be.ia32.isa"
39 static set *cur_reg_set = NULL;
42 #define is_Start(irn) (get_irn_opcode(irn) == iro_Start)
44 /**************************************************
47 * _ __ ___ __ _ __ _| | | ___ ___ _| |_
48 * | '__/ _ \/ _` | / _` | | |/ _ \ / __| | | _|
49 * | | | __/ (_| | | (_| | | | (_) | (__ | | |
50 * |_| \___|\__, | \__,_|_|_|\___/ \___| |_|_|
53 **************************************************/
55 static ir_node *my_skip_proj(const ir_node *n) {
61 static int is_Call_Proj(const ir_node *n) {
63 is_Proj(get_Proj_pred(n)) &&
64 get_irn_mode(get_Proj_pred(n)) == mode_T &&
65 is_ia32_Call(get_Proj_pred(get_Proj_pred(n))))
73 static int is_Start_Proj(const ir_node *n) {
75 is_Proj(get_Proj_pred(n)) &&
76 get_irn_mode(get_Proj_pred(n)) == mode_T &&
77 is_Start(get_Proj_pred(get_Proj_pred(n))))
85 static int is_P_frame_base_Proj(const ir_node *n) {
87 is_Start(get_Proj_pred(n)) &&
88 get_Proj_proj(n) == pn_Start_P_frame_base)
96 static int is_used_by_Keep(const ir_node *n) {
97 return be_is_Keep(get_edge_src_irn(get_irn_out_edge_first(n)));
101 * Return register requirements for an ia32 node.
102 * If the node returns a tuple (mode_T) then the proj's
103 * will be asked for this information.
105 static const arch_register_req_t *ia32_get_irn_reg_req(const void *self, arch_register_req_t *req, const ir_node *irn, int pos) {
106 const ia32_register_req_t *irn_req;
107 long node_pos = pos == -1 ? 0 : pos;
108 ir_mode *mode = get_irn_mode(irn);
109 firm_dbg_module_t *mod = firm_dbg_register(DEBUG_MODULE);
110 const ia32_irn_ops_t *ops = self;
112 if (mode == mode_T || mode == mode_M) {
113 DBG((mod, LEVEL_1, "ignoring mode_T, mode_M node %+F\n", irn));
117 DBG((mod, LEVEL_1, "get requirements at pos %d for %+F ... ", pos, irn));
120 if (is_Call_Proj(irn) && is_used_by_Keep(irn)) {
125 irn_req = ia32_projnum_reg_req_map[get_Proj_proj(irn)];
126 memcpy(req, &(irn_req->req), sizeof(*req));
131 else if (is_Start_Proj(irn)) {
132 irn_req = ops->cg->reg_param_req[get_Proj_proj(irn)];
133 assert(irn_req && "missing requirement for regparam");
134 memcpy(req, &(irn_req->req), sizeof(*req));
137 else if (is_Proj(irn)) {
139 node_pos = ia32_translate_proj_pos(irn);
145 irn = my_skip_proj(irn);
147 DB((mod, LEVEL_1, "skipping Proj, going to %+F at pos %d ... ", irn, node_pos));
150 if (is_ia32_irn(irn)) {
152 irn_req = get_ia32_in_req(irn, pos);
155 irn_req = get_ia32_out_req(irn, node_pos);
158 DB((mod, LEVEL_1, "returning reqs for %+F at pos %d\n", irn, pos));
160 memcpy(req, &(irn_req->req), sizeof(*req));
162 if (arch_register_req_is(&(irn_req->req), should_be_same) ||
163 arch_register_req_is(&(irn_req->req), should_be_different)) {
164 assert(irn_req->pos >= 0 && "should be same/different constraint for in -> out NYI");
165 req->other = get_irn_n(irn, irn_req->pos);
169 /* treat Phi like Const with default requirements */
171 DB((mod, LEVEL_1, "returning standard reqs for %+F\n", irn));
172 if (mode_is_float(mode))
173 memcpy(req, &(ia32_default_req_ia32_floating_point.req), sizeof(*req));
174 else if (mode_is_int(mode) || mode_is_reference(mode))
175 memcpy(req, &(ia32_default_req_ia32_general_purpose.req), sizeof(*req));
176 else if (mode == mode_T || mode == mode_M) {
177 DBG((mod, LEVEL_1, "ignoring Phi node %+F\n", irn));
181 assert(0 && "unsupported Phi-Mode");
183 else if (is_Start(irn)) {
184 DB((mod, LEVEL_1, "returning reqs none for ProjX -> Start (%+F )\n", irn));
186 case pn_Start_X_initial_exec:
187 case pn_Start_P_value_arg_base:
188 case pn_Start_P_globals:
189 case pn_Start_P_frame_base:
190 memcpy(req, &(ia32_default_req_none.req), sizeof(*req));
192 case pn_Start_T_args:
193 assert(0 && "ProjT(pn_Start_T_args) should not be asked");
196 else if (get_irn_op(irn) == op_Return && pos > 0) {
197 DB((mod, LEVEL_1, "returning reqs EAX for %+F\n", irn));
198 memcpy(req, &(ia32_default_req_ia32_general_purpose_eax.req), sizeof(*req));
201 DB((mod, LEVEL_1, "returning NULL for %+F (not ia32)\n", irn));
209 static void ia32_set_irn_reg(const void *self, ir_node *irn, const arch_register_t *reg) {
212 if ((is_Call_Proj(irn) && is_used_by_Keep(irn)) ||
213 is_P_frame_base_Proj(irn) ||
216 /* don't skip the proj, we want to take the else below */
218 else if (is_Proj(irn)) {
219 pos = ia32_translate_proj_pos(irn);
220 irn = my_skip_proj(irn);
223 if (is_ia32_irn(irn)) {
224 const arch_register_t **slots;
226 slots = get_ia32_slots(irn);
230 ia32_set_firm_reg(irn, reg, cur_reg_set);
234 static const arch_register_t *ia32_get_irn_reg(const void *self, const ir_node *irn) {
236 const arch_register_t *reg = NULL;
238 if ((is_Call_Proj(irn) && is_used_by_Keep(irn)) ||
239 is_P_frame_base_Proj(irn) ||
242 /* don't skip the proj, we want to take the else below */
244 else if (is_Proj(irn)) {
245 pos = ia32_translate_proj_pos(irn);
246 irn = my_skip_proj(irn);
249 if (is_ia32_irn(irn)) {
250 const arch_register_t **slots;
251 slots = get_ia32_slots(irn);
255 reg = ia32_get_firm_reg(irn, cur_reg_set);
261 static arch_irn_class_t ia32_classify(const void *self, const ir_node *irn) {
262 irn = my_skip_proj(irn);
264 return arch_irn_class_branch;
265 else if (is_ia32_Call(irn))
266 return arch_irn_class_call;
267 else if (is_ia32_irn(irn))
268 return arch_irn_class_normal;
273 static arch_irn_flags_t ia32_get_flags(const void *self, const ir_node *irn) {
274 irn = my_skip_proj(irn);
275 if (is_ia32_irn(irn))
276 return get_ia32_flags(irn);
278 if (is_Start_Proj(irn))
279 return arch_irn_flags_ignore;
285 /* fill register allocator interface */
287 static const arch_irn_ops_if_t ia32_irn_ops_if = {
288 ia32_get_irn_reg_req,
295 ia32_irn_ops_t ia32_irn_ops = {
302 /**************************************************
305 * ___ ___ __| | ___ __ _ ___ _ __ _| |_
306 * / __/ _ \ / _` |/ _ \/ _` |/ _ \ '_ \ | | _|
307 * | (_| (_) | (_| | __/ (_| | __/ | | | | | |
308 * \___\___/ \__,_|\___|\__, |\___|_| |_| |_|_|
311 **************************************************/
313 static void check_for_alloca(ir_node *irn, void *env) {
314 int *has_alloca = env;
316 if (get_irn_op(irn) == op_Alloc) {
317 if (get_Alloc_where(irn) == stack_alloc) {
324 * Transforms the standard firm graph into
327 static void ia32_prepare_graph(void *self) {
328 ia32_code_gen_t *cg = self;
330 if (! is_pseudo_ir_graph(cg->irg)) {
331 /* If there is a alloca in the irg, we use %ebp for stack addressing */
332 /* instead of %esp, as alloca destroys %esp. */
336 /* check for alloca node */
337 irg_walk_blkwise_graph(cg->irg, check_for_alloca, NULL, &(cg->has_alloca));
339 if (cg->has_alloca) {
340 ia32_general_purpose_regs[REG_EBP].type = arch_register_type_ignore;
343 irg_walk_blkwise_graph(cg->irg, ia32_place_consts, ia32_transform_node, cg);
350 * Stack reservation and StackParam lowering.
352 static void ia32_finish_irg(ir_graph *irg, ia32_code_gen_t *cg) {
353 firm_dbg_module_t *mod = cg->mod;
354 ir_node *frame = get_irg_frame(irg);
355 ir_node *end_block = get_irg_end_block(irg);
356 ir_node **returns, **in, **new_in;
357 ir_node *stack_reserve, *sched_point;
358 ir_node *stack_free, *new_ret, *return_block;
359 int stack_size = 0, i, n_arg;
360 arch_register_t *stack_reg;
361 tarval *stack_size_tv;
364 /* Determine stack register */
365 if (cg->has_alloca) {
366 stack_reg = &ia32_general_purpose_regs[REG_EBP];
369 stack_reg = &ia32_general_purpose_regs[REG_ESP];
372 /* If frame is used, then we need to reserve some stackspace. */
373 if (get_irn_n_edges(frame) > 0) {
374 /* The initial stack reservation. */
375 stack_size = get_type_size_bytes(get_irg_frame_type(irg));
376 frame_dbg = get_irn_dbg_info(frame);
377 stack_reserve = new_rd_ia32_Sub_i(frame_dbg, irg, get_nodes_block(frame), new_NoMem(), mode_Is);
378 stack_size_tv = new_tarval_from_long(stack_size, mode_Is);
379 set_ia32_Immop_tarval(stack_reserve, stack_size_tv);
381 assert(stack_size && "bOrken stack layout");
383 /* reroute all edges from frame pointer to corrected frame pointer */
384 edges_reroute(frame, stack_reserve, irg);
385 set_irn_n(stack_reserve, 0, frame);
387 /* schedule frame pointer */
388 if (! sched_is_scheduled(frame)) {
389 sched_add_after(get_irg_start(irg), frame);
393 arch_set_irn_register(cg->arch_env, frame, stack_reg);
394 arch_set_irn_register(cg->arch_env, stack_reserve, stack_reg);
396 /* insert into schedule */
397 sched_add_after(frame, stack_reserve);
399 /* Free stack for each Return node */
400 returns = get_Block_cfgpred_arr(end_block);
401 for (i = 0; i < get_Block_n_cfgpreds(end_block); i++) {
402 assert(get_irn_opcode(returns[i]) == iro_Return && "cfgpred of endblock is not a return");
404 return_block = get_nodes_block(returns[i]);
407 stack_free = new_rd_ia32_Add_i(frame_dbg, irg, return_block, stack_reserve, mode_Is);
408 set_ia32_Immop_tarval(stack_free, stack_size_tv);
409 arch_set_irn_register(cg->arch_env, stack_free, stack_reg);
411 DBG((mod, LEVEL_1, "examining %+F, %+F created, block %+F", returns[i], stack_free, return_block));
413 /* get the old Return arguments */
414 n_arg = get_Return_n_ress(returns[i]);
415 in = get_Return_res_arr(returns[i]);
416 new_in = xmalloc((n_arg + 2) * sizeof(new_in[0]));
419 printf("\nMUAAAAHAHAHAHAHAHAHAH\n");
423 /* copy the old to the new in's */
424 memcpy(new_in, in, n_arg * sizeof(in[0]));
425 new_in[n_arg++] = stack_free;
426 new_in[n_arg++] = get_Return_mem(returns[i]);
428 /* create the new return node */
429 new_ret = new_rd_ia32_Return(get_irn_dbg_info(returns[i]), irg, return_block, n_arg, new_in);
430 sched_point = sched_prev(returns[i]);
431 sched_remove(returns[i]);
433 /* exchange the old return with the new one */
434 exchange(returns[i], new_ret);
436 DB((mod, LEVEL_1, " ... replaced with %+F\n", new_ret));
438 /* remove the old one from schedule and add the new nodes properly */
439 sched_add_after(sched_point, new_ret);
440 sched_add_before(new_ret, stack_free);
448 * Dummy functions for hooks we don't need but which must be filled.
450 static void ia32_before_sched(void *self) {
451 ia32_code_gen_t *cg = self;
453 lower_nodes_before_sched(cg->irg, cg->arch_env);
456 static void ia32_before_ra(void *self) {
461 * Creates a Store for a Spill
463 static ir_node *ia32_lower_spill(void *self, ir_node *spill) {
464 ia32_code_gen_t *cg = self;
465 dbg_info *dbg = get_irn_dbg_info(spill);
466 ir_node *block = get_nodes_block(spill);
467 ir_node *ptr = get_irg_frame(cg->irg);
468 ir_node *val = be_get_Spill_context(spill);
469 ir_node *mem = new_rd_NoMem(cg->irg);
470 ir_mode *mode = get_irn_mode(spill);
472 entity *ent = be_get_spill_entity(spill);
473 unsigned offs = get_entity_offset_bytes(ent);
475 DB((cg->mod, LEVEL_1, "lower_spill: got offset %d for %+F\n", offs, ent));
477 res = new_rd_ia32_Store(dbg, cg->irg, block, ptr, val, mem, mode);
478 set_ia32_am_offs(res, new_tarval_from_long(offs, mode_Iu));
484 * Create a Load for a Spill
486 static ir_node *ia32_lower_reload(void *self, ir_node *reload) {
487 ia32_code_gen_t *cg = self;
488 dbg_info *dbg = get_irn_dbg_info(reload);
489 ir_node *block = get_nodes_block(reload);
490 ir_node *ptr = get_irg_frame(cg->irg);
491 ir_mode *mode = get_irn_mode(reload);
492 ir_node *pred = get_irn_n(reload, 0);
496 if (be_is_Spill(pred)) {
497 entity *ent = be_get_spill_entity(pred);
498 unsigned offs = get_entity_offset_bytes(ent);
499 DB((cg->mod, LEVEL_1, "lower_reload: got offset %d for %+F\n", offs, ent));
500 tv = new_tarval_from_long(offs, mode_Iu);
502 else if (is_ia32_Store(pred)) {
503 tv = get_ia32_am_offs(pred);
506 assert(0 && "unsupported Reload predecessor");
509 res = new_rd_ia32_Load(dbg, cg->irg, block, ptr, pred, mode);
510 set_ia32_am_offs(res, tv);
516 * Return the stack register for this irg.
518 static const arch_register_t *ia32_get_stack_register(void *self) {
519 ia32_code_gen_t *cg = self;
521 if (cg->has_alloca) {
522 return &ia32_general_purpose_regs[REG_EBP];
525 return &ia32_general_purpose_regs[REG_ESP];
529 * Emits the code, closes the output file and frees
530 * the code generator interface.
532 static void ia32_codegen(void *self) {
533 ia32_code_gen_t *cg = self;
534 ir_graph *irg = cg->irg;
537 if (cg->emit_decls) {
538 ia32_gen_decls(cg->out);
542 ia32_finish_irg(irg, cg);
543 dump_ir_block_graph_sched(irg, "-finished");
544 ia32_gen_routine(out, irg, cg);
548 /* de-allocate code generator */
549 del_set(cg->reg_set);
553 static void *ia32_cg_init(FILE *F, ir_graph *irg, const arch_env_t *arch_env);
555 static const arch_code_generator_if_t ia32_code_gen_if = {
558 ia32_before_sched, /* before scheduling hook */
559 ia32_before_ra, /* before register allocation hook */
562 ia32_get_stack_register,
563 ia32_codegen /* emit && done */
567 * Initializes the code generator.
569 static void *ia32_cg_init(FILE *F, ir_graph *irg, const arch_env_t *arch_env) {
570 ia32_isa_t *isa = (ia32_isa_t *)arch_env->isa;
571 ia32_code_gen_t *cg = xmalloc(sizeof(*cg));
573 cg->impl = &ia32_code_gen_if;
575 cg->reg_set = new_set(ia32_cmp_irn_reg_assoc, 1024);
576 cg->mod = firm_dbg_register("firm.be.ia32.cg");
578 cg->arch_env = arch_env;
582 if (isa->num_codegens > 1)
587 cur_reg_set = cg->reg_set;
589 ia32_irn_ops.cg = cg;
591 return (arch_code_generator_t *)cg;
596 /*****************************************************************
597 * ____ _ _ _____ _____
598 * | _ \ | | | | |_ _|/ ____| /\
599 * | |_) | __ _ ___| | _____ _ __ __| | | | | (___ / \
600 * | _ < / _` |/ __| |/ / _ \ '_ \ / _` | | | \___ \ / /\ \
601 * | |_) | (_| | (__| < __/ | | | (_| | _| |_ ____) / ____ \
602 * |____/ \__,_|\___|_|\_\___|_| |_|\__,_| |_____|_____/_/ \_\
604 *****************************************************************/
607 * Initializes the backend ISA and opens the output file.
609 static void *ia32_init(void) {
610 static int inited = 0;
611 ia32_isa_t *isa = xmalloc(sizeof(*isa));
613 isa->impl = &ia32_isa_if;
620 isa->num_codegens = 0;
621 isa->reg_projnum_map = new_set(ia32_cmp_reg_projnum_assoc, 1024);
623 ia32_register_init(isa);
624 ia32_create_opcodes();
632 * Closes the output file and frees the ISA structure.
634 static void ia32_done(void *self) {
640 static int ia32_get_n_reg_class(const void *self) {
644 static const arch_register_class_t *ia32_get_reg_class(const void *self, int i) {
645 assert(i >= 0 && i < N_CLASSES && "Invalid ia32 register class requested.");
646 return &ia32_reg_classes[i];
649 static const void *ia32_get_irn_ops(const arch_irn_handler_t *self, const ir_node *irn) {
650 return &ia32_irn_ops;
653 const arch_irn_handler_t ia32_irn_handler = {
657 const arch_irn_handler_t *ia32_get_irn_handler(const void *self) {
658 return &ia32_irn_handler;
661 long ia32_handle_call_proj(const void *self, ir_node *proj, int is_keep) {
662 ia32_isa_t *isa = (ia32_isa_t *)self;
663 long pn = get_Proj_proj(proj);
666 /* It's not a Keep proj, which means, that it is a result proj. */
667 /* Possible result proj numbers are 0 and 1 */
668 /* Set the correct register (depends on the mode) and the */
669 /* corresponding proj number */
670 if (mode_is_float(get_irn_mode(proj))) {
671 assert(pn == 0 && "only one floating point result supported");
673 /* Get the proj number for the floating point result */
674 pn = ia32_get_reg_projnum(&ia32_floating_point_regs[REG_XMM0], isa->reg_projnum_map);
677 /* In case of 64bit return value, the result is */
678 /* in EDX:EAX and we have two result projs. */
681 pn = ia32_get_reg_projnum(&ia32_floating_point_regs[REG_EAX], isa->reg_projnum_map);
684 pn = ia32_get_reg_projnum(&ia32_floating_point_regs[REG_EDX], isa->reg_projnum_map);
687 assert(0 && "only two int results supported");
691 /* Set the correct proj number */
692 set_Proj_proj(proj, pn);
695 /* Set mode to floating point if required */
696 if (!strcmp(ia32_reg_classes[CLASS_ia32_floating_point].name,
697 ia32_projnum_reg_req_map[pn]->req.cls->name)) {
698 set_irn_mode(proj, mode_F);
705 int ia32_to_appear_in_schedule(void *block_env, const ir_node *irn) {
706 return is_ia32_irn(irn);
710 * Initializes the code generator interface.
712 static const arch_code_generator_if_t *ia32_get_code_generator_if(void *self) {
713 return &ia32_code_gen_if;
716 list_sched_selector_t ia32_sched_selector;
719 * Returns the reg_pressure scheduler with to_appear_in_schedule() overloaded
721 static const list_sched_selector_t *ia32_get_list_sched_selector(const void *self) {
722 memcpy(&ia32_sched_selector, reg_pressure_selector, sizeof(list_sched_selector_t));
723 ia32_sched_selector.to_appear_in_schedule = ia32_to_appear_in_schedule;
724 return &ia32_sched_selector;
728 static void ia32_register_options(lc_opt_entry_t *ent)
731 #endif /* WITH_LIBCORE */
733 const arch_isa_if_t ia32_isa_if = {
735 ia32_register_options,
739 ia32_get_n_reg_class,
741 ia32_get_irn_handler,
742 ia32_get_code_generator_if,
743 ia32_get_list_sched_selector,
744 ia32_handle_call_proj