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
1184 static ir_node *create_be_return(be_abi_irg_t *const env, ir_node *const irn)
1186 ir_node *const bl = get_nodes_block(irn);
1187 be_abi_call_t *call = env->call;
1188 ir_graph *irg = get_Block_irg(bl);
1189 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1190 pmap *reg_map = pmap_create();
1191 ir_node *keep = pmap_get(ir_node, env->keep_map, bl);
1196 const arch_register_t **regs;
1200 get the valid stack node in this block.
1201 If we had a call in that block there is a Keep constructed by process_calls()
1202 which points to the last stack modification in that block. we'll use
1203 it then. Else we use the stack from the start block and let
1204 the ssa construction fix the usage.
1206 stack = be_abi_reg_map_get(env->regs, arch_env->sp);
1208 stack = get_irn_n(keep, 0);
1210 remove_End_keepalive(get_irg_end(irg), keep);
1213 int const n_res = get_Return_n_ress(irn);
1214 /* Insert results for Return into the register map. */
1215 for (i = 0; i < n_res; ++i) {
1216 ir_node *res = get_Return_res(irn, i);
1217 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1218 assert(arg->in_reg && "return value must be passed in register");
1219 pmap_insert(reg_map, (void *) arg->reg, res);
1222 /* Add uses of the callee save registers. */
1223 foreach_pmap(env->regs, ent) {
1224 const arch_register_t *reg = (const arch_register_t*)ent->key;
1225 if ((reg->type & arch_register_type_ignore) || arch_register_is_callee_save(arch_env, reg))
1226 pmap_insert(reg_map, ent->key, ent->value);
1229 be_abi_reg_map_set(reg_map, arch_env->sp, stack);
1232 Maximum size of the in array for Return nodes is
1233 return args + callee save/ignore registers + memory + stack pointer
1235 in_max = pmap_count(reg_map) + n_res + 2;
1237 in = ALLOCAN(ir_node*, in_max);
1238 regs = ALLOCAN(arch_register_t const*, in_max);
1240 in[0] = get_Return_mem(irn);
1241 in[1] = be_abi_reg_map_get(reg_map, arch_env->sp);
1243 regs[1] = arch_env->sp;
1246 /* clear SP entry, since it has already been grown. */
1247 pmap_insert(reg_map, (void *) arch_env->sp, NULL);
1248 for (i = 0; i < n_res; ++i) {
1249 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1251 in[n] = be_abi_reg_map_get(reg_map, arg->reg);
1252 regs[n++] = arg->reg;
1254 /* Clear the map entry to mark the register as processed. */
1255 be_abi_reg_map_set(reg_map, arg->reg, NULL);
1258 /* grow the rest of the stuff. */
1259 foreach_pmap(reg_map, ent) {
1261 in[n] = (ir_node*)ent->value;
1262 regs[n++] = (const arch_register_t*)ent->key;
1266 /* The in array for the new back end return is now ready. */
1267 dbg_info *const dbgi = get_irn_dbg_info(irn);
1268 ir_node *const ret = be_new_Return(dbgi, irg, bl, n_res, call->pop, n, in);
1270 /* Set the register classes of the return's parameter accordingly. */
1271 for (i = 0; i < n; ++i) {
1272 if (regs[i] == NULL)
1275 be_set_constr_single_reg_in(ret, i, regs[i], arch_register_req_type_none);
1278 /* Free the space of the Epilog's in array and the register <-> proj map. */
1279 pmap_destroy(reg_map);
1284 typedef struct lower_frame_sels_env_t {
1285 ir_node *frame; /**< the current frame */
1286 const arch_register_class_t *sp_class; /**< register class of the stack pointer */
1287 } lower_frame_sels_env_t;
1290 * Walker: Replaces Sels of frame type and
1291 * value param type entities by FrameAddress.
1292 * Links all used entities.
1294 static void lower_frame_sels_walker(ir_node *irn, void *data)
1296 lower_frame_sels_env_t *ctx = (lower_frame_sels_env_t*)data;
1299 ir_node *ptr = get_Sel_ptr(irn);
1301 if (ptr == ctx->frame) {
1302 ir_entity *ent = get_Sel_entity(irn);
1303 ir_node *bl = get_nodes_block(irn);
1306 nw = be_new_FrameAddr(ctx->sp_class, bl, ctx->frame, ent);
1313 * The start block has no jump, instead it has an initial exec Proj.
1314 * The backend wants to handle all blocks the same way, so we replace
1315 * the out cfg edge with a real jump.
1317 static void fix_start_block(ir_graph *irg)
1319 ir_node *initial_X = get_irg_initial_exec(irg);
1320 ir_node *start_block = get_irg_start_block(irg);
1321 ir_node *jmp = new_r_Jmp(start_block);
1323 assert(is_Proj(initial_X));
1324 exchange(initial_X, jmp);
1325 set_irg_initial_exec(irg, new_r_Bad(irg, mode_X));
1327 /* merge start block with successor if possible */
1329 foreach_out_edge(jmp, edge) {
1330 ir_node *succ = get_edge_src_irn(edge);
1331 if (!is_Block(succ))
1334 if (get_irn_arity(succ) == 1) {
1335 exchange(succ, start_block);
1343 * Modify the irg itself and the frame type.
1345 static void modify_irg(ir_graph *const irg, be_abi_irg_t *const env)
1347 be_abi_call_t *call = env->call;
1348 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1349 const arch_register_t *sp = arch_env->sp;
1350 ir_type *method_type = get_entity_type(get_irg_entity(irg));
1351 be_irg_t *birg = be_birg_from_irg(irg);
1352 struct obstack *obst = be_get_be_obst(irg);
1353 be_stack_layout_t *stack_layout = be_get_irg_stack_layout(irg);
1356 ir_node *new_mem_proj;
1364 const arch_register_t *fp_reg;
1365 ir_node *frame_pointer;
1369 ir_type *arg_type, *bet_type;
1370 lower_frame_sels_env_t ctx;
1372 DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1374 old_mem = get_irg_initial_mem(irg);
1376 irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1378 arg_type = compute_arg_type(irg, call, method_type);
1380 /* Convert the Sel nodes in the irg to frame addr nodes: */
1381 ctx.frame = get_irg_frame(irg);
1382 ctx.sp_class = arch_env->sp->reg_class;
1384 ir_type *const frame_tp = get_irg_frame_type(irg);
1385 /* layout the stackframe now */
1386 if (get_type_state(frame_tp) == layout_undefined) {
1387 default_layout_compound_type(frame_tp);
1390 /* align stackframe */
1391 unsigned const alignment = 1U << arch_env->stack_alignment;
1392 unsigned const frame_size = round_up2(get_type_size_bytes(frame_tp), alignment);
1393 set_type_size_bytes(frame_tp, frame_size);
1395 env->regs = pmap_create();
1397 n_params = get_method_n_params(method_type);
1398 args = OALLOCNZ(obst, ir_node*, n_params);
1400 be_add_parameter_entity_stores(irg);
1402 irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1404 irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1406 /* Fill the argument vector */
1407 arg_tuple = get_irg_args(irg);
1408 foreach_out_edge(arg_tuple, edge) {
1409 ir_node *irn = get_edge_src_irn(edge);
1410 if (! is_Anchor(irn)) {
1411 int nr = get_Proj_proj(irn);
1413 DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1417 stack_layout->sp_relative = call->flags.try_omit_fp;
1418 bet_type = call->cb->get_between_type(irg);
1419 stack_frame_init(stack_layout, arg_type, bet_type,
1420 get_irg_frame_type(irg));
1422 /* Count the register params and add them to the number of Projs for the RegParams node */
1423 for (i = 0; i < n_params; ++i) {
1424 be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 1);
1425 if (arg->in_reg && args[i]) {
1426 assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1427 assert(i == get_Proj_proj(args[i]));
1429 /* For now, associate the register with the old Proj from Start representing that argument. */
1430 pmap_insert(env->regs, (void *) arg->reg, args[i]);
1431 DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1435 /* Collect all callee-save registers */
1436 for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
1437 const arch_register_class_t *cls = &arch_env->register_classes[i];
1438 for (j = 0; j < cls->n_regs; ++j) {
1439 const arch_register_t *reg = &cls->regs[j];
1440 if ((reg->type & arch_register_type_state) || arch_register_is_callee_save(arch_env, reg)) {
1441 pmap_insert(env->regs, (void *) reg, NULL);
1446 fp_reg = call->flags.try_omit_fp ? arch_env->sp : arch_env->bp;
1447 rbitset_clear(birg->allocatable_regs, fp_reg->global_index);
1449 /* handle start block here (place a jump in the block) */
1450 fix_start_block(irg);
1452 pmap_insert(env->regs, (void *) sp, NULL);
1453 pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1454 start_bl = get_irg_start_block(irg);
1455 ir_node *const start = be_new_Start(NULL, start_bl, pmap_count(env->regs) + 1);
1456 set_irg_start(irg, start);
1459 * make proj nodes for the callee save registers.
1460 * memorize them, since Return nodes get those as inputs.
1462 * Note, that if a register corresponds to an argument, the regs map
1463 * contains the old Proj from start for that argument.
1465 rm = ALLOCAN(reg_node_map_t, pmap_count(env->regs));
1466 reg_map_to_arr(rm, env->regs);
1467 for (i = 0, n = pmap_count(env->regs); i < n; ++i) {
1468 const arch_register_t *reg = rm[i].reg;
1469 ir_mode *mode = reg->reg_class->mode;
1471 arch_register_req_type_t add_type = arch_register_req_type_none;
1475 add_type |= arch_register_req_type_produces_sp;
1476 if (!rbitset_is_set(birg->allocatable_regs, reg->global_index)) {
1477 add_type |= arch_register_req_type_ignore;
1481 proj = new_r_Proj(start, mode, nr + 1);
1482 pmap_insert(env->regs, (void *) reg, proj);
1483 be_set_constr_single_reg_out(start, nr + 1, reg, add_type);
1484 arch_set_irn_register(proj, reg);
1486 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1489 /* create a new initial memory proj */
1490 assert(is_Proj(old_mem));
1491 arch_set_irn_register_req_out(start, 0, arch_no_register_req);
1492 new_mem_proj = new_r_Proj(start, mode_M, 0);
1494 set_irg_initial_mem(irg, mem);
1496 env->init_sp = be_abi_reg_map_get(env->regs, sp);
1498 /* set new frame_pointer */
1499 frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
1500 set_irg_frame(irg, frame_pointer);
1502 /* rewire old mem users to new mem */
1503 exchange(old_mem, mem);
1505 /* keep the mem (for functions with an endless loop = no return) */
1508 set_irg_initial_mem(irg, mem);
1510 /* Now, introduce stack param nodes for all parameters passed on the stack */
1511 for (i = 0; i < n_params; ++i) {
1512 ir_node *arg_proj = args[i];
1513 ir_node *repl = NULL;
1515 if (arg_proj != NULL) {
1516 be_abi_call_arg_t *arg;
1517 ir_type *param_type;
1518 int nr = get_Proj_proj(arg_proj);
1521 nr = MIN(nr, n_params);
1522 arg = get_call_arg(call, 0, nr, 1);
1523 param_type = get_method_param_type(method_type, nr);
1526 repl = pmap_get(ir_node, env->regs, arg->reg);
1528 ir_node *addr = be_new_FrameAddr(sp->reg_class, start_bl, frame_pointer, arg->stack_ent);
1530 /* For atomic parameters which are actually used, we create a Load node. */
1531 if (is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
1532 ir_mode *mode = get_type_mode(param_type);
1533 ir_mode *load_mode = arg->load_mode;
1534 ir_node *nomem = get_irg_no_mem(irg);
1536 ir_node *load = new_r_Load(start_bl, nomem, addr, load_mode, cons_floats);
1537 repl = new_r_Proj(load, load_mode, pn_Load_res);
1539 if (mode != load_mode) {
1540 repl = new_r_Conv(start_bl, repl, mode);
1543 /* The stack parameter is not primitive (it is a struct or array),
1544 * we thus will create a node representing the parameter's address
1550 assert(repl != NULL);
1552 /* Beware: the mode of the register parameters is always the mode of the register class
1553 which may be wrong. Add Conv's then. */
1554 mode = get_irn_mode(args[i]);
1555 if (mode != get_irn_mode(repl)) {
1556 repl = new_r_Conv(get_nodes_block(repl), repl, mode);
1558 exchange(args[i], repl);
1562 /* the arg proj is not needed anymore now and should be only used by the anchor */
1563 assert(get_irn_n_edges(arg_tuple) == 1);
1564 kill_node(arg_tuple);
1565 set_irg_args(irg, new_r_Bad(irg, mode_T));
1567 /* All Return nodes hang on the End node, so look for them there. */
1568 end = get_irg_end_block(irg);
1569 for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
1570 ir_node *irn = get_Block_cfgpred(end, i);
1572 if (is_Return(irn)) {
1573 ir_node *const ret = create_be_return(env, irn);
1578 /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
1579 the code is dead and will never be executed. */
1582 /** Fix the state inputs of calls that still hang on unknowns */
1583 static void fix_call_state_inputs(ir_graph *const irg, be_abi_irg_t *const env)
1585 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1587 arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
1589 /* Collect caller save registers */
1590 n = arch_env->n_register_classes;
1591 for (i = 0; i < n; ++i) {
1593 const arch_register_class_t *cls = &arch_env->register_classes[i];
1594 for (j = 0; j < cls->n_regs; ++j) {
1595 const arch_register_t *reg = arch_register_for_index(cls, j);
1596 if (reg->type & arch_register_type_state) {
1597 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
1602 n = ARR_LEN(env->calls);
1603 n_states = ARR_LEN(stateregs);
1604 for (i = 0; i < n; ++i) {
1606 ir_node *call = env->calls[i];
1608 arity = get_irn_arity(call);
1610 /* the state reg inputs are the last n inputs of the calls */
1611 for (s = 0; s < n_states; ++s) {
1612 int inp = arity - n_states + s;
1613 const arch_register_t *reg = stateregs[s];
1614 ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
1616 set_irn_n(call, inp, regnode);
1620 DEL_ARR_F(stateregs);
1624 * Create a trampoline entity for the given method.
1626 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
1628 ir_type *type = get_entity_type(method);
1629 ident *old_id = get_entity_ld_ident(method);
1630 ident *id = id_mangle3("", old_id, "$stub");
1631 ir_type *parent = be->pic_trampolines_type;
1632 ir_entity *ent = new_entity(parent, old_id, type);
1633 set_entity_ld_ident(ent, id);
1634 set_entity_visibility(ent, ir_visibility_private);
1640 * Returns the trampoline entity for the given method.
1642 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
1644 ir_entity *result = pmap_get(ir_entity, env->ent_trampoline_map, method);
1645 if (result == NULL) {
1646 result = create_trampoline(env, method);
1647 pmap_insert(env->ent_trampoline_map, method, result);
1653 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
1655 ident *old_id = get_entity_ld_ident(entity);
1656 ident *id = id_mangle3("", old_id, "$non_lazy_ptr");
1657 ir_type *e_type = get_entity_type(entity);
1658 ir_type *type = new_type_pointer(e_type);
1659 ir_type *parent = be->pic_symbols_type;
1660 ir_entity *ent = new_entity(parent, old_id, type);
1661 set_entity_ld_ident(ent, id);
1662 set_entity_visibility(ent, ir_visibility_private);
1667 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
1669 ir_entity *result = pmap_get(ir_entity, env->ent_pic_symbol_map, entity);
1670 if (result == NULL) {
1671 result = create_pic_symbol(env, entity);
1672 pmap_insert(env->ent_pic_symbol_map, entity, result);
1681 * Returns non-zero if a given entity can be accessed using a relative address.
1683 static int can_address_relative(ir_entity *entity)
1685 return entity_has_definition(entity) && !(get_entity_linkage(entity) & IR_LINKAGE_MERGE);
1688 static ir_node *get_pic_base(ir_graph *irg)
1690 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1691 if (arch_env->impl->get_pic_base == NULL)
1693 return arch_env->impl->get_pic_base(irg);
1696 /** patches SymConsts to work in position independent code */
1697 static void fix_pic_symconsts(ir_node *node, void *data)
1699 ir_graph *irg = get_irn_irg(node);
1700 be_main_env_t *be = be_get_irg_main_env(irg);
1710 arity = get_irn_arity(node);
1711 for (i = 0; i < arity; ++i) {
1713 ir_node *pred = get_irn_n(node, i);
1715 ir_entity *pic_symbol;
1716 ir_node *pic_symconst;
1718 if (!is_SymConst(pred))
1721 entity = get_SymConst_entity(pred);
1722 block = get_nodes_block(pred);
1724 /* calls can jump to relative addresses, so we can directly jump to
1725 the (relatively) known call address or the trampoline */
1726 if (i == 1 && is_Call(node)) {
1727 ir_entity *trampoline;
1728 ir_node *trampoline_const;
1730 if (can_address_relative(entity))
1733 dbgi = get_irn_dbg_info(pred);
1734 trampoline = get_trampoline(be, entity);
1735 trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1737 set_irn_n(node, i, trampoline_const);
1741 /* everything else is accessed relative to EIP */
1742 mode = get_irn_mode(pred);
1743 pic_base = get_pic_base(irg);
1745 /* all ok now for locally constructed stuff */
1746 if (can_address_relative(entity)) {
1747 ir_node *add = new_r_Add(block, pic_base, pred, mode);
1749 /* make sure the walker doesn't visit this add again */
1750 mark_irn_visited(add);
1751 set_irn_n(node, i, add);
1755 /* get entry from pic symbol segment */
1756 dbgi = get_irn_dbg_info(pred);
1757 pic_symbol = get_pic_symbol(be, entity);
1758 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1760 add = new_r_Add(block, pic_base, pic_symconst, mode);
1761 mark_irn_visited(add);
1763 /* we need an extra indirection for global data outside our current
1764 module. The loads are always safe and can therefore float
1765 and need no memory input */
1766 load = new_r_Load(block, get_irg_no_mem(irg), add, mode, cons_floats);
1767 load_res = new_r_Proj(load, mode, pn_Load_res);
1769 set_irn_n(node, i, load_res);
1773 void be_abi_introduce(ir_graph *irg)
1775 ir_node *old_frame = get_irg_frame(irg);
1776 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1777 ir_entity *entity = get_irg_entity(irg);
1778 ir_type *method_type = get_entity_type(entity);
1779 be_irg_t *birg = be_birg_from_irg(irg);
1780 struct obstack *obst = &birg->obst;
1781 ir_node *dummy = new_r_Dummy(irg,
1782 arch_env->sp->reg_class->mode);
1785 /* determine allocatable registers */
1786 assert(birg->allocatable_regs == NULL);
1787 birg->allocatable_regs = rbitset_obstack_alloc(obst, arch_env->n_registers);
1788 for (r = 0; r < arch_env->n_registers; ++r) {
1789 const arch_register_t *reg = &arch_env->registers[r];
1790 if ( !(reg->type & arch_register_type_ignore)) {
1791 rbitset_set(birg->allocatable_regs, r);
1795 /* Break here if backend provides a custom API. */
1798 env.keep_map = pmap_create();
1799 env.call = be_abi_call_new();
1800 arch_env_get_call_abi(arch_env, method_type, env.call);
1802 env.init_sp = dummy;
1803 env.calls = NEW_ARR_F(ir_node*, 0);
1807 if (be_options.pic) {
1808 irg_walk_graph(irg, fix_pic_symconsts, NULL, NULL);
1811 /* Lower all call nodes in the IRG. */
1812 process_calls(irg, &env);
1814 /* Process the IRG */
1815 modify_irg(irg, &env);
1817 /* fix call inputs for state registers */
1818 fix_call_state_inputs(irg, &env);
1820 be_abi_call_free(env.call);
1822 /* We don't need the keep map anymore. */
1823 pmap_destroy(env.keep_map);
1825 /* calls array is not needed anymore */
1826 DEL_ARR_F(env.calls);
1828 /* reroute the stack origin of the calls to the true stack origin. */
1829 exchange(dummy, env.init_sp);
1830 exchange(old_frame, get_irg_frame(irg));
1832 pmap_destroy(env.regs);
1835 void be_put_allocatable_regs(const ir_graph *irg,
1836 const arch_register_class_t *cls, bitset_t *bs)
1838 be_irg_t *birg = be_birg_from_irg(irg);
1839 unsigned *allocatable_regs = birg->allocatable_regs;
1842 assert(bitset_size(bs) == cls->n_regs);
1843 bitset_clear_all(bs);
1844 for (i = 0; i < cls->n_regs; ++i) {
1845 const arch_register_t *reg = &cls->regs[i];
1846 if (rbitset_is_set(allocatable_regs, reg->global_index))
1851 unsigned be_get_n_allocatable_regs(const ir_graph *irg,
1852 const arch_register_class_t *cls)
1854 bitset_t *bs = bitset_alloca(cls->n_regs);
1855 be_put_allocatable_regs(irg, cls, bs);
1856 return bitset_popcount(bs);
1859 void be_set_allocatable_regs(const ir_graph *irg,
1860 const arch_register_class_t *cls,
1861 unsigned *raw_bitset)
1863 be_irg_t *birg = be_birg_from_irg(irg);
1864 unsigned *allocatable_regs = birg->allocatable_regs;
1867 rbitset_clear_all(raw_bitset, cls->n_regs);
1868 for (i = 0; i < cls->n_regs; ++i) {
1869 const arch_register_t *reg = &cls->regs[i];
1870 if (rbitset_is_set(allocatable_regs, reg->global_index))
1871 rbitset_set(raw_bitset, i);
1875 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_abi)
1876 void be_init_abi(void)
1878 FIRM_DBG_REGISTER(dbg, "firm.be.abi");