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