gcc/tree-tailcall.c

   1 /* Tail call optimization on trees.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  19 Boston, MA 02110-1301, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "hard-reg-set.h"
  29 #include "basic-block.h"
  30 #include "function.h"
  31 #include "tree-flow.h"
  32 #include "tree-dump.h"
  33 #include "diagnostic.h"
  34 #include "except.h"
  35 #include "tree-pass.h"
  36 #include "flags.h"
  37 #include "langhooks.h"
  38 #include "dbgcnt.h"
  39
  40 /* The file implements the tail recursion elimination.  It is also used to
  41    analyze the tail calls in general, passing the results to the rtl level
  42    where they are used for sibcall optimization.
  43
  44    In addition to the standard tail recursion elimination, we handle the most
  45    trivial cases of making the call tail recursive by creating accumulators.
  46    For example the following function
  47
  48    int sum (int n)
  49    {
  50      if (n > 0)
  51        return n + sum (n - 1);
  52      else
  53        return 0;
  54    }
  55
  56    is transformed into
  57
  58    int sum (int n)
  59    {
  60      int acc = 0;
  61
  62      while (n > 0)
  63        acc += n--;
  64
  65      return acc;
  66    }
  67
  68    To do this, we maintain two accumulators (a_acc and m_acc) that indicate
  69    when we reach the return x statement, we should return a_acc + x * m_acc
  70    instead.  They are initially initialized to 0 and 1, respectively,
  71    so the semantics of the function is obviously preserved.  If we are
  72    guaranteed that the value of the accumulator never change, we
  73    omit the accumulator.
  74
  75    There are three cases how the function may exit.  The first one is
  76    handled in adjust_return_value, the other two in adjust_accumulator_values
  77    (the second case is actually a special case of the third one and we
  78    present it separately just for clarity):
  79
  80    1) Just return x, where x is not in any of the remaining special shapes.
  81       We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
  82
  83    2) return f (...), where f is the current function, is rewritten in a
  84       classical tail-recursion elimination way, into assignment of arguments
  85       and jump to the start of the function.  Values of the accumulators
  86       are unchanged.
  87
  88    3) return a + m * f(...), where a and m do not depend on call to f.
  89       To preserve the semantics described before we want this to be rewritten
  90       in such a way that we finally return
  91
  92       a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
  93
  94       I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
  95       eliminate the tail call to f.  Special cases when the value is just
  96       added or just multiplied are obtained by setting a = 0 or m = 1.
  97
  98    TODO -- it is possible to do similar tricks for other operations.  */
  99
 100 /* A structure that describes the tailcall.  */
 101
 102 struct tailcall
 103 {
 104   /* The block in that the call occur.  */
 105   basic_block call_block;
 106
 107   /* The iterator pointing to the call statement.  */
 108   block_stmt_iterator call_bsi;
 109
 110   /* True if it is a call to the current function.  */
 111   bool tail_recursion;
 112
 113   /* The return value of the caller is mult * f + add, where f is the return
 114      value of the call.  */
 115   tree mult, add;
 116
 117   /* Next tailcall in the chain.  */
 118   struct tailcall *next;
 119 };
 120
 121 /* The variables holding the value of multiplicative and additive
 122    accumulator.  */
 123 static tree m_acc, a_acc;
 124
 125 static bool suitable_for_tail_opt_p (void);
 126 static bool optimize_tail_call (struct tailcall *, bool);
 127 static void eliminate_tail_call (struct tailcall *);
 128 static void find_tail_calls (basic_block, struct tailcall **);
 129
 130 /* Returns false when the function is not suitable for tail call optimization
 131    from some reason (e.g. if it takes variable number of arguments).  */
 132
 133 static bool
 134 suitable_for_tail_opt_p (void)
 135 {
 136   referenced_var_iterator rvi;
 137   tree var;
 138
 139   if (current_function_stdarg)
 140     return false;
 141
 142   /* No local variable nor structure field should be call-clobbered.  We
 143      ignore any kind of memory tag, as these are not real variables.  */
 144
 145   FOR_EACH_REFERENCED_VAR (var, rvi)
 146     {
 147       if (!is_global_var (var)
 148           && (!MTAG_P (var) || TREE_CODE (var) == STRUCT_FIELD_TAG)
 149           && (gimple_aliases_computed_p (cfun) ? is_call_clobbered (var)
 150               : TREE_ADDRESSABLE (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 = GIMPLE_STMT_OPERAND (ass, 0);
 277   tree src = GIMPLE_STMT_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, POINTER_PLUS_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, 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) == GIMPLE_MODIFY_STMT)
 400         {
 401           ass_var = GIMPLE_STMT_OPERAND (stmt, 0);
 402           call = GIMPLE_STMT_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       call_expr_arg_iterator iter;
 438       tree arg;
 439       for (param = DECL_ARGUMENTS (func),
 440              arg = first_call_expr_arg (call, &iter);
 441            param && arg;
 442            param = TREE_CHAIN (param), arg = next_call_expr_arg (&iter))
 443         {
 444           if (param != arg)
 445             {
 446               /* Make sure there are no problems with copying.  The parameter
 447                  have a copyable type and the two arguments must have reasonably
 448                  equivalent types.  The latter requirement could be relaxed if
 449                  we emitted a suitable type conversion statement.  */
 450               if (!is_gimple_reg_type (TREE_TYPE (param))
 451                   || !lang_hooks.types_compatible_p (TREE_TYPE (param),
 452                                                      TREE_TYPE (arg)))
 453                 break;
 454
 455               /* The parameter should be a real operand, so that phi node
 456                  created for it at the start of the function has the meaning
 457                  of copying the value.  This test implies is_gimple_reg_type
 458                  from the previous condition, however this one could be
 459                  relaxed by being more careful with copying the new value
 460                  of the parameter (emitting appropriate GIMPLE_MODIFY_STMT and
 461                  updating the virtual operands).  */
 462               if (!is_gimple_reg (param))
 463                 break;
 464             }
 465         }
 466       if (!arg && !param)
 467         tail_recursion = true;
 468     }
 469
 470   /* Now check the statements after the call.  None of them has virtual
 471      operands, so they may only depend on the call through its return
 472      value.  The return value should also be dependent on each of them,
 473      since we are running after dce.  */
 474   m = NULL_TREE;
 475   a = NULL_TREE;
 476
 477   abb = bb;
 478   absi = bsi;
 479   while (1)
 480     {
 481       bsi_next (&absi);
 482
 483       while (bsi_end_p (absi))
 484         {
 485           ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
 486           abb = single_succ (abb);
 487           absi = bsi_start (abb);
 488         }
 489
 490       stmt = bsi_stmt (absi);
 491
 492       if (TREE_CODE (stmt) == LABEL_EXPR)
 493         continue;
 494
 495       if (TREE_CODE (stmt) == RETURN_EXPR)
 496         break;
 497
 498       if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
 499         return;
 500
 501       if (!process_assignment (stmt, stmt, bsi, &m, &a, &ass_var))
 502         return;
 503     }
 504
 505   /* See if this is a tail call we can handle.  */
 506   ret_var = TREE_OPERAND (stmt, 0);
 507   if (ret_var
 508       && TREE_CODE (ret_var) == GIMPLE_MODIFY_STMT)
 509     {
 510       tree ret_op = GIMPLE_STMT_OPERAND (ret_var, 1);
 511       STRIP_NOPS (ret_op);
 512       if (!tail_recursion
 513           && TREE_CODE (ret_op) != SSA_NAME)
 514         return;
 515
 516       if (!process_assignment (ret_var, stmt, bsi, &m, &a, &ass_var))
 517         return;
 518       ret_var = GIMPLE_STMT_OPERAND (ret_var, 0);
 519     }
 520
 521   /* We may proceed if there either is no return value, or the return value
 522      is identical to the call's return.  */
 523   if (ret_var
 524       && (ret_var != ass_var))
 525     return;
 526
 527   /* If this is not a tail recursive call, we cannot handle addends or
 528      multiplicands.  */
 529   if (!tail_recursion && (m || a))
 530     return;
 531
 532   nw = XNEW (struct tailcall);
 533
 534   nw->call_block = bb;
 535   nw->call_bsi = bsi;
 536
 537   nw->tail_recursion = tail_recursion;
 538
 539   nw->mult = m;
 540   nw->add = a;
 541
 542   nw->next = *ret;
 543   *ret = nw;
 544 }
 545
 546 /* Adjust the accumulator values according to A and M after BSI, and update
 547    the phi nodes on edge BACK.  */
 548
 549 static void
 550 adjust_accumulator_values (block_stmt_iterator bsi, tree m, tree a, edge back)
 551 {
 552   tree stmt, var, phi, tmp;
 553   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 554   tree a_acc_arg = a_acc, m_acc_arg = m_acc;
 555
 556   if (a)
 557     {
 558       if (m_acc)
 559         {
 560           if (integer_onep (a))
 561             var = m_acc;
 562           else
 563             {
 564               stmt = build_gimple_modify_stmt (NULL_TREE,
 565                                                build2 (MULT_EXPR, ret_type,
 566                                                        m_acc, a));
 567
 568               tmp = create_tmp_var (ret_type, "acc_tmp");
 569               add_referenced_var (tmp);
 570
 571               var = make_ssa_name (tmp, stmt);
 572               GIMPLE_STMT_OPERAND (stmt, 0) = var;
 573               bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 574             }
 575         }
 576       else
 577         var = a;
 578
 579       stmt = build_gimple_modify_stmt (NULL_TREE, build2 (PLUS_EXPR, ret_type,
 580                                                           a_acc, var));
 581       var = make_ssa_name (SSA_NAME_VAR (a_acc), stmt);
 582       GIMPLE_STMT_OPERAND (stmt, 0) = var;
 583       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 584       a_acc_arg = var;
 585     }
 586
 587   if (m)
 588     {
 589       stmt = build_gimple_modify_stmt (NULL_TREE,
 590                                        build2 (MULT_EXPR, ret_type,
 591                                                m_acc, m));
 592       var = make_ssa_name (SSA_NAME_VAR (m_acc), stmt);
 593       GIMPLE_STMT_OPERAND (stmt, 0) = var;
 594       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 595       m_acc_arg = var;
 596     }
 597
 598   if (a_acc)
 599     {
 600       for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
 601         if (PHI_RESULT (phi) == a_acc)
 602           break;
 603
 604       add_phi_arg (phi, a_acc_arg, back);
 605     }
 606
 607   if (m_acc)
 608     {
 609       for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
 610         if (PHI_RESULT (phi) == m_acc)
 611           break;
 612
 613       add_phi_arg (phi, m_acc_arg, back);
 614     }
 615 }
 616
 617 /* Adjust value of the return at the end of BB according to M and A
 618    accumulators.  */
 619
 620 static void
 621 adjust_return_value (basic_block bb, tree m, tree a)
 622 {
 623   tree ret_stmt = last_stmt (bb), ret_var, var, stmt, tmp;
 624   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 625   tree *ret_op;
 626   block_stmt_iterator bsi = bsi_last (bb);
 627
 628   gcc_assert (TREE_CODE (ret_stmt) == RETURN_EXPR);
 629
 630   ret_var = TREE_OPERAND (ret_stmt, 0);
 631   if (!ret_var)
 632     return;
 633
 634   if (TREE_CODE (ret_var) == GIMPLE_MODIFY_STMT)
 635     {
 636       ret_op = &GIMPLE_STMT_OPERAND (ret_var, 1);
 637       ret_var = *ret_op;
 638     }
 639   else
 640     ret_op = &TREE_OPERAND (ret_stmt, 0);
 641
 642   if (m)
 643     {
 644       stmt = build_gimple_modify_stmt (NULL_TREE,
 645                                        build2 (MULT_EXPR, ret_type,
 646                                                m_acc, ret_var));
 647
 648       tmp = create_tmp_var (ret_type, "acc_tmp");
 649       add_referenced_var (tmp);
 650
 651       var = make_ssa_name (tmp, stmt);
 652       GIMPLE_STMT_OPERAND (stmt, 0) = var;
 653       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 654     }
 655   else
 656     var = ret_var;
 657
 658   if (a)
 659     {
 660       stmt = build_gimple_modify_stmt (NULL_TREE,
 661                                        build2 (PLUS_EXPR, ret_type,
 662                                                a_acc, var));
 663
 664       tmp = create_tmp_var (ret_type, "acc_tmp");
 665       add_referenced_var (tmp);
 666
 667       var = make_ssa_name (tmp, stmt);
 668       GIMPLE_STMT_OPERAND (stmt, 0) = var;
 669       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 670     }
 671
 672   *ret_op = var;
 673   update_stmt (ret_stmt);
 674 }
 675
 676 /* Subtract COUNT and FREQUENCY from the basic block and it's
 677    outgoing edge.  */
 678 static void
 679 decrease_profile (basic_block bb, gcov_type count, int frequency)
 680 {
 681   edge e;
 682   bb->count -= count;
 683   if (bb->count < 0)
 684     bb->count = 0;
 685   bb->frequency -= frequency;
 686   if (bb->frequency < 0)
 687     bb->frequency = 0;
 688   if (!single_succ_p (bb))
 689     {
 690       gcc_assert (!EDGE_COUNT (bb->succs));
 691       return;
 692     }
 693   e = single_succ_edge (bb);
 694   e->count -= count;
 695   if (e->count < 0)
 696     e->count = 0;
 697 }
 698
 699 /* Returns true if argument PARAM of the tail recursive call needs to be copied
 700    when the call is eliminated.  */
 701
 702 static bool
 703 arg_needs_copy_p (tree param)
 704 {
 705   tree def;
 706
 707   if (!is_gimple_reg (param) || !var_ann (param))
 708     return false;
 709
 710   /* Parameters that are only defined but never used need not be copied.  */
 711   def = gimple_default_def (cfun, param);
 712   if (!def)
 713     return false;
 714
 715   return true;
 716 }
 717
 718 /* Eliminates tail call described by T.  TMP_VARS is a list of
 719    temporary variables used to copy the function arguments.  */
 720
 721 static void
 722 eliminate_tail_call (struct tailcall *t)
 723 {
 724   tree param, stmt, rslt, call;
 725   tree arg;
 726   call_expr_arg_iterator iter;
 727   basic_block bb, first;
 728   edge e;
 729   tree phi;
 730   block_stmt_iterator bsi;
 731   tree orig_stmt;
 732
 733   stmt = orig_stmt = bsi_stmt (t->call_bsi);
 734   bb = t->call_block;
 735
 736   if (dump_file && (dump_flags & TDF_DETAILS))
 737     {
 738       fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
 739                bb->index);
 740       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 741       fprintf (dump_file, "\n");
 742     }
 743
 744   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 745     stmt = GIMPLE_STMT_OPERAND (stmt, 1);
 746
 747   first = single_succ (ENTRY_BLOCK_PTR);
 748
 749   /* Remove the code after call_bsi that will become unreachable.  The
 750      possibly unreachable code in other blocks is removed later in
 751      cfg cleanup.  */
 752   bsi = t->call_bsi;
 753   bsi_next (&bsi);
 754   while (!bsi_end_p (bsi))
 755     {
 756       tree t = bsi_stmt (bsi);
 757       /* Do not remove the return statement, so that redirect_edge_and_branch
 758          sees how the block ends.  */
 759       if (TREE_CODE (t) == RETURN_EXPR)
 760         break;
 761
 762       bsi_remove (&bsi, true);
 763       release_defs (t);
 764     }
 765
 766   /* Number of executions of function has reduced by the tailcall.  */
 767   e = single_succ_edge (t->call_block);
 768   decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
 769   decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
 770   if (e->dest != EXIT_BLOCK_PTR)
 771     decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
 772
 773   /* Replace the call by a jump to the start of function.  */
 774   e = redirect_edge_and_branch (single_succ_edge (t->call_block), first);
 775   gcc_assert (e);
 776   PENDING_STMT (e) = NULL_TREE;
 777
 778   /* Add phi node entries for arguments.  The ordering of the phi nodes should
 779      be the same as the ordering of the arguments.  */
 780   for (param = DECL_ARGUMENTS (current_function_decl),
 781          arg = first_call_expr_arg (stmt, &iter),
 782          phi = phi_nodes (first);
 783        param;
 784        param = TREE_CHAIN (param), arg = next_call_expr_arg (&iter))
 785     {
 786       if (!arg_needs_copy_p (param))
 787         continue;
 788       gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
 789
 790       add_phi_arg (phi, arg, e);
 791       phi = PHI_CHAIN (phi);
 792     }
 793
 794   /* Update the values of accumulators.  */
 795   adjust_accumulator_values (t->call_bsi, t->mult, t->add, e);
 796
 797   call = bsi_stmt (t->call_bsi);
 798   if (TREE_CODE (call) == GIMPLE_MODIFY_STMT)
 799     {
 800       rslt = GIMPLE_STMT_OPERAND (call, 0);
 801
 802       /* Result of the call will no longer be defined.  So adjust the
 803          SSA_NAME_DEF_STMT accordingly.  */
 804       SSA_NAME_DEF_STMT (rslt) = build_empty_stmt ();
 805     }
 806
 807   bsi_remove (&t->call_bsi, true);
 808   release_defs (call);
 809 }
 810
 811 /* Add phi nodes for the virtual operands defined in the function to the
 812    header of the loop created by tail recursion elimination.
 813
 814    Originally, we used to add phi nodes only for call clobbered variables,
 815    as the value of the non-call clobbered ones obviously cannot be used
 816    or changed within the recursive call.  However, the local variables
 817    from multiple calls now share the same location, so the virtual ssa form
 818    requires us to say that the location dies on further iterations of the loop,
 819    which requires adding phi nodes.
 820 */
 821 static void
 822 add_virtual_phis (void)
 823 {
 824   referenced_var_iterator rvi;
 825   tree var;
 826
 827   /* The problematic part is that there is no way how to know what
 828      to put into phi nodes (there in fact does not have to be such
 829      ssa name available).  A solution would be to have an artificial
 830      use/kill for all virtual operands in EXIT node.  Unless we have
 831      this, we cannot do much better than to rebuild the ssa form for
 832      possibly affected virtual ssa names from scratch.  */
 833
 834   FOR_EACH_REFERENCED_VAR (var, rvi)
 835     {
 836       if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE)
 837         mark_sym_for_renaming (var);
 838     }
 839 }
 840
 841 /* Optimizes the tailcall described by T.  If OPT_TAILCALLS is true, also
 842    mark the tailcalls for the sibcall optimization.  */
 843
 844 static bool
 845 optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
 846 {
 847   if (t->tail_recursion)
 848     {
 849       eliminate_tail_call (t);
 850       return true;
 851     }
 852
 853   if (opt_tailcalls)
 854     {
 855       tree stmt = bsi_stmt (t->call_bsi);
 856
 857       stmt = get_call_expr_in (stmt);
 858       CALL_EXPR_TAILCALL (stmt) = 1;
 859       if (dump_file && (dump_flags & TDF_DETAILS))
 860         {
 861           fprintf (dump_file, "Found tail call ");
 862           print_generic_expr (dump_file, stmt, dump_flags);
 863           fprintf (dump_file, " in bb %i\n", t->call_block->index);
 864         }
 865     }
 866
 867   return false;
 868 }
 869
 870 /* Optimizes tail calls in the function, turning the tail recursion
 871    into iteration.  */
 872
 873 static unsigned int
 874 tree_optimize_tail_calls_1 (bool opt_tailcalls)
 875 {
 876   edge e;
 877   bool phis_constructed = false;
 878   struct tailcall *tailcalls = NULL, *act, *next;
 879   bool changed = false;
 880   basic_block first = single_succ (ENTRY_BLOCK_PTR);
 881   tree stmt, param, ret_type, tmp, phi;
 882   edge_iterator ei;
 883
 884   if (!suitable_for_tail_opt_p ())
 885     return 0;
 886   if (opt_tailcalls)
 887     opt_tailcalls = suitable_for_tail_call_opt_p ();
 888
 889   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 890     {
 891       /* Only traverse the normal exits, i.e. those that end with return
 892          statement.  */
 893       stmt = last_stmt (e->src);
 894
 895       if (stmt
 896           && TREE_CODE (stmt) == RETURN_EXPR)
 897         find_tail_calls (e->src, &tailcalls);
 898     }
 899
 900   /* Construct the phi nodes and accumulators if necessary.  */
 901   a_acc = m_acc = NULL_TREE;
 902   for (act = tailcalls; act; act = act->next)
 903     {
 904       if (!act->tail_recursion)
 905         continue;
 906
 907       if (!phis_constructed)
 908         {
 909           /* Ensure that there is only one predecessor of the block.  */
 910           if (!single_pred_p (first))
 911             first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
 912
 913           /* Copy the args if needed.  */
 914           for (param = DECL_ARGUMENTS (current_function_decl);
 915                param;
 916                param = TREE_CHAIN (param))
 917             if (arg_needs_copy_p (param))
 918               {
 919                 tree name = gimple_default_def (cfun, param);
 920                 tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
 921                 tree phi;
 922
 923                 set_default_def (param, new_name);
 924                 phi = create_phi_node (name, first);
 925                 SSA_NAME_DEF_STMT (name) = phi;
 926                 add_phi_arg (phi, new_name, single_pred_edge (first));
 927               }
 928           phis_constructed = true;
 929         }
 930
 931       if (act->add && !a_acc)
 932         {
 933           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 934
 935           tmp = create_tmp_var (ret_type, "add_acc");
 936           add_referenced_var (tmp);
 937
 938           phi = create_phi_node (tmp, first);
 939           add_phi_arg (phi,
 940                        /* RET_TYPE can be a float when -ffast-maths is
 941                           enabled.  */
 942                        fold_convert (ret_type, integer_zero_node),
 943                        single_pred_edge (first));
 944           a_acc = PHI_RESULT (phi);
 945         }
 946
 947       if (act->mult && !m_acc)
 948         {
 949           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 950
 951           tmp = create_tmp_var (ret_type, "mult_acc");
 952           add_referenced_var (tmp);
 953
 954           phi = create_phi_node (tmp, first);
 955           add_phi_arg (phi,
 956                        /* RET_TYPE can be a float when -ffast-maths is
 957                           enabled.  */
 958                        fold_convert (ret_type, integer_one_node),
 959                        single_pred_edge (first));
 960           m_acc = PHI_RESULT (phi);
 961         }
 962     }
 963
 964
 965   if (phis_constructed)
 966     {
 967       /* Reverse the order of the phi nodes, so that it matches the order
 968          of operands of the function, as assumed by eliminate_tail_call.  */
 969       set_phi_nodes (first, phi_reverse (phi_nodes (first)));
 970     }
 971
 972   for (; tailcalls; tailcalls = next)
 973     {
 974       next = tailcalls->next;
 975       changed |= optimize_tail_call (tailcalls, opt_tailcalls);
 976       free (tailcalls);
 977     }
 978
 979   if (a_acc || m_acc)
 980     {
 981       /* Modify the remaining return statements.  */
 982       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 983         {
 984           stmt = last_stmt (e->src);
 985
 986           if (stmt
 987               && TREE_CODE (stmt) == RETURN_EXPR)
 988             adjust_return_value (e->src, m_acc, a_acc);
 989         }
 990     }
 991
 992   if (changed)
 993     free_dominance_info (CDI_DOMINATORS);
 994
 995   if (phis_constructed)
 996     add_virtual_phis ();
 997   if (changed)
 998     return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
 999   return 0;
1000 }
1001
1002 static unsigned int
1003 execute_tail_recursion (void)
1004 {
1005   return tree_optimize_tail_calls_1 (false);
1006 }
1007
1008 static bool
1009 gate_tail_calls (void)
1010 {
1011   return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call);
1012 }
1013
1014 static unsigned int
1015 execute_tail_calls (void)
1016 {
1017   return tree_optimize_tail_calls_1 (true);
1018 }
1019
1020 struct tree_opt_pass pass_tail_recursion =
1021 {
1022   "tailr",                              /* name */
1023   gate_tail_calls,                      /* gate */
1024   execute_tail_recursion,               /* execute */
1025   NULL,                                 /* sub */
1026   NULL,                                 /* next */
1027   0,                                    /* static_pass_number */
1028   0,                                    /* tv_id */
1029   PROP_cfg | PROP_ssa,                  /* properties_required */
1030   0,                                    /* properties_provided */
1031   0,                                    /* properties_destroyed */
1032   0,                                    /* todo_flags_start */
1033   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
1034   0                                     /* letter */
1035 };
1036
1037 struct tree_opt_pass pass_tail_calls =
1038 {
1039   "tailc",                              /* name */
1040   gate_tail_calls,                      /* gate */
1041   execute_tail_calls,                   /* execute */
1042   NULL,                                 /* sub */
1043   NULL,                                 /* next */
1044   0,                                    /* static_pass_number */
1045   0,                                    /* tv_id */
1046   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1047   0,                                    /* properties_provided */
1048   0,                                    /* properties_destroyed */
1049   0,                                    /* todo_flags_start */
1050   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
1051   0                                     /* letter */
1052 };