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 The main mips backend driver file.
23 * @author Matthias Braun, Mehdi
30 #include "pseudo_irg.h"
47 #include "../bearch_t.h"
48 #include "../benode_t.h"
49 #include "../belower.h"
50 #include "../besched_t.h"
51 #include "../beblocksched.h"
52 #include "../beirg_t.h"
55 #include "../bemachine.h"
56 #include "../bemodule.h"
57 #include "../bespillslots.h"
58 #include "../beemitter.h"
59 #include "../begnuas.h"
61 #include "bearch_mips_t.h"
63 #include "mips_new_nodes.h"
64 #include "gen_mips_regalloc_if.h"
65 #include "mips_transform.h"
66 #include "mips_emitter.h"
67 #include "mips_map_regs.h"
68 #include "mips_util.h"
69 #include "mips_scheduler.h"
71 #define DEBUG_MODULE "firm.be.mips.isa"
73 /* TODO: ugly, but we need it to get access to the registers assigned to Phi nodes */
74 static set *cur_reg_set = NULL;
76 /**************************************************
79 * _ __ ___ __ _ __ _| | | ___ ___ _| |_
80 * | '__/ _ \/ _` | / _` | | |/ _ \ / __| | | _|
81 * | | | __/ (_| | | (_| | | | (_) | (__ | | |
82 * |_| \___|\__, | \__,_|_|_|\___/ \___| |_|_|
85 **************************************************/
88 * Return register requirements for a mips node.
89 * If the node returns a tuple (mode_T) then the proj's
90 * will be asked for this information.
93 arch_register_req_t *mips_get_irn_reg_req(const ir_node *node, int pos)
95 long node_pos = pos == -1 ? 0 : pos;
96 ir_mode *mode = get_irn_mode(node);
98 if (is_Block(node) || mode == mode_X || mode == mode_M) {
99 return arch_no_register_req;
102 if (mode == mode_T && pos < 0) {
103 return arch_no_register_req;
107 /* in case of a proj, we need to get the correct OUT slot */
108 /* of the node corresponding to the proj number */
110 node_pos = mips_translate_proj_pos(node);
116 node = skip_Proj_const(node);
119 /* get requirements for our own nodes */
120 if (is_mips_irn(node)) {
121 const arch_register_req_t *req;
123 req = get_mips_in_req(node, pos);
125 req = get_mips_out_req(node, node_pos);
131 /* unknown should be translated by now */
132 assert(!is_Unknown(node));
134 return arch_no_register_req;
137 static void mips_set_irn_reg(ir_node *irn, const arch_register_t *reg)
143 if (get_irn_mode(irn) == mode_X) {
147 pos = mips_translate_proj_pos(irn);
148 irn = skip_Proj(irn);
151 if (is_mips_irn(irn)) {
152 const arch_register_t **slots;
154 slots = get_mips_slots(irn);
157 /* here we set the registers for the Phi nodes */
158 mips_set_firm_reg(irn, reg, cur_reg_set);
162 static const arch_register_t *mips_get_irn_reg(const ir_node *irn)
165 const arch_register_t *reg = NULL;
169 if (get_irn_mode(irn) == mode_X) {
173 pos = mips_translate_proj_pos(irn);
174 irn = skip_Proj_const(irn);
177 if (is_mips_irn(irn)) {
178 const arch_register_t **slots;
179 slots = get_mips_slots(irn);
183 reg = mips_get_firm_reg(irn, cur_reg_set);
189 static arch_irn_class_t mips_classify(const ir_node *irn)
191 irn = skip_Proj_const(irn);
194 return arch_irn_class_branch;
195 } else if (is_mips_irn(irn)) {
196 return arch_irn_class_normal;
202 static arch_irn_flags_t mips_get_flags(const ir_node *irn)
204 irn = skip_Proj_const(irn);
206 if (!is_mips_irn(irn))
209 return get_mips_flags(irn);
212 int mips_is_Load(const ir_node *node)
214 return is_mips_lw(node) || is_mips_lh(node) || is_mips_lhu(node) ||
215 is_mips_lb(node) || is_mips_lbu(node);
218 int mips_is_Store(const ir_node *node)
220 return is_mips_sw(node) || is_mips_sh(node) || is_mips_sb(node);
223 static ir_entity *mips_get_frame_entity(const ir_node *node)
225 const mips_load_store_attr_t *attr;
227 if(!is_mips_irn(node))
229 if(!mips_is_Load(node) && !mips_is_Store(node))
232 attr = get_mips_load_store_attr_const(node);
233 return attr->stack_entity;
236 static void mips_set_frame_entity(ir_node *node, ir_entity *entity)
238 mips_load_store_attr_t *attr;
240 if(!is_mips_irn(node)) {
241 panic("trying to set frame entity on non load/store node %+F", node);
243 if(!mips_is_Load(node) && !mips_is_Store(node)) {
244 panic("trying to set frame entity on non load/store node %+F", node);
247 attr = get_irn_generic_attr(node);
248 attr->stack_entity = entity;
252 * This function is called by the generic backend to correct offsets for
253 * nodes accessing the stack.
255 static void mips_set_frame_offset(ir_node *node, int offset)
257 mips_load_store_attr_t *attr;
259 if(!is_mips_irn(node)) {
260 panic("trying to set frame offset on non load/store node %+F", node);
262 if(!mips_is_Load(node) && !mips_is_Store(node)) {
263 panic("trying to set frame offset on non load/store node %+F", node);
266 attr = get_irn_generic_attr(node);
267 attr->offset += offset;
269 if(attr->offset < -32768 || attr->offset > 32767) {
270 panic("Out of stack space! (mips supports only 16bit offsets)");
274 static int mips_get_sp_bias(const ir_node *irn)
280 /* fill register allocator interface */
282 static const arch_irn_ops_t mips_irn_ops = {
283 mips_get_irn_reg_req,
288 mips_get_frame_entity,
289 mips_set_frame_entity,
290 mips_set_frame_offset,
292 NULL, /* get_inverse */
293 NULL, /* get_op_estimated_cost */
294 NULL, /* possible_memory_operand */
295 NULL, /* perform_memory_operand */
298 /**************************************************
301 * ___ ___ __| | ___ __ _ ___ _ __ _| |_
302 * / __/ _ \ / _` |/ _ \/ _` |/ _ \ '_ \ | | _|
303 * | (_| (_) | (_| | __/ (_| | __/ | | | | | |
304 * \___\___/ \__,_|\___|\__, |\___|_| |_| |_|_|
307 **************************************************/
310 * Transforms the standard firm graph into
313 static void mips_prepare_graph(void *self) {
314 mips_code_gen_t *cg = self;
316 /* do local optimizations */
317 optimize_graph_df(cg->irg);
319 /* TODO: we often have dead code reachable through out-edges here. So for
320 * now we rebuild edges (as we need correct user count for code selection)
323 edges_deactivate(cg->irg);
324 edges_activate(cg->irg);
327 // walk the graph and transform firm nodes into mips nodes where possible
328 mips_transform_graph(cg);
329 dump_ir_block_graph_sched(cg->irg, "-transformed");
331 /* do local optimizations (mainly CSE) */
332 optimize_graph_df(cg->irg);
334 /* do code placement, to optimize the position of constants */
337 be_dump(cg->irg, "-place", dump_ir_block_graph_sched);
341 * Called immediately before emit phase.
343 static void mips_finish_irg(void *self) {
344 mips_code_gen_t *cg = self;
345 ir_graph *irg = cg->irg;
347 /* create block schedule, this also removes empty blocks which might
348 * produce critical edges */
349 cg->block_schedule = be_create_block_schedule(irg, cg->birg->exec_freq);
351 dump_ir_block_graph_sched(irg, "-mips-finished");
356 * These are some hooks which must be filled but are probably not needed.
358 static void mips_before_sched(void *self)
363 static void mips_before_ra(void *self)
368 static void mips_after_ra(void* self)
370 mips_code_gen_t *cg = self;
371 be_coalesce_spillslots(cg->birg);
372 irg_walk_blkwise_graph(cg->irg, NULL, mips_after_ra_walker, self);
376 * Emits the code, closes the output file and frees
377 * the code generator interface.
379 static void mips_emit_and_done(void *self)
381 mips_code_gen_t *cg = self;
382 ir_graph *irg = cg->irg;
385 mips_gen_routine(cg, irg);
389 /* de-allocate code generator */
390 del_set(cg->reg_set);
394 static void *mips_cg_init(be_irg_t *birg);
396 static const arch_code_generator_if_t mips_code_gen_if = {
398 NULL, /* get_pic_base */
399 NULL, /* before abi introduce */
402 mips_before_sched, /* before scheduling hook */
403 mips_before_ra, /* before register allocation hook */
410 * Initializes the code generator.
412 static void *mips_cg_init(be_irg_t *birg)
414 const arch_env_t *arch_env = be_get_birg_arch_env(birg);
415 mips_isa_t *isa = (mips_isa_t *) arch_env;
416 mips_code_gen_t *cg = xmalloc(sizeof(*cg));
417 memset(cg, 0, sizeof(*cg));
419 cg->impl = &mips_code_gen_if;
420 cg->irg = be_get_birg_irg(birg);
421 cg->reg_set = new_set(mips_cmp_irn_reg_assoc, 1024);
422 cg->arch_env = arch_env;
426 cur_reg_set = cg->reg_set;
430 return (arch_code_generator_t *)cg;
434 /*****************************************************************
435 * ____ _ _ _____ _____
436 * | _ \ | | | | |_ _|/ ____| /\
437 * | |_) | __ _ ___| | _____ _ __ __| | | | | (___ / \
438 * | _ < / _` |/ __| |/ / _ \ '_ \ / _` | | | \___ \ / /\ \
439 * | |_) | (_| | (__| < __/ | | | (_| | _| |_ ____) / ____ \
440 * |____/ \__,_|\___|_|\_\___|_| |_|\__,_| |_____|_____/_/ \_\
442 *****************************************************************/
444 static mips_isa_t mips_isa_template = {
447 &mips_gp_regs[REG_SP],
448 &mips_gp_regs[REG_FP],
449 -1, /* stack direction */
450 2, /* power of two stack alignment for calls, 2^2 == 4 */
451 NULL, /* main environment */
453 5, /* reload costs */
459 * Initializes the backend ISA and opens the output file.
461 static arch_env_t *mips_init(FILE *file_handle) {
462 static int inited = 0;
469 isa = xcalloc(1, sizeof(isa[0]));
470 memcpy(isa, &mips_isa_template, sizeof(isa[0]));
472 be_emit_init(file_handle);
474 mips_register_init();
475 mips_create_opcodes(&mips_irn_ops);
476 // mips_init_opcode_transforms();
478 /* we mark referenced global entities, so we can only emit those which
479 * are actually referenced. (Note: you mustn't use the type visited flag
480 * elsewhere in the backend)
482 inc_master_type_visited();
484 return &isa->arch_env;
488 * Closes the output file and frees the ISA structure.
490 static void mips_done(void *self)
492 mips_isa_t *isa = self;
494 be_gas_emit_decls(isa->arch_env.main_env, 1);
500 static unsigned mips_get_n_reg_class(const void *self)
506 static const arch_register_class_t *mips_get_reg_class(const void *self,
510 assert(i < N_CLASSES);
511 return &mips_reg_classes[i];
517 * Get the register class which shall be used to store a value of a given mode.
518 * @param self The this pointer.
519 * @param mode The mode in question.
520 * @return A register class which can hold values of the given mode.
522 const arch_register_class_t *mips_get_reg_class_for_mode(const void *self,
527 ASSERT_NO_FLOAT(mode);
528 return &mips_reg_classes[CLASS_mips_gp];
532 be_abi_call_flags_bits_t flags;
533 const arch_env_t *arch_env;
535 // do special handling to support debuggers
539 static void *mips_abi_init(const be_abi_call_t *call, const arch_env_t *arch_env, ir_graph *irg)
541 mips_abi_env_t *env = xmalloc(sizeof(env[0]));
542 be_abi_call_flags_t fl = be_abi_call_get_flags(call);
543 env->flags = fl.bits;
545 env->arch_env = arch_env;
550 static void mips_abi_dont_save_regs(void *self, pset *s)
552 mips_abi_env_t *env = self;
554 if(env->flags.try_omit_fp)
555 pset_insert_ptr(s, env->arch_env->bp);
558 static const arch_register_t *mips_abi_prologue(void *self, ir_node** mem, pmap *reg_map, int *stack_bias)
560 mips_abi_env_t *env = self;
561 ir_graph *irg = env->irg;
562 ir_node *block = get_irg_start_block(env->irg);
563 ir_node *sp = be_abi_reg_map_get(reg_map, &mips_gp_regs[REG_SP]);
564 ir_node *fp = be_abi_reg_map_get(reg_map, &mips_gp_regs[REG_FP]);
565 int initialstackframesize;
571 * The calling conventions wants a stack frame of at least 24bytes size with
572 * a0-a3 saved in offset 0-12
573 * fp saved in offset 16
574 * ra saved in offset 20
577 ir_node *sync, *reg, *store;
578 initialstackframesize = 24;
580 // - setup first part of stackframe
581 sp = new_rd_mips_addu(NULL, irg, block, sp,
582 mips_create_Immediate(initialstackframesize));
583 mips_set_irn_reg(sp, &mips_gp_regs[REG_SP]);
584 set_mips_flags(sp, arch_irn_flags_ignore);
586 /* TODO: where to get an edge with a0-a3
588 for(i = 0; i < 4; ++i) {
589 ir_node *reg = be_abi_reg_map_get(reg_map, &mips_gp_regs[REG_A0 + i]);
590 ir_node *store = new_rd_mips_store_r(dbg, irg, block, *mem, sp, reg, mode_T);
591 attr = get_mips_attr(store);
592 attr->load_store_mode = mode_Iu;
593 attr->tv = new_tarval_from_long(i * 4, mode_Is);
595 mm[i] = new_r_Proj(irg, block, store, mode_M, pn_Store_M);
599 reg = be_abi_reg_map_get(reg_map, &mips_gp_regs[REG_FP]);
600 store = new_rd_mips_sw(NULL, irg, block, sp, reg, *mem, NULL, 16);
604 reg = be_abi_reg_map_get(reg_map, &mips_gp_regs[REG_RA]);
605 store = new_rd_mips_sw(NULL, irg, block, sp, reg, *mem, NULL, 20);
609 /* Note: ideally we would route these mem edges directly towards the
610 * epilogue, but this is currently not supported so we sync all mems
612 sync = new_r_Sync(irg, block, 2, mm+4);
615 ir_node *reg, *store;
616 initialstackframesize = 4;
618 // save old framepointer
619 sp = new_rd_mips_addu(NULL, irg, block, sp,
620 mips_create_Immediate(-initialstackframesize));
621 mips_set_irn_reg(sp, &mips_gp_regs[REG_SP]);
622 set_mips_flags(sp, arch_irn_flags_ignore);
624 reg = be_abi_reg_map_get(reg_map, &mips_gp_regs[REG_FP]);
625 store = new_rd_mips_sw(NULL, irg, block, sp, reg, *mem, NULL, 0);
630 // setup framepointer
631 fp = new_rd_mips_addu(NULL, irg, block, sp,
632 mips_create_Immediate(-initialstackframesize));
633 mips_set_irn_reg(fp, &mips_gp_regs[REG_FP]);
634 set_mips_flags(fp, arch_irn_flags_ignore);
636 be_abi_reg_map_set(reg_map, &mips_gp_regs[REG_FP], fp);
637 be_abi_reg_map_set(reg_map, &mips_gp_regs[REG_SP], sp);
639 return &mips_gp_regs[REG_SP];
642 static void mips_abi_epilogue(void *self, ir_node *block, ir_node **mem, pmap *reg_map)
644 mips_abi_env_t *env = self;
646 ir_graph *irg = env->irg;
647 ir_node *sp = be_abi_reg_map_get(reg_map, &mips_gp_regs[REG_SP]);
648 ir_node *fp = be_abi_reg_map_get(reg_map, &mips_gp_regs[REG_FP]);
650 int initial_frame_size = env->debug ? 24 : 4;
651 int fp_save_offset = env->debug ? 16 : 0;
654 sp = new_rd_mips_or(NULL, irg, block, fp, mips_create_zero());
655 mips_set_irn_reg(sp, &mips_gp_regs[REG_SP]);
656 set_mips_flags(sp, arch_irn_flags_ignore);
659 load = new_rd_mips_lw(NULL, irg, block, sp, *mem, NULL,
660 fp_save_offset - initial_frame_size);
661 set_mips_flags(load, arch_irn_flags_ignore);
663 fp = new_r_Proj(irg, block, load, mode_Iu, pn_mips_lw_res);
664 *mem = new_r_Proj(irg, block, load, mode_Iu, pn_mips_lw_M);
665 arch_set_irn_register(env->arch_env, fp, &mips_gp_regs[REG_FP]);
667 be_abi_reg_map_set(reg_map, &mips_gp_regs[REG_FP], fp);
668 be_abi_reg_map_set(reg_map, &mips_gp_regs[REG_SP], sp);
672 * Produces the type which sits between the stack args and the locals on the stack.
673 * it will contain the return address and space to store the old frame pointer.
674 * @return The Firm type modelling the ABI between type.
676 static ir_type *mips_abi_get_between_type(void *self) {
677 mips_abi_env_t *env = self;
679 static ir_type *debug_between_type = NULL;
680 static ir_type *opt_between_type = NULL;
681 static ir_entity *old_fp_ent = NULL;
683 if(env->debug && debug_between_type == NULL) {
684 ir_entity *a0_ent, *a1_ent, *a2_ent, *a3_ent;
685 ir_entity *ret_addr_ent;
686 ir_type *ret_addr_type = new_type_primitive(new_id_from_str("return_addr"), mode_P);
687 ir_type *old_fp_type = new_type_primitive(new_id_from_str("fp"), mode_P);
688 ir_type *old_param_type = new_type_primitive(new_id_from_str("param"), mode_Iu);
690 debug_between_type = new_type_class(new_id_from_str("mips_between_type"));
691 a0_ent = new_entity(debug_between_type, new_id_from_str("a0_ent"), old_param_type);
692 a1_ent = new_entity(debug_between_type, new_id_from_str("a1_ent"), old_param_type);
693 a2_ent = new_entity(debug_between_type, new_id_from_str("a2_ent"), old_param_type);
694 a3_ent = new_entity(debug_between_type, new_id_from_str("a3_ent"), old_param_type);
695 old_fp_ent = new_entity(debug_between_type, new_id_from_str("old_fp"), old_fp_type);
696 ret_addr_ent = new_entity(debug_between_type, new_id_from_str("ret_addr"), ret_addr_type);
698 set_entity_offset(a0_ent, 0);
699 set_entity_offset(a1_ent, 4);
700 set_entity_offset(a2_ent, 8);
701 set_entity_offset(a3_ent, 12);
702 set_entity_offset(old_fp_ent, 16);
703 set_entity_offset(ret_addr_ent, 20);
705 set_type_size_bytes(debug_between_type, 24);
706 } else if(!env->debug && opt_between_type == NULL) {
707 ir_type *old_fp_type = new_type_primitive(new_id_from_str("fp"), mode_P);
708 ir_entity *old_fp_ent;
710 opt_between_type = new_type_class(new_id_from_str("mips_between_type"));
711 old_fp_ent = new_entity(opt_between_type, new_id_from_str("old_fp"), old_fp_type);
712 set_entity_offset(old_fp_ent, 0);
713 set_type_size_bytes(opt_between_type, 4);
716 return env->debug ? debug_between_type : opt_between_type;
719 static const be_abi_callbacks_t mips_abi_callbacks = {
722 mips_abi_get_between_type,
723 mips_abi_dont_save_regs,
729 * Get the ABI restrictions for procedure calls.
730 * @param self The this pointer.
731 * @param method_type The type of the method (procedure) in question.
732 * @param abi The abi object to be modified
734 static void mips_get_call_abi(const void *self, ir_type *method_type,
739 int n = get_method_n_params(method_type);
743 const arch_register_t *reg;
744 be_abi_call_flags_t call_flags;
747 memset(&call_flags, 0, sizeof(call_flags));
748 call_flags.bits.left_to_right = 0;
749 call_flags.bits.store_args_sequential = 0;
750 call_flags.bits.try_omit_fp = 1;
751 call_flags.bits.fp_free = 0;
752 call_flags.bits.call_has_imm = 1;
754 /* set stack parameter passing style */
755 be_abi_call_set_flags(abi, call_flags, &mips_abi_callbacks);
757 /* collect the mode for each type */
758 modes = alloca(n * sizeof(modes[0]));
759 for (i = 0; i < n; i++) {
760 tp = get_method_param_type(method_type, i);
761 modes[i] = get_type_mode(tp);
764 // assigns parameters to registers or stack
765 for (i = 0; i < n; i++) {
766 // first 4 params in $a0-$a3, the others on the stack
768 reg = &mips_gp_regs[REG_A0 + i];
769 be_abi_call_param_reg(abi, i, reg);
771 /* default: all parameters on stack */
772 be_abi_call_param_stack(abi, i, modes[i], 4, 0, 0);
776 /* set return register */
777 /* default: return value is in R0 (and maybe R1) */
778 result_count = get_method_n_ress(method_type);
779 assert(result_count <= 2 && "More than 2 result values not supported");
780 for(i = 0; i < result_count; ++i) {
781 const arch_register_t* reg;
782 tp = get_method_res_type(method_type, i);
783 mode = get_type_mode(tp);
784 ASSERT_NO_FLOAT(mode);
786 reg = &mips_gp_regs[REG_V0 + i];
787 be_abi_call_res_reg(abi, i, reg);
792 * Initializes the code generator interface.
794 static const arch_code_generator_if_t *mips_get_code_generator_if(void *self)
797 return &mips_code_gen_if;
801 * Returns the necessary byte alignment for storing a register of given class.
803 static int mips_get_reg_class_alignment(const void *self,
804 const arch_register_class_t *cls)
806 ir_mode *mode = arch_register_class_mode(cls);
808 return get_mode_size_bytes(mode);
811 static const be_execution_unit_t ***mips_get_allowed_execution_units(
812 const void *self, const ir_node *irn)
817 panic("Unimplemented mips_get_allowed_execution_units()");
820 static const be_machine_t *mips_get_machine(const void *self)
824 panic("Unimplemented mips_get_machine()");
828 * Return irp irgs in the desired order.
830 static ir_graph **mips_get_irg_list(const void *self, ir_graph ***irg_list)
838 * Returns the libFirm configuration parameter for this backend.
840 static const backend_params *mips_get_libfirm_params(void) {
841 static backend_params p = {
842 1, /* need dword lowering */
843 0, /* don't support inline assembler yet */
844 0, /* no immediate floating point mode. */
845 NULL, /* no additional opcodes */
846 NULL, /* will be set later */
847 NULL, /* but yet no creator function */
848 NULL, /* context for create_intrinsic_fkt */
849 NULL, /* no if conversion settings */
850 NULL /* no immediate fp mode */
856 static asm_constraint_flags_t mips_parse_asm_constraint(const void *self,
861 return ASM_CONSTRAINT_FLAG_INVALID;
864 static int mips_is_valid_clobber(const void *self, const char *clobber)
871 const arch_isa_if_t mips_isa_if = {
874 mips_get_n_reg_class,
876 mips_get_reg_class_for_mode,
878 mips_get_code_generator_if,
879 mips_get_list_sched_selector,
880 mips_get_ilp_sched_selector,
881 mips_get_reg_class_alignment,
882 mips_get_libfirm_params,
883 mips_get_allowed_execution_units,
886 NULL, /* mark remat */
887 mips_parse_asm_constraint,
888 mips_is_valid_clobber
891 void be_init_arch_mips(void)
893 be_register_isa_if("mips", &mips_isa_if);
896 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_arch_mips);