nsz Git - libfirm/blob - ir/be/sparc/sparc_finish.c

   1 /*
   2  * Copyright (C) 1995-2010 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   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.
  10  *
  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.
  14  *
  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
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief    Peephole optimization and legalization of a sparc function
  23  * @author   Matthias Braun
  24  * @version  $Id$
  25  *
  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
  38  * accordingly.
  39  */
  40 #include "config.h"
  41
  42 #include "bearch_sparc_t.h"
  43 #include "gen_sparc_regalloc_if.h"
  44 #include "sparc_new_nodes.h"
  45 #include "irprog.h"
  46 #include "irgmod.h"
  47 #include "ircons.h"
  48 #include "irgwalk.h"
  49
  50 #include "../bepeephole.h"
  51 #include "../benode.h"
  52 #include "../besched.h"
  53 #include "../bespillslots.h"
  54 #include "../bestack.h"
  55 #include "../beirgmod.h"
  56
  57 static void kill_unused_stacknodes(ir_node *node)
  58 {
  59         if (get_irn_n_edges(node) > 0)
  60                 return;
  61
  62         if (be_is_IncSP(node)) {
  63                 sched_remove(node);
  64                 kill_node(node);
  65         } else if (is_Phi(node)) {
  66                 int       arity = get_irn_arity(node);
  67                 ir_node **ins   = ALLOCAN(ir_node*, arity);
  68                 int       i;
  69                 sched_remove(node);
  70                 memcpy(ins, get_irn_in(node), arity*sizeof(ins[0]));
  71                 kill_node(node);
  72
  73                 for (i = 0; i < arity; ++i)
  74                         kill_unused_stacknodes(ins[i]);
  75         }
  76 }
  77
  78 static void introduce_epilog(ir_node *ret)
  79 {
  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);
  88
  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);
  96
  97                 kill_unused_stacknodes(sp);
  98         } else {
  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);
 102         }
 103 }
 104
 105 void sparc_introduce_prolog_epilog(ir_graph *irg)
 106 {
 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);
 116
 117         /* introduce epilog for every return node */
 118         {
 119                 ir_node *end_block = get_irg_end_block(irg);
 120                 int      arity     = get_irn_arity(end_block);
 121                 int      i;
 122
 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);
 127                 }
 128         }
 129
 130         while (be_is_Keep(sched_next(schedpoint)))
 131                 schedpoint = sched_next(schedpoint);
 132
 133         if (!layout->sp_relative) {
 134                 ir_node *incsp;
 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);
 139                 schedpoint = save;
 140
 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);
 145                 schedpoint = incsp;
 146
 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)
 151                  */
 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);
 156                 }
 157         } else {
 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);
 162         }
 163 }
 164
 165 static void finish_sparc_Save(ir_node *node)
 166 {
 167         sparc_attr_t *attr = get_sparc_attr(node);
 168         int offset = attr->immediate_value;
 169         ir_node  *schedpoint = node;
 170         dbg_info *dbgi;
 171         ir_node  *block;
 172         ir_node  *new_save;
 173         ir_node  *stack;
 174         ir_entity *entity;
 175
 176         if (sparc_is_value_imm_encodeable(offset))
 177                 return;
 178
 179         /* uhh only works for the imm variant yet */
 180         assert(get_irn_arity(node) == 1);
 181
 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]);
 188         stack = new_save;
 189
 190         sched_add_after(node, new_save);
 191         schedpoint = new_save;
 192         while (offset > SPARC_IMMEDIATE_MAX || offset < SPARC_IMMEDIATE_MIN) {
 193                 if (offset > 0) {
 194                         stack = be_new_IncSP(&sparc_registers[REG_SP], block, stack,
 195                                              SPARC_IMMEDIATE_MIN, 0);
 196                         offset -= -SPARC_IMMEDIATE_MIN;
 197                 } else {
 198                         stack = be_new_IncSP(&sparc_registers[REG_SP], block, stack,
 199                                              -SPARC_IMMEDIATE_MIN, 0);
 200                         offset -= SPARC_IMMEDIATE_MIN;
 201                 }
 202                 sched_add_after(schedpoint, stack);
 203                 schedpoint = stack;
 204         }
 205         attr = get_sparc_attr(new_save);
 206         attr->immediate_value = offset;
 207         be_peephole_exchange(node, stack);
 208 }
 209
 210 /**
 211  * sparc immediates are limited. Split IncSP with bigger immediates if
 212  * necessary.
 213  */
 214 static void finish_be_IncSP(ir_node *node)
 215 {
 216         int      sign   = 1;
 217         int      offset = be_get_IncSP_offset(node);
 218         ir_node *sp     = be_get_IncSP_pred(node);
 219         ir_node *block;
 220
 221         /* we might have to break the IncSP apart if the constant has become too
 222          * big */
 223         if (offset < 0) {
 224                 offset = -offset;
 225                 sign   = -1;
 226         }
 227
 228         if (sparc_is_value_imm_encodeable(-offset))
 229                 return;
 230
 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;
 238         }
 239
 240         be_set_IncSP_pred(node, sp);
 241         be_set_IncSP_offset(node, sign*offset);
 242 }
 243
 244 /**
 245  * adjust sp-relative offsets. Split into multiple instructions if offset
 246  * exceeds sparc immediate range.
 247  */
 248 static void finish_sparc_FrameAddr(ir_node *node)
 249 {
 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);
 256         int           sign   = 1;
 257         bool          sp_relative
 258                 = arch_get_irn_register(base) == &sparc_registers[REG_SP];
 259         if (sp_relative) {
 260                 offset += SPARC_MIN_STACKSIZE;
 261         }
 262
 263         if (offset < 0) {
 264                 sign   = -1;
 265                 offset = -offset;
 266         }
 267
 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);
 274
 275                 sched_add_after(schedpoint, new_frameaddr);
 276                 schedpoint = new_frameaddr;
 277                 arch_set_irn_register(new_frameaddr, reg);
 278                 base = new_frameaddr;
 279
 280                 while (offset > -SPARC_IMMEDIATE_MIN) {
 281                         if (sign > 0) {
 282                                 base = new_bd_sparc_Sub_imm(dbgi, block, base, NULL,
 283                                                                                         SPARC_IMMEDIATE_MIN);
 284                         } else {
 285                                 base = new_bd_sparc_Add_imm(dbgi, block, base, NULL,
 286                                                                                         SPARC_IMMEDIATE_MIN);
 287                         }
 288                         arch_set_irn_register(base, reg);
 289                         sched_add_after(schedpoint, base);
 290                         schedpoint = base;
 291
 292                         offset -= -SPARC_IMMEDIATE_MIN;
 293                 }
 294
 295                 be_peephole_exchange(node, base);
 296                 attr = get_sparc_attr(new_frameaddr);
 297         }
 298         attr->immediate_value = sign*offset;
 299 }
 300
 301 static void finish_sparc_LdSt(ir_node *node)
 302 {
 303         sparc_load_store_attr_t *attr = get_sparc_load_store_attr(node);
 304         if (attr->is_frame_entity) {
 305                 ir_node *base;
 306                 bool     sp_relative;
 307                 if (is_sparc_Ld(node) || is_sparc_Ldf(node)) {
 308                         base = get_irn_n(node, n_sparc_Ld_ptr);
 309                 } else {
 310                         assert(is_sparc_St(node) || is_sparc_Stf(node));
 311                         base = get_irn_n(node, n_sparc_St_ptr);
 312                 }
 313                 sp_relative = arch_get_irn_register(base) == &sparc_registers[REG_SP];
 314                 if (sp_relative)
 315                         attr->base.immediate_value += SPARC_MIN_STACKSIZE;
 316         }
 317 }
 318
 319 static void peephole_be_IncSP(ir_node *node)
 320 {
 321         ir_node *pred;
 322         node = be_peephole_IncSP_IncSP(node);
 323         if (!be_is_IncSP(node))
 324                 return;
 325
 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);
 332         }
 333 }
 334
 335 static void peephole_sparc_FrameAddr(ir_node *node)
 336 {
 337         /* the peephole code currently doesn't allow this since it changes
 338          * the register. Find out why and how to workaround this... */
 339 #if 0
 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);
 344         }
 345 #endif
 346         (void) node;
 347 }
 348
 349 static void finish_sparc_Return(ir_node *node)
 350 {
 351         ir_node *schedpoint = node;
 352         ir_node *restore;
 353         /* see that there is no code between Return and restore, if there is move
 354          * it in front of the restore */
 355         while (true) {
 356                 if (!sched_has_prev(schedpoint))
 357                         return;
 358                 schedpoint = sched_prev(schedpoint);
 359                 if (is_sparc_Restore(schedpoint) || is_sparc_RestoreZero(schedpoint))
 360                         break;
 361         }
 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;
 370         }
 371 }
 372
 373 static void register_peephole_optimisation(ir_op *op, peephole_opt_func func)
 374 {
 375         assert(op->ops.generic == NULL);
 376         op->ops.generic = (op_func) func;
 377 }
 378
 379 /**
 380  * transform reload node => load
 381  */
 382 static void transform_Reload(ir_node *node)
 383 {
 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;
 391         ir_node   *proj;
 392         ir_node   *load;
 393
 394         ir_node  *sched_point = sched_prev(node);
 395
 396         load = new_bd_sparc_Ld_imm(dbgi, block, ptr, mem, mode, entity, 0, true);
 397         sched_add_after(sched_point, load);
 398         sched_remove(node);
 399
 400         proj = new_rd_Proj(dbgi, load, mode, pn_sparc_Ld_res);
 401
 402         reg = arch_get_irn_register(node);
 403         arch_set_irn_register(proj, reg);
 404
 405         exchange(node, proj);
 406 }
 407
 408 /**
 409  * transform spill node => store
 410  */
 411 static void transform_Spill(ir_node *node)
 412 {
 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;
 422         ir_node   *store;
 423
 424         sched_point = sched_prev(node);
 425         store = new_bd_sparc_St_imm(dbgi, block, val, ptr, mem, mode, entity, 0, true);
 426         sched_remove(node);
 427         sched_add_after(sched_point, store);
 428
 429         exchange(node, store);
 430 }
 431
 432 /**
 433  * walker to transform be_Spill and be_Reload nodes
 434  */
 435 static void sparc_after_ra_walker(ir_node *block, void *data)
 436 {
 437         ir_node *node, *prev;
 438         (void) data;
 439
 440         for (node = sched_last(block); !sched_is_begin(node); node = prev) {
 441                 prev = sched_prev(node);
 442
 443                 if (be_is_Reload(node)) {
 444                         transform_Reload(node);
 445                 } else if (be_is_Spill(node)) {
 446                         transform_Spill(node);
 447                 }
 448         }
 449 }
 450
 451 static void sparc_collect_frame_entity_nodes(ir_node *node, void *data)
 452 {
 453         be_fec_env_t  *env = (be_fec_env_t*)data;
 454         const ir_mode *mode;
 455         int            align;
 456         ir_entity     *entity;
 457         const sparc_load_store_attr_t *attr;
 458
 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);
 463                 return;
 464         }
 465
 466         if (!is_sparc_Ld(node) && !is_sparc_Ldf(node))
 467                 return;
 468
 469         attr   = get_sparc_load_store_attr_const(node);
 470         entity = attr->base.immediate_value_entity;
 471         mode   = attr->load_store_mode;
 472         if (entity != NULL)
 473                 return;
 474         if (!attr->is_frame_entity)
 475                 return;
 476         if (arch_irn_get_flags(node) & sparc_arch_irn_flag_needs_64bit_spillslot)
 477                 mode = mode_Lu;
 478         align  = get_mode_size_bytes(mode);
 479         be_node_needs_frame_entity(env, node, mode, align);
 480 }
 481
 482 static void sparc_set_frame_entity(ir_node *node, ir_entity *entity)
 483 {
 484         if (is_be_node(node)) {
 485                 be_node_set_frame_entity(node, entity);
 486         } else {
 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;
 493         }
 494 }
 495
 496 void sparc_finish(ir_graph *irg)
 497 {
 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);
 501
 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);
 505
 506         irg_block_walk_graph(irg, NULL, sparc_after_ra_walker, NULL);
 507
 508         sparc_introduce_prolog_epilog(irg);
 509
 510         /* fix stack entity offsets */
 511         be_abi_fix_stack_nodes(irg);
 512         be_abi_fix_stack_bias(irg);
 513
 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);
 519
 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);
 531
 532         be_remove_dead_nodes_from_schedule(irg);
 533 }