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 (!is_global_var (var)
 148           && (!MTAG_P (var) || TREE_CODE (var) == STRUCT_FIELD_TAG)
 149           && is_call_clobbered (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 = TREE_OPERAND (ass, 0);
 276   tree src = TREE_OPERAND (ass, 1);
 277   enum tree_code code = TREE_CODE (src);
 278   tree src_var = src;
 279
 280   /* See if this is a simple copy operation of an SSA name to the function
 281      result.  In that case we may have a simple tail call.  Ignore type
 282      conversions that can never produce extra code between the function
 283      call and the function return.  */
 284   STRIP_NOPS (src_var);
 285   if (TREE_CODE (src_var) == SSA_NAME)
 286     {
 287       if (src_var != *ass_var)
 288         return false;
 289
 290       *ass_var = dest;
 291       return true;
 292     }
 293
 294   if (TREE_CODE_CLASS (code) != tcc_binary)
 295     return false;
 296
 297   /* Accumulator optimizations will reverse the order of operations.
 298      We can only do that for floating-point types if we're assuming
 299      that addition and multiplication are associative.  */
 300   if (!flag_unsafe_math_optimizations)
 301     if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
 302       return false;
 303
 304   /* We only handle the code like
 305
 306      x = call ();
 307      y = m * x;
 308      z = y + a;
 309      return z;
 310
 311      TODO -- Extend it for cases where the linear transformation of the output
 312      is expressed in a more complicated way.  */
 313
 314   op0 = TREE_OPERAND (src, 0);
 315   op1 = TREE_OPERAND (src, 1);
 316
 317   if (op0 == *ass_var
 318       && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
 319     ;
 320   else if (op1 == *ass_var
 321            && (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
 322     ;
 323   else
 324     return false;
 325
 326   switch (code)
 327     {
 328     case PLUS_EXPR:
 329       /* There should be no previous addition.  TODO -- it should be fairly
 330          straightforward to lift this restriction -- just allow storing
 331          more complicated expressions in *A, and gimplify it in
 332          adjust_accumulator_values.  */
 333       if (*a)
 334         return false;
 335       *a = non_ass_var;
 336       *ass_var = dest;
 337       return true;
 338
 339     case MULT_EXPR:
 340       /* Similar remark applies here.  Handling multiplication after addition
 341          is just slightly more complicated -- we need to multiply both *A and
 342          *M.  */
 343       if (*a || *m)
 344         return false;
 345       *m = non_ass_var;
 346       *ass_var = dest;
 347       return true;
 348
 349       /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR).  */
 350
 351     default:
 352       return false;
 353     }
 354 }
 355
 356 /* Propagate VAR through phis on edge E.  */
 357
 358 static tree
 359 propagate_through_phis (tree var, edge e)
 360 {
 361   basic_block dest = e->dest;
 362   tree phi;
 363
 364   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
 365     if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
 366       return PHI_RESULT (phi);
 367
 368   return var;
 369 }
 370
 371 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
 372    added to the start of RET.  */
 373
 374 static void
 375 find_tail_calls (basic_block bb, struct tailcall **ret)
 376 {
 377   tree ass_var, ret_var, stmt, func, param, args, call = NULL_TREE;
 378   block_stmt_iterator bsi, absi;
 379   bool tail_recursion;
 380   struct tailcall *nw;
 381   edge e;
 382   tree m, a;
 383   basic_block abb;
 384   stmt_ann_t ann;
 385
 386   if (!single_succ_p (bb))
 387     return;
 388
 389   for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
 390     {
 391       stmt = bsi_stmt (bsi);
 392
 393       /* Ignore labels.  */
 394       if (TREE_CODE (stmt) == LABEL_EXPR)
 395         continue;
 396
 397       /* Check for a call.  */
 398       if (TREE_CODE (stmt) == MODIFY_EXPR)
 399         {
 400           ass_var = TREE_OPERAND (stmt, 0);
 401           call = TREE_OPERAND (stmt, 1);
 402           if (TREE_CODE (call) == WITH_SIZE_EXPR)
 403             call = TREE_OPERAND (call, 0);
 404         }
 405       else
 406         {
 407           ass_var = NULL_TREE;
 408           call = stmt;
 409         }
 410
 411       if (TREE_CODE (call) == CALL_EXPR)
 412         break;
 413
 414       /* If the statement has virtual or volatile operands, fail.  */
 415       ann = stmt_ann (stmt);
 416       if (!ZERO_SSA_OPERANDS (stmt, (SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS))
 417           || ann->has_volatile_ops)
 418         return;
 419     }
 420
 421   if (bsi_end_p (bsi))
 422     {
 423       edge_iterator ei;
 424       /* Recurse to the predecessors.  */
 425       FOR_EACH_EDGE (e, ei, bb->preds)
 426         find_tail_calls (e->src, ret);
 427
 428       return;
 429     }
 430
 431   /* We found the call, check whether it is suitable.  */
 432   tail_recursion = false;
 433   func = get_callee_fndecl (call);
 434   if (func == current_function_decl)
 435     {
 436       for (param = DECL_ARGUMENTS (func), args = TREE_OPERAND (call, 1);
 437            param && args;
 438            param = TREE_CHAIN (param), args = TREE_CHAIN (args))
 439         {
 440           tree arg = TREE_VALUE (args);
 441           if (param != arg)
 442             {
 443               /* Make sure there are no problems with copying.  The parameter
 444                  have a copyable type and the two arguments must have reasonably
 445                  equivalent types.  The latter requirement could be relaxed if
 446                  we emitted a suitable type conversion statement.  */
 447               if (!is_gimple_reg_type (TREE_TYPE (param))
 448                   || !lang_hooks.types_compatible_p (TREE_TYPE (param),
 449                                                      TREE_TYPE (arg)))
 450                 break;
 451
 452               /* The parameter should be a real operand, so that phi node
 453                  created for it at the start of the function has the meaning
 454                  of copying the value.  This test implies is_gimple_reg_type
 455                  from the previous condition, however this one could be
 456                  relaxed by being more careful with copying the new value
 457                  of the parameter (emitting appropriate MODIFY_EXPR and
 458                  updating the virtual operands).  */
 459               if (!is_gimple_reg (param))
 460                 break;
 461             }
 462         }
 463       if (!args && !param)
 464         tail_recursion = true;
 465     }
 466
 467   /* Now check the statements after the call.  None of them has virtual
 468      operands, so they may only depend on the call through its return
 469      value.  The return value should also be dependent on each of them,
 470      since we are running after dce.  */
 471   m = NULL_TREE;
 472   a = NULL_TREE;
 473
 474   abb = bb;
 475   absi = bsi;
 476   while (1)
 477     {
 478       bsi_next (&absi);
 479
 480       while (bsi_end_p (absi))
 481         {
 482           ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
 483           abb = single_succ (abb);
 484           absi = bsi_start (abb);
 485         }
 486
 487       stmt = bsi_stmt (absi);
 488
 489       if (TREE_CODE (stmt) == LABEL_EXPR)
 490         continue;
 491
 492       if (TREE_CODE (stmt) == RETURN_EXPR)
 493         break;
 494
 495       if (TREE_CODE (stmt) != MODIFY_EXPR)
 496         return;
 497
 498       if (!process_assignment (stmt, stmt, bsi, &m, &a, &ass_var))
 499         return;
 500     }
 501
 502   /* See if this is a tail call we can handle.  */
 503   ret_var = TREE_OPERAND (stmt, 0);
 504   if (ret_var
 505       && TREE_CODE (ret_var) == MODIFY_EXPR)
 506     {
 507       tree ret_op = TREE_OPERAND (ret_var, 1);
 508       STRIP_NOPS (ret_op);
 509       if (!tail_recursion
 510           && TREE_CODE (ret_op) != SSA_NAME)
 511         return;
 512
 513       if (!process_assignment (ret_var, stmt, bsi, &m, &a, &ass_var))
 514         return;
 515       ret_var = TREE_OPERAND (ret_var, 0);
 516     }
 517
 518   /* We may proceed if there either is no return value, or the return value
 519      is identical to the call's return.  */
 520   if (ret_var
 521       && (ret_var != ass_var))
 522     return;
 523
 524   /* If this is not a tail recursive call, we cannot handle addends or
 525      multiplicands.  */
 526   if (!tail_recursion && (m || a))
 527     return;
 528
 529   nw = XNEW (struct tailcall);
 530
 531   nw->call_block = bb;
 532   nw->call_bsi = bsi;
 533
 534   nw->tail_recursion = tail_recursion;
 535
 536   nw->mult = m;
 537   nw->add = a;
 538
 539   nw->next = *ret;
 540   *ret = nw;
 541 }
 542
 543 /* Adjust the accumulator values according to A and M after BSI, and update
 544    the phi nodes on edge BACK.  */
 545
 546 static void
 547 adjust_accumulator_values (block_stmt_iterator bsi, tree m, tree a, edge back)
 548 {
 549   tree stmt, var, phi, tmp;
 550   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 551   tree a_acc_arg = a_acc, m_acc_arg = m_acc;
 552
 553   if (a)
 554     {
 555       if (m_acc)
 556         {
 557           if (integer_onep (a))
 558             var = m_acc;
 559           else
 560             {
 561               stmt = build2 (MODIFY_EXPR, ret_type, NULL_TREE,
 562                              build2 (MULT_EXPR, ret_type, m_acc, a));
 563
 564               tmp = create_tmp_var (ret_type, "acc_tmp");
 565               add_referenced_tmp_var (tmp);
 566
 567               var = make_ssa_name (tmp, stmt);
 568               TREE_OPERAND (stmt, 0) = var;
 569               bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 570             }
 571         }
 572       else
 573         var = a;
 574
 575       stmt = build2 (MODIFY_EXPR, ret_type, NULL_TREE,
 576                      build2 (PLUS_EXPR, ret_type, a_acc, var));
 577       var = make_ssa_name (SSA_NAME_VAR (a_acc), stmt);
 578       TREE_OPERAND (stmt, 0) = var;
 579       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 580       a_acc_arg = var;
 581     }
 582
 583   if (m)
 584     {
 585       stmt = build2 (MODIFY_EXPR, ret_type, NULL_TREE,
 586                      build2 (MULT_EXPR, ret_type, m_acc, m));
 587       var = make_ssa_name (SSA_NAME_VAR (m_acc), stmt);
 588       TREE_OPERAND (stmt, 0) = var;
 589       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 590       m_acc_arg = var;
 591     }
 592
 593   if (a_acc)
 594     {
 595       for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
 596         if (PHI_RESULT (phi) == a_acc)
 597           break;
 598
 599       add_phi_arg (phi, a_acc_arg, back);
 600     }
 601
 602   if (m_acc)
 603     {
 604       for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
 605         if (PHI_RESULT (phi) == m_acc)
 606           break;
 607
 608       add_phi_arg (phi, m_acc_arg, back);
 609     }
 610 }
 611
 612 /* Adjust value of the return at the end of BB according to M and A
 613    accumulators.  */
 614
 615 static void
 616 adjust_return_value (basic_block bb, tree m, tree a)
 617 {
 618   tree ret_stmt = last_stmt (bb), ret_var, var, stmt, tmp;
 619   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 620   block_stmt_iterator bsi = bsi_last (bb);
 621
 622   gcc_assert (TREE_CODE (ret_stmt) == RETURN_EXPR);
 623
 624   ret_var = TREE_OPERAND (ret_stmt, 0);
 625   if (!ret_var)
 626     return;
 627
 628   if (TREE_CODE (ret_var) == MODIFY_EXPR)
 629     {
 630       ret_var->common.ann = (tree_ann_t) stmt_ann (ret_stmt);
 631       bsi_replace (&bsi, ret_var, true);
 632       SSA_NAME_DEF_STMT (TREE_OPERAND (ret_var, 0)) = ret_var;
 633       ret_var = TREE_OPERAND (ret_var, 0);
 634       ret_stmt = build1 (RETURN_EXPR, TREE_TYPE (ret_stmt), ret_var);
 635       bsi_insert_after (&bsi, ret_stmt, BSI_NEW_STMT);
 636     }
 637
 638   if (m)
 639     {
 640       stmt = build2 (MODIFY_EXPR, ret_type, NULL_TREE,
 641                      build2 (MULT_EXPR, ret_type, m_acc, ret_var));
 642
 643       tmp = create_tmp_var (ret_type, "acc_tmp");
 644       add_referenced_tmp_var (tmp);
 645
 646       var = make_ssa_name (tmp, stmt);
 647       TREE_OPERAND (stmt, 0) = var;
 648       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 649     }
 650   else
 651     var = ret_var;
 652
 653   if (a)
 654     {
 655       stmt = build2 (MODIFY_EXPR, ret_type, NULL_TREE,
 656                      build2 (PLUS_EXPR, ret_type, a_acc, var));
 657
 658       tmp = create_tmp_var (ret_type, "acc_tmp");
 659       add_referenced_tmp_var (tmp);
 660
 661       var = make_ssa_name (tmp, stmt);
 662       TREE_OPERAND (stmt, 0) = var;
 663       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 664     }
 665
 666   TREE_OPERAND (ret_stmt, 0) = var;
 667   update_stmt (ret_stmt);
 668 }
 669
 670 /* Subtract COUNT and FREQUENCY from the basic block and it's
 671    outgoing edge.  */
 672 static void
 673 decrease_profile (basic_block bb, gcov_type count, int frequency)
 674 {
 675   edge e;
 676   bb->count -= count;
 677   if (bb->count < 0)
 678     bb->count = 0;
 679   bb->frequency -= frequency;
 680   if (bb->frequency < 0)
 681     bb->frequency = 0;
 682   if (!single_succ_p (bb))
 683     {
 684       gcc_assert (!EDGE_COUNT (bb->succs));
 685       return;
 686     }
 687   e = single_succ_edge (bb);
 688   e->count -= count;
 689   if (e->count < 0)
 690     e->count = 0;
 691 }
 692
 693 /* Eliminates tail call described by T.  TMP_VARS is a list of
 694    temporary variables used to copy the function arguments.  */
 695
 696 static void
 697 eliminate_tail_call (struct tailcall *t)
 698 {
 699   tree param, stmt, args, rslt, call;
 700   basic_block bb, first;
 701   edge e;
 702   tree phi;
 703   block_stmt_iterator bsi;
 704   use_operand_p mayuse;
 705   def_operand_p maydef;
 706   ssa_op_iter iter;
 707   tree orig_stmt;
 708
 709   stmt = orig_stmt = bsi_stmt (t->call_bsi);
 710   bb = t->call_block;
 711
 712   if (dump_file && (dump_flags & TDF_DETAILS))
 713     {
 714       fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
 715                bb->index);
 716       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 717       fprintf (dump_file, "\n");
 718     }
 719
 720   if (TREE_CODE (stmt) == MODIFY_EXPR)
 721     stmt = TREE_OPERAND (stmt, 1);
 722
 723   first = single_succ (ENTRY_BLOCK_PTR);
 724
 725   /* Remove the code after call_bsi that will become unreachable.  The
 726      possibly unreachable code in other blocks is removed later in
 727      cfg cleanup.  */
 728   bsi = t->call_bsi;
 729   bsi_next (&bsi);
 730   while (!bsi_end_p (bsi))
 731     {
 732       tree t = bsi_stmt (bsi);
 733       /* Do not remove the return statement, so that redirect_edge_and_branch
 734          sees how the block ends.  */
 735       if (TREE_CODE (t) == RETURN_EXPR)
 736         break;
 737
 738       bsi_remove (&bsi, true);
 739       release_defs (t);
 740     }
 741
 742   /* Number of executions of function has reduced by the tailcall.  */
 743   e = single_succ_edge (t->call_block);
 744   decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
 745   decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
 746   if (e->dest != EXIT_BLOCK_PTR)
 747     decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
 748
 749   /* Replace the call by a jump to the start of function.  */
 750   e = redirect_edge_and_branch (single_succ_edge (t->call_block), first);
 751   gcc_assert (e);
 752   PENDING_STMT (e) = NULL_TREE;
 753
 754   /* Add phi node entries for arguments.  Not every PHI node corresponds to
 755      a function argument (there may be PHI nodes for virtual definitions of the
 756      eliminated calls), so we search for a PHI corresponding to each argument
 757      rather than searching for which argument a PHI node corresponds to.  */
 758
 759   for (param = DECL_ARGUMENTS (current_function_decl),
 760        args = TREE_OPERAND (stmt, 1);
 761        param;
 762        param = TREE_CHAIN (param),
 763        args = TREE_CHAIN (args))
 764     {
 765
 766       for (phi = phi_nodes (first); phi; phi = PHI_CHAIN (phi))
 767         if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
 768           break;
 769
 770       /* The phi node indeed does not have to be there, in case the operand is
 771          invariant in the function.  */
 772       if (!phi)
 773         continue;
 774
 775       add_phi_arg (phi, TREE_VALUE (args), e);
 776     }
 777
 778   /* Add phi nodes for the call clobbered variables.  */
 779   FOR_EACH_SSA_MAYDEF_OPERAND (maydef, mayuse, orig_stmt, iter)
 780     {
 781       param = SSA_NAME_VAR (DEF_FROM_PTR (maydef));
 782       for (phi = phi_nodes (first); phi; phi = PHI_CHAIN (phi))
 783         if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
 784           break;
 785
 786       if (!phi)
 787         {
 788           tree name = default_def (param);
 789           tree new_name;
 790
 791           if (!name)
 792             {
 793               /* It may happen that the tag does not have a default_def in case
 794                  when all uses of it are dominated by a MUST_DEF.  This however
 795                  means that it is not necessary to add a phi node for this
 796                  tag.  */
 797               continue;
 798             }
 799           new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
 800
 801           set_default_def (param, new_name);
 802           phi = create_phi_node (name, first);
 803           SSA_NAME_DEF_STMT (name) = phi;
 804           add_phi_arg (phi, new_name, single_succ_edge (ENTRY_BLOCK_PTR));
 805
 806           /* For all calls the same set of variables should be clobbered.  This
 807              means that there always should be the appropriate phi node except
 808              for the first time we eliminate the call.  */
 809           gcc_assert (EDGE_COUNT (first->preds) <= 2);
 810         }
 811
 812       add_phi_arg (phi, USE_FROM_PTR (mayuse), e);
 813     }
 814
 815   /* Update the values of accumulators.  */
 816   adjust_accumulator_values (t->call_bsi, t->mult, t->add, e);
 817
 818   call = bsi_stmt (t->call_bsi);
 819   if (TREE_CODE (call) == MODIFY_EXPR)
 820     {
 821       rslt = TREE_OPERAND (call, 0);
 822
 823       /* Result of the call will no longer be defined.  So adjust the
 824          SSA_NAME_DEF_STMT accordingly.  */
 825       SSA_NAME_DEF_STMT (rslt) = build_empty_stmt ();
 826     }
 827
 828   bsi_remove (&t->call_bsi, true);
 829   release_defs (call);
 830 }
 831
 832 /* Optimizes the tailcall described by T.  If OPT_TAILCALLS is true, also
 833    mark the tailcalls for the sibcall optimization.  */
 834
 835 static bool
 836 optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
 837 {
 838   if (t->tail_recursion)
 839     {
 840       eliminate_tail_call (t);
 841       return true;
 842     }
 843
 844   if (opt_tailcalls)
 845     {
 846       tree stmt = bsi_stmt (t->call_bsi);
 847
 848       stmt = get_call_expr_in (stmt);
 849       CALL_EXPR_TAILCALL (stmt) = 1;
 850       if (dump_file && (dump_flags & TDF_DETAILS))
 851         {
 852           fprintf (dump_file, "Found tail call ");
 853           print_generic_expr (dump_file, stmt, dump_flags);
 854           fprintf (dump_file, " in bb %i\n", t->call_block->index);
 855         }
 856     }
 857
 858   return false;
 859 }
 860
 861 /* Optimizes tail calls in the function, turning the tail recursion
 862    into iteration.  */
 863
 864 static void
 865 tree_optimize_tail_calls_1 (bool opt_tailcalls)
 866 {
 867   edge e;
 868   bool phis_constructed = false;
 869   struct tailcall *tailcalls = NULL, *act, *next;
 870   bool changed = false;
 871   basic_block first = single_succ (ENTRY_BLOCK_PTR);
 872   tree stmt, param, ret_type, tmp, phi;
 873   edge_iterator ei;
 874
 875   if (!suitable_for_tail_opt_p ())
 876     return;
 877   if (opt_tailcalls)
 878     opt_tailcalls = suitable_for_tail_call_opt_p ();
 879
 880   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 881     {
 882       /* Only traverse the normal exits, i.e. those that end with return
 883          statement.  */
 884       stmt = last_stmt (e->src);
 885
 886       if (stmt
 887           && TREE_CODE (stmt) == RETURN_EXPR)
 888         find_tail_calls (e->src, &tailcalls);
 889     }
 890
 891   /* Construct the phi nodes and accumulators if necessary.  */
 892   a_acc = m_acc = NULL_TREE;
 893   for (act = tailcalls; act; act = act->next)
 894     {
 895       if (!act->tail_recursion)
 896         continue;
 897
 898       if (!phis_constructed)
 899         {
 900           tree name;
 901           /* Ensure that there is only one predecessor of the block.  */
 902           if (!single_pred_p (first))
 903             first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
 904
 905           /* Copy the args if needed.  */
 906           for (param = DECL_ARGUMENTS (current_function_decl);
 907                param;
 908                param = TREE_CHAIN (param))
 909             if (is_gimple_reg (param)
 910                 && var_ann (param)
 911                 /* Also parameters that are only defined but never used need not
 912                    be copied.  */
 913                 && ((name = default_def (param))
 914                     && TREE_CODE (name) == SSA_NAME))
 915             {
 916               tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
 917               tree phi;
 918
 919               set_default_def (param, new_name);
 920               phi = create_phi_node (name, first);
 921               SSA_NAME_DEF_STMT (name) = phi;
 922               add_phi_arg (phi, new_name, single_pred_edge (first));
 923             }
 924           phis_constructed = true;
 925         }
 926
 927       if (act->add && !a_acc)
 928         {
 929           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 930
 931           tmp = create_tmp_var (ret_type, "add_acc");
 932           add_referenced_tmp_var (tmp);
 933
 934           phi = create_phi_node (tmp, first);
 935           add_phi_arg (phi,
 936                        /* RET_TYPE can be a float when -ffast-maths is
 937                           enabled.  */
 938                        fold_convert (ret_type, integer_zero_node),
 939                        single_pred_edge (first));
 940           a_acc = PHI_RESULT (phi);
 941         }
 942
 943       if (act->mult && !m_acc)
 944         {
 945           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 946
 947           tmp = create_tmp_var (ret_type, "mult_acc");
 948           add_referenced_tmp_var (tmp);
 949
 950           phi = create_phi_node (tmp, first);
 951           add_phi_arg (phi,
 952                        /* RET_TYPE can be a float when -ffast-maths is
 953                           enabled.  */
 954                        fold_convert (ret_type, integer_one_node),
 955                        single_pred_edge (first));
 956           m_acc = PHI_RESULT (phi);
 957         }
 958     }
 959
 960   for (; tailcalls; tailcalls = next)
 961     {
 962       next = tailcalls->next;
 963       changed |= optimize_tail_call (tailcalls, opt_tailcalls);
 964       free (tailcalls);
 965     }
 966
 967   if (a_acc || m_acc)
 968     {
 969       /* Modify the remaining return statements.  */
 970       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 971         {
 972           stmt = last_stmt (e->src);
 973
 974           if (stmt
 975               && TREE_CODE (stmt) == RETURN_EXPR)
 976             adjust_return_value (e->src, m_acc, a_acc);
 977         }
 978     }
 979
 980   if (changed)
 981     {
 982       free_dominance_info (CDI_DOMINATORS);
 983       cleanup_tree_cfg ();
 984     }
 985 }
 986
 987 static void
 988 execute_tail_recursion (void)
 989 {
 990   tree_optimize_tail_calls_1 (false);
 991 }
 992
 993 static bool
 994 gate_tail_calls (void)
 995 {
 996   return flag_optimize_sibling_calls != 0;
 997 }
 998
 999 static void
1000 execute_tail_calls (void)
1001 {
1002   tree_optimize_tail_calls_1 (true);
1003 }
1004
1005 struct tree_opt_pass pass_tail_recursion =
1006 {
1007   "tailr",                              /* name */
1008   NULL,                                 /* gate */
1009   execute_tail_recursion,               /* execute */
1010   NULL,                                 /* sub */
1011   NULL,                                 /* next */
1012   0,                                    /* static_pass_number */
1013   0,                                    /* tv_id */
1014   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1015   0,                                    /* properties_provided */
1016   0,                                    /* properties_destroyed */
1017   0,                                    /* todo_flags_start */
1018   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
1019   0                                     /* letter */
1020 };
1021
1022 struct tree_opt_pass pass_tail_calls =
1023 {
1024   "tailc",                              /* name */
1025   gate_tail_calls,                      /* gate */
1026   execute_tail_calls,                   /* execute */
1027   NULL,                                 /* sub */
1028   NULL,                                 /* next */
1029   0,                                    /* static_pass_number */
1030   0,                                    /* tv_id */
1031   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1032   0,                                    /* properties_provided */
1033   0,                                    /* properties_destroyed */
1034   0,                                    /* todo_flags_start */
1035   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
1036   0                                     /* letter */
1037 };