2 * Copyright (C) 1995-2010 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 Peephole optimization and legalization of a sparc function
23 * @author Matthias Braun
26 * A note on sparc stackpointer (sp) behaviour:
27 * The ABI expects SPARC_MIN_STACKSIZE bytes to be available at the
28 * stackpointer. This space will be used to spill register windows,
29 * and for spilling va_arg arguments (maybe we can optimize this away for
30 * statically known not-va-arg-functions...)
31 * This in effect means that we allocate that extra space at the function begin
32 * which is easy. But this space isn't really fixed at the beginning of the
33 * stackframe. Instead you should rather imagine the space as always being the
34 * last-thing on the stack.
35 * So when addressing anything stack-specific we have to account for this
36 * area, while our compiler thinks the space is occupied at the beginning
37 * of the stack frame. The code here among other things adjusts these offsets
42 #include "bearch_sparc_t.h"
43 #include "gen_sparc_regalloc_if.h"
44 #include "sparc_new_nodes.h"
50 #include "../bepeephole.h"
51 #include "../benode.h"
52 #include "../besched.h"
53 #include "../bespillslots.h"
54 #include "../bestack.h"
55 #include "../beirgmod.h"
57 static void kill_unused_stacknodes(ir_node *node)
59 if (get_irn_n_edges(node) > 0)
62 if (be_is_IncSP(node)) {
65 } else if (is_Phi(node)) {
66 int arity = get_irn_arity(node);
67 ir_node **ins = ALLOCAN(ir_node*, arity);
70 memcpy(ins, get_irn_in(node), arity*sizeof(ins[0]));
73 for (i = 0; i < arity; ++i)
74 kill_unused_stacknodes(ins[i]);
78 static void introduce_epilog(ir_node *ret)
80 const arch_register_t *sp_reg = &sparc_registers[REG_SP];
81 ir_graph *irg = get_irn_irg(ret);
82 be_stack_layout_t *layout = be_get_irg_stack_layout(irg);
83 ir_node *block = get_nodes_block(ret);
84 ir_type *frame_type = get_irg_frame_type(irg);
85 unsigned frame_size = get_type_size_bytes(frame_type);
86 int sp_idx = be_find_return_reg_input(ret, sp_reg);
87 ir_node *sp = get_irn_n(ret, sp_idx);
89 if (!layout->sp_relative) {
90 const arch_register_t *fp_reg = &sparc_registers[REG_FRAME_POINTER];
91 ir_node *fp = be_get_initial_reg_value(irg, fp_reg);
92 ir_node *restore = new_bd_sparc_RestoreZero(NULL, block, fp);
93 sched_add_before(ret, restore);
94 arch_set_irn_register(restore, sp_reg);
95 set_irn_n(ret, sp_idx, restore);
97 kill_unused_stacknodes(sp);
99 ir_node *incsp = be_new_IncSP(sp_reg, block, sp, -frame_size, 0);
100 set_irn_n(ret, sp_idx, incsp);
101 sched_add_before(ret, incsp);
105 void sparc_introduce_prolog_epilog(ir_graph *irg)
107 const arch_register_t *sp_reg = &sparc_registers[REG_SP];
108 ir_node *start = get_irg_start(irg);
109 be_stack_layout_t *layout = be_get_irg_stack_layout(irg);
110 ir_node *block = get_nodes_block(start);
111 ir_node *initial_sp = be_get_initial_reg_value(irg, sp_reg);
112 ir_node *sp = initial_sp;
113 ir_node *schedpoint = start;
114 ir_type *frame_type = get_irg_frame_type(irg);
115 unsigned frame_size = get_type_size_bytes(frame_type);
117 /* introduce epilog for every return node */
119 ir_node *end_block = get_irg_end_block(irg);
120 int arity = get_irn_arity(end_block);
123 for (i = 0; i < arity; ++i) {
124 ir_node *ret = get_irn_n(end_block, i);
125 assert(is_sparc_Return(ret));
126 introduce_epilog(ret);
130 while (be_is_Keep(sched_next(schedpoint)))
131 schedpoint = sched_next(schedpoint);
133 if (!layout->sp_relative) {
135 ir_node *save = new_bd_sparc_Save_imm(NULL, block, sp, NULL,
136 -SPARC_MIN_STACKSIZE);
137 arch_set_irn_register(save, sp_reg);
138 sched_add_after(schedpoint, save);
141 incsp = be_new_IncSP(sp_reg, block, save, frame_size, 0);
142 edges_reroute(initial_sp, incsp);
143 set_irn_n(save, n_sparc_Save_stack, initial_sp);
144 sched_add_after(schedpoint, incsp);
147 /* we still need the IncSP even if noone is explicitely using the
148 * value. (TODO: this isn't 100% correct yet, something at the end of
149 * the function should hold the IncSP, even if we use a restore
150 * which just overrides it instead of using the value)
152 if (get_irn_n_edges(incsp) == 0) {
153 ir_node *in[] = { incsp };
154 ir_node *keep = be_new_Keep(block, 1, in);
155 sched_add_after(schedpoint, keep);
158 ir_node *incsp = be_new_IncSP(sp_reg, block, sp, frame_size, 0);
159 edges_reroute(initial_sp, incsp);
160 be_set_IncSP_pred(incsp, sp);
161 sched_add_after(schedpoint, incsp);
165 static void finish_sparc_Save(ir_node *node)
167 sparc_attr_t *attr = get_sparc_attr(node);
168 int offset = attr->immediate_value;
169 ir_node *schedpoint = node;
176 if (sparc_is_value_imm_encodeable(offset))
179 /* uhh only works for the imm variant yet */
180 assert(get_irn_arity(node) == 1);
182 block = get_nodes_block(node);
183 dbgi = get_irn_dbg_info(node);
184 stack = get_irn_n(node, n_sparc_Save_stack);
185 entity = attr->immediate_value_entity;
186 new_save = new_bd_sparc_Save_imm(dbgi, block, stack, entity, 0);
187 arch_set_irn_register(new_save, &sparc_registers[REG_SP]);
190 sched_add_after(node, new_save);
191 schedpoint = new_save;
192 while (offset > SPARC_IMMEDIATE_MAX || offset < SPARC_IMMEDIATE_MIN) {
194 stack = be_new_IncSP(&sparc_registers[REG_SP], block, stack,
195 SPARC_IMMEDIATE_MIN, 0);
196 offset -= -SPARC_IMMEDIATE_MIN;
198 stack = be_new_IncSP(&sparc_registers[REG_SP], block, stack,
199 -SPARC_IMMEDIATE_MIN, 0);
200 offset -= SPARC_IMMEDIATE_MIN;
202 sched_add_after(schedpoint, stack);
205 attr = get_sparc_attr(new_save);
206 attr->immediate_value = offset;
207 be_peephole_exchange(node, stack);
211 * sparc immediates are limited. Split IncSP with bigger immediates if
214 static void finish_be_IncSP(ir_node *node)
217 int offset = be_get_IncSP_offset(node);
218 ir_node *sp = be_get_IncSP_pred(node);
221 /* we might have to break the IncSP apart if the constant has become too
228 if (sparc_is_value_imm_encodeable(-offset))
231 /* split incsp into multiple instructions */
232 block = get_nodes_block(node);
233 while (offset > -SPARC_IMMEDIATE_MIN) {
234 sp = be_new_IncSP(&sparc_registers[REG_SP], block, sp,
235 sign * -SPARC_IMMEDIATE_MIN, 0);
236 sched_add_before(node, sp);
237 offset -= -SPARC_IMMEDIATE_MIN;
240 be_set_IncSP_pred(node, sp);
241 be_set_IncSP_offset(node, sign*offset);
245 * adjust sp-relative offsets. Split into multiple instructions if offset
246 * exceeds sparc immediate range.
248 static void finish_sparc_FrameAddr(ir_node *node)
250 /* adapt to sparc stack magic */
251 sparc_attr_t *attr = get_sparc_attr(node);
252 int offset = attr->immediate_value;
253 ir_node *base = get_irn_n(node, n_sparc_FrameAddr_base);
254 dbg_info *dbgi = get_irn_dbg_info(node);
255 ir_node *block = get_nodes_block(node);
258 = arch_get_irn_register(base) == &sparc_registers[REG_SP];
260 offset += SPARC_MIN_STACKSIZE;
268 if (offset > -SPARC_IMMEDIATE_MIN) {
269 ir_entity *entity = attr->immediate_value_entity;
270 ir_node *new_frameaddr
271 = new_bd_sparc_FrameAddr(dbgi, block, base, entity, 0);
272 ir_node *schedpoint = node;
273 const arch_register_t *reg = arch_get_irn_register(node);
275 sched_add_after(schedpoint, new_frameaddr);
276 schedpoint = new_frameaddr;
277 arch_set_irn_register(new_frameaddr, reg);
278 base = new_frameaddr;
280 while (offset > -SPARC_IMMEDIATE_MIN) {
282 base = new_bd_sparc_Sub_imm(dbgi, block, base, NULL,
283 SPARC_IMMEDIATE_MIN);
285 base = new_bd_sparc_Add_imm(dbgi, block, base, NULL,
286 SPARC_IMMEDIATE_MIN);
288 arch_set_irn_register(base, reg);
289 sched_add_after(schedpoint, base);
292 offset -= -SPARC_IMMEDIATE_MIN;
295 be_peephole_exchange(node, base);
296 attr = get_sparc_attr(new_frameaddr);
298 attr->immediate_value = sign*offset;
301 static void finish_sparc_LdSt(ir_node *node)
303 sparc_load_store_attr_t *attr = get_sparc_load_store_attr(node);
304 if (attr->is_frame_entity) {
307 if (is_sparc_Ld(node) || is_sparc_Ldf(node)) {
308 base = get_irn_n(node, n_sparc_Ld_ptr);
310 assert(is_sparc_St(node) || is_sparc_Stf(node));
311 base = get_irn_n(node, n_sparc_St_ptr);
313 sp_relative = arch_get_irn_register(base) == &sparc_registers[REG_SP];
315 attr->base.immediate_value += SPARC_MIN_STACKSIZE;
319 static void peephole_be_IncSP(ir_node *node)
322 node = be_peephole_IncSP_IncSP(node);
323 if (!be_is_IncSP(node))
326 pred = be_get_IncSP_pred(node);
327 if (is_sparc_Save(pred) && be_has_only_one_user(pred)) {
328 int offset = -be_get_IncSP_offset(node);
329 sparc_attr_t *attr = get_sparc_attr(pred);
330 attr->immediate_value += offset;
331 be_peephole_exchange(node, pred);
335 static void peephole_sparc_FrameAddr(ir_node *node)
337 /* the peephole code currently doesn't allow this since it changes
338 * the register. Find out why and how to workaround this... */
340 const sparc_attr_t *attr = get_sparc_attr_const(node);
341 if (attr->immediate_value == 0) {
342 ir_node *base = get_irn_n(node, n_sparc_FrameAddr_base);
343 be_peephole_exchange(node, base);
349 static void finish_sparc_Return(ir_node *node)
351 ir_node *schedpoint = node;
353 /* see that there is no code between Return and restore, if there is move
354 * it in front of the restore */
356 if (!sched_has_prev(schedpoint))
358 schedpoint = sched_prev(schedpoint);
359 if (is_sparc_Restore(schedpoint) || is_sparc_RestoreZero(schedpoint))
362 restore = schedpoint;
363 schedpoint = sched_prev(node);
364 /* move all code between return and restore up */
365 while (schedpoint != restore) {
366 ir_node *next_schedpoint = sched_prev(schedpoint);
367 sched_remove(schedpoint);
368 sched_add_before(restore, schedpoint);
369 schedpoint = next_schedpoint;
373 static void register_peephole_optimisation(ir_op *op, peephole_opt_func func)
375 assert(op->ops.generic == NULL);
376 op->ops.generic = (op_func) func;
380 * transform reload node => load
382 static void transform_Reload(ir_node *node)
384 ir_node *block = get_nodes_block(node);
385 dbg_info *dbgi = get_irn_dbg_info(node);
386 ir_node *ptr = get_irn_n(node, n_be_Spill_frame);
387 ir_node *mem = get_irn_n(node, n_be_Reload_mem);
388 ir_mode *mode = get_irn_mode(node);
389 ir_entity *entity = be_get_frame_entity(node);
390 const arch_register_t *reg;
394 ir_node *sched_point = sched_prev(node);
396 load = new_bd_sparc_Ld_imm(dbgi, block, ptr, mem, mode, entity, 0, true);
397 sched_add_after(sched_point, load);
400 proj = new_rd_Proj(dbgi, load, mode, pn_sparc_Ld_res);
402 reg = arch_get_irn_register(node);
403 arch_set_irn_register(proj, reg);
405 exchange(node, proj);
409 * transform spill node => store
411 static void transform_Spill(ir_node *node)
413 ir_node *block = get_nodes_block(node);
414 dbg_info *dbgi = get_irn_dbg_info(node);
415 ir_node *ptr = get_irn_n(node, n_be_Spill_frame);
416 ir_graph *irg = get_irn_irg(node);
417 ir_node *mem = get_irg_no_mem(irg);
418 ir_node *val = get_irn_n(node, n_be_Spill_val);
419 ir_mode *mode = get_irn_mode(val);
420 ir_entity *entity = be_get_frame_entity(node);
421 ir_node *sched_point;
424 sched_point = sched_prev(node);
425 store = new_bd_sparc_St_imm(dbgi, block, val, ptr, mem, mode, entity, 0, true);
427 sched_add_after(sched_point, store);
429 exchange(node, store);
433 * walker to transform be_Spill and be_Reload nodes
435 static void sparc_after_ra_walker(ir_node *block, void *data)
437 ir_node *node, *prev;
440 for (node = sched_last(block); !sched_is_begin(node); node = prev) {
441 prev = sched_prev(node);
443 if (be_is_Reload(node)) {
444 transform_Reload(node);
445 } else if (be_is_Spill(node)) {
446 transform_Spill(node);
451 static void sparc_collect_frame_entity_nodes(ir_node *node, void *data)
453 be_fec_env_t *env = (be_fec_env_t*)data;
457 const sparc_load_store_attr_t *attr;
459 if (be_is_Reload(node) && be_get_frame_entity(node) == NULL) {
460 mode = get_irn_mode(node);
461 align = get_mode_size_bytes(mode);
462 be_node_needs_frame_entity(env, node, mode, align);
466 if (!is_sparc_Ld(node) && !is_sparc_Ldf(node))
469 attr = get_sparc_load_store_attr_const(node);
470 entity = attr->base.immediate_value_entity;
471 mode = attr->load_store_mode;
474 if (!attr->is_frame_entity)
476 if (arch_irn_get_flags(node) & sparc_arch_irn_flag_needs_64bit_spillslot)
478 align = get_mode_size_bytes(mode);
479 be_node_needs_frame_entity(env, node, mode, align);
482 static void sparc_set_frame_entity(ir_node *node, ir_entity *entity)
484 if (is_be_node(node)) {
485 be_node_set_frame_entity(node, entity);
487 /* we only say be_node_needs_frame_entity on nodes with load_store
488 * attributes, so this should be fine */
489 sparc_load_store_attr_t *attr = get_sparc_load_store_attr(node);
490 assert(attr->is_frame_entity);
491 assert(attr->base.immediate_value_entity == NULL);
492 attr->base.immediate_value_entity = entity;
496 void sparc_finish(ir_graph *irg)
498 be_stack_layout_t *stack_layout = be_get_irg_stack_layout(irg);
499 bool at_begin = stack_layout->sp_relative ? true : false;
500 be_fec_env_t *fec_env = be_new_frame_entity_coalescer(irg);
502 irg_walk_graph(irg, NULL, sparc_collect_frame_entity_nodes, fec_env);
503 be_assign_entities(fec_env, sparc_set_frame_entity, at_begin);
504 be_free_frame_entity_coalescer(fec_env);
506 irg_block_walk_graph(irg, NULL, sparc_after_ra_walker, NULL);
508 sparc_introduce_prolog_epilog(irg);
510 /* fix stack entity offsets */
511 be_abi_fix_stack_nodes(irg);
512 be_abi_fix_stack_bias(irg);
514 /* perform peephole optimizations */
515 clear_irp_opcodes_generic_func();
516 register_peephole_optimisation(op_be_IncSP, peephole_be_IncSP);
517 register_peephole_optimisation(op_sparc_FrameAddr, peephole_sparc_FrameAddr);
518 be_peephole_opt(irg);
520 /* perform legalizations (mostly fix nodes with too big immediates) */
521 clear_irp_opcodes_generic_func();
522 register_peephole_optimisation(op_be_IncSP, finish_be_IncSP);
523 register_peephole_optimisation(op_sparc_FrameAddr, finish_sparc_FrameAddr);
524 register_peephole_optimisation(op_sparc_Ld, finish_sparc_LdSt);
525 register_peephole_optimisation(op_sparc_Ldf, finish_sparc_LdSt);
526 register_peephole_optimisation(op_sparc_Return, finish_sparc_Return);
527 register_peephole_optimisation(op_sparc_Save, finish_sparc_Save);
528 register_peephole_optimisation(op_sparc_St, finish_sparc_LdSt);
529 register_peephole_optimisation(op_sparc_Stf, finish_sparc_LdSt);
530 be_peephole_opt(irg);
532 be_remove_dead_nodes_from_schedule(irg);