2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Helper functions for handling ABI constraints in the code
24 * @author Matthias Braun
29 #include "beabihelper.h"
36 #include "irphase_t.h"
40 * An entry in the register state map.
42 typedef struct reg_flag_t {
43 const arch_register_t *reg; /**< register at an input position.
44 may be NULL in case of memory input */
45 arch_register_req_type_t flags; /**< requirement flags for this register. */
49 * A register state mapping keeps track of the symbol values (=firm nodes)
50 * to registers. This is useful when constructing straight line code
51 * like the function prolog or epilog in some architectures.
53 typedef struct register_state_mapping_t {
54 ir_node **value_map; /**< mapping of state indices to values */
55 int **reg_index_map; /**< mapping of regclass,regnum to an index
57 reg_flag_t *regs; /**< registers (and memory values) that form a
59 ir_node *last_barrier;
60 } register_state_mapping_t;
63 * The environment for all helper functions.
65 struct beabi_helper_env_t {
66 ir_graph *irg; /**< the graph we operate on */
67 register_state_mapping_t prolog; /**< the register state map for the prolog */
68 register_state_mapping_t epilog; /**< the register state map for the epilog */
69 ir_phase *stack_order; /**< a phase to handle stack dependencies. */
73 * Create a new empty register state map for the given
76 * @param rsm the register state map to be initialized
77 * @param arch_env the architecture environment
79 * After this call, the register map is initialized to empty.
81 static void prepare_rsm(register_state_mapping_t *rsm,
82 const arch_env_t *arch_env)
84 unsigned n_reg_classes = arch_env->n_register_classes;
86 reg_flag_t memory = { NULL, arch_register_req_type_none };
88 rsm->regs = NEW_ARR_F(reg_flag_t, 0);
89 /* memory input at 0 */
90 ARR_APP1(reg_flag_t, rsm->regs, memory);
92 rsm->value_map = NULL;
93 rsm->reg_index_map = XMALLOCN(int*, n_reg_classes);
94 for (c = 0; c < n_reg_classes; ++c) {
95 const arch_register_class_t *cls = &arch_env->register_classes[c];
96 unsigned n_regs = arch_register_class_n_regs(cls);
99 rsm->reg_index_map[c] = XMALLOCN(int, n_regs);
100 for (r = 0; r < n_regs; ++r) {
101 rsm->reg_index_map[c][r] = -1;
107 * Destroy a register state map for the given
110 * @param rsm the register state map to be destroyed
111 * @param arch_env the architecture environment
113 * After this call, the register map is initialized to empty.
115 static void free_rsm(register_state_mapping_t *rsm, const arch_env_t *arch_env)
117 unsigned n_reg_classes = arch_env->n_register_classes;
120 for (c = 0; c < n_reg_classes; ++c) {
121 free(rsm->reg_index_map[c]);
124 free(rsm->reg_index_map);
125 if (rsm->value_map != NULL)
126 DEL_ARR_F(rsm->value_map);
127 DEL_ARR_F(rsm->regs);
130 rsm->reg_index_map = NULL;
131 rsm->value_map = NULL;
135 * Remove all registers from a register state map.
137 * @param rsm the register state map to be destroyed
138 * @param arch_env the architecture environment
140 static void rsm_clear_regs(register_state_mapping_t *rsm,
141 const arch_env_t *arch_env)
143 unsigned n_reg_classes = arch_env->n_register_classes;
145 reg_flag_t memory = { NULL, arch_register_req_type_none };
147 for (c = 0; c < n_reg_classes; ++c) {
148 const arch_register_class_t *cls = &arch_env->register_classes[c];
149 unsigned n_regs = arch_register_class_n_regs(cls);
152 for (r = 0; r < n_regs; ++r) {
153 rsm->reg_index_map[c][r] = -1;
156 ARR_RESIZE(reg_flag_t, rsm->regs, 0);
157 ARR_APP1(reg_flag_t, rsm->regs, memory);
159 if (rsm->value_map != NULL) {
160 DEL_ARR_F(rsm->value_map);
161 rsm->value_map = NULL;
166 * Add a register and its constraint flags to a register state map
167 * and return its index inside the map.
169 static int rsm_add_reg(register_state_mapping_t *rsm,
170 const arch_register_t *reg,
171 arch_register_req_type_t flags)
173 int input_idx = ARR_LEN(rsm->regs);
174 int cls_idx = reg->reg_class->index;
175 int reg_idx = reg->index;
176 reg_flag_t regflag = { reg, flags };
178 /* we must not have used get_value yet */
179 assert(rsm->reg_index_map[cls_idx][reg_idx] == -1);
180 rsm->reg_index_map[cls_idx][reg_idx] = input_idx;
181 ARR_APP1(reg_flag_t, rsm->regs, regflag);
183 if (rsm->value_map != NULL) {
184 ARR_APP1(ir_node*, rsm->value_map, NULL);
185 assert(ARR_LEN(rsm->value_map) == ARR_LEN(rsm->regs));
191 * Retrieve the ir_node stored at the given index in the register state map.
193 static ir_node *rsm_get_value(register_state_mapping_t *rsm, int index)
195 assert(0 <= index && index < ARR_LEN(rsm->value_map));
196 return rsm->value_map[index];
200 * Retrieve the ir_node occupying the given register in the register state map.
202 static ir_node *rsm_get_reg_value(register_state_mapping_t *rsm,
203 const arch_register_t *reg)
205 int cls_idx = reg->reg_class->index;
206 int reg_idx = reg->index;
207 int input_idx = rsm->reg_index_map[cls_idx][reg_idx];
209 return rsm_get_value(rsm, input_idx);
213 * Enter a ir_node at the given index in the register state map.
215 static void rsm_set_value(register_state_mapping_t *rsm, int index,
218 assert(0 <= index && index < ARR_LEN(rsm->value_map));
219 rsm->value_map[index] = value;
223 * Enter a ir_node at the given register in the register state map.
225 static void rsm_set_reg_value(register_state_mapping_t *rsm,
226 const arch_register_t *reg, ir_node *value)
228 int cls_idx = reg->reg_class->index;
229 int reg_idx = reg->index;
230 int input_idx = rsm->reg_index_map[cls_idx][reg_idx];
231 rsm_set_value(rsm, input_idx, value);
235 * Create a Barrier from the registers stored at a register state map.
237 * @param rsm the register state map
238 * @param block the block to create the Barrier on
240 static ir_node *rsm_create_barrier(register_state_mapping_t *rsm,
243 int n_barrier_outs = ARR_LEN(rsm->regs);
244 ir_node **in = rsm->value_map;
248 assert(ARR_LEN(rsm->value_map) == n_barrier_outs);
250 barrier = be_new_Barrier(block, n_barrier_outs, in);
252 for (o = 0; o < n_barrier_outs; ++o) {
253 const reg_flag_t *regflag = &rsm->regs[o];
254 const arch_register_t *reg = regflag->reg;
257 arch_set_out_register_req(barrier, o, arch_no_register_req);
258 proj = new_r_Proj(barrier, mode_M, o);
260 be_set_constr_single_reg_in(barrier, o, reg, arch_register_req_type_none);
261 be_set_constr_single_reg_out(barrier, o, reg, regflag->flags);
262 proj = new_r_Proj(barrier, reg->reg_class->mode, o);
264 rsm->value_map[o] = proj;
267 rsm->last_barrier = barrier;
276 beabi_helper_env_t *be_abihelper_prepare(ir_graph *irg)
278 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
279 beabi_helper_env_t *env = XMALLOCZ(beabi_helper_env_t);
282 prepare_rsm(&env->prolog, arch_env);
283 prepare_rsm(&env->epilog, arch_env);
288 void be_abihelper_finish(beabi_helper_env_t *env)
290 const arch_env_t *arch_env = be_get_irg_arch_env(env->irg);
292 free_rsm(&env->prolog, arch_env);
293 if (env->epilog.reg_index_map != NULL) {
294 free_rsm(&env->epilog, arch_env);
299 void be_prolog_add_reg(beabi_helper_env_t *env, const arch_register_t *reg,
300 arch_register_req_type_t flags)
302 rsm_add_reg(&env->prolog, reg, flags);
305 ir_node *be_prolog_create_start(beabi_helper_env_t *env, dbg_info *dbgi,
308 int n_start_outs = ARR_LEN(env->prolog.regs);
309 ir_node *start = be_new_Start(dbgi, block, n_start_outs);
312 assert(env->prolog.value_map == NULL);
313 env->prolog.value_map = NEW_ARR_F(ir_node*, n_start_outs);
315 for (o = 0; o < n_start_outs; ++o) {
316 const reg_flag_t *regflag = &env->prolog.regs[o];
317 const arch_register_t *reg = regflag->reg;
320 arch_set_out_register_req(start, o, arch_no_register_req);
321 proj = new_r_Proj(start, mode_M, o);
323 be_set_constr_single_reg_out(start, o, regflag->reg,
325 arch_irn_set_register(start, o, regflag->reg);
326 proj = new_r_Proj(start, reg->reg_class->mode, o);
328 env->prolog.value_map[o] = proj;
331 /* start node should really be the first thing constructed */
332 assert(env->prolog.last_barrier == NULL);
333 env->prolog.last_barrier = start;
338 ir_node *be_prolog_create_barrier(beabi_helper_env_t *env, ir_node *block)
340 return rsm_create_barrier(&env->prolog, block);
343 ir_node *be_prolog_get_reg_value(beabi_helper_env_t *env,
344 const arch_register_t *reg)
346 return rsm_get_reg_value(&env->prolog, reg);
349 ir_node *be_prolog_get_memory(beabi_helper_env_t *env)
351 return rsm_get_value(&env->prolog, 0);
354 void be_prolog_set_reg_value(beabi_helper_env_t *env,
355 const arch_register_t *reg, ir_node *value)
357 rsm_set_reg_value(&env->prolog, reg, value);
360 void be_prolog_set_memory(beabi_helper_env_t *env, ir_node *value)
362 rsm_set_value(&env->prolog, 0, value);
367 void be_epilog_begin(beabi_helper_env_t *env)
369 const arch_env_t *arch_env = be_get_irg_arch_env(env->irg);
370 rsm_clear_regs(&env->epilog, arch_env);
371 env->epilog.value_map = NEW_ARR_F(ir_node*, 1);
372 env->epilog.value_map[0] = NULL;
375 void be_epilog_add_reg(beabi_helper_env_t *env, const arch_register_t *reg,
376 arch_register_req_type_t flags, ir_node *value)
378 int index = rsm_add_reg(&env->epilog, reg, flags);
379 rsm_set_value(&env->epilog, index, value);
382 void be_epilog_set_reg_value(beabi_helper_env_t *env,
383 const arch_register_t *reg, ir_node *value)
385 rsm_set_reg_value(&env->epilog, reg, value);
388 void be_epilog_set_memory(beabi_helper_env_t *env, ir_node *value)
390 rsm_set_value(&env->epilog, 0, value);
393 ir_node *be_epilog_get_reg_value(beabi_helper_env_t *env,
394 const arch_register_t *reg)
396 return rsm_get_reg_value(&env->epilog, reg);
399 ir_node *be_epilog_get_memory(beabi_helper_env_t *env)
401 return rsm_get_value(&env->epilog, 0);
404 ir_node *be_epilog_create_barrier(beabi_helper_env_t *env, ir_node *block)
406 return rsm_create_barrier(&env->epilog, block);
409 ir_node *be_epilog_create_return(beabi_helper_env_t *env, dbg_info *dbgi,
412 int n_return_in = ARR_LEN(env->epilog.regs);
413 ir_node **in = env->epilog.value_map;
414 int n_res = 1; /* TODO */
415 unsigned pop = 0; /* TODO */
419 assert(ARR_LEN(env->epilog.value_map) == n_return_in);
421 ret = be_new_Return(dbgi, get_irn_irg(block), block, n_res, pop,
423 for (i = 0; i < n_return_in; ++i) {
424 const reg_flag_t *regflag = &env->epilog.regs[i];
425 const arch_register_t *reg = regflag->reg;
427 be_set_constr_single_reg_in(ret, i, reg,
428 arch_register_req_type_none);
432 rsm_clear_regs(&env->epilog, be_get_irg_arch_env(env->irg));
433 env->epilog.last_barrier = NULL;
438 static void add_missing_keep_walker(ir_node *node, void *data)
441 unsigned *found_projs;
442 const ir_edge_t *edge;
443 ir_mode *mode = get_irn_mode(node);
449 n_outs = arch_irn_get_n_outs(node);
453 rbitset_alloca(found_projs, n_outs);
454 foreach_out_edge(node, edge) {
455 ir_node *succ = get_edge_src_irn(edge);
456 ir_mode *mode = get_irn_mode(succ);
459 /* The node could be kept */
460 if (is_End(succ) || is_Anchor(succ))
463 if (mode == mode_M || mode == mode_X)
466 pn = get_Proj_proj(succ);
468 rbitset_set(found_projs, pn);
472 /* are keeps missing? */
474 for (i = 0; i < n_outs; ++i) {
477 const arch_register_req_t *req;
478 const arch_register_class_t *cls;
480 if (rbitset_is_set(found_projs, i)) {
484 req = arch_get_out_register_req(node, i);
486 if (cls == NULL || (cls->flags & arch_register_class_flag_manual_ra)) {
490 block = get_nodes_block(node);
491 in[0] = new_r_Proj(node, arch_register_class_mode(cls), i);
492 if (last_keep != NULL) {
493 be_Keep_add_node(last_keep, cls, in[0]);
495 last_keep = be_new_Keep(block, 1, in);
496 if (sched_is_scheduled(node)) {
497 sched_add_after(node, last_keep);
503 void be_add_missing_keeps(ir_graph *irg)
505 irg_walk_graph(irg, add_missing_keep_walker, NULL, NULL);
510 * Link the node into its block list as a new head.
512 static void collect_node(ir_node *node)
514 ir_node *block = get_nodes_block(node);
515 ir_node *old = (ir_node*)get_irn_link(block);
517 set_irn_link(node, old);
518 set_irn_link(block, node);
522 * Post-walker: link all nodes that probably access the stack into lists of their block.
524 static void link_ops_in_block_walker(ir_node *node, void *data)
528 switch (get_irn_opcode(node)) {
534 /** all non-stack alloc nodes should be lowered before the backend */
535 assert(get_Alloc_where(node) == stack_alloc);
539 assert(get_Free_where(node) == stack_alloc);
543 if (get_Builtin_kind(node) == ir_bk_return_address) {
544 ir_node *param = get_Builtin_param(node, 0);
545 ir_tarval *tv = get_Const_tarval(param); /* must be Const */
546 long value = get_tarval_long(tv);
548 /* not the return address of the current function:
549 * we need the stack pointer for the frame climbing */
559 static ir_heights_t *heights;
562 * Check if a node is somehow data dependent on another one.
563 * both nodes must be in the same basic block.
564 * @param n1 The first node.
565 * @param n2 The second node.
566 * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
568 static int dependent_on(const ir_node *n1, const ir_node *n2)
570 assert(get_nodes_block(n1) == get_nodes_block(n2));
572 return heights_reachable_in_block(heights, n1, n2);
576 * Classical qsort() comparison function behavior:
578 * 0 if both elements are equal, no node depend on the other
579 * +1 if first depends on second (first is greater)
580 * -1 if second depends on first (second is greater)
582 static int cmp_call_dependency(const void *c1, const void *c2)
584 const ir_node *n1 = *(const ir_node **) c1;
585 const ir_node *n2 = *(const ir_node **) c2;
587 if (dependent_on(n1, n2))
590 if (dependent_on(n2, n1))
593 /* The nodes have no depth order, but we need a total order because qsort()
595 return get_irn_idx(n2) - get_irn_idx(n1);
599 * Block-walker: sorts dependencies and remember them into a phase
601 static void process_ops_in_block(ir_node *block, void *data)
603 ir_phase *phase = (ir_phase*)data;
610 for (node = (ir_node*)get_irn_link(block); node != NULL;
611 node = (ir_node*)get_irn_link(node)) {
618 nodes = XMALLOCN(ir_node*, n_nodes);
620 for (node = (ir_node*)get_irn_link(block); node != NULL;
621 node = (ir_node*)get_irn_link(node)) {
624 assert(n == n_nodes);
626 /* order nodes according to their data dependencies */
627 qsort(nodes, n_nodes, sizeof(nodes[0]), cmp_call_dependency);
629 /* remember the calculated dependency into a phase */
630 for (n = n_nodes-1; n > 0; --n) {
631 ir_node *node = nodes[n];
632 ir_node *pred = nodes[n-1];
634 phase_set_irn_data(phase, node, pred);
639 void be_collect_stacknodes(beabi_helper_env_t *env)
641 ir_graph *irg = env->irg;
643 /* collect all potential^stack accessing nodes */
644 irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, NULL);
646 assert(env->stack_order == NULL);
647 env->stack_order = new_phase(irg, phase_irn_init_default);
649 /* use heights to create a total order for those nodes: this order is stored
650 * in the created phase */
651 heights = heights_new(irg);
652 irg_block_walk_graph(irg, NULL, process_ops_in_block, env->stack_order);
653 heights_free(heights);
656 ir_node *be_get_stack_pred(const beabi_helper_env_t *env, const ir_node *node)
658 return (ir_node*)phase_get_irn_data(env->stack_order, node);