gcc/sibcall.c

   1 /* Generic sibling call optimization support
   2    Copyright (C) 1999, 2000 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23
  24 #include "rtl.h"
  25 #include "regs.h"
  26 #include "function.h"
  27 #include "hard-reg-set.h"
  28 #include "flags.h"
  29 #include "insn-config.h"
  30 #include "recog.h"
  31 #include "basic-block.h"
  32 #include "output.h"
  33 #include "except.h"
  34
  35 static int identify_call_return_value   PARAMS ((rtx, rtx *, rtx *));
  36 static rtx skip_copy_to_return_value    PARAMS ((rtx, rtx, rtx));
  37 static rtx skip_use_of_return_value     PARAMS ((rtx, enum rtx_code));
  38 static rtx skip_stack_adjustment        PARAMS ((rtx));
  39 static rtx skip_jump_insn               PARAMS ((rtx));
  40 static int uses_addressof               PARAMS ((rtx, int));
  41 static int sequence_uses_addressof      PARAMS ((rtx));
  42 static void purge_reg_equiv_notes       PARAMS ((void));
  43
  44 /* Examine a CALL_PLACEHOLDER pattern and determine where the call's
  45    return value is located.  P_HARD_RETURN receives the hard register
  46    that the function used; P_SOFT_RETURN receives the pseudo register
  47    that the sequence used.  Return non-zero if the values were located.  */
  48
  49 static int
  50 identify_call_return_value (cp, p_hard_return, p_soft_return)
  51      rtx cp;
  52      rtx *p_hard_return, *p_soft_return;
  53 {
  54   rtx insn, set, hard, soft;
  55
  56   insn = XEXP (cp, 0);
  57   /* Search backward through the "normal" call sequence to the CALL insn.  */
  58   while (NEXT_INSN (insn))
  59     insn = NEXT_INSN (insn);
  60   while (GET_CODE (insn) != CALL_INSN)
  61     insn = PREV_INSN (insn);
  62
  63   /* Assume the pattern is (set (dest) (call ...)), or that the first
  64      member of a parallel is.  This is the hard return register used
  65      by the function.  */
  66   if (GET_CODE (PATTERN (insn)) == SET
  67       && GET_CODE (SET_SRC (PATTERN (insn))) == CALL)
  68     hard = SET_DEST (PATTERN (insn));
  69   else if (GET_CODE (PATTERN (insn)) == PARALLEL
  70            && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
  71            && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == CALL)
  72     hard = SET_DEST (XVECEXP (PATTERN (insn), 0, 0));
  73   else
  74     return 0;
  75
  76   /* If we didn't get a single hard register (e.g. a parallel), give up.  */
  77   if (GET_CODE (hard) != REG)
  78     return 0;
  79
  80   /* Stack adjustment done after call may appear here.  */
  81   insn = skip_stack_adjustment (insn);
  82   if (! insn)
  83     return 0;
  84
  85   /* If there's nothing after, there's no soft return value.  */
  86   insn = NEXT_INSN (insn);
  87   if (! insn)
  88     return 0;
  89
  90   /* We're looking for a source of the hard return register.  */
  91   set = single_set (insn);
  92   if (! set || SET_SRC (set) != hard)
  93     return 0;
  94
  95   soft = SET_DEST (set);
  96   insn = NEXT_INSN (insn);
  97
  98   /* Allow this first destination to be copied to a second register,
  99      as might happen if the first register wasn't the particular pseudo
 100      we'd been expecting.  */
 101   if (insn
 102       && (set = single_set (insn)) != NULL_RTX
 103       && SET_SRC (set) == soft)
 104     {
 105       soft = SET_DEST (set);
 106       insn = NEXT_INSN (insn);
 107     }
 108
 109   /* Don't fool with anything but pseudo registers.  */
 110   if (GET_CODE (soft) != REG || REGNO (soft) < FIRST_PSEUDO_REGISTER)
 111     return 0;
 112
 113   /* This value must not be modified before the end of the sequence.  */
 114   if (reg_set_between_p (soft, insn, NULL_RTX))
 115     return 0;
 116
 117   *p_hard_return = hard;
 118   *p_soft_return = soft;
 119
 120   return 1;
 121 }
 122
 123 /* If the first real insn after ORIG_INSN copies to this function's
 124    return value from RETVAL, then return the insn which performs the
 125    copy.  Otherwise return ORIG_INSN.  */
 126
 127 static rtx
 128 skip_copy_to_return_value (orig_insn, hardret, softret)
 129      rtx orig_insn;
 130      rtx hardret, softret;
 131 {
 132   rtx insn, set = NULL_RTX;
 133
 134   insn = next_nonnote_insn (orig_insn);
 135   if (! insn)
 136     return orig_insn;
 137
 138   set = single_set (insn);
 139   if (! set)
 140     return orig_insn;
 141
 142   /* The destination must be the same as the called function's return
 143      value to ensure that any return value is put in the same place by the
 144      current function and the function we're calling.
 145
 146      Further, the source must be the same as the pseudo into which the
 147      called function's return value was copied.  Otherwise we're returning
 148      some other value.  */
 149
 150 #ifndef OUTGOING_REGNO
 151 #define OUTGOING_REGNO(N) (N)
 152 #endif
 153
 154   if (SET_DEST (set) == current_function_return_rtx
 155       && REG_P (SET_DEST (set))
 156       && OUTGOING_REGNO (REGNO (SET_DEST (set))) == REGNO (hardret)
 157       && SET_SRC (set) == softret)
 158     return insn;
 159
 160   /* It did not look like a copy of the return value, so return the
 161      same insn we were passed.  */
 162   return orig_insn;
 163 }
 164
 165 /* If the first real insn after ORIG_INSN is a CODE of this function's return
 166    value, return insn.  Otherwise return ORIG_INSN.  */
 167
 168 static rtx
 169 skip_use_of_return_value (orig_insn, code)
 170      rtx orig_insn;
 171      enum rtx_code code;
 172 {
 173   rtx insn;
 174
 175   insn = next_nonnote_insn (orig_insn);
 176
 177   if (insn
 178       && GET_CODE (insn) == INSN
 179       && GET_CODE (PATTERN (insn)) == code
 180       && (XEXP (PATTERN (insn), 0) == current_function_return_rtx
 181           || XEXP (PATTERN (insn), 0) == const0_rtx))
 182     return insn;
 183
 184   return orig_insn;
 185 }
 186
 187 /* If the first real insn after ORIG_INSN adjusts the stack pointer
 188    by a constant, return the insn with the stack pointer adjustment.
 189    Otherwise return ORIG_INSN.  */
 190
 191 static rtx
 192 skip_stack_adjustment (orig_insn)
 193      rtx orig_insn;
 194 {
 195   rtx insn, set = NULL_RTX;
 196
 197   insn = next_nonnote_insn (orig_insn);
 198
 199   if (insn)
 200     set = single_set (insn);
 201
 202   /* The source must be the same as the current function's return value to
 203      ensure that any return value is put in the same place by the current
 204      function and the function we're calling.   The destination register
 205      must be a pseudo.  */
 206   if (insn
 207       && set
 208       && GET_CODE (SET_SRC (set)) == PLUS
 209       && XEXP (SET_SRC (set), 0) == stack_pointer_rtx
 210       && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
 211       && SET_DEST (set) == stack_pointer_rtx)
 212     return insn;
 213
 214   /* It did not look like a copy of the return value, so return the
 215      same insn we were passed.  */
 216   return orig_insn;
 217 }
 218
 219 /* If the first real insn after ORIG_INSN is a jump, return the JUMP_INSN.
 220    Otherwise return ORIG_INSN.  */
 221
 222 static rtx
 223 skip_jump_insn (orig_insn)
 224      rtx orig_insn;
 225 {
 226   rtx insn;
 227
 228   insn = next_nonnote_insn (orig_insn);
 229
 230   if (insn
 231       && GET_CODE (insn) == JUMP_INSN
 232       && any_uncondjump_p (insn))
 233     return insn;
 234
 235   return orig_insn;
 236 }
 237
 238 /* Scan the rtx X for ADDRESSOF expressions or
 239    current_function_internal_arg_pointer registers.
 240    INMEM argument should be 1 if we're looking at inner part of some
 241    MEM expression, otherwise 0.
 242    Return nonzero if an ADDRESSOF expresion is found or if
 243    current_function_internal_arg_pointer is found outside of some MEM
 244    expression, else return zero.  */
 245
 246 static int
 247 uses_addressof (x, inmem)
 248      rtx x;
 249      int inmem;
 250 {
 251   RTX_CODE code;
 252   int i, j;
 253   const char *fmt;
 254
 255   if (x == NULL_RTX)
 256     return 0;
 257
 258   code = GET_CODE (x);
 259
 260   if (code == ADDRESSOF)
 261     return 1;
 262
 263   if (x == current_function_internal_arg_pointer && ! inmem)
 264     return 1;
 265
 266   if (code == MEM)
 267     return uses_addressof (XEXP (x, 0), 1);
 268
 269   /* Scan all subexpressions. */
 270   fmt = GET_RTX_FORMAT (code);
 271   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
 272     {
 273       if (*fmt == 'e')
 274         {
 275           if (uses_addressof (XEXP (x, i), inmem))
 276             return 1;
 277         }
 278       else if (*fmt == 'E')
 279         {
 280           for (j = 0; j < XVECLEN (x, i); j++)
 281             if (uses_addressof (XVECEXP (x, i, j), inmem))
 282               return 1;
 283         }
 284     }
 285   return 0;
 286 }
 287
 288 /* Scan the sequence of insns in SEQ to see if any have an ADDRESSOF
 289    rtl expression or current_function_internal_arg_pointer occurences
 290    not enclosed within a MEM.  If an ADDRESSOF expression or
 291    current_function_internal_arg_pointer is found, return nonzero, otherwise
 292    return zero.
 293
 294    This function handles CALL_PLACEHOLDERs which contain multiple sequences
 295    of insns.  */
 296
 297 static int
 298 sequence_uses_addressof (seq)
 299      rtx seq;
 300 {
 301   rtx insn;
 302
 303   for (insn = seq; insn; insn = NEXT_INSN (insn))
 304     if (INSN_P (insn))
 305       {
 306         /* If this is a CALL_PLACEHOLDER, then recursively call ourselves
 307            with each nonempty sequence attached to the CALL_PLACEHOLDER.  */
 308         if (GET_CODE (insn) == CALL_INSN
 309             && GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
 310           {
 311             if (XEXP (PATTERN (insn), 0) != NULL_RTX
 312                 && sequence_uses_addressof (XEXP (PATTERN (insn), 0)))
 313               return 1;
 314             if (XEXP (PATTERN (insn), 1) != NULL_RTX
 315                 && sequence_uses_addressof (XEXP (PATTERN (insn), 1)))
 316               return 1;
 317             if (XEXP (PATTERN (insn), 2) != NULL_RTX
 318                 && sequence_uses_addressof (XEXP (PATTERN (insn), 2)))
 319               return 1;
 320           }
 321         else if (uses_addressof (PATTERN (insn), 0)
 322                  || (REG_NOTES (insn) && uses_addressof (REG_NOTES (insn), 0)))
 323           return 1;
 324       }
 325   return 0;
 326 }
 327
 328 /* Remove all REG_EQUIV notes found in the insn chain.  */
 329
 330 static void
 331 purge_reg_equiv_notes ()
 332 {
 333   rtx insn;
 334
 335   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 336     {
 337       while (1)
 338         {
 339           rtx note = find_reg_note (insn, REG_EQUIV, 0);
 340           if (note)
 341             {
 342               /* Remove the note and keep looking at the notes for
 343                  this insn.  */
 344               remove_note (insn, note);
 345               continue;
 346             }
 347           break;
 348         }
 349     }
 350 }
 351
 352 /* Replace the CALL_PLACEHOLDER with one of its children.  INSN should be
 353    the CALL_PLACEHOLDER insn; USE tells which child to use.  */
 354
 355 void
 356 replace_call_placeholder (insn, use)
 357      rtx insn;
 358      sibcall_use_t use;
 359 {
 360   if (use == sibcall_use_tail_recursion)
 361     emit_insns_before (XEXP (PATTERN (insn), 2), insn);
 362   else if (use == sibcall_use_sibcall)
 363     emit_insns_before (XEXP (PATTERN (insn), 1), insn);
 364   else if (use == sibcall_use_normal)
 365     emit_insns_before (XEXP (PATTERN (insn), 0), insn);
 366   else
 367     abort();
 368
 369   /* Turn off LABEL_PRESERVE_P for the tail recursion label if it
 370      exists.  We only had to set it long enough to keep the jump
 371      pass above from deleting it as unused.  */
 372   if (XEXP (PATTERN (insn), 3))
 373     LABEL_PRESERVE_P (XEXP (PATTERN (insn), 3)) = 0;
 374
 375   /* "Delete" the placeholder insn. */
 376   PUT_CODE (insn, NOTE);
 377   NOTE_SOURCE_FILE (insn) = 0;
 378   NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
 379 }
 380
 381 /* Given a (possibly empty) set of potential sibling or tail recursion call
 382    sites, determine if optimization is possible.
 383
 384    Potential sibling or tail recursion calls are marked with CALL_PLACEHOLDER
 385    insns.  The CALL_PLACEHOLDER insn holds chains of insns to implement a
 386    normal call, sibling call or tail recursive call.
 387
 388    Replace the CALL_PLACEHOLDER with an appropriate insn chain.  */
 389
 390 void
 391 optimize_sibling_and_tail_recursive_calls ()
 392 {
 393   rtx insn, insns;
 394   basic_block alternate_exit = EXIT_BLOCK_PTR;
 395   int current_function_uses_addressof;
 396   int successful_sibling_call = 0;
 397   int replaced_call_placeholder = 0;
 398   edge e;
 399
 400   insns = get_insns ();
 401
 402   /* We do not perform these calls when flag_exceptions is true, so this
 403      is probably a NOP at the current time.  However, we may want to support
 404      sibling and tail recursion optimizations in the future, so let's plan
 405      ahead and find all the EH labels.  */
 406   find_exception_handler_labels ();
 407
 408   /* Run a jump optimization pass to clean up the CFG.  We primarily want
 409      this to thread jumps so that it is obvious which blocks jump to the
 410      epilouge.  */
 411   jump_optimize_minimal (insns);
 412
 413   /* We need cfg information to determine which blocks are succeeded
 414      only by the epilogue.  */
 415   find_basic_blocks (insns, max_reg_num (), 0);
 416   cleanup_cfg (insns);
 417
 418   /* If there are no basic blocks, then there is nothing to do.  */
 419   if (n_basic_blocks == 0)
 420     return;
 421
 422   /* Find the exit block.
 423
 424      It is possible that we have blocks which can reach the exit block
 425      directly.  However, most of the time a block will jump (or fall into)
 426      N_BASIC_BLOCKS - 1, which in turn falls into the exit block.  */
 427   for (e = EXIT_BLOCK_PTR->pred;
 428        e && alternate_exit == EXIT_BLOCK_PTR;
 429        e = e->pred_next)
 430     {
 431       rtx insn;
 432
 433       if (e->dest != EXIT_BLOCK_PTR || e->succ_next != NULL)
 434         continue;
 435
 436       /* Walk forwards through the last normal block and see if it
 437          does nothing except fall into the exit block.  */
 438       for (insn = BLOCK_HEAD (n_basic_blocks - 1);
 439            insn;
 440            insn = NEXT_INSN (insn))
 441         {
 442           /* This should only happen once, at the start of this block.  */
 443           if (GET_CODE (insn) == CODE_LABEL)
 444             continue;
 445
 446           if (GET_CODE (insn) == NOTE)
 447             continue;
 448
 449           if (GET_CODE (insn) == INSN
 450               && GET_CODE (PATTERN (insn)) == USE)
 451             continue;
 452
 453           break;
 454         }
 455
 456       /* If INSN is zero, then the search walked all the way through the
 457          block without hitting anything interesting.  This block is a
 458          valid alternate exit block.  */
 459       if (insn == NULL)
 460         alternate_exit = e->src;
 461     }
 462
 463   /* If the function uses ADDRESSOF, we can't (easily) determine
 464      at this point if the value will end up on the stack.  */
 465   current_function_uses_addressof = sequence_uses_addressof (insns);
 466
 467   /* Walk the insn chain and find any CALL_PLACEHOLDER insns.  We need to
 468      select one of the insn sequences attached to each CALL_PLACEHOLDER.
 469
 470      The different sequences represent different ways to implement the call,
 471      ie, tail recursion, sibling call or normal call.
 472
 473      Since we do not create nested CALL_PLACEHOLDERs, the scan
 474      continues with the insn that was after a replaced CALL_PLACEHOLDER;
 475      we don't rescan the replacement insns.  */
 476   for (insn = insns; insn; insn = NEXT_INSN (insn))
 477     {
 478       if (GET_CODE (insn) == CALL_INSN
 479           && GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
 480         {
 481           int sibcall = (XEXP (PATTERN (insn), 1) != NULL_RTX);
 482           int tailrecursion = (XEXP (PATTERN (insn), 2) != NULL_RTX);
 483           basic_block succ_block, call_block;
 484           rtx temp, hardret, softret;
 485
 486           /* We must be careful with stack slots which are live at
 487              potential optimization sites.
 488
 489              ?!? This test is overly conservative and will be replaced.  */
 490           if (frame_offset)
 491             goto failure;
 492
 493           /* alloca (until we have stack slot life analysis) inhibits
 494              sibling call optimizations, but not tail recursion.
 495
 496              Similarly if we have ADDRESSOF expressions.
 497
 498              Similarly if we use varargs or stdarg since they implicitly
 499              may take the address of an argument.  */
 500           if (current_function_calls_alloca || current_function_uses_addressof
 501               || current_function_varargs || current_function_stdarg)
 502             sibcall = 0;
 503
 504           call_block = BLOCK_FOR_INSN (insn);
 505
 506           /* If the block has more than one successor, then we can not
 507              perform sibcall or tail recursion optimizations.  */
 508           if (call_block->succ == NULL
 509               || call_block->succ->succ_next != NULL)
 510             goto failure;
 511
 512           /* If the single successor is not the exit block, then we can not
 513              perform sibcall or tail recursion optimizations.
 514
 515              Note that this test combined with the previous is sufficient
 516              to prevent tail call optimization in the presense of active
 517              exception handlers.  */
 518           succ_block = call_block->succ->dest;
 519           if (succ_block != EXIT_BLOCK_PTR && succ_block != alternate_exit)
 520             goto failure;
 521
 522           /* If the call was the end of the block, then we're OK.  */
 523           temp = insn;
 524           if (temp == call_block->end)
 525             goto success;
 526
 527           /* Skip over copying from the call's return value pseudo into
 528              this function's hard return register.  */
 529           if (identify_call_return_value (PATTERN (insn), &hardret, &softret))
 530             {
 531               temp = skip_copy_to_return_value (temp, hardret, softret);
 532               if (temp == call_block->end)
 533                 goto success;
 534             }
 535
 536           /* Skip any stack adjustment.  */
 537           temp = skip_stack_adjustment (temp);
 538           if (temp == call_block->end)
 539             goto success;
 540
 541           /* Skip over a CLOBBER of the return value (as a hard reg).  */
 542           temp = skip_use_of_return_value (temp, CLOBBER);
 543           if (temp == call_block->end)
 544             goto success;
 545
 546           /* Skip over a USE of the return value (as a hard reg).  */
 547           temp = skip_use_of_return_value (temp, USE);
 548           if (temp == call_block->end)
 549             goto success;
 550
 551           /* Skip over the JUMP_INSN at the end of the block.  */
 552           temp = skip_jump_insn (temp);
 553           if (GET_CODE (temp) == NOTE)
 554             temp = next_nonnote_insn (temp);
 555           if (temp == call_block->end)
 556             goto success;
 557
 558           /* There are operations at the end of the block which we must
 559              execute after returning from the function call.  So this call
 560              can not be optimized.  */
 561 failure:
 562           sibcall = 0, tailrecursion = 0;
 563 success:
 564
 565           /* Select a set of insns to implement the call and emit them.
 566              Tail recursion is the most efficient, so select it over
 567              a tail/sibling call.  */
 568
 569           if (sibcall)
 570             successful_sibling_call = 1;
 571           replaced_call_placeholder = 1;
 572           replace_call_placeholder (insn,
 573                                     tailrecursion != 0
 574                                       ? sibcall_use_tail_recursion
 575                                       : sibcall != 0
 576                                          ? sibcall_use_sibcall
 577                                          : sibcall_use_normal);
 578         }
 579     }
 580
 581   /* A sibling call sequence invalidates any REG_EQUIV notes made for
 582      this function's incoming arguments.
 583
 584      At the start of RTL generation we know the only REG_EQUIV notes
 585      in the rtl chain are those for incoming arguments, so we can safely
 586      flush any REG_EQUIV note.
 587
 588      This is (slight) overkill.  We could keep track of the highest argument
 589      we clobber and be more selective in removing notes, but it does not
 590      seem to be worth the effort.  */
 591   if (successful_sibling_call)
 592     purge_reg_equiv_notes ();
 593
 594   /* There may have been NOTE_INSN_BLOCK_{BEGIN,END} notes in the
 595      CALL_PLACEHOLDER alternatives that we didn't emit.  Rebuild the
 596      lexical block tree to correspond to the notes that still exist.  */
 597   if (replaced_call_placeholder)
 598     reorder_blocks ();
 599
 600   /* This information will be invalid after inline expansion.  Kill it now.  */
 601   free_basic_block_vars (0);
 602 }