2 * Copyright (C) 1995-2011 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 Backend ABI implementation.
23 * @author Sebastian Hack, Michael Beck
31 #include "irgraph_t.h"
34 #include "iredges_t.h"
37 #include "irprintf_t.h"
44 #include "raw_bitset.h"
55 #include "bessaconstr.h"
57 #include "betranshlp.h"
59 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
61 typedef struct be_abi_call_arg_t {
62 unsigned is_res : 1; /**< 1: the call argument is a return value. 0: it's a call parameter. */
63 unsigned in_reg : 1; /**< 1: this argument is transmitted 1: in registers, 0: on stack. */
64 unsigned callee : 1; /**< 1: someone called us. 0: We call another function */
67 const arch_register_t *reg;
70 unsigned alignment; /**< stack alignment */
71 unsigned space_before; /**< allocate space before */
72 unsigned space_after; /**< allocate space after */
75 struct be_abi_call_t {
76 be_abi_call_flags_t flags; /**< Flags describing the ABI behavior on calls */
77 int pop; /**< number of bytes the stack frame is shrinked by the callee on return. */
78 const be_abi_callbacks_t *cb;
83 * The ABI information for the current graph.
86 be_abi_call_t *call; /**< The ABI call information. */
88 ir_node *init_sp; /**< The node representing the stack pointer
89 at the start of the function. */
91 pmap *regs; /**< A map of all callee-save and ignore regs to
92 their Projs to the RegParams node. */
93 pmap *keep_map; /**< mapping blocks to keep nodes. */
95 ir_node **calls; /**< flexible array containing all be_Call nodes */
98 static ir_heights_t *ir_heights;
100 static ir_node *be_abi_reg_map_get(pmap *map, const arch_register_t *reg)
102 return pmap_get(ir_node, map, reg);
105 static void be_abi_reg_map_set(pmap *map, const arch_register_t* reg,
108 pmap_insert(map, reg, node);
112 * Check if the given register is callee save, ie. will be saved by the callee.
114 static bool arch_register_is_callee_save(
115 const arch_env_t *arch_env,
116 const arch_register_t *reg)
118 if (arch_env->impl->register_saved_by)
119 return arch_env->impl->register_saved_by(reg, /*callee=*/1);
124 * Check if the given register is caller save, ie. must be saved by the caller.
126 static bool arch_register_is_caller_save(
127 const arch_env_t *arch_env,
128 const arch_register_t *reg)
130 if (arch_env->impl->register_saved_by)
131 return arch_env->impl->register_saved_by(reg, /*callee=*/0);
138 _ ____ ___ ____ _ _ _ _
139 / \ | __ )_ _| / ___|__ _| | | |__ __ _ ___| | _____
140 / _ \ | _ \| | | | / _` | | | '_ \ / _` |/ __| |/ / __|
141 / ___ \| |_) | | | |__| (_| | | | |_) | (_| | (__| <\__ \
142 /_/ \_\____/___| \____\__,_|_|_|_.__/ \__,_|\___|_|\_\___/
144 These callbacks are used by the backend to set the parameters
145 for a specific call type.
149 * Set compare function: compares two ABI call object arguments.
151 static int cmp_call_arg(const void *a, const void *b, size_t n)
153 const be_abi_call_arg_t *p = (const be_abi_call_arg_t*)a;
154 const be_abi_call_arg_t *q = (const be_abi_call_arg_t*)b;
156 return !(p->is_res == q->is_res && p->pos == q->pos && p->callee == q->callee);
160 * Get an ABI call object argument.
162 * @param call the abi call
163 * @param is_res true for call results, false for call arguments
164 * @param pos position of the argument
165 * @param callee context type - if we are callee or caller
167 static be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos, int callee)
169 be_abi_call_arg_t arg;
172 memset(&arg, 0, sizeof(arg));
177 hash = is_res * 128 + pos;
179 return set_find(be_abi_call_arg_t, call->params, &arg, sizeof(arg), hash);
183 * Set an ABI call object argument.
185 static void remember_call_arg(be_abi_call_arg_t *arg, be_abi_call_t *call, be_abi_context_t context)
187 unsigned hash = arg->is_res * 128 + arg->pos;
188 if (context & ABI_CONTEXT_CALLEE) {
190 (void)set_insert(be_abi_call_arg_t, call->params, arg, sizeof(*arg), hash);
192 if (context & ABI_CONTEXT_CALLER) {
194 (void)set_insert(be_abi_call_arg_t, call->params, arg, sizeof(*arg), hash);
198 /* Set the flags for a call. */
199 void be_abi_call_set_flags(be_abi_call_t *call, be_abi_call_flags_t flags, const be_abi_callbacks_t *cb)
205 /* Sets the number of bytes the stackframe is shrinked by the callee on return */
206 void be_abi_call_set_pop(be_abi_call_t *call, int pop)
212 void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos,
213 ir_mode *load_mode, unsigned alignment,
214 unsigned space_before, unsigned space_after,
215 be_abi_context_t context)
217 be_abi_call_arg_t arg;
218 memset(&arg, 0, sizeof(arg));
219 assert(alignment > 0 && "Alignment must be greater than 0");
220 arg.load_mode = load_mode;
221 arg.alignment = alignment;
222 arg.space_before = space_before;
223 arg.space_after = space_after;
227 remember_call_arg(&arg, call, context);
230 void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg, be_abi_context_t context)
232 be_abi_call_arg_t arg;
233 memset(&arg, 0, sizeof(arg));
240 remember_call_arg(&arg, call, context);
243 void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg, be_abi_context_t context)
245 be_abi_call_arg_t arg;
246 memset(&arg, 0, sizeof(arg));
253 remember_call_arg(&arg, call, context);
256 /* Get the flags of a ABI call object. */
257 be_abi_call_flags_t be_abi_call_get_flags(const be_abi_call_t *call)
263 * Constructor for a new ABI call object.
265 * @return the new ABI call object
267 static be_abi_call_t *be_abi_call_new(void)
269 be_abi_call_t *call = XMALLOCZ(be_abi_call_t);
271 call->params = new_set(cmp_call_arg, 16);
273 call->flags.try_omit_fp = be_options.omit_fp;
279 * Destructor for an ABI call object.
281 static void be_abi_call_free(be_abi_call_t *call)
283 del_set(call->params);
288 * Initializes the frame layout from parts
290 * @param frame the stack layout that will be initialized
291 * @param args the stack argument layout type
292 * @param between the between layout type
293 * @param locals the method frame type
295 * @return the initialized stack layout
297 static be_stack_layout_t *stack_frame_init(be_stack_layout_t *frame, ir_type *args,
298 ir_type *between, ir_type *locals)
300 frame->arg_type = args;
301 frame->between_type = between;
302 frame->frame_type = locals;
303 frame->initial_offset = 0;
304 frame->initial_bias = 0;
305 frame->order[1] = between;
307 /* typical decreasing stack: locals have the
308 * lowest addresses, arguments the highest */
309 frame->order[0] = locals;
310 frame->order[2] = args;
321 Adjustment of the calls inside a graph.
326 * Transform a call node into a be_Call node.
328 * @param env The ABI environment for the current irg.
329 * @param irn The call node.
330 * @param curr_sp The stack pointer node to use.
331 * @return The stack pointer after the call.
333 static ir_node *adjust_call(be_abi_irg_t *env, ir_node *irn, ir_node *curr_sp)
335 ir_graph *irg = get_irn_irg(irn);
336 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
337 ir_type *call_tp = get_Call_type(irn);
338 ir_node *call_ptr = get_Call_ptr(irn);
339 size_t n_params = get_method_n_params(call_tp);
340 ir_node *curr_mem = get_Call_mem(irn);
341 ir_node *bl = get_nodes_block(irn);
343 const arch_register_t *sp = arch_env->sp;
344 be_abi_call_t *call = be_abi_call_new();
345 ir_mode *mach_mode = sp->reg_class->mode;
346 int n_res = get_method_n_ress(call_tp);
348 ir_node *res_proj = NULL;
349 int n_reg_params = 0;
350 int n_stack_params = 0;
353 const arch_register_t **states = NEW_ARR_F(const arch_register_t*, 0);
354 const arch_register_t **destroyed_regs = NEW_ARR_F(const arch_register_t*, 0);
358 int n_reg_results = 0;
360 int *stack_param_idx;
362 int throws_exception;
367 /* Let the isa fill out the abi description for that call node. */
368 arch_env_get_call_abi(arch_env, call_tp, call);
370 /* Insert code to put the stack arguments on the stack. */
371 assert((size_t)get_Call_n_params(irn) == n_params);
372 stack_param_idx = ALLOCAN(int, n_params);
373 for (p = 0; p < n_params; ++p) {
374 be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
377 int arg_size = get_type_size_bytes(get_method_param_type(call_tp, p));
379 stack_size += round_up2(arg->space_before, arg->alignment);
380 stack_size += round_up2(arg_size, arg->alignment);
381 stack_size += round_up2(arg->space_after, arg->alignment);
383 stack_param_idx[n_stack_params++] = p;
387 /* Collect all arguments which are passed in registers. */
388 reg_param_idxs = ALLOCAN(int, n_params);
389 for (p = 0; p < n_params; ++p) {
390 be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
391 if (arg && arg->in_reg) {
392 reg_param_idxs[n_reg_params++] = p;
397 * If the stack is decreasing and we do not want to store sequentially,
398 * or someone else allocated the call frame
399 * we allocate as much space on the stack all parameters need, by
400 * moving the stack pointer along the stack's direction.
402 * Note: we also have to do this for stack_size == 0, because we may have
403 * to adjust stack alignment for the call.
405 curr_sp = be_new_IncSP(sp, bl, curr_sp, stack_size, 1);
407 dbgi = get_irn_dbg_info(irn);
408 /* If there are some parameters which shall be passed on the stack. */
409 if (n_stack_params > 0) {
411 ir_node **in = ALLOCAN(ir_node*, n_stack_params+1);
414 curr_mem = get_Call_mem(irn);
415 in[n_in++] = curr_mem;
417 for (i = 0; i < n_stack_params; ++i) {
418 int p = stack_param_idx[i];
419 be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
420 ir_node *param = get_Call_param(irn, p);
421 ir_node *addr = curr_sp;
423 ir_type *param_type = get_method_param_type(call_tp, p);
424 int param_size = get_type_size_bytes(param_type) + arg->space_after;
427 * If we wanted to build the arguments sequentially,
428 * the stack pointer for the next must be incremented,
429 * and the memory value propagated.
431 curr_ofs += arg->space_before;
432 curr_ofs = round_up2(curr_ofs, arg->alignment);
434 /* Make the expression to compute the argument's offset. */
436 ir_mode *constmode = mach_mode;
437 if (mode_is_reference(mach_mode)) {
440 addr = new_r_Const_long(irg, constmode, curr_ofs);
441 addr = new_r_Add(bl, curr_sp, addr, mach_mode);
444 /* Insert a store for primitive arguments. */
445 if (is_atomic_type(param_type)) {
446 ir_node *nomem = get_irg_no_mem(irg);
447 ir_node *mem_input = nomem;
448 ir_node *store = new_rd_Store(dbgi, bl, mem_input, addr, param, cons_none);
449 mem = new_r_Proj(store, mode_M, pn_Store_M);
451 /* Make a mem copy for compound arguments. */
454 assert(mode_is_reference(get_irn_mode(param)));
455 copy = new_rd_CopyB(dbgi, bl, curr_mem, addr, param, param_type);
456 mem = new_r_Proj(copy, mode_M, pn_CopyB_M);
459 curr_ofs += param_size;
464 /* We need the sync only, if we didn't build the stores sequentially. */
465 if (n_stack_params >= 1) {
466 curr_mem = new_r_Sync(bl, n_in, in);
468 curr_mem = get_Call_mem(irn);
472 /* Put caller save into the destroyed set and state registers in the states
474 for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
476 const arch_register_class_t *cls = &arch_env->register_classes[i];
477 for (j = 0; j < cls->n_regs; ++j) {
478 const arch_register_t *reg = arch_register_for_index(cls, j);
480 /* even if destroyed all is specified, neither SP nor FP are
481 * destroyed (else bad things will happen) */
482 if (reg == arch_env->sp || reg == arch_env->bp)
485 if (reg->type & arch_register_type_state) {
486 ARR_APP1(const arch_register_t*, destroyed_regs, reg);
487 ARR_APP1(const arch_register_t*, states, reg);
488 /* we're already in the destroyed set so no need for further
492 if (arch_register_is_caller_save(arch_env, reg)) {
493 if (!(reg->type & arch_register_type_ignore)) {
494 ARR_APP1(const arch_register_t*, destroyed_regs, reg);
500 /* search the largest result proj number */
501 res_projs = ALLOCANZ(ir_node*, n_res);
503 foreach_out_edge(irn, edge) {
504 ir_node *irn = get_edge_src_irn(edge);
506 if (!is_Proj(irn) || get_Proj_proj(irn) != pn_Call_T_result)
509 foreach_out_edge(irn, res_edge) {
511 ir_node *res = get_edge_src_irn(res_edge);
513 assert(is_Proj(res));
515 proj = get_Proj_proj(res);
516 assert(proj < n_res);
517 assert(res_projs[proj] == NULL);
518 res_projs[proj] = res;
524 /** TODO: this is not correct for cases where return values are passed
525 * on the stack, but no known ABI does this currently...
527 n_reg_results = n_res;
530 in = ALLOCAN(ir_node*, n_reg_params + ARR_LEN(states));
532 /* make the back end call node and set its register requirements. */
533 for (i = 0; i < n_reg_params; ++i) {
534 in[n_ins++] = get_Call_param(irn, reg_param_idxs[i]);
537 /* add state registers ins */
538 for (s = 0; s < ARR_LEN(states); ++s) {
539 const arch_register_t *reg = states[s];
540 const arch_register_class_t *cls = reg->reg_class;
541 ir_node *regnode = new_r_Unknown(irg, cls->mode);
542 in[n_ins++] = regnode;
544 assert(n_ins == (int) (n_reg_params + ARR_LEN(states)));
546 /* ins collected, build the call */
547 throws_exception = ir_throws_exception(irn);
548 if (env->call->flags.call_has_imm && is_SymConst(call_ptr)) {
550 low_call = be_new_Call(dbgi, irg, bl, curr_mem, sp->single_req, curr_sp,
551 sp->single_req, curr_sp,
552 n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
553 n_ins, in, get_Call_type(irn));
554 be_Call_set_entity(low_call, get_SymConst_entity(call_ptr));
557 low_call = be_new_Call(dbgi, irg, bl, curr_mem, sp->single_req, curr_sp,
558 sp->reg_class->class_req, call_ptr,
559 n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
560 n_ins, in, get_Call_type(irn));
562 ir_set_throws_exception(low_call, throws_exception);
563 be_Call_set_pop(low_call, call->pop);
565 /* put the call into the list of all calls for later processing */
566 ARR_APP1(ir_node *, env->calls, low_call);
568 /* create new stack pointer */
569 curr_sp = new_r_Proj(low_call, get_irn_mode(curr_sp), pn_be_Call_sp);
570 be_set_constr_single_reg_out(low_call, pn_be_Call_sp, sp,
571 arch_register_req_type_ignore | arch_register_req_type_produces_sp);
572 arch_set_irn_register(curr_sp, sp);
574 /* now handle results */
575 for (i = 0; i < n_res; ++i) {
576 ir_node *proj = res_projs[i];
577 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 0);
579 /* returns values on stack not supported yet */
583 shift the proj number to the right, since we will drop the
584 unspeakable Proj_T from the Call. Therefore, all real argument
585 Proj numbers must be increased by pn_be_Call_first_res
587 long pn = i + pn_be_Call_first_res;
590 ir_type *res_type = get_method_res_type(call_tp, i);
591 ir_mode *mode = get_type_mode(res_type);
592 proj = new_r_Proj(low_call, mode, pn);
595 set_Proj_pred(proj, low_call);
596 set_Proj_proj(proj, pn);
600 /* remove register from destroyed regs */
602 size_t n = ARR_LEN(destroyed_regs);
603 for (j = 0; j < n; ++j) {
604 if (destroyed_regs[j] == arg->reg) {
605 destroyed_regs[j] = destroyed_regs[n-1];
606 ARR_SHRINKLEN(destroyed_regs,n-1);
613 DBG((dbg, LEVEL_3, "\tcreated backend call %+F\n", low_call));
615 /* Set the register classes and constraints of the Call parameters. */
616 for (i = 0; i < n_reg_params; ++i) {
617 int index = reg_param_idxs[i];
618 be_abi_call_arg_t *arg = get_call_arg(call, 0, index, 0);
619 assert(arg->reg != NULL);
621 be_set_constr_single_reg_in(low_call, n_be_Call_first_arg + i,
622 arg->reg, arch_register_req_type_none);
625 /* Set the register constraints of the results. */
626 for (i = 0; i < n_res; ++i) {
627 ir_node *proj = res_projs[i];
628 const be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 0);
629 int pn = get_Proj_proj(proj);
632 be_set_constr_single_reg_out(low_call, pn, arg->reg,
633 arch_register_req_type_none);
634 arch_set_irn_register(proj, arg->reg);
636 exchange(irn, low_call);
638 /* kill the ProjT node */
639 if (res_proj != NULL) {
643 /* Make additional projs for the caller save registers
644 and the Keep node which keeps them alive. */
650 int curr_res_proj = pn_be_Call_first_res + n_reg_results;
653 n_ins = ARR_LEN(destroyed_regs) + n_reg_results + 1;
654 in = ALLOCAN(ir_node *, n_ins);
656 /* also keep the stack pointer */
657 set_irn_link(curr_sp, (void*) sp);
660 for (d = 0; d < ARR_LEN(destroyed_regs); ++d) {
661 const arch_register_t *reg = destroyed_regs[d];
662 ir_node *proj = new_r_Proj(low_call, reg->reg_class->mode, curr_res_proj);
664 /* memorize the register in the link field. we need afterwards to set the register class of the keep correctly. */
665 be_set_constr_single_reg_out(low_call, curr_res_proj, reg,
666 arch_register_req_type_none);
667 arch_set_irn_register(proj, reg);
669 set_irn_link(proj, (void*) reg);
674 for (i = 0; i < n_reg_results; ++i) {
675 ir_node *proj = res_projs[i];
676 const arch_register_t *reg = arch_get_irn_register(proj);
677 set_irn_link(proj, (void*) reg);
682 /* create the Keep for the caller save registers */
683 keep = be_new_Keep(bl, n, in);
684 for (i = 0; i < n; ++i) {
685 const arch_register_t *reg = (const arch_register_t*)get_irn_link(in[i]);
686 be_node_set_reg_class_in(keep, i, reg->reg_class);
690 /* Clean up the stack. */
691 assert(stack_size >= call->pop);
692 stack_size -= call->pop;
694 if (stack_size > 0) {
695 ir_node *mem_proj = NULL;
697 foreach_out_edge(low_call, edge) {
698 ir_node *irn = get_edge_src_irn(edge);
699 if (is_Proj(irn) && get_Proj_proj(irn) == pn_Call_M) {
706 mem_proj = new_r_Proj(low_call, mode_M, pn_be_Call_M);
707 keep_alive(mem_proj);
710 /* Clean up the stack frame or revert alignment fixes if we allocated it */
711 curr_sp = be_new_IncSP(sp, bl, curr_sp, -stack_size, 0);
713 be_abi_call_free(call);
716 DEL_ARR_F(destroyed_regs);
722 * Adjust the size of a node representing a stack alloc or free for the minimum stack alignment.
724 * @param alignment the minimum stack alignment
725 * @param size the node containing the non-aligned size
726 * @param block the block where new nodes are allocated on
727 * @param dbg debug info for new nodes
729 * @return a node representing the aligned size
731 static ir_node *adjust_alloc_size(unsigned stack_alignment, ir_node *size,
732 ir_node *block, dbg_info *dbg)
734 if (stack_alignment > 1) {
740 assert(is_po2(stack_alignment));
742 mode = get_irn_mode(size);
743 tv = new_tarval_from_long(stack_alignment-1, mode);
744 irg = get_Block_irg(block);
745 mask = new_r_Const(irg, tv);
746 size = new_rd_Add(dbg, block, size, mask, mode);
748 tv = new_tarval_from_long(-(long)stack_alignment, mode);
749 mask = new_r_Const(irg, tv);
750 size = new_rd_And(dbg, block, size, mask, mode);
756 * The alloca is transformed into a back end alloca node and connected to the stack nodes.
758 static ir_node *adjust_alloc(be_abi_irg_t *env, ir_node *alloc, ir_node *curr_sp)
760 ir_node *block = get_nodes_block(alloc);
761 ir_graph *irg = get_Block_irg(block);
762 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
763 ir_node *alloc_mem = NULL;
764 ir_node *alloc_res = NULL;
765 ir_type *type = get_Alloc_type(alloc);
772 unsigned stack_alignment;
774 /* all non-stack Alloc nodes should already be lowered before the backend */
775 assert(get_Alloc_where(alloc) == stack_alloc);
777 foreach_out_edge(alloc, edge) {
778 ir_node *irn = get_edge_src_irn(edge);
780 assert(is_Proj(irn));
781 switch (get_Proj_proj(irn)) {
793 /* Beware: currently Alloc nodes without a result might happen,
794 only escape analysis kills them and this phase runs only for object
795 oriented source. We kill the Alloc here. */
796 if (alloc_res == NULL && alloc_mem) {
797 exchange(alloc_mem, get_Alloc_mem(alloc));
801 dbg = get_irn_dbg_info(alloc);
802 count = get_Alloc_count(alloc);
804 /* we might need to multiply the count with the element size */
805 if (!is_unknown_type(type) && get_type_size_bytes(type) != 1) {
806 ir_mode *mode = get_irn_mode(count);
807 ir_tarval *tv = new_tarval_from_long(get_type_size_bytes(type),
809 ir_node *cnst = new_rd_Const(dbg, irg, tv);
810 size = new_rd_Mul(dbg, block, count, cnst, mode);
815 /* The stack pointer will be modified in an unknown manner.
816 We cannot omit it. */
817 env->call->flags.try_omit_fp = 0;
819 stack_alignment = 1 << arch_env->stack_alignment;
820 size = adjust_alloc_size(stack_alignment, size, block, dbg);
821 new_alloc = be_new_AddSP(arch_env->sp, block, curr_sp, size);
822 set_irn_dbg_info(new_alloc, dbg);
824 if (alloc_mem != NULL) {
828 addsp_mem = new_r_Proj(new_alloc, mode_M, pn_be_AddSP_M);
830 /* We need to sync the output mem of the AddSP with the input mem
831 edge into the alloc node. */
832 ins[0] = get_Alloc_mem(alloc);
834 sync = new_r_Sync(block, 2, ins);
836 exchange(alloc_mem, sync);
839 exchange(alloc, new_alloc);
841 /* fix projnum of alloca res */
842 set_Proj_proj(alloc_res, pn_be_AddSP_res);
844 curr_sp = new_r_Proj(new_alloc, get_irn_mode(curr_sp), pn_be_AddSP_sp);
851 * The Free is transformed into a back end free node and connected to the stack nodes.
853 static ir_node *adjust_free(be_abi_irg_t *env, ir_node *free, ir_node *curr_sp)
855 ir_node *block = get_nodes_block(free);
856 ir_graph *irg = get_irn_irg(free);
857 ir_type *type = get_Free_type(free);
858 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
859 ir_mode *sp_mode = arch_env->sp->reg_class->mode;
860 dbg_info *dbg = get_irn_dbg_info(free);
861 ir_node *subsp, *mem, *res, *size, *sync;
863 unsigned stack_alignment;
865 /* all non-stack-alloc Free nodes should already be lowered before the
867 assert(get_Free_where(free) == stack_alloc);
869 /* we might need to multiply the size with the element size */
870 if (!is_unknown_type(type) && get_type_size_bytes(type) != 1) {
871 ir_tarval *tv = new_tarval_from_long(get_type_size_bytes(type), mode_Iu);
872 ir_node *cnst = new_rd_Const(dbg, irg, tv);
873 ir_node *mul = new_rd_Mul(dbg, block, get_Free_count(free),
877 size = get_Free_count(free);
880 stack_alignment = 1 << arch_env->stack_alignment;
881 size = adjust_alloc_size(stack_alignment, size, block, dbg);
883 /* The stack pointer will be modified in an unknown manner.
884 We cannot omit it. */
885 env->call->flags.try_omit_fp = 0;
886 subsp = be_new_SubSP(arch_env->sp, block, curr_sp, size);
887 set_irn_dbg_info(subsp, dbg);
889 mem = new_r_Proj(subsp, mode_M, pn_be_SubSP_M);
890 res = new_r_Proj(subsp, sp_mode, pn_be_SubSP_sp);
892 /* we need to sync the memory */
893 in[0] = get_Free_mem(free);
895 sync = new_r_Sync(block, 2, in);
897 /* and make the AddSP dependent on the former memory */
898 add_irn_dep(subsp, get_Free_mem(free));
901 exchange(free, sync);
908 * Check if a node is somehow data dependent on another one.
909 * both nodes must be in the same basic block.
910 * @param n1 The first node.
911 * @param n2 The second node.
912 * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
914 static int dependent_on(ir_node *n1, ir_node *n2)
916 assert(get_nodes_block(n1) == get_nodes_block(n2));
918 return heights_reachable_in_block(ir_heights, n1, n2);
921 static int cmp_call_dependency(const void *c1, const void *c2)
923 ir_node *n1 = *(ir_node **) c1;
924 ir_node *n2 = *(ir_node **) c2;
928 Classical qsort() comparison function behavior:
929 0 if both elements are equal
930 1 if second is "smaller" that first
931 -1 if first is "smaller" that second
933 if (dependent_on(n1, n2))
936 if (dependent_on(n2, n1))
939 /* The nodes have no depth order, but we need a total order because qsort()
942 * Additionally, we need to respect transitive dependencies. Consider a
943 * Call a depending on Call b and an independent Call c.
944 * We MUST NOT order c > a and b > c. */
945 h1 = get_irn_height(ir_heights, n1);
946 h2 = get_irn_height(ir_heights, n2);
947 if (h1 < h2) return -1;
948 if (h1 > h2) return 1;
949 /* Same height, so use a random (but stable) order */
950 return get_irn_idx(n1) - get_irn_idx(n2);
954 * Walker: links all Call/Alloc/Free nodes to the Block they are contained.
956 static void link_ops_in_block_walker(ir_node *irn, void *data)
958 be_abi_irg_t *env = (be_abi_irg_t*)data;
959 unsigned code = get_irn_opcode(irn);
961 if (code == iro_Call ||
962 (code == iro_Alloc && get_Alloc_where(irn) == stack_alloc) ||
963 (code == iro_Free && get_Free_where(irn) == stack_alloc)) {
964 ir_node *bl = get_nodes_block(irn);
965 void *save = get_irn_link(bl);
967 set_irn_link(irn, save);
968 set_irn_link(bl, irn);
971 if (code == iro_Builtin && get_Builtin_kind(irn) == ir_bk_return_address) {
972 ir_node *param = get_Builtin_param(irn, 0);
973 ir_tarval *tv = get_Const_tarval(param);
974 unsigned long value = get_tarval_long(tv);
975 /* use ebp, so the climbframe algo works... */
977 env->call->flags.try_omit_fp = 0;
984 * Process all Call/Alloc/Free nodes inside a basic block.
985 * Note that the link field of the block must contain a linked list of all
986 * nodes inside the Block. We first order this list according to data dependency
987 * and that connect the nodes together.
989 static void process_ops_in_block(ir_node *bl, void *data)
991 be_abi_irg_t *env = (be_abi_irg_t*)data;
992 ir_node *curr_sp = env->init_sp;
999 for (irn = (ir_node*)get_irn_link(bl); irn != NULL;
1000 irn = (ir_node*)get_irn_link(irn)) {
1004 nodes = ALLOCAN(ir_node*, n_nodes);
1005 for (irn = (ir_node*)get_irn_link(bl), n = 0; irn != NULL;
1006 irn = (ir_node*)get_irn_link(irn), ++n) {
1010 /* If there were call nodes in the block. */
1015 /* order the call nodes according to data dependency */
1016 qsort(nodes, n_nodes, sizeof(nodes[0]), cmp_call_dependency);
1018 for (i = n_nodes - 1; i >= 0; --i) {
1019 ir_node *irn = nodes[i];
1021 DBG((dbg, LEVEL_3, "\tprocessing call %+F\n", irn));
1022 switch (get_irn_opcode(irn)) {
1024 curr_sp = adjust_call(env, irn, curr_sp);
1027 if (get_Alloc_where(irn) == stack_alloc)
1028 curr_sp = adjust_alloc(env, irn, curr_sp);
1031 if (get_Free_where(irn) == stack_alloc)
1032 curr_sp = adjust_free(env, irn, curr_sp);
1035 panic("invalid call");
1039 /* Keep the last stack state in the block by tying it to Keep node,
1040 * the proj from calls is already kept */
1041 if (curr_sp != env->init_sp &&
1042 !(is_Proj(curr_sp) && be_is_Call(get_Proj_pred(curr_sp)))) {
1044 keep = be_new_Keep(bl, 1, nodes);
1045 pmap_insert(env->keep_map, bl, keep);
1049 set_irn_link(bl, curr_sp);
1053 * Adjust all call nodes in the graph to the ABI conventions.
1055 static void process_calls(ir_graph *const irg, be_abi_irg_t *const abi)
1057 irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, abi);
1059 ir_heights = heights_new(irg);
1060 irg_block_walk_graph(irg, NULL, process_ops_in_block, abi);
1061 heights_free(ir_heights);
1065 * Computes the stack argument layout type.
1066 * Changes a possibly allocated value param type by moving
1067 * entities to the stack layout type.
1069 * @param call the current call ABI
1070 * @param method_type the method type
1072 * @return the stack argument layout type
1074 static ir_type *compute_arg_type(ir_graph *irg, be_abi_call_t *call,
1075 ir_type *method_type)
1077 struct obstack *obst = be_get_be_obst(irg);
1078 ir_type *frame_type = get_irg_frame_type(irg);
1079 size_t n_params = get_method_n_params(method_type);
1080 size_t n_frame_members = get_compound_n_members(frame_type);
1081 ir_entity *va_start_entity = NULL;
1087 ir_entity **map = OALLOCNZ(obst, ir_entity*, n_params);
1088 res = new_type_struct(new_id_from_chars("arg_type", 8));
1090 /* collect existing entities for value_param_types */
1091 for (f = n_frame_members; f > 0; ) {
1092 ir_entity *entity = get_compound_member(frame_type, --f);
1095 set_entity_link(entity, NULL);
1096 if (!is_parameter_entity(entity))
1098 num = get_entity_parameter_number(entity);
1099 if (num == IR_VA_START_PARAMETER_NUMBER) {
1100 /* move entity to new arg_type */
1101 set_entity_owner(entity, res);
1102 va_start_entity = entity;
1105 assert(num < n_params);
1106 if (map[num] != NULL)
1107 panic("multiple entities for parameter %u in %+F found", f, irg);
1109 if (num != n_params && get_call_arg(call, 0, num, 1)->in_reg) {
1110 /* don't move this entity */
1115 /* move entity to new arg_type */
1116 set_entity_owner(entity, res);
1119 for (i = 0; i < n_params; ++i) {
1120 be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 1);
1121 ir_type *param_type = get_method_param_type(method_type, i);
1127 if (entity == NULL) {
1128 /* create a new entity */
1129 entity = new_parameter_entity(res, i, param_type);
1131 ofs += arg->space_before;
1132 ofs = round_up2(ofs, arg->alignment);
1133 set_entity_offset(entity, ofs);
1134 ofs += arg->space_after;
1135 ofs += get_type_size_bytes(param_type);
1136 arg->stack_ent = entity;
1138 if (va_start_entity != NULL) {
1139 set_entity_offset(va_start_entity, ofs);
1141 set_type_size_bytes(res, ofs);
1142 set_type_state(res, layout_fixed);
1148 const arch_register_t *reg;
1152 static int cmp_regs(const void *a, const void *b)
1154 const reg_node_map_t *p = (const reg_node_map_t*)a;
1155 const reg_node_map_t *q = (const reg_node_map_t*)b;
1157 if (p->reg->reg_class == q->reg->reg_class)
1158 return p->reg->index - q->reg->index;
1160 return p->reg->reg_class < q->reg->reg_class ? -1 : +1;
1163 static void reg_map_to_arr(reg_node_map_t *res, pmap *reg_map)
1166 size_t n = pmap_count(reg_map);
1169 foreach_pmap(reg_map, ent) {
1170 res[i].reg = (const arch_register_t*)ent->key;
1171 res[i].irn = (ir_node*)ent->value;
1175 qsort(res, n, sizeof(res[0]), cmp_regs);
1179 * Creates a be_Return for a Return node.
1181 * @param @env the abi environment
1182 * @param irn the Return node
1183 * @param bl the block where the be_Retun should be placed
1184 * @param mem the current memory
1185 * @param n_res number of return results
1187 static ir_node *create_be_return(be_abi_irg_t *env, ir_node *irn, ir_node *bl,
1188 ir_node *mem, int n_res)
1190 be_abi_call_t *call = env->call;
1191 ir_graph *irg = get_Block_irg(bl);
1192 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1193 pmap *reg_map = pmap_create();
1194 ir_node *keep = pmap_get(ir_node, env->keep_map, bl);
1201 const arch_register_t **regs;
1205 get the valid stack node in this block.
1206 If we had a call in that block there is a Keep constructed by process_calls()
1207 which points to the last stack modification in that block. we'll use
1208 it then. Else we use the stack from the start block and let
1209 the ssa construction fix the usage.
1211 stack = be_abi_reg_map_get(env->regs, arch_env->sp);
1213 stack = get_irn_n(keep, 0);
1215 remove_End_keepalive(get_irg_end(irg), keep);
1218 /* Insert results for Return into the register map. */
1219 for (i = 0; i < n_res; ++i) {
1220 ir_node *res = get_Return_res(irn, i);
1221 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1222 assert(arg->in_reg && "return value must be passed in register");
1223 pmap_insert(reg_map, (void *) arg->reg, res);
1226 /* Add uses of the callee save registers. */
1227 foreach_pmap(env->regs, ent) {
1228 const arch_register_t *reg = (const arch_register_t*)ent->key;
1229 if ((reg->type & arch_register_type_ignore) || arch_register_is_callee_save(arch_env, reg))
1230 pmap_insert(reg_map, ent->key, ent->value);
1233 be_abi_reg_map_set(reg_map, arch_env->sp, stack);
1236 Maximum size of the in array for Return nodes is
1237 return args + callee save/ignore registers + memory + stack pointer
1239 in_max = pmap_count(reg_map) + n_res + 2;
1241 in = ALLOCAN(ir_node*, in_max);
1242 regs = ALLOCAN(arch_register_t const*, in_max);
1245 in[1] = be_abi_reg_map_get(reg_map, arch_env->sp);
1247 regs[1] = arch_env->sp;
1250 /* clear SP entry, since it has already been grown. */
1251 pmap_insert(reg_map, (void *) arch_env->sp, NULL);
1252 for (i = 0; i < n_res; ++i) {
1253 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1255 in[n] = be_abi_reg_map_get(reg_map, arg->reg);
1256 regs[n++] = arg->reg;
1258 /* Clear the map entry to mark the register as processed. */
1259 be_abi_reg_map_set(reg_map, arg->reg, NULL);
1262 /* grow the rest of the stuff. */
1263 foreach_pmap(reg_map, ent) {
1265 in[n] = (ir_node*)ent->value;
1266 regs[n++] = (const arch_register_t*)ent->key;
1270 /* The in array for the new back end return is now ready. */
1271 dbg_info *const dbgi = get_irn_dbg_info(irn);
1272 /* we have to pop the shadow parameter in in case of struct returns */
1274 ret = be_new_Return(dbgi, irg, bl, n_res, pop, n, in);
1276 /* Set the register classes of the return's parameter accordingly. */
1277 for (i = 0; i < n; ++i) {
1278 if (regs[i] == NULL)
1281 be_set_constr_single_reg_in(ret, i, regs[i], arch_register_req_type_none);
1284 /* Free the space of the Epilog's in array and the register <-> proj map. */
1285 pmap_destroy(reg_map);
1290 typedef struct lower_frame_sels_env_t {
1291 ir_node *frame; /**< the current frame */
1292 const arch_register_class_t *sp_class; /**< register class of the stack pointer */
1293 } lower_frame_sels_env_t;
1296 * Walker: Replaces Sels of frame type and
1297 * value param type entities by FrameAddress.
1298 * Links all used entities.
1300 static void lower_frame_sels_walker(ir_node *irn, void *data)
1302 lower_frame_sels_env_t *ctx = (lower_frame_sels_env_t*)data;
1305 ir_node *ptr = get_Sel_ptr(irn);
1307 if (ptr == ctx->frame) {
1308 ir_entity *ent = get_Sel_entity(irn);
1309 ir_node *bl = get_nodes_block(irn);
1312 nw = be_new_FrameAddr(ctx->sp_class, bl, ctx->frame, ent);
1319 * The start block has no jump, instead it has an initial exec Proj.
1320 * The backend wants to handle all blocks the same way, so we replace
1321 * the out cfg edge with a real jump.
1323 static void fix_start_block(ir_graph *irg)
1325 ir_node *initial_X = get_irg_initial_exec(irg);
1326 ir_node *start_block = get_irg_start_block(irg);
1327 ir_node *jmp = new_r_Jmp(start_block);
1329 assert(is_Proj(initial_X));
1330 exchange(initial_X, jmp);
1331 set_irg_initial_exec(irg, new_r_Bad(irg, mode_X));
1333 /* merge start block with successor if possible */
1335 foreach_out_edge(jmp, edge) {
1336 ir_node *succ = get_edge_src_irn(edge);
1337 if (!is_Block(succ))
1340 if (get_irn_arity(succ) == 1) {
1341 exchange(succ, start_block);
1349 * Modify the irg itself and the frame type.
1351 static void modify_irg(ir_graph *const irg, be_abi_irg_t *const env)
1353 be_abi_call_t *call = env->call;
1354 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1355 const arch_register_t *sp = arch_env->sp;
1356 ir_type *method_type = get_entity_type(get_irg_entity(irg));
1357 be_irg_t *birg = be_birg_from_irg(irg);
1358 struct obstack *obst = be_get_be_obst(irg);
1359 be_stack_layout_t *stack_layout = be_get_irg_stack_layout(irg);
1362 ir_node *new_mem_proj;
1370 const arch_register_t *fp_reg;
1371 ir_node *frame_pointer;
1375 ir_type *arg_type, *bet_type;
1376 lower_frame_sels_env_t ctx;
1378 DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1380 old_mem = get_irg_initial_mem(irg);
1382 irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1384 arg_type = compute_arg_type(irg, call, method_type);
1386 /* Convert the Sel nodes in the irg to frame addr nodes: */
1387 ctx.frame = get_irg_frame(irg);
1388 ctx.sp_class = arch_env->sp->reg_class;
1390 ir_type *const frame_tp = get_irg_frame_type(irg);
1391 /* layout the stackframe now */
1392 if (get_type_state(frame_tp) == layout_undefined) {
1393 default_layout_compound_type(frame_tp);
1396 /* align stackframe */
1397 unsigned const alignment = 1U << arch_env->stack_alignment;
1398 unsigned const frame_size = round_up2(get_type_size_bytes(frame_tp), alignment);
1399 set_type_size_bytes(frame_tp, frame_size);
1401 env->regs = pmap_create();
1403 n_params = get_method_n_params(method_type);
1404 args = OALLOCNZ(obst, ir_node*, n_params);
1406 be_add_parameter_entity_stores(irg);
1408 irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1410 irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1412 /* Fill the argument vector */
1413 arg_tuple = get_irg_args(irg);
1414 foreach_out_edge(arg_tuple, edge) {
1415 ir_node *irn = get_edge_src_irn(edge);
1416 if (! is_Anchor(irn)) {
1417 int nr = get_Proj_proj(irn);
1419 DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1423 stack_layout->sp_relative = call->flags.try_omit_fp;
1424 bet_type = call->cb->get_between_type(irg);
1425 stack_frame_init(stack_layout, arg_type, bet_type,
1426 get_irg_frame_type(irg));
1428 /* Count the register params and add them to the number of Projs for the RegParams node */
1429 for (i = 0; i < n_params; ++i) {
1430 be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 1);
1431 if (arg->in_reg && args[i]) {
1432 assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1433 assert(i == get_Proj_proj(args[i]));
1435 /* For now, associate the register with the old Proj from Start representing that argument. */
1436 pmap_insert(env->regs, (void *) arg->reg, args[i]);
1437 DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1441 /* Collect all callee-save registers */
1442 for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
1443 const arch_register_class_t *cls = &arch_env->register_classes[i];
1444 for (j = 0; j < cls->n_regs; ++j) {
1445 const arch_register_t *reg = &cls->regs[j];
1446 if ((reg->type & arch_register_type_state) || arch_register_is_callee_save(arch_env, reg)) {
1447 pmap_insert(env->regs, (void *) reg, NULL);
1452 fp_reg = call->flags.try_omit_fp ? arch_env->sp : arch_env->bp;
1453 rbitset_clear(birg->allocatable_regs, fp_reg->global_index);
1455 /* handle start block here (place a jump in the block) */
1456 fix_start_block(irg);
1458 pmap_insert(env->regs, (void *) sp, NULL);
1459 pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1460 start_bl = get_irg_start_block(irg);
1461 ir_node *const start = be_new_Start(NULL, start_bl, pmap_count(env->regs) + 1);
1462 set_irg_start(irg, start);
1465 * make proj nodes for the callee save registers.
1466 * memorize them, since Return nodes get those as inputs.
1468 * Note, that if a register corresponds to an argument, the regs map
1469 * contains the old Proj from start for that argument.
1471 rm = ALLOCAN(reg_node_map_t, pmap_count(env->regs));
1472 reg_map_to_arr(rm, env->regs);
1473 for (i = 0, n = pmap_count(env->regs); i < n; ++i) {
1474 const arch_register_t *reg = rm[i].reg;
1475 ir_mode *mode = reg->reg_class->mode;
1477 arch_register_req_type_t add_type = arch_register_req_type_none;
1481 add_type |= arch_register_req_type_produces_sp;
1482 if (!rbitset_is_set(birg->allocatable_regs, reg->global_index)) {
1483 add_type |= arch_register_req_type_ignore;
1487 proj = new_r_Proj(start, mode, nr + 1);
1488 pmap_insert(env->regs, (void *) reg, proj);
1489 be_set_constr_single_reg_out(start, nr + 1, reg, add_type);
1490 arch_set_irn_register(proj, reg);
1492 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1495 /* create a new initial memory proj */
1496 assert(is_Proj(old_mem));
1497 arch_set_irn_register_req_out(start, 0, arch_no_register_req);
1498 new_mem_proj = new_r_Proj(start, mode_M, 0);
1500 set_irg_initial_mem(irg, mem);
1502 env->init_sp = be_abi_reg_map_get(env->regs, sp);
1504 /* set new frame_pointer */
1505 frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
1506 set_irg_frame(irg, frame_pointer);
1508 /* rewire old mem users to new mem */
1509 exchange(old_mem, mem);
1511 /* keep the mem (for functions with an endless loop = no return) */
1514 set_irg_initial_mem(irg, mem);
1516 /* Now, introduce stack param nodes for all parameters passed on the stack */
1517 for (i = 0; i < n_params; ++i) {
1518 ir_node *arg_proj = args[i];
1519 ir_node *repl = NULL;
1521 if (arg_proj != NULL) {
1522 be_abi_call_arg_t *arg;
1523 ir_type *param_type;
1524 int nr = get_Proj_proj(arg_proj);
1527 nr = MIN(nr, n_params);
1528 arg = get_call_arg(call, 0, nr, 1);
1529 param_type = get_method_param_type(method_type, nr);
1532 repl = pmap_get(ir_node, env->regs, arg->reg);
1534 ir_node *addr = be_new_FrameAddr(sp->reg_class, start_bl, frame_pointer, arg->stack_ent);
1536 /* For atomic parameters which are actually used, we create a Load node. */
1537 if (is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
1538 ir_mode *mode = get_type_mode(param_type);
1539 ir_mode *load_mode = arg->load_mode;
1540 ir_node *nomem = get_irg_no_mem(irg);
1542 ir_node *load = new_r_Load(start_bl, nomem, addr, load_mode, cons_floats);
1543 repl = new_r_Proj(load, load_mode, pn_Load_res);
1545 if (mode != load_mode) {
1546 repl = new_r_Conv(start_bl, repl, mode);
1549 /* The stack parameter is not primitive (it is a struct or array),
1550 * we thus will create a node representing the parameter's address
1556 assert(repl != NULL);
1558 /* Beware: the mode of the register parameters is always the mode of the register class
1559 which may be wrong. Add Conv's then. */
1560 mode = get_irn_mode(args[i]);
1561 if (mode != get_irn_mode(repl)) {
1562 repl = new_r_Conv(get_nodes_block(repl), repl, mode);
1564 exchange(args[i], repl);
1568 /* the arg proj is not needed anymore now and should be only used by the anchor */
1569 assert(get_irn_n_edges(arg_tuple) == 1);
1570 kill_node(arg_tuple);
1571 set_irg_args(irg, new_r_Bad(irg, mode_T));
1573 /* All Return nodes hang on the End node, so look for them there. */
1574 end = get_irg_end_block(irg);
1575 for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
1576 ir_node *irn = get_Block_cfgpred(end, i);
1578 if (is_Return(irn)) {
1579 ir_node *blk = get_nodes_block(irn);
1580 ir_node *mem = get_Return_mem(irn);
1581 ir_node *ret = create_be_return(env, irn, blk, mem, get_Return_n_ress(irn));
1586 /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
1587 the code is dead and will never be executed. */
1590 /** Fix the state inputs of calls that still hang on unknowns */
1591 static void fix_call_state_inputs(ir_graph *const irg, be_abi_irg_t *const env)
1593 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1595 arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
1597 /* Collect caller save registers */
1598 n = arch_env->n_register_classes;
1599 for (i = 0; i < n; ++i) {
1601 const arch_register_class_t *cls = &arch_env->register_classes[i];
1602 for (j = 0; j < cls->n_regs; ++j) {
1603 const arch_register_t *reg = arch_register_for_index(cls, j);
1604 if (reg->type & arch_register_type_state) {
1605 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
1610 n = ARR_LEN(env->calls);
1611 n_states = ARR_LEN(stateregs);
1612 for (i = 0; i < n; ++i) {
1614 ir_node *call = env->calls[i];
1616 arity = get_irn_arity(call);
1618 /* the state reg inputs are the last n inputs of the calls */
1619 for (s = 0; s < n_states; ++s) {
1620 int inp = arity - n_states + s;
1621 const arch_register_t *reg = stateregs[s];
1622 ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
1624 set_irn_n(call, inp, regnode);
1628 DEL_ARR_F(stateregs);
1632 * Create a trampoline entity for the given method.
1634 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
1636 ir_type *type = get_entity_type(method);
1637 ident *old_id = get_entity_ld_ident(method);
1638 ident *id = id_mangle3("", old_id, "$stub");
1639 ir_type *parent = be->pic_trampolines_type;
1640 ir_entity *ent = new_entity(parent, old_id, type);
1641 set_entity_ld_ident(ent, id);
1642 set_entity_visibility(ent, ir_visibility_private);
1648 * Returns the trampoline entity for the given method.
1650 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
1652 ir_entity *result = pmap_get(ir_entity, env->ent_trampoline_map, method);
1653 if (result == NULL) {
1654 result = create_trampoline(env, method);
1655 pmap_insert(env->ent_trampoline_map, method, result);
1661 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
1663 ident *old_id = get_entity_ld_ident(entity);
1664 ident *id = id_mangle3("", old_id, "$non_lazy_ptr");
1665 ir_type *e_type = get_entity_type(entity);
1666 ir_type *type = new_type_pointer(e_type);
1667 ir_type *parent = be->pic_symbols_type;
1668 ir_entity *ent = new_entity(parent, old_id, type);
1669 set_entity_ld_ident(ent, id);
1670 set_entity_visibility(ent, ir_visibility_private);
1675 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
1677 ir_entity *result = pmap_get(ir_entity, env->ent_pic_symbol_map, entity);
1678 if (result == NULL) {
1679 result = create_pic_symbol(env, entity);
1680 pmap_insert(env->ent_pic_symbol_map, entity, result);
1689 * Returns non-zero if a given entity can be accessed using a relative address.
1691 static int can_address_relative(ir_entity *entity)
1693 return entity_has_definition(entity) && !(get_entity_linkage(entity) & IR_LINKAGE_MERGE);
1696 static ir_node *get_pic_base(ir_graph *irg)
1698 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1699 if (arch_env->impl->get_pic_base == NULL)
1701 return arch_env->impl->get_pic_base(irg);
1704 /** patches SymConsts to work in position independent code */
1705 static void fix_pic_symconsts(ir_node *node, void *data)
1707 ir_graph *irg = get_irn_irg(node);
1708 be_main_env_t *be = be_get_irg_main_env(irg);
1718 arity = get_irn_arity(node);
1719 for (i = 0; i < arity; ++i) {
1721 ir_node *pred = get_irn_n(node, i);
1723 ir_entity *pic_symbol;
1724 ir_node *pic_symconst;
1726 if (!is_SymConst(pred))
1729 entity = get_SymConst_entity(pred);
1730 block = get_nodes_block(pred);
1732 /* calls can jump to relative addresses, so we can directly jump to
1733 the (relatively) known call address or the trampoline */
1734 if (i == 1 && is_Call(node)) {
1735 ir_entity *trampoline;
1736 ir_node *trampoline_const;
1738 if (can_address_relative(entity))
1741 dbgi = get_irn_dbg_info(pred);
1742 trampoline = get_trampoline(be, entity);
1743 trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1745 set_irn_n(node, i, trampoline_const);
1749 /* everything else is accessed relative to EIP */
1750 mode = get_irn_mode(pred);
1751 pic_base = get_pic_base(irg);
1753 /* all ok now for locally constructed stuff */
1754 if (can_address_relative(entity)) {
1755 ir_node *add = new_r_Add(block, pic_base, pred, mode);
1757 /* make sure the walker doesn't visit this add again */
1758 mark_irn_visited(add);
1759 set_irn_n(node, i, add);
1763 /* get entry from pic symbol segment */
1764 dbgi = get_irn_dbg_info(pred);
1765 pic_symbol = get_pic_symbol(be, entity);
1766 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1768 add = new_r_Add(block, pic_base, pic_symconst, mode);
1769 mark_irn_visited(add);
1771 /* we need an extra indirection for global data outside our current
1772 module. The loads are always safe and can therefore float
1773 and need no memory input */
1774 load = new_r_Load(block, get_irg_no_mem(irg), add, mode, cons_floats);
1775 load_res = new_r_Proj(load, mode, pn_Load_res);
1777 set_irn_n(node, i, load_res);
1781 void be_abi_introduce(ir_graph *irg)
1783 ir_node *old_frame = get_irg_frame(irg);
1784 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1785 ir_entity *entity = get_irg_entity(irg);
1786 ir_type *method_type = get_entity_type(entity);
1787 be_irg_t *birg = be_birg_from_irg(irg);
1788 struct obstack *obst = &birg->obst;
1789 ir_node *dummy = new_r_Dummy(irg,
1790 arch_env->sp->reg_class->mode);
1793 /* determine allocatable registers */
1794 assert(birg->allocatable_regs == NULL);
1795 birg->allocatable_regs = rbitset_obstack_alloc(obst, arch_env->n_registers);
1796 for (r = 0; r < arch_env->n_registers; ++r) {
1797 const arch_register_t *reg = &arch_env->registers[r];
1798 if ( !(reg->type & arch_register_type_ignore)) {
1799 rbitset_set(birg->allocatable_regs, r);
1803 /* Break here if backend provides a custom API. */
1806 env.keep_map = pmap_create();
1807 env.call = be_abi_call_new();
1808 arch_env_get_call_abi(arch_env, method_type, env.call);
1810 env.init_sp = dummy;
1811 env.calls = NEW_ARR_F(ir_node*, 0);
1815 if (be_options.pic) {
1816 irg_walk_graph(irg, fix_pic_symconsts, NULL, NULL);
1819 /* Lower all call nodes in the IRG. */
1820 process_calls(irg, &env);
1822 /* Process the IRG */
1823 modify_irg(irg, &env);
1825 /* fix call inputs for state registers */
1826 fix_call_state_inputs(irg, &env);
1828 be_abi_call_free(env.call);
1830 /* We don't need the keep map anymore. */
1831 pmap_destroy(env.keep_map);
1833 /* calls array is not needed anymore */
1834 DEL_ARR_F(env.calls);
1836 /* reroute the stack origin of the calls to the true stack origin. */
1837 exchange(dummy, env.init_sp);
1838 exchange(old_frame, get_irg_frame(irg));
1840 pmap_destroy(env.regs);
1843 void be_put_allocatable_regs(const ir_graph *irg,
1844 const arch_register_class_t *cls, bitset_t *bs)
1846 be_irg_t *birg = be_birg_from_irg(irg);
1847 unsigned *allocatable_regs = birg->allocatable_regs;
1850 assert(bitset_size(bs) == cls->n_regs);
1851 bitset_clear_all(bs);
1852 for (i = 0; i < cls->n_regs; ++i) {
1853 const arch_register_t *reg = &cls->regs[i];
1854 if (rbitset_is_set(allocatable_regs, reg->global_index))
1859 unsigned be_get_n_allocatable_regs(const ir_graph *irg,
1860 const arch_register_class_t *cls)
1862 bitset_t *bs = bitset_alloca(cls->n_regs);
1863 be_put_allocatable_regs(irg, cls, bs);
1864 return bitset_popcount(bs);
1867 void be_set_allocatable_regs(const ir_graph *irg,
1868 const arch_register_class_t *cls,
1869 unsigned *raw_bitset)
1871 be_irg_t *birg = be_birg_from_irg(irg);
1872 unsigned *allocatable_regs = birg->allocatable_regs;
1875 rbitset_clear_all(raw_bitset, cls->n_regs);
1876 for (i = 0; i < cls->n_regs; ++i) {
1877 const arch_register_t *reg = &cls->regs[i];
1878 if (rbitset_is_set(allocatable_regs, reg->global_index))
1879 rbitset_set(raw_bitset, i);
1883 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_abi)
1884 void be_init_abi(void)
1886 FIRM_DBG_REGISTER(dbg, "firm.be.abi");