LCOV - code coverage report
Current view: top level - gcc - tree-tailcall.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 95.4 % 960 916
Test Date: 2025-07-05 13:26:22 Functions: 93.5 % 31 29
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Tail call optimization on trees.
       2                 :             :    Copyright (C) 2003-2025 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
       7                 :             : it under the terms of the GNU General Public License as published by
       8                 :             : the Free Software Foundation; either version 3, or (at your option)
       9                 :             : any later version.
      10                 :             : 
      11                 :             : GCC 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 GCC; see the file COPYING3.  If not see
      18                 :             : <http://www.gnu.org/licenses/>.  */
      19                 :             : 
      20                 :             : #include "config.h"
      21                 :             : #include "system.h"
      22                 :             : #include "coretypes.h"
      23                 :             : #include "backend.h"
      24                 :             : #include "rtl.h"
      25                 :             : #include "tree.h"
      26                 :             : #include "gimple.h"
      27                 :             : #include "cfghooks.h"
      28                 :             : #include "tree-pass.h"
      29                 :             : #include "ssa.h"
      30                 :             : #include "cgraph.h"
      31                 :             : #include "gimple-pretty-print.h"
      32                 :             : #include "fold-const.h"
      33                 :             : #include "stor-layout.h"
      34                 :             : #include "gimple-iterator.h"
      35                 :             : #include "gimplify-me.h"
      36                 :             : #include "tree-cfg.h"
      37                 :             : #include "tree-into-ssa.h"
      38                 :             : #include "tree-dfa.h"
      39                 :             : #include "except.h"
      40                 :             : #include "tree-eh.h"
      41                 :             : #include "dbgcnt.h"
      42                 :             : #include "cfgloop.h"
      43                 :             : #include "intl.h"
      44                 :             : #include "common/common-target.h"
      45                 :             : #include "ipa-utils.h"
      46                 :             : #include "tree-ssa-live.h"
      47                 :             : #include "diagnostic-core.h"
      48                 :             : #include "gimple-range.h"
      49                 :             : #include "alloc-pool.h"
      50                 :             : #include "sreal.h"
      51                 :             : #include "symbol-summary.h"
      52                 :             : #include "ipa-cp.h"
      53                 :             : #include "ipa-prop.h"
      54                 :             : #include "attribs.h"
      55                 :             : #include "asan.h"
      56                 :             : 
      57                 :             : /* The file implements the tail recursion elimination.  It is also used to
      58                 :             :    analyze the tail calls in general, passing the results to the rtl level
      59                 :             :    where they are used for sibcall optimization.
      60                 :             : 
      61                 :             :    In addition to the standard tail recursion elimination, we handle the most
      62                 :             :    trivial cases of making the call tail recursive by creating accumulators.
      63                 :             :    For example the following function
      64                 :             : 
      65                 :             :    int sum (int n)
      66                 :             :    {
      67                 :             :      if (n > 0)
      68                 :             :        return n + sum (n - 1);
      69                 :             :      else
      70                 :             :        return 0;
      71                 :             :    }
      72                 :             : 
      73                 :             :    is transformed into
      74                 :             : 
      75                 :             :    int sum (int n)
      76                 :             :    {
      77                 :             :      int acc = 0;
      78                 :             : 
      79                 :             :      while (n > 0)
      80                 :             :        acc += n--;
      81                 :             : 
      82                 :             :      return acc;
      83                 :             :    }
      84                 :             : 
      85                 :             :    To do this, we maintain two accumulators (a_acc and m_acc) that indicate
      86                 :             :    when we reach the return x statement, we should return a_acc + x * m_acc
      87                 :             :    instead.  They are initially initialized to 0 and 1, respectively,
      88                 :             :    so the semantics of the function is obviously preserved.  If we are
      89                 :             :    guaranteed that the value of the accumulator never change, we
      90                 :             :    omit the accumulator.
      91                 :             : 
      92                 :             :    There are three cases how the function may exit.  The first one is
      93                 :             :    handled in adjust_return_value, the other two in adjust_accumulator_values
      94                 :             :    (the second case is actually a special case of the third one and we
      95                 :             :    present it separately just for clarity):
      96                 :             : 
      97                 :             :    1) Just return x, where x is not in any of the remaining special shapes.
      98                 :             :       We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
      99                 :             : 
     100                 :             :    2) return f (...), where f is the current function, is rewritten in a
     101                 :             :       classical tail-recursion elimination way, into assignment of arguments
     102                 :             :       and jump to the start of the function.  Values of the accumulators
     103                 :             :       are unchanged.
     104                 :             : 
     105                 :             :    3) return a + m * f(...), where a and m do not depend on call to f.
     106                 :             :       To preserve the semantics described before we want this to be rewritten
     107                 :             :       in such a way that we finally return
     108                 :             : 
     109                 :             :       a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
     110                 :             : 
     111                 :             :       I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
     112                 :             :       eliminate the tail call to f.  Special cases when the value is just
     113                 :             :       added or just multiplied are obtained by setting a = 0 or m = 1.
     114                 :             : 
     115                 :             :    TODO -- it is possible to do similar tricks for other operations.  */
     116                 :             : 
     117                 :             : /* A structure that describes the tailcall.  */
     118                 :             : 
     119                 :             : struct tailcall
     120                 :             : {
     121                 :             :   /* The iterator pointing to the call statement.  */
     122                 :             :   gimple_stmt_iterator call_gsi;
     123                 :             : 
     124                 :             :   /* True if it is a call to the current function.  */
     125                 :             :   bool tail_recursion;
     126                 :             : 
     127                 :             :   /* True if there is __tsan_func_exit call after the call.  */
     128                 :             :   bool has_tsan_func_exit;
     129                 :             : 
     130                 :             :   /* The return value of the caller is mult * f + add, where f is the return
     131                 :             :      value of the call.  */
     132                 :             :   tree mult, add;
     133                 :             : 
     134                 :             :   /* Next tailcall in the chain.  */
     135                 :             :   struct tailcall *next;
     136                 :             : };
     137                 :             : 
     138                 :             : /* The variables holding the value of multiplicative and additive
     139                 :             :    accumulator.  */
     140                 :             : static tree m_acc, a_acc;
     141                 :             : 
     142                 :             : /* Bitmap with a bit for each function parameter which is set to true if we
     143                 :             :    have to copy the parameter for conversion of tail-recursive calls.  */
     144                 :             : 
     145                 :             : static bitmap tailr_arg_needs_copy;
     146                 :             : 
     147                 :             : static void maybe_error_musttail (gcall *call, const char *err, bool);
     148                 :             : 
     149                 :             : /* Returns false when the function is not suitable for tail call optimization
     150                 :             :    from some reason (e.g. if it takes variable number of arguments). CALL
     151                 :             :    is call to report for.  */
     152                 :             : 
     153                 :             : static bool
     154                 :     1532396 : suitable_for_tail_opt_p (gcall *call, bool diag_musttail)
     155                 :             : {
     156                 :     1532396 :   if (cfun->stdarg)
     157                 :             :     {
     158                 :       18384 :       maybe_error_musttail (call, _("caller uses stdargs"), diag_musttail);
     159                 :       18384 :       return false;
     160                 :             :     }
     161                 :             : 
     162                 :             :   return true;
     163                 :             : }
     164                 :             : 
     165                 :             : /* Returns false when the function is not suitable for tail call optimization
     166                 :             :    for some reason (e.g. if it takes variable number of arguments).
     167                 :             :    This test must pass in addition to suitable_for_tail_opt_p in order to make
     168                 :             :    tail call discovery happen. CALL is call to report error for.  */
     169                 :             : 
     170                 :             : static bool
     171                 :     1514012 : suitable_for_tail_call_opt_p (gcall *call, bool diag_musttail)
     172                 :             : {
     173                 :             :   /* alloca (until we have stack slot life analysis) inhibits
     174                 :             :      sibling call optimizations, but not tail recursion.  */
     175                 :     1514012 :   if (cfun->calls_alloca)
     176                 :             :     {
     177                 :       15040 :       maybe_error_musttail (call, _("caller uses alloca"), diag_musttail);
     178                 :       15040 :       return false;
     179                 :             :     }
     180                 :             : 
     181                 :             :   /* If we are using sjlj exceptions, we may need to add a call to
     182                 :             :      _Unwind_SjLj_Unregister at exit of the function.  Which means
     183                 :             :      that we cannot do any sibcall transformations.  */
     184                 :     1498972 :   if (targetm_common.except_unwind_info (&global_options) == UI_SJLJ
     185                 :     1498972 :       && current_function_has_exception_handlers ())
     186                 :             :     {
     187                 :           0 :       maybe_error_musttail (call, _("caller uses sjlj exceptions"),
     188                 :             :                             diag_musttail);
     189                 :           0 :       return false;
     190                 :             :     }
     191                 :             : 
     192                 :             :   /* Any function that calls setjmp might have longjmp called from
     193                 :             :      any called function.  ??? We really should represent this
     194                 :             :      properly in the CFG so that this needn't be special cased.  */
     195                 :     1498972 :   if (cfun->calls_setjmp)
     196                 :             :     {
     197                 :         144 :       maybe_error_musttail (call, _("caller uses setjmp"), diag_musttail);
     198                 :         144 :       return false;
     199                 :             :     }
     200                 :             : 
     201                 :             :   /* Various targets don't handle tail calls correctly in functions
     202                 :             :      that call __builtin_eh_return.  */
     203                 :     1498828 :   if (cfun->calls_eh_return)
     204                 :             :     {
     205                 :           8 :       maybe_error_musttail (call, _("caller uses __builtin_eh_return"),
     206                 :             :                             diag_musttail);
     207                 :           8 :       return false;
     208                 :             :     }
     209                 :             : 
     210                 :     1498820 :   if (diag_musttail
     211                 :      363732 :       && gimple_call_must_tail_p (call)
     212                 :     1499514 :       && warn_musttail_local_addr)
     213                 :        1663 :     for (unsigned int i = 0; i < gimple_call_num_args (call); i++)
     214                 :             :       {
     215                 :         969 :         tree arg = gimple_call_arg (call, i);
     216                 :         969 :         if (!POINTER_TYPE_P (TREE_TYPE (arg)))
     217                 :         496 :           continue;
     218                 :         473 :         if (TREE_CODE (arg) == ADDR_EXPR)
     219                 :             :           {
     220                 :         179 :             arg = get_base_address (TREE_OPERAND (arg, 0));
     221                 :         179 :             if (auto_var_in_fn_p (arg, current_function_decl))
     222                 :             :               {
     223                 :         179 :                 if (TREE_CODE (arg) == LABEL_DECL)
     224                 :          16 :                   warning_at (gimple_location (call), OPT_Wmusttail_local_addr,
     225                 :             :                               "address of label passed to %<musttail%> "
     226                 :             :                               "call argument");
     227                 :         163 :                 else if (TREE_CODE (arg) == PARM_DECL)
     228                 :          25 :                   warning_at (gimple_location (call), OPT_Wmusttail_local_addr,
     229                 :             :                               "address of parameter %qD passed to "
     230                 :             :                               "%<musttail%> call argument", arg);
     231                 :         138 :                 else if (!DECL_ARTIFICIAL (arg) && DECL_NAME (arg))
     232                 :         129 :                   warning_at (gimple_location (call), OPT_Wmusttail_local_addr,
     233                 :             :                               "address of automatic variable %qD passed to "
     234                 :             :                               "%<musttail%> call argument", arg);
     235                 :             :                 else
     236                 :           9 :                   warning_at (gimple_location (call), OPT_Wmusttail_local_addr,
     237                 :             :                               "address of local variable passed to "
     238                 :             :                               "%<musttail%> call argument");
     239                 :         179 :                 suppress_warning (call, OPT_Wmaybe_musttail_local_addr);
     240                 :             :               }
     241                 :             :           }
     242                 :             :       }
     243                 :             : 
     244                 :             :   return true;
     245                 :             : }
     246                 :             : 
     247                 :             : /* Return single successor edge ignoring EDGE_EH edges.  */
     248                 :             : 
     249                 :             : static edge
     250                 :      524981 : single_non_eh_succ_edge (basic_block bb)
     251                 :             : {
     252                 :      524981 :    edge e, ret = NULL;
     253                 :      524981 :    edge_iterator ei;
     254                 :     1050122 :    FOR_EACH_EDGE (e, ei, bb->succs)
     255                 :      525141 :     if ((e->flags & EDGE_EH) == 0)
     256                 :             :       {
     257                 :      524981 :         gcc_assert (ret == NULL);
     258                 :             :         ret = e;
     259                 :             :       }
     260                 :      524981 :   gcc_assert (ret);
     261                 :      524981 :   return ret;
     262                 :             : }
     263                 :             : 
     264                 :             : /* Checks whether the expression EXPR in stmt AT is independent of the
     265                 :             :    statement pointed to by GSI (in a sense that we already know EXPR's value
     266                 :             :    at GSI).  We use the fact that we are only called from the chain of
     267                 :             :    basic blocks that have only single successor.  Returns the expression
     268                 :             :    containing the value of EXPR at GSI.  */
     269                 :             : 
     270                 :             : static tree
     271                 :       23130 : independent_of_stmt_p (tree expr, gimple *at, gimple_stmt_iterator gsi,
     272                 :             :                        bitmap to_move)
     273                 :             : {
     274                 :       23130 :   basic_block bb, call_bb, at_bb;
     275                 :       23130 :   edge e;
     276                 :       23130 :   edge_iterator ei;
     277                 :             : 
     278                 :       23130 :   if (is_gimple_min_invariant (expr))
     279                 :             :     return expr;
     280                 :             : 
     281                 :        6103 :   if (TREE_CODE (expr) != SSA_NAME)
     282                 :             :     return NULL_TREE;
     283                 :             : 
     284                 :        6103 :   if (bitmap_bit_p (to_move, SSA_NAME_VERSION (expr)))
     285                 :             :     return expr;
     286                 :             : 
     287                 :             :   /* Mark the blocks in the chain leading to the end.  */
     288                 :        6082 :   at_bb = gimple_bb (at);
     289                 :        6082 :   call_bb = gimple_bb (gsi_stmt (gsi));
     290                 :        6882 :   for (bb = call_bb; bb != at_bb; bb = single_non_eh_succ_edge (bb)->dest)
     291                 :         800 :     bb->aux = &bb->aux;
     292                 :        6082 :   bb->aux = &bb->aux;
     293                 :             : 
     294                 :        6189 :   while (1)
     295                 :             :     {
     296                 :        6189 :       at = SSA_NAME_DEF_STMT (expr);
     297                 :        6189 :       bb = gimple_bb (at);
     298                 :             : 
     299                 :             :       /* The default definition or defined before the chain.  */
     300                 :        6189 :       if (!bb || !bb->aux)
     301                 :             :         break;
     302                 :             : 
     303                 :        3074 :       if (bb == call_bb)
     304                 :             :         {
     305                 :       18510 :           for (; !gsi_end_p (gsi); gsi_next (&gsi))
     306                 :       15731 :             if (gsi_stmt (gsi) == at)
     307                 :             :               break;
     308                 :             : 
     309                 :        2945 :           if (!gsi_end_p (gsi))
     310                 :         166 :             expr = NULL_TREE;
     311                 :             :           break;
     312                 :             :         }
     313                 :             : 
     314                 :         129 :       if (gimple_code (at) != GIMPLE_PHI)
     315                 :             :         {
     316                 :             :           expr = NULL_TREE;
     317                 :             :           break;
     318                 :             :         }
     319                 :             : 
     320                 :         142 :       FOR_EACH_EDGE (e, ei, bb->preds)
     321                 :         142 :         if (e->src->aux)
     322                 :             :           break;
     323                 :         129 :       gcc_assert (e);
     324                 :             : 
     325                 :         129 :       expr = PHI_ARG_DEF_FROM_EDGE (at, e);
     326                 :         129 :       if (TREE_CODE (expr) != SSA_NAME)
     327                 :             :         {
     328                 :             :           /* The value is a constant.  */
     329                 :             :           break;
     330                 :             :         }
     331                 :             :     }
     332                 :             : 
     333                 :             :   /* Unmark the blocks.  */
     334                 :        6882 :   for (bb = call_bb; bb != at_bb; bb = single_non_eh_succ_edge (bb)->dest)
     335                 :         800 :     bb->aux = NULL;
     336                 :        6082 :   bb->aux = NULL;
     337                 :             : 
     338                 :        6082 :   return expr;
     339                 :             : }
     340                 :             : 
     341                 :             : enum par { FAIL, OK, TRY_MOVE };
     342                 :             : 
     343                 :             : /* Simulates the effect of an assignment STMT on the return value of the tail
     344                 :             :    recursive CALL passed in ASS_VAR.  M and A are the multiplicative and the
     345                 :             :    additive factor for the real return value.  */
     346                 :             : 
     347                 :             : static par
     348                 :      112657 : process_assignment (gassign *stmt,
     349                 :             :                     gimple_stmt_iterator call, tree *m,
     350                 :             :                     tree *a, tree *ass_var, bitmap to_move)
     351                 :             : {
     352                 :      112657 :   tree op0, op1 = NULL_TREE, non_ass_var = NULL_TREE;
     353                 :      112657 :   tree dest = gimple_assign_lhs (stmt);
     354                 :      112657 :   enum tree_code code = gimple_assign_rhs_code (stmt);
     355                 :      112657 :   enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
     356                 :      112657 :   tree src_var = gimple_assign_rhs1 (stmt);
     357                 :             : 
     358                 :             :   /* See if this is a simple copy operation of an SSA name to the function
     359                 :             :      result.  In that case we may have a simple tail call.  Ignore type
     360                 :             :      conversions that can never produce extra code between the function
     361                 :             :      call and the function return.  */
     362                 :       54770 :   if ((rhs_class == GIMPLE_SINGLE_RHS || gimple_assign_cast_p (stmt))
     363                 :      133140 :       && src_var == *ass_var)
     364                 :             :     {
     365                 :             :       /* Reject a tailcall if the type conversion might need
     366                 :             :          additional code.  */
     367                 :       22821 :       if (gimple_assign_cast_p (stmt))
     368                 :             :         {
     369                 :       18374 :           if (TYPE_MODE (TREE_TYPE (dest)) != TYPE_MODE (TREE_TYPE (src_var)))
     370                 :             :             return FAIL;
     371                 :             : 
     372                 :             :           /* Even if the type modes are the same, if the precision of the
     373                 :             :              type is smaller than mode's precision,
     374                 :             :              reduce_to_bit_field_precision would generate additional code.  */
     375                 :       16916 :           if (INTEGRAL_TYPE_P (TREE_TYPE (dest))
     376                 :       16409 :               && !type_has_mode_precision_p (TREE_TYPE (dest)))
     377                 :             :             return FAIL;
     378                 :             :         }
     379                 :             : 
     380                 :       12872 :       *ass_var = dest;
     381                 :       12872 :       return OK;
     382                 :             :     }
     383                 :             : 
     384                 :       89836 :   switch (rhs_class)
     385                 :             :     {
     386                 :       31555 :     case GIMPLE_BINARY_RHS:
     387                 :       31555 :       op1 = gimple_assign_rhs2 (stmt);
     388                 :             : 
     389                 :             :       /* Fall through.  */
     390                 :             : 
     391                 :       36025 :     case GIMPLE_UNARY_RHS:
     392                 :       36025 :       op0 = gimple_assign_rhs1 (stmt);
     393                 :       36025 :       break;
     394                 :             : 
     395                 :             :     default:
     396                 :             :       return FAIL;
     397                 :             :     }
     398                 :             : 
     399                 :             :   /* Accumulator optimizations will reverse the order of operations.
     400                 :             :      We can only do that for floating-point types if we're assuming
     401                 :             :      that addition and multiplication are associative.  */
     402                 :       36025 :   if (!flag_associative_math)
     403                 :       35677 :     if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
     404                 :             :       return FAIL;
     405                 :             : 
     406                 :             :   /* We at least cannot build -1 for all fixed point types.  */
     407                 :       32022 :   if (FIXED_POINT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
     408                 :             :     return FAIL;
     409                 :             : 
     410                 :       32022 :   if (rhs_class == GIMPLE_UNARY_RHS
     411                 :        4146 :       && op0 == *ass_var)
     412                 :             :     ;
     413                 :       29967 :   else if (op0 == *ass_var
     414                 :       29967 :            && (non_ass_var = independent_of_stmt_p (op1, stmt, call,
     415                 :             :                                                     to_move)))
     416                 :             :     ;
     417                 :       13405 :   else if (*ass_var
     418                 :        6729 :            && op1 == *ass_var
     419                 :       19835 :            && (non_ass_var = independent_of_stmt_p (op0, stmt, call,
     420                 :             :                                                     to_move)))
     421                 :             :     ;
     422                 :             :   else
     423                 :        7057 :     return TRY_MOVE;
     424                 :             : 
     425                 :       24965 :   switch (code)
     426                 :             :     {
     427                 :        6510 :     case PLUS_EXPR:
     428                 :        6510 :       *a = non_ass_var;
     429                 :        6510 :       *ass_var = dest;
     430                 :        6510 :       return OK;
     431                 :             : 
     432                 :         324 :     case POINTER_PLUS_EXPR:
     433                 :         324 :       if (op0 != *ass_var)
     434                 :             :         return FAIL;
     435                 :          83 :       *a = non_ass_var;
     436                 :          83 :       *ass_var = dest;
     437                 :          83 :       return OK;
     438                 :             : 
     439                 :         376 :     case MULT_EXPR:
     440                 :         376 :       *m = non_ass_var;
     441                 :         376 :       *ass_var = dest;
     442                 :         376 :       return OK;
     443                 :             : 
     444                 :         110 :     case NEGATE_EXPR:
     445                 :         110 :       *m = build_minus_one_cst (TREE_TYPE (op0));
     446                 :         110 :       *ass_var = dest;
     447                 :         110 :       return OK;
     448                 :             : 
     449                 :        1753 :     case MINUS_EXPR:
     450                 :        1753 :       if (*ass_var == op0)
     451                 :         114 :         *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
     452                 :             :       else
     453                 :             :         {
     454                 :        1639 :           *m = build_minus_one_cst (TREE_TYPE (non_ass_var));
     455                 :        1639 :           *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
     456                 :             :         }
     457                 :             : 
     458                 :        1753 :       *ass_var = dest;
     459                 :        1753 :       return OK;
     460                 :             : 
     461                 :             :     default:
     462                 :             :       return FAIL;
     463                 :             :     }
     464                 :             : }
     465                 :             : 
     466                 :             : /* Propagate VAR through phis on edge E.  */
     467                 :             : 
     468                 :             : static tree
     469                 :      521270 : propagate_through_phis (tree var, edge e)
     470                 :             : {
     471                 :      521270 :   basic_block dest = e->dest;
     472                 :      521270 :   gphi_iterator gsi;
     473                 :             : 
     474                 :      989355 :   for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
     475                 :             :     {
     476                 :      532517 :       gphi *phi = gsi.phi ();
     477                 :      532517 :       if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
     478                 :       64432 :         return PHI_RESULT (phi);
     479                 :             :     }
     480                 :             :   return var;
     481                 :             : }
     482                 :             : 
     483                 :             : /* Report an error for failing to tail convert must call CALL
     484                 :             :    with error message ERR. Also clear the flag to prevent further
     485                 :             :    errors.  */
     486                 :             : 
     487                 :             : static void
     488                 :      740543 : maybe_error_musttail (gcall *call, const char *err, bool diag_musttail)
     489                 :             : {
     490                 :      740543 :   if (gimple_call_must_tail_p (call) && diag_musttail)
     491                 :             :     {
     492                 :          39 :       error_at (gimple_location (call), "cannot tail-call: %s", err);
     493                 :             :       /* Avoid another error. ??? If there are multiple reasons why tail
     494                 :             :          calls fail it might be useful to report them all to avoid
     495                 :             :          whack-a-mole for the user. But currently there is too much
     496                 :             :          redundancy in the reporting, so keep it simple.  */
     497                 :          39 :       gimple_call_set_must_tail (call, false); /* Avoid another error.  */
     498                 :          39 :       gimple_call_set_tail (call, false);
     499                 :             :     }
     500                 :      740543 :   if (dump_file && (dump_flags & TDF_DETAILS))
     501                 :             :     {
     502                 :          13 :       fprintf (dump_file, "Cannot tail-call: %s: ", err);
     503                 :          13 :       print_gimple_stmt (dump_file, call, 0, TDF_SLIM);
     504                 :             :     }
     505                 :      740543 : }
     506                 :             : 
     507                 :             : /* Return true if there is no real work performed in the exception
     508                 :             :    path starting at BB and it will in the end result in external exception.
     509                 :             :    Search at most CNT basic blocks (so that we don't need to do trivial
     510                 :             :    loop discovery).  */
     511                 :             : static bool
     512                 :         206 : empty_eh_cleanup (basic_block bb, int *eh_has_tsan_func_exit, int cnt)
     513                 :             : {
     514                 :         299 :   if (EDGE_COUNT (bb->succs) > 1)
     515                 :             :     return false;
     516                 :             : 
     517                 :         466 :   for (gimple_stmt_iterator gsi = gsi_after_labels (bb); !gsi_end_p (gsi);
     518                 :         167 :        gsi_next (&gsi))
     519                 :             :     {
     520                 :         406 :       gimple *g = gsi_stmt (gsi);
     521                 :         406 :       if (is_gimple_debug (g) || gimple_clobber_p (g))
     522                 :          55 :         continue;
     523                 :         355 :       if (eh_has_tsan_func_exit
     524                 :         276 :           && !*eh_has_tsan_func_exit
     525                 :         272 :           && sanitize_flags_p (SANITIZE_THREAD)
     526                 :         355 :           && gimple_call_builtin_p (g, BUILT_IN_TSAN_FUNC_EXIT))
     527                 :             :         {
     528                 :           4 :           *eh_has_tsan_func_exit = 1;
     529                 :           4 :           continue;
     530                 :             :         }
     531                 :         455 :       if (eh_has_tsan_func_exit
     532                 :         272 :           && sanitize_flags_p (SANITIZE_ADDRESS)
     533                 :         515 :           && asan_mark_p (g, ASAN_MARK_POISON))
     534                 :         108 :         continue;
     535                 :         239 :       if (is_gimple_resx (g))
     536                 :             :         {
     537                 :         239 :           if (stmt_can_throw_external (cfun, g))
     538                 :         206 :             return true;
     539                 :         239 :           if (single_succ_p (bb)
     540                 :          33 :               && (single_succ_edge (bb)->flags & EDGE_EH)
     541                 :          66 :               && cnt > 1)
     542                 :          33 :             return empty_eh_cleanup (single_succ (bb), eh_has_tsan_func_exit,
     543                 :          33 :                                      cnt - 1);
     544                 :             :         }
     545                 :             :       return false;
     546                 :             :     }
     547                 :          60 :   if (!single_succ_p (bb))
     548                 :             :     return false;
     549                 :          60 :   if (cnt == 1)
     550                 :             :     return false;
     551                 :          60 :   return empty_eh_cleanup (single_succ (bb), eh_has_tsan_func_exit, cnt - 1);
     552                 :             : }
     553                 :             : 
     554                 :             : /* Argument for compute_live_vars/live_vars_at_stmt and what compute_live_vars
     555                 :             :    returns.  Computed lazily, but just once for the function.  */
     556                 :             : static live_vars_map *live_vars;
     557                 :             : static vec<bitmap_head> live_vars_vec;
     558                 :             : 
     559                 :             : /* Finds tailcalls falling into basic block BB when coming from edge ESUCC (or
     560                 :             :    NULL).  The list of found tailcalls is added to the start of RET.
     561                 :             :    When ONLY_MUSTTAIL is set only handle musttail.
     562                 :             :    Update OPT_TAILCALLS as output parameter.  If DIAG_MUSTTAIL, diagnose
     563                 :             :    failures for musttail calls.  RETRY_TSAN_FUNC_EXIT is initially 0 and
     564                 :             :    in that case the last call is attempted to be tail called, including
     565                 :             :    __tsan_func_exit with -fsanitize=thread.  It is set to -1 if we
     566                 :             :    detect __tsan_func_exit call and in that case tree_optimize_tail_calls_1
     567                 :             :    will retry with it set to 1 (regardless of whether turning the
     568                 :             :    __tsan_func_exit was successfully detected as tail call or not) and that
     569                 :             :    will allow turning musttail calls before that call into tail calls as well
     570                 :             :    by adding __tsan_func_exit call before the call.
     571                 :             :    IGNORED_EDGES and MUST_SEE_BBS are used in recursive calls when handling
     572                 :             :    GIMPLE_CONDs for cleanups.  */
     573                 :             : 
     574                 :             : static void
     575                 :     7207208 : find_tail_calls (basic_block bb, edge esucc, struct tailcall **ret,
     576                 :             :                  bool only_musttail, bool &opt_tailcalls, bool diag_musttail,
     577                 :             :                  int &retry_tsan_func_exit, hash_set<edge> *ignored_edges,
     578                 :             :                  hash_set<basic_block> *must_see_bbs)
     579                 :             : {
     580                 :     7207208 :   tree ass_var = NULL_TREE, ret_var, func, param;
     581                 :     7207208 :   gimple *stmt;
     582                 :     7207208 :   gcall *call = NULL;
     583                 :     7207208 :   gimple_stmt_iterator gsi, agsi;
     584                 :     7207208 :   bool tail_recursion;
     585                 :     7207208 :   struct tailcall *nw;
     586                 :     7207208 :   edge e;
     587                 :     7207208 :   tree m, a;
     588                 :     7207208 :   basic_block abb;
     589                 :     7207208 :   size_t idx;
     590                 :     7207208 :   tree var;
     591                 :     7207208 :   bool only_tailr = false;
     592                 :     7207208 :   bool has_tsan_func_exit = false;
     593                 :     7207208 :   int eh_has_tsan_func_exit = -1;
     594                 :     7207208 :   bool delete_ignored_edges = false;
     595                 :             : 
     596                 :     7207208 :   if (!single_succ_p (bb)
     597                 :     7207208 :       && (EDGE_COUNT (bb->succs) || !cfun->has_musttail || !diag_musttail))
     598                 :             :     {
     599                 :     1802390 :       if (EDGE_COUNT (bb->succs) == 2
     600                 :     1763213 :           && esucc
     601                 :     1763213 :           && cfun->has_musttail
     602                 :         451 :           && diag_musttail
     603                 :         314 :           && (EDGE_SUCC (bb, 0)->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
     604                 :         159 :           && (EDGE_SUCC (bb, 1)->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
     605                 :         159 :           && (stmt = last_nondebug_stmt (bb))
     606                 :     1802549 :           && gimple_code (stmt) == GIMPLE_COND)
     607                 :             :         ;
     608                 :             :       /* If there is an abnormal edge assume it's the only extra one.
     609                 :             :          Tolerate that case so that we can give better error messages
     610                 :             :          for musttail later.  */
     611                 :     1802231 :       else if (!has_abnormal_or_eh_outgoing_edge_p (bb))
     612                 :             :         {
     613                 :     1731146 :           if (dump_file)
     614                 :         108 :             fprintf (dump_file, "Basic block %d has extra exit edges\n",
     615                 :             :                      bb->index);
     616                 :     6371584 :           return;
     617                 :             :         }
     618                 :       71244 :       if (!cfun->has_musttail)
     619                 :             :         return;
     620                 :             :     }
     621                 :             : 
     622                 :     5405201 :   bool bad_stmt = false;
     623                 :     5405201 :   gimple *last_stmt = nullptr;
     624                 :    23466848 :   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
     625                 :             :     {
     626                 :    15356470 :       stmt = gsi_stmt (gsi);
     627                 :             : 
     628                 :             :       /* Ignore labels, returns, nops, clobbers and debug stmts.  */
     629                 :    15356470 :       if (gimple_code (stmt) == GIMPLE_LABEL
     630                 :             :           || gimple_code (stmt) == GIMPLE_RETURN
     631                 :             :           || gimple_code (stmt) == GIMPLE_NOP
     632                 :             :           || gimple_code (stmt) == GIMPLE_PREDICT
     633                 :    11579643 :           || gimple_clobber_p (stmt)
     634                 :    10565178 :           || is_gimple_debug (stmt))
     635                 :    11678603 :         continue;
     636                 :             : 
     637                 :     3677867 :       if (cfun->has_musttail
     638                 :        2395 :           && sanitize_flags_p (SANITIZE_THREAD)
     639                 :          44 :           && gimple_call_builtin_p (stmt, BUILT_IN_TSAN_FUNC_EXIT)
     640                 :     3677883 :           && diag_musttail)
     641                 :             :         {
     642                 :          16 :           if (retry_tsan_func_exit == 0)
     643                 :           8 :             retry_tsan_func_exit = -1;
     644                 :           8 :           else if (retry_tsan_func_exit == 1)
     645                 :           8 :             continue;
     646                 :             :         }
     647                 :             : 
     648                 :     3678111 :       if (cfun->has_musttail
     649                 :        2387 :           && sanitize_flags_p (SANITIZE_ADDRESS)
     650                 :         553 :           && asan_mark_p (stmt, ASAN_MARK_POISON)
     651                 :     3678255 :           && diag_musttail)
     652                 :         252 :         continue;
     653                 :             : 
     654                 :             :       /* Especially at -O0 with -fsanitize=address we can end up with
     655                 :             :          code like
     656                 :             :            _26 = foo (x_24(D)); [must tail call]
     657                 :             :            finally_tmp.3_27 = 0;
     658                 :             :            goto <bb 5>; [INV]
     659                 :             : 
     660                 :             :            ...
     661                 :             : 
     662                 :             :            <bb 5> :
     663                 :             :            # _6 = PHI <_26(3), _23(D)(4)>
     664                 :             :            # finally_tmp.3_8 = PHI <finally_tmp.3_27(3), finally_tmp.3_22(4)>
     665                 :             :            .ASAN_MARK (POISON, &c, 4);
     666                 :             :            if (finally_tmp.3_8 == 1)
     667                 :             :              goto <bb 7>; [INV]
     668                 :             :            else
     669                 :             :              goto <bb 6>; [INV]
     670                 :             :          When walking backwards, ESUCC is the edge we are coming from,
     671                 :             :          depending on its EDGE_TRUE_FLAG, == vs. != for the comparison
     672                 :             :          and value compared against try to find out through which edge
     673                 :             :          we need to go and which edge should be ignored.  The code handles
     674                 :             :          both INTEGER_CST PHI arguments and SSA_NAMEs set to constants
     675                 :             :          (for -O0 where those aren't propagated).  */
     676                 :     3677607 :       if (cfun->has_musttail
     677                 :             :           && diag_musttail
     678                 :        2135 :           && esucc
     679                 :        1287 :           && gimple_code (stmt) == GIMPLE_COND
     680                 :         159 :           && (gimple_cond_code (stmt) == EQ_EXPR
     681                 :           8 :               || gimple_cond_code (stmt) == NE_EXPR)
     682                 :         155 :           && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
     683                 :         155 :           && TREE_CODE (gimple_cond_rhs (stmt)) == INTEGER_CST
     684                 :         155 :           && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
     685                 :     3677762 :           && (integer_zerop (gimple_cond_rhs (stmt))
     686                 :         151 :               || integer_onep (gimple_cond_rhs (stmt))))
     687                 :             :         {
     688                 :          36 :           tree lhs = gimple_cond_lhs (stmt);
     689                 :          36 :           bool rhsv = integer_onep (gimple_cond_rhs (stmt));
     690                 :          72 :           if (((esucc->flags & EDGE_TRUE_VALUE) != 0)
     691                 :          36 :               ^ (gimple_cond_code (stmt) == EQ_EXPR))
     692                 :          36 :             rhsv = !rhsv;
     693                 :          36 :           if (!ignored_edges)
     694                 :             :             {
     695                 :          22 :               ignored_edges = new hash_set<edge>;
     696                 :          22 :               must_see_bbs = new hash_set<basic_block>;
     697                 :          22 :               delete_ignored_edges = true;
     698                 :             :             }
     699                 :          36 :           if (is_gimple_assign (SSA_NAME_DEF_STMT (lhs))
     700                 :          36 :               && (gimple_assign_rhs_code (SSA_NAME_DEF_STMT (lhs))
     701                 :             :                   == INTEGER_CST))
     702                 :             :             {
     703                 :           0 :               tree rhs = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (lhs));
     704                 :           0 :               if (rhsv ? integer_onep (rhs) : integer_zerop (rhs))
     705                 :           0 :                 continue;
     706                 :             :             }
     707                 :          36 :           else if (gimple_code (SSA_NAME_DEF_STMT (lhs)) == GIMPLE_PHI)
     708                 :             :             {
     709                 :          12 :               gimple *phi = SSA_NAME_DEF_STMT (lhs);
     710                 :          12 :               basic_block pbb = gimple_bb (phi);
     711                 :          12 :               must_see_bbs->add (pbb);
     712                 :          12 :               edge_iterator ei;
     713                 :          36 :               FOR_EACH_EDGE (e, ei, pbb->preds)
     714                 :             :                 {
     715                 :          24 :                   tree rhs = gimple_phi_arg_def_from_edge (phi, e);
     716                 :          24 :                   if (TREE_CODE (rhs) == SSA_NAME
     717                 :          24 :                       && is_gimple_assign (SSA_NAME_DEF_STMT (rhs))
     718                 :          48 :                       && (gimple_assign_rhs_code (SSA_NAME_DEF_STMT (rhs))
     719                 :             :                           == INTEGER_CST))
     720                 :          24 :                     rhs = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (rhs));
     721                 :          24 :                   if (!(rhsv ? integer_onep (rhs) : integer_zerop (rhs)))
     722                 :          12 :                     ignored_edges->add (e);
     723                 :             :                 }
     724                 :             :             }
     725                 :             :         }
     726                 :             : 
     727                 :     3677607 :       if (!last_stmt)
     728                 :     3047092 :         last_stmt = stmt;
     729                 :             :       /* Check for a call.  */
     730                 :     3677607 :       if (is_gimple_call (stmt))
     731                 :             :         {
     732                 :     1532427 :           call = as_a <gcall *> (stmt);
     733                 :             :           /* Handle only musttail calls when not optimizing.  */
     734                 :     1532427 :           if (only_musttail && !gimple_call_must_tail_p (call))
     735                 :             :             {
     736                 :     3872805 :             maybe_delete_ignored_edges:
     737                 :     3872805 :               if (delete_ignored_edges)
     738                 :             :                 {
     739                 :          44 :                   delete ignored_edges;
     740                 :          44 :                   delete must_see_bbs;
     741                 :             :                 }
     742                 :     3872805 :               return;
     743                 :             :             }
     744                 :     1532405 :           if (bad_stmt)
     745                 :             :             {
     746                 :           9 :               maybe_error_musttail (call, _("memory reference or volatile "
     747                 :             :                                             "after call"), diag_musttail);
     748                 :           9 :               goto maybe_delete_ignored_edges;
     749                 :             :             }
     750                 :     1532396 :           ass_var = gimple_call_lhs (call);
     751                 :     1532396 :           break;
     752                 :             :         }
     753                 :             : 
     754                 :             :       /* Allow simple copies between local variables, even if they're
     755                 :             :          aggregates.  */
     756                 :     2145180 :       if (is_gimple_assign (stmt)
     757                 :     2124263 :           && auto_var_in_fn_p (gimple_assign_lhs (stmt), cfun->decl)
     758                 :     2202304 :           && auto_var_in_fn_p (gimple_assign_rhs1 (stmt), cfun->decl))
     759                 :       28219 :         continue;
     760                 :             : 
     761                 :             :       /* If the statement references memory or volatile operands, fail.  */
     762                 :     2116961 :       if (gimple_references_memory_p (stmt)
     763                 :    13605527 :           || gimple_has_volatile_ops (stmt))
     764                 :             :         {
     765                 :     1167704 :           if (dump_file)
     766                 :             :             {
     767                 :          26 :               fprintf (dump_file, "Cannot handle ");
     768                 :          26 :               print_gimple_stmt (dump_file, stmt, 0);
     769                 :             :             }
     770                 :     1167704 :           bad_stmt = true;
     771                 :     1167704 :           if (!cfun->has_musttail)
     772                 :             :             break;
     773                 :             :         }
     774                 :             :     }
     775                 :             : 
     776                 :     5405170 :   if (bad_stmt)
     777                 :     1167655 :     goto maybe_delete_ignored_edges;
     778                 :             : 
     779                 :     4237515 :   if (gsi_end_p (gsi))
     780                 :             :     {
     781                 :     2705119 :       if (must_see_bbs)
     782                 :          36 :         must_see_bbs->remove (bb);
     783                 :             : 
     784                 :     2705119 :       edge_iterator ei;
     785                 :             :       /* Recurse to the predecessors.  */
     786                 :     6494591 :       FOR_EACH_EDGE (e, ei, bb->preds)
     787                 :             :         {
     788                 :     3789472 :           if (ignored_edges && ignored_edges->contains (e))
     789                 :          12 :             continue;
     790                 :     3789460 :           find_tail_calls (e->src, e, ret, only_musttail, opt_tailcalls,
     791                 :             :                            diag_musttail, retry_tsan_func_exit, ignored_edges,
     792                 :             :                            must_see_bbs);
     793                 :             :         }
     794                 :             : 
     795                 :     2705119 :       goto maybe_delete_ignored_edges;
     796                 :             :     }
     797                 :             : 
     798                 :     1532396 :   if (must_see_bbs && !must_see_bbs->is_empty ())
     799                 :           0 :     goto maybe_delete_ignored_edges;
     800                 :             : 
     801                 :     1532396 :   if (delete_ignored_edges)
     802                 :             :     {
     803                 :           0 :       delete ignored_edges;
     804                 :           0 :       delete must_see_bbs;
     805                 :             :     }
     806                 :             : 
     807                 :     1532396 :   if (!suitable_for_tail_opt_p (call, diag_musttail))
     808                 :             :     return;
     809                 :             : 
     810                 :     1514012 :   if (!suitable_for_tail_call_opt_p (call, diag_musttail))
     811                 :       15192 :     opt_tailcalls = false;
     812                 :             : 
     813                 :             :   /* ??? It is OK if the argument of a function is taken in some cases,
     814                 :             :      but not in all cases.  See PR15387 and PR19616.  Revisit for 4.1.  */
     815                 :     1514012 :   if (!diag_musttail || !gimple_call_must_tail_p (call))
     816                 :     1513318 :     for (param = DECL_ARGUMENTS (current_function_decl);
     817                 :     4469703 :          param; param = DECL_CHAIN (param))
     818                 :     2956385 :       if (TREE_ADDRESSABLE (param))
     819                 :             :         {
     820                 :       28649 :           maybe_error_musttail (call, _("address of caller arguments taken"),
     821                 :             :                                 diag_musttail);
     822                 :             :           /* If current function has musttail calls, we can't disable tail
     823                 :             :              calls altogether for the whole caller, because those might be
     824                 :             :              actually fine.  So just punt if this exact call is not
     825                 :             :              a tail recursion.  */
     826                 :       28649 :           if (cfun->has_musttail)
     827                 :             :             only_tailr = true;
     828                 :             :           else
     829                 :       28577 :             opt_tailcalls = false;
     830                 :             :         }
     831                 :             : 
     832                 :             :   /* If the LHS of our call is not just a simple register or local
     833                 :             :      variable, we can't transform this into a tail or sibling call.
     834                 :             :      This situation happens, in (e.g.) "*p = foo()" where foo returns a
     835                 :             :      struct.  In this case we won't have a temporary here, but we need
     836                 :             :      to carry out the side effect anyway, so tailcall is impossible.
     837                 :             : 
     838                 :             :      ??? In some situations (when the struct is returned in memory via
     839                 :             :      invisible argument) we could deal with this, e.g. by passing 'p'
     840                 :             :      itself as that argument to foo, but it's too early to do this here,
     841                 :             :      and expand_call() will not handle it anyway.  If it ever can, then
     842                 :             :      we need to revisit this here, to allow that situation.  */
     843                 :     1514012 :   if (ass_var
     844                 :      429780 :       && !is_gimple_reg (ass_var)
     845                 :     1572613 :       && !auto_var_in_fn_p (ass_var, cfun->decl))
     846                 :             :     {
     847                 :        7771 :       maybe_error_musttail (call, _("return value in memory"), diag_musttail);
     848                 :        7771 :       return;
     849                 :             :     }
     850                 :             : 
     851                 :     1506241 :   if (cfun->calls_setjmp)
     852                 :             :     {
     853                 :         164 :       maybe_error_musttail (call, _("caller uses setjmp"), diag_musttail);
     854                 :         164 :       return;
     855                 :             :     }
     856                 :             : 
     857                 :             :   /* If the call might throw an exception that wouldn't propagate out of
     858                 :             :      cfun, we can't transform to a tail or sibling call (82081).  */
     859                 :     1506077 :   if ((stmt_could_throw_p (cfun, stmt)
     860                 :     1506077 :        && !stmt_can_throw_external (cfun, stmt)) || EDGE_COUNT (bb->succs) > 1)
     861                 :             :   {
     862                 :       18967 :     if (stmt != last_stmt)
     863                 :             :       {
     864                 :          74 :         maybe_error_musttail (call, _("code between call and return"),
     865                 :             :                               diag_musttail);
     866                 :       18835 :         return;
     867                 :             :       }
     868                 :             : 
     869                 :       18893 :     edge e;
     870                 :       18893 :     edge_iterator ei;
     871                 :       37584 :     FOR_EACH_EDGE (e, ei, bb->succs)
     872                 :       18905 :       if (e->flags & EDGE_EH)
     873                 :             :         break;
     874                 :             : 
     875                 :       18893 :     if (!e)
     876                 :             :       {
     877                 :       18679 :         maybe_error_musttail (call, _("call may throw exception that does not "
     878                 :             :                                       "propagate"), diag_musttail);
     879                 :       18679 :         return;
     880                 :             :       }
     881                 :             : 
     882                 :         214 :     if (diag_musttail && gimple_call_must_tail_p (call))
     883                 :         137 :       eh_has_tsan_func_exit = 0;
     884                 :         214 :     if (!gimple_call_must_tail_p (call)
     885                 :         206 :         || !empty_eh_cleanup (e->dest,
     886                 :         206 :                               eh_has_tsan_func_exit
     887                 :             :                               ? NULL : &eh_has_tsan_func_exit, 20)
     888                 :         420 :         || EDGE_COUNT (bb->succs) > 2)
     889                 :             :       {
     890                 :           8 :         maybe_error_musttail (call, _("call may throw exception caught "
     891                 :             :                                       "locally or perform cleanups"),
     892                 :             :                               diag_musttail);
     893                 :           8 :         return;
     894                 :             :       }
     895                 :             :   }
     896                 :             : 
     897                 :             :   /* If the function returns a value, then at present, the tail call
     898                 :             :      must return the same type of value.  There is conceptually a copy
     899                 :             :      between the object returned by the tail call candidate and the
     900                 :             :      object returned by CFUN itself.
     901                 :             : 
     902                 :             :      This means that if we have:
     903                 :             : 
     904                 :             :          lhs = f (&<retval>);    // f reads from <retval>
     905                 :             :                                  // (lhs is usually also <retval>)
     906                 :             : 
     907                 :             :      there is a copy between the temporary object returned by f and lhs,
     908                 :             :      meaning that any use of <retval> in f occurs before the assignment
     909                 :             :      to lhs begins.  Thus the <retval> that is live on entry to the call
     910                 :             :      to f is really an independent local variable V that happens to be
     911                 :             :      stored in the RESULT_DECL rather than a local VAR_DECL.
     912                 :             : 
     913                 :             :      Turning this into a tail call would remove the copy and make the
     914                 :             :      lifetimes of the return value and V overlap.  The same applies to
     915                 :             :      tail recursion, since if f can read from <retval>, we have to assume
     916                 :             :      that CFUN might already have written to <retval> before the call.
     917                 :             : 
     918                 :             :      The problem doesn't apply when <retval> is passed by value, but that
     919                 :             :      isn't a case we handle anyway.  */
     920                 :     1487316 :   tree result_decl = DECL_RESULT (cfun->decl);
     921                 :     1487316 :   if (result_decl
     922                 :     1487316 :       && may_be_aliased (result_decl)
     923                 :     1492035 :       && ref_maybe_used_by_stmt_p (call, result_decl, false))
     924                 :             :     {
     925                 :        1538 :       maybe_error_musttail (call, _("return value used after call"),
     926                 :             :                             diag_musttail);
     927                 :        1538 :       return;
     928                 :             :     }
     929                 :             : 
     930                 :             :   /* We found the call, check whether it is suitable.  */
     931                 :     1485778 :   tail_recursion = false;
     932                 :     1485778 :   func = gimple_call_fndecl (call);
     933                 :     1485778 :   if (func
     934                 :     1410604 :       && !fndecl_built_in_p (func)
     935                 :     1079709 :       && recursive_call_p (current_function_decl, func)
     936                 :     1488722 :       && !only_musttail)
     937                 :             :     {
     938                 :        2921 :       tree arg;
     939                 :             : 
     940                 :        2921 :       for (param = DECL_ARGUMENTS (current_function_decl), idx = 0;
     941                 :       10025 :            param && idx < gimple_call_num_args (call);
     942                 :        7104 :            param = DECL_CHAIN (param), idx ++)
     943                 :             :         {
     944                 :        7217 :           arg = gimple_call_arg (call, idx);
     945                 :        7217 :           if (param != arg)
     946                 :             :             {
     947                 :             :               /* Make sure there are no problems with copying.  The parameter
     948                 :             :                  have a copyable type and the two arguments must have reasonably
     949                 :             :                  equivalent types.  The latter requirement could be relaxed if
     950                 :             :                  we emitted a suitable type conversion statement.  */
     951                 :        7005 :               if (TREE_ADDRESSABLE (TREE_TYPE (param))
     952                 :       14010 :                   || !useless_type_conversion_p (TREE_TYPE (param),
     953                 :        7005 :                                                  TREE_TYPE (arg)))
     954                 :             :                 break;
     955                 :             : 
     956                 :       13489 :               if (is_gimple_reg_type (TREE_TYPE (param))
     957                 :        6969 :                   ? !is_gimple_reg (param)
     958                 :         449 :                   : (!is_gimple_variable (param)
     959                 :         449 :                      || TREE_THIS_VOLATILE (param)
     960                 :         898 :                      || may_be_aliased (param)))
     961                 :             :                 break;
     962                 :             :             }
     963                 :             :         }
     964                 :        2921 :       if (idx == gimple_call_num_args (call) && !param)
     965                 :     1485778 :         tail_recursion = true;
     966                 :             :     }
     967                 :             : 
     968                 :     1485778 :   if (only_tailr && !tail_recursion)
     969                 :             :     return;
     970                 :             : 
     971                 :             :   /* Compute live vars if not computed yet.  */
     972                 :     1485706 :   if (live_vars == NULL)
     973                 :             :     {
     974                 :     1443425 :       unsigned int cnt = 0;
     975                 :    13212436 :       FOR_EACH_LOCAL_DECL (cfun, idx, var)
     976                 :    10521847 :         if (VAR_P (var)
     977                 :    10521847 :             && auto_var_in_fn_p (var, cfun->decl)
     978                 :    20921271 :             && may_be_aliased (var))
     979                 :             :           {
     980                 :      868296 :             if (live_vars == NULL)
     981                 :      207175 :               live_vars = new live_vars_map;
     982                 :      868296 :             live_vars->put (DECL_UID (var), cnt++);
     983                 :             :           }
     984                 :     1443425 :       if (live_vars)
     985                 :      207175 :         live_vars_vec = compute_live_vars (cfun, live_vars);
     986                 :             :     }
     987                 :             : 
     988                 :             :   /* Determine a bitmap of variables which are still in scope after the
     989                 :             :      call.  */
     990                 :     1485706 :   bitmap local_live_vars = NULL;
     991                 :     1485706 :   if (live_vars)
     992                 :      249456 :     local_live_vars = live_vars_at_stmt (live_vars_vec, live_vars, call);
     993                 :             : 
     994                 :             :   /* Make sure the tail invocation of this function does not indirectly
     995                 :             :      refer to local variables.  (Passing variables directly by value
     996                 :             :      is OK.)  */
     997                 :    13500220 :   FOR_EACH_LOCAL_DECL (cfun, idx, var)
     998                 :             :     {
     999                 :    10912374 :       if (TREE_CODE (var) != PARM_DECL
    1000                 :    10912374 :           && auto_var_in_fn_p (var, cfun->decl)
    1001                 :    10834892 :           && may_be_aliased (var)
    1002                 :    11627871 :           && (ref_maybe_used_by_stmt_p (call, var, false)
    1003                 :      325150 :               || call_may_clobber_ref_p (call, var, false)))
    1004                 :             :         {
    1005                 :      446902 :           if (!VAR_P (var))
    1006                 :             :             {
    1007                 :           0 :               if (diag_musttail && gimple_call_must_tail_p (call))
    1008                 :             :                 {
    1009                 :           0 :                   auto opt = OPT_Wmaybe_musttail_local_addr;
    1010                 :           0 :                   if (!warning_suppressed_p (call,
    1011                 :             :                                              opt))
    1012                 :             :                     {
    1013                 :           0 :                       warning_at (gimple_location (call), opt,
    1014                 :             :                                   "address of local variable can escape to "
    1015                 :             :                                   "%<musttail%> call");
    1016                 :           0 :                       suppress_warning (call, opt);
    1017                 :             :                     }
    1018                 :           0 :                   continue;
    1019                 :           0 :                 }
    1020                 :           0 :               if (local_live_vars)
    1021                 :           0 :                 BITMAP_FREE (local_live_vars);
    1022                 :           0 :               maybe_error_musttail (call, _("call invocation refers to "
    1023                 :             :                                             "locals"), diag_musttail);
    1024                 :           0 :               return;
    1025                 :             :             }
    1026                 :             :           else
    1027                 :             :             {
    1028                 :      446902 :               unsigned int *v = live_vars->get (DECL_UID (var));
    1029                 :      446902 :               if (bitmap_bit_p (local_live_vars, *v))
    1030                 :             :                 {
    1031                 :      187733 :                   if (diag_musttail && gimple_call_must_tail_p (call))
    1032                 :             :                     {
    1033                 :         428 :                       auto opt = OPT_Wmaybe_musttail_local_addr;
    1034                 :         428 :                       if (!warning_suppressed_p (call, opt))
    1035                 :             :                         {
    1036                 :         151 :                           if (!DECL_ARTIFICIAL (var) && DECL_NAME (var))
    1037                 :         150 :                             warning_at (gimple_location (call), opt,
    1038                 :             :                                         "address of automatic variable %qD "
    1039                 :             :                                         "can escape to %<musttail%> call",
    1040                 :             :                                         var);
    1041                 :             :                           else
    1042                 :           1 :                             warning_at (gimple_location (call), opt,
    1043                 :             :                                         "address of local variable can escape "
    1044                 :             :                                         "to %<musttail%> call");
    1045                 :         151 :                           suppress_warning (call, opt);
    1046                 :             :                         }
    1047                 :         428 :                       continue;
    1048                 :         428 :                     }
    1049                 :      187305 :                   BITMAP_FREE (local_live_vars);
    1050                 :      187305 :                   maybe_error_musttail (call, _("call invocation refers to "
    1051                 :             :                                                 "locals"), diag_musttail);
    1052                 :      187305 :                   return;
    1053                 :             :                 }
    1054                 :             :             }
    1055                 :             :         }
    1056                 :             :     }
    1057                 :     1298401 :   if (diag_musttail
    1058                 :      307469 :       && gimple_call_must_tail_p (call)
    1059                 :     1299086 :       && !warning_suppressed_p (call, OPT_Wmaybe_musttail_local_addr))
    1060                 :         387 :     for (tree param = DECL_ARGUMENTS (current_function_decl);
    1061                 :         761 :          param; param = DECL_CHAIN (param))
    1062                 :         399 :       if (may_be_aliased (param)
    1063                 :         399 :           && (ref_maybe_used_by_stmt_p (call, param, false)
    1064                 :           0 :               || call_may_clobber_ref_p (call, param, false)))
    1065                 :             :         {
    1066                 :          25 :           auto opt = OPT_Wmaybe_musttail_local_addr;
    1067                 :          25 :           warning_at (gimple_location (call), opt,
    1068                 :             :                       "address of parameter %qD can escape to "
    1069                 :             :                       "%<musttail%> call", param);
    1070                 :          25 :           suppress_warning (call, opt);
    1071                 :          25 :           break;
    1072                 :             :         }
    1073                 :             : 
    1074                 :     1298401 :   if (local_live_vars)
    1075                 :       62151 :     BITMAP_FREE (local_live_vars);
    1076                 :             : 
    1077                 :             :   /* Now check the statements after the call.  None of them has virtual
    1078                 :             :      operands, so they may only depend on the call through its return
    1079                 :             :      value.  The return value should also be dependent on each of them,
    1080                 :             :      since we are running after dce.  */
    1081                 :     1298401 :   m = NULL_TREE;
    1082                 :     1298401 :   a = NULL_TREE;
    1083                 :     2134025 :   auto_bitmap to_move_defs;
    1084                 :     2134025 :   auto_vec<gimple *> to_move_stmts;
    1085                 :     1298401 :   bool is_noreturn = gimple_call_noreturn_p (call);
    1086                 :     2134025 :   auto_vec<edge> edges;
    1087                 :             : 
    1088                 :     1298401 :   abb = bb;
    1089                 :     1298401 :   agsi = gsi;
    1090                 :     3066788 :   while (!is_noreturn)
    1091                 :             :     {
    1092                 :     3066122 :       tree tmp_a = NULL_TREE;
    1093                 :     3066122 :       tree tmp_m = NULL_TREE;
    1094                 :     3066122 :       gsi_next (&agsi);
    1095                 :             : 
    1096                 :             :     new_bb:
    1097                 :     3587392 :       while (gsi_end_p (agsi))
    1098                 :             :         {
    1099                 :      521258 :           edge e = single_non_eh_succ_edge (abb);
    1100                 :      521258 :           ass_var = propagate_through_phis (ass_var, e);
    1101                 :      521258 :           if (!ass_var || ignored_edges)
    1102                 :      433165 :             edges.safe_push (e);
    1103                 :      521258 :           abb = e->dest;
    1104                 :     1042516 :           agsi = gsi_start_bb (abb);
    1105                 :             :         }
    1106                 :             : 
    1107                 :     3066134 :       stmt = gsi_stmt (agsi);
    1108                 :     3066134 :       if (gimple_code (stmt) == GIMPLE_RETURN)
    1109                 :             :         break;
    1110                 :             : 
    1111                 :     3605967 :       if (gimple_code (stmt) == GIMPLE_LABEL
    1112                 :     1834119 :           || gimple_code (stmt) == GIMPLE_NOP
    1113                 :     1834119 :           || gimple_code (stmt) == GIMPLE_PREDICT
    1114                 :     1814816 :           || gimple_clobber_p (stmt)
    1115                 :     3506791 :           || is_gimple_debug (stmt))
    1116                 :     1746683 :         continue;
    1117                 :             : 
    1118                 :      113207 :       if (cfun->has_musttail
    1119                 :         528 :           && sanitize_flags_p (SANITIZE_THREAD)
    1120                 :          10 :           && retry_tsan_func_exit == 1
    1121                 :          10 :           && gimple_call_builtin_p (stmt, BUILT_IN_TSAN_FUNC_EXIT)
    1122                 :           8 :           && !has_tsan_func_exit
    1123                 :      113207 :           && gimple_call_must_tail_p (call))
    1124                 :             :         {
    1125                 :           8 :           has_tsan_func_exit = true;
    1126                 :           8 :           continue;
    1127                 :             :         }
    1128                 :             : 
    1129                 :      113443 :       if (cfun->has_musttail
    1130                 :         520 :           && sanitize_flags_p (SANITIZE_ADDRESS)
    1131                 :         279 :           && asan_mark_p (stmt, ASAN_MARK_POISON)
    1132                 :      113443 :           && diag_musttail)
    1133                 :         252 :         continue;
    1134                 :             : 
    1135                 :             :       /* See earlier comment on GIMPLE_CONDs.  Here we need to propagate
    1136                 :             :          through on the forward walk, so based on the edges vector we've
    1137                 :             :          walked through determine which edge to follow.  */ 
    1138                 :      112939 :       if (ignored_edges)
    1139                 :             :         {
    1140                 :          26 :           if (is_gimple_assign (stmt)
    1141                 :          26 :               && gimple_assign_rhs_code (stmt) == INTEGER_CST)
    1142                 :             :             {
    1143                 :          12 :               use_operand_p use_p;
    1144                 :          12 :               gimple *use_stmt;
    1145                 :          12 :               if ((integer_zerop (gimple_assign_rhs1 (stmt))
    1146                 :           0 :                    || integer_onep (gimple_assign_rhs1 (stmt)))
    1147                 :          12 :                   && single_imm_use (gimple_assign_lhs (stmt), &use_p,
    1148                 :             :                                      &use_stmt))
    1149                 :             :                 {
    1150                 :          12 :                   if (gimple_code (use_stmt) == GIMPLE_COND)
    1151                 :          12 :                     continue;
    1152                 :          24 :                   if (gimple_code (use_stmt) == GIMPLE_PHI
    1153                 :          12 :                       && single_imm_use (gimple_phi_result (use_stmt),
    1154                 :             :                                          &use_p, &use_stmt)
    1155                 :          24 :                       && gimple_code (use_stmt) == GIMPLE_COND)
    1156                 :          12 :                     continue;
    1157                 :             :                 }
    1158                 :             :             }
    1159                 :          14 :           if (gimple_code (stmt) == GIMPLE_COND
    1160                 :          12 :               && (gimple_cond_code (stmt) == EQ_EXPR
    1161                 :           0 :                   || gimple_cond_code (stmt) == NE_EXPR)
    1162                 :          12 :               && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
    1163                 :          12 :               && TREE_CODE (gimple_cond_rhs (stmt)) == INTEGER_CST
    1164                 :          12 :               && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
    1165                 :          26 :               && (integer_zerop (gimple_cond_rhs (stmt))
    1166                 :          12 :                   || integer_onep (gimple_cond_rhs (stmt))))
    1167                 :             :             {
    1168                 :          12 :               edge e = NULL, et, ef;
    1169                 :          12 :               tree lhs = gimple_cond_lhs (stmt);
    1170                 :          12 :               bool rhsv = integer_onep (gimple_cond_rhs (stmt));
    1171                 :          12 :               if (gimple_cond_code (stmt) == NE_EXPR)
    1172                 :           0 :                 rhsv = !rhsv;
    1173                 :          12 :               extract_true_false_edges_from_block (gimple_bb (stmt), &et, &ef);
    1174                 :          12 :               if (is_gimple_assign (SSA_NAME_DEF_STMT (lhs))
    1175                 :          12 :                   && (gimple_assign_rhs_code (SSA_NAME_DEF_STMT (lhs))
    1176                 :             :                       == INTEGER_CST))
    1177                 :             :                 {
    1178                 :           0 :                   tree rhs = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (lhs));
    1179                 :           0 :                   if (rhsv ? integer_onep (rhs) : integer_zerop (rhs))
    1180                 :           0 :                     e = et;
    1181                 :           0 :                   else if (rhsv ? integer_zerop (rhs) : integer_onep (rhs))
    1182                 :           0 :                     e = ef;
    1183                 :             :                 }
    1184                 :          12 :               else if (gimple_code (SSA_NAME_DEF_STMT (lhs)) == GIMPLE_PHI)
    1185                 :             :                 {
    1186                 :          12 :                   gimple *phi = SSA_NAME_DEF_STMT (lhs);
    1187                 :          12 :                   basic_block pbb = gimple_bb (phi);
    1188                 :          52 :                   for (edge e2 : edges)
    1189                 :          28 :                     if (e2->dest == pbb)
    1190                 :             :                       {
    1191                 :          12 :                         tree rhs = gimple_phi_arg_def_from_edge (phi, e2);
    1192                 :          12 :                         if (TREE_CODE (rhs) == SSA_NAME)
    1193                 :          12 :                           if (gimple *g = SSA_NAME_DEF_STMT (rhs))
    1194                 :          12 :                             if (is_gimple_assign (g)
    1195                 :          12 :                                 && gimple_assign_rhs_code (g) == INTEGER_CST)
    1196                 :          12 :                               rhs = gimple_assign_rhs1 (g);
    1197                 :          12 :                         if (rhsv ? integer_onep (rhs) : integer_zerop (rhs))
    1198                 :           0 :                           e = et;
    1199                 :          12 :                         else if (rhsv ? integer_zerop (rhs)
    1200                 :           0 :                                  : integer_onep (rhs))
    1201                 :          12 :                           e = ef;
    1202                 :             :                         break;
    1203                 :             :                       }
    1204                 :             :                 }
    1205                 :          12 :               if (e)
    1206                 :             :                 {
    1207                 :          12 :                   ass_var = propagate_through_phis (ass_var, e);
    1208                 :          12 :                   if (!ass_var || ignored_edges)
    1209                 :          12 :                     edges.safe_push (e);
    1210                 :          12 :                   abb = e->dest;
    1211                 :          12 :                   agsi = gsi_start_bb (abb);
    1212                 :          12 :                   goto new_bb;
    1213                 :             :                 }
    1214                 :             :             }
    1215                 :             :         }
    1216                 :             : 
    1217                 :      112915 :       if (gimple_code (stmt) != GIMPLE_ASSIGN)
    1218                 :             :         {
    1219                 :         258 :           maybe_error_musttail (call, _("unhandled code after call"),
    1220                 :             :                                 diag_musttail);
    1221                 :       91442 :           return;
    1222                 :             :         }
    1223                 :             : 
    1224                 :             :       /* This is a gimple assign. */
    1225                 :      112657 :       par ret = process_assignment (as_a <gassign *> (stmt), gsi,
    1226                 :             :                                     &tmp_m, &tmp_a, &ass_var, to_move_defs);
    1227                 :      112657 :       if (ret == FAIL || (ret == TRY_MOVE && !tail_recursion))
    1228                 :             :         {
    1229                 :       90913 :           maybe_error_musttail (call, _("return value changed after call"),
    1230                 :             :                                 diag_musttail);
    1231                 :       90913 :           return;
    1232                 :             :         }
    1233                 :       21744 :       else if (ret == TRY_MOVE)
    1234                 :             :         {
    1235                 :             :           /* Do not deal with checking dominance, the real fix is to
    1236                 :             :              do path isolation for the transform phase anyway, removing
    1237                 :             :              the need to compute the accumulators with new stmts.  */
    1238                 :          40 :           if (abb != bb)
    1239                 :             :             return;
    1240                 :          81 :           for (unsigned opno = 1; opno < gimple_num_ops (stmt); ++opno)
    1241                 :             :             {
    1242                 :          54 :               tree op = gimple_op (stmt, opno);
    1243                 :          54 :               if (independent_of_stmt_p (op, stmt, gsi, to_move_defs) != op)
    1244                 :             :                 return;
    1245                 :             :             }
    1246                 :          54 :           bitmap_set_bit (to_move_defs,
    1247                 :          27 :                           SSA_NAME_VERSION (gimple_assign_lhs (stmt)));
    1248                 :          27 :           to_move_stmts.safe_push (stmt);
    1249                 :          27 :           continue;
    1250                 :          27 :         }
    1251                 :             : 
    1252                 :       21704 :       if (tmp_a)
    1253                 :             :         {
    1254                 :        8346 :           tree type = TREE_TYPE (tmp_a);
    1255                 :        8346 :           if (a)
    1256                 :         296 :             a = fold_build2 (PLUS_EXPR, type, fold_convert (type, a), tmp_a);
    1257                 :             :           else
    1258                 :             :             a = tmp_a;
    1259                 :             :         }
    1260                 :       21704 :       if (tmp_m)
    1261                 :             :         {
    1262                 :        2125 :           tree type = TREE_TYPE (tmp_m);
    1263                 :        2125 :           if (m)
    1264                 :          76 :             m = fold_build2 (MULT_EXPR, type, fold_convert (type, m), tmp_m);
    1265                 :             :           else
    1266                 :             :             m = tmp_m;
    1267                 :             : 
    1268                 :        2125 :           if (a)
    1269                 :        1649 :             a = fold_build2 (MULT_EXPR, type, fold_convert (type, a), tmp_m);
    1270                 :             :         }
    1271                 :             :     }
    1272                 :             : 
    1273                 :             :   /* See if this is a tail call we can handle.  */
    1274                 :     1207217 :   if (is_noreturn)
    1275                 :             :     {
    1276                 :         666 :       if (gimple_call_internal_p (call))
    1277                 :             :         {
    1278                 :         654 :           maybe_error_musttail (call, _("internal call"), diag_musttail);
    1279                 :         654 :           return;
    1280                 :             :         }
    1281                 :          12 :       tree rettype = TREE_TYPE (TREE_TYPE (current_function_decl));
    1282                 :          12 :       tree calltype = TREE_TYPE (gimple_call_fntype (call));
    1283                 :          12 :       if (!VOID_TYPE_P (rettype)
    1284                 :          12 :           && !useless_type_conversion_p (rettype, calltype))
    1285                 :             :         {
    1286                 :           0 :           maybe_error_musttail (call, _("call and return value are different"),
    1287                 :             :                                 diag_musttail);
    1288                 :           0 :           return;
    1289                 :             :         }
    1290                 :             :       ret_var = NULL_TREE;
    1291                 :             :     }
    1292                 :             :   else
    1293                 :     1206551 :     ret_var = gimple_return_retval (as_a <greturn *> (stmt));
    1294                 :             : 
    1295                 :             :   /* We may proceed if there either is no return value, or the return value
    1296                 :             :      is identical to the call's return or if the return decl is an empty type
    1297                 :             :      variable and the call's return was not assigned. */
    1298                 :     1206551 :   if (ret_var
    1299                 :     1206551 :       && (ret_var != ass_var
    1300                 :      370277 :           && !(is_empty_type (TREE_TYPE (ret_var)) && !ass_var)))
    1301                 :             :     {
    1302                 :      369751 :       bool ok = false;
    1303                 :      369751 :       value_range val;
    1304                 :      369751 :       if (ass_var == NULL_TREE && !tail_recursion)
    1305                 :             :         {
    1306                 :      369647 :           tree other_value = NULL_TREE;
    1307                 :             :           /* If we have a function call that we know the return value is the same
    1308                 :             :              as the argument, try the argument too. */
    1309                 :      369647 :           int flags = gimple_call_return_flags (call);
    1310                 :      369647 :           if ((flags & ERF_RETURNS_ARG) != 0
    1311                 :      369647 :               && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (call))
    1312                 :             :             {
    1313                 :        4310 :               tree arg = gimple_call_arg (call, flags & ERF_RETURN_ARG_MASK);
    1314                 :        4310 :               if (useless_type_conversion_p (TREE_TYPE (ret_var), TREE_TYPE (arg) ))
    1315                 :             :                 other_value = arg;
    1316                 :             :             }
    1317                 :             :           /* If IPA-VRP proves called function always returns a singleton range,
    1318                 :             :              the return value is replaced by the only value in that range.
    1319                 :             :              For tail call purposes, pretend such replacement didn't happen.  */
    1320                 :      365337 :           else if (tree type = gimple_range_type (call))
    1321                 :       81801 :             if (tree callee = gimple_call_fndecl (call))
    1322                 :             :               {
    1323                 :       81238 :                 tree valr;
    1324                 :       81238 :                 if ((INTEGRAL_TYPE_P (type)
    1325                 :             :                      || SCALAR_FLOAT_TYPE_P (type)
    1326                 :       81238 :                      || POINTER_TYPE_P (type))
    1327                 :       81238 :                     && useless_type_conversion_p (TREE_TYPE (TREE_TYPE (callee)),
    1328                 :             :                                               type)
    1329                 :       81230 :                     && useless_type_conversion_p (TREE_TYPE (ret_var), type)
    1330                 :       21171 :                     && ipa_return_value_range (val, callee)
    1331                 :       90966 :                     && val.singleton_p (&valr))
    1332                 :        6441 :                   other_value = valr;
    1333                 :             :               }
    1334                 :             : 
    1335                 :       83722 :           if (other_value)
    1336                 :             :             {
    1337                 :        8925 :               tree rv = ret_var;
    1338                 :        8925 :               unsigned int i = edges.length ();
    1339                 :             :               /* If ret_var is equal to other_value, we can tail optimize.  */
    1340                 :        8925 :               if (operand_equal_p (ret_var, other_value, 0))
    1341                 :             :                 ok = true;
    1342                 :             :               else
    1343                 :             :                 /* Otherwise, if ret_var is a PHI result, try to find out
    1344                 :             :                    if other_value isn't propagated through PHIs on the path from
    1345                 :             :                    call's bb to SSA_NAME_DEF_STMT (ret_var)'s bb.  */
    1346                 :        3891 :                 while (TREE_CODE (rv) == SSA_NAME
    1347                 :        3891 :                       && gimple_code (SSA_NAME_DEF_STMT (rv)) == GIMPLE_PHI)
    1348                 :             :                   {
    1349                 :        1459 :                     tree nrv = NULL_TREE;
    1350                 :             :                     gimple *g = SSA_NAME_DEF_STMT (rv);
    1351                 :        1459 :                     for (; i; --i)
    1352                 :             :                       {
    1353                 :        1459 :                         if (edges[i - 1]->dest == gimple_bb (g))
    1354                 :             :                           {
    1355                 :        1459 :                             nrv = gimple_phi_arg_def_from_edge (g,
    1356                 :        1459 :                                                                 edges[i - 1]);
    1357                 :        1459 :                             --i;
    1358                 :        1459 :                             break;
    1359                 :             :                           }
    1360                 :             :                       }
    1361                 :        1459 :                     if (nrv == NULL_TREE)
    1362                 :             :                       break;
    1363                 :        1459 :                     if (operand_equal_p (nrv, other_value, 0))
    1364                 :             :                       {
    1365                 :             :                         ok = true;
    1366                 :             :                         break;
    1367                 :             :                       }
    1368                 :             :                       rv = nrv;
    1369                 :             :                   }
    1370                 :             :           }
    1371                 :             :         }
    1372                 :        2793 :       if (!ok)
    1373                 :             :         {
    1374                 :      363258 :           maybe_error_musttail (call, _("call and return value are different"),
    1375                 :             :                                 diag_musttail);
    1376                 :      363258 :           return;
    1377                 :             :         }
    1378                 :      369751 :     }
    1379                 :             : 
    1380                 :             :   /* If this is not a tail recursive call, we cannot handle addends or
    1381                 :             :      multiplicands.  */
    1382                 :      843305 :   if (!tail_recursion && (m || a))
    1383                 :             :     {
    1384                 :        7681 :       maybe_error_musttail (call, _("operations after non tail recursive "
    1385                 :             :                                     "call"), diag_musttail);
    1386                 :        7681 :       return;
    1387                 :             :     }
    1388                 :             : 
    1389                 :             :   /* For pointers only allow additions.  */
    1390                 :        2133 :   if (m && POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
    1391                 :             :     {
    1392                 :           0 :       maybe_error_musttail (call, _("tail recursion with pointers can only "
    1393                 :             :                                     "use additions"), diag_musttail);
    1394                 :           0 :       return;
    1395                 :             :     }
    1396                 :             : 
    1397                 :      835624 :   if (eh_has_tsan_func_exit != -1
    1398                 :         137 :       && eh_has_tsan_func_exit != has_tsan_func_exit)
    1399                 :             :     {
    1400                 :           0 :       if (eh_has_tsan_func_exit)
    1401                 :           0 :         maybe_error_musttail (call, _("call may throw exception caught "
    1402                 :             :                                       "locally or perform cleanups"),
    1403                 :             :                               diag_musttail);
    1404                 :             :       else
    1405                 :           0 :         maybe_error_musttail (call, _("exception cleanups omit "
    1406                 :             :                                       "__tsan_func_exit call"), diag_musttail);
    1407                 :           0 :       return;
    1408                 :             :     }
    1409                 :             : 
    1410                 :             :   /* Move queued defs.  */
    1411                 :      835624 :   if (tail_recursion)
    1412                 :             :     {
    1413                 :             :       unsigned i;
    1414                 :        2136 :       FOR_EACH_VEC_ELT (to_move_stmts, i, stmt)
    1415                 :             :         {
    1416                 :           3 :           gimple_stmt_iterator mgsi = gsi_for_stmt (stmt);
    1417                 :           3 :           gsi_move_before (&mgsi, &gsi);
    1418                 :             :         }
    1419                 :        2133 :       if (!tailr_arg_needs_copy)
    1420                 :        1206 :         tailr_arg_needs_copy = BITMAP_ALLOC (NULL);
    1421                 :        2133 :       for (param = DECL_ARGUMENTS (current_function_decl), idx = 0;
    1422                 :        7856 :            param;
    1423                 :        5723 :            param = DECL_CHAIN (param), idx++)
    1424                 :             :         {
    1425                 :        5723 :           tree ddef, arg = gimple_call_arg (call, idx);
    1426                 :        5723 :           if (!is_gimple_reg (param)
    1427                 :        5723 :               || ((ddef = ssa_default_def (cfun, param))
    1428                 :        5233 :                   && arg != ddef))
    1429                 :        2770 :             bitmap_set_bit (tailr_arg_needs_copy, idx);
    1430                 :             :         }
    1431                 :             :     }
    1432                 :             : 
    1433                 :      835624 :   nw = XNEW (struct tailcall);
    1434                 :             : 
    1435                 :      835624 :   nw->call_gsi = gsi;
    1436                 :             : 
    1437                 :      835624 :   nw->tail_recursion = tail_recursion;
    1438                 :      835624 :   nw->has_tsan_func_exit = has_tsan_func_exit;
    1439                 :             : 
    1440                 :      835624 :   nw->mult = m;
    1441                 :      835624 :   nw->add = a;
    1442                 :             : 
    1443                 :      835624 :   nw->next = *ret;
    1444                 :      835624 :   *ret = nw;
    1445                 :             : }
    1446                 :             : 
    1447                 :             : /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E.  */
    1448                 :             : 
    1449                 :             : static void
    1450                 :         212 : add_successor_phi_arg (edge e, tree var, tree phi_arg)
    1451                 :             : {
    1452                 :         212 :   gphi_iterator gsi;
    1453                 :             : 
    1454                 :         450 :   for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
    1455                 :         450 :     if (PHI_RESULT (gsi.phi ()) == var)
    1456                 :             :       break;
    1457                 :             : 
    1458                 :         212 :   gcc_assert (!gsi_end_p (gsi));
    1459                 :         212 :   add_phi_arg (gsi.phi (), phi_arg, e, UNKNOWN_LOCATION);
    1460                 :         212 : }
    1461                 :             : 
    1462                 :             : /* Creates a GIMPLE statement which computes the operation specified by
    1463                 :             :    CODE, ACC and OP1 to a new variable with name LABEL and inserts the
    1464                 :             :    statement in the position specified by GSI.  Returns the
    1465                 :             :    tree node of the statement's result.  */
    1466                 :             : 
    1467                 :             : static tree
    1468                 :         178 : adjust_return_value_with_ops (enum tree_code code, const char *label,
    1469                 :             :                               tree acc, tree op1, gimple_stmt_iterator gsi)
    1470                 :             : {
    1471                 :             : 
    1472                 :         178 :   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
    1473                 :         178 :   tree result = make_temp_ssa_name (ret_type, NULL, label);
    1474                 :         178 :   gassign *stmt;
    1475                 :             : 
    1476                 :         178 :   if (POINTER_TYPE_P (ret_type))
    1477                 :             :     {
    1478                 :           6 :       gcc_assert (code == PLUS_EXPR && TREE_TYPE (acc) == sizetype);
    1479                 :             :       code = POINTER_PLUS_EXPR;
    1480                 :             :     }
    1481                 :         178 :   if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1))
    1482                 :         178 :       && code != POINTER_PLUS_EXPR)
    1483                 :         167 :     stmt = gimple_build_assign (result, code, acc, op1);
    1484                 :             :   else
    1485                 :             :     {
    1486                 :          11 :       tree tem;
    1487                 :          11 :       if (code == POINTER_PLUS_EXPR)
    1488                 :           6 :         tem = fold_build2 (code, TREE_TYPE (op1), op1, acc);
    1489                 :             :       else
    1490                 :           5 :         tem = fold_build2 (code, TREE_TYPE (op1),
    1491                 :             :                            fold_convert (TREE_TYPE (op1), acc), op1);
    1492                 :          11 :       tree rhs = fold_convert (ret_type, tem);
    1493                 :          11 :       rhs = force_gimple_operand_gsi (&gsi, rhs,
    1494                 :             :                                       false, NULL, true, GSI_SAME_STMT);
    1495                 :          11 :       stmt = gimple_build_assign (result, rhs);
    1496                 :             :     }
    1497                 :             : 
    1498                 :         178 :   gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
    1499                 :         178 :   return result;
    1500                 :             : }
    1501                 :             : 
    1502                 :             : /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
    1503                 :             :    the computation specified by CODE and OP1 and insert the statement
    1504                 :             :    at the position specified by GSI as a new statement.  Returns new SSA name
    1505                 :             :    of updated accumulator.  */
    1506                 :             : 
    1507                 :             : static tree
    1508                 :         209 : update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
    1509                 :             :                              gimple_stmt_iterator gsi)
    1510                 :             : {
    1511                 :         209 :   gassign *stmt;
    1512                 :         209 :   tree var = copy_ssa_name (acc);
    1513                 :         209 :   if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
    1514                 :         195 :     stmt = gimple_build_assign (var, code, acc, op1);
    1515                 :             :   else
    1516                 :             :     {
    1517                 :          14 :       tree rhs = fold_convert (TREE_TYPE (acc),
    1518                 :             :                                fold_build2 (code,
    1519                 :             :                                             TREE_TYPE (op1),
    1520                 :             :                                             fold_convert (TREE_TYPE (op1), acc),
    1521                 :             :                                             op1));
    1522                 :          14 :       rhs = force_gimple_operand_gsi (&gsi, rhs,
    1523                 :             :                                       false, NULL, false, GSI_CONTINUE_LINKING);
    1524                 :          14 :       stmt = gimple_build_assign (var, rhs);
    1525                 :             :     }
    1526                 :         209 :   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
    1527                 :         209 :   return var;
    1528                 :             : }
    1529                 :             : 
    1530                 :             : /* Adjust the accumulator values according to A and M after GSI, and update
    1531                 :             :    the phi nodes on edge BACK.  */
    1532                 :             : 
    1533                 :             : static void
    1534                 :        2127 : adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
    1535                 :             : {
    1536                 :        2127 :   tree var, a_acc_arg, m_acc_arg;
    1537                 :             : 
    1538                 :        2127 :   if (m)
    1539                 :         115 :     m = force_gimple_operand_gsi (&gsi, m, true, NULL, true, GSI_SAME_STMT);
    1540                 :        2127 :   if (a)
    1541                 :          94 :     a = force_gimple_operand_gsi (&gsi, a, true, NULL, true, GSI_SAME_STMT);
    1542                 :             : 
    1543                 :        2127 :   a_acc_arg = a_acc;
    1544                 :        2127 :   m_acc_arg = m_acc;
    1545                 :        2127 :   if (a)
    1546                 :             :     {
    1547                 :          94 :       if (m_acc)
    1548                 :             :         {
    1549                 :          18 :           if (integer_onep (a))
    1550                 :           1 :             var = m_acc;
    1551                 :             :           else
    1552                 :          17 :             var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc,
    1553                 :             :                                                 a, gsi);
    1554                 :             :         }
    1555                 :             :       else
    1556                 :             :         var = a;
    1557                 :             : 
    1558                 :          94 :       a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi);
    1559                 :             :     }
    1560                 :             : 
    1561                 :        2127 :   if (m)
    1562                 :         115 :     m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi);
    1563                 :             : 
    1564                 :        2127 :   if (a_acc)
    1565                 :          97 :     add_successor_phi_arg (back, a_acc, a_acc_arg);
    1566                 :             : 
    1567                 :        2127 :   if (m_acc)
    1568                 :         115 :     add_successor_phi_arg (back, m_acc, m_acc_arg);
    1569                 :        2127 : }
    1570                 :             : 
    1571                 :             : /* Adjust value of the return at the end of BB according to M and A
    1572                 :             :    accumulators.  */
    1573                 :             : 
    1574                 :             : static void
    1575                 :         148 : adjust_return_value (basic_block bb, tree m, tree a)
    1576                 :             : {
    1577                 :         148 :   tree retval;
    1578                 :         296 :   greturn *ret_stmt = as_a <greturn *> (gimple_seq_last_stmt (bb_seq (bb)));
    1579                 :         148 :   gimple_stmt_iterator gsi = gsi_last_bb (bb);
    1580                 :             : 
    1581                 :         148 :   gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN);
    1582                 :             : 
    1583                 :         148 :   retval = gimple_return_retval (ret_stmt);
    1584                 :         148 :   if (!retval || retval == error_mark_node)
    1585                 :           0 :     return;
    1586                 :             : 
    1587                 :         148 :   if (m)
    1588                 :          86 :     retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval,
    1589                 :             :                                            gsi);
    1590                 :         148 :   if (a)
    1591                 :          75 :     retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval,
    1592                 :             :                                            gsi);
    1593                 :         148 :   gimple_return_set_retval (ret_stmt, retval);
    1594                 :         148 :   update_stmt (ret_stmt);
    1595                 :             : }
    1596                 :             : 
    1597                 :             : /* Subtract COUNT and FREQUENCY from the basic block and it's
    1598                 :             :    outgoing edge.  */
    1599                 :             : static void
    1600                 :        6116 : decrease_profile (basic_block bb, profile_count count)
    1601                 :             : {
    1602                 :           0 :   bb->count = bb->count - count;
    1603                 :           0 : }
    1604                 :             : 
    1605                 :             : /* Eliminates tail call described by T.  TMP_VARS is a list of
    1606                 :             :    temporary variables used to copy the function arguments.
    1607                 :             :    Allocates *NEW_LOOP if not already done and initializes it.  */
    1608                 :             : 
    1609                 :             : static void
    1610                 :        2127 : eliminate_tail_call (struct tailcall *t, class loop *&new_loop)
    1611                 :             : {
    1612                 :        2127 :   tree param, rslt;
    1613                 :        2127 :   gimple *stmt, *call;
    1614                 :        2127 :   tree arg;
    1615                 :        2127 :   size_t idx;
    1616                 :        2127 :   basic_block bb, first;
    1617                 :        2127 :   edge e;
    1618                 :        2127 :   gphi *phi;
    1619                 :        2127 :   gphi_iterator gpi;
    1620                 :        2127 :   gimple_stmt_iterator gsi;
    1621                 :        2127 :   gimple *orig_stmt;
    1622                 :             : 
    1623                 :        2127 :   stmt = orig_stmt = gsi_stmt (t->call_gsi);
    1624                 :        2127 :   bb = gsi_bb (t->call_gsi);
    1625                 :             : 
    1626                 :        2127 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1627                 :             :     {
    1628                 :           8 :       fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
    1629                 :             :                bb->index);
    1630                 :           8 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1631                 :           8 :       fprintf (dump_file, "\n");
    1632                 :             :     }
    1633                 :             : 
    1634                 :        2127 :   gcc_assert (is_gimple_call (stmt));
    1635                 :             : 
    1636                 :        2127 :   first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
    1637                 :             : 
    1638                 :             :   /* Remove the code after call_gsi that will become unreachable.  The
    1639                 :             :      possibly unreachable code in other blocks is removed later in
    1640                 :             :      cfg cleanup.  */
    1641                 :        2127 :   gsi = t->call_gsi;
    1642                 :        2127 :   gimple_stmt_iterator gsi2 = gsi_last_bb (gimple_bb (gsi_stmt (gsi)));
    1643                 :        3461 :   while (gsi_stmt (gsi2) != gsi_stmt (gsi))
    1644                 :             :     {
    1645                 :        1334 :       gimple *t = gsi_stmt (gsi2);
    1646                 :             :       /* Do not remove the return statement, so that redirect_edge_and_branch
    1647                 :             :          sees how the block ends.  */
    1648                 :        1334 :       if (gimple_code (t) != GIMPLE_RETURN)
    1649                 :             :         {
    1650                 :        1081 :           gimple_stmt_iterator gsi3 = gsi2;
    1651                 :        1081 :           gsi_prev (&gsi2);
    1652                 :        1081 :           gsi_remove (&gsi3, true);
    1653                 :        1081 :           release_defs (t);
    1654                 :             :         }
    1655                 :             :       else
    1656                 :        3714 :         gsi_prev (&gsi2);
    1657                 :             :     }
    1658                 :             : 
    1659                 :        2127 :   if (gimple_call_noreturn_p (as_a <gcall *> (stmt)))
    1660                 :             :     {
    1661                 :           4 :       e = make_edge (gsi_bb (t->call_gsi), first, EDGE_FALLTHRU);
    1662                 :           4 :       e->probability = profile_probability::always ();
    1663                 :             :     }
    1664                 :             :   else
    1665                 :             :     {
    1666                 :             :       /* Number of executions of function has reduced by the tailcall.  */
    1667                 :        2123 :       e = single_non_eh_succ_edge (gsi_bb (t->call_gsi));
    1668                 :             : 
    1669                 :        2123 :       profile_count count = e->count ();
    1670                 :             : 
    1671                 :             :       /* When profile is inconsistent and the recursion edge is more frequent
    1672                 :             :          than number of executions of functions, scale it down, so we do not
    1673                 :             :          end up with 0 executions of entry block.  */
    1674                 :        2123 :       if (count >= ENTRY_BLOCK_PTR_FOR_FN (cfun)->count)
    1675                 :          38 :         count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.apply_scale (7, 8);
    1676                 :        2123 :       decrease_profile (EXIT_BLOCK_PTR_FOR_FN (cfun), count);
    1677                 :        2123 :       decrease_profile (ENTRY_BLOCK_PTR_FOR_FN (cfun), count);
    1678                 :        2123 :       if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
    1679                 :        1870 :         decrease_profile (e->dest, count);
    1680                 :             : 
    1681                 :             :       /* Replace the call by a jump to the start of function.  */
    1682                 :        2123 :       e = redirect_edge_and_branch (e, first);
    1683                 :             :     }
    1684                 :        2127 :   gcc_assert (e);
    1685                 :        2127 :   PENDING_STMT (e) = NULL;
    1686                 :             : 
    1687                 :             :   /* Add the new loop.  */
    1688                 :        2127 :   if (!new_loop)
    1689                 :             :     {
    1690                 :        1204 :       new_loop = alloc_loop ();
    1691                 :        1204 :       new_loop->header = first;
    1692                 :        1204 :       new_loop->finite_p = true;
    1693                 :             :     }
    1694                 :             :   else
    1695                 :         923 :     gcc_assert (new_loop->header == first);
    1696                 :             : 
    1697                 :             :   /* Add phi node entries for arguments.  The ordering of the phi nodes should
    1698                 :             :      be the same as the ordering of the arguments.  */
    1699                 :        2127 :   auto_vec<tree> copies;
    1700                 :        2127 :   for (param = DECL_ARGUMENTS (current_function_decl),
    1701                 :        2127 :          idx = 0, gpi = gsi_start_phis (first);
    1702                 :        7838 :        param;
    1703                 :        5711 :        param = DECL_CHAIN (param), idx++)
    1704                 :             :     {
    1705                 :        5711 :       if (!bitmap_bit_p (tailr_arg_needs_copy, idx))
    1706                 :        2938 :         continue;
    1707                 :             : 
    1708                 :        2773 :       if (!is_gimple_reg_type (TREE_TYPE (param)))
    1709                 :             :         {
    1710                 :         452 :           if (param == gimple_call_arg (stmt, idx))
    1711                 :         160 :             continue;
    1712                 :             :           /* First check if param isn't used by any of the following
    1713                 :             :              call arguments.  If it is, we need to copy first to
    1714                 :             :              a temporary and only after doing all the assignments copy it
    1715                 :             :              to param.  */
    1716                 :         292 :           size_t idx2 = idx + 1;
    1717                 :         292 :           tree param2 = DECL_CHAIN (param);
    1718                 :        1503 :           for (; param2; param2 = DECL_CHAIN (param2), idx2++)
    1719                 :        1212 :             if (!is_gimple_reg_type (TREE_TYPE (param)))
    1720                 :             :               {
    1721                 :        1212 :                 tree base = get_base_address (gimple_call_arg (stmt, idx2));
    1722                 :        1212 :                 if (base == param)
    1723                 :             :                   break;
    1724                 :             :               }
    1725                 :         292 :           tree tmp = param;
    1726                 :         292 :           if (param2)
    1727                 :             :             {
    1728                 :           1 :               tmp = create_tmp_var (TREE_TYPE (param));
    1729                 :           1 :               copies.safe_push (param);
    1730                 :           1 :               copies.safe_push (tmp);
    1731                 :             :             }
    1732                 :         292 :           gimple *g = gimple_build_assign (tmp, gimple_call_arg (stmt, idx));
    1733                 :         292 :           gsi_insert_before (&t->call_gsi, g, GSI_SAME_STMT);
    1734                 :         292 :           continue;
    1735                 :         292 :         }
    1736                 :             : 
    1737                 :        2321 :       arg = gimple_call_arg (stmt, idx);
    1738                 :        2321 :       phi = gpi.phi ();
    1739                 :        2321 :       gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
    1740                 :             : 
    1741                 :        2321 :       add_phi_arg (phi, arg, e, gimple_location (stmt));
    1742                 :        2321 :       gsi_next (&gpi);
    1743                 :             :     }
    1744                 :        2128 :   for (unsigned i = 0; i < copies.length (); i += 2)
    1745                 :             :     {
    1746                 :           1 :       gimple *g = gimple_build_assign (copies[i], copies[i + 1]);
    1747                 :           1 :       gsi_insert_before (&t->call_gsi, g, GSI_SAME_STMT);
    1748                 :             :     }
    1749                 :             : 
    1750                 :             :   /* Update the values of accumulators.  */
    1751                 :        2127 :   adjust_accumulator_values (t->call_gsi, t->mult, t->add, e);
    1752                 :             : 
    1753                 :        2127 :   call = gsi_stmt (t->call_gsi);
    1754                 :        2127 :   rslt = gimple_call_lhs (call);
    1755                 :        2127 :   if (rslt != NULL_TREE && TREE_CODE (rslt) == SSA_NAME)
    1756                 :             :     {
    1757                 :             :       /* Result of the call will no longer be defined.  So adjust the
    1758                 :             :          SSA_NAME_DEF_STMT accordingly.  */
    1759                 :         524 :       SSA_NAME_DEF_STMT (rslt) = gimple_build_nop ();
    1760                 :             :     }
    1761                 :             : 
    1762                 :        2127 :   gsi_remove (&t->call_gsi, true);
    1763                 :        2127 :   release_defs (call);
    1764                 :        2127 : }
    1765                 :             : 
    1766                 :             : /* Optimizes the tailcall described by T.  If OPT_TAILCALLS is true, also
    1767                 :             :    mark the tailcalls for the sibcall optimization.  */
    1768                 :             : 
    1769                 :             : static bool
    1770                 :      835618 : optimize_tail_call (struct tailcall *t, bool opt_tailcalls,
    1771                 :             :                     class loop *&new_loop)
    1772                 :             : {
    1773                 :      835618 :   if (t->has_tsan_func_exit && (t->tail_recursion || opt_tailcalls))
    1774                 :             :     {
    1775                 :           8 :       tree builtin_decl = builtin_decl_implicit (BUILT_IN_TSAN_FUNC_EXIT);
    1776                 :           8 :       gimple *g = gimple_build_call (builtin_decl, 0);
    1777                 :           8 :       gimple_set_location (g, cfun->function_end_locus);
    1778                 :           8 :       gsi_insert_before (&t->call_gsi, g, GSI_SAME_STMT);
    1779                 :             :     }
    1780                 :             : 
    1781                 :      835618 :   if (t->tail_recursion)
    1782                 :             :     {
    1783                 :        2127 :       eliminate_tail_call (t, new_loop);
    1784                 :        2127 :       return true;
    1785                 :             :     }
    1786                 :             : 
    1787                 :      833491 :   if (opt_tailcalls)
    1788                 :             :     {
    1789                 :      172808 :       gcall *stmt = as_a <gcall *> (gsi_stmt (t->call_gsi));
    1790                 :             : 
    1791                 :      172808 :       gimple_call_set_tail (stmt, true);
    1792                 :      172808 :       cfun->tail_call_marked = true;
    1793                 :      172808 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1794                 :             :         {
    1795                 :          25 :           fprintf (dump_file, "Found tail call ");
    1796                 :          25 :           print_gimple_stmt (dump_file, stmt, 0, dump_flags);
    1797                 :          25 :           fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index);
    1798                 :             :         }
    1799                 :      172808 :       return t->has_tsan_func_exit;
    1800                 :             :     }
    1801                 :             : 
    1802                 :             :   return false;
    1803                 :             : }
    1804                 :             : 
    1805                 :             : /* Creates a tail-call accumulator of the same type as the return type of the
    1806                 :             :    current function.  LABEL is the name used to creating the temporary
    1807                 :             :    variable for the accumulator.  The accumulator will be inserted in the
    1808                 :             :    phis of a basic block BB with single predecessor with an initial value
    1809                 :             :    INIT converted to the current function return type.  */
    1810                 :             : 
    1811                 :             : static tree
    1812                 :         194 : create_tailcall_accumulator (const char *label, basic_block bb, tree init)
    1813                 :             : {
    1814                 :         194 :   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
    1815                 :         194 :   if (POINTER_TYPE_P (ret_type))
    1816                 :           6 :     ret_type = sizetype;
    1817                 :             : 
    1818                 :         194 :   tree tmp = make_temp_ssa_name (ret_type, NULL, label);
    1819                 :         194 :   gphi *phi;
    1820                 :             : 
    1821                 :         194 :   phi = create_phi_node (tmp, bb);
    1822                 :         194 :   add_phi_arg (phi, init, single_pred_edge (bb),
    1823                 :             :                UNKNOWN_LOCATION);
    1824                 :         194 :   return PHI_RESULT (phi);
    1825                 :             : }
    1826                 :             : 
    1827                 :             : /* Optimizes tail calls in the function, turning the tail recursion
    1828                 :             :    into iteration.  When ONLY_MUSTTAIL is true only optimize musttail
    1829                 :             :    marked calls.  When DIAG_MUSTTAIL, diagnose if musttail calls can't
    1830                 :             :    be tail call optimized.  */
    1831                 :             : 
    1832                 :             : static unsigned int
    1833                 :     3485718 : tree_optimize_tail_calls_1 (bool opt_tailcalls, bool only_musttail,
    1834                 :             :                             bool diag_musttail)
    1835                 :             : {
    1836                 :     3485718 :   edge e;
    1837                 :     3485718 :   bool phis_constructed = false;
    1838                 :     3485718 :   struct tailcall *tailcalls = NULL, *act, *next;
    1839                 :     3485718 :   bool changed = false;
    1840                 :     3485718 :   basic_block first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
    1841                 :     3485718 :   tree param;
    1842                 :     3485718 :   edge_iterator ei;
    1843                 :             : 
    1844                 :     6904296 :   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
    1845                 :             :     {
    1846                 :             :       /* Only traverse the normal exits, i.e. those that end with return
    1847                 :             :          statement.  */
    1848                 :    10254884 :       if (safe_is_a <greturn *> (*gsi_last_bb (e->src)))
    1849                 :             :         {
    1850                 :     3417728 :           int retry_tsan_func_exit = 0;
    1851                 :     3417728 :           find_tail_calls (e->src, e, &tailcalls, only_musttail, opt_tailcalls,
    1852                 :             :                            diag_musttail, retry_tsan_func_exit, NULL, NULL);
    1853                 :     3417728 :           if (retry_tsan_func_exit == -1)
    1854                 :             :             {
    1855                 :           8 :               retry_tsan_func_exit = 1;
    1856                 :           8 :               find_tail_calls (e->src, e, &tailcalls, only_musttail,
    1857                 :             :                                opt_tailcalls, diag_musttail,
    1858                 :             :                                retry_tsan_func_exit, NULL, NULL);
    1859                 :             :             }
    1860                 :             :         }
    1861                 :             :     }
    1862                 :     3485718 :   if (cfun->has_musttail && diag_musttail)
    1863                 :             :     {
    1864                 :         445 :       basic_block bb;
    1865                 :         445 :       int retry_tsan_func_exit = 0;
    1866                 :        2766 :       FOR_EACH_BB_FN (bb, cfun)
    1867                 :        2321 :         if (EDGE_COUNT (bb->succs) == 0
    1868                 :        2197 :             || (single_succ_p (bb)
    1869                 :        1490 :                 && (single_succ_edge (bb)->flags & EDGE_EH)))
    1870                 :         210 :           if (gimple *c = last_nondebug_stmt (bb))
    1871                 :         210 :             if (is_gimple_call (c)
    1872                 :          12 :                 && gimple_call_must_tail_p (as_a <gcall *> (c))
    1873                 :         222 :                 && gimple_call_noreturn_p (as_a <gcall *> (c)))
    1874                 :          12 :               find_tail_calls (bb, NULL, &tailcalls, only_musttail,
    1875                 :             :                                opt_tailcalls, diag_musttail,
    1876                 :             :                                retry_tsan_func_exit, NULL, NULL);
    1877                 :             :     }
    1878                 :             : 
    1879                 :     3485718 :   if (live_vars)
    1880                 :             :     {
    1881                 :      207175 :       destroy_live_vars (live_vars_vec);
    1882                 :      414350 :       delete live_vars;
    1883                 :      207175 :       live_vars = NULL;
    1884                 :             :     }
    1885                 :             : 
    1886                 :     3485718 :   if (cfun->has_musttail)
    1887                 :             :     {
    1888                 :             :       /* We can't mix non-recursive must tail calls with tail recursive
    1889                 :             :          calls which require accumulators, because in that case we have to
    1890                 :             :          emit code in between the musttail calls and return, which prevent
    1891                 :             :          calling them as tail calls.  So, in that case give up on the
    1892                 :             :          tail recursion.  */
    1893                 :         977 :       for (act = tailcalls; act; act = act->next)
    1894                 :         658 :         if (!act->tail_recursion)
    1895                 :             :           {
    1896                 :         616 :             gcall *call = as_a <gcall *> (gsi_stmt (act->call_gsi));
    1897                 :         616 :             if (gimple_call_must_tail_p (call))
    1898                 :             :               break;
    1899                 :             :           }
    1900                 :         926 :       if (act)
    1901                 :        1660 :         for (struct tailcall **p = &tailcalls; *p; )
    1902                 :             :           {
    1903                 :        1053 :             if ((*p)->tail_recursion && ((*p)->add || (*p)->mult))
    1904                 :             :               {
    1905                 :           6 :                 struct tailcall *a = *p;
    1906                 :           6 :                 *p = (*p)->next;
    1907                 :           6 :                 gcall *call = as_a <gcall *> (gsi_stmt (a->call_gsi));
    1908                 :           6 :                 maybe_error_musttail (call, _("tail recursion with "
    1909                 :             :                                               "accumulation mixed with "
    1910                 :             :                                               "musttail non-recursive call"),
    1911                 :             :                                       diag_musttail);
    1912                 :           6 :                 free (a);
    1913                 :           6 :               }
    1914                 :             :             else
    1915                 :        1047 :               p = &(*p)->next;
    1916                 :             :           }
    1917                 :             :     }
    1918                 :             :   /* Construct the phi nodes and accumulators if necessary.  */
    1919                 :     3485718 :   a_acc = m_acc = NULL_TREE;
    1920                 :     4321336 :   for (act = tailcalls; act; act = act->next)
    1921                 :             :     {
    1922                 :      835618 :       if (!act->tail_recursion)
    1923                 :      833491 :         continue;
    1924                 :             : 
    1925                 :        2127 :       if (!phis_constructed)
    1926                 :             :         {
    1927                 :             :           /* Ensure that there is only one predecessor of the block
    1928                 :             :              or if there are existing degenerate PHI nodes.  */
    1929                 :        1204 :           if (!single_pred_p (first)
    1930                 :        1204 :               || !gimple_seq_empty_p (phi_nodes (first)))
    1931                 :           0 :             first
    1932                 :           0 :               = split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
    1933                 :             : 
    1934                 :             :           /* Copy the args if needed.  */
    1935                 :        1204 :           unsigned idx;
    1936                 :        1204 :           for (param = DECL_ARGUMENTS (current_function_decl), idx = 0;
    1937                 :        4244 :                param;
    1938                 :        3040 :                param = DECL_CHAIN (param), idx++)
    1939                 :        3040 :             if (bitmap_bit_p (tailr_arg_needs_copy, idx))
    1940                 :             :               {
    1941                 :        1824 :                 if (!is_gimple_reg_type (TREE_TYPE (param)))
    1942                 :         452 :                   continue;
    1943                 :        1372 :                 tree name = ssa_default_def (cfun, param);
    1944                 :        1372 :                 tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
    1945                 :        1372 :                 gphi *phi;
    1946                 :             : 
    1947                 :        1372 :                 set_ssa_default_def (cfun, param, new_name);
    1948                 :        1372 :                 phi = create_phi_node (name, first);
    1949                 :        1372 :                 add_phi_arg (phi, new_name, single_pred_edge (first),
    1950                 :        1372 :                              EXPR_LOCATION (param));
    1951                 :             :               }
    1952                 :             :           phis_constructed = true;
    1953                 :             :         }
    1954                 :        2127 :       tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
    1955                 :        2127 :       if (POINTER_TYPE_P (ret_type))
    1956                 :         141 :         ret_type = sizetype;
    1957                 :             : 
    1958                 :        2127 :       if (act->add && !a_acc)
    1959                 :          88 :         a_acc = create_tailcall_accumulator ("add_acc", first,
    1960                 :             :                                              build_zero_cst (ret_type));
    1961                 :             : 
    1962                 :        2127 :       if (act->mult && !m_acc)
    1963                 :         106 :         m_acc = create_tailcall_accumulator ("mult_acc", first,
    1964                 :             :                                              build_one_cst (ret_type));
    1965                 :             :     }
    1966                 :             : 
    1967                 :     3485718 :   if (a_acc || m_acc)
    1968                 :             :     {
    1969                 :             :       /* When the tail call elimination using accumulators is performed,
    1970                 :             :          statements adding the accumulated value are inserted at all exits.
    1971                 :             :          This turns all other tail calls to non-tail ones.  */
    1972                 :         176 :       opt_tailcalls = false;
    1973                 :             :     }
    1974                 :             : 
    1975                 :     3485718 :   class loop *new_loop = NULL;
    1976                 :     4321336 :   for (; tailcalls; tailcalls = next)
    1977                 :             :     {
    1978                 :      835618 :       next = tailcalls->next;
    1979                 :      835618 :       changed |= optimize_tail_call (tailcalls, opt_tailcalls, new_loop);
    1980                 :      835618 :       free (tailcalls);
    1981                 :             :     }
    1982                 :     3485718 :   if (new_loop)
    1983                 :        1204 :     add_loop (new_loop, loops_for_fn (cfun)->tree_root);
    1984                 :             : 
    1985                 :     3485718 :   if (a_acc || m_acc)
    1986                 :             :     {
    1987                 :             :       /* Modify the remaining return statements.  */
    1988                 :         324 :       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
    1989                 :             :         {
    1990                 :         444 :           if (safe_is_a <greturn *> (*gsi_last_bb (e->src)))
    1991                 :         148 :             adjust_return_value (e->src, m_acc, a_acc);
    1992                 :             :         }
    1993                 :             :     }
    1994                 :             : 
    1995                 :     3485718 :   if (changed)
    1996                 :        1210 :     free_dominance_info (CDI_DOMINATORS);
    1997                 :             : 
    1998                 :             :   /* Add phi nodes for the virtual operands defined in the function to the
    1999                 :             :      header of the loop created by tail recursion elimination.  Do so
    2000                 :             :      by triggering the SSA renamer.  */
    2001                 :     3485718 :   if (phis_constructed)
    2002                 :        1204 :     mark_virtual_operands_for_renaming (cfun);
    2003                 :             : 
    2004                 :     3485718 :   if (tailr_arg_needs_copy)
    2005                 :        1206 :     BITMAP_FREE (tailr_arg_needs_copy);
    2006                 :             : 
    2007                 :     3485718 :   if (diag_musttail)
    2008                 :      708327 :     cfun->has_musttail = false;
    2009                 :             : 
    2010                 :     3485718 :   if (changed)
    2011                 :        1210 :     return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
    2012                 :             :   return 0;
    2013                 :             : }
    2014                 :             : 
    2015                 :             : static bool
    2016                 :     4473707 : gate_tail_calls (void)
    2017                 :             : {
    2018                 :     4473707 :   return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call);
    2019                 :             : }
    2020                 :             : 
    2021                 :             : static unsigned int
    2022                 :      708107 : execute_tail_calls (void)
    2023                 :             : {
    2024                 :           0 :   return tree_optimize_tail_calls_1 (true, false, true);
    2025                 :             : }
    2026                 :             : 
    2027                 :             : namespace {
    2028                 :             : 
    2029                 :             : const pass_data pass_data_tail_recursion =
    2030                 :             : {
    2031                 :             :   GIMPLE_PASS, /* type */
    2032                 :             :   "tailr", /* name */
    2033                 :             :   OPTGROUP_NONE, /* optinfo_flags */
    2034                 :             :   TV_NONE, /* tv_id */
    2035                 :             :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    2036                 :             :   0, /* properties_provided */
    2037                 :             :   0, /* properties_destroyed */
    2038                 :             :   0, /* todo_flags_start */
    2039                 :             :   0, /* todo_flags_finish */
    2040                 :             : };
    2041                 :             : 
    2042                 :             : class pass_tail_recursion : public gimple_opt_pass
    2043                 :             : {
    2044                 :             : public:
    2045                 :      573364 :   pass_tail_recursion (gcc::context *ctxt)
    2046                 :     1146728 :     : gimple_opt_pass (pass_data_tail_recursion, ctxt)
    2047                 :             :   {}
    2048                 :             : 
    2049                 :             :   /* opt_pass methods: */
    2050                 :      286682 :   opt_pass * clone () final override
    2051                 :             :   {
    2052                 :      286682 :     return new pass_tail_recursion (m_ctxt);
    2053                 :             :   }
    2054                 :     3452401 :   bool gate (function *) final override { return gate_tail_calls (); }
    2055                 :     2777391 :   unsigned int execute (function *) final override
    2056                 :             :     {
    2057                 :     2777391 :       return tree_optimize_tail_calls_1 (false, false, false);
    2058                 :             :     }
    2059                 :             : 
    2060                 :             : }; // class pass_tail_recursion
    2061                 :             : 
    2062                 :             : } // anon namespace
    2063                 :             : 
    2064                 :             : gimple_opt_pass *
    2065                 :      286682 : make_pass_tail_recursion (gcc::context *ctxt)
    2066                 :             : {
    2067                 :      286682 :   return new pass_tail_recursion (ctxt);
    2068                 :             : }
    2069                 :             : 
    2070                 :             : namespace {
    2071                 :             : 
    2072                 :             : const pass_data pass_data_tail_calls =
    2073                 :             : {
    2074                 :             :   GIMPLE_PASS, /* type */
    2075                 :             :   "tailc", /* name */
    2076                 :             :   OPTGROUP_NONE, /* optinfo_flags */
    2077                 :             :   TV_NONE, /* tv_id */
    2078                 :             :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    2079                 :             :   0, /* properties_provided */
    2080                 :             :   0, /* properties_destroyed */
    2081                 :             :   0, /* todo_flags_start */
    2082                 :             :   0, /* todo_flags_finish */
    2083                 :             : };
    2084                 :             : 
    2085                 :             : class pass_tail_calls : public gimple_opt_pass
    2086                 :             : {
    2087                 :             : public:
    2088                 :      286682 :   pass_tail_calls (gcc::context *ctxt)
    2089                 :      573364 :     : gimple_opt_pass (pass_data_tail_calls, ctxt)
    2090                 :             :   {}
    2091                 :             : 
    2092                 :             :   /* opt_pass methods: */
    2093                 :     1021306 :   bool gate (function *) final override { return gate_tail_calls (); }
    2094                 :      708107 :   unsigned int execute (function *) final override
    2095                 :             :   {
    2096                 :      708107 :     return execute_tail_calls ();
    2097                 :             :   }
    2098                 :             : 
    2099                 :             : }; // class pass_tail_calls
    2100                 :             : 
    2101                 :             : } // anon namespace
    2102                 :             : 
    2103                 :             : gimple_opt_pass *
    2104                 :      286682 : make_pass_tail_calls (gcc::context *ctxt)
    2105                 :             : {
    2106                 :      286682 :   return new pass_tail_calls (ctxt);
    2107                 :             : }
    2108                 :             : 
    2109                 :             : namespace {
    2110                 :             : 
    2111                 :             : const pass_data pass_data_musttail =
    2112                 :             : {
    2113                 :             :   GIMPLE_PASS, /* type */
    2114                 :             :   "musttail", /* name */
    2115                 :             :   OPTGROUP_NONE, /* optinfo_flags */
    2116                 :             :   TV_NONE, /* tv_id */
    2117                 :             :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    2118                 :             :   0, /* properties_provided */
    2119                 :             :   0, /* properties_destroyed */
    2120                 :             :   0, /* todo_flags_start */
    2121                 :             :   0, /* todo_flags_finish */
    2122                 :             : };
    2123                 :             : 
    2124                 :             : class pass_musttail : public gimple_opt_pass
    2125                 :             : {
    2126                 :             : public:
    2127                 :      286682 :   pass_musttail (gcc::context *ctxt)
    2128                 :      573364 :     : gimple_opt_pass (pass_data_musttail, ctxt)
    2129                 :             :   {}
    2130                 :             : 
    2131                 :             :   /* opt_pass methods: */
    2132                 :             :   /* This pass is only used when the other tail call pass
    2133                 :             :      doesn't run to make [[musttail]] still work.  But only
    2134                 :             :      run it when there is actually a musttail in the function.  */
    2135                 :     1456109 :   bool gate (function *f) final override
    2136                 :             :   {
    2137                 :     1456109 :     return f->has_musttail;
    2138                 :             :   }
    2139                 :         220 :   unsigned int execute (function *) final override
    2140                 :             :   {
    2141                 :         220 :     return tree_optimize_tail_calls_1 (true, true, true);
    2142                 :             :   }
    2143                 :             : 
    2144                 :             : }; // class pass_musttail
    2145                 :             : 
    2146                 :             : } // anon namespace
    2147                 :             : 
    2148                 :             : gimple_opt_pass *
    2149                 :      286682 : make_pass_musttail (gcc::context *ctxt)
    2150                 :             : {
    2151                 :      286682 :   return new pass_musttail (ctxt);
    2152                 :             : }
        

Generated by: LCOV version 2.1-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.