gcc/tree-tailcall.c

   1 /* Tail call optimization on trees.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "tm_p.h"
  27 #include "basic-block.h"
  28 #include "function.h"
  29 #include "tree-flow.h"
  30 #include "tree-dump.h"
  31 #include "gimple-pretty-print.h"
  32 #include "except.h"
  33 #include "tree-pass.h"
  34 #include "flags.h"
  35 #include "langhooks.h"
  36 #include "dbgcnt.h"
  37
  38 /* The file implements the tail recursion elimination.  It is also used to
  39    analyze the tail calls in general, passing the results to the rtl level
  40    where they are used for sibcall optimization.
  41
  42    In addition to the standard tail recursion elimination, we handle the most
  43    trivial cases of making the call tail recursive by creating accumulators.
  44    For example the following function
  45
  46    int sum (int n)
  47    {
  48      if (n > 0)
  49        return n + sum (n - 1);
  50      else
  51        return 0;
  52    }
  53
  54    is transformed into
  55
  56    int sum (int n)
  57    {
  58      int acc = 0;
  59
  60      while (n > 0)
  61        acc += n--;
  62
  63      return acc;
  64    }
  65
  66    To do this, we maintain two accumulators (a_acc and m_acc) that indicate
  67    when we reach the return x statement, we should return a_acc + x * m_acc
  68    instead.  They are initially initialized to 0 and 1, respectively,
  69    so the semantics of the function is obviously preserved.  If we are
  70    guaranteed that the value of the accumulator never change, we
  71    omit the accumulator.
  72
  73    There are three cases how the function may exit.  The first one is
  74    handled in adjust_return_value, the other two in adjust_accumulator_values
  75    (the second case is actually a special case of the third one and we
  76    present it separately just for clarity):
  77
  78    1) Just return x, where x is not in any of the remaining special shapes.
  79       We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
  80
  81    2) return f (...), where f is the current function, is rewritten in a
  82       classical tail-recursion elimination way, into assignment of arguments
  83       and jump to the start of the function.  Values of the accumulators
  84       are unchanged.
  85
  86    3) return a + m * f(...), where a and m do not depend on call to f.
  87       To preserve the semantics described before we want this to be rewritten
  88       in such a way that we finally return
  89
  90       a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
  91
  92       I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
  93       eliminate the tail call to f.  Special cases when the value is just
  94       added or just multiplied are obtained by setting a = 0 or m = 1.
  95
  96    TODO -- it is possible to do similar tricks for other operations.  */
  97
  98 /* A structure that describes the tailcall.  */
  99
 100 struct tailcall
 101 {
 102   /* The iterator pointing to the call statement.  */
 103   gimple_stmt_iterator call_gsi;
 104
 105   /* True if it is a call to the current function.  */
 106   bool tail_recursion;
 107
 108   /* The return value of the caller is mult * f + add, where f is the return
 109      value of the call.  */
 110   tree mult, add;
 111
 112   /* Next tailcall in the chain.  */
 113   struct tailcall *next;
 114 };
 115
 116 /* The variables holding the value of multiplicative and additive
 117    accumulator.  */
 118 static tree m_acc, a_acc;
 119
 120 static bool suitable_for_tail_opt_p (void);
 121 static bool optimize_tail_call (struct tailcall *, bool);
 122 static void eliminate_tail_call (struct tailcall *);
 123 static void find_tail_calls (basic_block, struct tailcall **);
 124
 125 /* Returns false when the function is not suitable for tail call optimization
 126    from some reason (e.g. if it takes variable number of arguments).  */
 127
 128 static bool
 129 suitable_for_tail_opt_p (void)
 130 {
 131   if (cfun->stdarg)
 132     return false;
 133
 134   return true;
 135 }
 136 /* Returns false when the function is not suitable for tail call optimization
 137    from some reason (e.g. if it takes variable number of arguments).
 138    This test must pass in addition to suitable_for_tail_opt_p in order to make
 139    tail call discovery happen.  */
 140
 141 static bool
 142 suitable_for_tail_call_opt_p (void)
 143 {
 144   tree param;
 145
 146   /* alloca (until we have stack slot life analysis) inhibits
 147      sibling call optimizations, but not tail recursion.  */
 148   if (cfun->calls_alloca)
 149     return false;
 150
 151   /* If we are using sjlj exceptions, we may need to add a call to
 152      _Unwind_SjLj_Unregister at exit of the function.  Which means
 153      that we cannot do any sibcall transformations.  */
 154   if (USING_SJLJ_EXCEPTIONS && current_function_has_exception_handlers ())
 155     return false;
 156
 157   /* Any function that calls setjmp might have longjmp called from
 158      any called function.  ??? We really should represent this
 159      properly in the CFG so that this needn't be special cased.  */
 160   if (cfun->calls_setjmp)
 161     return false;
 162
 163   /* ??? It is OK if the argument of a function is taken in some cases,
 164      but not in all cases.  See PR15387 and PR19616.  Revisit for 4.1.  */
 165   for (param = DECL_ARGUMENTS (current_function_decl);
 166        param;
 167        param = TREE_CHAIN (param))
 168     if (TREE_ADDRESSABLE (param))
 169       return false;
 170
 171   return true;
 172 }
 173
 174 /* Checks whether the expression EXPR in stmt AT is independent of the
 175    statement pointed to by GSI (in a sense that we already know EXPR's value
 176    at GSI).  We use the fact that we are only called from the chain of
 177    basic blocks that have only single successor.  Returns the expression
 178    containing the value of EXPR at GSI.  */
 179
 180 static tree
 181 independent_of_stmt_p (tree expr, gimple at, gimple_stmt_iterator gsi)
 182 {
 183   basic_block bb, call_bb, at_bb;
 184   edge e;
 185   edge_iterator ei;
 186
 187   if (is_gimple_min_invariant (expr))
 188     return expr;
 189
 190   if (TREE_CODE (expr) != SSA_NAME)
 191     return NULL_TREE;
 192
 193   /* Mark the blocks in the chain leading to the end.  */
 194   at_bb = gimple_bb (at);
 195   call_bb = gimple_bb (gsi_stmt (gsi));
 196   for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
 197     bb->aux = &bb->aux;
 198   bb->aux = &bb->aux;
 199
 200   while (1)
 201     {
 202       at = SSA_NAME_DEF_STMT (expr);
 203       bb = gimple_bb (at);
 204
 205       /* The default definition or defined before the chain.  */
 206       if (!bb || !bb->aux)
 207         break;
 208
 209       if (bb == call_bb)
 210         {
 211           for (; !gsi_end_p (gsi); gsi_next (&gsi))
 212             if (gsi_stmt (gsi) == at)
 213               break;
 214
 215           if (!gsi_end_p (gsi))
 216             expr = NULL_TREE;
 217           break;
 218         }
 219
 220       if (gimple_code (at) != GIMPLE_PHI)
 221         {
 222           expr = NULL_TREE;
 223           break;
 224         }
 225
 226       FOR_EACH_EDGE (e, ei, bb->preds)
 227         if (e->src->aux)
 228           break;
 229       gcc_assert (e);
 230
 231       expr = PHI_ARG_DEF_FROM_EDGE (at, e);
 232       if (TREE_CODE (expr) != SSA_NAME)
 233         {
 234           /* The value is a constant.  */
 235           break;
 236         }
 237     }
 238
 239   /* Unmark the blocks.  */
 240   for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
 241     bb->aux = NULL;
 242   bb->aux = NULL;
 243
 244   return expr;
 245 }
 246
 247 /* Simulates the effect of an assignment STMT on the return value of the tail
 248    recursive CALL passed in ASS_VAR.  M and A are the multiplicative and the
 249    additive factor for the real return value.  */
 250
 251 static bool
 252 process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
 253                     tree *a, tree *ass_var)
 254 {
 255   tree op0, op1, non_ass_var;
 256   tree dest = gimple_assign_lhs (stmt);
 257   enum tree_code code = gimple_assign_rhs_code (stmt);
 258   enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
 259   tree src_var = gimple_assign_rhs1 (stmt);
 260
 261   /* See if this is a simple copy operation of an SSA name to the function
 262      result.  In that case we may have a simple tail call.  Ignore type
 263      conversions that can never produce extra code between the function
 264      call and the function return.  */
 265   if ((rhs_class == GIMPLE_SINGLE_RHS || gimple_assign_cast_p (stmt))
 266       && (TREE_CODE (src_var) == SSA_NAME))
 267     {
 268       /* Reject a tailcall if the type conversion might need
 269          additional code.  */
 270       if (gimple_assign_cast_p (stmt)
 271           && TYPE_MODE (TREE_TYPE (dest)) != TYPE_MODE (TREE_TYPE (src_var)))
 272         return false;
 273
 274       if (src_var != *ass_var)
 275         return false;
 276
 277       *ass_var = dest;
 278       return true;
 279     }
 280
 281   if (rhs_class != GIMPLE_BINARY_RHS)
 282     return false;
 283
 284   /* Accumulator optimizations will reverse the order of operations.
 285      We can only do that for floating-point types if we're assuming
 286      that addition and multiplication are associative.  */
 287   if (!flag_associative_math)
 288     if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
 289       return false;
 290
 291   /* We only handle the code like
 292
 293      x = call ();
 294      y = m * x;
 295      z = y + a;
 296      return z;
 297
 298      TODO -- Extend it for cases where the linear transformation of the output
 299      is expressed in a more complicated way.  */
 300
 301   op0 = gimple_assign_rhs1 (stmt);
 302   op1 = gimple_assign_rhs2 (stmt);
 303
 304   if (op0 == *ass_var
 305       && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
 306     ;
 307   else if (op1 == *ass_var
 308            && (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
 309     ;
 310   else
 311     return false;
 312
 313   switch (code)
 314     {
 315     case PLUS_EXPR:
 316       *a = non_ass_var;
 317       *ass_var = dest;
 318       return true;
 319
 320     case MULT_EXPR:
 321       *m = non_ass_var;
 322       *ass_var = dest;
 323       return true;
 324
 325       /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR,
 326          POINTER_PLUS_EXPR).  */
 327
 328     default:
 329       return false;
 330     }
 331 }
 332
 333 /* Propagate VAR through phis on edge E.  */
 334
 335 static tree
 336 propagate_through_phis (tree var, edge e)
 337 {
 338   basic_block dest = e->dest;
 339   gimple_stmt_iterator gsi;
 340
 341   for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
 342     {
 343       gimple phi = gsi_stmt (gsi);
 344       if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
 345         return PHI_RESULT (phi);
 346     }
 347   return var;
 348 }
 349
 350 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
 351    added to the start of RET.  */
 352
 353 static void
 354 find_tail_calls (basic_block bb, struct tailcall **ret)
 355 {
 356   tree ass_var = NULL_TREE, ret_var, func, param;
 357   gimple stmt, call = NULL;
 358   gimple_stmt_iterator gsi, agsi;
 359   bool tail_recursion;
 360   struct tailcall *nw;
 361   edge e;
 362   tree m, a;
 363   basic_block abb;
 364   size_t idx;
 365   tree var;
 366   referenced_var_iterator rvi;
 367
 368   if (!single_succ_p (bb))
 369     return;
 370
 371   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
 372     {
 373       stmt = gsi_stmt (gsi);
 374
 375       /* Ignore labels.  */
 376       if (gimple_code (stmt) == GIMPLE_LABEL || is_gimple_debug (stmt))
 377         continue;
 378
 379       /* Check for a call.  */
 380       if (is_gimple_call (stmt))
 381         {
 382           call = stmt;
 383           ass_var = gimple_call_lhs (stmt);
 384           break;
 385         }
 386
 387       /* If the statement references memory or volatile operands, fail.  */
 388       if (gimple_references_memory_p (stmt)
 389           || gimple_has_volatile_ops (stmt))
 390         return;
 391     }
 392
 393   if (gsi_end_p (gsi))
 394     {
 395       edge_iterator ei;
 396       /* Recurse to the predecessors.  */
 397       FOR_EACH_EDGE (e, ei, bb->preds)
 398         find_tail_calls (e->src, ret);
 399
 400       return;
 401     }
 402
 403   /* If the LHS of our call is not just a simple register, we can't
 404      transform this into a tail or sibling call.  This situation happens,
 405      in (e.g.) "*p = foo()" where foo returns a struct.  In this case
 406      we won't have a temporary here, but we need to carry out the side
 407      effect anyway, so tailcall is impossible.
 408
 409      ??? In some situations (when the struct is returned in memory via
 410      invisible argument) we could deal with this, e.g. by passing 'p'
 411      itself as that argument to foo, but it's too early to do this here,
 412      and expand_call() will not handle it anyway.  If it ever can, then
 413      we need to revisit this here, to allow that situation.  */
 414   if (ass_var && !is_gimple_reg (ass_var))
 415     return;
 416
 417   /* We found the call, check whether it is suitable.  */
 418   tail_recursion = false;
 419   func = gimple_call_fndecl (call);
 420   if (func == current_function_decl)
 421     {
 422       tree arg;
 423
 424       for (param = DECL_ARGUMENTS (func), idx = 0;
 425            param && idx < gimple_call_num_args (call);
 426            param = TREE_CHAIN (param), idx ++)
 427         {
 428           arg = gimple_call_arg (call, idx);
 429           if (param != arg)
 430             {
 431               /* Make sure there are no problems with copying.  The parameter
 432                  have a copyable type and the two arguments must have reasonably
 433                  equivalent types.  The latter requirement could be relaxed if
 434                  we emitted a suitable type conversion statement.  */
 435               if (!is_gimple_reg_type (TREE_TYPE (param))
 436                   || !useless_type_conversion_p (TREE_TYPE (param),
 437                                                  TREE_TYPE (arg)))
 438                 break;
 439
 440               /* The parameter should be a real operand, so that phi node
 441                  created for it at the start of the function has the meaning
 442                  of copying the value.  This test implies is_gimple_reg_type
 443                  from the previous condition, however this one could be
 444                  relaxed by being more careful with copying the new value
 445                  of the parameter (emitting appropriate GIMPLE_ASSIGN and
 446                  updating the virtual operands).  */
 447               if (!is_gimple_reg (param))
 448                 break;
 449             }
 450         }
 451       if (idx == gimple_call_num_args (call) && !param)
 452         tail_recursion = true;
 453     }
 454
 455   /* Make sure the tail invocation of this function does not refer
 456      to local variables.  */
 457   FOR_EACH_REFERENCED_VAR (var, rvi)
 458     {
 459       if (TREE_CODE (var) != PARM_DECL
 460           && auto_var_in_fn_p (var, cfun->decl)
 461           && (ref_maybe_used_by_stmt_p (call, var)
 462               || call_may_clobber_ref_p (call, var)))
 463         return;
 464     }
 465
 466   /* Now check the statements after the call.  None of them has virtual
 467      operands, so they may only depend on the call through its return
 468      value.  The return value should also be dependent on each of them,
 469      since we are running after dce.  */
 470   m = NULL_TREE;
 471   a = NULL_TREE;
 472
 473   abb = bb;
 474   agsi = gsi;
 475   while (1)
 476     {
 477       tree tmp_a = NULL_TREE;
 478       tree tmp_m = NULL_TREE;
 479       gsi_next (&agsi);
 480
 481       while (gsi_end_p (agsi))
 482         {
 483           ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
 484           abb = single_succ (abb);
 485           agsi = gsi_start_bb (abb);
 486         }
 487
 488       stmt = gsi_stmt (agsi);
 489
 490       if (gimple_code (stmt) == GIMPLE_LABEL)
 491         continue;
 492
 493       if (gimple_code (stmt) == GIMPLE_RETURN)
 494         break;
 495
 496       if (is_gimple_debug (stmt))
 497         continue;
 498
 499       if (gimple_code (stmt) != GIMPLE_ASSIGN)
 500         return;
 501
 502       /* This is a gimple assign. */
 503       if (! process_assignment (stmt, gsi, &tmp_m, &tmp_a, &ass_var))
 504         return;
 505
 506       if (tmp_a)
 507         {
 508           if (a)
 509             a = fold_build2 (PLUS_EXPR, TREE_TYPE (tmp_a), a, tmp_a);
 510           else
 511             a = tmp_a;
 512         }
 513       if (tmp_m)
 514         {
 515           if (m)
 516             m = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), m, tmp_m);
 517           else
 518             m = tmp_m;
 519
 520           if (a)
 521             a = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), a, tmp_m);
 522         }
 523     }
 524
 525   /* See if this is a tail call we can handle.  */
 526   ret_var = gimple_return_retval (stmt);
 527
 528   /* We may proceed if there either is no return value, or the return value
 529      is identical to the call's return.  */
 530   if (ret_var
 531       && (ret_var != ass_var))
 532     return;
 533
 534   /* If this is not a tail recursive call, we cannot handle addends or
 535      multiplicands.  */
 536   if (!tail_recursion && (m || a))
 537     return;
 538
 539   nw = XNEW (struct tailcall);
 540
 541   nw->call_gsi = gsi;
 542
 543   nw->tail_recursion = tail_recursion;
 544
 545   nw->mult = m;
 546   nw->add = a;
 547
 548   nw->next = *ret;
 549   *ret = nw;
 550 }
 551
 552 /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E.  */
 553
 554 static void
 555 add_successor_phi_arg (edge e, tree var, tree phi_arg)
 556 {
 557   gimple_stmt_iterator gsi;
 558
 559   for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
 560     if (PHI_RESULT (gsi_stmt (gsi)) == var)
 561       break;
 562
 563   gcc_assert (!gsi_end_p (gsi));
 564   add_phi_arg (gsi_stmt (gsi), phi_arg, e, UNKNOWN_LOCATION);
 565 }
 566
 567 /* Creates a GIMPLE statement which computes the operation specified by
 568    CODE, OP0 and OP1 to a new variable with name LABEL and inserts the
 569    statement in the position specified by GSI and UPDATE.  Returns the
 570    tree node of the statement's result.  */
 571
 572 static tree
 573 adjust_return_value_with_ops (enum tree_code code, const char *label,
 574                               tree acc, tree op1, gimple_stmt_iterator gsi)
 575 {
 576
 577   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 578   tree tmp = create_tmp_reg (ret_type, label);
 579   gimple stmt;
 580   tree result;
 581
 582   add_referenced_var (tmp);
 583
 584   if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
 585     stmt = gimple_build_assign_with_ops (code, tmp, acc, op1);
 586   else
 587     {
 588       tree rhs = fold_convert (TREE_TYPE (acc),
 589                                fold_build2 (code,
 590                                             TREE_TYPE (op1),
 591                                             fold_convert (TREE_TYPE (op1), acc),
 592                                             op1));
 593       rhs = force_gimple_operand_gsi (&gsi, rhs,
 594                                       false, NULL, true, GSI_CONTINUE_LINKING);
 595       stmt = gimple_build_assign (NULL_TREE, rhs);
 596     }
 597
 598   result = make_ssa_name (tmp, stmt);
 599   gimple_assign_set_lhs (stmt, result);
 600   update_stmt (stmt);
 601   gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
 602   return result;
 603 }
 604
 605 /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
 606    the computation specified by CODE and OP1 and insert the statement
 607    at the position specified by GSI as a new statement.  Returns new SSA name
 608    of updated accumulator.  */
 609
 610 static tree
 611 update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
 612                              gimple_stmt_iterator gsi)
 613 {
 614   gimple stmt;
 615   tree var;
 616   if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
 617     stmt = gimple_build_assign_with_ops (code, SSA_NAME_VAR (acc), acc, op1);
 618   else
 619     {
 620       tree rhs = fold_convert (TREE_TYPE (acc),
 621                                fold_build2 (code,
 622                                             TREE_TYPE (op1),
 623                                             fold_convert (TREE_TYPE (op1), acc),
 624                                             op1));
 625       rhs = force_gimple_operand_gsi (&gsi, rhs,
 626                                       false, NULL, false, GSI_CONTINUE_LINKING);
 627       stmt = gimple_build_assign (NULL_TREE, rhs);
 628     }
 629   var = make_ssa_name (SSA_NAME_VAR (acc), stmt);
 630   gimple_assign_set_lhs (stmt, var);
 631   update_stmt (stmt);
 632   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
 633   return var;
 634 }
 635
 636 /* Adjust the accumulator values according to A and M after GSI, and update
 637    the phi nodes on edge BACK.  */
 638
 639 static void
 640 adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
 641 {
 642   tree var, a_acc_arg, m_acc_arg;
 643
 644   if (m)
 645     m = force_gimple_operand_gsi (&gsi, m, true, NULL, true, GSI_SAME_STMT);
 646   if (a)
 647     a = force_gimple_operand_gsi (&gsi, a, true, NULL, true, GSI_SAME_STMT);
 648
 649   a_acc_arg = a_acc;
 650   m_acc_arg = m_acc;
 651   if (a)
 652     {
 653       if (m_acc)
 654         {
 655           if (integer_onep (a))
 656             var = m_acc;
 657           else
 658             var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc,
 659                                                 a, gsi);
 660         }
 661       else
 662         var = a;
 663
 664       a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi);
 665     }
 666
 667   if (m)
 668     m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi);
 669
 670   if (a_acc)
 671     add_successor_phi_arg (back, a_acc, a_acc_arg);
 672
 673   if (m_acc)
 674     add_successor_phi_arg (back, m_acc, m_acc_arg);
 675 }
 676
 677 /* Adjust value of the return at the end of BB according to M and A
 678    accumulators.  */
 679
 680 static void
 681 adjust_return_value (basic_block bb, tree m, tree a)
 682 {
 683   tree retval;
 684   gimple ret_stmt = gimple_seq_last_stmt (bb_seq (bb));
 685   gimple_stmt_iterator gsi = gsi_last_bb (bb);
 686
 687   gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN);
 688
 689   retval = gimple_return_retval (ret_stmt);
 690   if (!retval || retval == error_mark_node)
 691     return;
 692
 693   if (m)
 694     retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval,
 695                                            gsi);
 696   if (a)
 697     retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval,
 698                                            gsi);
 699   gimple_return_set_retval (ret_stmt, retval);
 700   update_stmt (ret_stmt);
 701 }
 702
 703 /* Subtract COUNT and FREQUENCY from the basic block and it's
 704    outgoing edge.  */
 705 static void
 706 decrease_profile (basic_block bb, gcov_type count, int frequency)
 707 {
 708   edge e;
 709   bb->count -= count;
 710   if (bb->count < 0)
 711     bb->count = 0;
 712   bb->frequency -= frequency;
 713   if (bb->frequency < 0)
 714     bb->frequency = 0;
 715   if (!single_succ_p (bb))
 716     {
 717       gcc_assert (!EDGE_COUNT (bb->succs));
 718       return;
 719     }
 720   e = single_succ_edge (bb);
 721   e->count -= count;
 722   if (e->count < 0)
 723     e->count = 0;
 724 }
 725
 726 /* Returns true if argument PARAM of the tail recursive call needs to be copied
 727    when the call is eliminated.  */
 728
 729 static bool
 730 arg_needs_copy_p (tree param)
 731 {
 732   tree def;
 733
 734   if (!is_gimple_reg (param) || !var_ann (param))
 735     return false;
 736
 737   /* Parameters that are only defined but never used need not be copied.  */
 738   def = gimple_default_def (cfun, param);
 739   if (!def)
 740     return false;
 741
 742   return true;
 743 }
 744
 745 /* Eliminates tail call described by T.  TMP_VARS is a list of
 746    temporary variables used to copy the function arguments.  */
 747
 748 static void
 749 eliminate_tail_call (struct tailcall *t)
 750 {
 751   tree param, rslt;
 752   gimple stmt, call;
 753   tree arg;
 754   size_t idx;
 755   basic_block bb, first;
 756   edge e;
 757   gimple phi;
 758   gimple_stmt_iterator gsi;
 759   gimple orig_stmt;
 760
 761   stmt = orig_stmt = gsi_stmt (t->call_gsi);
 762   bb = gsi_bb (t->call_gsi);
 763
 764   if (dump_file && (dump_flags & TDF_DETAILS))
 765     {
 766       fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
 767                bb->index);
 768       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 769       fprintf (dump_file, "\n");
 770     }
 771
 772   gcc_assert (is_gimple_call (stmt));
 773
 774   first = single_succ (ENTRY_BLOCK_PTR);
 775
 776   /* Remove the code after call_gsi that will become unreachable.  The
 777      possibly unreachable code in other blocks is removed later in
 778      cfg cleanup.  */
 779   gsi = t->call_gsi;
 780   gsi_next (&gsi);
 781   while (!gsi_end_p (gsi))
 782     {
 783       gimple t = gsi_stmt (gsi);
 784       /* Do not remove the return statement, so that redirect_edge_and_branch
 785          sees how the block ends.  */
 786       if (gimple_code (t) == GIMPLE_RETURN)
 787         break;
 788
 789       gsi_remove (&gsi, true);
 790       release_defs (t);
 791     }
 792
 793   /* Number of executions of function has reduced by the tailcall.  */
 794   e = single_succ_edge (gsi_bb (t->call_gsi));
 795   decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
 796   decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
 797   if (e->dest != EXIT_BLOCK_PTR)
 798     decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
 799
 800   /* Replace the call by a jump to the start of function.  */
 801   e = redirect_edge_and_branch (single_succ_edge (gsi_bb (t->call_gsi)),
 802                                 first);
 803   gcc_assert (e);
 804   PENDING_STMT (e) = NULL;
 805
 806   /* Add phi node entries for arguments.  The ordering of the phi nodes should
 807      be the same as the ordering of the arguments.  */
 808   for (param = DECL_ARGUMENTS (current_function_decl),
 809          idx = 0, gsi = gsi_start_phis (first);
 810        param;
 811        param = TREE_CHAIN (param), idx++)
 812     {
 813       if (!arg_needs_copy_p (param))
 814         continue;
 815
 816       arg = gimple_call_arg (stmt, idx);
 817       phi = gsi_stmt (gsi);
 818       gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
 819
 820       add_phi_arg (phi, arg, e, gimple_location (stmt));
 821       gsi_next (&gsi);
 822     }
 823
 824   /* Update the values of accumulators.  */
 825   adjust_accumulator_values (t->call_gsi, t->mult, t->add, e);
 826
 827   call = gsi_stmt (t->call_gsi);
 828   rslt = gimple_call_lhs (call);
 829   if (rslt != NULL_TREE)
 830     {
 831       /* Result of the call will no longer be defined.  So adjust the
 832          SSA_NAME_DEF_STMT accordingly.  */
 833       SSA_NAME_DEF_STMT (rslt) = gimple_build_nop ();
 834     }
 835
 836   gsi_remove (&t->call_gsi, true);
 837   release_defs (call);
 838 }
 839
 840 /* Add phi nodes for the virtual operands defined in the function to the
 841    header of the loop created by tail recursion elimination.
 842
 843    Originally, we used to add phi nodes only for call clobbered variables,
 844    as the value of the non-call clobbered ones obviously cannot be used
 845    or changed within the recursive call.  However, the local variables
 846    from multiple calls now share the same location, so the virtual ssa form
 847    requires us to say that the location dies on further iterations of the loop,
 848    which requires adding phi nodes.
 849 */
 850 static void
 851 add_virtual_phis (void)
 852 {
 853   referenced_var_iterator rvi;
 854   tree var;
 855
 856   /* The problematic part is that there is no way how to know what
 857      to put into phi nodes (there in fact does not have to be such
 858      ssa name available).  A solution would be to have an artificial
 859      use/kill for all virtual operands in EXIT node.  Unless we have
 860      this, we cannot do much better than to rebuild the ssa form for
 861      possibly affected virtual ssa names from scratch.  */
 862
 863   FOR_EACH_REFERENCED_VAR (var, rvi)
 864     {
 865       if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE)
 866         mark_sym_for_renaming (var);
 867     }
 868 }
 869
 870 /* Optimizes the tailcall described by T.  If OPT_TAILCALLS is true, also
 871    mark the tailcalls for the sibcall optimization.  */
 872
 873 static bool
 874 optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
 875 {
 876   if (t->tail_recursion)
 877     {
 878       eliminate_tail_call (t);
 879       return true;
 880     }
 881
 882   if (opt_tailcalls)
 883     {
 884       gimple stmt = gsi_stmt (t->call_gsi);
 885
 886       gimple_call_set_tail (stmt, true);
 887       if (dump_file && (dump_flags & TDF_DETAILS))
 888         {
 889           fprintf (dump_file, "Found tail call ");
 890           print_gimple_stmt (dump_file, stmt, 0, dump_flags);
 891           fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index);
 892         }
 893     }
 894
 895   return false;
 896 }
 897
 898 /* Creates a tail-call accumulator of the same type as the return type of the
 899    current function.  LABEL is the name used to creating the temporary
 900    variable for the accumulator.  The accumulator will be inserted in the
 901    phis of a basic block BB with single predecessor with an initial value
 902    INIT converted to the current function return type.  */
 903
 904 static tree
 905 create_tailcall_accumulator (const char *label, basic_block bb, tree init)
 906 {
 907   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 908   tree tmp = create_tmp_reg (ret_type, label);
 909   gimple phi;
 910
 911   add_referenced_var (tmp);
 912   phi = create_phi_node (tmp, bb);
 913   /* RET_TYPE can be a float when -ffast-maths is enabled.  */
 914   add_phi_arg (phi, fold_convert (ret_type, init), single_pred_edge (bb),
 915                UNKNOWN_LOCATION);
 916   return PHI_RESULT (phi);
 917 }
 918
 919 /* Optimizes tail calls in the function, turning the tail recursion
 920    into iteration.  */
 921
 922 static unsigned int
 923 tree_optimize_tail_calls_1 (bool opt_tailcalls)
 924 {
 925   edge e;
 926   bool phis_constructed = false;
 927   struct tailcall *tailcalls = NULL, *act, *next;
 928   bool changed = false;
 929   basic_block first = single_succ (ENTRY_BLOCK_PTR);
 930   tree param;
 931   gimple stmt;
 932   edge_iterator ei;
 933
 934   if (!suitable_for_tail_opt_p ())
 935     return 0;
 936   if (opt_tailcalls)
 937     opt_tailcalls = suitable_for_tail_call_opt_p ();
 938
 939   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 940     {
 941       /* Only traverse the normal exits, i.e. those that end with return
 942          statement.  */
 943       stmt = last_stmt (e->src);
 944
 945       if (stmt
 946           && gimple_code (stmt) == GIMPLE_RETURN)
 947         find_tail_calls (e->src, &tailcalls);
 948     }
 949
 950   /* Construct the phi nodes and accumulators if necessary.  */
 951   a_acc = m_acc = NULL_TREE;
 952   for (act = tailcalls; act; act = act->next)
 953     {
 954       if (!act->tail_recursion)
 955         continue;
 956
 957       if (!phis_constructed)
 958         {
 959           /* Ensure that there is only one predecessor of the block
 960              or if there are existing degenerate PHI nodes.  */
 961           if (!single_pred_p (first)
 962               || !gimple_seq_empty_p (phi_nodes (first)))
 963             first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
 964
 965           /* Copy the args if needed.  */
 966           for (param = DECL_ARGUMENTS (current_function_decl);
 967                param;
 968                param = TREE_CHAIN (param))
 969             if (arg_needs_copy_p (param))
 970               {
 971                 tree name = gimple_default_def (cfun, param);
 972                 tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
 973                 gimple phi;
 974
 975                 set_default_def (param, new_name);
 976                 phi = create_phi_node (name, first);
 977                 SSA_NAME_DEF_STMT (name) = phi;
 978                 add_phi_arg (phi, new_name, single_pred_edge (first),
 979                              EXPR_LOCATION (param));
 980               }
 981           phis_constructed = true;
 982         }
 983
 984       if (act->add && !a_acc)
 985         a_acc = create_tailcall_accumulator ("add_acc", first,
 986                                              integer_zero_node);
 987
 988       if (act->mult && !m_acc)
 989         m_acc = create_tailcall_accumulator ("mult_acc", first,
 990                                              integer_one_node);
 991     }
 992
 993   for (; tailcalls; tailcalls = next)
 994     {
 995       next = tailcalls->next;
 996       changed |= optimize_tail_call (tailcalls, opt_tailcalls);
 997       free (tailcalls);
 998     }
 999
1000   if (a_acc || m_acc)
1001     {
1002       /* Modify the remaining return statements.  */
1003       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1004         {
1005           stmt = last_stmt (e->src);
1006
1007           if (stmt
1008               && gimple_code (stmt) == GIMPLE_RETURN)
1009             adjust_return_value (e->src, m_acc, a_acc);
1010         }
1011     }
1012
1013   if (changed)
1014     free_dominance_info (CDI_DOMINATORS);
1015
1016   if (phis_constructed)
1017     add_virtual_phis ();
1018   if (changed)
1019     return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
1020   return 0;
1021 }
1022
1023 static unsigned int
1024 execute_tail_recursion (void)
1025 {
1026   return tree_optimize_tail_calls_1 (false);
1027 }
1028
1029 static bool
1030 gate_tail_calls (void)
1031 {
1032   return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call);
1033 }
1034
1035 static unsigned int
1036 execute_tail_calls (void)
1037 {
1038   return tree_optimize_tail_calls_1 (true);
1039 }
1040
1041 struct gimple_opt_pass pass_tail_recursion =
1042 {
1043  {
1044   GIMPLE_PASS,
1045   "tailr",                              /* name */
1046   gate_tail_calls,                      /* gate */
1047   execute_tail_recursion,               /* execute */
1048   NULL,                                 /* sub */
1049   NULL,                                 /* next */
1050   0,                                    /* static_pass_number */
1051   TV_NONE,                              /* tv_id */
1052   PROP_cfg | PROP_ssa,                  /* properties_required */
1053   0,                                    /* properties_provided */
1054   0,                                    /* properties_destroyed */
1055   0,                                    /* todo_flags_start */
1056   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1057  }
1058 };
1059
1060 struct gimple_opt_pass pass_tail_calls =
1061 {
1062  {
1063   GIMPLE_PASS,
1064   "tailc",                              /* name */
1065   gate_tail_calls,                      /* gate */
1066   execute_tail_calls,                   /* execute */
1067   NULL,                                 /* sub */
1068   NULL,                                 /* next */
1069   0,                                    /* static_pass_number */
1070   TV_NONE,                              /* tv_id */
1071   PROP_cfg | PROP_ssa,                  /* properties_required */
1072   0,                                    /* properties_provided */
1073   0,                                    /* properties_destroyed */
1074   0,                                    /* todo_flags_start */
1075   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1076  }
1077 };