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