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