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