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