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);
1198 const arch_register_t **regs;
1202 get the valid stack node in this block.
1203 If we had a call in that block there is a Keep constructed by process_calls()
1204 which points to the last stack modification in that block. we'll use
1205 it then. Else we use the stack from the start block and let
1206 the ssa construction fix the usage.
1208 stack = be_abi_reg_map_get(env->regs, arch_env->sp);
1210 stack = get_irn_n(keep, 0);
1212 remove_End_keepalive(get_irg_end(irg), keep);
1215 int const n_res = get_Return_n_ress(irn);
1216 /* Insert results for Return into the register map. */
1217 for (i = 0; i < n_res; ++i) {
1218 ir_node *res = get_Return_res(irn, i);
1219 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1220 assert(arg->in_reg && "return value must be passed in register");
1221 pmap_insert(reg_map, (void *) arg->reg, res);
1224 /* Add uses of the callee save registers. */
1225 foreach_pmap(env->regs, ent) {
1226 const arch_register_t *reg = (const arch_register_t*)ent->key;
1227 if ((reg->type & arch_register_type_ignore) || arch_register_is_callee_save(arch_env, reg))
1228 pmap_insert(reg_map, ent->key, ent->value);
1231 be_abi_reg_map_set(reg_map, arch_env->sp, stack);
1234 Maximum size of the in array for Return nodes is
1235 return args + callee save/ignore registers + memory + stack pointer
1237 in_max = pmap_count(reg_map) + n_res + 2;
1239 in = ALLOCAN(ir_node*, in_max);
1240 regs = ALLOCAN(arch_register_t const*, in_max);
1242 in[0] = get_Return_mem(irn);
1243 in[1] = be_abi_reg_map_get(reg_map, arch_env->sp);
1245 regs[1] = arch_env->sp;
1248 /* clear SP entry, since it has already been grown. */
1249 pmap_insert(reg_map, (void *) arch_env->sp, NULL);
1250 for (i = 0; i < n_res; ++i) {
1251 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1253 in[n] = be_abi_reg_map_get(reg_map, arg->reg);
1254 regs[n++] = arg->reg;
1256 /* Clear the map entry to mark the register as processed. */
1257 be_abi_reg_map_set(reg_map, arg->reg, NULL);
1260 /* grow the rest of the stuff. */
1261 foreach_pmap(reg_map, ent) {
1263 in[n] = (ir_node*)ent->value;
1264 regs[n++] = (const arch_register_t*)ent->key;
1268 /* The in array for the new back end return is now ready. */
1269 dbg_info *const dbgi = get_irn_dbg_info(irn);
1270 /* we have to pop the shadow parameter in in case of struct returns */
1272 ret = be_new_Return(dbgi, irg, bl, n_res, pop, n, in);
1274 /* Set the register classes of the return's parameter accordingly. */
1275 for (i = 0; i < n; ++i) {
1276 if (regs[i] == NULL)
1279 be_set_constr_single_reg_in(ret, i, regs[i], arch_register_req_type_none);
1282 /* Free the space of the Epilog's in array and the register <-> proj map. */
1283 pmap_destroy(reg_map);
1288 typedef struct lower_frame_sels_env_t {
1289 ir_node *frame; /**< the current frame */
1290 const arch_register_class_t *sp_class; /**< register class of the stack pointer */
1291 } lower_frame_sels_env_t;
1294 * Walker: Replaces Sels of frame type and
1295 * value param type entities by FrameAddress.
1296 * Links all used entities.
1298 static void lower_frame_sels_walker(ir_node *irn, void *data)
1300 lower_frame_sels_env_t *ctx = (lower_frame_sels_env_t*)data;
1303 ir_node *ptr = get_Sel_ptr(irn);
1305 if (ptr == ctx->frame) {
1306 ir_entity *ent = get_Sel_entity(irn);
1307 ir_node *bl = get_nodes_block(irn);
1310 nw = be_new_FrameAddr(ctx->sp_class, bl, ctx->frame, ent);
1317 * The start block has no jump, instead it has an initial exec Proj.
1318 * The backend wants to handle all blocks the same way, so we replace
1319 * the out cfg edge with a real jump.
1321 static void fix_start_block(ir_graph *irg)
1323 ir_node *initial_X = get_irg_initial_exec(irg);
1324 ir_node *start_block = get_irg_start_block(irg);
1325 ir_node *jmp = new_r_Jmp(start_block);
1327 assert(is_Proj(initial_X));
1328 exchange(initial_X, jmp);
1329 set_irg_initial_exec(irg, new_r_Bad(irg, mode_X));
1331 /* merge start block with successor if possible */
1333 foreach_out_edge(jmp, edge) {
1334 ir_node *succ = get_edge_src_irn(edge);
1335 if (!is_Block(succ))
1338 if (get_irn_arity(succ) == 1) {
1339 exchange(succ, start_block);
1347 * Modify the irg itself and the frame type.
1349 static void modify_irg(ir_graph *const irg, be_abi_irg_t *const env)
1351 be_abi_call_t *call = env->call;
1352 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1353 const arch_register_t *sp = arch_env->sp;
1354 ir_type *method_type = get_entity_type(get_irg_entity(irg));
1355 be_irg_t *birg = be_birg_from_irg(irg);
1356 struct obstack *obst = be_get_be_obst(irg);
1357 be_stack_layout_t *stack_layout = be_get_irg_stack_layout(irg);
1360 ir_node *new_mem_proj;
1368 const arch_register_t *fp_reg;
1369 ir_node *frame_pointer;
1373 ir_type *arg_type, *bet_type;
1374 lower_frame_sels_env_t ctx;
1376 DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1378 old_mem = get_irg_initial_mem(irg);
1380 irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1382 arg_type = compute_arg_type(irg, call, method_type);
1384 /* Convert the Sel nodes in the irg to frame addr nodes: */
1385 ctx.frame = get_irg_frame(irg);
1386 ctx.sp_class = arch_env->sp->reg_class;
1388 ir_type *const frame_tp = get_irg_frame_type(irg);
1389 /* layout the stackframe now */
1390 if (get_type_state(frame_tp) == layout_undefined) {
1391 default_layout_compound_type(frame_tp);
1394 /* align stackframe */
1395 unsigned const alignment = 1U << arch_env->stack_alignment;
1396 unsigned const frame_size = round_up2(get_type_size_bytes(frame_tp), alignment);
1397 set_type_size_bytes(frame_tp, frame_size);
1399 env->regs = pmap_create();
1401 n_params = get_method_n_params(method_type);
1402 args = OALLOCNZ(obst, ir_node*, n_params);
1404 be_add_parameter_entity_stores(irg);
1406 irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1408 irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1410 /* Fill the argument vector */
1411 arg_tuple = get_irg_args(irg);
1412 foreach_out_edge(arg_tuple, edge) {
1413 ir_node *irn = get_edge_src_irn(edge);
1414 if (! is_Anchor(irn)) {
1415 int nr = get_Proj_proj(irn);
1417 DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1421 stack_layout->sp_relative = call->flags.try_omit_fp;
1422 bet_type = call->cb->get_between_type(irg);
1423 stack_frame_init(stack_layout, arg_type, bet_type,
1424 get_irg_frame_type(irg));
1426 /* Count the register params and add them to the number of Projs for the RegParams node */
1427 for (i = 0; i < n_params; ++i) {
1428 be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 1);
1429 if (arg->in_reg && args[i]) {
1430 assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1431 assert(i == get_Proj_proj(args[i]));
1433 /* For now, associate the register with the old Proj from Start representing that argument. */
1434 pmap_insert(env->regs, (void *) arg->reg, args[i]);
1435 DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1439 /* Collect all callee-save registers */
1440 for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
1441 const arch_register_class_t *cls = &arch_env->register_classes[i];
1442 for (j = 0; j < cls->n_regs; ++j) {
1443 const arch_register_t *reg = &cls->regs[j];
1444 if ((reg->type & arch_register_type_state) || arch_register_is_callee_save(arch_env, reg)) {
1445 pmap_insert(env->regs, (void *) reg, NULL);
1450 fp_reg = call->flags.try_omit_fp ? arch_env->sp : arch_env->bp;
1451 rbitset_clear(birg->allocatable_regs, fp_reg->global_index);
1453 /* handle start block here (place a jump in the block) */
1454 fix_start_block(irg);
1456 pmap_insert(env->regs, (void *) sp, NULL);
1457 pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1458 start_bl = get_irg_start_block(irg);
1459 ir_node *const start = be_new_Start(NULL, start_bl, pmap_count(env->regs) + 1);
1460 set_irg_start(irg, start);
1463 * make proj nodes for the callee save registers.
1464 * memorize them, since Return nodes get those as inputs.
1466 * Note, that if a register corresponds to an argument, the regs map
1467 * contains the old Proj from start for that argument.
1469 rm = ALLOCAN(reg_node_map_t, pmap_count(env->regs));
1470 reg_map_to_arr(rm, env->regs);
1471 for (i = 0, n = pmap_count(env->regs); i < n; ++i) {
1472 const arch_register_t *reg = rm[i].reg;
1473 ir_mode *mode = reg->reg_class->mode;
1475 arch_register_req_type_t add_type = arch_register_req_type_none;
1479 add_type |= arch_register_req_type_produces_sp;
1480 if (!rbitset_is_set(birg->allocatable_regs, reg->global_index)) {
1481 add_type |= arch_register_req_type_ignore;
1485 proj = new_r_Proj(start, mode, nr + 1);
1486 pmap_insert(env->regs, (void *) reg, proj);
1487 be_set_constr_single_reg_out(start, nr + 1, reg, add_type);
1488 arch_set_irn_register(proj, reg);
1490 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1493 /* create a new initial memory proj */
1494 assert(is_Proj(old_mem));
1495 arch_set_irn_register_req_out(start, 0, arch_no_register_req);
1496 new_mem_proj = new_r_Proj(start, mode_M, 0);
1498 set_irg_initial_mem(irg, mem);
1500 env->init_sp = be_abi_reg_map_get(env->regs, sp);
1502 /* set new frame_pointer */
1503 frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
1504 set_irg_frame(irg, frame_pointer);
1506 /* rewire old mem users to new mem */
1507 exchange(old_mem, mem);
1509 /* keep the mem (for functions with an endless loop = no return) */
1512 set_irg_initial_mem(irg, mem);
1514 /* Now, introduce stack param nodes for all parameters passed on the stack */
1515 for (i = 0; i < n_params; ++i) {
1516 ir_node *arg_proj = args[i];
1517 ir_node *repl = NULL;
1519 if (arg_proj != NULL) {
1520 be_abi_call_arg_t *arg;
1521 ir_type *param_type;
1522 int nr = get_Proj_proj(arg_proj);
1525 nr = MIN(nr, n_params);
1526 arg = get_call_arg(call, 0, nr, 1);
1527 param_type = get_method_param_type(method_type, nr);
1530 repl = pmap_get(ir_node, env->regs, arg->reg);
1532 ir_node *addr = be_new_FrameAddr(sp->reg_class, start_bl, frame_pointer, arg->stack_ent);
1534 /* For atomic parameters which are actually used, we create a Load node. */
1535 if (is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
1536 ir_mode *mode = get_type_mode(param_type);
1537 ir_mode *load_mode = arg->load_mode;
1538 ir_node *nomem = get_irg_no_mem(irg);
1540 ir_node *load = new_r_Load(start_bl, nomem, addr, load_mode, cons_floats);
1541 repl = new_r_Proj(load, load_mode, pn_Load_res);
1543 if (mode != load_mode) {
1544 repl = new_r_Conv(start_bl, repl, mode);
1547 /* The stack parameter is not primitive (it is a struct or array),
1548 * we thus will create a node representing the parameter's address
1554 assert(repl != NULL);
1556 /* Beware: the mode of the register parameters is always the mode of the register class
1557 which may be wrong. Add Conv's then. */
1558 mode = get_irn_mode(args[i]);
1559 if (mode != get_irn_mode(repl)) {
1560 repl = new_r_Conv(get_nodes_block(repl), repl, mode);
1562 exchange(args[i], repl);
1566 /* the arg proj is not needed anymore now and should be only used by the anchor */
1567 assert(get_irn_n_edges(arg_tuple) == 1);
1568 kill_node(arg_tuple);
1569 set_irg_args(irg, new_r_Bad(irg, mode_T));
1571 /* All Return nodes hang on the End node, so look for them there. */
1572 end = get_irg_end_block(irg);
1573 for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
1574 ir_node *irn = get_Block_cfgpred(end, i);
1576 if (is_Return(irn)) {
1577 ir_node *const ret = create_be_return(env, irn);
1582 /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
1583 the code is dead and will never be executed. */
1586 /** Fix the state inputs of calls that still hang on unknowns */
1587 static void fix_call_state_inputs(ir_graph *const irg, be_abi_irg_t *const env)
1589 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1591 arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
1593 /* Collect caller save registers */
1594 n = arch_env->n_register_classes;
1595 for (i = 0; i < n; ++i) {
1597 const arch_register_class_t *cls = &arch_env->register_classes[i];
1598 for (j = 0; j < cls->n_regs; ++j) {
1599 const arch_register_t *reg = arch_register_for_index(cls, j);
1600 if (reg->type & arch_register_type_state) {
1601 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
1606 n = ARR_LEN(env->calls);
1607 n_states = ARR_LEN(stateregs);
1608 for (i = 0; i < n; ++i) {
1610 ir_node *call = env->calls[i];
1612 arity = get_irn_arity(call);
1614 /* the state reg inputs are the last n inputs of the calls */
1615 for (s = 0; s < n_states; ++s) {
1616 int inp = arity - n_states + s;
1617 const arch_register_t *reg = stateregs[s];
1618 ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
1620 set_irn_n(call, inp, regnode);
1624 DEL_ARR_F(stateregs);
1628 * Create a trampoline entity for the given method.
1630 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
1632 ir_type *type = get_entity_type(method);
1633 ident *old_id = get_entity_ld_ident(method);
1634 ident *id = id_mangle3("", old_id, "$stub");
1635 ir_type *parent = be->pic_trampolines_type;
1636 ir_entity *ent = new_entity(parent, old_id, type);
1637 set_entity_ld_ident(ent, id);
1638 set_entity_visibility(ent, ir_visibility_private);
1644 * Returns the trampoline entity for the given method.
1646 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
1648 ir_entity *result = pmap_get(ir_entity, env->ent_trampoline_map, method);
1649 if (result == NULL) {
1650 result = create_trampoline(env, method);
1651 pmap_insert(env->ent_trampoline_map, method, result);
1657 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
1659 ident *old_id = get_entity_ld_ident(entity);
1660 ident *id = id_mangle3("", old_id, "$non_lazy_ptr");
1661 ir_type *e_type = get_entity_type(entity);
1662 ir_type *type = new_type_pointer(e_type);
1663 ir_type *parent = be->pic_symbols_type;
1664 ir_entity *ent = new_entity(parent, old_id, type);
1665 set_entity_ld_ident(ent, id);
1666 set_entity_visibility(ent, ir_visibility_private);
1671 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
1673 ir_entity *result = pmap_get(ir_entity, env->ent_pic_symbol_map, entity);
1674 if (result == NULL) {
1675 result = create_pic_symbol(env, entity);
1676 pmap_insert(env->ent_pic_symbol_map, entity, result);
1685 * Returns non-zero if a given entity can be accessed using a relative address.
1687 static int can_address_relative(ir_entity *entity)
1689 return entity_has_definition(entity) && !(get_entity_linkage(entity) & IR_LINKAGE_MERGE);
1692 static ir_node *get_pic_base(ir_graph *irg)
1694 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1695 if (arch_env->impl->get_pic_base == NULL)
1697 return arch_env->impl->get_pic_base(irg);
1700 /** patches SymConsts to work in position independent code */
1701 static void fix_pic_symconsts(ir_node *node, void *data)
1703 ir_graph *irg = get_irn_irg(node);
1704 be_main_env_t *be = be_get_irg_main_env(irg);
1714 arity = get_irn_arity(node);
1715 for (i = 0; i < arity; ++i) {
1717 ir_node *pred = get_irn_n(node, i);
1719 ir_entity *pic_symbol;
1720 ir_node *pic_symconst;
1722 if (!is_SymConst(pred))
1725 entity = get_SymConst_entity(pred);
1726 block = get_nodes_block(pred);
1728 /* calls can jump to relative addresses, so we can directly jump to
1729 the (relatively) known call address or the trampoline */
1730 if (i == 1 && is_Call(node)) {
1731 ir_entity *trampoline;
1732 ir_node *trampoline_const;
1734 if (can_address_relative(entity))
1737 dbgi = get_irn_dbg_info(pred);
1738 trampoline = get_trampoline(be, entity);
1739 trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1741 set_irn_n(node, i, trampoline_const);
1745 /* everything else is accessed relative to EIP */
1746 mode = get_irn_mode(pred);
1747 pic_base = get_pic_base(irg);
1749 /* all ok now for locally constructed stuff */
1750 if (can_address_relative(entity)) {
1751 ir_node *add = new_r_Add(block, pic_base, pred, mode);
1753 /* make sure the walker doesn't visit this add again */
1754 mark_irn_visited(add);
1755 set_irn_n(node, i, add);
1759 /* get entry from pic symbol segment */
1760 dbgi = get_irn_dbg_info(pred);
1761 pic_symbol = get_pic_symbol(be, entity);
1762 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1764 add = new_r_Add(block, pic_base, pic_symconst, mode);
1765 mark_irn_visited(add);
1767 /* we need an extra indirection for global data outside our current
1768 module. The loads are always safe and can therefore float
1769 and need no memory input */
1770 load = new_r_Load(block, get_irg_no_mem(irg), add, mode, cons_floats);
1771 load_res = new_r_Proj(load, mode, pn_Load_res);
1773 set_irn_n(node, i, load_res);
1777 void be_abi_introduce(ir_graph *irg)
1779 ir_node *old_frame = get_irg_frame(irg);
1780 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1781 ir_entity *entity = get_irg_entity(irg);
1782 ir_type *method_type = get_entity_type(entity);
1783 be_irg_t *birg = be_birg_from_irg(irg);
1784 struct obstack *obst = &birg->obst;
1785 ir_node *dummy = new_r_Dummy(irg,
1786 arch_env->sp->reg_class->mode);
1789 /* determine allocatable registers */
1790 assert(birg->allocatable_regs == NULL);
1791 birg->allocatable_regs = rbitset_obstack_alloc(obst, arch_env->n_registers);
1792 for (r = 0; r < arch_env->n_registers; ++r) {
1793 const arch_register_t *reg = &arch_env->registers[r];
1794 if ( !(reg->type & arch_register_type_ignore)) {
1795 rbitset_set(birg->allocatable_regs, r);
1799 /* Break here if backend provides a custom API. */
1802 env.keep_map = pmap_create();
1803 env.call = be_abi_call_new();
1804 arch_env_get_call_abi(arch_env, method_type, env.call);
1806 env.init_sp = dummy;
1807 env.calls = NEW_ARR_F(ir_node*, 0);
1811 if (be_options.pic) {
1812 irg_walk_graph(irg, fix_pic_symconsts, NULL, NULL);
1815 /* Lower all call nodes in the IRG. */
1816 process_calls(irg, &env);
1818 /* Process the IRG */
1819 modify_irg(irg, &env);
1821 /* fix call inputs for state registers */
1822 fix_call_state_inputs(irg, &env);
1824 be_abi_call_free(env.call);
1826 /* We don't need the keep map anymore. */
1827 pmap_destroy(env.keep_map);
1829 /* calls array is not needed anymore */
1830 DEL_ARR_F(env.calls);
1832 /* reroute the stack origin of the calls to the true stack origin. */
1833 exchange(dummy, env.init_sp);
1834 exchange(old_frame, get_irg_frame(irg));
1836 pmap_destroy(env.regs);
1839 void be_put_allocatable_regs(const ir_graph *irg,
1840 const arch_register_class_t *cls, bitset_t *bs)
1842 be_irg_t *birg = be_birg_from_irg(irg);
1843 unsigned *allocatable_regs = birg->allocatable_regs;
1846 assert(bitset_size(bs) == cls->n_regs);
1847 bitset_clear_all(bs);
1848 for (i = 0; i < cls->n_regs; ++i) {
1849 const arch_register_t *reg = &cls->regs[i];
1850 if (rbitset_is_set(allocatable_regs, reg->global_index))
1855 unsigned be_get_n_allocatable_regs(const ir_graph *irg,
1856 const arch_register_class_t *cls)
1858 bitset_t *bs = bitset_alloca(cls->n_regs);
1859 be_put_allocatable_regs(irg, cls, bs);
1860 return bitset_popcount(bs);
1863 void be_set_allocatable_regs(const ir_graph *irg,
1864 const arch_register_class_t *cls,
1865 unsigned *raw_bitset)
1867 be_irg_t *birg = be_birg_from_irg(irg);
1868 unsigned *allocatable_regs = birg->allocatable_regs;
1871 rbitset_clear_all(raw_bitset, cls->n_regs);
1872 for (i = 0; i < cls->n_regs; ++i) {
1873 const arch_register_t *reg = &cls->regs[i];
1874 if (rbitset_is_set(allocatable_regs, reg->global_index))
1875 rbitset_set(raw_bitset, i);
1879 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_abi)
1880 void be_init_abi(void)
1882 FIRM_DBG_REGISTER(dbg, "firm.be.abi");