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) num_referenced_vars; i++)
 143     {
 144       tree var = VEC_index (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       /* Check for a call.  */
 398       if (TREE_CODE (stmt) == MODIFY_EXPR)
 399         {
 400           ass_var = TREE_OPERAND (stmt, 0);
 401           call = TREE_OPERAND (stmt, 1);
 402           if (TREE_CODE (call) == WITH_SIZE_EXPR)
 403             call = TREE_OPERAND (call, 0);
 404         }
 405       else
 406         {
 407           ass_var = NULL_TREE;
 408           call = stmt;
 409         }
 410
 411       if (TREE_CODE (call) == CALL_EXPR)
 412         break;
 413
 414       /* If the statement has virtual or volatile operands, fail.  */
 415       ann = stmt_ann (stmt);
 416       if (!ZERO_SSA_OPERANDS (stmt, (SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS))
 417           || ann->has_volatile_ops)
 418         return;
 419     }
 420
 421   if (bsi_end_p (bsi))
 422     {
 423       edge_iterator ei;
 424       /* Recurse to the predecessors.  */
 425       FOR_EACH_EDGE (e, ei, bb->preds)
 426         find_tail_calls (e->src, ret);
 427
 428       return;
 429     }
 430
 431   /* We found the call, check whether it is suitable.  */
 432   tail_recursion = false;
 433   func = get_callee_fndecl (call);
 434   if (func == current_function_decl)
 435     {
 436       for (param = DECL_ARGUMENTS (func), args = TREE_OPERAND (call, 1);
 437            param && args;
 438            param = TREE_CHAIN (param), args = TREE_CHAIN (args))
 439         {
 440           tree arg = TREE_VALUE (args);
 441           if (param != arg)
 442             {
 443               /* Make sure there are no problems with copying.  The parameter
 444                  have a copyable type and the two arguments must have reasonably
 445                  equivalent types.  The latter requirement could be relaxed if
 446                  we emitted a suitable type conversion statement.  */
 447               if (!is_gimple_reg_type (TREE_TYPE (param))
 448                   || !lang_hooks.types_compatible_p (TREE_TYPE (param),
 449                                                      TREE_TYPE (arg)))
 450                 break;
 451
 452               /* The parameter should be a real operand, so that phi node
 453                  created for it at the start of the function has the meaning
 454                  of copying the value.  This test implies is_gimple_reg_type
 455                  from the previous condition, however this one could be
 456                  relaxed by being more careful with copying the new value
 457                  of the parameter (emitting appropriate MODIFY_EXPR and
 458                  updating the virtual operands).  */
 459               if (!is_gimple_reg (param))
 460                 break;
 461             }
 462         }
 463       if (!args && !param)
 464         tail_recursion = true;
 465     }
 466
 467   /* Now check the statements after the call.  None of them has virtual
 468      operands, so they may only depend on the call through its return
 469      value.  The return value should also be dependent on each of them,
 470      since we are running after dce.  */
 471   m = NULL_TREE;
 472   a = NULL_TREE;
 473
 474   abb = bb;
 475   absi = bsi;
 476   while (1)
 477     {
 478       bsi_next (&absi);
 479
 480       while (bsi_end_p (absi))
 481         {
 482           ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
 483           abb = single_succ (abb);
 484           absi = bsi_start (abb);
 485         }
 486
 487       stmt = bsi_stmt (absi);
 488
 489       if (TREE_CODE (stmt) == LABEL_EXPR)
 490         continue;
 491
 492       if (TREE_CODE (stmt) == RETURN_EXPR)
 493         break;
 494
 495       if (TREE_CODE (stmt) != MODIFY_EXPR)
 496         return;
 497
 498       if (!process_assignment (stmt, stmt, bsi, &m, &a, &ass_var))
 499         return;
 500     }
 501
 502   /* See if this is a tail call we can handle.  */
 503   ret_var = TREE_OPERAND (stmt, 0);
 504   if (ret_var
 505       && TREE_CODE (ret_var) == MODIFY_EXPR)
 506     {
 507       tree ret_op = TREE_OPERAND (ret_var, 1);
 508       STRIP_NOPS (ret_op);
 509       if (!tail_recursion
 510           && TREE_CODE (ret_op) != SSA_NAME)
 511         return;
 512
 513       if (!process_assignment (ret_var, stmt, bsi, &m, &a, &ass_var))
 514         return;
 515       ret_var = TREE_OPERAND (ret_var, 0);
 516     }
 517
 518   /* We may proceed if there either is no return value, or the return value
 519      is identical to the call's return.  */
 520   if (ret_var
 521       && (ret_var != ass_var))
 522     return;
 523
 524   /* If this is not a tail recursive call, we cannot handle addends or
 525      multiplicands.  */
 526   if (!tail_recursion && (m || a))
 527     return;
 528
 529   nw = xmalloc (sizeof (struct tailcall));
 530
 531   nw->call_block = bb;
 532   nw->call_bsi = bsi;
 533
 534   nw->tail_recursion = tail_recursion;
 535
 536   nw->mult = m;
 537   nw->add = a;
 538
 539   nw->next = *ret;
 540   *ret = nw;
 541 }
 542
 543 /* Adjust the accumulator values according to A and M after BSI, and update
 544    the phi nodes on edge BACK.  */
 545
 546 static void
 547 adjust_accumulator_values (block_stmt_iterator bsi, tree m, tree a, edge back)
 548 {
 549   tree stmt, var, phi, tmp;
 550   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 551   tree a_acc_arg = a_acc, m_acc_arg = m_acc;
 552
 553   if (a)
 554     {
 555       if (m_acc)
 556         {
 557           if (integer_onep (a))
 558             var = m_acc;
 559           else
 560             {
 561               stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 562                             build (MULT_EXPR, ret_type, m_acc, a));
 563
 564               tmp = create_tmp_var (ret_type, "acc_tmp");
 565               add_referenced_tmp_var (tmp);
 566
 567               var = make_ssa_name (tmp, stmt);
 568               TREE_OPERAND (stmt, 0) = var;
 569               bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 570             }
 571         }
 572       else
 573         var = a;
 574
 575       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 576                     build (PLUS_EXPR, ret_type, a_acc, var));
 577       var = make_ssa_name (SSA_NAME_VAR (a_acc), stmt);
 578       TREE_OPERAND (stmt, 0) = var;
 579       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 580       a_acc_arg = var;
 581     }
 582
 583   if (m)
 584     {
 585       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 586                     build (MULT_EXPR, ret_type, m_acc, m));
 587       var = make_ssa_name (SSA_NAME_VAR (m_acc), stmt);
 588       TREE_OPERAND (stmt, 0) = var;
 589       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 590       m_acc_arg = var;
 591     }
 592
 593   if (a_acc)
 594     {
 595       for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
 596         if (PHI_RESULT (phi) == a_acc)
 597           break;
 598
 599       add_phi_arg (phi, a_acc_arg, back);
 600     }
 601
 602   if (m_acc)
 603     {
 604       for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
 605         if (PHI_RESULT (phi) == m_acc)
 606           break;
 607
 608       add_phi_arg (phi, m_acc_arg, back);
 609     }
 610 }
 611
 612 /* Adjust value of the return at the end of BB according to M and A
 613    accumulators.  */
 614
 615 static void
 616 adjust_return_value (basic_block bb, tree m, tree a)
 617 {
 618   tree ret_stmt = last_stmt (bb), ret_var, var, stmt, tmp;
 619   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 620   block_stmt_iterator bsi = bsi_last (bb);
 621
 622   gcc_assert (TREE_CODE (ret_stmt) == RETURN_EXPR);
 623
 624   ret_var = TREE_OPERAND (ret_stmt, 0);
 625   if (!ret_var)
 626     return;
 627
 628   if (TREE_CODE (ret_var) == MODIFY_EXPR)
 629     {
 630       ret_var->common.ann = (tree_ann_t) stmt_ann (ret_stmt);
 631       bsi_replace (&bsi, ret_var, true);
 632       SSA_NAME_DEF_STMT (TREE_OPERAND (ret_var, 0)) = ret_var;
 633       ret_var = TREE_OPERAND (ret_var, 0);
 634       ret_stmt = build1 (RETURN_EXPR, TREE_TYPE (ret_stmt), ret_var);
 635       bsi_insert_after (&bsi, ret_stmt, BSI_NEW_STMT);
 636     }
 637
 638   if (m)
 639     {
 640       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 641                     build (MULT_EXPR, ret_type, m_acc, ret_var));
 642
 643       tmp = create_tmp_var (ret_type, "acc_tmp");
 644       add_referenced_tmp_var (tmp);
 645
 646       var = make_ssa_name (tmp, stmt);
 647       TREE_OPERAND (stmt, 0) = var;
 648       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 649     }
 650   else
 651     var = ret_var;
 652
 653   if (a)
 654     {
 655       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 656                     build (PLUS_EXPR, ret_type, a_acc, var));
 657
 658       tmp = create_tmp_var (ret_type, "acc_tmp");
 659       add_referenced_tmp_var (tmp);
 660
 661       var = make_ssa_name (tmp, stmt);
 662       TREE_OPERAND (stmt, 0) = var;
 663       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 664     }
 665
 666   TREE_OPERAND (ret_stmt, 0) = var;
 667   update_stmt (ret_stmt);
 668 }
 669
 670 /* Eliminates tail call described by T.  TMP_VARS is a list of
 671    temporary variables used to copy the function arguments.  */
 672
 673 static void
 674 eliminate_tail_call (struct tailcall *t)
 675 {
 676   tree param, stmt, args, rslt, call;
 677   basic_block bb, first;
 678   edge e;
 679   tree phi;
 680   block_stmt_iterator bsi;
 681   use_operand_p mayuse;
 682   def_operand_p maydef;
 683   ssa_op_iter iter;
 684   tree orig_stmt;
 685
 686   stmt = orig_stmt = bsi_stmt (t->call_bsi);
 687   bb = t->call_block;
 688
 689   if (dump_file && (dump_flags & TDF_DETAILS))
 690     {
 691       fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
 692                bb->index);
 693       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 694       fprintf (dump_file, "\n");
 695     }
 696
 697   if (TREE_CODE (stmt) == MODIFY_EXPR)
 698     stmt = TREE_OPERAND (stmt, 1);
 699
 700   first = single_succ (ENTRY_BLOCK_PTR);
 701
 702   /* Remove the code after call_bsi that will become unreachable.  The
 703      possibly unreachable code in other blocks is removed later in
 704      cfg cleanup.  */
 705   bsi = t->call_bsi;
 706   bsi_next (&bsi);
 707   while (!bsi_end_p (bsi))
 708     {
 709       tree t = bsi_stmt (bsi);
 710       /* Do not remove the return statement, so that redirect_edge_and_branch
 711          sees how the block ends.  */
 712       if (TREE_CODE (t) == RETURN_EXPR)
 713         break;
 714
 715       bsi_remove (&bsi);
 716       release_defs (t);
 717     }
 718
 719   /* Replace the call by a jump to the start of function.  */
 720   e = redirect_edge_and_branch (single_succ_edge (t->call_block), first);
 721   gcc_assert (e);
 722   PENDING_STMT (e) = NULL_TREE;
 723
 724   /* Add phi node entries for arguments.  Not every PHI node corresponds to
 725      a function argument (there may be PHI nodes for virtual definitions of the
 726      eliminated calls), so we search for a PHI corresponding to each argument
 727      rather than searching for which argument a PHI node corresponds to.  */
 728
 729   for (param = DECL_ARGUMENTS (current_function_decl),
 730        args = TREE_OPERAND (stmt, 1);
 731        param;
 732        param = TREE_CHAIN (param),
 733        args = TREE_CHAIN (args))
 734     {
 735
 736       for (phi = phi_nodes (first); phi; phi = PHI_CHAIN (phi))
 737         if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
 738           break;
 739
 740       /* The phi node indeed does not have to be there, in case the operand is
 741          invariant in the function.  */
 742       if (!phi)
 743         continue;
 744
 745       add_phi_arg (phi, TREE_VALUE (args), e);
 746     }
 747
 748   /* Add phi nodes for the call clobbered variables.  */
 749   FOR_EACH_SSA_MAYDEF_OPERAND (maydef, mayuse, orig_stmt, iter)
 750     {
 751       param = SSA_NAME_VAR (DEF_FROM_PTR (maydef));
 752       for (phi = phi_nodes (first); phi; phi = PHI_CHAIN (phi))
 753         if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
 754           break;
 755
 756       if (!phi)
 757         {
 758           tree name = var_ann (param)->default_def;
 759           tree new_name;
 760
 761           if (!name)
 762             {
 763               /* It may happen that the tag does not have a default_def in case
 764                  when all uses of it are dominated by a MUST_DEF.  This however
 765                  means that it is not necessary to add a phi node for this
 766                  tag.  */
 767               continue;
 768             }
 769           new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
 770
 771           var_ann (param)->default_def = new_name;
 772           phi = create_phi_node (name, first);
 773           SSA_NAME_DEF_STMT (name) = phi;
 774           add_phi_arg (phi, new_name, single_succ_edge (ENTRY_BLOCK_PTR));
 775
 776           /* For all calls the same set of variables should be clobbered.  This
 777              means that there always should be the appropriate phi node except
 778              for the first time we eliminate the call.  */
 779           gcc_assert (EDGE_COUNT (first->preds) <= 2);
 780         }
 781
 782       add_phi_arg (phi, USE_FROM_PTR (mayuse), e);
 783     }
 784
 785   /* Update the values of accumulators.  */
 786   adjust_accumulator_values (t->call_bsi, t->mult, t->add, e);
 787
 788   call = bsi_stmt (t->call_bsi);
 789   if (TREE_CODE (call) == MODIFY_EXPR)
 790     {
 791       rslt = TREE_OPERAND (call, 0);
 792
 793       /* Result of the call will no longer be defined.  So adjust the
 794          SSA_NAME_DEF_STMT accordingly.  */
 795       SSA_NAME_DEF_STMT (rslt) = build_empty_stmt ();
 796     }
 797
 798   bsi_remove (&t->call_bsi);
 799   release_defs (call);
 800 }
 801
 802 /* Optimizes the tailcall described by T.  If OPT_TAILCALLS is true, also
 803    mark the tailcalls for the sibcall optimization.  */
 804
 805 static bool
 806 optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
 807 {
 808   if (t->tail_recursion)
 809     {
 810       eliminate_tail_call (t);
 811       return true;
 812     }
 813
 814   if (opt_tailcalls)
 815     {
 816       tree stmt = bsi_stmt (t->call_bsi);
 817
 818       stmt = get_call_expr_in (stmt);
 819       CALL_EXPR_TAILCALL (stmt) = 1;
 820       if (dump_file && (dump_flags & TDF_DETAILS))
 821         {
 822           fprintf (dump_file, "Found tail call ");
 823           print_generic_expr (dump_file, stmt, dump_flags);
 824           fprintf (dump_file, " in bb %i\n", t->call_block->index);
 825         }
 826     }
 827
 828   return false;
 829 }
 830
 831 /* Optimizes tail calls in the function, turning the tail recursion
 832    into iteration.  */
 833
 834 static void
 835 tree_optimize_tail_calls_1 (bool opt_tailcalls)
 836 {
 837   edge e;
 838   bool phis_constructed = false;
 839   struct tailcall *tailcalls = NULL, *act, *next;
 840   bool changed = false;
 841   basic_block first = single_succ (ENTRY_BLOCK_PTR);
 842   tree stmt, param, ret_type, tmp, phi;
 843   edge_iterator ei;
 844
 845   if (!suitable_for_tail_opt_p ())
 846     return;
 847   if (opt_tailcalls)
 848     opt_tailcalls = suitable_for_tail_call_opt_p ();
 849
 850   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 851     {
 852       /* Only traverse the normal exits, i.e. those that end with return
 853          statement.  */
 854       stmt = last_stmt (e->src);
 855
 856       if (stmt
 857           && TREE_CODE (stmt) == RETURN_EXPR)
 858         find_tail_calls (e->src, &tailcalls);
 859     }
 860
 861   /* Construct the phi nodes and accumulators if necessary.  */
 862   a_acc = m_acc = NULL_TREE;
 863   for (act = tailcalls; act; act = act->next)
 864     {
 865       if (!act->tail_recursion)
 866         continue;
 867
 868       if (!phis_constructed)
 869         {
 870           /* Ensure that there is only one predecessor of the block.  */
 871           if (!single_pred_p (first))
 872             first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
 873
 874           /* Copy the args if needed.  */
 875           for (param = DECL_ARGUMENTS (current_function_decl);
 876                param;
 877                param = TREE_CHAIN (param))
 878             if (is_gimple_reg (param)
 879                 && var_ann (param)
 880                 /* Also parameters that are only defined but never used need not
 881                    be copied.  */
 882                 && (var_ann (param)->default_def
 883                     && TREE_CODE (var_ann (param)->default_def) == SSA_NAME))
 884             {
 885               tree name = var_ann (param)->default_def;
 886               tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
 887               tree phi;
 888
 889               var_ann (param)->default_def = new_name;
 890               phi = create_phi_node (name, first);
 891               SSA_NAME_DEF_STMT (name) = phi;
 892               add_phi_arg (phi, new_name, single_pred_edge (first));
 893             }
 894           phis_constructed = true;
 895         }
 896
 897       if (act->add && !a_acc)
 898         {
 899           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 900
 901           tmp = create_tmp_var (ret_type, "add_acc");
 902           add_referenced_tmp_var (tmp);
 903
 904           phi = create_phi_node (tmp, first);
 905           add_phi_arg (phi,
 906                        /* RET_TYPE can be a float when -ffast-maths is
 907                           enabled.  */
 908                        fold_convert (ret_type, integer_zero_node),
 909                        single_pred_edge (first));
 910           a_acc = PHI_RESULT (phi);
 911         }
 912
 913       if (act->mult && !m_acc)
 914         {
 915           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 916
 917           tmp = create_tmp_var (ret_type, "mult_acc");
 918           add_referenced_tmp_var (tmp);
 919
 920           phi = create_phi_node (tmp, first);
 921           add_phi_arg (phi,
 922                        /* RET_TYPE can be a float when -ffast-maths is
 923                           enabled.  */
 924                        fold_convert (ret_type, integer_one_node),
 925                        single_pred_edge (first));
 926           m_acc = PHI_RESULT (phi);
 927         }
 928     }
 929
 930   for (; tailcalls; tailcalls = next)
 931     {
 932       next = tailcalls->next;
 933       changed |= optimize_tail_call (tailcalls, opt_tailcalls);
 934       free (tailcalls);
 935     }
 936
 937   if (a_acc || m_acc)
 938     {
 939       /* Modify the remaining return statements.  */
 940       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 941         {
 942           stmt = last_stmt (e->src);
 943
 944           if (stmt
 945               && TREE_CODE (stmt) == RETURN_EXPR)
 946             adjust_return_value (e->src, m_acc, a_acc);
 947         }
 948     }
 949
 950   if (changed)
 951     {
 952       free_dominance_info (CDI_DOMINATORS);
 953       cleanup_tree_cfg ();
 954     }
 955 }
 956
 957 static void
 958 execute_tail_recursion (void)
 959 {
 960   tree_optimize_tail_calls_1 (false);
 961 }
 962
 963 static bool
 964 gate_tail_calls (void)
 965 {
 966   return flag_optimize_sibling_calls != 0;
 967 }
 968
 969 static void
 970 execute_tail_calls (void)
 971 {
 972   tree_optimize_tail_calls_1 (true);
 973 }
 974
 975 struct tree_opt_pass pass_tail_recursion =
 976 {
 977   "tailr",                              /* name */
 978   NULL,                                 /* gate */
 979   execute_tail_recursion,               /* execute */
 980   NULL,                                 /* sub */
 981   NULL,                                 /* next */
 982   0,                                    /* static_pass_number */
 983   0,                                    /* tv_id */
 984   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 985   0,                                    /* properties_provided */
 986   0,                                    /* properties_destroyed */
 987   0,                                    /* todo_flags_start */
 988   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
 989   0                                     /* letter */
 990 };
 991
 992 struct tree_opt_pass pass_tail_calls =
 993 {
 994   "tailc",                              /* name */
 995   gate_tail_calls,                      /* gate */
 996   execute_tail_calls,                   /* execute */
 997   NULL,                                 /* sub */
 998   NULL,                                 /* next */
 999   0,                                    /* static_pass_number */
1000   0,                                    /* tv_id */
1001   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1002   0,                                    /* properties_provided */
1003   0,                                    /* properties_destroyed */
1004   0,                                    /* todo_flags_start */
1005   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
1006   0                                     /* letter */
1007 };