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