gcc/tree-tailcall.c

   1 /* Tail call optimization on trees.
   2    Copyright (C) 2003, 2004 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) || DECL_EXTERNAL (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   edge_iterator ei;
 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 = EDGE_SUCC (bb, 0)->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_EACH_EDGE (e, ei, bb->preds)
 235         if (e->src->aux)
 236           break;
 237       gcc_assert (e);
 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 = EDGE_SUCC (bb, 0)->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) != tcc_binary)
 284     return false;
 285
 286   /* Accumulator optimizations will reverse the order of operations.
 287      We can only do that for floating-point types if we're assuming
 288      that addition and multiplication are associative.  */
 289   if (!flag_unsafe_math_optimizations)
 290     if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
 291       return false;
 292
 293   /* We only handle the code like
 294
 295      x = call ();
 296      y = m * x;
 297      z = y + a;
 298      return z;
 299
 300      TODO -- Extend it for cases where the linear transformation of the output
 301      is expressed in a more complicated way.  */
 302
 303   op0 = TREE_OPERAND (src, 0);
 304   op1 = TREE_OPERAND (src, 1);
 305
 306   if (op0 == *ass_var
 307       && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
 308     ;
 309   else if (op1 == *ass_var
 310            && (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
 311     ;
 312   else
 313     return false;
 314
 315   switch (code)
 316     {
 317     case PLUS_EXPR:
 318       /* There should be no previous addition.  TODO -- it should be fairly
 319          straightforward to lift this restriction -- just allow storing
 320          more complicated expressions in *A, and gimplify it in
 321          adjust_accumulator_values.  */
 322       if (*a)
 323         return false;
 324       *a = non_ass_var;
 325       *ass_var = dest;
 326       return true;
 327
 328     case MULT_EXPR:
 329       /* Similar remark applies here.  Handling multiplication after addition
 330          is just slightly more complicated -- we need to multiply both *A and
 331          *M.  */
 332       if (*a || *m)
 333         return false;
 334       *m = non_ass_var;
 335       *ass_var = dest;
 336       return true;
 337
 338       /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR).  */
 339
 340     default:
 341       return false;
 342     }
 343 }
 344
 345 /* Propagate VAR through phis on edge E.  */
 346
 347 static tree
 348 propagate_through_phis (tree var, edge e)
 349 {
 350   basic_block dest = e->dest;
 351   tree phi;
 352
 353   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
 354     if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
 355       return PHI_RESULT (phi);
 356
 357   return var;
 358 }
 359
 360 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
 361    added to the start of RET.  */
 362
 363 static void
 364 find_tail_calls (basic_block bb, struct tailcall **ret)
 365 {
 366   tree ass_var, ret_var, stmt, func, param, args, call = NULL_TREE;
 367   block_stmt_iterator bsi, absi;
 368   bool tail_recursion;
 369   struct tailcall *nw;
 370   edge e;
 371   tree m, a;
 372   basic_block abb;
 373   stmt_ann_t ann;
 374
 375   if (EDGE_COUNT (bb->succs) > 1)
 376     return;
 377
 378   for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
 379     {
 380       stmt = bsi_stmt (bsi);
 381
 382       /* Ignore labels.  */
 383       if (TREE_CODE (stmt) == LABEL_EXPR)
 384         continue;
 385
 386       get_stmt_operands (stmt);
 387
 388       /* Check for a call.  */
 389       if (TREE_CODE (stmt) == MODIFY_EXPR)
 390         {
 391           ass_var = TREE_OPERAND (stmt, 0);
 392           call = TREE_OPERAND (stmt, 1);
 393           if (TREE_CODE (call) == WITH_SIZE_EXPR)
 394             call = TREE_OPERAND (call, 0);
 395         }
 396       else
 397         {
 398           ass_var = NULL_TREE;
 399           call = stmt;
 400         }
 401
 402       if (TREE_CODE (call) == CALL_EXPR)
 403         break;
 404
 405       /* If the statement has virtual or volatile operands, fail.  */
 406       ann = stmt_ann (stmt);
 407       if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann))
 408           || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann))
 409           || NUM_VUSES (VUSE_OPS (ann))
 410           || ann->has_volatile_ops)
 411         return;
 412     }
 413
 414   if (bsi_end_p (bsi))
 415     {
 416       edge_iterator ei;
 417       /* Recurse to the predecessors.  */
 418       FOR_EACH_EDGE (e, ei, bb->preds)
 419         find_tail_calls (e->src, ret);
 420
 421       return;
 422     }
 423
 424   /* We found the call, check whether it is suitable.  */
 425   tail_recursion = false;
 426   func = get_callee_fndecl (call);
 427   if (func == current_function_decl)
 428     {
 429       for (param = DECL_ARGUMENTS (func), args = TREE_OPERAND (call, 1);
 430            param && args;
 431            param = TREE_CHAIN (param), args = TREE_CHAIN (args))
 432         {
 433           tree arg = TREE_VALUE (args);
 434           if (param != arg
 435               /* Make sure there are no problems with copying.  Note we must
 436                  have a copyable type and the two arguments must have reasonably
 437                  equivalent types.  The latter requirement could be relaxed if
 438                  we emitted a suitable type conversion statement.  */
 439               && (!is_gimple_reg_type (TREE_TYPE (param))
 440                   || !lang_hooks.types_compatible_p (TREE_TYPE (param),
 441                                                      TREE_TYPE (arg))))
 442             break;
 443         }
 444       if (!args && !param)
 445         tail_recursion = true;
 446     }
 447
 448   /* Now check the statements after the call.  None of them has virtual
 449      operands, so they may only depend on the call through its return
 450      value.  The return value should also be dependent on each of them,
 451      since we are running after dce.  */
 452   m = NULL_TREE;
 453   a = NULL_TREE;
 454
 455   abb = bb;
 456   absi = bsi;
 457   while (1)
 458     {
 459       bsi_next (&absi);
 460
 461       while (bsi_end_p (absi))
 462         {
 463           ass_var = propagate_through_phis (ass_var, EDGE_SUCC (abb, 0));
 464           abb = EDGE_SUCC (abb, 0)->dest;
 465           absi = bsi_start (abb);
 466         }
 467
 468       stmt = bsi_stmt (absi);
 469
 470       if (TREE_CODE (stmt) == LABEL_EXPR)
 471         continue;
 472
 473       if (TREE_CODE (stmt) == RETURN_EXPR)
 474         break;
 475
 476       if (TREE_CODE (stmt) != MODIFY_EXPR)
 477         return;
 478
 479       if (!process_assignment (stmt, stmt, bsi, &m, &a, &ass_var))
 480         return;
 481     }
 482
 483   /* See if this is a tail call we can handle.  */
 484   ret_var = TREE_OPERAND (stmt, 0);
 485   if (ret_var
 486       && TREE_CODE (ret_var) == MODIFY_EXPR)
 487     {
 488       tree ret_op = TREE_OPERAND (ret_var, 1);
 489       STRIP_NOPS (ret_op);
 490       if (!tail_recursion
 491           && TREE_CODE (ret_op) != SSA_NAME)
 492         return;
 493
 494       if (!process_assignment (ret_var, stmt, bsi, &m, &a, &ass_var))
 495         return;
 496       ret_var = TREE_OPERAND (ret_var, 0);
 497     }
 498
 499   /* We may proceed if there either is no return value, or the return value
 500      is identical to the call's return.  */
 501   if (ret_var
 502       && (ret_var != ass_var))
 503     return;
 504
 505   /* If this is not a tail recursive call, we cannot handle addends or
 506      multiplicands.  */
 507   if (!tail_recursion && (m || a))
 508     return;
 509
 510   nw = xmalloc (sizeof (struct tailcall));
 511
 512   nw->call_block = bb;
 513   nw->call_bsi = bsi;
 514
 515   nw->tail_recursion = tail_recursion;
 516
 517   nw->mult = m;
 518   nw->add = a;
 519
 520   nw->next = *ret;
 521   *ret = nw;
 522 }
 523
 524 /* Adjust the accumulator values according to A and M after BSI, and update
 525    the phi nodes on edge BACK.  */
 526
 527 static void
 528 adjust_accumulator_values (block_stmt_iterator bsi, tree m, tree a, edge back)
 529 {
 530   tree stmt, var, phi, tmp;
 531   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 532   tree a_acc_arg = a_acc, m_acc_arg = m_acc;
 533
 534   if (a)
 535     {
 536       if (m_acc)
 537         {
 538           if (integer_onep (a))
 539             var = m_acc;
 540           else
 541             {
 542               stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 543                             build (MULT_EXPR, ret_type, m_acc, a));
 544
 545               tmp = create_tmp_var (ret_type, "acc_tmp");
 546               add_referenced_tmp_var (tmp);
 547
 548               var = make_ssa_name (tmp, stmt);
 549               TREE_OPERAND (stmt, 0) = var;
 550               bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 551             }
 552         }
 553       else
 554         var = a;
 555
 556       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 557                     build (PLUS_EXPR, ret_type, a_acc, var));
 558       var = make_ssa_name (SSA_NAME_VAR (a_acc), stmt);
 559       TREE_OPERAND (stmt, 0) = var;
 560       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 561       a_acc_arg = var;
 562     }
 563
 564   if (m)
 565     {
 566       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 567                     build (MULT_EXPR, ret_type, m_acc, m));
 568       var = make_ssa_name (SSA_NAME_VAR (m_acc), stmt);
 569       TREE_OPERAND (stmt, 0) = var;
 570       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 571       m_acc_arg = var;
 572     }
 573
 574   if (a_acc)
 575     {
 576       for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
 577         if (PHI_RESULT (phi) == a_acc)
 578           break;
 579
 580       add_phi_arg (&phi, a_acc_arg, back);
 581     }
 582
 583   if (m_acc)
 584     {
 585       for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
 586         if (PHI_RESULT (phi) == m_acc)
 587           break;
 588
 589       add_phi_arg (&phi, m_acc_arg, back);
 590     }
 591 }
 592
 593 /* Adjust value of the return at the end of BB according to M and A
 594    accumulators.  */
 595
 596 static void
 597 adjust_return_value (basic_block bb, tree m, tree a)
 598 {
 599   tree ret_stmt = last_stmt (bb), ret_var, var, stmt, tmp;
 600   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 601   block_stmt_iterator bsi = bsi_last (bb);
 602
 603   gcc_assert (TREE_CODE (ret_stmt) == RETURN_EXPR);
 604
 605   ret_var = TREE_OPERAND (ret_stmt, 0);
 606   if (!ret_var)
 607     return;
 608
 609   if (TREE_CODE (ret_var) == MODIFY_EXPR)
 610     {
 611       ret_var->common.ann = (tree_ann_t) stmt_ann (ret_stmt);
 612       bsi_replace (&bsi, ret_var, true);
 613       SSA_NAME_DEF_STMT (TREE_OPERAND (ret_var, 0)) = ret_var;
 614       ret_var = TREE_OPERAND (ret_var, 0);
 615       ret_stmt = build1 (RETURN_EXPR, TREE_TYPE (ret_stmt), ret_var);
 616       bsi_insert_after (&bsi, ret_stmt, BSI_NEW_STMT);
 617     }
 618
 619   if (m)
 620     {
 621       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 622                     build (MULT_EXPR, ret_type, m_acc, ret_var));
 623
 624       tmp = create_tmp_var (ret_type, "acc_tmp");
 625       add_referenced_tmp_var (tmp);
 626
 627       var = make_ssa_name (tmp, stmt);
 628       TREE_OPERAND (stmt, 0) = var;
 629       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 630     }
 631   else
 632     var = ret_var;
 633
 634   if (a)
 635     {
 636       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 637                     build (PLUS_EXPR, ret_type, a_acc, var));
 638
 639       tmp = create_tmp_var (ret_type, "acc_tmp");
 640       add_referenced_tmp_var (tmp);
 641
 642       var = make_ssa_name (tmp, stmt);
 643       TREE_OPERAND (stmt, 0) = var;
 644       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 645     }
 646
 647   TREE_OPERAND (ret_stmt, 0) = var;
 648   modify_stmt (ret_stmt);
 649 }
 650
 651 /* Eliminates tail call described by T.  TMP_VARS is a list of
 652    temporary variables used to copy the function arguments.  */
 653
 654 static void
 655 eliminate_tail_call (struct tailcall *t)
 656 {
 657   tree param, stmt, args, rslt, call;
 658   basic_block bb, first;
 659   edge e;
 660   tree phi;
 661   stmt_ann_t ann;
 662   v_may_def_optype v_may_defs;
 663   unsigned i;
 664   block_stmt_iterator bsi;
 665
 666   stmt = bsi_stmt (t->call_bsi);
 667   get_stmt_operands (stmt);
 668   ann = stmt_ann (stmt);
 669   bb = t->call_block;
 670
 671   if (dump_file && (dump_flags & TDF_DETAILS))
 672     {
 673       fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
 674                bb->index);
 675       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 676       fprintf (dump_file, "\n");
 677     }
 678
 679   if (TREE_CODE (stmt) == MODIFY_EXPR)
 680     stmt = TREE_OPERAND (stmt, 1);
 681
 682   first = EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest;
 683
 684   /* Remove the code after call_bsi that will become unreachable.  The
 685      possibly unreachable code in other blocks is removed later in
 686      cfg cleanup.  */
 687   bsi = t->call_bsi;
 688   bsi_next (&bsi);
 689   while (!bsi_end_p (bsi))
 690     {
 691       tree t = bsi_stmt (bsi);
 692       /* Do not remove the return statement, so that redirect_edge_and_branch
 693          sees how the block ends.  */
 694       if (TREE_CODE (t) == RETURN_EXPR)
 695         break;
 696
 697       bsi_remove (&bsi);
 698       release_defs (t);
 699     }
 700
 701   /* Replace the call by a jump to the start of function.  */
 702   e = redirect_edge_and_branch (EDGE_SUCC (t->call_block, 0), first);
 703   gcc_assert (e);
 704   PENDING_STMT (e) = NULL_TREE;
 705
 706   /* Add phi node entries for arguments.  Not every PHI node corresponds to
 707      a function argument (there may be PHI nodes for virtual definitions of the
 708      eliminated calls), so we search for a PHI corresponding to each argument
 709      rather than searching for which argument a PHI node corresponds to.  */
 710
 711   for (param = DECL_ARGUMENTS (current_function_decl),
 712        args = TREE_OPERAND (stmt, 1);
 713        param;
 714        param = TREE_CHAIN (param),
 715        args = TREE_CHAIN (args))
 716     {
 717
 718       for (phi = phi_nodes (first); phi; phi = PHI_CHAIN (phi))
 719         if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
 720           break;
 721
 722       /* The phi node indeed does not have to be there, in case the operand is
 723          invariant in the function.  */
 724       if (!phi)
 725         continue;
 726
 727       add_phi_arg (&phi, TREE_VALUE (args), e);
 728     }
 729
 730   /* Add phi nodes for the call clobbered variables.  */
 731   v_may_defs = V_MAY_DEF_OPS (ann);
 732   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 733     {
 734       param = SSA_NAME_VAR (V_MAY_DEF_RESULT (v_may_defs, i));
 735       for (phi = phi_nodes (first); phi; phi = PHI_CHAIN (phi))
 736         if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
 737           break;
 738
 739       if (!phi)
 740         {
 741           tree name = var_ann (param)->default_def;
 742           tree new_name;
 743
 744           if (!name)
 745             {
 746               /* It may happen that the tag does not have a default_def in case
 747                  when all uses of it are dominated by a MUST_DEF.  This however
 748                  means that it is not necessary to add a phi node for this
 749                  tag.  */
 750               continue;
 751             }
 752           new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
 753
 754           var_ann (param)->default_def = new_name;
 755           phi = create_phi_node (name, first);
 756           SSA_NAME_DEF_STMT (name) = phi;
 757           add_phi_arg (&phi, new_name, EDGE_SUCC (ENTRY_BLOCK_PTR, 0));
 758
 759           /* For all calls the same set of variables should be clobbered.  This
 760              means that there always should be the appropriate phi node except
 761              for the first time we eliminate the call.  */
 762           gcc_assert (EDGE_COUNT (first->preds) <= 2);
 763         }
 764
 765       add_phi_arg (&phi, V_MAY_DEF_OP (v_may_defs, i), e);
 766     }
 767
 768   /* Update the values of accumulators.  */
 769   adjust_accumulator_values (t->call_bsi, t->mult, t->add, e);
 770
 771   call = bsi_stmt (t->call_bsi);
 772   if (TREE_CODE (call) == MODIFY_EXPR)
 773     {
 774       rslt = TREE_OPERAND (call, 0);
 775
 776       /* Result of the call will no longer be defined.  So adjust the
 777          SSA_NAME_DEF_STMT accordingly.  */
 778       SSA_NAME_DEF_STMT (rslt) = build_empty_stmt ();
 779     }
 780
 781   bsi_remove (&t->call_bsi);
 782   release_defs (call);
 783 }
 784
 785 /* Optimizes the tailcall described by T.  If OPT_TAILCALLS is true, also
 786    mark the tailcalls for the sibcall optimization.  */
 787
 788 static bool
 789 optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
 790 {
 791   if (t->tail_recursion)
 792     {
 793       eliminate_tail_call (t);
 794       return true;
 795     }
 796
 797   if (opt_tailcalls)
 798     {
 799       tree stmt = bsi_stmt (t->call_bsi);
 800
 801       stmt = get_call_expr_in (stmt);
 802       CALL_EXPR_TAILCALL (stmt) = 1;
 803       if (dump_file && (dump_flags & TDF_DETAILS))
 804         {
 805           fprintf (dump_file, "Found tail call ");
 806           print_generic_expr (dump_file, stmt, dump_flags);
 807           fprintf (dump_file, " in bb %i\n", t->call_block->index);
 808         }
 809     }
 810
 811   return false;
 812 }
 813
 814 /* Optimizes tail calls in the function, turning the tail recursion
 815    into iteration.  */
 816
 817 static void
 818 tree_optimize_tail_calls_1 (bool opt_tailcalls)
 819 {
 820   edge e;
 821   bool phis_constructed = false;
 822   struct tailcall *tailcalls = NULL, *act, *next;
 823   bool changed = false;
 824   basic_block first = EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest;
 825   tree stmt, param, ret_type, tmp, phi;
 826   edge_iterator ei;
 827
 828   if (!suitable_for_tail_opt_p ())
 829     return;
 830   if (opt_tailcalls)
 831     opt_tailcalls = suitable_for_tail_call_opt_p ();
 832
 833   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 834     {
 835       /* Only traverse the normal exits, i.e. those that end with return
 836          statement.  */
 837       stmt = last_stmt (e->src);
 838
 839       if (stmt
 840           && TREE_CODE (stmt) == RETURN_EXPR)
 841         find_tail_calls (e->src, &tailcalls);
 842     }
 843
 844   /* Construct the phi nodes and accumulators if necessary.  */
 845   a_acc = m_acc = NULL_TREE;
 846   for (act = tailcalls; act; act = act->next)
 847     {
 848       if (!act->tail_recursion)
 849         continue;
 850
 851       if (!phis_constructed)
 852         {
 853           /* Ensure that there is only one predecessor of the block.  */
 854           if (EDGE_COUNT (first->preds) > 1)
 855             first = split_edge (EDGE_SUCC (ENTRY_BLOCK_PTR, 0));
 856
 857           /* Copy the args if needed.  */
 858           for (param = DECL_ARGUMENTS (current_function_decl);
 859                param;
 860                param = TREE_CHAIN (param))
 861             if (var_ann (param)
 862                 /* Also parameters that are only defined but never used need not
 863                    be copied.  */
 864                 && (var_ann (param)->default_def
 865                     && TREE_CODE (var_ann (param)->default_def) == SSA_NAME))
 866             {
 867               tree name = var_ann (param)->default_def;
 868               tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
 869               tree phi;
 870
 871               var_ann (param)->default_def = new_name;
 872               phi = create_phi_node (name, first);
 873               SSA_NAME_DEF_STMT (name) = phi;
 874               add_phi_arg (&phi, new_name, EDGE_PRED (first, 0));
 875             }
 876           phis_constructed = true;
 877         }
 878
 879       if (act->add && !a_acc)
 880         {
 881           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 882
 883           tmp = create_tmp_var (ret_type, "add_acc");
 884           add_referenced_tmp_var (tmp);
 885
 886           phi = create_phi_node (tmp, first);
 887           add_phi_arg (&phi, build_int_cst (ret_type, 0), EDGE_PRED (first, 0));
 888           a_acc = PHI_RESULT (phi);
 889         }
 890
 891       if (act->mult && !m_acc)
 892         {
 893           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 894
 895           tmp = create_tmp_var (ret_type, "mult_acc");
 896           add_referenced_tmp_var (tmp);
 897
 898           phi = create_phi_node (tmp, first);
 899           add_phi_arg (&phi, build_int_cst (ret_type, 1), EDGE_PRED (first, 0));
 900           m_acc = PHI_RESULT (phi);
 901         }
 902     }
 903
 904   for (; tailcalls; tailcalls = next)
 905     {
 906       next = tailcalls->next;
 907       changed |= optimize_tail_call (tailcalls, opt_tailcalls);
 908       free (tailcalls);
 909     }
 910
 911   if (a_acc || m_acc)
 912     {
 913       /* Modify the remaining return statements.  */
 914       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 915         {
 916           stmt = last_stmt (e->src);
 917
 918           if (stmt
 919               && TREE_CODE (stmt) == RETURN_EXPR)
 920             adjust_return_value (e->src, m_acc, a_acc);
 921         }
 922     }
 923
 924   if (changed)
 925     {
 926       free_dominance_info (CDI_DOMINATORS);
 927       cleanup_tree_cfg ();
 928     }
 929 }
 930
 931 static void
 932 execute_tail_recursion (void)
 933 {
 934   tree_optimize_tail_calls_1 (false);
 935 }
 936
 937 static bool
 938 gate_tail_calls (void)
 939 {
 940   return flag_optimize_sibling_calls != 0;
 941 }
 942
 943 static void
 944 execute_tail_calls (void)
 945 {
 946   tree_optimize_tail_calls_1 (true);
 947 }
 948
 949 struct tree_opt_pass pass_tail_recursion =
 950 {
 951   "tailr",                              /* name */
 952   NULL,                                 /* gate */
 953   execute_tail_recursion,               /* execute */
 954   NULL,                                 /* sub */
 955   NULL,                                 /* next */
 956   0,                                    /* static_pass_number */
 957   0,                                    /* tv_id */
 958   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 959   0,                                    /* properties_provided */
 960   0,                                    /* properties_destroyed */
 961   0,                                    /* todo_flags_start */
 962   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
 963   0                                     /* letter */
 964 };
 965
 966 struct tree_opt_pass pass_tail_calls =
 967 {
 968   "tailc",                              /* name */
 969   gate_tail_calls,                      /* gate */
 970   execute_tail_calls,                   /* execute */
 971   NULL,                                 /* sub */
 972   NULL,                                 /* next */
 973   0,                                    /* static_pass_number */
 974   0,                                    /* tv_id */
 975   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 976   0,                                    /* properties_provided */
 977   0,                                    /* properties_destroyed */
 978   0,                                    /* todo_flags_start */
 979   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
 980   0                                     /* letter */
 981 };