gcc/tree-tailcall.c

   1 /* Tail call optimization on trees.
   2    Copyright (C) 2003, 2004, 2005 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 2, 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 COPYING.  If not, write to
  18 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  19 Boston, MA 02110-1301, USA.  */
  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
  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 block in that the call occur.  */
 104   basic_block call_block;
 105
 106   /* The iterator pointing to the call statement.  */
 107   block_stmt_iterator call_bsi;
 108
 109   /* True if it is a call to the current function.  */
 110   bool tail_recursion;
 111
 112   /* The return value of the caller is mult * f + add, where f is the return
 113      value of the call.  */
 114   tree mult, add;
 115
 116   /* Next tailcall in the chain.  */
 117   struct tailcall *next;
 118 };
 119
 120 /* The variables holding the value of multiplicative and additive
 121    accumulator.  */
 122 static tree m_acc, a_acc;
 123
 124 static bool suitable_for_tail_opt_p (void);
 125 static bool optimize_tail_call (struct tailcall *, bool);
 126 static void eliminate_tail_call (struct tailcall *);
 127 static void find_tail_calls (basic_block, struct tailcall **);
 128
 129 /* Returns false when the function is not suitable for tail call optimization
 130    from some reason (e.g. if it takes variable number of arguments).  */
 131
 132 static bool
 133 suitable_for_tail_opt_p (void)
 134 {
 135   referenced_var_iterator rvi;
 136   tree var;
 137
 138   if (current_function_stdarg)
 139     return false;
 140
 141   /* No local variable nor structure field should be call-clobbered.  We
 142      ignore any kind of memory tag, as these are not real variables.  */
 143
 144   FOR_EACH_REFERENCED_VAR (var, rvi)
 145     {
 146
 147       if (!(TREE_STATIC (var) || DECL_EXTERNAL (var))
 148           && (var_ann (var)->mem_tag_kind == NOT_A_TAG
 149               || var_ann (var)->mem_tag_kind == STRUCT_FIELD)
 150           && is_call_clobbered (var))
 151         return false;
 152     }
 153
 154   return true;
 155 }
 156 /* Returns false when the function is not suitable for tail call optimization
 157    from some reason (e.g. if it takes variable number of arguments).
 158    This test must pass in addition to suitable_for_tail_opt_p in order to make
 159    tail call discovery happen.  */
 160
 161 static bool
 162 suitable_for_tail_call_opt_p (void)
 163 {
 164   tree param;
 165
 166   /* alloca (until we have stack slot life analysis) inhibits
 167      sibling call optimizations, but not tail recursion.  */
 168   if (current_function_calls_alloca)
 169     return false;
 170
 171   /* If we are using sjlj exceptions, we may need to add a call to
 172      _Unwind_SjLj_Unregister at exit of the function.  Which means
 173      that we cannot do any sibcall transformations.  */
 174   if (USING_SJLJ_EXCEPTIONS && current_function_has_exception_handlers ())
 175     return false;
 176
 177   /* Any function that calls setjmp might have longjmp called from
 178      any called function.  ??? We really should represent this
 179      properly in the CFG so that this needn't be special cased.  */
 180   if (current_function_calls_setjmp)
 181     return false;
 182
 183   /* ??? It is OK if the argument of a function is taken in some cases,
 184      but not in all cases.  See PR15387 and PR19616.  Revisit for 4.1.  */
 185   for (param = DECL_ARGUMENTS (current_function_decl);
 186        param;
 187        param = TREE_CHAIN (param))
 188     if (TREE_ADDRESSABLE (param))
 189       return false;
 190
 191   return true;
 192 }
 193
 194 /* Checks whether the expression EXPR in stmt AT is independent of the
 195    statement pointed by BSI (in a sense that we already know EXPR's value
 196    at BSI).  We use the fact that we are only called from the chain of
 197    basic blocks that have only single successor.  Returns the expression
 198    containing the value of EXPR at BSI.  */
 199
 200 static tree
 201 independent_of_stmt_p (tree expr, tree at, block_stmt_iterator bsi)
 202 {
 203   basic_block bb, call_bb, at_bb;
 204   edge e;
 205   edge_iterator ei;
 206
 207   if (is_gimple_min_invariant (expr))
 208     return expr;
 209
 210   if (TREE_CODE (expr) != SSA_NAME)
 211     return NULL_TREE;
 212
 213   /* Mark the blocks in the chain leading to the end.  */
 214   at_bb = bb_for_stmt (at);
 215   call_bb = bb_for_stmt (bsi_stmt (bsi));
 216   for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
 217     bb->aux = &bb->aux;
 218   bb->aux = &bb->aux;
 219
 220   while (1)
 221     {
 222       at = SSA_NAME_DEF_STMT (expr);
 223       bb = bb_for_stmt (at);
 224
 225       /* The default definition or defined before the chain.  */
 226       if (!bb || !bb->aux)
 227         break;
 228
 229       if (bb == call_bb)
 230         {
 231           for (; !bsi_end_p (bsi); bsi_next (&bsi))
 232             if (bsi_stmt (bsi) == at)
 233               break;
 234
 235           if (!bsi_end_p (bsi))
 236             expr = NULL_TREE;
 237           break;
 238         }
 239
 240       if (TREE_CODE (at) != PHI_NODE)
 241         {
 242           expr = NULL_TREE;
 243           break;
 244         }
 245
 246       FOR_EACH_EDGE (e, ei, bb->preds)
 247         if (e->src->aux)
 248           break;
 249       gcc_assert (e);
 250
 251       expr = PHI_ARG_DEF_FROM_EDGE (at, e);
 252       if (TREE_CODE (expr) != SSA_NAME)
 253         {
 254           /* The value is a constant.  */
 255           break;
 256         }
 257     }
 258
 259   /* Unmark the blocks.  */
 260   for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
 261     bb->aux = NULL;
 262   bb->aux = NULL;
 263
 264   return expr;
 265 }
 266
 267 /* Simulates the effect of an assignment of ASS in STMT on the return value
 268    of the tail recursive CALL passed in ASS_VAR.  M and A are the
 269    multiplicative and the additive factor for the real return value.  */
 270
 271 static bool
 272 process_assignment (tree ass, tree stmt, block_stmt_iterator call, tree *m,
 273                     tree *a, tree *ass_var)
 274 {
 275   tree op0, op1, non_ass_var;
 276   tree dest = TREE_OPERAND (ass, 0);
 277   tree src = TREE_OPERAND (ass, 1);
 278   enum tree_code code = TREE_CODE (src);
 279   tree src_var = src;
 280
 281   /* See if this is a simple copy operation of an SSA name to the function
 282      result.  In that case we may have a simple tail call.  Ignore type
 283      conversions that can never produce extra code between the function
 284      call and the function return.  */
 285   STRIP_NOPS (src_var);
 286   if (TREE_CODE (src_var) == SSA_NAME)
 287     {
 288       if (src_var != *ass_var)
 289         return false;
 290
 291       *ass_var = dest;
 292       return true;
 293     }
 294
 295   if (TREE_CODE_CLASS (code) != tcc_binary)
 296     return false;
 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_unsafe_math_optimizations)
 302     if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
 303       return false;
 304
 305   /* We only handle the code like
 306
 307      x = call ();
 308      y = m * x;
 309      z = y + a;
 310      return z;
 311
 312      TODO -- Extend it for cases where the linear transformation of the output
 313      is expressed in a more complicated way.  */
 314
 315   op0 = TREE_OPERAND (src, 0);
 316   op1 = TREE_OPERAND (src, 1);
 317
 318   if (op0 == *ass_var
 319       && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
 320     ;
 321   else if (op1 == *ass_var
 322            && (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
 323     ;
 324   else
 325     return false;
 326
 327   switch (code)
 328     {
 329     case PLUS_EXPR:
 330       /* There should be no previous addition.  TODO -- it should be fairly
 331          straightforward to lift this restriction -- just allow storing
 332          more complicated expressions in *A, and gimplify it in
 333          adjust_accumulator_values.  */
 334       if (*a)
 335         return false;
 336       *a = non_ass_var;
 337       *ass_var = dest;
 338       return true;
 339
 340     case MULT_EXPR:
 341       /* Similar remark applies here.  Handling multiplication after addition
 342          is just slightly more complicated -- we need to multiply both *A and
 343          *M.  */
 344       if (*a || *m)
 345         return false;
 346       *m = non_ass_var;
 347       *ass_var = dest;
 348       return true;
 349
 350       /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR).  */
 351
 352     default:
 353       return false;
 354     }
 355 }
 356
 357 /* Propagate VAR through phis on edge E.  */
 358
 359 static tree
 360 propagate_through_phis (tree var, edge e)
 361 {
 362   basic_block dest = e->dest;
 363   tree phi;
 364
 365   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
 366     if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
 367       return PHI_RESULT (phi);
 368
 369   return var;
 370 }
 371
 372 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
 373    added to the start of RET.  */
 374
 375 static void
 376 find_tail_calls (basic_block bb, struct tailcall **ret)
 377 {
 378   tree ass_var, ret_var, stmt, func, param, args, call = NULL_TREE;
 379   block_stmt_iterator bsi, absi;
 380   bool tail_recursion;
 381   struct tailcall *nw;
 382   edge e;
 383   tree m, a;
 384   basic_block abb;
 385   stmt_ann_t ann;
 386
 387   if (!single_succ_p (bb))
 388     return;
 389
 390   for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
 391     {
 392       stmt = bsi_stmt (bsi);
 393
 394       /* Ignore labels.  */
 395       if (TREE_CODE (stmt) == LABEL_EXPR)
 396         continue;
 397
 398       /* Check for a call.  */
 399       if (TREE_CODE (stmt) == MODIFY_EXPR)
 400         {
 401           ass_var = TREE_OPERAND (stmt, 0);
 402           call = TREE_OPERAND (stmt, 1);
 403           if (TREE_CODE (call) == WITH_SIZE_EXPR)
 404             call = TREE_OPERAND (call, 0);
 405         }
 406       else
 407         {
 408           ass_var = NULL_TREE;
 409           call = stmt;
 410         }
 411
 412       if (TREE_CODE (call) == CALL_EXPR)
 413         break;
 414
 415       /* If the statement has virtual or volatile operands, fail.  */
 416       ann = stmt_ann (stmt);
 417       if (!ZERO_SSA_OPERANDS (stmt, (SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS))
 418           || ann->has_volatile_ops)
 419         return;
 420     }
 421
 422   if (bsi_end_p (bsi))
 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   /* We found the call, check whether it is suitable.  */
 433   tail_recursion = false;
 434   func = get_callee_fndecl (call);
 435   if (func == current_function_decl)
 436     {
 437       for (param = DECL_ARGUMENTS (func), args = TREE_OPERAND (call, 1);
 438            param && args;
 439            param = TREE_CHAIN (param), args = TREE_CHAIN (args))
 440         {
 441           tree arg = TREE_VALUE (args);
 442           if (param != arg)
 443             {
 444               /* Make sure there are no problems with copying.  The parameter
 445                  have a copyable type and the two arguments must have reasonably
 446                  equivalent types.  The latter requirement could be relaxed if
 447                  we emitted a suitable type conversion statement.  */
 448               if (!is_gimple_reg_type (TREE_TYPE (param))
 449                   || !lang_hooks.types_compatible_p (TREE_TYPE (param),
 450                                                      TREE_TYPE (arg)))
 451                 break;
 452
 453               /* The parameter should be a real operand, so that phi node
 454                  created for it at the start of the function has the meaning
 455                  of copying the value.  This test implies is_gimple_reg_type
 456                  from the previous condition, however this one could be
 457                  relaxed by being more careful with copying the new value
 458                  of the parameter (emitting appropriate MODIFY_EXPR and
 459                  updating the virtual operands).  */
 460               if (!is_gimple_reg (param))
 461                 break;
 462             }
 463         }
 464       if (!args && !param)
 465         tail_recursion = true;
 466     }
 467
 468   /* Now check the statements after the call.  None of them has virtual
 469      operands, so they may only depend on the call through its return
 470      value.  The return value should also be dependent on each of them,
 471      since we are running after dce.  */
 472   m = NULL_TREE;
 473   a = NULL_TREE;
 474
 475   abb = bb;
 476   absi = bsi;
 477   while (1)
 478     {
 479       bsi_next (&absi);
 480
 481       while (bsi_end_p (absi))
 482         {
 483           ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
 484           abb = single_succ (abb);
 485           absi = bsi_start (abb);
 486         }
 487
 488       stmt = bsi_stmt (absi);
 489
 490       if (TREE_CODE (stmt) == LABEL_EXPR)
 491         continue;
 492
 493       if (TREE_CODE (stmt) == RETURN_EXPR)
 494         break;
 495
 496       if (TREE_CODE (stmt) != MODIFY_EXPR)
 497         return;
 498
 499       if (!process_assignment (stmt, stmt, bsi, &m, &a, &ass_var))
 500         return;
 501     }
 502
 503   /* See if this is a tail call we can handle.  */
 504   ret_var = TREE_OPERAND (stmt, 0);
 505   if (ret_var
 506       && TREE_CODE (ret_var) == MODIFY_EXPR)
 507     {
 508       tree ret_op = TREE_OPERAND (ret_var, 1);
 509       STRIP_NOPS (ret_op);
 510       if (!tail_recursion
 511           && TREE_CODE (ret_op) != SSA_NAME)
 512         return;
 513
 514       if (!process_assignment (ret_var, stmt, bsi, &m, &a, &ass_var))
 515         return;
 516       ret_var = TREE_OPERAND (ret_var, 0);
 517     }
 518
 519   /* We may proceed if there either is no return value, or the return value
 520      is identical to the call's return.  */
 521   if (ret_var
 522       && (ret_var != ass_var))
 523     return;
 524
 525   /* If this is not a tail recursive call, we cannot handle addends or
 526      multiplicands.  */
 527   if (!tail_recursion && (m || a))
 528     return;
 529
 530   nw = xmalloc (sizeof (struct tailcall));
 531
 532   nw->call_block = bb;
 533   nw->call_bsi = bsi;
 534
 535   nw->tail_recursion = tail_recursion;
 536
 537   nw->mult = m;
 538   nw->add = a;
 539
 540   nw->next = *ret;
 541   *ret = nw;
 542 }
 543
 544 /* Adjust the accumulator values according to A and M after BSI, and update
 545    the phi nodes on edge BACK.  */
 546
 547 static void
 548 adjust_accumulator_values (block_stmt_iterator bsi, tree m, tree a, edge back)
 549 {
 550   tree stmt, var, phi, tmp;
 551   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 552   tree a_acc_arg = a_acc, m_acc_arg = m_acc;
 553
 554   if (a)
 555     {
 556       if (m_acc)
 557         {
 558           if (integer_onep (a))
 559             var = m_acc;
 560           else
 561             {
 562               stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 563                             build (MULT_EXPR, ret_type, m_acc, a));
 564
 565               tmp = create_tmp_var (ret_type, "acc_tmp");
 566               add_referenced_tmp_var (tmp);
 567
 568               var = make_ssa_name (tmp, stmt);
 569               TREE_OPERAND (stmt, 0) = var;
 570               bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 571             }
 572         }
 573       else
 574         var = a;
 575
 576       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 577                     build (PLUS_EXPR, ret_type, a_acc, var));
 578       var = make_ssa_name (SSA_NAME_VAR (a_acc), stmt);
 579       TREE_OPERAND (stmt, 0) = var;
 580       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 581       a_acc_arg = var;
 582     }
 583
 584   if (m)
 585     {
 586       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 587                     build (MULT_EXPR, ret_type, m_acc, m));
 588       var = make_ssa_name (SSA_NAME_VAR (m_acc), stmt);
 589       TREE_OPERAND (stmt, 0) = var;
 590       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 591       m_acc_arg = var;
 592     }
 593
 594   if (a_acc)
 595     {
 596       for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
 597         if (PHI_RESULT (phi) == a_acc)
 598           break;
 599
 600       add_phi_arg (phi, a_acc_arg, back);
 601     }
 602
 603   if (m_acc)
 604     {
 605       for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
 606         if (PHI_RESULT (phi) == m_acc)
 607           break;
 608
 609       add_phi_arg (phi, m_acc_arg, back);
 610     }
 611 }
 612
 613 /* Adjust value of the return at the end of BB according to M and A
 614    accumulators.  */
 615
 616 static void
 617 adjust_return_value (basic_block bb, tree m, tree a)
 618 {
 619   tree ret_stmt = last_stmt (bb), ret_var, var, stmt, tmp;
 620   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 621   block_stmt_iterator bsi = bsi_last (bb);
 622
 623   gcc_assert (TREE_CODE (ret_stmt) == RETURN_EXPR);
 624
 625   ret_var = TREE_OPERAND (ret_stmt, 0);
 626   if (!ret_var)
 627     return;
 628
 629   if (TREE_CODE (ret_var) == MODIFY_EXPR)
 630     {
 631       ret_var->common.ann = (tree_ann_t) stmt_ann (ret_stmt);
 632       bsi_replace (&bsi, ret_var, true);
 633       SSA_NAME_DEF_STMT (TREE_OPERAND (ret_var, 0)) = ret_var;
 634       ret_var = TREE_OPERAND (ret_var, 0);
 635       ret_stmt = build1 (RETURN_EXPR, TREE_TYPE (ret_stmt), ret_var);
 636       bsi_insert_after (&bsi, ret_stmt, BSI_NEW_STMT);
 637     }
 638
 639   if (m)
 640     {
 641       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 642                     build (MULT_EXPR, ret_type, m_acc, ret_var));
 643
 644       tmp = create_tmp_var (ret_type, "acc_tmp");
 645       add_referenced_tmp_var (tmp);
 646
 647       var = make_ssa_name (tmp, stmt);
 648       TREE_OPERAND (stmt, 0) = var;
 649       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 650     }
 651   else
 652     var = ret_var;
 653
 654   if (a)
 655     {
 656       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 657                     build (PLUS_EXPR, ret_type, a_acc, var));
 658
 659       tmp = create_tmp_var (ret_type, "acc_tmp");
 660       add_referenced_tmp_var (tmp);
 661
 662       var = make_ssa_name (tmp, stmt);
 663       TREE_OPERAND (stmt, 0) = var;
 664       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 665     }
 666
 667   TREE_OPERAND (ret_stmt, 0) = var;
 668   update_stmt (ret_stmt);
 669 }
 670
 671 /* Eliminates tail call described by T.  TMP_VARS is a list of
 672    temporary variables used to copy the function arguments.  */
 673
 674 static void
 675 eliminate_tail_call (struct tailcall *t)
 676 {
 677   tree param, stmt, args, rslt, call;
 678   basic_block bb, first;
 679   edge e;
 680   tree phi;
 681   block_stmt_iterator bsi;
 682   use_operand_p mayuse;
 683   def_operand_p maydef;
 684   ssa_op_iter iter;
 685   tree orig_stmt;
 686
 687   stmt = orig_stmt = bsi_stmt (t->call_bsi);
 688   bb = t->call_block;
 689
 690   if (dump_file && (dump_flags & TDF_DETAILS))
 691     {
 692       fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
 693                bb->index);
 694       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 695       fprintf (dump_file, "\n");
 696     }
 697
 698   if (TREE_CODE (stmt) == MODIFY_EXPR)
 699     stmt = TREE_OPERAND (stmt, 1);
 700
 701   first = single_succ (ENTRY_BLOCK_PTR);
 702
 703   /* Remove the code after call_bsi that will become unreachable.  The
 704      possibly unreachable code in other blocks is removed later in
 705      cfg cleanup.  */
 706   bsi = t->call_bsi;
 707   bsi_next (&bsi);
 708   while (!bsi_end_p (bsi))
 709     {
 710       tree t = bsi_stmt (bsi);
 711       /* Do not remove the return statement, so that redirect_edge_and_branch
 712          sees how the block ends.  */
 713       if (TREE_CODE (t) == RETURN_EXPR)
 714         break;
 715
 716       bsi_remove (&bsi);
 717       release_defs (t);
 718     }
 719
 720   /* Replace the call by a jump to the start of function.  */
 721   e = redirect_edge_and_branch (single_succ_edge (t->call_block), first);
 722   gcc_assert (e);
 723   PENDING_STMT (e) = NULL_TREE;
 724
 725   /* Add phi node entries for arguments.  Not every PHI node corresponds to
 726      a function argument (there may be PHI nodes for virtual definitions of the
 727      eliminated calls), so we search for a PHI corresponding to each argument
 728      rather than searching for which argument a PHI node corresponds to.  */
 729
 730   for (param = DECL_ARGUMENTS (current_function_decl),
 731        args = TREE_OPERAND (stmt, 1);
 732        param;
 733        param = TREE_CHAIN (param),
 734        args = TREE_CHAIN (args))
 735     {
 736
 737       for (phi = phi_nodes (first); phi; phi = PHI_CHAIN (phi))
 738         if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
 739           break;
 740
 741       /* The phi node indeed does not have to be there, in case the operand is
 742          invariant in the function.  */
 743       if (!phi)
 744         continue;
 745
 746       add_phi_arg (phi, TREE_VALUE (args), e);
 747     }
 748
 749   /* Add phi nodes for the call clobbered variables.  */
 750   FOR_EACH_SSA_MAYDEF_OPERAND (maydef, mayuse, orig_stmt, iter)
 751     {
 752       param = SSA_NAME_VAR (DEF_FROM_PTR (maydef));
 753       for (phi = phi_nodes (first); phi; phi = PHI_CHAIN (phi))
 754         if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
 755           break;
 756
 757       if (!phi)
 758         {
 759           tree name = var_ann (param)->default_def;
 760           tree new_name;
 761
 762           if (!name)
 763             {
 764               /* It may happen that the tag does not have a default_def in case
 765                  when all uses of it are dominated by a MUST_DEF.  This however
 766                  means that it is not necessary to add a phi node for this
 767                  tag.  */
 768               continue;
 769             }
 770           new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
 771
 772           var_ann (param)->default_def = new_name;
 773           phi = create_phi_node (name, first);
 774           SSA_NAME_DEF_STMT (name) = phi;
 775           add_phi_arg (phi, new_name, single_succ_edge (ENTRY_BLOCK_PTR));
 776
 777           /* For all calls the same set of variables should be clobbered.  This
 778              means that there always should be the appropriate phi node except
 779              for the first time we eliminate the call.  */
 780           gcc_assert (EDGE_COUNT (first->preds) <= 2);
 781         }
 782
 783       add_phi_arg (phi, USE_FROM_PTR (mayuse), e);
 784     }
 785
 786   /* Update the values of accumulators.  */
 787   adjust_accumulator_values (t->call_bsi, t->mult, t->add, e);
 788
 789   call = bsi_stmt (t->call_bsi);
 790   if (TREE_CODE (call) == MODIFY_EXPR)
 791     {
 792       rslt = TREE_OPERAND (call, 0);
 793
 794       /* Result of the call will no longer be defined.  So adjust the
 795          SSA_NAME_DEF_STMT accordingly.  */
 796       SSA_NAME_DEF_STMT (rslt) = build_empty_stmt ();
 797     }
 798
 799   bsi_remove (&t->call_bsi);
 800   release_defs (call);
 801 }
 802
 803 /* Optimizes the tailcall described by T.  If OPT_TAILCALLS is true, also
 804    mark the tailcalls for the sibcall optimization.  */
 805
 806 static bool
 807 optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
 808 {
 809   if (t->tail_recursion)
 810     {
 811       eliminate_tail_call (t);
 812       return true;
 813     }
 814
 815   if (opt_tailcalls)
 816     {
 817       tree stmt = bsi_stmt (t->call_bsi);
 818
 819       stmt = get_call_expr_in (stmt);
 820       CALL_EXPR_TAILCALL (stmt) = 1;
 821       if (dump_file && (dump_flags & TDF_DETAILS))
 822         {
 823           fprintf (dump_file, "Found tail call ");
 824           print_generic_expr (dump_file, stmt, dump_flags);
 825           fprintf (dump_file, " in bb %i\n", t->call_block->index);
 826         }
 827     }
 828
 829   return false;
 830 }
 831
 832 /* Optimizes tail calls in the function, turning the tail recursion
 833    into iteration.  */
 834
 835 static void
 836 tree_optimize_tail_calls_1 (bool opt_tailcalls)
 837 {
 838   edge e;
 839   bool phis_constructed = false;
 840   struct tailcall *tailcalls = NULL, *act, *next;
 841   bool changed = false;
 842   basic_block first = single_succ (ENTRY_BLOCK_PTR);
 843   tree stmt, param, ret_type, tmp, phi;
 844   edge_iterator ei;
 845
 846   if (!suitable_for_tail_opt_p ())
 847     return;
 848   if (opt_tailcalls)
 849     opt_tailcalls = suitable_for_tail_call_opt_p ();
 850
 851   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 852     {
 853       /* Only traverse the normal exits, i.e. those that end with return
 854          statement.  */
 855       stmt = last_stmt (e->src);
 856
 857       if (stmt
 858           && TREE_CODE (stmt) == RETURN_EXPR)
 859         find_tail_calls (e->src, &tailcalls);
 860     }
 861
 862   /* Construct the phi nodes and accumulators if necessary.  */
 863   a_acc = m_acc = NULL_TREE;
 864   for (act = tailcalls; act; act = act->next)
 865     {
 866       if (!act->tail_recursion)
 867         continue;
 868
 869       if (!phis_constructed)
 870         {
 871           /* Ensure that there is only one predecessor of the block.  */
 872           if (!single_pred_p (first))
 873             first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
 874
 875           /* Copy the args if needed.  */
 876           for (param = DECL_ARGUMENTS (current_function_decl);
 877                param;
 878                param = TREE_CHAIN (param))
 879             if (is_gimple_reg (param)
 880                 && var_ann (param)
 881                 /* Also parameters that are only defined but never used need not
 882                    be copied.  */
 883                 && (var_ann (param)->default_def
 884                     && TREE_CODE (var_ann (param)->default_def) == SSA_NAME))
 885             {
 886               tree name = var_ann (param)->default_def;
 887               tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
 888               tree phi;
 889
 890               var_ann (param)->default_def = new_name;
 891               phi = create_phi_node (name, first);
 892               SSA_NAME_DEF_STMT (name) = phi;
 893               add_phi_arg (phi, new_name, single_pred_edge (first));
 894             }
 895           phis_constructed = true;
 896         }
 897
 898       if (act->add && !a_acc)
 899         {
 900           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 901
 902           tmp = create_tmp_var (ret_type, "add_acc");
 903           add_referenced_tmp_var (tmp);
 904
 905           phi = create_phi_node (tmp, first);
 906           add_phi_arg (phi,
 907                        /* RET_TYPE can be a float when -ffast-maths is
 908                           enabled.  */
 909                        fold_convert (ret_type, integer_zero_node),
 910                        single_pred_edge (first));
 911           a_acc = PHI_RESULT (phi);
 912         }
 913
 914       if (act->mult && !m_acc)
 915         {
 916           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 917
 918           tmp = create_tmp_var (ret_type, "mult_acc");
 919           add_referenced_tmp_var (tmp);
 920
 921           phi = create_phi_node (tmp, first);
 922           add_phi_arg (phi,
 923                        /* RET_TYPE can be a float when -ffast-maths is
 924                           enabled.  */
 925                        fold_convert (ret_type, integer_one_node),
 926                        single_pred_edge (first));
 927           m_acc = PHI_RESULT (phi);
 928         }
 929     }
 930
 931   for (; tailcalls; tailcalls = next)
 932     {
 933       next = tailcalls->next;
 934       changed |= optimize_tail_call (tailcalls, opt_tailcalls);
 935       free (tailcalls);
 936     }
 937
 938   if (a_acc || m_acc)
 939     {
 940       /* Modify the remaining return statements.  */
 941       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 942         {
 943           stmt = last_stmt (e->src);
 944
 945           if (stmt
 946               && TREE_CODE (stmt) == RETURN_EXPR)
 947             adjust_return_value (e->src, m_acc, a_acc);
 948         }
 949     }
 950
 951   if (changed)
 952     {
 953       free_dominance_info (CDI_DOMINATORS);
 954       cleanup_tree_cfg ();
 955     }
 956 }
 957
 958 static void
 959 execute_tail_recursion (void)
 960 {
 961   tree_optimize_tail_calls_1 (false);
 962 }
 963
 964 static bool
 965 gate_tail_calls (void)
 966 {
 967   return flag_optimize_sibling_calls != 0;
 968 }
 969
 970 static void
 971 execute_tail_calls (void)
 972 {
 973   tree_optimize_tail_calls_1 (true);
 974 }
 975
 976 struct tree_opt_pass pass_tail_recursion =
 977 {
 978   "tailr",                              /* name */
 979   NULL,                                 /* gate */
 980   execute_tail_recursion,               /* execute */
 981   NULL,                                 /* sub */
 982   NULL,                                 /* next */
 983   0,                                    /* static_pass_number */
 984   0,                                    /* tv_id */
 985   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 986   0,                                    /* properties_provided */
 987   0,                                    /* properties_destroyed */
 988   0,                                    /* todo_flags_start */
 989   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
 990   0                                     /* letter */
 991 };
 992
 993 struct tree_opt_pass pass_tail_calls =
 994 {
 995   "tailc",                              /* name */
 996   gate_tail_calls,                      /* gate */
 997   execute_tail_calls,                   /* execute */
 998   NULL,                                 /* sub */
 999   NULL,                                 /* next */
1000   0,                                    /* static_pass_number */
1001   0,                                    /* tv_id */
1002   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1003   0,                                    /* properties_provided */
1004   0,                                    /* properties_destroyed */
1005   0,                                    /* todo_flags_start */
1006   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
1007   0                                     /* letter */
1008 };