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