nsz Git - libfirm/blob - ir/be/bestack.c

   1 /*
   2  * Copyright (C) 1995-2008 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  * @author      Sebastian Hack, Matthias Braun
  23  *
  24  * Handling of the stack frame. It is composed of three types:
  25  * 1) The type of the arguments which are pushed on the stack.
  26  * 2) The "between type" which consists of stuff the call of the
  27  *    function pushes on the stack (like the return address and
  28  *    the old base pointer for ia32).
  29  * 3) The Firm frame type which consists of all local variables
  30  *    and the spills.
  31  */
  32 #include "config.h"
  33
  34 #include "bestack.h"
  35 #include "beirg.h"
  36 #include "besched.h"
  37 #include "benode.h"
  38 #include "bessaconstr.h"
  39
  40 #include "ircons_t.h"
  41 #include "irnode_t.h"
  42 #include "irgwalk.h"
  43 #include "irgmod.h"
  44
  45 int be_get_stack_entity_offset(be_stack_layout_t *frame, ir_entity *ent,
  46                                int bias)
  47 {
  48         ir_type *t = get_entity_owner(ent);
  49         int ofs    = get_entity_offset(ent);
  50
  51         int index;
  52
  53         /* Find the type the entity is contained in. */
  54         for (index = 0; index < N_FRAME_TYPES; ++index) {
  55                 if (frame->order[index] == t)
  56                         break;
  57                 /* Add the size of all the types below the one of the entity to the entity's offset */
  58                 ofs += get_type_size_bytes(frame->order[index]);
  59         }
  60
  61         /* correct the offset by the initial position of the frame pointer */
  62         ofs -= frame->initial_offset;
  63
  64         /* correct the offset with the current bias. */
  65         ofs += bias;
  66
  67         return ofs;
  68 }
  69
  70 /**
  71  * Retrieve the entity with given offset from a frame type.
  72  */
  73 static ir_entity *search_ent_with_offset(ir_type *t, int offset)
  74 {
  75         int i, n;
  76
  77         for (i = 0, n = get_compound_n_members(t); i < n; ++i) {
  78                 ir_entity *ent = get_compound_member(t, i);
  79                 if (get_entity_offset(ent) == offset)
  80                         return ent;
  81         }
  82
  83         return NULL;
  84 }
  85
  86 static void stack_frame_compute_initial_offset(be_stack_layout_t *frame)
  87 {
  88         ir_type  *base = frame->between_type;
  89         ir_entity *ent = search_ent_with_offset(base, 0);
  90
  91         if (ent == NULL) {
  92                 frame->initial_offset = get_type_size_bytes(frame->frame_type);
  93         } else {
  94                 frame->initial_offset = be_get_stack_entity_offset(frame, ent, 0);
  95         }
  96 }
  97
  98 /**
  99  * Walker: finally lower all Sels of outer frame or parameter
 100  * entities.
 101  */
 102 static void lower_outer_frame_sels(ir_node *sel, void *ctx)
 103 {
 104         ir_node           *ptr;
 105         ir_entity         *ent;
 106         ir_type           *owner;
 107         be_stack_layout_t *layout;
 108         ir_graph          *irg;
 109         (void) ctx;
 110
 111         if (! is_Sel(sel))
 112                 return;
 113
 114         ent    = get_Sel_entity(sel);
 115         owner  = get_entity_owner(ent);
 116         ptr    = get_Sel_ptr(sel);
 117         irg    = get_irn_irg(sel);
 118         layout = be_get_irg_stack_layout(irg);
 119
 120         if (owner == layout->frame_type || owner == layout->arg_type) {
 121                 /* found access to outer frame or arguments */
 122                 int offset = be_get_stack_entity_offset(layout, ent, 0);
 123
 124                 if (offset != 0) {
 125                         ir_node  *bl   = get_nodes_block(sel);
 126                         dbg_info *dbgi = get_irn_dbg_info(sel);
 127                         ir_mode  *mode = get_irn_mode(sel);
 128                         ir_mode  *mode_UInt = get_reference_mode_unsigned_eq(mode);
 129                         ir_node  *cnst = new_r_Const_long(irg, mode_UInt, offset);
 130
 131                         ptr = new_rd_Add(dbgi, bl, ptr, cnst, mode);
 132                 }
 133                 exchange(sel, ptr);
 134         }
 135 }
 136
 137 /**
 138  * A helper struct for the bias walker.
 139  */
 140 typedef struct bias_walk {
 141         int      start_block_bias; /**< The bias at the end of the start block. */
 142         ir_node *start_block;      /**< The start block of the current graph. */
 143 } bias_walk;
 144
 145 /**
 146  * Fix all stack accessing operations in the block bl.
 147  *
 148  * @param bl         the block to process
 149  * @param real_bias  the bias value
 150  *
 151  * @return the bias at the end of this block
 152  */
 153 static int process_stack_bias(ir_node *bl, int real_bias)
 154 {
 155         int                wanted_bias = real_bias;
 156         ir_graph          *irg         = get_Block_irg(bl);
 157         be_stack_layout_t *layout      = be_get_irg_stack_layout(irg);
 158         bool               sp_relative = layout->sp_relative;
 159         const arch_env_t  *arch_env    = be_get_irg_arch_env(irg);
 160
 161         sched_foreach(bl, irn) {
 162                 int ofs;
 163
 164                 /*
 165                    Check, if the node relates to an entity on the stack frame.
 166                    If so, set the true offset (including the bias) for that
 167                    node.
 168                  */
 169                 ir_entity *ent = arch_get_frame_entity(irn);
 170                 if (ent != NULL) {
 171                         int bias   = sp_relative ? real_bias : 0;
 172                         int offset = be_get_stack_entity_offset(layout, ent, bias);
 173                         arch_set_frame_offset(irn, offset);
 174                 }
 175
 176                 /*
 177                  * If the node modifies the stack pointer by a constant offset,
 178                  * record that in the bias.
 179                  */
 180                 if (be_is_IncSP(irn)) {
 181                         ofs = be_get_IncSP_offset(irn);
 182                         /* fill in real stack frame size */
 183                         if (be_get_IncSP_align(irn)) {
 184                                 /* patch IncSP to produce an aligned stack pointer */
 185                                 int const between_size = get_type_size_bytes(layout->between_type);
 186                                 int const alignment    = 1 << arch_env->stack_alignment;
 187                                 int const delta        = (real_bias + ofs + between_size) & (alignment - 1);
 188                                 assert(ofs >= 0);
 189                                 if (delta > 0) {
 190                                         be_set_IncSP_offset(irn, ofs + alignment - delta);
 191                                         real_bias += alignment - delta;
 192                                 }
 193                         } else {
 194                                 /* adjust so real_bias corresponds with wanted_bias */
 195                                 int delta = wanted_bias - real_bias;
 196                                 assert(delta <= 0);
 197                                 if (delta != 0) {
 198                                         be_set_IncSP_offset(irn, ofs + delta);
 199                                         real_bias += delta;
 200                                 }
 201                         }
 202                         real_bias   += ofs;
 203                         wanted_bias += ofs;
 204                 } else {
 205                         ofs = arch_get_sp_bias(irn);
 206                         if (ofs == SP_BIAS_RESET) {
 207                                 real_bias   = 0;
 208                                 wanted_bias = 0;
 209                         } else {
 210                                 real_bias   += ofs;
 211                                 wanted_bias += ofs;
 212                         }
 213                 }
 214         }
 215
 216         assert(real_bias == wanted_bias);
 217         return real_bias;
 218 }
 219
 220 /**
 221  * Block-Walker: fix all stack offsets for all blocks
 222  * except the start block
 223  */
 224 static void stack_bias_walker(ir_node *bl, void *data)
 225 {
 226         bias_walk *bw = (bias_walk*)data;
 227         if (bl != bw->start_block) {
 228                 process_stack_bias(bl, bw->start_block_bias);
 229         }
 230 }
 231
 232 void be_abi_fix_stack_bias(ir_graph *irg)
 233 {
 234         be_stack_layout_t *stack_layout = be_get_irg_stack_layout(irg);
 235         ir_type           *frame_tp;
 236         int                i;
 237         bias_walk          bw;
 238
 239         stack_frame_compute_initial_offset(stack_layout);
 240
 241         /* Determine the stack bias at the end of the start block. */
 242         bw.start_block_bias = process_stack_bias(get_irg_start_block(irg),
 243                                                  stack_layout->initial_bias);
 244
 245         /* fix the bias is all other blocks */
 246         bw.start_block = get_irg_start_block(irg);
 247         irg_block_walk_graph(irg, stack_bias_walker, NULL, &bw);
 248
 249         /* fix now inner functions: these still have Sel node to outer
 250            frame and parameter entities */
 251         frame_tp = get_irg_frame_type(irg);
 252         for (i = get_class_n_members(frame_tp) - 1; i >= 0; --i) {
 253                 ir_entity *ent = get_class_member(frame_tp, i);
 254                 ir_graph  *irg = get_entity_irg(ent);
 255
 256                 if (irg != NULL) {
 257                         irg_walk_graph(irg, NULL, lower_outer_frame_sels, NULL);
 258                 }
 259         }
 260 }
 261
 262 typedef struct fix_stack_walker_env_t {
 263         ir_node **sp_nodes;
 264 } fix_stack_walker_env_t;
 265
 266 /**
 267  * Walker. Collect all stack modifying nodes.
 268  */
 269 static void collect_stack_nodes_walker(ir_node *node, void *data)
 270 {
 271         fix_stack_walker_env_t *const env = (fix_stack_walker_env_t*)data;
 272
 273         if (get_irn_mode(node) == mode_T)
 274                 return;
 275
 276         arch_register_req_t const *const req = arch_get_irn_register_req(node);
 277         if (!arch_register_req_is(req, produces_sp))
 278                 return;
 279
 280         ARR_APP1(ir_node*, env->sp_nodes, node);
 281 }
 282
 283 void be_abi_fix_stack_nodes(ir_graph *irg)
 284 {
 285         be_lv_t                   *lv       = be_get_irg_liveness(irg);
 286         const arch_env_t          *arch_env = be_get_irg_arch_env(irg);
 287         be_irg_t                  *birg     = be_birg_from_irg(irg);
 288         const arch_register_t     *sp       = arch_env->sp;
 289         be_ssa_construction_env_t  senv;
 290         int i, len;
 291         ir_node **phis;
 292         fix_stack_walker_env_t walker_env;
 293
 294         arch_register_req_t const *sp_req = birg->sp_req;
 295         if (sp_req == NULL) {
 296                 arch_register_req_type_t type = arch_register_req_type_produces_sp;
 297                 if (!rbitset_is_set(birg->allocatable_regs, sp->global_index))
 298                         type |= arch_register_req_type_ignore;
 299
 300                 struct obstack *const obst = be_get_be_obst(irg);
 301                 birg->sp_req = sp_req = be_create_reg_req(obst, sp, type);
 302         }
 303
 304         walker_env.sp_nodes = NEW_ARR_F(ir_node*, 0);
 305
 306         irg_walk_graph(irg, collect_stack_nodes_walker, NULL, &walker_env);
 307
 308         /* nothing to be done if we didn't find any node, in fact we mustn't
 309          * continue, as for endless loops incsp might have had no users and is bad
 310          * now.
 311          */
 312         len = ARR_LEN(walker_env.sp_nodes);
 313         if (len == 0) {
 314                 DEL_ARR_F(walker_env.sp_nodes);
 315                 return;
 316         }
 317
 318         be_ssa_construction_init(&senv, irg);
 319         be_ssa_construction_add_copies(&senv, walker_env.sp_nodes,
 320                                    ARR_LEN(walker_env.sp_nodes));
 321         be_ssa_construction_fix_users_array(&senv, walker_env.sp_nodes,
 322                                             ARR_LEN(walker_env.sp_nodes));
 323
 324         if (lv != NULL) {
 325                 len = ARR_LEN(walker_env.sp_nodes);
 326                 for (i = 0; i < len; ++i) {
 327                         be_liveness_update(lv, walker_env.sp_nodes[i]);
 328                 }
 329                 be_ssa_construction_update_liveness_phis(&senv, lv);
 330         }
 331
 332         phis = be_ssa_construction_get_new_phis(&senv);
 333
 334         /* set register requirements for stack phis */
 335         len = ARR_LEN(phis);
 336         for (i = 0; i < len; ++i) {
 337                 ir_node *phi = phis[i];
 338                 be_set_phi_reg_req(phi, sp_req);
 339                 arch_set_irn_register(phi, arch_env->sp);
 340         }
 341         be_ssa_construction_destroy(&senv);
 342         DEL_ARR_F(walker_env.sp_nodes);
 343
 344         /* when doing code with frame-pointers then often the last incsp-nodes are
 345          * not used anymore because we copy the framepointer to the stack pointer
 346          * when leaving the function. Though the last incsp is often kept (because
 347          * you often don't know which incsp is the last one and fixstack should find
 348          * them all). Remove unnecessary keeps and IncSP nodes */
 349         {
 350                 ir_node  *end    = get_irg_end(irg);
 351                 int       arity  = get_irn_arity(end);
 352                 int       i;
 353                 for (i = arity-1; i >= 0; --i) {
 354                         ir_node *in = get_irn_n(end, i);
 355                         if (!be_is_IncSP(in)) {
 356                                 continue;
 357                         }
 358
 359                         remove_End_keepalive(end, in);
 360                         if (get_irn_n_edges(in) == 0) {
 361                                 sched_remove(in);
 362                                 kill_node(in);
 363                         }
 364                 }
 365         }
 366 }