gcc/tree-tailcall.c

   1 /* Tail call optimization on trees.
   2    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  19 Boston, MA 02110-1301, 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   referenced_var_iterator rvi;
 136   tree var;
 137
 138   if (current_function_stdarg)
 139     return false;
 140
 141   /* No local variable nor structure field should be call-clobbered.  We
 142      ignore any kind of memory tag, as these are not real variables.  */
 143
 144   FOR_EACH_REFERENCED_VAR (var, rvi)
 145     {
 146       if (!is_global_var (var)
 147           && (!MTAG_P (var) || TREE_CODE (var) == STRUCT_FIELD_TAG)
 148           && (gimple_aliases_computed_p (cfun) ? is_call_clobbered (var)
 149               : TREE_ADDRESSABLE (var)))
 150         return false;
 151     }
 152
 153   return true;
 154 }
 155 /* Returns false when the function is not suitable for tail call optimization
 156    from some reason (e.g. if it takes variable number of arguments).
 157    This test must pass in addition to suitable_for_tail_opt_p in order to make
 158    tail call discovery happen.  */
 159
 160 static bool
 161 suitable_for_tail_call_opt_p (void)
 162 {
 163   tree param;
 164
 165   /* alloca (until we have stack slot life analysis) inhibits
 166      sibling call optimizations, but not tail recursion.  */
 167   if (current_function_calls_alloca)
 168     return false;
 169
 170   /* If we are using sjlj exceptions, we may need to add a call to
 171      _Unwind_SjLj_Unregister at exit of the function.  Which means
 172      that we cannot do any sibcall transformations.  */
 173   if (USING_SJLJ_EXCEPTIONS && current_function_has_exception_handlers ())
 174     return false;
 175
 176   /* Any function that calls setjmp might have longjmp called from
 177      any called function.  ??? We really should represent this
 178      properly in the CFG so that this needn't be special cased.  */
 179   if (current_function_calls_setjmp)
 180     return false;
 181
 182   /* ??? It is OK if the argument of a function is taken in some cases,
 183      but not in all cases.  See PR15387 and PR19616.  Revisit for 4.1.  */
 184   for (param = DECL_ARGUMENTS (current_function_decl);
 185        param;
 186        param = TREE_CHAIN (param))
 187     if (TREE_ADDRESSABLE (param))
 188       return false;
 189
 190   return true;
 191 }
 192
 193 /* Checks whether the expression EXPR in stmt AT is independent of the
 194    statement pointed to by BSI (in a sense that we already know EXPR's value
 195    at BSI).  We use the fact that we are only called from the chain of
 196    basic blocks that have only single successor.  Returns the expression
 197    containing the value of EXPR at BSI.  */
 198
 199 static tree
 200 independent_of_stmt_p (tree expr, tree at, block_stmt_iterator bsi)
 201 {
 202   basic_block bb, call_bb, at_bb;
 203   edge e;
 204   edge_iterator ei;
 205
 206   if (is_gimple_min_invariant (expr))
 207     return expr;
 208
 209   if (TREE_CODE (expr) != SSA_NAME)
 210     return NULL_TREE;
 211
 212   /* Mark the blocks in the chain leading to the end.  */
 213   at_bb = bb_for_stmt (at);
 214   call_bb = bb_for_stmt (bsi_stmt (bsi));
 215   for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
 216     bb->aux = &bb->aux;
 217   bb->aux = &bb->aux;
 218
 219   while (1)
 220     {
 221       at = SSA_NAME_DEF_STMT (expr);
 222       bb = bb_for_stmt (at);
 223
 224       /* The default definition or defined before the chain.  */
 225       if (!bb || !bb->aux)
 226         break;
 227
 228       if (bb == call_bb)
 229         {
 230           for (; !bsi_end_p (bsi); bsi_next (&bsi))
 231             if (bsi_stmt (bsi) == at)
 232               break;
 233
 234           if (!bsi_end_p (bsi))
 235             expr = NULL_TREE;
 236           break;
 237         }
 238
 239       if (TREE_CODE (at) != PHI_NODE)
 240         {
 241           expr = NULL_TREE;
 242           break;
 243         }
 244
 245       FOR_EACH_EDGE (e, ei, bb->preds)
 246         if (e->src->aux)
 247           break;
 248       gcc_assert (e);
 249
 250       expr = PHI_ARG_DEF_FROM_EDGE (at, e);
 251       if (TREE_CODE (expr) != SSA_NAME)
 252         {
 253           /* The value is a constant.  */
 254           break;
 255         }
 256     }
 257
 258   /* Unmark the blocks.  */
 259   for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
 260     bb->aux = NULL;
 261   bb->aux = NULL;
 262
 263   return expr;
 264 }
 265
 266 /* Simulates the effect of an assignment of ASS in STMT on the return value
 267    of the tail recursive CALL passed in ASS_VAR.  M and A are the
 268    multiplicative and the additive factor for the real return value.  */
 269
 270 static bool
 271 process_assignment (tree ass, tree stmt, block_stmt_iterator call, tree *m,
 272                     tree *a, tree *ass_var)
 273 {
 274   tree op0, op1, non_ass_var;
 275   tree dest = GIMPLE_STMT_OPERAND (ass, 0);
 276   tree src = GIMPLE_STMT_OPERAND (ass, 1);
 277   enum tree_code code = TREE_CODE (src);
 278   tree src_var = src;
 279
 280   /* See if this is a simple copy operation of an SSA name to the function
 281      result.  In that case we may have a simple tail call.  Ignore type
 282      conversions that can never produce extra code between the function
 283      call and the function return.  */
 284   STRIP_NOPS (src_var);
 285   if (TREE_CODE (src_var) == SSA_NAME)
 286     {
 287       if (src_var != *ass_var)
 288         return false;
 289
 290       *ass_var = dest;
 291       return true;
 292     }
 293
 294   if (TREE_CODE_CLASS (code) != tcc_binary)
 295     return false;
 296
 297   /* Accumulator optimizations will reverse the order of operations.
 298      We can only do that for floating-point types if we're assuming
 299      that addition and multiplication are associative.  */
 300   if (!flag_unsafe_math_optimizations)
 301     if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
 302       return false;
 303
 304   /* We only handle the code like
 305
 306      x = call ();
 307      y = m * x;
 308      z = y + a;
 309      return z;
 310
 311      TODO -- Extend it for cases where the linear transformation of the output
 312      is expressed in a more complicated way.  */
 313
 314   op0 = TREE_OPERAND (src, 0);
 315   op1 = TREE_OPERAND (src, 1);
 316
 317   if (op0 == *ass_var
 318       && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
 319     ;
 320   else if (op1 == *ass_var
 321            && (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
 322     ;
 323   else
 324     return false;
 325
 326   switch (code)
 327     {
 328     case PLUS_EXPR:
 329       /* There should be no previous addition.  TODO -- it should be fairly
 330          straightforward to lift this restriction -- just allow storing
 331          more complicated expressions in *A, and gimplify it in
 332          adjust_accumulator_values.  */
 333       if (*a)
 334         return false;
 335       *a = non_ass_var;
 336       *ass_var = dest;
 337       return true;
 338
 339     case MULT_EXPR:
 340       /* Similar remark applies here.  Handling multiplication after addition
 341          is just slightly more complicated -- we need to multiply both *A and
 342          *M.  */
 343       if (*a || *m)
 344         return false;
 345       *m = non_ass_var;
 346       *ass_var = dest;
 347       return true;
 348
 349       /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR).  */
 350
 351     default:
 352       return false;
 353     }
 354 }
 355
 356 /* Propagate VAR through phis on edge E.  */
 357
 358 static tree
 359 propagate_through_phis (tree var, edge e)
 360 {
 361   basic_block dest = e->dest;
 362   tree phi;
 363
 364   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
 365     if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
 366       return PHI_RESULT (phi);
 367
 368   return var;
 369 }
 370
 371 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
 372    added to the start of RET.  */
 373
 374 static void
 375 find_tail_calls (basic_block bb, struct tailcall **ret)
 376 {
 377   tree ass_var, ret_var, stmt, func, param, args, call = NULL_TREE;
 378   block_stmt_iterator bsi, absi;
 379   bool tail_recursion;
 380   struct tailcall *nw;
 381   edge e;
 382   tree m, a;
 383   basic_block abb;
 384   stmt_ann_t ann;
 385
 386   if (!single_succ_p (bb))
 387     return;
 388
 389   for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
 390     {
 391       stmt = bsi_stmt (bsi);
 392
 393       /* Ignore labels.  */
 394       if (TREE_CODE (stmt) == LABEL_EXPR)
 395         continue;
 396
 397       /* Check for a call.  */
 398       if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 399         {
 400           ass_var = GIMPLE_STMT_OPERAND (stmt, 0);
 401           call = GIMPLE_STMT_OPERAND (stmt, 1);
 402           if (TREE_CODE (call) == WITH_SIZE_EXPR)
 403             call = TREE_OPERAND (call, 0);
 404         }
 405       else
 406         {
 407           ass_var = NULL_TREE;
 408           call = stmt;
 409         }
 410
 411       if (TREE_CODE (call) == CALL_EXPR)
 412         break;
 413
 414       /* If the statement has virtual or volatile operands, fail.  */
 415       ann = stmt_ann (stmt);
 416       if (!ZERO_SSA_OPERANDS (stmt, (SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS))
 417           || ann->has_volatile_ops)
 418         return;
 419     }
 420
 421   if (bsi_end_p (bsi))
 422     {
 423       edge_iterator ei;
 424       /* Recurse to the predecessors.  */
 425       FOR_EACH_EDGE (e, ei, bb->preds)
 426         find_tail_calls (e->src, ret);
 427
 428       return;
 429     }
 430
 431   /* We found the call, check whether it is suitable.  */
 432   tail_recursion = false;
 433   func = get_callee_fndecl (call);
 434   if (func == current_function_decl)
 435     {
 436       for (param = DECL_ARGUMENTS (func), args = TREE_OPERAND (call, 1);
 437            param && args;
 438            param = TREE_CHAIN (param), args = TREE_CHAIN (args))
 439         {
 440           tree arg = TREE_VALUE (args);
 441           if (param != arg)
 442             {
 443               /* Make sure there are no problems with copying.  The parameter
 444                  have a copyable type and the two arguments must have reasonably
 445                  equivalent types.  The latter requirement could be relaxed if
 446                  we emitted a suitable type conversion statement.  */
 447               if (!is_gimple_reg_type (TREE_TYPE (param))
 448                   || !lang_hooks.types_compatible_p (TREE_TYPE (param),
 449                                                      TREE_TYPE (arg)))
 450                 break;
 451
 452               /* The parameter should be a real operand, so that phi node
 453                  created for it at the start of the function has the meaning
 454                  of copying the value.  This test implies is_gimple_reg_type
 455                  from the previous condition, however this one could be
 456                  relaxed by being more careful with copying the new value
 457                  of the parameter (emitting appropriate GIMPLE_MODIFY_STMT and
 458                  updating the virtual operands).  */
 459               if (!is_gimple_reg (param))
 460                 break;
 461             }
 462         }
 463       if (!args && !param)
 464         tail_recursion = true;
 465     }
 466
 467   /* Now check the statements after the call.  None of them has virtual
 468      operands, so they may only depend on the call through its return
 469      value.  The return value should also be dependent on each of them,
 470      since we are running after dce.  */
 471   m = NULL_TREE;
 472   a = NULL_TREE;
 473
 474   abb = bb;
 475   absi = bsi;
 476   while (1)
 477     {
 478       bsi_next (&absi);
 479
 480       while (bsi_end_p (absi))
 481         {
 482           ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
 483           abb = single_succ (abb);
 484           absi = bsi_start (abb);
 485         }
 486
 487       stmt = bsi_stmt (absi);
 488
 489       if (TREE_CODE (stmt) == LABEL_EXPR)
 490         continue;
 491
 492       if (TREE_CODE (stmt) == RETURN_EXPR)
 493         break;
 494
 495       if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
 496         return;
 497
 498       if (!process_assignment (stmt, stmt, bsi, &m, &a, &ass_var))
 499         return;
 500     }
 501
 502   /* See if this is a tail call we can handle.  */
 503   ret_var = TREE_OPERAND (stmt, 0);
 504   if (ret_var
 505       && TREE_CODE (ret_var) == GIMPLE_MODIFY_STMT)
 506     {
 507       tree ret_op = GIMPLE_STMT_OPERAND (ret_var, 1);
 508       STRIP_NOPS (ret_op);
 509       if (!tail_recursion
 510           && TREE_CODE (ret_op) != SSA_NAME)
 511         return;
 512
 513       if (!process_assignment (ret_var, stmt, bsi, &m, &a, &ass_var))
 514         return;
 515       ret_var = GIMPLE_STMT_OPERAND (ret_var, 0);
 516     }
 517
 518   /* We may proceed if there either is no return value, or the return value
 519      is identical to the call's return.  */
 520   if (ret_var
 521       && (ret_var != ass_var))
 522     return;
 523
 524   /* If this is not a tail recursive call, we cannot handle addends or
 525      multiplicands.  */
 526   if (!tail_recursion && (m || a))
 527     return;
 528
 529   nw = XNEW (struct tailcall);
 530
 531   nw->call_block = bb;
 532   nw->call_bsi = bsi;
 533
 534   nw->tail_recursion = tail_recursion;
 535
 536   nw->mult = m;
 537   nw->add = a;
 538
 539   nw->next = *ret;
 540   *ret = nw;
 541 }
 542
 543 /* Adjust the accumulator values according to A and M after BSI, and update
 544    the phi nodes on edge BACK.  */
 545
 546 static void
 547 adjust_accumulator_values (block_stmt_iterator bsi, tree m, tree a, edge back)
 548 {
 549   tree stmt, var, phi, tmp;
 550   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 551   tree a_acc_arg = a_acc, m_acc_arg = m_acc;
 552
 553   if (a)
 554     {
 555       if (m_acc)
 556         {
 557           if (integer_onep (a))
 558             var = m_acc;
 559           else
 560             {
 561               stmt = build2 (GIMPLE_MODIFY_STMT, ret_type, NULL_TREE,
 562                              build2 (MULT_EXPR, ret_type, m_acc, a));
 563
 564               tmp = create_tmp_var (ret_type, "acc_tmp");
 565               add_referenced_var (tmp);
 566
 567               var = make_ssa_name (tmp, stmt);
 568               GIMPLE_STMT_OPERAND (stmt, 0) = var;
 569               bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 570             }
 571         }
 572       else
 573         var = a;
 574
 575       stmt = build2 (GIMPLE_MODIFY_STMT, ret_type, NULL_TREE,
 576                      build2 (PLUS_EXPR, ret_type, a_acc, var));
 577       var = make_ssa_name (SSA_NAME_VAR (a_acc), stmt);
 578       GIMPLE_STMT_OPERAND (stmt, 0) = var;
 579       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 580       a_acc_arg = var;
 581     }
 582
 583   if (m)
 584     {
 585       stmt = build2 (GIMPLE_MODIFY_STMT, ret_type, NULL_TREE,
 586                      build2 (MULT_EXPR, ret_type, m_acc, m));
 587       var = make_ssa_name (SSA_NAME_VAR (m_acc), stmt);
 588       GIMPLE_STMT_OPERAND (stmt, 0) = var;
 589       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 590       m_acc_arg = var;
 591     }
 592
 593   if (a_acc)
 594     {
 595       for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
 596         if (PHI_RESULT (phi) == a_acc)
 597           break;
 598
 599       add_phi_arg (phi, a_acc_arg, back);
 600     }
 601
 602   if (m_acc)
 603     {
 604       for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
 605         if (PHI_RESULT (phi) == m_acc)
 606           break;
 607
 608       add_phi_arg (phi, m_acc_arg, back);
 609     }
 610 }
 611
 612 /* Adjust value of the return at the end of BB according to M and A
 613    accumulators.  */
 614
 615 static void
 616 adjust_return_value (basic_block bb, tree m, tree a)
 617 {
 618   tree ret_stmt = last_stmt (bb), ret_var, var, stmt, tmp;
 619   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 620   tree *ret_op;
 621   block_stmt_iterator bsi = bsi_last (bb);
 622
 623   gcc_assert (TREE_CODE (ret_stmt) == RETURN_EXPR);
 624
 625   ret_var = TREE_OPERAND (ret_stmt, 0);
 626   if (!ret_var)
 627     return;
 628
 629   if (TREE_CODE (ret_var) == GIMPLE_MODIFY_STMT)
 630     {
 631       ret_op = &GIMPLE_STMT_OPERAND (ret_var, 1);
 632       ret_var = *ret_op;
 633     }
 634   else
 635     ret_op = &TREE_OPERAND (ret_stmt, 0);
 636
 637   if (m)
 638     {
 639       stmt = build2 (GIMPLE_MODIFY_STMT, ret_type, NULL_TREE,
 640                      build2 (MULT_EXPR, ret_type, m_acc, ret_var));
 641
 642       tmp = create_tmp_var (ret_type, "acc_tmp");
 643       add_referenced_var (tmp);
 644
 645       var = make_ssa_name (tmp, stmt);
 646       GIMPLE_STMT_OPERAND (stmt, 0) = var;
 647       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 648     }
 649   else
 650     var = ret_var;
 651
 652   if (a)
 653     {
 654       stmt = build2 (GIMPLE_MODIFY_STMT, ret_type, NULL_TREE,
 655                      build2 (PLUS_EXPR, ret_type, a_acc, var));
 656
 657       tmp = create_tmp_var (ret_type, "acc_tmp");
 658       add_referenced_var (tmp);
 659
 660       var = make_ssa_name (tmp, stmt);
 661       GIMPLE_STMT_OPERAND (stmt, 0) = var;
 662       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 663     }
 664
 665   *ret_op = var;
 666   update_stmt (ret_stmt);
 667 }
 668
 669 /* Subtract COUNT and FREQUENCY from the basic block and it's
 670    outgoing edge.  */
 671 static void
 672 decrease_profile (basic_block bb, gcov_type count, int frequency)
 673 {
 674   edge e;
 675   bb->count -= count;
 676   if (bb->count < 0)
 677     bb->count = 0;
 678   bb->frequency -= frequency;
 679   if (bb->frequency < 0)
 680     bb->frequency = 0;
 681   if (!single_succ_p (bb))
 682     {
 683       gcc_assert (!EDGE_COUNT (bb->succs));
 684       return;
 685     }
 686   e = single_succ_edge (bb);
 687   e->count -= count;
 688   if (e->count < 0)
 689     e->count = 0;
 690 }
 691
 692 /* Returns true if argument PARAM of the tail recursive call needs to be copied
 693    when the call is eliminated.  */
 694
 695 static bool
 696 arg_needs_copy_p (tree param)
 697 {
 698   tree def;
 699
 700   if (!is_gimple_reg (param) || !var_ann (param))
 701     return false;
 702
 703   /* Parameters that are only defined but never used need not be copied.  */
 704   def = gimple_default_def (cfun, param);
 705   if (!def)
 706     return false;
 707
 708   return true;
 709 }
 710
 711 /* Eliminates tail call described by T.  TMP_VARS is a list of
 712    temporary variables used to copy the function arguments.  */
 713
 714 static void
 715 eliminate_tail_call (struct tailcall *t)
 716 {
 717   tree param, stmt, args, rslt, call;
 718   basic_block bb, first;
 719   edge e;
 720   tree phi;
 721   block_stmt_iterator bsi;
 722   tree orig_stmt;
 723
 724   stmt = orig_stmt = bsi_stmt (t->call_bsi);
 725   bb = t->call_block;
 726
 727   if (dump_file && (dump_flags & TDF_DETAILS))
 728     {
 729       fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
 730                bb->index);
 731       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 732       fprintf (dump_file, "\n");
 733     }
 734
 735   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 736     stmt = GIMPLE_STMT_OPERAND (stmt, 1);
 737
 738   first = single_succ (ENTRY_BLOCK_PTR);
 739
 740   /* Remove the code after call_bsi that will become unreachable.  The
 741      possibly unreachable code in other blocks is removed later in
 742      cfg cleanup.  */
 743   bsi = t->call_bsi;
 744   bsi_next (&bsi);
 745   while (!bsi_end_p (bsi))
 746     {
 747       tree t = bsi_stmt (bsi);
 748       /* Do not remove the return statement, so that redirect_edge_and_branch
 749          sees how the block ends.  */
 750       if (TREE_CODE (t) == RETURN_EXPR)
 751         break;
 752
 753       bsi_remove (&bsi, true);
 754       release_defs (t);
 755     }
 756
 757   /* Number of executions of function has reduced by the tailcall.  */
 758   e = single_succ_edge (t->call_block);
 759   decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
 760   decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
 761   if (e->dest != EXIT_BLOCK_PTR)
 762     decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
 763
 764   /* Replace the call by a jump to the start of function.  */
 765   e = redirect_edge_and_branch (single_succ_edge (t->call_block), first);
 766   gcc_assert (e);
 767   PENDING_STMT (e) = NULL_TREE;
 768
 769   /* Add phi node entries for arguments.  The ordering of the phi nodes should
 770      be the same as the ordering of the arguments.  */
 771   for (param = DECL_ARGUMENTS (current_function_decl),
 772        args = TREE_OPERAND (stmt, 1),
 773        phi = phi_nodes (first);
 774        param;
 775        param = TREE_CHAIN (param),
 776        args = TREE_CHAIN (args))
 777     {
 778       if (!arg_needs_copy_p (param))
 779         continue;
 780       gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
 781
 782       add_phi_arg (phi, TREE_VALUE (args), e);
 783       phi = PHI_CHAIN (phi);
 784     }
 785
 786   /* Update the values of accumulators.  */
 787   adjust_accumulator_values (t->call_bsi, t->mult, t->add, e);
 788
 789   call = bsi_stmt (t->call_bsi);
 790   if (TREE_CODE (call) == GIMPLE_MODIFY_STMT)
 791     {
 792       rslt = GIMPLE_STMT_OPERAND (call, 0);
 793
 794       /* Result of the call will no longer be defined.  So adjust the
 795          SSA_NAME_DEF_STMT accordingly.  */
 796       SSA_NAME_DEF_STMT (rslt) = build_empty_stmt ();
 797     }
 798
 799   bsi_remove (&t->call_bsi, true);
 800   release_defs (call);
 801 }
 802
 803 /* Add phi nodes for the virtual operands defined in the function to the
 804    header of the loop created by tail recursion elimination.
 805
 806    Originally, we used to add phi nodes only for call clobbered variables,
 807    as the value of the non-call clobbered ones obviously cannot be used
 808    or changed within the recursive call.  However, the local variables
 809    from multiple calls now share the same location, so the virtual ssa form
 810    requires us to say that the location dies on further iterations of the loop,
 811    which requires adding phi nodes.
 812 */
 813 static void
 814 add_virtual_phis (void)
 815 {
 816   referenced_var_iterator rvi;
 817   tree var;
 818
 819   /* The problematic part is that there is no way how to know what
 820      to put into phi nodes (there in fact does not have to be such
 821      ssa name available).  A solution would be to have an artificial
 822      use/kill for all virtual operands in EXIT node.  Unless we have
 823      this, we cannot do much better than to rebuild the ssa form for
 824      possibly affected virtual ssa names from scratch.  */
 825
 826   FOR_EACH_REFERENCED_VAR (var, rvi)
 827     {
 828       if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE)
 829         mark_sym_for_renaming (var);
 830     }
 831 }
 832
 833 /* Optimizes the tailcall described by T.  If OPT_TAILCALLS is true, also
 834    mark the tailcalls for the sibcall optimization.  */
 835
 836 static bool
 837 optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
 838 {
 839   if (t->tail_recursion)
 840     {
 841       eliminate_tail_call (t);
 842       return true;
 843     }
 844
 845   if (opt_tailcalls)
 846     {
 847       tree stmt = bsi_stmt (t->call_bsi);
 848
 849       stmt = get_call_expr_in (stmt);
 850       CALL_EXPR_TAILCALL (stmt) = 1;
 851       if (dump_file && (dump_flags & TDF_DETAILS))
 852         {
 853           fprintf (dump_file, "Found tail call ");
 854           print_generic_expr (dump_file, stmt, dump_flags);
 855           fprintf (dump_file, " in bb %i\n", t->call_block->index);
 856         }
 857     }
 858
 859   return false;
 860 }
 861
 862 /* Optimizes tail calls in the function, turning the tail recursion
 863    into iteration.  */
 864
 865 static unsigned int
 866 tree_optimize_tail_calls_1 (bool opt_tailcalls)
 867 {
 868   edge e;
 869   bool phis_constructed = false;
 870   struct tailcall *tailcalls = NULL, *act, *next;
 871   bool changed = false;
 872   basic_block first = single_succ (ENTRY_BLOCK_PTR);
 873   tree stmt, param, ret_type, tmp, phi;
 874   edge_iterator ei;
 875
 876   if (!suitable_for_tail_opt_p ())
 877     return 0;
 878   if (opt_tailcalls)
 879     opt_tailcalls = suitable_for_tail_call_opt_p ();
 880
 881   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 882     {
 883       /* Only traverse the normal exits, i.e. those that end with return
 884          statement.  */
 885       stmt = last_stmt (e->src);
 886
 887       if (stmt
 888           && TREE_CODE (stmt) == RETURN_EXPR)
 889         find_tail_calls (e->src, &tailcalls);
 890     }
 891
 892   /* Construct the phi nodes and accumulators if necessary.  */
 893   a_acc = m_acc = NULL_TREE;
 894   for (act = tailcalls; act; act = act->next)
 895     {
 896       if (!act->tail_recursion)
 897         continue;
 898
 899       if (!phis_constructed)
 900         {
 901           /* Ensure that there is only one predecessor of the block.  */
 902           if (!single_pred_p (first))
 903             first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
 904
 905           /* Copy the args if needed.  */
 906           for (param = DECL_ARGUMENTS (current_function_decl);
 907                param;
 908                param = TREE_CHAIN (param))
 909             if (arg_needs_copy_p (param))
 910               {
 911                 tree name = gimple_default_def (cfun, param);
 912                 tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
 913                 tree phi;
 914
 915                 set_default_def (param, new_name);
 916                 phi = create_phi_node (name, first);
 917                 SSA_NAME_DEF_STMT (name) = phi;
 918                 add_phi_arg (phi, new_name, single_pred_edge (first));
 919               }
 920           phis_constructed = true;
 921         }
 922
 923       if (act->add && !a_acc)
 924         {
 925           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 926
 927           tmp = create_tmp_var (ret_type, "add_acc");
 928           add_referenced_var (tmp);
 929
 930           phi = create_phi_node (tmp, first);
 931           add_phi_arg (phi,
 932                        /* RET_TYPE can be a float when -ffast-maths is
 933                           enabled.  */
 934                        fold_convert (ret_type, integer_zero_node),
 935                        single_pred_edge (first));
 936           a_acc = PHI_RESULT (phi);
 937         }
 938
 939       if (act->mult && !m_acc)
 940         {
 941           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 942
 943           tmp = create_tmp_var (ret_type, "mult_acc");
 944           add_referenced_var (tmp);
 945
 946           phi = create_phi_node (tmp, first);
 947           add_phi_arg (phi,
 948                        /* RET_TYPE can be a float when -ffast-maths is
 949                           enabled.  */
 950                        fold_convert (ret_type, integer_one_node),
 951                        single_pred_edge (first));
 952           m_acc = PHI_RESULT (phi);
 953         }
 954     }
 955
 956
 957   if (phis_constructed)
 958     {
 959       /* Reverse the order of the phi nodes, so that it matches the order
 960          of operands of the function, as assumed by eliminate_tail_call.  */
 961       set_phi_nodes (first, phi_reverse (phi_nodes (first)));
 962     }
 963
 964   for (; tailcalls; tailcalls = next)
 965     {
 966       next = tailcalls->next;
 967       changed |= optimize_tail_call (tailcalls, opt_tailcalls);
 968       free (tailcalls);
 969     }
 970
 971   if (a_acc || m_acc)
 972     {
 973       /* Modify the remaining return statements.  */
 974       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 975         {
 976           stmt = last_stmt (e->src);
 977
 978           if (stmt
 979               && TREE_CODE (stmt) == RETURN_EXPR)
 980             adjust_return_value (e->src, m_acc, a_acc);
 981         }
 982     }
 983
 984   if (changed)
 985     free_dominance_info (CDI_DOMINATORS);
 986
 987   if (phis_constructed)
 988     add_virtual_phis ();
 989   if (changed)
 990     return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
 991   return 0;
 992 }
 993
 994 static unsigned int
 995 execute_tail_recursion (void)
 996 {
 997   return tree_optimize_tail_calls_1 (false);
 998 }
 999
1000 static bool
1001 gate_tail_calls (void)
1002 {
1003   return flag_optimize_sibling_calls != 0;
1004 }
1005
1006 static unsigned int
1007 execute_tail_calls (void)
1008 {
1009   return tree_optimize_tail_calls_1 (true);
1010 }
1011
1012 struct tree_opt_pass pass_tail_recursion =
1013 {
1014   "tailr",                              /* name */
1015   gate_tail_calls,                      /* gate */
1016   execute_tail_recursion,               /* execute */
1017   NULL,                                 /* sub */
1018   NULL,                                 /* next */
1019   0,                                    /* static_pass_number */
1020   0,                                    /* tv_id */
1021   PROP_cfg | PROP_ssa,                  /* properties_required */
1022   0,                                    /* properties_provided */
1023   0,                                    /* properties_destroyed */
1024   0,                                    /* todo_flags_start */
1025   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
1026   0                                     /* letter */
1027 };
1028
1029 struct tree_opt_pass pass_tail_calls =
1030 {
1031   "tailc",                              /* name */
1032   gate_tail_calls,                      /* gate */
1033   execute_tail_calls,                   /* execute */
1034   NULL,                                 /* sub */
1035   NULL,                                 /* next */
1036   0,                                    /* static_pass_number */
1037   0,                                    /* tv_id */
1038   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1039   0,                                    /* properties_provided */
1040   0,                                    /* properties_destroyed */
1041   0,                                    /* todo_flags_start */
1042   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
1043   0                                     /* letter */
1044 };