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"
39 typedef struct reg_flag_t {
40 const arch_register_t *reg; /**< register at an input position.
41 may be NULL in case of memory input */
42 arch_irn_flags_t flags;
46 * A register state mapping keeps track of the symbol values (=firm nodes)
47 * to registers. This is usefull when constructing straight line code
48 * which like the function prolog or epilog in some architectures.
50 typedef struct register_state_mapping_t {
51 ir_node **value_map; /**< mapping of state indices to values */
52 int **reg_index_map; /**< mapping of regclass,regnum to an index
54 reg_flag_t *regs; /**< registers (and memory values) that form a
56 ir_node *last_barrier;
57 } register_state_mapping_t;
59 struct beabi_helper_env_t {
61 register_state_mapping_t prolog;
62 register_state_mapping_t epilog;
63 ir_phase *stack_order;
66 static void prepare_rsm(register_state_mapping_t *rsm,
67 const arch_env_t *arch_env)
69 unsigned n_reg_classes = arch_env_get_n_reg_class(arch_env);
71 reg_flag_t memory = { NULL, 0 };
73 rsm->regs = NEW_ARR_F(reg_flag_t, 0);
74 /* memory input at 0 */
75 ARR_APP1(reg_flag_t, rsm->regs, memory);
77 rsm->value_map = NULL;
78 rsm->reg_index_map = XMALLOCN(int*, n_reg_classes);
79 for (c = 0; c < n_reg_classes; ++c) {
80 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, c);
81 unsigned n_regs = arch_register_class_n_regs(cls);
84 rsm->reg_index_map[c] = XMALLOCN(int, n_regs);
85 for (r = 0; r < n_regs; ++r) {
86 rsm->reg_index_map[c][r] = -1;
91 static void free_rsm(register_state_mapping_t *rsm, const arch_env_t *arch_env)
93 unsigned n_reg_classes = arch_env_get_n_reg_class(arch_env);
96 for (c = 0; c < n_reg_classes; ++c) {
97 free(rsm->reg_index_map[c]);
100 free(rsm->reg_index_map);
101 if (rsm->value_map != NULL)
102 DEL_ARR_F(rsm->value_map);
103 DEL_ARR_F(rsm->regs);
106 rsm->reg_index_map = NULL;
107 rsm->value_map = NULL;
110 static void rsm_clear_regs(register_state_mapping_t *rsm,
111 const arch_env_t *arch_env)
113 unsigned n_reg_classes = arch_env_get_n_reg_class(arch_env);
115 reg_flag_t memory = { NULL, 0 };
117 for (c = 0; c < n_reg_classes; ++c) {
118 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, c);
119 unsigned n_regs = arch_register_class_n_regs(cls);
122 for (r = 0; r < n_regs; ++r) {
123 rsm->reg_index_map[c][r] = -1;
126 ARR_RESIZE(reg_flag_t, rsm->regs, 0);
127 ARR_APP1(reg_flag_t, rsm->regs, memory);
129 if (rsm->value_map != NULL) {
130 DEL_ARR_F(rsm->value_map);
131 rsm->value_map = NULL;
135 static void rsm_add_reg(register_state_mapping_t *rsm,
136 const arch_register_t *reg, arch_irn_flags_t flags)
138 int input_idx = ARR_LEN(rsm->regs);
139 int cls_idx = reg->reg_class->index;
140 int reg_idx = reg->index;
141 reg_flag_t regflag = { reg, flags };
143 /* we must not have used get_value yet */
144 assert(rsm->reg_index_map[cls_idx][reg_idx] == -1);
145 rsm->reg_index_map[cls_idx][reg_idx] = input_idx;
146 ARR_APP1(reg_flag_t, rsm->regs, regflag);
150 static ir_node *rsm_get_value(register_state_mapping_t *rsm, int index)
152 assert(0 <= index && index < ARR_LEN(rsm->value_map));
153 return rsm->value_map[index];
156 static ir_node *rsm_get_reg_value(register_state_mapping_t *rsm,
157 const arch_register_t *reg)
159 int cls_idx = reg->reg_class->index;
160 int reg_idx = reg->index;
161 int input_idx = rsm->reg_index_map[cls_idx][reg_idx];
163 return rsm_get_value(rsm, input_idx);
166 static void rsm_set_value(register_state_mapping_t *rsm, int index,
169 assert(0 <= index && index < ARR_LEN(rsm->value_map));
170 rsm->value_map[index] = value;
173 static void rsm_set_reg_value(register_state_mapping_t *rsm,
174 const arch_register_t *reg, ir_node *value)
176 int cls_idx = reg->reg_class->index;
177 int reg_idx = reg->index;
178 int input_idx = rsm->reg_index_map[cls_idx][reg_idx];
179 rsm_set_value(rsm, input_idx, value);
182 static ir_node *rsm_create_barrier(register_state_mapping_t *rsm,
185 int n_barrier_outs = ARR_LEN(rsm->regs);
186 ir_node **in = rsm->value_map;
190 assert(ARR_LEN(rsm->value_map) == n_barrier_outs);
192 barrier = be_new_Barrier(block, n_barrier_outs, in);
194 for (o = 0; o < n_barrier_outs; ++o) {
195 const reg_flag_t *regflag = &rsm->regs[o];
196 const arch_register_t *reg = regflag->reg;
199 arch_set_out_register_req(barrier, o, arch_no_register_req);
200 proj = new_r_Proj(barrier, mode_M, o);
202 be_set_constr_single_reg_in(barrier, o, reg, 0);
203 be_set_constr_single_reg_out(barrier, o, reg, regflag->flags);
204 proj = new_r_Proj(barrier, reg->reg_class->mode, o);
206 rsm->value_map[o] = proj;
209 rsm->last_barrier = barrier;
218 beabi_helper_env_t *be_abihelper_prepare(ir_graph *irg)
220 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
221 beabi_helper_env_t *env = XMALLOCZ(beabi_helper_env_t);
224 prepare_rsm(&env->prolog, arch_env);
225 prepare_rsm(&env->epilog, arch_env);
230 void be_abihelper_finish(beabi_helper_env_t *env)
232 const arch_env_t *arch_env = be_get_irg_arch_env(env->irg);
234 free_rsm(&env->prolog, arch_env);
235 if (env->epilog.reg_index_map != NULL) {
236 free_rsm(&env->epilog, arch_env);
241 void be_prolog_add_reg(beabi_helper_env_t *env, const arch_register_t *reg,
242 arch_irn_flags_t flags)
244 rsm_add_reg(&env->prolog, reg, flags);
247 ir_node *be_prolog_create_start(beabi_helper_env_t *env, dbg_info *dbgi,
250 int n_start_outs = ARR_LEN(env->prolog.regs);
251 ir_node *start = be_new_Start(dbgi, block, n_start_outs);
254 assert(env->prolog.value_map == NULL);
255 env->prolog.value_map = NEW_ARR_F(ir_node*, n_start_outs);
257 for (o = 0; o < n_start_outs; ++o) {
258 const reg_flag_t *regflag = &env->prolog.regs[o];
259 const arch_register_t *reg = regflag->reg;
262 arch_set_out_register_req(start, o, arch_no_register_req);
263 proj = new_r_Proj(start, mode_M, o);
265 be_set_constr_single_reg_out(start, o, regflag->reg,
267 arch_irn_set_register(start, o, regflag->reg);
268 proj = new_r_Proj(start, reg->reg_class->mode, o);
270 env->prolog.value_map[o] = proj;
273 /* start node should really be the first thing constructed */
274 assert(env->prolog.last_barrier == NULL);
275 env->prolog.last_barrier = start;
280 ir_node *be_prolog_create_barrier(beabi_helper_env_t *env, ir_node *block)
282 return rsm_create_barrier(&env->prolog, block);
285 ir_node *be_prolog_get_reg_value(beabi_helper_env_t *env,
286 const arch_register_t *reg)
288 return rsm_get_reg_value(&env->prolog, reg);
291 ir_node *be_prolog_get_memory(beabi_helper_env_t *env)
293 return rsm_get_value(&env->prolog, 0);
296 void be_prolog_set_reg_value(beabi_helper_env_t *env,
297 const arch_register_t *reg, ir_node *value)
299 rsm_set_reg_value(&env->prolog, reg, value);
302 void be_prolog_set_memory(beabi_helper_env_t *env, ir_node *value)
304 rsm_set_value(&env->prolog, 0, value);
309 void be_epilog_begin(beabi_helper_env_t *env)
311 const arch_env_t *arch_env = be_get_irg_arch_env(env->irg);
312 rsm_clear_regs(&env->epilog, arch_env);
313 env->epilog.value_map = NEW_ARR_F(ir_node*, 1);
314 env->epilog.value_map[0] = NULL;
317 void be_epilog_add_reg(beabi_helper_env_t *env, const arch_register_t *reg,
318 arch_irn_flags_t flags, ir_node *value)
320 rsm_add_reg(&env->epilog, reg, flags);
321 ARR_APP1(ir_node*, env->epilog.value_map, value);
324 void be_epilog_set_reg_value(beabi_helper_env_t *env,
325 const arch_register_t *reg, ir_node *value)
327 rsm_set_reg_value(&env->epilog, reg, value);
330 void be_epilog_set_memory(beabi_helper_env_t *env, ir_node *value)
332 rsm_set_value(&env->epilog, 0, value);
335 ir_node *be_epilog_get_reg_value(beabi_helper_env_t *env,
336 const arch_register_t *reg)
338 return rsm_get_reg_value(&env->epilog, reg);
341 ir_node *be_epilog_get_memory(beabi_helper_env_t *env)
343 return rsm_get_value(&env->epilog, 0);
346 ir_node *be_epilog_create_barrier(beabi_helper_env_t *env, ir_node *block)
348 return rsm_create_barrier(&env->epilog, block);
351 ir_node *be_epilog_create_return(beabi_helper_env_t *env, dbg_info *dbgi,
354 int n_return_in = ARR_LEN(env->epilog.regs);
355 ir_node **in = env->epilog.value_map;
356 int n_res = 1; /* TODO */
357 unsigned pop = 0; /* TODO */
361 assert(ARR_LEN(env->epilog.value_map) == n_return_in);
363 ret = be_new_Return(dbgi, get_irn_irg(block), block, n_res, pop,
365 for (i = 0; i < n_return_in; ++i) {
366 const reg_flag_t *regflag = &env->epilog.regs[i];
367 const arch_register_t *reg = regflag->reg;
369 be_set_constr_single_reg_in(ret, i, reg, 0);
373 rsm_clear_regs(&env->epilog, be_get_irg_arch_env(env->irg));
374 env->epilog.last_barrier = NULL;
379 static void add_missing_keep_walker(ir_node *node, void *data)
382 unsigned found_projs = 0;
383 const ir_edge_t *edge;
384 ir_mode *mode = get_irn_mode(node);
390 n_outs = arch_irn_get_n_outs(node);
394 assert(n_outs < (int) sizeof(unsigned) * 8);
395 foreach_out_edge(node, edge) {
396 ir_node *succ = get_edge_src_irn(edge);
399 /* The node could be kept */
400 if (is_End(succ) || is_Anchor(succ))
403 if (get_irn_mode(succ) == mode_M)
406 pn = get_Proj_proj(succ);
408 found_projs |= 1 << pn;
412 /* are keeps missing? */
414 for (i = 0; i < n_outs; ++i) {
417 const arch_register_req_t *req;
418 const arch_register_class_t *cls;
420 if (found_projs & (1 << i)) {
424 req = arch_get_out_register_req(node, i);
426 if (cls == NULL || (cls->flags & arch_register_class_flag_manual_ra)) {
430 block = get_nodes_block(node);
431 in[0] = new_r_Proj(node, arch_register_class_mode(cls), i);
432 if (last_keep != NULL) {
433 be_Keep_add_node(last_keep, cls, in[0]);
435 last_keep = be_new_Keep(block, 1, in);
436 if (sched_is_scheduled(node)) {
437 sched_add_after(node, last_keep);
443 void be_add_missing_keeps(ir_graph *irg)
445 irg_walk_graph(irg, add_missing_keep_walker, NULL, NULL);
450 static void collect_node(ir_node *node)
452 ir_node *block = get_nodes_block(node);
453 ir_node *old = get_irn_link(block);
455 set_irn_link(node, old);
456 set_irn_link(block, node);
459 static void link_ops_in_block_walker(ir_node *node, void *data)
463 switch (get_irn_opcode(node)) {
469 /** all non-stack alloc nodes should be lowered before the backend */
470 assert(get_Alloc_where(node) == stack_alloc);
474 assert(get_Free_where(node) == stack_alloc);
478 if (get_Builtin_kind(node) == ir_bk_return_address) {
479 ir_node *param = get_Builtin_param(node, 0);
480 tarval *tv = get_Const_tarval(param); /* must be Const */
481 long value = get_tarval_long(tv);
483 /* we need esp for the climbframe algo */
493 static heights_t *heights;
496 * Check if a node is somehow data dependent on another one.
497 * both nodes must be in the same basic block.
498 * @param n1 The first node.
499 * @param n2 The second node.
500 * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
502 static int dependent_on(const ir_node *n1, const ir_node *n2)
504 assert(get_nodes_block(n1) == get_nodes_block(n2));
506 return heights_reachable_in_block(heights, n1, n2);
509 static int cmp_call_dependency(const void *c1, const void *c2)
511 const ir_node *n1 = *(const ir_node **) c1;
512 const ir_node *n2 = *(const ir_node **) c2;
515 Classical qsort() comparison function behavior:
516 0 if both elements are equal
517 1 if second is "smaller" that first
518 -1 if first is "smaller" that second
520 if (dependent_on(n1, n2))
523 if (dependent_on(n2, n1))
526 /* The nodes have no depth order, but we need a total order because qsort()
528 return get_irn_idx(n2) - get_irn_idx(n1);
531 static void process_ops_in_block(ir_node *block, void *data)
533 ir_phase *phase = data;
540 for (node = get_irn_link(block); node != NULL; node = get_irn_link(node)) {
547 nodes = XMALLOCN(ir_node*, n_nodes);
549 for (node = get_irn_link(block); node != NULL; node = get_irn_link(node)) {
552 assert(n == n_nodes);
554 /* order nodes according to their data dependencies */
555 qsort(nodes, n_nodes, sizeof(nodes[0]), cmp_call_dependency);
557 for (n = n_nodes-1; n > 0; --n) {
558 ir_node *node = nodes[n];
559 ir_node *pred = nodes[n-1];
561 phase_set_irn_data(phase, node, pred);
565 void be_collect_stacknodes(beabi_helper_env_t *env)
567 ir_graph *irg = env->irg;
568 irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, NULL);
570 assert(env->stack_order == NULL);
571 env->stack_order = new_phase(irg, phase_irn_init_default);
573 heights = heights_new(irg);
574 irg_block_walk_graph(irg, NULL, process_ops_in_block, env->stack_order);
575 heights_free(heights);
578 ir_node *be_get_stack_pred(const beabi_helper_env_t *env, const ir_node *node)
580 return phase_get_irn_data(env->stack_order, node);