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