1 /* Combine stack adjustments. 2 Copyright (C) 1987-2013 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it under 7 the terms of the GNU General Public License as published by the Free 8 Software Foundation; either version 3, or (at your option) any later 9 version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12 WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 /* Track stack adjustments and stack memory references. Attempt to 21 reduce the number of stack adjustments by back-propagating across 22 the memory references. 23 24 This is intended primarily for use with targets that do not define 25 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to 26 targets that define PREFERRED_STACK_BOUNDARY more aligned than 27 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed 28 (e.g. x86 fp regs) which would ordinarily have to be implemented 29 as a sub/mov pair due to restrictions in calls.c. 30 31 Propagation stops when any of the insns that need adjusting are 32 (a) no longer valid because we've exceeded their range, (b) a 33 non-trivial push instruction, or (c) a call instruction. 34 35 Restriction B is based on the assumption that push instructions 36 are smaller or faster. If a port really wants to remove all 37 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The 38 one exception that is made is for an add immediately followed 39 by a push. */ 40 41 #include "config.h" 42 #include "system.h" 43 #include "coretypes.h" 44 #include "tm.h" 45 #include "rtl.h" 46 #include "tm_p.h" 47 #include "insn-config.h" 48 #include "recog.h" 49 #include "regs.h" 50 #include "hard-reg-set.h" 51 #include "flags.h" 52 #include "function.h" 53 #include "expr.h" 54 #include "basic-block.h" 55 #include "df.h" 56 #include "except.h" 57 #include "reload.h" 58 #include "tree-pass.h" 59 60 61 /* Turn STACK_GROWS_DOWNWARD into a boolean. */ 62 #ifdef STACK_GROWS_DOWNWARD 63 #undef STACK_GROWS_DOWNWARD 64 #define STACK_GROWS_DOWNWARD 1 65 #else 66 #define STACK_GROWS_DOWNWARD 0 67 #endif 68 69 /* This structure records two kinds of stack references between stack 70 adjusting instructions: stack references in memory addresses for 71 regular insns and all stack references for debug insns. */ 72 73 struct csa_reflist 74 { 75 HOST_WIDE_INT sp_offset; 76 rtx insn, *ref; 77 struct csa_reflist *next; 78 }; 79 80 static int stack_memref_p (rtx); 81 static rtx single_set_for_csa (rtx); 82 static void free_csa_reflist (struct csa_reflist *); 83 static struct csa_reflist *record_one_stack_ref (rtx, rtx *, 84 struct csa_reflist *); 85 static int try_apply_stack_adjustment (rtx, struct csa_reflist *, 86 HOST_WIDE_INT, HOST_WIDE_INT); 87 static void combine_stack_adjustments_for_block (basic_block); 88 static int record_stack_refs (rtx *, void *); 89 90 91 /* Main entry point for stack adjustment combination. */ 92 93 static void 94 combine_stack_adjustments (void) 95 { 96 basic_block bb; 97 98 FOR_EACH_BB (bb) 99 combine_stack_adjustments_for_block (bb); 100 } 101 102 /* Recognize a MEM of the form (sp) or (plus sp const). */ 103 104 static int 105 stack_memref_p (rtx x) 106 { 107 if (!MEM_P (x)) 108 return 0; 109 x = XEXP (x, 0); 110 111 if (x == stack_pointer_rtx) 112 return 1; 113 if (GET_CODE (x) == PLUS 114 && XEXP (x, 0) == stack_pointer_rtx 115 && CONST_INT_P (XEXP (x, 1))) 116 return 1; 117 118 return 0; 119 } 120 121 /* Recognize either normal single_set or the hack in i386.md for 122 tying fp and sp adjustments. */ 123 124 static rtx 125 single_set_for_csa (rtx insn) 126 { 127 int i; 128 rtx tmp = single_set (insn); 129 if (tmp) 130 return tmp; 131 132 if (!NONJUMP_INSN_P (insn) 133 || GET_CODE (PATTERN (insn)) != PARALLEL) 134 return NULL_RTX; 135 136 tmp = PATTERN (insn); 137 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET) 138 return NULL_RTX; 139 140 for (i = 1; i < XVECLEN (tmp, 0); ++i) 141 { 142 rtx this_rtx = XVECEXP (tmp, 0, i); 143 144 /* The special case is allowing a no-op set. */ 145 if (GET_CODE (this_rtx) == SET 146 && SET_SRC (this_rtx) == SET_DEST (this_rtx)) 147 ; 148 else if (GET_CODE (this_rtx) != CLOBBER 149 && GET_CODE (this_rtx) != USE) 150 return NULL_RTX; 151 } 152 153 return XVECEXP (tmp, 0, 0); 154 } 155 156 /* Free the list of csa_reflist nodes. */ 157 158 static void 159 free_csa_reflist (struct csa_reflist *reflist) 160 { 161 struct csa_reflist *next; 162 for (; reflist ; reflist = next) 163 { 164 next = reflist->next; 165 free (reflist); 166 } 167 } 168 169 /* Create a new csa_reflist node from the given stack reference. 170 It is already known that the reference is either a MEM satisfying the 171 predicate stack_memref_p or a REG representing the stack pointer. */ 172 173 static struct csa_reflist * 174 record_one_stack_ref (rtx insn, rtx *ref, struct csa_reflist *next_reflist) 175 { 176 struct csa_reflist *ml; 177 178 ml = XNEW (struct csa_reflist); 179 180 if (REG_P (*ref) || XEXP (*ref, 0) == stack_pointer_rtx) 181 ml->sp_offset = 0; 182 else 183 ml->sp_offset = INTVAL (XEXP (XEXP (*ref, 0), 1)); 184 185 ml->insn = insn; 186 ml->ref = ref; 187 ml->next = next_reflist; 188 189 return ml; 190 } 191 192 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well 193 as each of the memories and stack references in REFLIST. Return true 194 on success. */ 195 196 static int 197 try_apply_stack_adjustment (rtx insn, struct csa_reflist *reflist, 198 HOST_WIDE_INT new_adjust, HOST_WIDE_INT delta) 199 { 200 struct csa_reflist *ml; 201 rtx set; 202 203 set = single_set_for_csa (insn); 204 if (MEM_P (SET_DEST (set))) 205 validate_change (insn, &SET_DEST (set), 206 replace_equiv_address (SET_DEST (set), stack_pointer_rtx), 207 1); 208 else 209 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1); 210 211 for (ml = reflist; ml ; ml = ml->next) 212 { 213 rtx new_addr = plus_constant (Pmode, stack_pointer_rtx, 214 ml->sp_offset - delta); 215 rtx new_val; 216 217 if (MEM_P (*ml->ref)) 218 new_val = replace_equiv_address_nv (*ml->ref, new_addr); 219 else if (GET_MODE (*ml->ref) == GET_MODE (stack_pointer_rtx)) 220 new_val = new_addr; 221 else 222 new_val = lowpart_subreg (GET_MODE (*ml->ref), new_addr, 223 GET_MODE (new_addr)); 224 validate_change (ml->insn, ml->ref, new_val, 1); 225 } 226 227 if (apply_change_group ()) 228 { 229 /* Succeeded. Update our knowledge of the stack references. */ 230 for (ml = reflist; ml ; ml = ml->next) 231 ml->sp_offset -= delta; 232 233 return 1; 234 } 235 else 236 return 0; 237 } 238 239 /* Called via for_each_rtx and used to record all stack memory and other 240 references in the insn and discard all other stack pointer references. */ 241 struct record_stack_refs_data 242 { 243 rtx insn; 244 struct csa_reflist *reflist; 245 }; 246 247 static int 248 record_stack_refs (rtx *xp, void *data) 249 { 250 rtx x = *xp; 251 struct record_stack_refs_data *d = 252 (struct record_stack_refs_data *) data; 253 if (!x) 254 return 0; 255 switch (GET_CODE (x)) 256 { 257 case MEM: 258 if (!reg_mentioned_p (stack_pointer_rtx, x)) 259 return -1; 260 /* We are not able to handle correctly all possible memrefs containing 261 stack pointer, so this check is necessary. */ 262 if (stack_memref_p (x)) 263 { 264 d->reflist = record_one_stack_ref (d->insn, xp, d->reflist); 265 return -1; 266 } 267 /* Try harder for DEBUG_INSNs, handle e.g. (mem (mem (sp + 16) + 4). */ 268 return !DEBUG_INSN_P (d->insn); 269 case REG: 270 /* ??? We want be able to handle non-memory stack pointer 271 references later. For now just discard all insns referring to 272 stack pointer outside mem expressions. We would probably 273 want to teach validate_replace to simplify expressions first. 274 275 We can't just compare with STACK_POINTER_RTX because the 276 reference to the stack pointer might be in some other mode. 277 In particular, an explicit clobber in an asm statement will 278 result in a QImode clobber. 279 280 In DEBUG_INSNs, we want to replace all occurrences, otherwise 281 they will cause -fcompare-debug failures. */ 282 if (REGNO (x) == STACK_POINTER_REGNUM) 283 { 284 if (!DEBUG_INSN_P (d->insn)) 285 return 1; 286 d->reflist = record_one_stack_ref (d->insn, xp, d->reflist); 287 return -1; 288 } 289 break; 290 default: 291 break; 292 } 293 return 0; 294 } 295 296 /* If INSN has a REG_ARGS_SIZE note, move it to LAST. 297 AFTER is true iff LAST follows INSN in the instruction stream. */ 298 299 static void 300 maybe_move_args_size_note (rtx last, rtx insn, bool after) 301 { 302 rtx note, last_note; 303 304 note = find_reg_note (insn, REG_ARGS_SIZE, NULL_RTX); 305 if (note == NULL) 306 return; 307 308 last_note = find_reg_note (last, REG_ARGS_SIZE, NULL_RTX); 309 if (last_note) 310 { 311 /* The ARGS_SIZE notes are *not* cumulative. They represent an 312 absolute value, and the "most recent" note wins. */ 313 if (!after) 314 XEXP (last_note, 0) = XEXP (note, 0); 315 } 316 else 317 add_reg_note (last, REG_ARGS_SIZE, XEXP (note, 0)); 318 } 319 320 /* Return the next (or previous) active insn within BB. */ 321 322 static rtx 323 prev_active_insn_bb (basic_block bb, rtx insn) 324 { 325 for (insn = PREV_INSN (insn); 326 insn != PREV_INSN (BB_HEAD (bb)); 327 insn = PREV_INSN (insn)) 328 if (active_insn_p (insn)) 329 return insn; 330 return NULL_RTX; 331 } 332 333 static rtx 334 next_active_insn_bb (basic_block bb, rtx insn) 335 { 336 for (insn = NEXT_INSN (insn); 337 insn != NEXT_INSN (BB_END (bb)); 338 insn = NEXT_INSN (insn)) 339 if (active_insn_p (insn)) 340 return insn; 341 return NULL_RTX; 342 } 343 344 /* If INSN has a REG_ARGS_SIZE note, if possible move it to PREV. Otherwise 345 search for a nearby candidate within BB where we can stick the note. */ 346 347 static void 348 force_move_args_size_note (basic_block bb, rtx prev, rtx insn) 349 { 350 rtx note, test, next_candidate, prev_candidate; 351 352 /* If PREV exists, tail-call to the logic in the other function. */ 353 if (prev) 354 { 355 maybe_move_args_size_note (prev, insn, false); 356 return; 357 } 358 359 /* First, make sure there's anything that needs doing. */ 360 note = find_reg_note (insn, REG_ARGS_SIZE, NULL_RTX); 361 if (note == NULL) 362 return; 363 364 /* We need to find a spot between the previous and next exception points 365 where we can place the note and "properly" deallocate the arguments. */ 366 next_candidate = prev_candidate = NULL; 367 368 /* It is often the case that we have insns in the order: 369 call 370 add sp (previous deallocation) 371 sub sp (align for next arglist) 372 push arg 373 and the add/sub cancel. Therefore we begin by searching forward. */ 374 375 test = insn; 376 while ((test = next_active_insn_bb (bb, test)) != NULL) 377 { 378 /* Found an existing note: nothing to do. */ 379 if (find_reg_note (test, REG_ARGS_SIZE, NULL_RTX)) 380 return; 381 /* Found something that affects unwinding. Stop searching. */ 382 if (CALL_P (test) || !insn_nothrow_p (test)) 383 break; 384 if (next_candidate == NULL) 385 next_candidate = test; 386 } 387 388 test = insn; 389 while ((test = prev_active_insn_bb (bb, test)) != NULL) 390 { 391 rtx tnote; 392 /* Found a place that seems logical to adjust the stack. */ 393 tnote = find_reg_note (test, REG_ARGS_SIZE, NULL_RTX); 394 if (tnote) 395 { 396 XEXP (tnote, 0) = XEXP (note, 0); 397 return; 398 } 399 if (prev_candidate == NULL) 400 prev_candidate = test; 401 /* Found something that affects unwinding. Stop searching. */ 402 if (CALL_P (test) || !insn_nothrow_p (test)) 403 break; 404 } 405 406 if (prev_candidate) 407 test = prev_candidate; 408 else if (next_candidate) 409 test = next_candidate; 410 else 411 { 412 /* ??? We *must* have a place, lest we ICE on the lost adjustment. 413 Options are: dummy clobber insn, nop, or prevent the removal of 414 the sp += 0 insn. */ 415 /* TODO: Find another way to indicate to the dwarf2 code that we 416 have not in fact lost an adjustment. */ 417 test = emit_insn_before (gen_rtx_CLOBBER (VOIDmode, const0_rtx), insn); 418 } 419 add_reg_note (test, REG_ARGS_SIZE, XEXP (note, 0)); 420 } 421 422 /* Subroutine of combine_stack_adjustments, called for each basic block. */ 423 424 static void 425 combine_stack_adjustments_for_block (basic_block bb) 426 { 427 HOST_WIDE_INT last_sp_adjust = 0; 428 rtx last_sp_set = NULL_RTX; 429 rtx last2_sp_set = NULL_RTX; 430 struct csa_reflist *reflist = NULL; 431 rtx insn, next, set; 432 struct record_stack_refs_data data; 433 bool end_of_block = false; 434 435 for (insn = BB_HEAD (bb); !end_of_block ; insn = next) 436 { 437 end_of_block = insn == BB_END (bb); 438 next = NEXT_INSN (insn); 439 440 if (! INSN_P (insn)) 441 continue; 442 443 set = single_set_for_csa (insn); 444 if (set) 445 { 446 rtx dest = SET_DEST (set); 447 rtx src = SET_SRC (set); 448 449 /* Find constant additions to the stack pointer. */ 450 if (dest == stack_pointer_rtx 451 && GET_CODE (src) == PLUS 452 && XEXP (src, 0) == stack_pointer_rtx 453 && CONST_INT_P (XEXP (src, 1))) 454 { 455 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1)); 456 457 /* If we've not seen an adjustment previously, record 458 it now and continue. */ 459 if (! last_sp_set) 460 { 461 last_sp_set = insn; 462 last_sp_adjust = this_adjust; 463 continue; 464 } 465 466 /* If not all recorded refs can be adjusted, or the 467 adjustment is now too large for a constant addition, 468 we cannot merge the two stack adjustments. 469 470 Also we need to be careful to not move stack pointer 471 such that we create stack accesses outside the allocated 472 area. We can combine an allocation into the first insn, 473 or a deallocation into the second insn. We can not 474 combine an allocation followed by a deallocation. 475 476 The only somewhat frequent occurrence of the later is when 477 a function allocates a stack frame but does not use it. 478 For this case, we would need to analyze rtl stream to be 479 sure that allocated area is really unused. This means not 480 only checking the memory references, but also all registers 481 or global memory references possibly containing a stack 482 frame address. 483 484 Perhaps the best way to address this problem is to teach 485 gcc not to allocate stack for objects never used. */ 486 487 /* Combine an allocation into the first instruction. */ 488 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0) 489 { 490 if (try_apply_stack_adjustment (last_sp_set, reflist, 491 last_sp_adjust + this_adjust, 492 this_adjust)) 493 { 494 /* It worked! */ 495 maybe_move_args_size_note (last_sp_set, insn, false); 496 delete_insn (insn); 497 last_sp_adjust += this_adjust; 498 continue; 499 } 500 } 501 502 /* Otherwise we have a deallocation. Do not combine with 503 a previous allocation. Combine into the second insn. */ 504 else if (STACK_GROWS_DOWNWARD 505 ? last_sp_adjust >= 0 : last_sp_adjust <= 0) 506 { 507 if (try_apply_stack_adjustment (insn, reflist, 508 last_sp_adjust + this_adjust, 509 -last_sp_adjust)) 510 { 511 /* It worked! */ 512 maybe_move_args_size_note (insn, last_sp_set, true); 513 delete_insn (last_sp_set); 514 last_sp_set = insn; 515 last_sp_adjust += this_adjust; 516 free_csa_reflist (reflist); 517 reflist = NULL; 518 continue; 519 } 520 } 521 522 /* Combination failed. Restart processing from here. If 523 deallocation+allocation conspired to cancel, we can 524 delete the old deallocation insn. */ 525 if (last_sp_set) 526 { 527 if (last_sp_adjust == 0) 528 { 529 maybe_move_args_size_note (insn, last_sp_set, true); 530 delete_insn (last_sp_set); 531 } 532 else 533 last2_sp_set = last_sp_set; 534 } 535 free_csa_reflist (reflist); 536 reflist = NULL; 537 last_sp_set = insn; 538 last_sp_adjust = this_adjust; 539 continue; 540 } 541 542 /* Find a store with pre-(dec|inc)rement or pre-modify of exactly 543 the previous adjustment and turn it into a simple store. This 544 is equivalent to anticipating the stack adjustment so this must 545 be an allocation. */ 546 if (MEM_P (dest) 547 && ((STACK_GROWS_DOWNWARD 548 ? (GET_CODE (XEXP (dest, 0)) == PRE_DEC 549 && last_sp_adjust 550 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))) 551 : (GET_CODE (XEXP (dest, 0)) == PRE_INC 552 && last_sp_adjust 553 == -(HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest)))) 554 || ((STACK_GROWS_DOWNWARD 555 ? last_sp_adjust >= 0 : last_sp_adjust <= 0) 556 && GET_CODE (XEXP (dest, 0)) == PRE_MODIFY 557 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS 558 && XEXP (XEXP (XEXP (dest, 0), 1), 0) 559 == stack_pointer_rtx 560 && GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1)) 561 == CONST_INT 562 && INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1)) 563 == -last_sp_adjust)) 564 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx 565 && !reg_mentioned_p (stack_pointer_rtx, src) 566 && memory_address_p (GET_MODE (dest), stack_pointer_rtx) 567 && try_apply_stack_adjustment (insn, reflist, 0, 568 -last_sp_adjust)) 569 { 570 if (last2_sp_set) 571 maybe_move_args_size_note (last2_sp_set, last_sp_set, false); 572 else 573 maybe_move_args_size_note (insn, last_sp_set, true); 574 delete_insn (last_sp_set); 575 free_csa_reflist (reflist); 576 reflist = NULL; 577 last_sp_set = NULL_RTX; 578 last_sp_adjust = 0; 579 continue; 580 } 581 } 582 583 data.insn = insn; 584 data.reflist = reflist; 585 if (!CALL_P (insn) && last_sp_set 586 && !for_each_rtx (&PATTERN (insn), record_stack_refs, &data)) 587 { 588 reflist = data.reflist; 589 continue; 590 } 591 reflist = data.reflist; 592 593 /* Otherwise, we were not able to process the instruction. 594 Do not continue collecting data across such a one. */ 595 if (last_sp_set 596 && (CALL_P (insn) 597 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn)))) 598 { 599 if (last_sp_set && last_sp_adjust == 0) 600 { 601 force_move_args_size_note (bb, last2_sp_set, last_sp_set); 602 delete_insn (last_sp_set); 603 } 604 free_csa_reflist (reflist); 605 reflist = NULL; 606 last2_sp_set = NULL_RTX; 607 last_sp_set = NULL_RTX; 608 last_sp_adjust = 0; 609 } 610 } 611 612 if (last_sp_set && last_sp_adjust == 0) 613 { 614 force_move_args_size_note (bb, last2_sp_set, last_sp_set); 615 delete_insn (last_sp_set); 616 } 617 618 if (reflist) 619 free_csa_reflist (reflist); 620 } 621 622 623 static bool 624 gate_handle_stack_adjustments (void) 625 { 626 /* This is kind of a heuristic. We need to run combine_stack_adjustments 627 even for machines with possibly nonzero TARGET_RETURN_POPS_ARGS 628 and ACCUMULATE_OUTGOING_ARGS. We expect that only ports having 629 push instructions will have popping returns. */ 630 #ifndef PUSH_ROUNDING 631 if (ACCUMULATE_OUTGOING_ARGS) 632 return false; 633 #endif 634 return flag_combine_stack_adjustments; 635 } 636 637 static unsigned int 638 rest_of_handle_stack_adjustments (void) 639 { 640 df_note_add_problem (); 641 df_analyze (); 642 combine_stack_adjustments (); 643 return 0; 644 } 645 646 struct rtl_opt_pass pass_stack_adjustments = 647 { 648 { 649 RTL_PASS, 650 "csa", /* name */ 651 OPTGROUP_NONE, /* optinfo_flags */ 652 gate_handle_stack_adjustments, /* gate */ 653 rest_of_handle_stack_adjustments, /* execute */ 654 NULL, /* sub */ 655 NULL, /* next */ 656 0, /* static_pass_number */ 657 TV_COMBINE_STACK_ADJUST, /* tv_id */ 658 0, /* properties_required */ 659 0, /* properties_provided */ 660 0, /* properties_destroyed */ 661 0, /* todo_flags_start */ 662 TODO_df_finish | TODO_verify_rtl_sharing | 663 TODO_ggc_collect, /* todo_flags_finish */ 664 } 665 }; 666