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