gcc/tree-tailcall.c

   1 /* Tail call optimization on trees.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007 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, 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       call_expr_arg_iterator iter;
 437       tree arg;
 438       for (param = DECL_ARGUMENTS (func),
 439              arg = first_call_expr_arg (call, &iter);
 440            param && arg;
 441            param = TREE_CHAIN (param), arg = next_call_expr_arg (&iter))
 442         {
 443           if (param != arg)
 444             {
 445               /* Make sure there are no problems with copying.  The parameter
 446                  have a copyable type and the two arguments must have reasonably
 447                  equivalent types.  The latter requirement could be relaxed if
 448                  we emitted a suitable type conversion statement.  */
 449               if (!is_gimple_reg_type (TREE_TYPE (param))
 450                   || !lang_hooks.types_compatible_p (TREE_TYPE (param),
 451                                                      TREE_TYPE (arg)))
 452                 break;
 453
 454               /* The parameter should be a real operand, so that phi node
 455                  created for it at the start of the function has the meaning
 456                  of copying the value.  This test implies is_gimple_reg_type
 457                  from the previous condition, however this one could be
 458                  relaxed by being more careful with copying the new value
 459                  of the parameter (emitting appropriate GIMPLE_MODIFY_STMT and
 460                  updating the virtual operands).  */
 461               if (!is_gimple_reg (param))
 462                 break;
 463             }
 464         }
 465       if (!arg && !param)
 466         tail_recursion = true;
 467     }
 468
 469   /* Now check the statements after the call.  None of them has virtual
 470      operands, so they may only depend on the call through its return
 471      value.  The return value should also be dependent on each of them,
 472      since we are running after dce.  */
 473   m = NULL_TREE;
 474   a = NULL_TREE;
 475
 476   abb = bb;
 477   absi = bsi;
 478   while (1)
 479     {
 480       bsi_next (&absi);
 481
 482       while (bsi_end_p (absi))
 483         {
 484           ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
 485           abb = single_succ (abb);
 486           absi = bsi_start (abb);
 487         }
 488
 489       stmt = bsi_stmt (absi);
 490
 491       if (TREE_CODE (stmt) == LABEL_EXPR)
 492         continue;
 493
 494       if (TREE_CODE (stmt) == RETURN_EXPR)
 495         break;
 496
 497       if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
 498         return;
 499
 500       if (!process_assignment (stmt, stmt, bsi, &m, &a, &ass_var))
 501         return;
 502     }
 503
 504   /* See if this is a tail call we can handle.  */
 505   ret_var = TREE_OPERAND (stmt, 0);
 506   if (ret_var
 507       && TREE_CODE (ret_var) == GIMPLE_MODIFY_STMT)
 508     {
 509       tree ret_op = GIMPLE_STMT_OPERAND (ret_var, 1);
 510       STRIP_NOPS (ret_op);
 511       if (!tail_recursion
 512           && TREE_CODE (ret_op) != SSA_NAME)
 513         return;
 514
 515       if (!process_assignment (ret_var, stmt, bsi, &m, &a, &ass_var))
 516         return;
 517       ret_var = GIMPLE_STMT_OPERAND (ret_var, 0);
 518     }
 519
 520   /* We may proceed if there either is no return value, or the return value
 521      is identical to the call's return.  */
 522   if (ret_var
 523       && (ret_var != ass_var))
 524     return;
 525
 526   /* If this is not a tail recursive call, we cannot handle addends or
 527      multiplicands.  */
 528   if (!tail_recursion && (m || a))
 529     return;
 530
 531   nw = XNEW (struct tailcall);
 532
 533   nw->call_block = bb;
 534   nw->call_bsi = bsi;
 535
 536   nw->tail_recursion = tail_recursion;
 537
 538   nw->mult = m;
 539   nw->add = a;
 540
 541   nw->next = *ret;
 542   *ret = nw;
 543 }
 544
 545 /* Adjust the accumulator values according to A and M after BSI, and update
 546    the phi nodes on edge BACK.  */
 547
 548 static void
 549 adjust_accumulator_values (block_stmt_iterator bsi, tree m, tree a, edge back)
 550 {
 551   tree stmt, var, phi, tmp;
 552   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 553   tree a_acc_arg = a_acc, m_acc_arg = m_acc;
 554
 555   if (a)
 556     {
 557       if (m_acc)
 558         {
 559           if (integer_onep (a))
 560             var = m_acc;
 561           else
 562             {
 563               stmt = build_gimple_modify_stmt (NULL_TREE,
 564                                                build2 (MULT_EXPR, ret_type,
 565                                                        m_acc, a));
 566
 567               tmp = create_tmp_var (ret_type, "acc_tmp");
 568               add_referenced_var (tmp);
 569
 570               var = make_ssa_name (tmp, stmt);
 571               GIMPLE_STMT_OPERAND (stmt, 0) = var;
 572               bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 573             }
 574         }
 575       else
 576         var = a;
 577
 578       stmt = build_gimple_modify_stmt (NULL_TREE, build2 (PLUS_EXPR, ret_type,
 579                                                           a_acc, var));
 580       var = make_ssa_name (SSA_NAME_VAR (a_acc), stmt);
 581       GIMPLE_STMT_OPERAND (stmt, 0) = var;
 582       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 583       a_acc_arg = var;
 584     }
 585
 586   if (m)
 587     {
 588       stmt = build_gimple_modify_stmt (NULL_TREE,
 589                                        build2 (MULT_EXPR, ret_type,
 590                                                m_acc, m));
 591       var = make_ssa_name (SSA_NAME_VAR (m_acc), stmt);
 592       GIMPLE_STMT_OPERAND (stmt, 0) = var;
 593       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 594       m_acc_arg = var;
 595     }
 596
 597   if (a_acc)
 598     {
 599       for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
 600         if (PHI_RESULT (phi) == a_acc)
 601           break;
 602
 603       add_phi_arg (phi, a_acc_arg, back);
 604     }
 605
 606   if (m_acc)
 607     {
 608       for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
 609         if (PHI_RESULT (phi) == m_acc)
 610           break;
 611
 612       add_phi_arg (phi, m_acc_arg, back);
 613     }
 614 }
 615
 616 /* Adjust value of the return at the end of BB according to M and A
 617    accumulators.  */
 618
 619 static void
 620 adjust_return_value (basic_block bb, tree m, tree a)
 621 {
 622   tree ret_stmt = last_stmt (bb), ret_var, var, stmt, tmp;
 623   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 624   tree *ret_op;
 625   block_stmt_iterator bsi = bsi_last (bb);
 626
 627   gcc_assert (TREE_CODE (ret_stmt) == RETURN_EXPR);
 628
 629   ret_var = TREE_OPERAND (ret_stmt, 0);
 630   if (!ret_var)
 631     return;
 632
 633   if (TREE_CODE (ret_var) == GIMPLE_MODIFY_STMT)
 634     {
 635       ret_op = &GIMPLE_STMT_OPERAND (ret_var, 1);
 636       ret_var = *ret_op;
 637     }
 638   else
 639     ret_op = &TREE_OPERAND (ret_stmt, 0);
 640
 641   if (m)
 642     {
 643       stmt = build_gimple_modify_stmt (NULL_TREE,
 644                                        build2 (MULT_EXPR, ret_type,
 645                                                m_acc, ret_var));
 646
 647       tmp = create_tmp_var (ret_type, "acc_tmp");
 648       add_referenced_var (tmp);
 649
 650       var = make_ssa_name (tmp, stmt);
 651       GIMPLE_STMT_OPERAND (stmt, 0) = var;
 652       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 653     }
 654   else
 655     var = ret_var;
 656
 657   if (a)
 658     {
 659       stmt = build_gimple_modify_stmt (NULL_TREE,
 660                                        build2 (PLUS_EXPR, ret_type,
 661                                                a_acc, var));
 662
 663       tmp = create_tmp_var (ret_type, "acc_tmp");
 664       add_referenced_var (tmp);
 665
 666       var = make_ssa_name (tmp, stmt);
 667       GIMPLE_STMT_OPERAND (stmt, 0) = var;
 668       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 669     }
 670
 671   *ret_op = var;
 672   update_stmt (ret_stmt);
 673 }
 674
 675 /* Subtract COUNT and FREQUENCY from the basic block and it's
 676    outgoing edge.  */
 677 static void
 678 decrease_profile (basic_block bb, gcov_type count, int frequency)
 679 {
 680   edge e;
 681   bb->count -= count;
 682   if (bb->count < 0)
 683     bb->count = 0;
 684   bb->frequency -= frequency;
 685   if (bb->frequency < 0)
 686     bb->frequency = 0;
 687   if (!single_succ_p (bb))
 688     {
 689       gcc_assert (!EDGE_COUNT (bb->succs));
 690       return;
 691     }
 692   e = single_succ_edge (bb);
 693   e->count -= count;
 694   if (e->count < 0)
 695     e->count = 0;
 696 }
 697
 698 /* Returns true if argument PARAM of the tail recursive call needs to be copied
 699    when the call is eliminated.  */
 700
 701 static bool
 702 arg_needs_copy_p (tree param)
 703 {
 704   tree def;
 705
 706   if (!is_gimple_reg (param) || !var_ann (param))
 707     return false;
 708
 709   /* Parameters that are only defined but never used need not be copied.  */
 710   def = gimple_default_def (cfun, param);
 711   if (!def)
 712     return false;
 713
 714   return true;
 715 }
 716
 717 /* Eliminates tail call described by T.  TMP_VARS is a list of
 718    temporary variables used to copy the function arguments.  */
 719
 720 static void
 721 eliminate_tail_call (struct tailcall *t)
 722 {
 723   tree param, stmt, rslt, call;
 724   tree arg;
 725   call_expr_arg_iterator iter;
 726   basic_block bb, first;
 727   edge e;
 728   tree phi;
 729   block_stmt_iterator bsi;
 730   tree orig_stmt;
 731
 732   stmt = orig_stmt = bsi_stmt (t->call_bsi);
 733   bb = t->call_block;
 734
 735   if (dump_file && (dump_flags & TDF_DETAILS))
 736     {
 737       fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
 738                bb->index);
 739       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 740       fprintf (dump_file, "\n");
 741     }
 742
 743   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 744     stmt = GIMPLE_STMT_OPERAND (stmt, 1);
 745
 746   first = single_succ (ENTRY_BLOCK_PTR);
 747
 748   /* Remove the code after call_bsi that will become unreachable.  The
 749      possibly unreachable code in other blocks is removed later in
 750      cfg cleanup.  */
 751   bsi = t->call_bsi;
 752   bsi_next (&bsi);
 753   while (!bsi_end_p (bsi))
 754     {
 755       tree t = bsi_stmt (bsi);
 756       /* Do not remove the return statement, so that redirect_edge_and_branch
 757          sees how the block ends.  */
 758       if (TREE_CODE (t) == RETURN_EXPR)
 759         break;
 760
 761       bsi_remove (&bsi, true);
 762       release_defs (t);
 763     }
 764
 765   /* Number of executions of function has reduced by the tailcall.  */
 766   e = single_succ_edge (t->call_block);
 767   decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
 768   decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
 769   if (e->dest != EXIT_BLOCK_PTR)
 770     decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
 771
 772   /* Replace the call by a jump to the start of function.  */
 773   e = redirect_edge_and_branch (single_succ_edge (t->call_block), first);
 774   gcc_assert (e);
 775   PENDING_STMT (e) = NULL_TREE;
 776
 777   /* Add phi node entries for arguments.  The ordering of the phi nodes should
 778      be the same as the ordering of the arguments.  */
 779   for (param = DECL_ARGUMENTS (current_function_decl),
 780          arg = first_call_expr_arg (stmt, &iter),
 781          phi = phi_nodes (first);
 782        param;
 783        param = TREE_CHAIN (param), arg = next_call_expr_arg (&iter))
 784     {
 785       if (!arg_needs_copy_p (param))
 786         continue;
 787       gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
 788
 789       add_phi_arg (phi, arg, e);
 790       phi = PHI_CHAIN (phi);
 791     }
 792
 793   /* Update the values of accumulators.  */
 794   adjust_accumulator_values (t->call_bsi, t->mult, t->add, e);
 795
 796   call = bsi_stmt (t->call_bsi);
 797   if (TREE_CODE (call) == GIMPLE_MODIFY_STMT)
 798     {
 799       rslt = GIMPLE_STMT_OPERAND (call, 0);
 800
 801       /* Result of the call will no longer be defined.  So adjust the
 802          SSA_NAME_DEF_STMT accordingly.  */
 803       SSA_NAME_DEF_STMT (rslt) = build_empty_stmt ();
 804     }
 805
 806   bsi_remove (&t->call_bsi, true);
 807   release_defs (call);
 808 }
 809
 810 /* Add phi nodes for the virtual operands defined in the function to the
 811    header of the loop created by tail recursion elimination.
 812
 813    Originally, we used to add phi nodes only for call clobbered variables,
 814    as the value of the non-call clobbered ones obviously cannot be used
 815    or changed within the recursive call.  However, the local variables
 816    from multiple calls now share the same location, so the virtual ssa form
 817    requires us to say that the location dies on further iterations of the loop,
 818    which requires adding phi nodes.
 819 */
 820 static void
 821 add_virtual_phis (void)
 822 {
 823   referenced_var_iterator rvi;
 824   tree var;
 825
 826   /* The problematic part is that there is no way how to know what
 827      to put into phi nodes (there in fact does not have to be such
 828      ssa name available).  A solution would be to have an artificial
 829      use/kill for all virtual operands in EXIT node.  Unless we have
 830      this, we cannot do much better than to rebuild the ssa form for
 831      possibly affected virtual ssa names from scratch.  */
 832
 833   FOR_EACH_REFERENCED_VAR (var, rvi)
 834     {
 835       if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE)
 836         mark_sym_for_renaming (var);
 837     }
 838 }
 839
 840 /* Optimizes the tailcall described by T.  If OPT_TAILCALLS is true, also
 841    mark the tailcalls for the sibcall optimization.  */
 842
 843 static bool
 844 optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
 845 {
 846   if (t->tail_recursion)
 847     {
 848       eliminate_tail_call (t);
 849       return true;
 850     }
 851
 852   if (opt_tailcalls)
 853     {
 854       tree stmt = bsi_stmt (t->call_bsi);
 855
 856       stmt = get_call_expr_in (stmt);
 857       CALL_EXPR_TAILCALL (stmt) = 1;
 858       if (dump_file && (dump_flags & TDF_DETAILS))
 859         {
 860           fprintf (dump_file, "Found tail call ");
 861           print_generic_expr (dump_file, stmt, dump_flags);
 862           fprintf (dump_file, " in bb %i\n", t->call_block->index);
 863         }
 864     }
 865
 866   return false;
 867 }
 868
 869 /* Optimizes tail calls in the function, turning the tail recursion
 870    into iteration.  */
 871
 872 static unsigned int
 873 tree_optimize_tail_calls_1 (bool opt_tailcalls)
 874 {
 875   edge e;
 876   bool phis_constructed = false;
 877   struct tailcall *tailcalls = NULL, *act, *next;
 878   bool changed = false;
 879   basic_block first = single_succ (ENTRY_BLOCK_PTR);
 880   tree stmt, param, ret_type, tmp, phi;
 881   edge_iterator ei;
 882
 883   if (!suitable_for_tail_opt_p ())
 884     return 0;
 885   if (opt_tailcalls)
 886     opt_tailcalls = suitable_for_tail_call_opt_p ();
 887
 888   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 889     {
 890       /* Only traverse the normal exits, i.e. those that end with return
 891          statement.  */
 892       stmt = last_stmt (e->src);
 893
 894       if (stmt
 895           && TREE_CODE (stmt) == RETURN_EXPR)
 896         find_tail_calls (e->src, &tailcalls);
 897     }
 898
 899   /* Construct the phi nodes and accumulators if necessary.  */
 900   a_acc = m_acc = NULL_TREE;
 901   for (act = tailcalls; act; act = act->next)
 902     {
 903       if (!act->tail_recursion)
 904         continue;
 905
 906       if (!phis_constructed)
 907         {
 908           /* Ensure that there is only one predecessor of the block.  */
 909           if (!single_pred_p (first))
 910             first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
 911
 912           /* Copy the args if needed.  */
 913           for (param = DECL_ARGUMENTS (current_function_decl);
 914                param;
 915                param = TREE_CHAIN (param))
 916             if (arg_needs_copy_p (param))
 917               {
 918                 tree name = gimple_default_def (cfun, param);
 919                 tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
 920                 tree phi;
 921
 922                 set_default_def (param, new_name);
 923                 phi = create_phi_node (name, first);
 924                 SSA_NAME_DEF_STMT (name) = phi;
 925                 add_phi_arg (phi, new_name, single_pred_edge (first));
 926               }
 927           phis_constructed = true;
 928         }
 929
 930       if (act->add && !a_acc)
 931         {
 932           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 933
 934           tmp = create_tmp_var (ret_type, "add_acc");
 935           add_referenced_var (tmp);
 936
 937           phi = create_phi_node (tmp, first);
 938           add_phi_arg (phi,
 939                        /* RET_TYPE can be a float when -ffast-maths is
 940                           enabled.  */
 941                        fold_convert (ret_type, integer_zero_node),
 942                        single_pred_edge (first));
 943           a_acc = PHI_RESULT (phi);
 944         }
 945
 946       if (act->mult && !m_acc)
 947         {
 948           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 949
 950           tmp = create_tmp_var (ret_type, "mult_acc");
 951           add_referenced_var (tmp);
 952
 953           phi = create_phi_node (tmp, first);
 954           add_phi_arg (phi,
 955                        /* RET_TYPE can be a float when -ffast-maths is
 956                           enabled.  */
 957                        fold_convert (ret_type, integer_one_node),
 958                        single_pred_edge (first));
 959           m_acc = PHI_RESULT (phi);
 960         }
 961     }
 962
 963
 964   if (phis_constructed)
 965     {
 966       /* Reverse the order of the phi nodes, so that it matches the order
 967          of operands of the function, as assumed by eliminate_tail_call.  */
 968       set_phi_nodes (first, phi_reverse (phi_nodes (first)));
 969     }
 970
 971   for (; tailcalls; tailcalls = next)
 972     {
 973       next = tailcalls->next;
 974       changed |= optimize_tail_call (tailcalls, opt_tailcalls);
 975       free (tailcalls);
 976     }
 977
 978   if (a_acc || m_acc)
 979     {
 980       /* Modify the remaining return statements.  */
 981       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 982         {
 983           stmt = last_stmt (e->src);
 984
 985           if (stmt
 986               && TREE_CODE (stmt) == RETURN_EXPR)
 987             adjust_return_value (e->src, m_acc, a_acc);
 988         }
 989     }
 990
 991   if (changed)
 992     free_dominance_info (CDI_DOMINATORS);
 993
 994   if (phis_constructed)
 995     add_virtual_phis ();
 996   if (changed)
 997     return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
 998   return 0;
 999 }
1000
1001 static unsigned int
1002 execute_tail_recursion (void)
1003 {
1004   return tree_optimize_tail_calls_1 (false);
1005 }
1006
1007 static bool
1008 gate_tail_calls (void)
1009 {
1010   return flag_optimize_sibling_calls != 0;
1011 }
1012
1013 static unsigned int
1014 execute_tail_calls (void)
1015 {
1016   return tree_optimize_tail_calls_1 (true);
1017 }
1018
1019 struct tree_opt_pass pass_tail_recursion =
1020 {
1021   "tailr",                              /* name */
1022   gate_tail_calls,                      /* gate */
1023   execute_tail_recursion,               /* execute */
1024   NULL,                                 /* sub */
1025   NULL,                                 /* next */
1026   0,                                    /* static_pass_number */
1027   0,                                    /* tv_id */
1028   PROP_cfg | PROP_ssa,                  /* properties_required */
1029   0,                                    /* properties_provided */
1030   0,                                    /* properties_destroyed */
1031   0,                                    /* todo_flags_start */
1032   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
1033   0                                     /* letter */
1034 };
1035
1036 struct tree_opt_pass pass_tail_calls =
1037 {
1038   "tailc",                              /* name */
1039   gate_tail_calls,                      /* gate */
1040   execute_tail_calls,                   /* execute */
1041   NULL,                                 /* sub */
1042   NULL,                                 /* next */
1043   0,                                    /* static_pass_number */
1044   0,                                    /* tv_id */
1045   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1046   0,                                    /* properties_provided */
1047   0,                                    /* properties_destroyed */
1048   0,                                    /* todo_flags_start */
1049   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
1050   0                                     /* letter */
1051 };