gcc/combine-stack-adj.c

   1 /* Combine stack adjustments.
   2    Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  21
  22 /* Track stack adjustments and stack memory references.  Attempt to
  23    reduce the number of stack adjustments by back-propagating across
  24    the memory references.
  25
  26    This is intended primarily for use with targets that do not define
  27    ACCUMULATE_OUTGOING_ARGS.  It is of significantly more value to
  28    targets that define PREFERRED_STACK_BOUNDARY more aligned than
  29    STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
  30    (e.g. x86 fp regs) which would ordinarily have to be implemented
  31    as a sub/mov pair due to restrictions in calls.c.
  32
  33    Propagation stops when any of the insns that need adjusting are
  34    (a) no longer valid because we've exceeded their range, (b) a
  35    non-trivial push instruction, or (c) a call instruction.
  36
  37    Restriction B is based on the assumption that push instructions
  38    are smaller or faster.  If a port really wants to remove all
  39    pushes, it should have defined ACCUMULATE_OUTGOING_ARGS.  The
  40    one exception that is made is for an add immediately followed
  41    by a push.  */
  42
  43 #include "config.h"
  44 #include "system.h"
  45 #include "coretypes.h"
  46 #include "tm.h"
  47 #include "rtl.h"
  48 #include "tm_p.h"
  49 #include "insn-config.h"
  50 #include "recog.h"
  51 #include "output.h"
  52 #include "regs.h"
  53 #include "hard-reg-set.h"
  54 #include "flags.h"
  55 #include "function.h"
  56 #include "expr.h"
  57 #include "basic-block.h"
  58 #include "except.h"
  59 #include "toplev.h"
  60 #include "reload.h"
  61 #include "timevar.h"
  62 #include "tree-pass.h"
  63
  64 \f
  65 /* Turn STACK_GROWS_DOWNWARD into a boolean.  */
  66 #ifdef STACK_GROWS_DOWNWARD
  67 #undef STACK_GROWS_DOWNWARD
  68 #define STACK_GROWS_DOWNWARD 1
  69 #else
  70 #define STACK_GROWS_DOWNWARD 0
  71 #endif
  72
  73 /* This structure records stack memory references between stack adjusting
  74    instructions.  */
  75
  76 struct csa_memlist
  77 {
  78   HOST_WIDE_INT sp_offset;
  79   rtx insn, *mem;
  80   struct csa_memlist *next;
  81 };
  82
  83 static int stack_memref_p (rtx);
  84 static rtx single_set_for_csa (rtx);
  85 static void free_csa_memlist (struct csa_memlist *);
  86 static struct csa_memlist *record_one_stack_memref (rtx, rtx *,
  87                                                     struct csa_memlist *);
  88 static int try_apply_stack_adjustment (rtx, struct csa_memlist *,
  89                                        HOST_WIDE_INT, HOST_WIDE_INT);
  90 static void combine_stack_adjustments_for_block (basic_block);
  91 static int record_stack_memrefs (rtx *, void *);
  92
  93
  94 /* Main entry point for stack adjustment combination.  */
  95
  96 static void
  97 combine_stack_adjustments (void)
  98 {
  99   basic_block bb;
 100
 101   FOR_EACH_BB (bb)
 102     combine_stack_adjustments_for_block (bb);
 103 }
 104
 105 /* Recognize a MEM of the form (sp) or (plus sp const).  */
 106
 107 static int
 108 stack_memref_p (rtx x)
 109 {
 110   if (!MEM_P (x))
 111     return 0;
 112   x = XEXP (x, 0);
 113
 114   if (x == stack_pointer_rtx)
 115     return 1;
 116   if (GET_CODE (x) == PLUS
 117       && XEXP (x, 0) == stack_pointer_rtx
 118       && GET_CODE (XEXP (x, 1)) == CONST_INT)
 119     return 1;
 120
 121   return 0;
 122 }
 123
 124 /* Recognize either normal single_set or the hack in i386.md for
 125    tying fp and sp adjustments.  */
 126
 127 static rtx
 128 single_set_for_csa (rtx insn)
 129 {
 130   int i;
 131   rtx tmp = single_set (insn);
 132   if (tmp)
 133     return tmp;
 134
 135   if (!NONJUMP_INSN_P (insn)
 136       || GET_CODE (PATTERN (insn)) != PARALLEL)
 137     return NULL_RTX;
 138
 139   tmp = PATTERN (insn);
 140   if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
 141     return NULL_RTX;
 142
 143   for (i = 1; i < XVECLEN (tmp, 0); ++i)
 144     {
 145       rtx this = XVECEXP (tmp, 0, i);
 146
 147       /* The special case is allowing a no-op set.  */
 148       if (GET_CODE (this) == SET
 149           && SET_SRC (this) == SET_DEST (this))
 150         ;
 151       else if (GET_CODE (this) != CLOBBER
 152                && GET_CODE (this) != USE)
 153         return NULL_RTX;
 154     }
 155
 156   return XVECEXP (tmp, 0, 0);
 157 }
 158
 159 /* Free the list of csa_memlist nodes.  */
 160
 161 static void
 162 free_csa_memlist (struct csa_memlist *memlist)
 163 {
 164   struct csa_memlist *next;
 165   for (; memlist ; memlist = next)
 166     {
 167       next = memlist->next;
 168       free (memlist);
 169     }
 170 }
 171
 172 /* Create a new csa_memlist node from the given memory reference.
 173    It is already known that the memory is stack_memref_p.  */
 174
 175 static struct csa_memlist *
 176 record_one_stack_memref (rtx insn, rtx *mem, struct csa_memlist *next_memlist)
 177 {
 178   struct csa_memlist *ml;
 179
 180   ml = XNEW (struct csa_memlist);
 181
 182   if (XEXP (*mem, 0) == stack_pointer_rtx)
 183     ml->sp_offset = 0;
 184   else
 185     ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
 186
 187   ml->insn = insn;
 188   ml->mem = mem;
 189   ml->next = next_memlist;
 190
 191   return ml;
 192 }
 193
 194 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
 195    as each of the memories in MEMLIST.  Return true on success.  */
 196
 197 static int
 198 try_apply_stack_adjustment (rtx insn, struct csa_memlist *memlist, HOST_WIDE_INT new_adjust,
 199                             HOST_WIDE_INT delta)
 200 {
 201   struct csa_memlist *ml;
 202   rtx set;
 203
 204   set = single_set_for_csa (insn);
 205   validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
 206
 207   for (ml = memlist; ml ; ml = ml->next)
 208     validate_change
 209       (ml->insn, ml->mem,
 210        replace_equiv_address_nv (*ml->mem,
 211                                  plus_constant (stack_pointer_rtx,
 212                                                 ml->sp_offset - delta)), 1);
 213
 214   if (apply_change_group ())
 215     {
 216       /* Succeeded.  Update our knowledge of the memory references.  */
 217       for (ml = memlist; ml ; ml = ml->next)
 218         ml->sp_offset -= delta;
 219
 220       return 1;
 221     }
 222   else
 223     return 0;
 224 }
 225
 226 /* Called via for_each_rtx and used to record all stack memory references in
 227    the insn and discard all other stack pointer references.  */
 228 struct record_stack_memrefs_data
 229 {
 230   rtx insn;
 231   struct csa_memlist *memlist;
 232 };
 233
 234 static int
 235 record_stack_memrefs (rtx *xp, void *data)
 236 {
 237   rtx x = *xp;
 238   struct record_stack_memrefs_data *d =
 239     (struct record_stack_memrefs_data *) data;
 240   if (!x)
 241     return 0;
 242   switch (GET_CODE (x))
 243     {
 244     case MEM:
 245       if (!reg_mentioned_p (stack_pointer_rtx, x))
 246         return -1;
 247       /* We are not able to handle correctly all possible memrefs containing
 248          stack pointer, so this check is necessary.  */
 249       if (stack_memref_p (x))
 250         {
 251           d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
 252           return -1;
 253         }
 254       return 1;
 255     case REG:
 256       /* ??? We want be able to handle non-memory stack pointer
 257          references later.  For now just discard all insns referring to
 258          stack pointer outside mem expressions.  We would probably
 259          want to teach validate_replace to simplify expressions first.
 260
 261          We can't just compare with STACK_POINTER_RTX because the
 262          reference to the stack pointer might be in some other mode.
 263          In particular, an explicit clobber in an asm statement will
 264          result in a QImode clobber.  */
 265       if (REGNO (x) == STACK_POINTER_REGNUM)
 266         return 1;
 267       break;
 268     default:
 269       break;
 270     }
 271   return 0;
 272 }
 273
 274 /* Subroutine of combine_stack_adjustments, called for each basic block.  */
 275
 276 static void
 277 combine_stack_adjustments_for_block (basic_block bb)
 278 {
 279   HOST_WIDE_INT last_sp_adjust = 0;
 280   rtx last_sp_set = NULL_RTX;
 281   struct csa_memlist *memlist = NULL;
 282   rtx insn, next, set;
 283   struct record_stack_memrefs_data data;
 284   bool end_of_block = false;
 285
 286   for (insn = BB_HEAD (bb); !end_of_block ; insn = next)
 287     {
 288       end_of_block = insn == BB_END (bb);
 289       next = NEXT_INSN (insn);
 290
 291       if (! INSN_P (insn))
 292         continue;
 293
 294       set = single_set_for_csa (insn);
 295       if (set)
 296         {
 297           rtx dest = SET_DEST (set);
 298           rtx src = SET_SRC (set);
 299
 300           /* Find constant additions to the stack pointer.  */
 301           if (dest == stack_pointer_rtx
 302               && GET_CODE (src) == PLUS
 303               && XEXP (src, 0) == stack_pointer_rtx
 304               && GET_CODE (XEXP (src, 1)) == CONST_INT)
 305             {
 306               HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
 307
 308               /* If we've not seen an adjustment previously, record
 309                  it now and continue.  */
 310               if (! last_sp_set)
 311                 {
 312                   last_sp_set = insn;
 313                   last_sp_adjust = this_adjust;
 314                   continue;
 315                 }
 316
 317               /* If not all recorded memrefs can be adjusted, or the
 318                  adjustment is now too large for a constant addition,
 319                  we cannot merge the two stack adjustments.
 320
 321                  Also we need to be careful to not move stack pointer
 322                  such that we create stack accesses outside the allocated
 323                  area.  We can combine an allocation into the first insn,
 324                  or a deallocation into the second insn.  We can not
 325                  combine an allocation followed by a deallocation.
 326
 327                  The only somewhat frequent occurrence of the later is when
 328                  a function allocates a stack frame but does not use it.
 329                  For this case, we would need to analyze rtl stream to be
 330                  sure that allocated area is really unused.  This means not
 331                  only checking the memory references, but also all registers
 332                  or global memory references possibly containing a stack
 333                  frame address.
 334
 335                  Perhaps the best way to address this problem is to teach
 336                  gcc not to allocate stack for objects never used.  */
 337
 338               /* Combine an allocation into the first instruction.  */
 339               if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
 340                 {
 341                   if (try_apply_stack_adjustment (last_sp_set, memlist,
 342                                                   last_sp_adjust + this_adjust,
 343                                                   this_adjust))
 344                     {
 345                       /* It worked!  */
 346                       delete_insn (insn);
 347                       last_sp_adjust += this_adjust;
 348                       continue;
 349                     }
 350                 }
 351
 352               /* Otherwise we have a deallocation.  Do not combine with
 353                  a previous allocation.  Combine into the second insn.  */
 354               else if (STACK_GROWS_DOWNWARD
 355                        ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
 356                 {
 357                   if (try_apply_stack_adjustment (insn, memlist,
 358                                                   last_sp_adjust + this_adjust,
 359                                                   -last_sp_adjust))
 360                     {
 361                       /* It worked!  */
 362                       delete_insn (last_sp_set);
 363                       last_sp_set = insn;
 364                       last_sp_adjust += this_adjust;
 365                       free_csa_memlist (memlist);
 366                       memlist = NULL;
 367                       continue;
 368                     }
 369                 }
 370
 371               /* Combination failed.  Restart processing from here.  If
 372                  deallocation+allocation conspired to cancel, we can
 373                  delete the old deallocation insn.  */
 374               if (last_sp_set && last_sp_adjust == 0)
 375                 delete_insn (insn);
 376               free_csa_memlist (memlist);
 377               memlist = NULL;
 378               last_sp_set = insn;
 379               last_sp_adjust = this_adjust;
 380               continue;
 381             }
 382
 383           /* Find a predecrement of exactly the previous adjustment and
 384              turn it into a direct store.  Obviously we can't do this if
 385              there were any intervening uses of the stack pointer.  */
 386           if (memlist == NULL
 387               && MEM_P (dest)
 388               && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
 389                    && (last_sp_adjust
 390                        == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
 391                   || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
 392                       && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
 393                       && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
 394                       && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
 395                           == CONST_INT)
 396                       && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
 397                           == -last_sp_adjust)))
 398               && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
 399               && ! reg_mentioned_p (stack_pointer_rtx, src)
 400               && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
 401               && validate_change (insn, &SET_DEST (set),
 402                                   replace_equiv_address (dest,
 403                                                          stack_pointer_rtx),
 404                                   0))
 405             {
 406               delete_insn (last_sp_set);
 407               free_csa_memlist (memlist);
 408               memlist = NULL;
 409               last_sp_set = NULL_RTX;
 410               last_sp_adjust = 0;
 411               continue;
 412             }
 413         }
 414
 415       data.insn = insn;
 416       data.memlist = memlist;
 417       if (!CALL_P (insn) && last_sp_set
 418           && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
 419         {
 420            memlist = data.memlist;
 421            continue;
 422         }
 423       memlist = data.memlist;
 424
 425       /* Otherwise, we were not able to process the instruction.
 426          Do not continue collecting data across such a one.  */
 427       if (last_sp_set
 428           && (CALL_P (insn)
 429               || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
 430         {
 431           if (last_sp_set && last_sp_adjust == 0)
 432             delete_insn (last_sp_set);
 433           free_csa_memlist (memlist);
 434           memlist = NULL;
 435           last_sp_set = NULL_RTX;
 436           last_sp_adjust = 0;
 437         }
 438     }
 439
 440   if (last_sp_set && last_sp_adjust == 0)
 441     delete_insn (last_sp_set);
 442
 443   if (memlist)
 444     free_csa_memlist (memlist);
 445 }
 446 \f
 447
 448 static bool
 449 gate_handle_stack_adjustments (void)
 450 {
 451   return (optimize > 0);
 452 }
 453
 454 static unsigned int
 455 rest_of_handle_stack_adjustments (void)
 456 {
 457   life_analysis (PROP_POSTRELOAD);
 458   cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_UPDATE_LIFE
 459                | (flag_crossjumping ? CLEANUP_CROSSJUMP : 0));
 460
 461   /* This is kind of a heuristic.  We need to run combine_stack_adjustments
 462      even for machines with possibly nonzero RETURN_POPS_ARGS
 463      and ACCUMULATE_OUTGOING_ARGS.  We expect that only ports having
 464      push instructions will have popping returns.  */
 465 #ifndef PUSH_ROUNDING
 466   if (!ACCUMULATE_OUTGOING_ARGS)
 467 #endif
 468     combine_stack_adjustments ();
 469   return 0;
 470 }
 471
 472 struct tree_opt_pass pass_stack_adjustments =
 473 {
 474   "csa",                                /* name */
 475   gate_handle_stack_adjustments,        /* gate */
 476   rest_of_handle_stack_adjustments,     /* execute */
 477   NULL,                                 /* sub */
 478   NULL,                                 /* next */
 479   0,                                    /* static_pass_number */
 480   0,                                    /* tv_id */
 481   0,                                    /* properties_required */
 482   0,                                    /* properties_provided */
 483   0,                                    /* properties_destroyed */
 484   0,                                    /* todo_flags_start */
 485   TODO_dump_func |
 486   TODO_ggc_collect,                     /* todo_flags_finish */
 487   0                                     /* letter */
 488 };
 489