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 "sparc_transform.h"
  46 #include "irprog.h"
  47 #include "irgmod.h"
  48 #include "ircons.h"
  49 #include "irgwalk.h"
  50
  51 #include "bepeephole.h"
  52 #include "benode.h"
  53 #include "besched.h"
  54 #include "bespillslots.h"
  55 #include "bestack.h"
  56 #include "beirgmod.h"
  57
  58 static void kill_unused_stacknodes(ir_node *node)
  59 {
  60         if (get_irn_n_edges(node) > 0)
  61                 return;
  62
  63         if (be_is_IncSP(node)) {
  64                 sched_remove(node);
  65                 kill_node(node);
  66         } else if (is_Phi(node)) {
  67                 int       arity = get_irn_arity(node);
  68                 ir_node **ins   = ALLOCAN(ir_node*, arity);
  69                 int       i;
  70                 sched_remove(node);
  71                 memcpy(ins, get_irn_in(node), arity*sizeof(ins[0]));
  72                 kill_node(node);
  73
  74                 for (i = 0; i < arity; ++i)
  75                         kill_unused_stacknodes(ins[i]);
  76         }
  77 }
  78
  79 static void introduce_epilog(ir_node *ret)
  80 {
  81         const arch_register_t *sp_reg     = &sparc_registers[REG_SP];
  82         ir_graph              *irg        = get_irn_irg(ret);
  83         be_stack_layout_t     *layout     = be_get_irg_stack_layout(irg);
  84         ir_node               *block      = get_nodes_block(ret);
  85         ir_type               *frame_type = get_irg_frame_type(irg);
  86         unsigned               frame_size = get_type_size_bytes(frame_type);
  87         int                    sp_idx     = be_find_return_reg_input(ret, sp_reg);
  88         ir_node               *sp         = get_irn_n(ret, sp_idx);
  89
  90         if (!layout->sp_relative) {
  91                 const arch_register_t *fp_reg = &sparc_registers[REG_FRAME_POINTER];
  92                 ir_node *fp      = be_get_initial_reg_value(irg, fp_reg);
  93                 ir_node *restore = new_bd_sparc_RestoreZero(NULL, block, fp);
  94                 sched_add_before(ret, restore);
  95                 arch_set_irn_register(restore, sp_reg);
  96                 set_irn_n(ret, sp_idx, restore);
  97
  98                 kill_unused_stacknodes(sp);
  99         } else {
 100                 ir_node *incsp  = be_new_IncSP(sp_reg, block, sp, -frame_size, 0);
 101                 set_irn_n(ret, sp_idx, incsp);
 102                 sched_add_before(ret, incsp);
 103         }
 104 }
 105
 106 void sparc_introduce_prolog_epilog(ir_graph *irg)
 107 {
 108         const arch_register_t *sp_reg     = &sparc_registers[REG_SP];
 109         ir_node               *start      = get_irg_start(irg);
 110         be_stack_layout_t     *layout     = be_get_irg_stack_layout(irg);
 111         ir_node               *block      = get_nodes_block(start);
 112         ir_node               *initial_sp = be_get_initial_reg_value(irg, sp_reg);
 113         ir_node               *sp         = initial_sp;
 114         ir_node               *schedpoint = start;
 115         ir_type               *frame_type = get_irg_frame_type(irg);
 116         unsigned               frame_size = get_type_size_bytes(frame_type);
 117
 118         /* introduce epilog for every return node */
 119         {
 120                 ir_node *end_block = get_irg_end_block(irg);
 121                 int      arity     = get_irn_arity(end_block);
 122                 int      i;
 123
 124                 for (i = 0; i < arity; ++i) {
 125                         ir_node *ret = get_irn_n(end_block, i);
 126                         assert(is_sparc_Return(ret));
 127                         introduce_epilog(ret);
 128                 }
 129         }
 130
 131         while (be_is_Keep(sched_next(schedpoint)))
 132                 schedpoint = sched_next(schedpoint);
 133
 134         if (!layout->sp_relative) {
 135                 ir_node *save = new_bd_sparc_Save_imm(NULL, block, sp, NULL,
 136                                                       -SPARC_MIN_STACKSIZE-frame_size);
 137                 arch_set_irn_register(save, sp_reg);
 138                 sched_add_after(schedpoint, save);
 139                 schedpoint = save;
 140
 141                 edges_reroute(initial_sp, save);
 142                 set_irn_n(save, n_sparc_Save_stack, initial_sp);
 143
 144                 /* we still need the Save even if noone is explicitely using the
 145                  * value. (TODO: this isn't 100% correct yet, something at the end of
 146                  * the function should hold the Save, even if we use a restore
 147                  * which just overrides it instead of using the value)
 148                  */
 149                 if (get_irn_n_edges(save) == 0) {
 150                         ir_node *in[] = { save };
 151                         ir_node *keep = be_new_Keep(block, 1, in);
 152                         sched_add_after(schedpoint, keep);
 153                 }
 154         } else {
 155                 ir_node *incsp = be_new_IncSP(sp_reg, block, sp, frame_size, 0);
 156                 edges_reroute(initial_sp, incsp);
 157                 be_set_IncSP_pred(incsp, sp);
 158                 sched_add_after(schedpoint, incsp);
 159         }
 160 }
 161
 162 /**
 163  * Creates a constant from an immediate value.
 164  */
 165 static ir_node *create_constant_from_immediate(ir_node *node, int offset)
 166 {
 167         dbg_info *dbgi  = get_irn_dbg_info(node);
 168         ir_node  *block = get_nodes_block(node);
 169         ir_node  *high  = new_bd_sparc_SetHi(dbgi, block, NULL, offset);
 170
 171         sched_add_before(node, high);
 172         arch_set_irn_register(high, &sparc_registers[REG_G4]);
 173
 174         if ((offset & 0x3ff) != 0) {
 175                 ir_node *low = new_bd_sparc_Or_imm(dbgi, block, high, NULL, offset & 0x3ff);
 176
 177                 sched_add_before(node, low);
 178                 arch_set_irn_register(low, &sparc_registers[REG_G4]);
 179
 180                 return low;
 181         }
 182
 183         return high;
 184 }
 185
 186 static void finish_sparc_Save(ir_node *node)
 187 {
 188         sparc_attr_t *attr = get_sparc_attr(node);
 189         int offset = attr->immediate_value;
 190
 191         if (! sparc_is_value_imm_encodeable(offset)) {
 192                 ir_node               *base     = get_irn_n(node, n_sparc_Save_stack);
 193                 dbg_info              *dbgi     = get_irn_dbg_info(node);
 194                 ir_node               *block    = get_nodes_block(node);
 195                 ir_node               *constant = create_constant_from_immediate(node, offset);
 196                 ir_node               *new_save = new_bd_sparc_Save_reg(dbgi, block, base, constant);
 197                 const arch_register_t *reg      = arch_get_irn_register(node);
 198
 199                 /* we have a Save with immediate */
 200                 assert(get_irn_arity(node) == 1);
 201
 202                 sched_add_before(node, new_save);
 203                 arch_set_irn_register(new_save, reg);
 204                 be_peephole_exchange(node, new_save);
 205         }
 206 }
 207
 208 /**
 209  * SPARC immediates are limited. Split IncSP with bigger immediates if
 210  * necessary.
 211  */
 212 static void finish_be_IncSP(ir_node *node)
 213 {
 214         int offset = be_get_IncSP_offset(node);
 215
 216         /* we might have to break the IncSP apart if the constant has become too big */
 217         if (! sparc_is_value_imm_encodeable(offset) && ! sparc_is_value_imm_encodeable(-offset)) {
 218                 ir_node               *sp       = be_get_IncSP_pred(node);
 219                 dbg_info              *dbgi     = get_irn_dbg_info(node);
 220                 ir_node               *block    = get_nodes_block(node);
 221                 ir_node               *constant = create_constant_from_immediate(node, offset);
 222                 ir_node               *sub      = new_bd_sparc_Sub_reg(dbgi, block, sp, constant);
 223
 224                 sched_add_before(node, sub);
 225                 arch_set_irn_register(sub, &sparc_registers[REG_SP]);
 226                 be_peephole_exchange(node, sub);
 227         }
 228 }
 229
 230 /**
 231  * Adjust sp-relative offsets.
 232  *
 233  * Split into multiple instructions if offset exceeds SPARC immediate range.
 234  */
 235 static void finish_sparc_FrameAddr(ir_node *node)
 236 {
 237         sparc_attr_t *attr   = get_sparc_attr(node);
 238         int           offset = attr->immediate_value;
 239
 240         if (! sparc_is_value_imm_encodeable(offset)) {
 241                 ir_node               *base          = get_irn_n(node, n_sparc_FrameAddr_base);
 242                 dbg_info              *dbgi          = get_irn_dbg_info(node);
 243                 ir_node               *block         = get_nodes_block(node);
 244                 ir_node               *constant      = create_constant_from_immediate(node, offset);
 245                 ir_node               *new_frameaddr = new_bd_sparc_Add_reg(dbgi, block, base, constant);
 246                 const arch_register_t *reg           = arch_get_irn_register(node);
 247
 248                 sched_add_before(node, new_frameaddr);
 249                 arch_set_irn_register(new_frameaddr, reg);
 250                 exchange(node, new_frameaddr);
 251         }
 252 }
 253
 254 static void finish_sparc_Ld(ir_node *node)
 255 {
 256         sparc_attr_t                  *attr            = get_sparc_attr(node);
 257         int                            offset          = attr->immediate_value;
 258         const sparc_load_store_attr_t *load_store_attr = get_sparc_load_store_attr_const(node);
 259
 260         if (! load_store_attr->is_frame_entity)
 261                 return;
 262
 263         if (! sparc_is_value_imm_encodeable(offset)) {
 264                 ir_node                 *ptr             = get_irn_n(node, n_sparc_Ld_ptr);
 265                 dbg_info                *dbgi            = get_irn_dbg_info(node);
 266                 ir_node                 *block           = get_nodes_block(node);
 267                 ir_node                 *mem             = get_irn_n(node, n_sparc_Ld_mem);
 268                 ir_mode                 *load_store_mode = load_store_attr->load_store_mode;
 269                 ir_node                 *constant        = create_constant_from_immediate(node, offset);
 270                 ir_node                 *new_load        = new_bd_sparc_Ld_reg(dbgi, block, ptr, constant, mem, load_store_mode);
 271                 sparc_load_store_attr_t *new_load_attr   = get_sparc_load_store_attr(new_load);
 272                 unsigned                 n_outs          = arch_get_irn_n_outs(node);
 273                 unsigned                 i;
 274
 275                 new_load_attr->is_frame_entity = load_store_attr->is_frame_entity;
 276                 new_load_attr->is_reg_reg      = load_store_attr->is_reg_reg;
 277
 278                 sched_add_before(node, new_load);
 279                 for (i = 0; i < n_outs; i++) {
 280                         arch_set_irn_register_out(new_load, i, arch_get_irn_register_out(node, i));
 281                 }
 282                 exchange(node, new_load);
 283         }
 284
 285 }
 286
 287 static void finish_sparc_Ldf(ir_node *node)
 288 {
 289         sparc_attr_t                  *attr            = get_sparc_attr(node);
 290         int                            offset          = attr->immediate_value;
 291         const sparc_load_store_attr_t *load_store_attr = get_sparc_load_store_attr_const(node);
 292
 293         if (! load_store_attr->is_frame_entity)
 294                 return;
 295
 296         if (! sparc_is_value_imm_encodeable(offset)) {
 297                 ir_node                 *ptr             = get_irn_n(node, n_sparc_Ldf_ptr);
 298                 dbg_info                *dbgi            = get_irn_dbg_info(node);
 299                 ir_node                 *block           = get_nodes_block(node);
 300                 ir_node                 *mem             = get_irn_n(node, n_sparc_Ldf_mem);
 301                 ir_mode                 *load_store_mode = load_store_attr->load_store_mode;
 302                 ir_node                 *constant        = create_constant_from_immediate(node, offset);
 303                 ir_node                 *new_ptr         = new_bd_sparc_Add_reg(dbgi, block, ptr, constant);
 304                 ir_node                 *new_load        = new_bd_sparc_Ldf_s(dbgi, block, new_ptr, mem, load_store_mode, NULL, 0, true);
 305                 sparc_load_store_attr_t *new_load_attr   = get_sparc_load_store_attr(new_load);
 306                 unsigned                 n_outs          = arch_get_irn_n_outs(node);
 307                 unsigned                 i;
 308
 309                 new_load_attr->is_frame_entity = load_store_attr->is_frame_entity;
 310                 new_load_attr->is_reg_reg      = load_store_attr->is_reg_reg;
 311
 312                 sched_add_before(node, new_load);
 313                 for (i = 0; i < n_outs; i++) {
 314                         arch_set_irn_register_out(new_load, i, arch_get_irn_register_out(node, i));
 315                 }
 316                 exchange(node, new_load);
 317         }
 318
 319 }
 320
 321 static void finish_sparc_St(ir_node *node)
 322 {
 323         sparc_attr_t                  *attr            = get_sparc_attr(node);
 324         int                            offset          = attr->immediate_value;
 325         const sparc_load_store_attr_t *load_store_attr = get_sparc_load_store_attr_const(node);
 326
 327         if (! load_store_attr->is_frame_entity)
 328                 return;
 329
 330         if (! sparc_is_value_imm_encodeable(offset)) {
 331                 ir_node                 *ptr             = get_irn_n(node, n_sparc_St_ptr);
 332                 dbg_info                *dbgi            = get_irn_dbg_info(node);
 333                 ir_node                 *block           = get_nodes_block(node);
 334                 ir_node                 *mem             = get_irn_n(node, n_sparc_St_mem);
 335                 ir_node                 *value           = get_irn_n(node, n_sparc_St_val);
 336                 ir_mode                 *load_store_mode = load_store_attr->load_store_mode;
 337                 ir_node                 *constant        = create_constant_from_immediate(node, offset);
 338                 ir_node                 *new_load        = new_bd_sparc_St_reg(dbgi, block, value, ptr, constant, mem, load_store_mode);
 339                 sparc_load_store_attr_t *new_load_attr   = get_sparc_load_store_attr(new_load);
 340                 unsigned                 n_outs          = arch_get_irn_n_outs(node);
 341                 unsigned                 i;
 342
 343                 new_load_attr->is_frame_entity = load_store_attr->is_frame_entity;
 344                 new_load_attr->is_reg_reg      = load_store_attr->is_reg_reg;
 345
 346                 sched_add_before(node, new_load);
 347                 for (i = 0; i < n_outs; i++) {
 348                         arch_set_irn_register_out(new_load, i, arch_get_irn_register_out(node, i));
 349                 }
 350                 exchange(node, new_load);
 351         }
 352
 353 }
 354
 355 static void finish_sparc_Stf(ir_node *node)
 356 {
 357         sparc_attr_t                  *attr            = get_sparc_attr(node);
 358         int                            offset          = attr->immediate_value;
 359         const sparc_load_store_attr_t *load_store_attr = get_sparc_load_store_attr_const(node);
 360
 361         if (! load_store_attr->is_frame_entity)
 362                 return;
 363
 364         if (! sparc_is_value_imm_encodeable(offset)) {
 365                 ir_node                 *ptr             = get_irn_n(node, n_sparc_Stf_ptr);
 366                 dbg_info                *dbgi            = get_irn_dbg_info(node);
 367                 ir_node                 *block           = get_nodes_block(node);
 368                 ir_node                 *mem             = get_irn_n(node, n_sparc_Stf_mem);
 369                 ir_node                 *value           = get_irn_n(node, n_sparc_Stf_val);
 370                 ir_mode                 *load_store_mode = load_store_attr->load_store_mode;
 371                 ir_node                 *constant        = create_constant_from_immediate(node, offset);
 372                 ir_node                 *new_ptr         = new_bd_sparc_Add_reg(dbgi, block, ptr, constant);
 373                 ir_node                 *new_load        = new_bd_sparc_Stf_s(dbgi, block, value, new_ptr, mem, load_store_mode, NULL, 0, true);
 374                 sparc_load_store_attr_t *new_load_attr   = get_sparc_load_store_attr(new_load);
 375                 unsigned                 n_outs          = arch_get_irn_n_outs(node);
 376                 unsigned                 i;
 377
 378                 new_load_attr->is_frame_entity = load_store_attr->is_frame_entity;
 379                 new_load_attr->is_reg_reg      = load_store_attr->is_reg_reg;
 380
 381                 sched_add_before(node, new_load);
 382                 for (i = 0; i < n_outs; i++) {
 383                         arch_set_irn_register_out(new_load, i, arch_get_irn_register_out(node, i));
 384                 }
 385                 exchange(node, new_load);
 386         }
 387
 388 }
 389
 390 static void peephole_be_IncSP(ir_node *node)
 391 {
 392         ir_node *pred;
 393         node = be_peephole_IncSP_IncSP(node);
 394         if (!be_is_IncSP(node))
 395                 return;
 396
 397         pred = be_get_IncSP_pred(node);
 398         if (is_sparc_Save(pred) && be_has_only_one_user(pred)) {
 399                 int offset = -be_get_IncSP_offset(node);
 400                 sparc_attr_t *attr = get_sparc_attr(pred);
 401                 attr->immediate_value += offset;
 402                 be_peephole_exchange(node, pred);
 403         }
 404 }
 405
 406 static void peephole_sparc_FrameAddr(ir_node *node)
 407 {
 408         /* the peephole code currently doesn't allow this since it changes
 409          * the register. Find out why and how to workaround this... */
 410 #if 0
 411         const sparc_attr_t *attr = get_sparc_attr_const(node);
 412         if (attr->immediate_value == 0) {
 413                 ir_node *base = get_irn_n(node, n_sparc_FrameAddr_base);
 414                 be_peephole_exchange(node, base);
 415         }
 416 #endif
 417         (void) node;
 418 }
 419
 420 static void finish_sparc_Return(ir_node *node)
 421 {
 422         ir_node *schedpoint = node;
 423         ir_node *restore;
 424         /* see that there is no code between Return and restore, if there is move
 425          * it in front of the restore */
 426         while (true) {
 427                 if (!sched_has_prev(schedpoint))
 428                         return;
 429                 schedpoint = sched_prev(schedpoint);
 430                 if (is_sparc_Restore(schedpoint) || is_sparc_RestoreZero(schedpoint))
 431                         break;
 432         }
 433         restore = schedpoint;
 434         schedpoint = sched_prev(node);
 435         /* move all code between return and restore up */
 436         while (schedpoint != restore) {
 437                 ir_node *next_schedpoint = sched_prev(schedpoint);
 438                 sched_remove(schedpoint);
 439                 sched_add_before(restore, schedpoint);
 440                 schedpoint = next_schedpoint;
 441         }
 442 }
 443
 444 static void register_peephole_optimisation(ir_op *op, peephole_opt_func func)
 445 {
 446         assert(op->ops.generic == NULL);
 447         op->ops.generic = (op_func) func;
 448 }
 449
 450 static void sparc_collect_frame_entity_nodes(ir_node *node, void *data)
 451 {
 452         be_fec_env_t  *env = (be_fec_env_t*)data;
 453         const ir_mode *mode;
 454         int            align;
 455         ir_entity     *entity;
 456         const sparc_load_store_attr_t *attr;
 457
 458         if (be_is_Reload(node) && be_get_frame_entity(node) == NULL) {
 459                 mode  = get_irn_mode(node);
 460                 align = get_mode_size_bytes(mode);
 461                 be_node_needs_frame_entity(env, node, mode, align);
 462                 return;
 463         }
 464
 465         if (!is_sparc_Ld(node) && !is_sparc_Ldf(node))
 466                 return;
 467
 468         attr   = get_sparc_load_store_attr_const(node);
 469         entity = attr->base.immediate_value_entity;
 470         mode   = attr->load_store_mode;
 471         if (entity != NULL)
 472                 return;
 473         if (!attr->is_frame_entity)
 474                 return;
 475         if (arch_get_irn_flags(node) & sparc_arch_irn_flag_needs_64bit_spillslot)
 476                 mode = mode_Lu;
 477         align  = get_mode_size_bytes(mode);
 478         be_node_needs_frame_entity(env, node, mode, align);
 479 }
 480
 481 static void sparc_set_frame_entity(ir_node *node, ir_entity *entity)
 482 {
 483         if (is_be_node(node)) {
 484                 be_node_set_frame_entity(node, entity);
 485         } else {
 486                 /* we only say be_node_needs_frame_entity on nodes with load_store
 487                  * attributes, so this should be fine */
 488                 sparc_load_store_attr_t *attr = get_sparc_load_store_attr(node);
 489                 assert(attr->is_frame_entity);
 490                 assert(attr->base.immediate_value_entity == NULL);
 491                 attr->base.immediate_value_entity = entity;
 492         }
 493 }
 494
 495 void sparc_finish(ir_graph *irg)
 496 {
 497         be_stack_layout_t *stack_layout = be_get_irg_stack_layout(irg);
 498         bool               at_begin     = stack_layout->sp_relative ? true : false;
 499         be_fec_env_t      *fec_env      = be_new_frame_entity_coalescer(irg);
 500
 501         irg_walk_graph(irg, NULL, sparc_collect_frame_entity_nodes, fec_env);
 502         be_assign_entities(fec_env, sparc_set_frame_entity, at_begin);
 503         be_free_frame_entity_coalescer(fec_env);
 504
 505         sparc_introduce_prolog_epilog(irg);
 506
 507         /* fix stack entity offsets */
 508         be_abi_fix_stack_nodes(irg);
 509         sparc_fix_stack_bias(irg);
 510
 511         /* perform peephole optimizations */
 512         clear_irp_opcodes_generic_func();
 513         register_peephole_optimisation(op_be_IncSP,        peephole_be_IncSP);
 514         register_peephole_optimisation(op_sparc_FrameAddr, peephole_sparc_FrameAddr);
 515         be_peephole_opt(irg);
 516
 517         /* perform legalizations (mostly fix nodes with too big immediates) */
 518         clear_irp_opcodes_generic_func();
 519         register_peephole_optimisation(op_be_IncSP,        finish_be_IncSP);
 520         register_peephole_optimisation(op_sparc_FrameAddr, finish_sparc_FrameAddr);
 521         register_peephole_optimisation(op_sparc_Ld,        finish_sparc_Ld);
 522         register_peephole_optimisation(op_sparc_Ldf,       finish_sparc_Ldf);
 523         register_peephole_optimisation(op_sparc_Return,    finish_sparc_Return);
 524         register_peephole_optimisation(op_sparc_Save,      finish_sparc_Save);
 525         register_peephole_optimisation(op_sparc_St,        finish_sparc_St);
 526         register_peephole_optimisation(op_sparc_Stf,       finish_sparc_Stf);
 527         be_peephole_opt(irg);
 528
 529         be_remove_dead_nodes_from_schedule(irg);
 530 }