gcc/combine-stack-adj.c

   1 /* Combine stack adjustments.
   2    Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
   3    1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
   4    Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  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 "df.h"
  59 #include "except.h"
  60 #include "toplev.h"
  61 #include "reload.h"
  62 #include "timevar.h"
  63 #include "tree-pass.h"
  64
  65 \f
  66 /* Turn STACK_GROWS_DOWNWARD into a boolean.  */
  67 #ifdef STACK_GROWS_DOWNWARD
  68 #undef STACK_GROWS_DOWNWARD
  69 #define STACK_GROWS_DOWNWARD 1
  70 #else
  71 #define STACK_GROWS_DOWNWARD 0
  72 #endif
  73
  74 /* This structure records two kinds of stack references between stack
  75    adjusting instructions: stack references in memory addresses for
  76    regular insns and all stack references for debug insns.  */
  77
  78 struct csa_reflist
  79 {
  80   HOST_WIDE_INT sp_offset;
  81   rtx insn, *ref;
  82   struct csa_reflist *next;
  83 };
  84
  85 static int stack_memref_p (rtx);
  86 static rtx single_set_for_csa (rtx);
  87 static void free_csa_reflist (struct csa_reflist *);
  88 static struct csa_reflist *record_one_stack_ref (rtx, rtx *,
  89                                                  struct csa_reflist *);
  90 static int try_apply_stack_adjustment (rtx, struct csa_reflist *,
  91                                        HOST_WIDE_INT, HOST_WIDE_INT);
  92 static void combine_stack_adjustments_for_block (basic_block);
  93 static int record_stack_refs (rtx *, void *);
  94
  95
  96 /* Main entry point for stack adjustment combination.  */
  97
  98 static void
  99 combine_stack_adjustments (void)
 100 {
 101   basic_block bb;
 102
 103   FOR_EACH_BB (bb)
 104     combine_stack_adjustments_for_block (bb);
 105 }
 106
 107 /* Recognize a MEM of the form (sp) or (plus sp const).  */
 108
 109 static int
 110 stack_memref_p (rtx x)
 111 {
 112   if (!MEM_P (x))
 113     return 0;
 114   x = XEXP (x, 0);
 115
 116   if (x == stack_pointer_rtx)
 117     return 1;
 118   if (GET_CODE (x) == PLUS
 119       && XEXP (x, 0) == stack_pointer_rtx
 120       && CONST_INT_P (XEXP (x, 1)))
 121     return 1;
 122
 123   return 0;
 124 }
 125
 126 /* Recognize either normal single_set or the hack in i386.md for
 127    tying fp and sp adjustments.  */
 128
 129 static rtx
 130 single_set_for_csa (rtx insn)
 131 {
 132   int i;
 133   rtx tmp = single_set (insn);
 134   if (tmp)
 135     return tmp;
 136
 137   if (!NONJUMP_INSN_P (insn)
 138       || GET_CODE (PATTERN (insn)) != PARALLEL)
 139     return NULL_RTX;
 140
 141   tmp = PATTERN (insn);
 142   if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
 143     return NULL_RTX;
 144
 145   for (i = 1; i < XVECLEN (tmp, 0); ++i)
 146     {
 147       rtx this_rtx = XVECEXP (tmp, 0, i);
 148
 149       /* The special case is allowing a no-op set.  */
 150       if (GET_CODE (this_rtx) == SET
 151           && SET_SRC (this_rtx) == SET_DEST (this_rtx))
 152         ;
 153       else if (GET_CODE (this_rtx) != CLOBBER
 154                && GET_CODE (this_rtx) != USE)
 155         return NULL_RTX;
 156     }
 157
 158   return XVECEXP (tmp, 0, 0);
 159 }
 160
 161 /* Free the list of csa_reflist nodes.  */
 162
 163 static void
 164 free_csa_reflist (struct csa_reflist *reflist)
 165 {
 166   struct csa_reflist *next;
 167   for (; reflist ; reflist = next)
 168     {
 169       next = reflist->next;
 170       free (reflist);
 171     }
 172 }
 173
 174 /* Create a new csa_reflist node from the given stack reference.
 175    It is already known that the reference is either a MEM satisfying the
 176    predicate stack_memref_p or a REG representing the stack pointer.  */
 177
 178 static struct csa_reflist *
 179 record_one_stack_ref (rtx insn, rtx *ref, struct csa_reflist *next_reflist)
 180 {
 181   struct csa_reflist *ml;
 182
 183   ml = XNEW (struct csa_reflist);
 184
 185   if (REG_P (*ref) || XEXP (*ref, 0) == stack_pointer_rtx)
 186     ml->sp_offset = 0;
 187   else
 188     ml->sp_offset = INTVAL (XEXP (XEXP (*ref, 0), 1));
 189
 190   ml->insn = insn;
 191   ml->ref = ref;
 192   ml->next = next_reflist;
 193
 194   return ml;
 195 }
 196
 197 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
 198    as each of the memories and stack references in REFLIST.  Return true
 199    on success.  */
 200
 201 static int
 202 try_apply_stack_adjustment (rtx insn, struct csa_reflist *reflist,
 203                             HOST_WIDE_INT new_adjust, HOST_WIDE_INT delta)
 204 {
 205   struct csa_reflist *ml;
 206   rtx set;
 207
 208   set = single_set_for_csa (insn);
 209   if (MEM_P (SET_DEST (set)))
 210     validate_change (insn, &SET_DEST (set),
 211                      replace_equiv_address (SET_DEST (set), stack_pointer_rtx),
 212                      1);
 213   else
 214     validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
 215
 216   for (ml = reflist; ml ; ml = ml->next)
 217     {
 218       rtx new_addr = plus_constant (stack_pointer_rtx, ml->sp_offset - delta);
 219       rtx new_val;
 220
 221       if (MEM_P (*ml->ref))
 222         new_val = replace_equiv_address_nv (*ml->ref, new_addr);
 223       else if (GET_MODE (*ml->ref) == GET_MODE (stack_pointer_rtx))
 224         new_val = new_addr;
 225       else
 226         new_val = lowpart_subreg (GET_MODE (*ml->ref), new_addr,
 227                                   GET_MODE (new_addr));
 228       validate_change (ml->insn, ml->ref, new_val, 1);
 229     }
 230
 231   if (apply_change_group ())
 232     {
 233       /* Succeeded.  Update our knowledge of the stack references.  */
 234       for (ml = reflist; ml ; ml = ml->next)
 235         ml->sp_offset -= delta;
 236
 237       return 1;
 238     }
 239   else
 240     return 0;
 241 }
 242
 243 /* Called via for_each_rtx and used to record all stack memory and other
 244    references in the insn and discard all other stack pointer references.  */
 245 struct record_stack_refs_data
 246 {
 247   rtx insn;
 248   struct csa_reflist *reflist;
 249 };
 250
 251 static int
 252 record_stack_refs (rtx *xp, void *data)
 253 {
 254   rtx x = *xp;
 255   struct record_stack_refs_data *d =
 256     (struct record_stack_refs_data *) data;
 257   if (!x)
 258     return 0;
 259   switch (GET_CODE (x))
 260     {
 261     case MEM:
 262       if (!reg_mentioned_p (stack_pointer_rtx, x))
 263         return -1;
 264       /* We are not able to handle correctly all possible memrefs containing
 265          stack pointer, so this check is necessary.  */
 266       if (stack_memref_p (x))
 267         {
 268           d->reflist = record_one_stack_ref (d->insn, xp, d->reflist);
 269           return -1;
 270         }
 271       /* Try harder for DEBUG_INSNs, handle e.g. (mem (mem (sp + 16) + 4).  */
 272       return !DEBUG_INSN_P (d->insn);
 273     case REG:
 274       /* ??? We want be able to handle non-memory stack pointer
 275          references later.  For now just discard all insns referring to
 276          stack pointer outside mem expressions.  We would probably
 277          want to teach validate_replace to simplify expressions first.
 278
 279          We can't just compare with STACK_POINTER_RTX because the
 280          reference to the stack pointer might be in some other mode.
 281          In particular, an explicit clobber in an asm statement will
 282          result in a QImode clobber.
 283
 284          In DEBUG_INSNs, we want to replace all occurrences, otherwise
 285          they will cause -fcompare-debug failures.  */
 286       if (REGNO (x) == STACK_POINTER_REGNUM)
 287         {
 288           if (!DEBUG_INSN_P (d->insn))
 289             return 1;
 290           d->reflist = record_one_stack_ref (d->insn, xp, d->reflist);
 291           return -1;
 292         }
 293       break;
 294     default:
 295       break;
 296     }
 297   return 0;
 298 }
 299
 300 /* Adjust or create REG_FRAME_RELATED_EXPR note when merging a stack
 301    adjustment into a frame related insn.  */
 302
 303 static void
 304 adjust_frame_related_expr (rtx last_sp_set, rtx insn,
 305                            HOST_WIDE_INT this_adjust)
 306 {
 307   rtx note = find_reg_note (last_sp_set, REG_FRAME_RELATED_EXPR, NULL_RTX);
 308   rtx new_expr = NULL_RTX;
 309
 310   if (note == NULL_RTX && RTX_FRAME_RELATED_P (insn))
 311     return;
 312
 313   if (note
 314       && GET_CODE (XEXP (note, 0)) == SEQUENCE
 315       && XVECLEN (XEXP (note, 0), 0) >= 2)
 316     {
 317       rtx expr = XEXP (note, 0);
 318       rtx last = XVECEXP (expr, 0, XVECLEN (expr, 0) - 1);
 319       int i;
 320
 321       if (GET_CODE (last) == SET
 322           && RTX_FRAME_RELATED_P (last) == RTX_FRAME_RELATED_P (insn)
 323           && SET_DEST (last) == stack_pointer_rtx
 324           && GET_CODE (SET_SRC (last)) == PLUS
 325           && XEXP (SET_SRC (last), 0) == stack_pointer_rtx
 326           && CONST_INT_P (XEXP (SET_SRC (last), 1)))
 327         {
 328           XEXP (SET_SRC (last), 1)
 329             = GEN_INT (INTVAL (XEXP (SET_SRC (last), 1)) + this_adjust);
 330           return;
 331         }
 332
 333       new_expr = gen_rtx_SEQUENCE (VOIDmode,
 334                                    rtvec_alloc (XVECLEN (expr, 0) + 1));
 335       for (i = 0; i < XVECLEN (expr, 0); i++)
 336         XVECEXP (new_expr, 0, i) = XVECEXP (expr, 0, i);
 337     }
 338   else
 339     {
 340       new_expr = gen_rtx_SEQUENCE (VOIDmode, rtvec_alloc (2));
 341       if (note)
 342         XVECEXP (new_expr, 0, 0) = XEXP (note, 0);
 343       else
 344         {
 345           rtx expr = copy_rtx (single_set_for_csa (last_sp_set));
 346
 347           XEXP (SET_SRC (expr), 1)
 348             = GEN_INT (INTVAL (XEXP (SET_SRC (expr), 1)) - this_adjust);
 349           RTX_FRAME_RELATED_P (expr) = 1;
 350           XVECEXP (new_expr, 0, 0) = expr;
 351         }
 352     }
 353
 354   XVECEXP (new_expr, 0, XVECLEN (new_expr, 0) - 1)
 355     = copy_rtx (single_set_for_csa (insn));
 356   RTX_FRAME_RELATED_P (XVECEXP (new_expr, 0, XVECLEN (new_expr, 0) - 1))
 357     = RTX_FRAME_RELATED_P (insn);
 358   if (note)
 359     XEXP (note, 0) = new_expr;
 360   else
 361     add_reg_note (last_sp_set, REG_FRAME_RELATED_EXPR, new_expr);
 362 }
 363
 364 /* Subroutine of combine_stack_adjustments, called for each basic block.  */
 365
 366 static void
 367 combine_stack_adjustments_for_block (basic_block bb)
 368 {
 369   HOST_WIDE_INT last_sp_adjust = 0;
 370   rtx last_sp_set = NULL_RTX;
 371   struct csa_reflist *reflist = NULL;
 372   rtx insn, next, set;
 373   struct record_stack_refs_data data;
 374   bool end_of_block = false;
 375
 376   for (insn = BB_HEAD (bb); !end_of_block ; insn = next)
 377     {
 378       end_of_block = insn == BB_END (bb);
 379       next = NEXT_INSN (insn);
 380
 381       if (! INSN_P (insn))
 382         continue;
 383
 384       set = single_set_for_csa (insn);
 385       if (set)
 386         {
 387           rtx dest = SET_DEST (set);
 388           rtx src = SET_SRC (set);
 389
 390           /* Find constant additions to the stack pointer.  */
 391           if (dest == stack_pointer_rtx
 392               && GET_CODE (src) == PLUS
 393               && XEXP (src, 0) == stack_pointer_rtx
 394               && CONST_INT_P (XEXP (src, 1)))
 395             {
 396               HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
 397
 398               /* If we've not seen an adjustment previously, record
 399                  it now and continue.  */
 400               if (! last_sp_set)
 401                 {
 402                   last_sp_set = insn;
 403                   last_sp_adjust = this_adjust;
 404                   continue;
 405                 }
 406
 407               /* If not all recorded refs can be adjusted, or the
 408                  adjustment is now too large for a constant addition,
 409                  we cannot merge the two stack adjustments.
 410
 411                  Also we need to be careful to not move stack pointer
 412                  such that we create stack accesses outside the allocated
 413                  area.  We can combine an allocation into the first insn,
 414                  or a deallocation into the second insn.  We can not
 415                  combine an allocation followed by a deallocation.
 416
 417                  The only somewhat frequent occurrence of the later is when
 418                  a function allocates a stack frame but does not use it.
 419                  For this case, we would need to analyze rtl stream to be
 420                  sure that allocated area is really unused.  This means not
 421                  only checking the memory references, but also all registers
 422                  or global memory references possibly containing a stack
 423                  frame address.
 424
 425                  Perhaps the best way to address this problem is to teach
 426                  gcc not to allocate stack for objects never used.  */
 427
 428               /* Combine an allocation into the first instruction.  */
 429               if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
 430                 {
 431                   if (try_apply_stack_adjustment (last_sp_set, reflist,
 432                                                   last_sp_adjust + this_adjust,
 433                                                   this_adjust))
 434                     {
 435                       if (RTX_FRAME_RELATED_P (last_sp_set))
 436                         adjust_frame_related_expr (last_sp_set, insn,
 437                                                    this_adjust);
 438                       /* It worked!  */
 439                       delete_insn (insn);
 440                       last_sp_adjust += this_adjust;
 441                       continue;
 442                     }
 443                 }
 444
 445               /* Otherwise we have a deallocation.  Do not combine with
 446                  a previous allocation.  Combine into the second insn.  */
 447               else if (STACK_GROWS_DOWNWARD
 448                        ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
 449                 {
 450                   if (try_apply_stack_adjustment (insn, reflist,
 451                                                   last_sp_adjust + this_adjust,
 452                                                   -last_sp_adjust))
 453                     {
 454                       /* It worked!  */
 455                       delete_insn (last_sp_set);
 456                       last_sp_set = insn;
 457                       last_sp_adjust += this_adjust;
 458                       free_csa_reflist (reflist);
 459                       reflist = NULL;
 460                       continue;
 461                     }
 462                 }
 463
 464               /* Combination failed.  Restart processing from here.  If
 465                  deallocation+allocation conspired to cancel, we can
 466                  delete the old deallocation insn.  */
 467               if (last_sp_set && last_sp_adjust == 0)
 468                 delete_insn (last_sp_set);
 469               free_csa_reflist (reflist);
 470               reflist = NULL;
 471               last_sp_set = insn;
 472               last_sp_adjust = this_adjust;
 473               continue;
 474             }
 475
 476           /* Find a store with pre-(dec|inc)rement or pre-modify of exactly
 477              the previous adjustment and turn it into a simple store.  This
 478              is equivalent to anticipating the stack adjustment so this must
 479              be an allocation.  */
 480           if (MEM_P (dest)
 481               && ((STACK_GROWS_DOWNWARD
 482                    ? (GET_CODE (XEXP (dest, 0)) == PRE_DEC
 483                       && last_sp_adjust
 484                          == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest)))
 485                    : (GET_CODE (XEXP (dest, 0)) == PRE_INC
 486                       && last_sp_adjust
 487                          == -(HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
 488                   || ((STACK_GROWS_DOWNWARD
 489                        ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
 490                       && GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
 491                       && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
 492                       && XEXP (XEXP (XEXP (dest, 0), 1), 0)
 493                          == stack_pointer_rtx
 494                       && GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
 495                          == CONST_INT
 496                       && INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
 497                          == -last_sp_adjust))
 498               && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
 499               && !reg_mentioned_p (stack_pointer_rtx, src)
 500               && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
 501               && try_apply_stack_adjustment (insn, reflist, 0,
 502                                              -last_sp_adjust))
 503             {
 504               delete_insn (last_sp_set);
 505               free_csa_reflist (reflist);
 506               reflist = NULL;
 507               last_sp_set = NULL_RTX;
 508               last_sp_adjust = 0;
 509               continue;
 510             }
 511         }
 512
 513       data.insn = insn;
 514       data.reflist = reflist;
 515       if (!CALL_P (insn) && last_sp_set
 516           && !for_each_rtx (&PATTERN (insn), record_stack_refs, &data))
 517         {
 518            reflist = data.reflist;
 519            continue;
 520         }
 521       reflist = data.reflist;
 522
 523       /* Otherwise, we were not able to process the instruction.
 524          Do not continue collecting data across such a one.  */
 525       if (last_sp_set
 526           && (CALL_P (insn)
 527               || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
 528         {
 529           if (last_sp_set && last_sp_adjust == 0)
 530             delete_insn (last_sp_set);
 531           free_csa_reflist (reflist);
 532           reflist = NULL;
 533           last_sp_set = NULL_RTX;
 534           last_sp_adjust = 0;
 535         }
 536     }
 537
 538   if (last_sp_set && last_sp_adjust == 0)
 539     delete_insn (last_sp_set);
 540
 541   if (reflist)
 542     free_csa_reflist (reflist);
 543 }
 544 \f
 545
 546 static bool
 547 gate_handle_stack_adjustments (void)
 548 {
 549   return (optimize > 0);
 550 }
 551
 552 static unsigned int
 553 rest_of_handle_stack_adjustments (void)
 554 {
 555   cleanup_cfg (flag_crossjumping ? CLEANUP_CROSSJUMP : 0);
 556
 557   /* This is kind of a heuristic.  We need to run combine_stack_adjustments
 558      even for machines with possibly nonzero TARGET_RETURN_POPS_ARGS
 559      and ACCUMULATE_OUTGOING_ARGS.  We expect that only ports having
 560      push instructions will have popping returns.  */
 561 #ifndef PUSH_ROUNDING
 562   if (!ACCUMULATE_OUTGOING_ARGS)
 563 #endif
 564     {
 565       df_note_add_problem ();
 566       df_analyze ();
 567       combine_stack_adjustments ();
 568     }
 569   return 0;
 570 }
 571
 572 struct rtl_opt_pass pass_stack_adjustments =
 573 {
 574  {
 575   RTL_PASS,
 576   "csa",                                /* name */
 577   gate_handle_stack_adjustments,        /* gate */
 578   rest_of_handle_stack_adjustments,     /* execute */
 579   NULL,                                 /* sub */
 580   NULL,                                 /* next */
 581   0,                                    /* static_pass_number */
 582   TV_COMBINE_STACK_ADJUST,              /* tv_id */
 583   0,                                    /* properties_required */
 584   0,                                    /* properties_provided */
 585   0,                                    /* properties_destroyed */
 586   0,                                    /* todo_flags_start */
 587   TODO_df_finish | TODO_verify_rtl_sharing |
 588   TODO_dump_func |
 589   TODO_ggc_collect,                     /* todo_flags_finish */
 590  }
 591 };