gcc/tree-tailcall.c

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