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