gcc/tree-tailcall.c

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