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, 2012 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 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 /* If INSN has a REG_ARGS_SIZE note, move it to LAST. 300 AFTER is true iff LAST follows INSN in the instruction stream. */ 301 302 static void 303 maybe_move_args_size_note (rtx last, rtx insn, bool after) 304 { 305 rtx note, last_note; 306 307 note = find_reg_note (insn, REG_ARGS_SIZE, NULL_RTX); 308 if (note == NULL) 309 return; 310 311 last_note = find_reg_note (last, REG_ARGS_SIZE, NULL_RTX); 312 if (last_note) 313 { 314 /* The ARGS_SIZE notes are *not* cumulative. They represent an 315 absolute value, and the "most recent" note wins. */ 316 if (!after) 317 XEXP (last_note, 0) = XEXP (note, 0); 318 } 319 else 320 add_reg_note (last, REG_ARGS_SIZE, XEXP (note, 0)); 321 } 322 323 /* Return the next (or previous) active insn within BB. */ 324 325 static rtx 326 prev_active_insn_bb (basic_block bb, rtx insn) 327 { 328 for (insn = PREV_INSN (insn); 329 insn != PREV_INSN (BB_HEAD (bb)); 330 insn = PREV_INSN (insn)) 331 if (active_insn_p (insn)) 332 return insn; 333 return NULL_RTX; 334 } 335 336 static rtx 337 next_active_insn_bb (basic_block bb, rtx insn) 338 { 339 for (insn = NEXT_INSN (insn); 340 insn != NEXT_INSN (BB_END (bb)); 341 insn = NEXT_INSN (insn)) 342 if (active_insn_p (insn)) 343 return insn; 344 return NULL_RTX; 345 } 346 347 /* If INSN has a REG_ARGS_SIZE note, if possible move it to PREV. Otherwise 348 search for a nearby candidate within BB where we can stick the note. */ 349 350 static void 351 force_move_args_size_note (basic_block bb, rtx prev, rtx insn) 352 { 353 rtx note, test, next_candidate, prev_candidate; 354 355 /* If PREV exists, tail-call to the logic in the other function. */ 356 if (prev) 357 { 358 maybe_move_args_size_note (prev, insn, false); 359 return; 360 } 361 362 /* First, make sure there's anything that needs doing. */ 363 note = find_reg_note (insn, REG_ARGS_SIZE, NULL_RTX); 364 if (note == NULL) 365 return; 366 367 /* We need to find a spot between the previous and next exception points 368 where we can place the note and "properly" deallocate the arguments. */ 369 next_candidate = prev_candidate = NULL; 370 371 /* It is often the case that we have insns in the order: 372 call 373 add sp (previous deallocation) 374 sub sp (align for next arglist) 375 push arg 376 and the add/sub cancel. Therefore we begin by searching forward. */ 377 378 test = insn; 379 while ((test = next_active_insn_bb (bb, test)) != NULL) 380 { 381 /* Found an existing note: nothing to do. */ 382 if (find_reg_note (test, REG_ARGS_SIZE, NULL_RTX)) 383 return; 384 /* Found something that affects unwinding. Stop searching. */ 385 if (CALL_P (test) || !insn_nothrow_p (test)) 386 break; 387 if (next_candidate == NULL) 388 next_candidate = test; 389 } 390 391 test = insn; 392 while ((test = prev_active_insn_bb (bb, test)) != NULL) 393 { 394 rtx tnote; 395 /* Found a place that seems logical to adjust the stack. */ 396 tnote = find_reg_note (test, REG_ARGS_SIZE, NULL_RTX); 397 if (tnote) 398 { 399 XEXP (tnote, 0) = XEXP (note, 0); 400 return; 401 } 402 if (prev_candidate == NULL) 403 prev_candidate = test; 404 /* Found something that affects unwinding. Stop searching. */ 405 if (CALL_P (test) || !insn_nothrow_p (test)) 406 break; 407 } 408 409 if (prev_candidate) 410 test = prev_candidate; 411 else if (next_candidate) 412 test = next_candidate; 413 else 414 { 415 /* ??? We *must* have a place, lest we ICE on the lost adjustment. 416 Options are: dummy clobber insn, nop, or prevent the removal of 417 the sp += 0 insn. */ 418 /* TODO: Find another way to indicate to the dwarf2 code that we 419 have not in fact lost an adjustment. */ 420 test = emit_insn_before (gen_rtx_CLOBBER (VOIDmode, const0_rtx), insn); 421 } 422 add_reg_note (test, REG_ARGS_SIZE, XEXP (note, 0)); 423 } 424 425 /* Subroutine of combine_stack_adjustments, called for each basic block. */ 426 427 static void 428 combine_stack_adjustments_for_block (basic_block bb) 429 { 430 HOST_WIDE_INT last_sp_adjust = 0; 431 rtx last_sp_set = NULL_RTX; 432 rtx last2_sp_set = NULL_RTX; 433 struct csa_reflist *reflist = NULL; 434 rtx insn, next, set; 435 struct record_stack_refs_data data; 436 bool end_of_block = false; 437 438 for (insn = BB_HEAD (bb); !end_of_block ; insn = next) 439 { 440 end_of_block = insn == BB_END (bb); 441 next = NEXT_INSN (insn); 442 443 if (! INSN_P (insn)) 444 continue; 445 446 set = single_set_for_csa (insn); 447 if (set) 448 { 449 rtx dest = SET_DEST (set); 450 rtx src = SET_SRC (set); 451 452 /* Find constant additions to the stack pointer. */ 453 if (dest == stack_pointer_rtx 454 && GET_CODE (src) == PLUS 455 && XEXP (src, 0) == stack_pointer_rtx 456 && CONST_INT_P (XEXP (src, 1))) 457 { 458 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1)); 459 460 /* If we've not seen an adjustment previously, record 461 it now and continue. */ 462 if (! last_sp_set) 463 { 464 last_sp_set = insn; 465 last_sp_adjust = this_adjust; 466 continue; 467 } 468 469 /* If not all recorded refs can be adjusted, or the 470 adjustment is now too large for a constant addition, 471 we cannot merge the two stack adjustments. 472 473 Also we need to be careful to not move stack pointer 474 such that we create stack accesses outside the allocated 475 area. We can combine an allocation into the first insn, 476 or a deallocation into the second insn. We can not 477 combine an allocation followed by a deallocation. 478 479 The only somewhat frequent occurrence of the later is when 480 a function allocates a stack frame but does not use it. 481 For this case, we would need to analyze rtl stream to be 482 sure that allocated area is really unused. This means not 483 only checking the memory references, but also all registers 484 or global memory references possibly containing a stack 485 frame address. 486 487 Perhaps the best way to address this problem is to teach 488 gcc not to allocate stack for objects never used. */ 489 490 /* Combine an allocation into the first instruction. */ 491 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0) 492 { 493 if (try_apply_stack_adjustment (last_sp_set, reflist, 494 last_sp_adjust + this_adjust, 495 this_adjust)) 496 { 497 /* It worked! */ 498 maybe_move_args_size_note (last_sp_set, insn, false); 499 delete_insn (insn); 500 last_sp_adjust += this_adjust; 501 continue; 502 } 503 } 504 505 /* Otherwise we have a deallocation. Do not combine with 506 a previous allocation. Combine into the second insn. */ 507 else if (STACK_GROWS_DOWNWARD 508 ? last_sp_adjust >= 0 : last_sp_adjust <= 0) 509 { 510 if (try_apply_stack_adjustment (insn, reflist, 511 last_sp_adjust + this_adjust, 512 -last_sp_adjust)) 513 { 514 /* It worked! */ 515 maybe_move_args_size_note (insn, last_sp_set, true); 516 delete_insn (last_sp_set); 517 last_sp_set = insn; 518 last_sp_adjust += this_adjust; 519 free_csa_reflist (reflist); 520 reflist = NULL; 521 continue; 522 } 523 } 524 525 /* Combination failed. Restart processing from here. If 526 deallocation+allocation conspired to cancel, we can 527 delete the old deallocation insn. */ 528 if (last_sp_set) 529 { 530 if (last_sp_adjust == 0) 531 { 532 maybe_move_args_size_note (insn, last_sp_set, true); 533 delete_insn (last_sp_set); 534 } 535 else 536 last2_sp_set = last_sp_set; 537 } 538 free_csa_reflist (reflist); 539 reflist = NULL; 540 last_sp_set = insn; 541 last_sp_adjust = this_adjust; 542 continue; 543 } 544 545 /* Find a store with pre-(dec|inc)rement or pre-modify of exactly 546 the previous adjustment and turn it into a simple store. This 547 is equivalent to anticipating the stack adjustment so this must 548 be an allocation. */ 549 if (MEM_P (dest) 550 && ((STACK_GROWS_DOWNWARD 551 ? (GET_CODE (XEXP (dest, 0)) == PRE_DEC 552 && last_sp_adjust 553 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))) 554 : (GET_CODE (XEXP (dest, 0)) == PRE_INC 555 && last_sp_adjust 556 == -(HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest)))) 557 || ((STACK_GROWS_DOWNWARD 558 ? last_sp_adjust >= 0 : last_sp_adjust <= 0) 559 && GET_CODE (XEXP (dest, 0)) == PRE_MODIFY 560 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS 561 && XEXP (XEXP (XEXP (dest, 0), 1), 0) 562 == stack_pointer_rtx 563 && GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1)) 564 == CONST_INT 565 && INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1)) 566 == -last_sp_adjust)) 567 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx 568 && !reg_mentioned_p (stack_pointer_rtx, src) 569 && memory_address_p (GET_MODE (dest), stack_pointer_rtx) 570 && try_apply_stack_adjustment (insn, reflist, 0, 571 -last_sp_adjust)) 572 { 573 if (last2_sp_set) 574 maybe_move_args_size_note (last2_sp_set, last_sp_set, false); 575 else 576 maybe_move_args_size_note (insn, last_sp_set, true); 577 delete_insn (last_sp_set); 578 free_csa_reflist (reflist); 579 reflist = NULL; 580 last_sp_set = NULL_RTX; 581 last_sp_adjust = 0; 582 continue; 583 } 584 } 585 586 data.insn = insn; 587 data.reflist = reflist; 588 if (!CALL_P (insn) && last_sp_set 589 && !for_each_rtx (&PATTERN (insn), record_stack_refs, &data)) 590 { 591 reflist = data.reflist; 592 continue; 593 } 594 reflist = data.reflist; 595 596 /* Otherwise, we were not able to process the instruction. 597 Do not continue collecting data across such a one. */ 598 if (last_sp_set 599 && (CALL_P (insn) 600 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn)))) 601 { 602 if (last_sp_set && last_sp_adjust == 0) 603 { 604 force_move_args_size_note (bb, last2_sp_set, last_sp_set); 605 delete_insn (last_sp_set); 606 } 607 free_csa_reflist (reflist); 608 reflist = NULL; 609 last2_sp_set = NULL_RTX; 610 last_sp_set = NULL_RTX; 611 last_sp_adjust = 0; 612 } 613 } 614 615 if (last_sp_set && last_sp_adjust == 0) 616 { 617 force_move_args_size_note (bb, last2_sp_set, last_sp_set); 618 delete_insn (last_sp_set); 619 } 620 621 if (reflist) 622 free_csa_reflist (reflist); 623 } 624 625 626 static bool 627 gate_handle_stack_adjustments (void) 628 { 629 return flag_combine_stack_adjustments; 630 } 631 632 static unsigned int 633 rest_of_handle_stack_adjustments (void) 634 { 635 cleanup_cfg (flag_crossjumping ? CLEANUP_CROSSJUMP : 0); 636 637 /* This is kind of a heuristic. We need to run combine_stack_adjustments 638 even for machines with possibly nonzero TARGET_RETURN_POPS_ARGS 639 and ACCUMULATE_OUTGOING_ARGS. We expect that only ports having 640 push instructions will have popping returns. */ 641 #ifndef PUSH_ROUNDING 642 if (!ACCUMULATE_OUTGOING_ARGS) 643 #endif 644 { 645 df_note_add_problem (); 646 df_analyze (); 647 combine_stack_adjustments (); 648 } 649 return 0; 650 } 651 652 struct rtl_opt_pass pass_stack_adjustments = 653 { 654 { 655 RTL_PASS, 656 "csa", /* name */ 657 gate_handle_stack_adjustments, /* gate */ 658 rest_of_handle_stack_adjustments, /* execute */ 659 NULL, /* sub */ 660 NULL, /* next */ 661 0, /* static_pass_number */ 662 TV_COMBINE_STACK_ADJUST, /* tv_id */ 663 0, /* properties_required */ 664 0, /* properties_provided */ 665 0, /* properties_destroyed */ 666 0, /* todo_flags_start */ 667 TODO_df_finish | TODO_verify_rtl_sharing | 668 TODO_ggc_collect, /* todo_flags_finish */ 669 } 670 }; 671