gcc/tree-tailcall.c

   1 /* Tail call optimization on trees.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
   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
 379   if (!single_succ_p (bb))
 380     return;
 381
 382   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
 383     {
 384       stmt = gsi_stmt (gsi);
 385
 386       /* Ignore labels.  */
 387       if (gimple_code (stmt) == GIMPLE_LABEL || is_gimple_debug (stmt))
 388         continue;
 389
 390       /* Check for a call.  */
 391       if (is_gimple_call (stmt))
 392         {
 393           call = stmt;
 394           ass_var = gimple_call_lhs (stmt);
 395           break;
 396         }
 397
 398       /* If the statement references memory or volatile operands, fail.  */
 399       if (gimple_references_memory_p (stmt)
 400           || gimple_has_volatile_ops (stmt))
 401         return;
 402     }
 403
 404   if (gsi_end_p (gsi))
 405     {
 406       edge_iterator ei;
 407       /* Recurse to the predecessors.  */
 408       FOR_EACH_EDGE (e, ei, bb->preds)
 409         find_tail_calls (e->src, ret);
 410
 411       return;
 412     }
 413
 414   /* If the LHS of our call is not just a simple register, we can't
 415      transform this into a tail or sibling call.  This situation happens,
 416      in (e.g.) "*p = foo()" where foo returns a struct.  In this case
 417      we won't have a temporary here, but we need to carry out the side
 418      effect anyway, so tailcall is impossible.
 419
 420      ??? In some situations (when the struct is returned in memory via
 421      invisible argument) we could deal with this, e.g. by passing 'p'
 422      itself as that argument to foo, but it's too early to do this here,
 423      and expand_call() will not handle it anyway.  If it ever can, then
 424      we need to revisit this here, to allow that situation.  */
 425   if (ass_var && !is_gimple_reg (ass_var))
 426     return;
 427
 428   /* We found the call, check whether it is suitable.  */
 429   tail_recursion = false;
 430   func = gimple_call_fndecl (call);
 431   if (func == current_function_decl)
 432     {
 433       tree arg;
 434       for (param = DECL_ARGUMENTS (func), idx = 0;
 435            param && idx < gimple_call_num_args (call);
 436            param = TREE_CHAIN (param), idx ++)
 437         {
 438           arg = gimple_call_arg (call, idx);
 439           if (param != arg)
 440             {
 441               /* Make sure there are no problems with copying.  The parameter
 442                  have a copyable type and the two arguments must have reasonably
 443                  equivalent types.  The latter requirement could be relaxed if
 444                  we emitted a suitable type conversion statement.  */
 445               if (!is_gimple_reg_type (TREE_TYPE (param))
 446                   || !useless_type_conversion_p (TREE_TYPE (param),
 447                                                  TREE_TYPE (arg)))
 448                 break;
 449
 450               /* The parameter should be a real operand, so that phi node
 451                  created for it at the start of the function has the meaning
 452                  of copying the value.  This test implies is_gimple_reg_type
 453                  from the previous condition, however this one could be
 454                  relaxed by being more careful with copying the new value
 455                  of the parameter (emitting appropriate GIMPLE_ASSIGN and
 456                  updating the virtual operands).  */
 457               if (!is_gimple_reg (param))
 458                 break;
 459             }
 460         }
 461       if (idx == gimple_call_num_args (call) && !param)
 462         tail_recursion = true;
 463     }
 464
 465   /* Now check the statements after the call.  None of them has virtual
 466      operands, so they may only depend on the call through its return
 467      value.  The return value should also be dependent on each of them,
 468      since we are running after dce.  */
 469   m = NULL_TREE;
 470   a = NULL_TREE;
 471
 472   abb = bb;
 473   agsi = gsi;
 474   while (1)
 475     {
 476       tree tmp_a = NULL_TREE;
 477       tree tmp_m = NULL_TREE;
 478       gsi_next (&agsi);
 479
 480       while (gsi_end_p (agsi))
 481         {
 482           ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
 483           abb = single_succ (abb);
 484           agsi = gsi_start_bb (abb);
 485         }
 486
 487       stmt = gsi_stmt (agsi);
 488
 489       if (gimple_code (stmt) == GIMPLE_LABEL)
 490         continue;
 491
 492       if (gimple_code (stmt) == GIMPLE_RETURN)
 493         break;
 494
 495       if (is_gimple_debug (stmt))
 496         continue;
 497
 498       if (gimple_code (stmt) != GIMPLE_ASSIGN)
 499         return;
 500
 501       /* This is a gimple assign. */
 502       if (! process_assignment (stmt, gsi, &tmp_m, &tmp_a, &ass_var))
 503         return;
 504
 505       if (tmp_a)
 506         {
 507           if (a)
 508             a = fold_build2 (PLUS_EXPR, TREE_TYPE (tmp_a), a, tmp_a);
 509           else
 510             a = tmp_a;
 511         }
 512       if (tmp_m)
 513         {
 514           if (m)
 515             m = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), m, tmp_m);
 516           else
 517             m = tmp_m;
 518
 519           if (a)
 520             a = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), a, tmp_m);
 521         }
 522     }
 523
 524   /* See if this is a tail call we can handle.  */
 525   ret_var = gimple_return_retval (stmt);
 526
 527   /* We may proceed if there either is no return value, or the return value
 528      is identical to the call's return.  */
 529   if (ret_var
 530       && (ret_var != ass_var))
 531     return;
 532
 533   /* If this is not a tail recursive call, we cannot handle addends or
 534      multiplicands.  */
 535   if (!tail_recursion && (m || a))
 536     return;
 537
 538   nw = XNEW (struct tailcall);
 539
 540   nw->call_gsi = gsi;
 541
 542   nw->tail_recursion = tail_recursion;
 543
 544   nw->mult = m;
 545   nw->add = a;
 546
 547   nw->next = *ret;
 548   *ret = nw;
 549 }
 550
 551 /* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E.  */
 552
 553 static void
 554 add_successor_phi_arg (edge e, tree var, tree phi_arg)
 555 {
 556   gimple_stmt_iterator gsi;
 557
 558   for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
 559     if (PHI_RESULT (gsi_stmt (gsi)) == var)
 560       break;
 561
 562   gcc_assert (!gsi_end_p (gsi));
 563   add_phi_arg (gsi_stmt (gsi), phi_arg, e, UNKNOWN_LOCATION);
 564 }
 565
 566 /* Creates a GIMPLE statement which computes the operation specified by
 567    CODE, OP0 and OP1 to a new variable with name LABEL and inserts the
 568    statement in the position specified by GSI and UPDATE.  Returns the
 569    tree node of the statement's result.  */
 570
 571 static tree
 572 adjust_return_value_with_ops (enum tree_code code, const char *label,
 573                               tree acc, tree op1, gimple_stmt_iterator gsi)
 574 {
 575
 576   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 577   tree tmp = create_tmp_var (ret_type, label);
 578   gimple stmt;
 579   tree result;
 580
 581   if (TREE_CODE (ret_type) == COMPLEX_TYPE
 582       || TREE_CODE (ret_type) == VECTOR_TYPE)
 583     DECL_GIMPLE_REG_P (tmp) = 1;
 584   add_referenced_var (tmp);
 585
 586   if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
 587     stmt = gimple_build_assign_with_ops (code, tmp, acc, op1);
 588   else
 589     {
 590       tree rhs = fold_convert (TREE_TYPE (acc),
 591                                fold_build2 (code,
 592                                             TREE_TYPE (op1),
 593                                             fold_convert (TREE_TYPE (op1), acc),
 594                                             op1));
 595       rhs = force_gimple_operand_gsi (&gsi, rhs,
 596                                       false, NULL, true, GSI_CONTINUE_LINKING);
 597       stmt = gimple_build_assign (NULL_TREE, rhs);
 598     }
 599
 600   result = make_ssa_name (tmp, stmt);
 601   gimple_assign_set_lhs (stmt, result);
 602   update_stmt (stmt);
 603   gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
 604   return result;
 605 }
 606
 607 /* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
 608    the computation specified by CODE and OP1 and insert the statement
 609    at the position specified by GSI as a new statement.  Returns new SSA name
 610    of updated accumulator.  */
 611
 612 static tree
 613 update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
 614                              gimple_stmt_iterator gsi)
 615 {
 616   gimple stmt;
 617   tree var;
 618   if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
 619     stmt = gimple_build_assign_with_ops (code, SSA_NAME_VAR (acc), acc, op1);
 620   else
 621     {
 622       tree rhs = fold_convert (TREE_TYPE (acc),
 623                                fold_build2 (code,
 624                                             TREE_TYPE (op1),
 625                                             fold_convert (TREE_TYPE (op1), acc),
 626                                             op1));
 627       rhs = force_gimple_operand_gsi (&gsi, rhs,
 628                                       false, NULL, false, GSI_CONTINUE_LINKING);
 629       stmt = gimple_build_assign (NULL_TREE, rhs);
 630     }
 631   var = make_ssa_name (SSA_NAME_VAR (acc), stmt);
 632   gimple_assign_set_lhs (stmt, var);
 633   update_stmt (stmt);
 634   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
 635   return var;
 636 }
 637
 638 /* Adjust the accumulator values according to A and M after GSI, and update
 639    the phi nodes on edge BACK.  */
 640
 641 static void
 642 adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
 643 {
 644   tree var, a_acc_arg, m_acc_arg;
 645
 646   if (m)
 647     m = force_gimple_operand_gsi (&gsi, m, true, NULL, true, GSI_SAME_STMT);
 648   if (a)
 649     a = force_gimple_operand_gsi (&gsi, a, true, NULL, true, GSI_SAME_STMT);
 650
 651   a_acc_arg = a_acc;
 652   m_acc_arg = m_acc;
 653   if (a)
 654     {
 655       if (m_acc)
 656         {
 657           if (integer_onep (a))
 658             var = m_acc;
 659           else
 660             var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc,
 661                                                 a, gsi);
 662         }
 663       else
 664         var = a;
 665
 666       a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi);
 667     }
 668
 669   if (m)
 670     m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi);
 671
 672   if (a_acc)
 673     add_successor_phi_arg (back, a_acc, a_acc_arg);
 674
 675   if (m_acc)
 676     add_successor_phi_arg (back, m_acc, m_acc_arg);
 677 }
 678
 679 /* Adjust value of the return at the end of BB according to M and A
 680    accumulators.  */
 681
 682 static void
 683 adjust_return_value (basic_block bb, tree m, tree a)
 684 {
 685   tree retval;
 686   gimple ret_stmt = gimple_seq_last_stmt (bb_seq (bb));
 687   gimple_stmt_iterator gsi = gsi_last_bb (bb);
 688
 689   gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN);
 690
 691   retval = gimple_return_retval (ret_stmt);
 692   if (!retval || retval == error_mark_node)
 693     return;
 694
 695   if (m)
 696     retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval,
 697                                            gsi);
 698   if (a)
 699     retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval,
 700                                            gsi);
 701   gimple_return_set_retval (ret_stmt, retval);
 702   update_stmt (ret_stmt);
 703 }
 704
 705 /* Subtract COUNT and FREQUENCY from the basic block and it's
 706    outgoing edge.  */
 707 static void
 708 decrease_profile (basic_block bb, gcov_type count, int frequency)
 709 {
 710   edge e;
 711   bb->count -= count;
 712   if (bb->count < 0)
 713     bb->count = 0;
 714   bb->frequency -= frequency;
 715   if (bb->frequency < 0)
 716     bb->frequency = 0;
 717   if (!single_succ_p (bb))
 718     {
 719       gcc_assert (!EDGE_COUNT (bb->succs));
 720       return;
 721     }
 722   e = single_succ_edge (bb);
 723   e->count -= count;
 724   if (e->count < 0)
 725     e->count = 0;
 726 }
 727
 728 /* Returns true if argument PARAM of the tail recursive call needs to be copied
 729    when the call is eliminated.  */
 730
 731 static bool
 732 arg_needs_copy_p (tree param)
 733 {
 734   tree def;
 735
 736   if (!is_gimple_reg (param) || !var_ann (param))
 737     return false;
 738
 739   /* Parameters that are only defined but never used need not be copied.  */
 740   def = gimple_default_def (cfun, param);
 741   if (!def)
 742     return false;
 743
 744   return true;
 745 }
 746
 747 /* Eliminates tail call described by T.  TMP_VARS is a list of
 748    temporary variables used to copy the function arguments.  */
 749
 750 static void
 751 eliminate_tail_call (struct tailcall *t)
 752 {
 753   tree param, rslt;
 754   gimple stmt, call;
 755   tree arg;
 756   size_t idx;
 757   basic_block bb, first;
 758   edge e;
 759   gimple phi;
 760   gimple_stmt_iterator gsi;
 761   gimple orig_stmt;
 762
 763   stmt = orig_stmt = gsi_stmt (t->call_gsi);
 764   bb = gsi_bb (t->call_gsi);
 765
 766   if (dump_file && (dump_flags & TDF_DETAILS))
 767     {
 768       fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
 769                bb->index);
 770       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 771       fprintf (dump_file, "\n");
 772     }
 773
 774   gcc_assert (is_gimple_call (stmt));
 775
 776   first = single_succ (ENTRY_BLOCK_PTR);
 777
 778   /* Remove the code after call_gsi that will become unreachable.  The
 779      possibly unreachable code in other blocks is removed later in
 780      cfg cleanup.  */
 781   gsi = t->call_gsi;
 782   gsi_next (&gsi);
 783   while (!gsi_end_p (gsi))
 784     {
 785       gimple t = gsi_stmt (gsi);
 786       /* Do not remove the return statement, so that redirect_edge_and_branch
 787          sees how the block ends.  */
 788       if (gimple_code (t) == GIMPLE_RETURN)
 789         break;
 790
 791       gsi_remove (&gsi, true);
 792       release_defs (t);
 793     }
 794
 795   /* Number of executions of function has reduced by the tailcall.  */
 796   e = single_succ_edge (gsi_bb (t->call_gsi));
 797   decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
 798   decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
 799   if (e->dest != EXIT_BLOCK_PTR)
 800     decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
 801
 802   /* Replace the call by a jump to the start of function.  */
 803   e = redirect_edge_and_branch (single_succ_edge (gsi_bb (t->call_gsi)),
 804                                 first);
 805   gcc_assert (e);
 806   PENDING_STMT (e) = NULL;
 807
 808   /* Add phi node entries for arguments.  The ordering of the phi nodes should
 809      be the same as the ordering of the arguments.  */
 810   for (param = DECL_ARGUMENTS (current_function_decl),
 811          idx = 0, gsi = gsi_start_phis (first);
 812        param;
 813        param = TREE_CHAIN (param), idx++)
 814     {
 815       if (!arg_needs_copy_p (param))
 816         continue;
 817
 818       arg = gimple_call_arg (stmt, idx);
 819       phi = gsi_stmt (gsi);
 820       gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
 821
 822       add_phi_arg (phi, arg, e, gimple_location (stmt));
 823       gsi_next (&gsi);
 824     }
 825
 826   /* Update the values of accumulators.  */
 827   adjust_accumulator_values (t->call_gsi, t->mult, t->add, e);
 828
 829   call = gsi_stmt (t->call_gsi);
 830   rslt = gimple_call_lhs (call);
 831   if (rslt != NULL_TREE)
 832     {
 833       /* Result of the call will no longer be defined.  So adjust the
 834          SSA_NAME_DEF_STMT accordingly.  */
 835       SSA_NAME_DEF_STMT (rslt) = gimple_build_nop ();
 836     }
 837
 838   gsi_remove (&t->call_gsi, true);
 839   release_defs (call);
 840 }
 841
 842 /* Add phi nodes for the virtual operands defined in the function to the
 843    header of the loop created by tail recursion elimination.
 844
 845    Originally, we used to add phi nodes only for call clobbered variables,
 846    as the value of the non-call clobbered ones obviously cannot be used
 847    or changed within the recursive call.  However, the local variables
 848    from multiple calls now share the same location, so the virtual ssa form
 849    requires us to say that the location dies on further iterations of the loop,
 850    which requires adding phi nodes.
 851 */
 852 static void
 853 add_virtual_phis (void)
 854 {
 855   referenced_var_iterator rvi;
 856   tree var;
 857
 858   /* The problematic part is that there is no way how to know what
 859      to put into phi nodes (there in fact does not have to be such
 860      ssa name available).  A solution would be to have an artificial
 861      use/kill for all virtual operands in EXIT node.  Unless we have
 862      this, we cannot do much better than to rebuild the ssa form for
 863      possibly affected virtual ssa names from scratch.  */
 864
 865   FOR_EACH_REFERENCED_VAR (var, rvi)
 866     {
 867       if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE)
 868         mark_sym_for_renaming (var);
 869     }
 870 }
 871
 872 /* Optimizes the tailcall described by T.  If OPT_TAILCALLS is true, also
 873    mark the tailcalls for the sibcall optimization.  */
 874
 875 static bool
 876 optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
 877 {
 878   if (t->tail_recursion)
 879     {
 880       eliminate_tail_call (t);
 881       return true;
 882     }
 883
 884   if (opt_tailcalls)
 885     {
 886       gimple stmt = gsi_stmt (t->call_gsi);
 887
 888       gimple_call_set_tail (stmt, true);
 889       if (dump_file && (dump_flags & TDF_DETAILS))
 890         {
 891           fprintf (dump_file, "Found tail call ");
 892           print_gimple_stmt (dump_file, stmt, 0, dump_flags);
 893           fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index);
 894         }
 895     }
 896
 897   return false;
 898 }
 899
 900 /* Creates a tail-call accumulator of the same type as the return type of the
 901    current function.  LABEL is the name used to creating the temporary
 902    variable for the accumulator.  The accumulator will be inserted in the
 903    phis of a basic block BB with single predecessor with an initial value
 904    INIT converted to the current function return type.  */
 905
 906 static tree
 907 create_tailcall_accumulator (const char *label, basic_block bb, tree init)
 908 {
 909   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 910   tree tmp = create_tmp_var (ret_type, label);
 911   gimple phi;
 912
 913   if (TREE_CODE (ret_type) == COMPLEX_TYPE
 914       || TREE_CODE (ret_type) == VECTOR_TYPE)
 915     DECL_GIMPLE_REG_P (tmp) = 1;
 916   add_referenced_var (tmp);
 917   phi = create_phi_node (tmp, bb);
 918   /* RET_TYPE can be a float when -ffast-maths is enabled.  */
 919   add_phi_arg (phi, fold_convert (ret_type, init), single_pred_edge (bb),
 920                UNKNOWN_LOCATION);
 921   return PHI_RESULT (phi);
 922 }
 923
 924 /* Optimizes tail calls in the function, turning the tail recursion
 925    into iteration.  */
 926
 927 static unsigned int
 928 tree_optimize_tail_calls_1 (bool opt_tailcalls)
 929 {
 930   edge e;
 931   bool phis_constructed = false;
 932   struct tailcall *tailcalls = NULL, *act, *next;
 933   bool changed = false;
 934   basic_block first = single_succ (ENTRY_BLOCK_PTR);
 935   tree param;
 936   gimple stmt;
 937   edge_iterator ei;
 938
 939   if (!suitable_for_tail_opt_p ())
 940     return 0;
 941   if (opt_tailcalls)
 942     opt_tailcalls = suitable_for_tail_call_opt_p ();
 943
 944   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 945     {
 946       /* Only traverse the normal exits, i.e. those that end with return
 947          statement.  */
 948       stmt = last_stmt (e->src);
 949
 950       if (stmt
 951           && gimple_code (stmt) == GIMPLE_RETURN)
 952         find_tail_calls (e->src, &tailcalls);
 953     }
 954
 955   /* Construct the phi nodes and accumulators if necessary.  */
 956   a_acc = m_acc = NULL_TREE;
 957   for (act = tailcalls; act; act = act->next)
 958     {
 959       if (!act->tail_recursion)
 960         continue;
 961
 962       if (!phis_constructed)
 963         {
 964           /* Ensure that there is only one predecessor of the block
 965              or if there are existing degenerate PHI nodes.  */
 966           if (!single_pred_p (first)
 967               || !gimple_seq_empty_p (phi_nodes (first)))
 968             first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
 969
 970           /* Copy the args if needed.  */
 971           for (param = DECL_ARGUMENTS (current_function_decl);
 972                param;
 973                param = TREE_CHAIN (param))
 974             if (arg_needs_copy_p (param))
 975               {
 976                 tree name = gimple_default_def (cfun, param);
 977                 tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
 978                 gimple phi;
 979
 980                 set_default_def (param, new_name);
 981                 phi = create_phi_node (name, first);
 982                 SSA_NAME_DEF_STMT (name) = phi;
 983                 add_phi_arg (phi, new_name, single_pred_edge (first),
 984                              EXPR_LOCATION (param));
 985               }
 986           phis_constructed = true;
 987         }
 988
 989       if (act->add && !a_acc)
 990         a_acc = create_tailcall_accumulator ("add_acc", first,
 991                                              integer_zero_node);
 992
 993       if (act->mult && !m_acc)
 994         m_acc = create_tailcall_accumulator ("mult_acc", first,
 995                                              integer_one_node);
 996     }
 997
 998   for (; tailcalls; tailcalls = next)
 999     {
1000       next = tailcalls->next;
1001       changed |= optimize_tail_call (tailcalls, opt_tailcalls);
1002       free (tailcalls);
1003     }
1004
1005   if (a_acc || m_acc)
1006     {
1007       /* Modify the remaining return statements.  */
1008       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1009         {
1010           stmt = last_stmt (e->src);
1011
1012           if (stmt
1013               && gimple_code (stmt) == GIMPLE_RETURN)
1014             adjust_return_value (e->src, m_acc, a_acc);
1015         }
1016     }
1017
1018   if (changed)
1019     free_dominance_info (CDI_DOMINATORS);
1020
1021   if (phis_constructed)
1022     add_virtual_phis ();
1023   if (changed)
1024     return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
1025   return 0;
1026 }
1027
1028 static unsigned int
1029 execute_tail_recursion (void)
1030 {
1031   return tree_optimize_tail_calls_1 (false);
1032 }
1033
1034 static bool
1035 gate_tail_calls (void)
1036 {
1037   return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call);
1038 }
1039
1040 static unsigned int
1041 execute_tail_calls (void)
1042 {
1043   return tree_optimize_tail_calls_1 (true);
1044 }
1045
1046 struct gimple_opt_pass pass_tail_recursion =
1047 {
1048  {
1049   GIMPLE_PASS,
1050   "tailr",                              /* name */
1051   gate_tail_calls,                      /* gate */
1052   execute_tail_recursion,               /* execute */
1053   NULL,                                 /* sub */
1054   NULL,                                 /* next */
1055   0,                                    /* static_pass_number */
1056   TV_NONE,                              /* tv_id */
1057   PROP_cfg | PROP_ssa,                  /* properties_required */
1058   0,                                    /* properties_provided */
1059   0,                                    /* properties_destroyed */
1060   0,                                    /* todo_flags_start */
1061   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1062  }
1063 };
1064
1065 struct gimple_opt_pass pass_tail_calls =
1066 {
1067  {
1068   GIMPLE_PASS,
1069   "tailc",                              /* name */
1070   gate_tail_calls,                      /* gate */
1071   execute_tail_calls,                   /* execute */
1072   NULL,                                 /* sub */
1073   NULL,                                 /* next */
1074   0,                                    /* static_pass_number */
1075   TV_NONE,                              /* tv_id */
1076   PROP_cfg | PROP_ssa,                  /* properties_required */
1077   0,                                    /* properties_provided */
1078   0,                                    /* properties_destroyed */
1079   0,                                    /* todo_flags_start */
1080   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1081  }
1082 };