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