merge after_ra and finish phase, and move stack_bias fixing into backends
[libfirm] / ir / be / arm / bearch_arm.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   The main arm backend driver file.
23  * @author  Matthias Braun, Oliver Richter, Tobias Gneist
24  * @version $Id$
25  */
26 #include "config.h"
27
28 #include "lc_opts.h"
29 #include "lc_opts_enum.h"
30
31 #include "irgwalk.h"
32 #include "irprog.h"
33 #include "irprintf.h"
34 #include "ircons.h"
35 #include "irgmod.h"
36 #include "irgopt.h"
37 #include "iroptimize.h"
38 #include "irdump.h"
39 #include "lower_calls.h"
40 #include "error.h"
41
42 #include "bitset.h"
43 #include "debug.h"
44 #include "array_t.h"
45 #include "irtools.h"
46
47 #include "../bearch.h"
48 #include "../benode.h"
49 #include "../belower.h"
50 #include "../besched.h"
51 #include "be.h"
52 #include "../bemachine.h"
53 #include "../bemodule.h"
54 #include "../beirg.h"
55 #include "../bespillslots.h"
56 #include "../begnuas.h"
57 #include "../belistsched.h"
58 #include "../beflags.h"
59 #include "../bestack.h"
60
61 #include "bearch_arm_t.h"
62
63 #include "arm_new_nodes.h"
64 #include "gen_arm_regalloc_if.h"
65 #include "arm_transform.h"
66 #include "arm_optimize.h"
67 #include "arm_emitter.h"
68 #include "arm_map_regs.h"
69
70 static arch_irn_class_t arm_classify(const ir_node *irn)
71 {
72         (void) irn;
73         /* TODO: we should mark reload/spill instructions and classify them here */
74         return arch_irn_class_none;
75 }
76
77 static ir_entity *arm_get_frame_entity(const ir_node *irn)
78 {
79         const arm_attr_t *attr = get_arm_attr_const(irn);
80
81         if (is_arm_FrameAddr(irn)) {
82                 const arm_SymConst_attr_t *frame_attr = get_arm_SymConst_attr_const(irn);
83                 return frame_attr->entity;
84         }
85         if (attr->is_load_store) {
86                 const arm_load_store_attr_t *load_store_attr
87                         = get_arm_load_store_attr_const(irn);
88                 if (load_store_attr->is_frame_entity) {
89                         return load_store_attr->entity;
90                 }
91         }
92         return NULL;
93 }
94
95 /**
96  * This function is called by the generic backend to correct offsets for
97  * nodes accessing the stack.
98  */
99 static void arm_set_stack_bias(ir_node *irn, int bias)
100 {
101         if (is_arm_FrameAddr(irn)) {
102                 arm_SymConst_attr_t *attr = get_arm_SymConst_attr(irn);
103                 attr->fp_offset += bias;
104         } else {
105                 arm_load_store_attr_t *attr = get_arm_load_store_attr(irn);
106                 assert(attr->base.is_load_store);
107                 attr->offset += bias;
108         }
109 }
110
111 static int arm_get_sp_bias(const ir_node *irn)
112 {
113         /* We don't have any nodes changing the stack pointer.
114            We probably want to support post-/pre increment/decrement later */
115         (void) irn;
116         return 0;
117 }
118
119 /* fill register allocator interface */
120
121 static const arch_irn_ops_t arm_irn_ops = {
122         arm_classify,
123         arm_get_frame_entity,
124         arm_set_stack_bias,
125         arm_get_sp_bias,
126         NULL,    /* get_inverse             */
127         NULL,    /* get_op_estimated_cost   */
128         NULL,    /* possible_memory_operand */
129         NULL,    /* perform_memory_operand  */
130 };
131
132 /**
133  * Transforms the standard Firm graph into
134  * a ARM firm graph.
135  */
136 static void arm_prepare_graph(ir_graph *irg)
137 {
138         /* transform nodes into assembler instructions */
139         arm_transform_graph(irg);
140
141         /* do local optimizations (mainly CSE) */
142         local_optimize_graph(irg);
143
144         /* do code placement, to optimize the position of constants */
145         place_code(irg);
146 }
147
148 static void arm_collect_frame_entity_nodes(ir_node *node, void *data)
149 {
150         be_fec_env_t  *env = (be_fec_env_t*)data;
151         const ir_mode *mode;
152         int            align;
153         ir_entity     *entity;
154         const arm_load_store_attr_t *attr;
155
156         if (be_is_Reload(node) && be_get_frame_entity(node) == NULL) {
157                 mode  = get_irn_mode(node);
158                 align = get_mode_size_bytes(mode);
159                 be_node_needs_frame_entity(env, node, mode, align);
160                 return;
161         }
162
163         switch (get_arm_irn_opcode(node)) {
164         case iro_arm_Ldf:
165         case iro_arm_Ldr:
166                 break;
167         default:
168                 return;
169         }
170
171         attr   = get_arm_load_store_attr_const(node);
172         entity = attr->entity;
173         mode   = attr->load_store_mode;
174         align  = get_mode_size_bytes(mode);
175         if (entity != NULL)
176                 return;
177         if (!attr->is_frame_entity)
178                 return;
179         be_node_needs_frame_entity(env, node, mode, align);
180 }
181
182 static void arm_set_frame_entity(ir_node *node, ir_entity *entity)
183 {
184         if (is_be_node(node)) {
185                 be_node_set_frame_entity(node, entity);
186         } else {
187                 arm_load_store_attr_t *attr = get_arm_load_store_attr(node);
188                 attr->entity = entity;
189         }
190 }
191
192 static void transform_Reload(ir_node *node)
193 {
194         ir_node   *block  = get_nodes_block(node);
195         dbg_info  *dbgi   = get_irn_dbg_info(node);
196         ir_node   *ptr    = get_irn_n(node, n_be_Reload_frame);
197         ir_node   *mem    = get_irn_n(node, n_be_Reload_mem);
198         ir_mode   *mode   = get_irn_mode(node);
199         ir_entity *entity = be_get_frame_entity(node);
200         const arch_register_t *reg;
201         ir_node   *proj;
202         ir_node   *load;
203
204         ir_node  *sched_point = sched_prev(node);
205
206         load = new_bd_arm_Ldr(dbgi, block, ptr, mem, mode, entity, false, 0, true);
207         sched_add_after(sched_point, load);
208         sched_remove(node);
209
210         proj = new_rd_Proj(dbgi, load, mode, pn_arm_Ldr_res);
211
212         reg = arch_get_irn_register(node);
213         arch_set_irn_register(proj, reg);
214
215         exchange(node, proj);
216 }
217
218 static void transform_Spill(ir_node *node)
219 {
220         ir_node   *block  = get_nodes_block(node);
221         dbg_info  *dbgi   = get_irn_dbg_info(node);
222         ir_node   *ptr    = get_irn_n(node, n_be_Spill_frame);
223         ir_graph  *irg    = get_irn_irg(node);
224         ir_node   *mem    = get_irg_no_mem(irg);
225         ir_node   *val    = get_irn_n(node, n_be_Spill_val);
226         ir_mode   *mode   = get_irn_mode(val);
227         ir_entity *entity = be_get_frame_entity(node);
228         ir_node   *sched_point;
229         ir_node   *store;
230
231         sched_point = sched_prev(node);
232         store = new_bd_arm_Str(dbgi, block, ptr, val, mem, mode, entity, false, 0,
233                                true);
234
235         sched_remove(node);
236         sched_add_after(sched_point, store);
237
238         exchange(node, store);
239 }
240
241 static void arm_after_ra_walker(ir_node *block, void *data)
242 {
243         ir_node *node, *prev;
244         (void) data;
245
246         for (node = sched_last(block); !sched_is_begin(node); node = prev) {
247                 prev = sched_prev(node);
248
249                 if (be_is_Reload(node)) {
250                         transform_Reload(node);
251                 } else if (be_is_Spill(node)) {
252                         transform_Spill(node);
253                 }
254         }
255 }
256
257 /**
258  * Called immediately before emit phase.
259  */
260 static void arm_finish_irg(ir_graph *irg)
261 {
262         be_stack_layout_t *stack_layout = be_get_irg_stack_layout(irg);
263         bool               at_begin     = stack_layout->sp_relative ? true : false;
264         be_fec_env_t      *fec_env      = be_new_frame_entity_coalescer(irg);
265
266         irg_walk_graph(irg, NULL, arm_collect_frame_entity_nodes, fec_env);
267         be_assign_entities(fec_env, arm_set_frame_entity, at_begin);
268         be_free_frame_entity_coalescer(fec_env);
269
270         irg_block_walk_graph(irg, NULL, arm_after_ra_walker, NULL);
271
272         /* fix stack entity offsets */
273         be_abi_fix_stack_nodes(irg);
274         be_abi_fix_stack_bias(irg);
275
276         /* do peephole optimizations and fix stack offsets */
277         arm_peephole_optimization(irg);
278 }
279
280 static void arm_before_ra(ir_graph *irg)
281 {
282         be_sched_fix_flags(irg, &arm_reg_classes[CLASS_arm_flags], NULL, NULL);
283 }
284
285 /**
286  * Initializes the code generator.
287  */
288 static void arm_init_graph(ir_graph *irg)
289 {
290         (void) irg;
291 }
292
293
294 /**
295  * Maps all intrinsic calls that the backend support
296  * and map all instructions the backend did not support
297  * to runtime calls.
298  */
299 static void arm_handle_intrinsics(void)
300 {
301         ir_type *tp, *int_tp, *uint_tp;
302         i_record records[8];
303         int n_records = 0;
304
305         runtime_rt rt_iDiv, rt_uDiv, rt_iMod, rt_uMod;
306
307 #define ID(x) new_id_from_chars(x, sizeof(x)-1)
308
309         int_tp  = get_type_for_mode(mode_Is);
310         uint_tp = get_type_for_mode(mode_Iu);
311
312         /* ARM has neither a signed div instruction ... */
313         {
314                 i_instr_record *map_Div = &records[n_records++].i_instr;
315
316                 tp = new_type_method(2, 1);
317                 set_method_param_type(tp, 0, int_tp);
318                 set_method_param_type(tp, 1, int_tp);
319                 set_method_res_type(tp, 0, int_tp);
320
321                 rt_iDiv.ent             = new_entity(get_glob_type(), ID("__divsi3"), tp);
322                 set_entity_ld_ident(rt_iDiv.ent, ID("__divsi3"));
323                 rt_iDiv.mode            = mode_T;
324                 rt_iDiv.res_mode        = mode_Is;
325                 rt_iDiv.mem_proj_nr     = pn_Div_M;
326                 rt_iDiv.regular_proj_nr = pn_Div_X_regular;
327                 rt_iDiv.exc_proj_nr     = pn_Div_X_except;
328                 rt_iDiv.res_proj_nr     = pn_Div_res;
329
330                 add_entity_linkage(rt_iDiv.ent, IR_LINKAGE_CONSTANT);
331                 set_entity_visibility(rt_iDiv.ent, ir_visibility_external);
332
333                 map_Div->kind     = INTRINSIC_INSTR;
334                 map_Div->op       = op_Div;
335                 map_Div->i_mapper = (i_mapper_func)i_mapper_RuntimeCall;
336                 map_Div->ctx      = &rt_iDiv;
337         }
338         /* ... nor an unsigned div instruction ... */
339         {
340                 i_instr_record *map_Div = &records[n_records++].i_instr;
341
342                 tp = new_type_method(2, 1);
343                 set_method_param_type(tp, 0, uint_tp);
344                 set_method_param_type(tp, 1, uint_tp);
345                 set_method_res_type(tp, 0, uint_tp);
346
347                 rt_uDiv.ent             = new_entity(get_glob_type(), ID("__udivsi3"), tp);
348                 set_entity_ld_ident(rt_uDiv.ent, ID("__udivsi3"));
349                 rt_uDiv.mode            = mode_T;
350                 rt_uDiv.res_mode        = mode_Iu;
351                 rt_uDiv.mem_proj_nr     = pn_Div_M;
352                 rt_uDiv.regular_proj_nr = pn_Div_X_regular;
353                 rt_uDiv.exc_proj_nr     = pn_Div_X_except;
354                 rt_uDiv.res_proj_nr     = pn_Div_res;
355
356                 set_entity_visibility(rt_uDiv.ent, ir_visibility_external);
357
358                 map_Div->kind     = INTRINSIC_INSTR;
359                 map_Div->op       = op_Div;
360                 map_Div->i_mapper = (i_mapper_func)i_mapper_RuntimeCall;
361                 map_Div->ctx      = &rt_uDiv;
362         }
363         /* ... nor a signed mod instruction ... */
364         {
365                 i_instr_record *map_Mod = &records[n_records++].i_instr;
366
367                 tp = new_type_method(2, 1);
368                 set_method_param_type(tp, 0, int_tp);
369                 set_method_param_type(tp, 1, int_tp);
370                 set_method_res_type(tp, 0, int_tp);
371
372                 rt_iMod.ent             = new_entity(get_glob_type(), ID("__modsi3"), tp);
373                 set_entity_ld_ident(rt_iMod.ent, ID("__modsi3"));
374                 rt_iMod.mode            = mode_T;
375                 rt_iMod.res_mode        = mode_Is;
376                 rt_iMod.mem_proj_nr     = pn_Mod_M;
377                 rt_iMod.regular_proj_nr = pn_Mod_X_regular;
378                 rt_iMod.exc_proj_nr     = pn_Mod_X_except;
379                 rt_iMod.res_proj_nr     = pn_Mod_res;
380
381                 set_entity_visibility(rt_iMod.ent, ir_visibility_external);
382
383                 map_Mod->kind     = INTRINSIC_INSTR;
384                 map_Mod->op       = op_Mod;
385                 map_Mod->i_mapper = (i_mapper_func)i_mapper_RuntimeCall;
386                 map_Mod->ctx      = &rt_iMod;
387         }
388         /* ... nor an unsigned mod. */
389         {
390                 i_instr_record *map_Mod = &records[n_records++].i_instr;
391
392                 tp = new_type_method(2, 1);
393                 set_method_param_type(tp, 0, uint_tp);
394                 set_method_param_type(tp, 1, uint_tp);
395                 set_method_res_type(tp, 0, uint_tp);
396
397                 rt_uMod.ent             = new_entity(get_glob_type(), ID("__umodsi3"), tp);
398                 set_entity_ld_ident(rt_uMod.ent, ID("__umodsi3"));
399                 rt_uMod.mode            = mode_T;
400                 rt_uMod.res_mode        = mode_Iu;
401                 rt_uMod.mem_proj_nr     = pn_Mod_M;
402                 rt_uMod.regular_proj_nr = pn_Mod_X_regular;
403                 rt_uMod.exc_proj_nr     = pn_Mod_X_except;
404                 rt_uMod.res_proj_nr     = pn_Mod_res;
405
406                 set_entity_visibility(rt_uMod.ent, ir_visibility_external);
407
408                 map_Mod->kind     = INTRINSIC_INSTR;
409                 map_Mod->op       = op_Mod;
410                 map_Mod->i_mapper = (i_mapper_func)i_mapper_RuntimeCall;
411                 map_Mod->ctx      = &rt_uMod;
412         }
413
414         if (n_records > 0)
415                 lower_intrinsics(records, n_records, /*part_block_used=*/0);
416 }
417
418 extern const arch_isa_if_t arm_isa_if;
419 static arm_isa_t arm_isa_template = {
420         {
421                 &arm_isa_if,           /* isa interface */
422                 N_ARM_REGISTERS,
423                 arm_registers,
424                 N_ARM_CLASSES,
425                 arm_reg_classes,
426                 &arm_registers[REG_SP],  /* stack pointer */
427                 &arm_registers[REG_R11], /* base pointer */
428                 &arm_reg_classes[CLASS_arm_gp],  /* static link pointer class */
429                 2,                     /* power of two stack alignment for calls, 2^2 == 4 */
430                 NULL,                  /* main environment */
431                 7,                     /* spill costs */
432                 5,                     /* reload costs */
433                 true,                  /* we do have custom abi handling */
434         },
435         ARM_FPU_ARCH_FPE,      /* FPU architecture */
436 };
437
438 /**
439  * Initializes the backend ISA and opens the output file.
440  */
441 static arch_env_t *arm_init(FILE *file_handle)
442 {
443         arm_isa_t *isa = XMALLOC(arm_isa_t);
444         *isa = arm_isa_template;
445
446         arm_register_init();
447
448         be_emit_init(file_handle);
449
450         arm_create_opcodes(&arm_irn_ops);
451         arm_handle_intrinsics();
452
453         be_gas_emit_types = false;
454
455         return &isa->base;
456 }
457
458
459
460 /**
461  * Closes the output file and frees the ISA structure.
462  */
463 static void arm_done(void *self)
464 {
465         arm_isa_t *isa = (arm_isa_t*)self;
466
467         be_gas_emit_decls(isa->base.main_env);
468
469         be_emit_exit();
470         free(self);
471 }
472
473 /**
474  * Get the register class which shall be used to store a value of a given mode.
475  * @param self The this pointer.
476  * @param mode The mode in question.
477  * @return A register class which can hold values of the given mode.
478  */
479 static const arch_register_class_t *arm_get_reg_class_for_mode(const ir_mode *mode)
480 {
481         if (mode_is_float(mode))
482                 return &arm_reg_classes[CLASS_arm_fpa];
483         else
484                 return &arm_reg_classes[CLASS_arm_gp];
485 }
486
487 /**
488  * Returns the necessary byte alignment for storing a register of given class.
489  */
490 static int arm_get_reg_class_alignment(const arch_register_class_t *cls)
491 {
492         (void) cls;
493         /* ARM is a 32 bit CPU, no need for other alignment */
494         return 4;
495 }
496
497 /**
498  * Return irp irgs in the desired order.
499  */
500 static ir_graph **arm_get_irg_list(const void *self, ir_graph ***irg_list)
501 {
502         (void) self;
503         (void) irg_list;
504         return NULL;
505 }
506
507 /**
508  * Allows or disallows the creation of Psi nodes for the given Phi nodes.
509  * @return 1 if allowed, 0 otherwise
510  */
511 static int arm_is_mux_allowed(ir_node *sel, ir_node *mux_false,
512                               ir_node *mux_true)
513 {
514         (void) sel;
515         (void) mux_false;
516         (void) mux_true;
517         return false;
518 }
519
520 static asm_constraint_flags_t arm_parse_asm_constraint(const char **c)
521 {
522         /* asm not supported */
523         (void) c;
524         return ASM_CONSTRAINT_FLAG_INVALID;
525 }
526
527 static int arm_is_valid_clobber(const char *clobber)
528 {
529         (void) clobber;
530         return 0;
531 }
532
533 static void arm_lower_for_target(void)
534 {
535         size_t i, n_irgs = get_irp_n_irgs();
536
537         /* lower compound param handling */
538         lower_calls_with_compounds(LF_RETURN_HIDDEN);
539
540         for (i = 0; i < n_irgs; ++i) {
541                 ir_graph *irg = get_irp_irg(i);
542                 lower_switch(irg, 4, 256, true);
543         }
544 }
545
546 /**
547  * Returns the libFirm configuration parameter for this backend.
548  */
549 static const backend_params *arm_get_libfirm_params(void)
550 {
551         static ir_settings_arch_dep_t ad = {
552                 1,    /* allow subs */
553                 1,    /* Muls are fast enough on ARM but ... */
554                 31,   /* ... one shift would be possible better */
555                 NULL, /* no evaluator function */
556                 0,    /* SMUL is needed, only in Arch M */
557                 0,    /* UMUL is needed, only in Arch M */
558                 32,   /* SMUL & UMUL available for 32 bit */
559         };
560         static backend_params p = {
561                 0,     /* don't support inline assembler yet */
562                 1,     /* support Rotl nodes */
563                 1,     /* big endian */
564                 1,     /* modulo shift efficient */
565                 0,     /* non-modulo shift not efficient */
566                 &ad,   /* will be set later */
567                 arm_is_mux_allowed, /* allow_ifconv function */
568                 32,    /* machine size */
569                 NULL,  /* float arithmetic mode (TODO) */
570                 NULL,  /* long long type */
571                 NULL,  /* unsigned long long type */
572                 NULL,  /* long double type */
573                 0,     /* no trampoline support: size 0 */
574                 0,     /* no trampoline support: align 0 */
575                 NULL,  /* no trampoline support: no trampoline builder */
576                 4      /* alignment of stack parameter */
577         };
578
579         return &p;
580 }
581
582 /* fpu set architectures. */
583 static const lc_opt_enum_int_items_t arm_fpu_items[] = {
584         { "softfloat", ARM_FPU_ARCH_SOFTFLOAT },
585         { "fpe",       ARM_FPU_ARCH_FPE },
586         { "fpa",       ARM_FPU_ARCH_FPA },
587         { "vfp1xd",    ARM_FPU_ARCH_VFP_V1xD },
588         { "vfp1",      ARM_FPU_ARCH_VFP_V1 },
589         { "vfp2",      ARM_FPU_ARCH_VFP_V2 },
590         { NULL,        0 }
591 };
592
593 static lc_opt_enum_int_var_t arch_fpu_var = {
594         &arm_isa_template.fpu_arch, arm_fpu_items
595 };
596
597 static const lc_opt_table_entry_t arm_options[] = {
598         LC_OPT_ENT_ENUM_INT("fpunit",    "select the floating point unit", &arch_fpu_var),
599         LC_OPT_LAST
600 };
601
602 const arch_isa_if_t arm_isa_if = {
603         arm_init,
604         arm_lower_for_target,
605         arm_done,
606         NULL,  /* handle_intrinsics */
607         arm_get_reg_class_for_mode,
608         NULL,
609         arm_get_reg_class_alignment,
610         arm_get_libfirm_params,
611         arm_get_irg_list,
612         NULL,               /* mark remat */
613         arm_parse_asm_constraint,
614         arm_is_valid_clobber,
615
616         arm_init_graph,
617         NULL,  /* get_pic_base */
618         NULL,  /* before_abi */
619         arm_prepare_graph,
620         arm_before_ra,
621         arm_finish_irg,
622         arm_gen_routine,
623         NULL, /* register_saved_by */
624 };
625
626 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_arch_arm)
627 void be_init_arch_arm(void)
628 {
629         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
630         lc_opt_entry_t *arm_grp = lc_opt_get_grp(be_grp, "arm");
631
632         lc_opt_add_table(arm_grp, arm_options);
633
634         be_register_isa_if("arm", &arm_isa_if);
635
636         arm_init_transform();
637         arm_init_emitter();
638 }