gcc/sibcall.c

   1 /* Generic sibling call optimization support
   2    Copyright (C) 1999, 2000, 2001 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 2, 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 COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 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 /* In case alternate_exit_block contains copy from pseudo, to return value,
  36    record the pseudo here.  In such case the pseudo must be set to function
  37    return in the sibcall sequence.  */
  38 static rtx return_value_pseudo;
  39
  40 static int identify_call_return_value   PARAMS ((rtx, rtx *, rtx *));
  41 static rtx skip_copy_to_return_value    PARAMS ((rtx));
  42 static rtx skip_use_of_return_value     PARAMS ((rtx, enum rtx_code));
  43 static rtx skip_stack_adjustment        PARAMS ((rtx));
  44 static rtx skip_pic_restore             PARAMS ((rtx));
  45 static rtx skip_jump_insn               PARAMS ((rtx));
  46 static int call_ends_block_p            PARAMS ((rtx, rtx));
  47 static int uses_addressof               PARAMS ((rtx));
  48 static int sequence_uses_addressof      PARAMS ((rtx));
  49 static void purge_reg_equiv_notes       PARAMS ((void));
  50 static void purge_mem_unchanging_flag   PARAMS ((rtx));
  51 static rtx skip_unreturned_value        PARAMS ((rtx));
  52
  53 /* Examine a CALL_PLACEHOLDER pattern and determine where the call's
  54    return value is located.  P_HARD_RETURN receives the hard register
  55    that the function used; P_SOFT_RETURN receives the pseudo register
  56    that the sequence used.  Return non-zero if the values were located.  */
  57
  58 static int
  59 identify_call_return_value (cp, p_hard_return, p_soft_return)
  60      rtx cp;
  61      rtx *p_hard_return, *p_soft_return;
  62 {
  63   rtx insn, set, hard, soft;
  64
  65   insn = XEXP (cp, 0);
  66   /* Search backward through the "normal" call sequence to the CALL insn.  */
  67   while (NEXT_INSN (insn))
  68     insn = NEXT_INSN (insn);
  69   while (GET_CODE (insn) != CALL_INSN)
  70     insn = PREV_INSN (insn);
  71
  72   /* Assume the pattern is (set (dest) (call ...)), or that the first
  73      member of a parallel is.  This is the hard return register used
  74      by the function.  */
  75   if (GET_CODE (PATTERN (insn)) == SET
  76       && GET_CODE (SET_SRC (PATTERN (insn))) == CALL)
  77     hard = SET_DEST (PATTERN (insn));
  78   else if (GET_CODE (PATTERN (insn)) == PARALLEL
  79            && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
  80            && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == CALL)
  81     hard = SET_DEST (XVECEXP (PATTERN (insn), 0, 0));
  82   else
  83     return 0;
  84
  85   /* If we didn't get a single hard register (e.g. a parallel), give up.  */
  86   if (GET_CODE (hard) != REG)
  87     return 0;
  88
  89   /* Stack adjustment done after call may appear here.  */
  90   insn = skip_stack_adjustment (insn);
  91   if (! insn)
  92     return 0;
  93
  94   /* Restore of GP register may appear here.  */
  95   insn = skip_pic_restore (insn);
  96   if (! insn)
  97     return 0;
  98
  99   /* If there's nothing after, there's no soft return value.  */
 100   insn = NEXT_INSN (insn);
 101   if (! insn)
 102     return 0;
 103
 104   /* We're looking for a source of the hard return register.  */
 105   set = single_set (insn);
 106   if (! set || SET_SRC (set) != hard)
 107     return 0;
 108
 109   soft = SET_DEST (set);
 110   insn = NEXT_INSN (insn);
 111
 112   /* Allow this first destination to be copied to a second register,
 113      as might happen if the first register wasn't the particular pseudo
 114      we'd been expecting.  */
 115   if (insn
 116       && (set = single_set (insn)) != NULL_RTX
 117       && SET_SRC (set) == soft)
 118     {
 119       soft = SET_DEST (set);
 120       insn = NEXT_INSN (insn);
 121     }
 122
 123   /* Don't fool with anything but pseudo registers.  */
 124   if (GET_CODE (soft) != REG || REGNO (soft) < FIRST_PSEUDO_REGISTER)
 125     return 0;
 126
 127   /* This value must not be modified before the end of the sequence.  */
 128   if (reg_set_between_p (soft, insn, NULL_RTX))
 129     return 0;
 130
 131   *p_hard_return = hard;
 132   *p_soft_return = soft;
 133
 134   return 1;
 135 }
 136
 137 /* If the first real insn after ORIG_INSN copies to this function's
 138    return value from RETVAL, then return the insn which performs the
 139    copy.  Otherwise return ORIG_INSN.  */
 140
 141 static rtx
 142 skip_copy_to_return_value (orig_insn)
 143      rtx orig_insn;
 144 {
 145   rtx insn, set = NULL_RTX;
 146   rtx hardret, softret;
 147
 148   /* If there is no return value, we have nothing to do.  */
 149   if (! identify_call_return_value (PATTERN (orig_insn), &hardret, &softret))
 150     return orig_insn;
 151
 152   insn = next_nonnote_insn (orig_insn);
 153   if (! insn)
 154     return orig_insn;
 155
 156   set = single_set (insn);
 157   if (! set)
 158     return orig_insn;
 159
 160   if (return_value_pseudo)
 161     {
 162       if (SET_DEST (set) == return_value_pseudo
 163           && SET_SRC (set) == softret)
 164         return insn;
 165       return orig_insn;
 166     }
 167
 168   /* The destination must be the same as the called function's return
 169      value to ensure that any return value is put in the same place by the
 170      current function and the function we're calling.
 171
 172      Further, the source must be the same as the pseudo into which the
 173      called function's return value was copied.  Otherwise we're returning
 174      some other value.  */
 175
 176 #ifndef OUTGOING_REGNO
 177 #define OUTGOING_REGNO(N) (N)
 178 #endif
 179
 180   if (SET_DEST (set) == current_function_return_rtx
 181       && REG_P (SET_DEST (set))
 182       && OUTGOING_REGNO (REGNO (SET_DEST (set))) == REGNO (hardret)
 183       && SET_SRC (set) == softret)
 184     return insn;
 185
 186   /* Recognize the situation when the called function's return value
 187      is copied in two steps: first into an intermediate pseudo, then
 188      the into the calling functions return value register.  */
 189
 190   if (REG_P (SET_DEST (set))
 191       && SET_SRC (set) == softret)
 192     {
 193       rtx x = SET_DEST (set);
 194
 195       insn = next_nonnote_insn (insn);
 196       if (! insn)
 197         return orig_insn;
 198
 199       set = single_set (insn);
 200       if (! set)
 201         return orig_insn;
 202
 203       if (SET_DEST (set) == current_function_return_rtx
 204           && REG_P (SET_DEST (set))
 205           && OUTGOING_REGNO (REGNO (SET_DEST (set))) == REGNO (hardret)
 206           && SET_SRC (set) == x)
 207         return insn;
 208     }
 209
 210   /* It did not look like a copy of the return value, so return the
 211      same insn we were passed.  */
 212   return orig_insn;
 213 }
 214
 215 /* If the first real insn after ORIG_INSN is a CODE of this function's return
 216    value, return insn.  Otherwise return ORIG_INSN.  */
 217
 218 static rtx
 219 skip_use_of_return_value (orig_insn, code)
 220      rtx orig_insn;
 221      enum rtx_code code;
 222 {
 223   rtx insn;
 224
 225   insn = next_nonnote_insn (orig_insn);
 226
 227   if (insn
 228       && GET_CODE (insn) == INSN
 229       && GET_CODE (PATTERN (insn)) == code
 230       && (XEXP (PATTERN (insn), 0) == current_function_return_rtx
 231           || XEXP (PATTERN (insn), 0) == const0_rtx))
 232     return insn;
 233
 234   return orig_insn;
 235 }
 236
 237 /* In case function does not return value,  we get clobber of pseudo followed
 238    by set to hard return value.  */
 239 static rtx
 240 skip_unreturned_value (orig_insn)
 241      rtx orig_insn;
 242 {
 243   rtx insn = next_nonnote_insn (orig_insn);
 244
 245   /* Skip possible clobber of pseudo return register.  */
 246   if (insn
 247       && GET_CODE (insn) == INSN
 248       && GET_CODE (PATTERN (insn)) == CLOBBER
 249       && REG_P (XEXP (PATTERN (insn), 0))
 250       && (REGNO (XEXP (PATTERN (insn), 0)) >= FIRST_PSEUDO_REGISTER))
 251     {
 252       rtx set_insn = next_nonnote_insn (insn);
 253       rtx set;
 254       if (!set_insn)
 255         return insn;
 256       set = single_set (set_insn);
 257       if (!set
 258           || SET_SRC (set) != XEXP (PATTERN (insn), 0)
 259           || SET_DEST (set) != current_function_return_rtx)
 260         return insn;
 261       return set_insn;
 262     }
 263   return orig_insn;
 264 }
 265
 266 /* If the first real insn after ORIG_INSN adjusts the stack pointer
 267    by a constant, return the insn with the stack pointer adjustment.
 268    Otherwise return ORIG_INSN.  */
 269
 270 static rtx
 271 skip_stack_adjustment (orig_insn)
 272      rtx orig_insn;
 273 {
 274   rtx insn, set = NULL_RTX;
 275
 276   insn = next_nonnote_insn (orig_insn);
 277
 278   if (insn)
 279     set = single_set (insn);
 280
 281   if (insn
 282       && set
 283       && GET_CODE (SET_SRC (set)) == PLUS
 284       && XEXP (SET_SRC (set), 0) == stack_pointer_rtx
 285       && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
 286       && SET_DEST (set) == stack_pointer_rtx)
 287     return insn;
 288
 289   return orig_insn;
 290 }
 291
 292 /* If the first real insn after ORIG_INSN sets the pic register,
 293    return it.  Otherwise return ORIG_INSN.  */
 294
 295 static rtx
 296 skip_pic_restore (orig_insn)
 297      rtx orig_insn;
 298 {
 299   rtx insn, set = NULL_RTX;
 300
 301   insn = next_nonnote_insn (orig_insn);
 302
 303   if (insn)
 304     set = single_set (insn);
 305
 306   if (insn && set && SET_DEST (set) == pic_offset_table_rtx)
 307     return insn;
 308
 309   return orig_insn;
 310 }
 311
 312 /* If the first real insn after ORIG_INSN is a jump, return the JUMP_INSN.
 313    Otherwise return ORIG_INSN.  */
 314
 315 static rtx
 316 skip_jump_insn (orig_insn)
 317      rtx orig_insn;
 318 {
 319   rtx insn;
 320
 321   insn = next_nonnote_insn (orig_insn);
 322
 323   if (insn
 324       && GET_CODE (insn) == JUMP_INSN
 325       && any_uncondjump_p (insn))
 326     return insn;
 327
 328   return orig_insn;
 329 }
 330 \f
 331 /* Using the above functions, see if INSN, skipping any of the above,
 332    goes all the way to END, the end of a basic block.  Return 1 if so.  */
 333
 334 static int
 335 call_ends_block_p (insn, end)
 336      rtx insn;
 337      rtx end;
 338 {
 339   rtx new_insn;
 340   /* END might be a note, so get the last nonnote insn of the block.  */
 341   end = next_nonnote_insn (PREV_INSN (end));
 342
 343   /* If the call was the end of the block, then we're OK.  */
 344   if (insn == end)
 345     return 1;
 346
 347   /* Skip over copying from the call's return value pseudo into
 348      this function's hard return register and if that's the end
 349      of the block, we're OK.  */
 350   new_insn = skip_copy_to_return_value (insn);
 351
 352   /* In case we return value in pseudo, we must set the pseudo to
 353      return value of called function, otherwise we are returning
 354      something else.  */
 355   if (return_value_pseudo && insn == new_insn)
 356     return 0;
 357   insn = new_insn;
 358
 359   if (insn == end)
 360     return 1;
 361
 362   /* Skip any stack adjustment.  */
 363   insn = skip_stack_adjustment (insn);
 364   if (insn == end)
 365     return 1;
 366
 367   /* Skip over a CLOBBER of the return value as a hard reg.  */
 368   insn = skip_use_of_return_value (insn, CLOBBER);
 369   if (insn == end)
 370     return 1;
 371
 372   /* Skip over a CLOBBER of the return value as a hard reg.  */
 373   insn = skip_unreturned_value (insn);
 374   if (insn == end)
 375     return 1;
 376
 377   /* Skip over a USE of the return value (as a hard reg).  */
 378   insn = skip_use_of_return_value (insn, USE);
 379   if (insn == end)
 380     return 1;
 381
 382   /* Skip over a JUMP_INSN at the end of the block.  If that doesn't end the
 383      block, the original CALL_INSN didn't.  */
 384   insn = skip_jump_insn (insn);
 385   return insn == end;
 386 }
 387
 388 /* Scan the rtx X for ADDRESSOF expressions or
 389    current_function_internal_arg_pointer registers.
 390    Return nonzero if an ADDRESSOF or current_function_internal_arg_pointer
 391    is found outside of some MEM expression, else return zero.  */
 392
 393 static int
 394 uses_addressof (x)
 395      rtx x;
 396 {
 397   RTX_CODE code;
 398   int i, j;
 399   const char *fmt;
 400
 401   if (x == NULL_RTX)
 402     return 0;
 403
 404   code = GET_CODE (x);
 405
 406   if (code == ADDRESSOF || x == current_function_internal_arg_pointer)
 407     return 1;
 408
 409   if (code == MEM)
 410     return 0;
 411
 412   /* Scan all subexpressions.  */
 413   fmt = GET_RTX_FORMAT (code);
 414   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
 415     {
 416       if (*fmt == 'e')
 417         {
 418           if (uses_addressof (XEXP (x, i)))
 419             return 1;
 420         }
 421       else if (*fmt == 'E')
 422         {
 423           for (j = 0; j < XVECLEN (x, i); j++)
 424             if (uses_addressof (XVECEXP (x, i, j)))
 425               return 1;
 426         }
 427     }
 428   return 0;
 429 }
 430
 431 /* Scan the sequence of insns in SEQ to see if any have an ADDRESSOF
 432    rtl expression or current_function_internal_arg_pointer occurrences
 433    not enclosed within a MEM.  If an ADDRESSOF expression or
 434    current_function_internal_arg_pointer is found, return nonzero, otherwise
 435    return zero.
 436
 437    This function handles CALL_PLACEHOLDERs which contain multiple sequences
 438    of insns.  */
 439
 440 static int
 441 sequence_uses_addressof (seq)
 442      rtx seq;
 443 {
 444   rtx insn;
 445
 446   for (insn = seq; insn; insn = NEXT_INSN (insn))
 447     if (INSN_P (insn))
 448       {
 449         /* If this is a CALL_PLACEHOLDER, then recursively call ourselves
 450            with each nonempty sequence attached to the CALL_PLACEHOLDER.  */
 451         if (GET_CODE (insn) == CALL_INSN
 452             && GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
 453           {
 454             if (XEXP (PATTERN (insn), 0) != NULL_RTX
 455                 && sequence_uses_addressof (XEXP (PATTERN (insn), 0)))
 456               return 1;
 457             if (XEXP (PATTERN (insn), 1) != NULL_RTX
 458                 && sequence_uses_addressof (XEXP (PATTERN (insn), 1)))
 459               return 1;
 460             if (XEXP (PATTERN (insn), 2) != NULL_RTX
 461                 && sequence_uses_addressof (XEXP (PATTERN (insn), 2)))
 462               return 1;
 463           }
 464         else if (uses_addressof (PATTERN (insn))
 465                  || (REG_NOTES (insn) && uses_addressof (REG_NOTES (insn))))
 466           return 1;
 467       }
 468   return 0;
 469 }
 470
 471 /* Remove all REG_EQUIV notes found in the insn chain.  */
 472
 473 static void
 474 purge_reg_equiv_notes ()
 475 {
 476   rtx insn;
 477
 478   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 479     {
 480       while (1)
 481         {
 482           rtx note = find_reg_note (insn, REG_EQUIV, 0);
 483           if (note)
 484             {
 485               /* Remove the note and keep looking at the notes for
 486                  this insn.  */
 487               remove_note (insn, note);
 488               continue;
 489             }
 490           break;
 491         }
 492     }
 493 }
 494
 495 /* Clear RTX_UNCHANGING_P flag of incoming argument MEMs.  */
 496
 497 static void
 498 purge_mem_unchanging_flag (x)
 499      rtx x;
 500 {
 501   RTX_CODE code;
 502   int i, j;
 503   const char *fmt;
 504
 505   if (x == NULL_RTX)
 506     return;
 507
 508   code = GET_CODE (x);
 509
 510   if (code == MEM)
 511     {
 512       if (RTX_UNCHANGING_P (x)
 513           && (XEXP (x, 0) == current_function_internal_arg_pointer
 514               || (GET_CODE (XEXP (x, 0)) == PLUS
 515                   && XEXP (XEXP (x, 0), 0) ==
 516                      current_function_internal_arg_pointer
 517                   && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)))
 518         RTX_UNCHANGING_P (x) = 0;
 519       return;
 520     }
 521
 522   /* Scan all subexpressions.  */
 523   fmt = GET_RTX_FORMAT (code);
 524   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
 525     {
 526       if (*fmt == 'e')
 527         purge_mem_unchanging_flag (XEXP (x, i));
 528       else if (*fmt == 'E')
 529         for (j = 0; j < XVECLEN (x, i); j++)
 530           purge_mem_unchanging_flag (XVECEXP (x, i, j));
 531     }
 532 }
 533
 534 /* Replace the CALL_PLACEHOLDER with one of its children.  INSN should be
 535    the CALL_PLACEHOLDER insn; USE tells which child to use.  */
 536
 537 void
 538 replace_call_placeholder (insn, use)
 539      rtx insn;
 540      sibcall_use_t use;
 541 {
 542   if (use == sibcall_use_tail_recursion)
 543     emit_insns_before (XEXP (PATTERN (insn), 2), insn);
 544   else if (use == sibcall_use_sibcall)
 545     emit_insns_before (XEXP (PATTERN (insn), 1), insn);
 546   else if (use == sibcall_use_normal)
 547     emit_insns_before (XEXP (PATTERN (insn), 0), insn);
 548   else
 549     abort();
 550
 551   /* Turn off LABEL_PRESERVE_P for the tail recursion label if it
 552      exists.  We only had to set it long enough to keep the jump
 553      pass above from deleting it as unused.  */
 554   if (XEXP (PATTERN (insn), 3))
 555     LABEL_PRESERVE_P (XEXP (PATTERN (insn), 3)) = 0;
 556
 557   /* "Delete" the placeholder insn.  */
 558   remove_insn (insn);
 559 }
 560
 561 /* Given a (possibly empty) set of potential sibling or tail recursion call
 562    sites, determine if optimization is possible.
 563
 564    Potential sibling or tail recursion calls are marked with CALL_PLACEHOLDER
 565    insns.  The CALL_PLACEHOLDER insn holds chains of insns to implement a
 566    normal call, sibling call or tail recursive call.
 567
 568    Replace the CALL_PLACEHOLDER with an appropriate insn chain.  */
 569
 570 void
 571 optimize_sibling_and_tail_recursive_calls ()
 572 {
 573   rtx insn, insns;
 574   basic_block alternate_exit = EXIT_BLOCK_PTR;
 575   int current_function_uses_addressof;
 576   int successful_sibling_call = 0;
 577   int replaced_call_placeholder = 0;
 578   edge e;
 579
 580   insns = get_insns ();
 581
 582   /* We do not perform these calls when flag_exceptions is true, so this
 583      is probably a NOP at the current time.  However, we may want to support
 584      sibling and tail recursion optimizations in the future, so let's plan
 585      ahead and find all the EH labels.  */
 586   find_exception_handler_labels ();
 587
 588   rebuild_jump_labels (insns);
 589   /* We need cfg information to determine which blocks are succeeded
 590      only by the epilogue.  */
 591   find_basic_blocks (insns, max_reg_num (), 0);
 592   cleanup_cfg (CLEANUP_PRE_SIBCALL | CLEANUP_PRE_LOOP);
 593
 594   /* If there are no basic blocks, then there is nothing to do.  */
 595   if (n_basic_blocks == 0)
 596     return;
 597
 598   return_value_pseudo = NULL_RTX;
 599
 600   /* Find the exit block.
 601
 602      It is possible that we have blocks which can reach the exit block
 603      directly.  However, most of the time a block will jump (or fall into)
 604      N_BASIC_BLOCKS - 1, which in turn falls into the exit block.  */
 605   for (e = EXIT_BLOCK_PTR->pred;
 606        e && alternate_exit == EXIT_BLOCK_PTR;
 607        e = e->pred_next)
 608     {
 609       rtx insn;
 610
 611       if (e->dest != EXIT_BLOCK_PTR || e->succ_next != NULL)
 612         continue;
 613
 614       /* Walk forwards through the last normal block and see if it
 615          does nothing except fall into the exit block.  */
 616       for (insn = BLOCK_HEAD (n_basic_blocks - 1);
 617            insn;
 618            insn = NEXT_INSN (insn))
 619         {
 620           rtx set;
 621           /* This should only happen once, at the start of this block.  */
 622           if (GET_CODE (insn) == CODE_LABEL)
 623             continue;
 624
 625           if (GET_CODE (insn) == NOTE)
 626             continue;
 627
 628           if (GET_CODE (insn) == INSN
 629               && GET_CODE (PATTERN (insn)) == USE)
 630             continue;
 631
 632           /* Exit block also may contain copy from pseudo containing
 633              return value to hard register.  */
 634           if (GET_CODE (insn) == INSN
 635               && (set = single_set (insn))
 636               && SET_DEST (set) == current_function_return_rtx
 637               && REG_P (SET_SRC (set))
 638               && !return_value_pseudo)
 639             {
 640               return_value_pseudo = SET_SRC (set);
 641               continue;
 642             }
 643
 644           break;
 645         }
 646
 647       /* If INSN is zero, then the search walked all the way through the
 648          block without hitting anything interesting.  This block is a
 649          valid alternate exit block.  */
 650       if (insn == NULL)
 651         alternate_exit = e->src;
 652       else
 653         return_value_pseudo = NULL;
 654     }
 655
 656   /* If the function uses ADDRESSOF, we can't (easily) determine
 657      at this point if the value will end up on the stack.  */
 658   current_function_uses_addressof = sequence_uses_addressof (insns);
 659
 660   /* Walk the insn chain and find any CALL_PLACEHOLDER insns.  We need to
 661      select one of the insn sequences attached to each CALL_PLACEHOLDER.
 662
 663      The different sequences represent different ways to implement the call,
 664      ie, tail recursion, sibling call or normal call.
 665
 666      Since we do not create nested CALL_PLACEHOLDERs, the scan
 667      continues with the insn that was after a replaced CALL_PLACEHOLDER;
 668      we don't rescan the replacement insns.  */
 669   for (insn = insns; insn; insn = NEXT_INSN (insn))
 670     {
 671       if (GET_CODE (insn) == CALL_INSN
 672           && GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
 673         {
 674           int sibcall = (XEXP (PATTERN (insn), 1) != NULL_RTX);
 675           int tailrecursion = (XEXP (PATTERN (insn), 2) != NULL_RTX);
 676           basic_block call_block = BLOCK_FOR_INSN (insn);
 677
 678           /* alloca (until we have stack slot life analysis) inhibits
 679              sibling call optimizations, but not tail recursion.
 680              Similarly if we use varargs or stdarg since they implicitly
 681              may take the address of an argument.  */
 682           if (current_function_calls_alloca
 683               || current_function_varargs || current_function_stdarg)
 684             sibcall = 0;
 685
 686           /* See if there are any reasons we can't perform either sibling or
 687              tail call optimizations.  We must be careful with stack slots
 688              which are live at potential optimization sites.  ??? The first
 689              test is overly conservative and should be replaced.  */
 690           if (frame_offset
 691               /* Can't take address of local var if used by recursive call.  */
 692               || current_function_uses_addressof
 693               /* Any function that calls setjmp might have longjmp called from
 694                  any called function.  ??? We really should represent this
 695                  properly in the CFG so that this needn't be special cased.  */
 696               || current_function_calls_setjmp
 697               /* Can't if more than one successor or single successor is not
 698                  exit block.  These two tests prevent tail call optimization
 699                  in the presense of active exception handlers.  */
 700               || call_block->succ == NULL
 701               || call_block->succ->succ_next != NULL
 702               || (call_block->succ->dest != EXIT_BLOCK_PTR
 703                   && call_block->succ->dest != alternate_exit)
 704               /* If this call doesn't end the block, there are operations at
 705                  the end of the block which we must execute after returning.  */
 706               || ! call_ends_block_p (insn, call_block->end))
 707             sibcall = 0, tailrecursion = 0;
 708
 709           /* Select a set of insns to implement the call and emit them.
 710              Tail recursion is the most efficient, so select it over
 711              a tail/sibling call.  */
 712           if (sibcall)
 713             successful_sibling_call = 1;
 714
 715           replaced_call_placeholder = 1;
 716           replace_call_placeholder (insn,
 717                                     tailrecursion != 0
 718                                       ? sibcall_use_tail_recursion
 719                                       : sibcall != 0
 720                                          ? sibcall_use_sibcall
 721                                          : sibcall_use_normal);
 722         }
 723     }
 724
 725   if (successful_sibling_call)
 726     {
 727       rtx insn;
 728
 729       /* A sibling call sequence invalidates any REG_EQUIV notes made for
 730          this function's incoming arguments.
 731
 732          At the start of RTL generation we know the only REG_EQUIV notes
 733          in the rtl chain are those for incoming arguments, so we can safely
 734          flush any REG_EQUIV note.
 735
 736          This is (slight) overkill.  We could keep track of the highest
 737          argument we clobber and be more selective in removing notes, but it
 738          does not seem to be worth the effort.  */
 739       purge_reg_equiv_notes ();
 740
 741       /* A sibling call sequence also may invalidate RTX_UNCHANGING_P
 742          flag of some incoming arguments MEM RTLs, because it can write into
 743          those slots.  We clear all those bits now.
 744
 745          This is (slight) overkill, we could keep track of which arguments
 746          we actually write into.  */
 747       for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 748         {
 749           if (INSN_P (insn))
 750             purge_mem_unchanging_flag (PATTERN (insn));
 751         }
 752     }
 753
 754   /* There may have been NOTE_INSN_BLOCK_{BEGIN,END} notes in the
 755      CALL_PLACEHOLDER alternatives that we didn't emit.  Rebuild the
 756      lexical block tree to correspond to the notes that still exist.  */
 757   if (replaced_call_placeholder)
 758     reorder_blocks ();
 759
 760   /* This information will be invalid after inline expansion.  Kill it now.  */
 761   free_basic_block_vars (0);
 762 }