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