gcc/tree-tailcall.c

   1 /* Tail calls optimization on trees.
   2    Copyright (C) 2003 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, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, 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    analyse 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 later 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       clasical 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   int i;
 136
 137   if (current_function_stdarg)
 138     return false;
 139
 140   /* No local variable should be call-clobbered.  We ignore any kind
 141      of memory tag, as these are not real variables.  */
 142   for (i = 0; i < (int) VARRAY_ACTIVE_SIZE (referenced_vars); i++)
 143     {
 144       tree var = VARRAY_TREE (referenced_vars, i);
 145
 146       if (decl_function_context (var) == current_function_decl
 147           && !TREE_STATIC (var)
 148           && var_ann (var)->mem_tag_kind == NOT_A_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   /* alloca (until we have stack slot life analysis) inhibits
 164      sibling call optimizations, but not tail recursion.  */
 165   if (current_function_calls_alloca)
 166     return false;
 167
 168   /* If we are using sjlj exceptions, we may need to add a call to
 169      _Unwind_SjLj_Unregister at exit of the function.  Which means
 170      that we cannot do any sibcall transformations.  */
 171   if (USING_SJLJ_EXCEPTIONS && current_function_has_exception_handlers ())
 172     return false;
 173
 174   /* Any function that calls setjmp might have longjmp called from
 175      any called function.  ??? We really should represent this
 176      properly in the CFG so that this needn't be special cased.  */
 177   if (current_function_calls_setjmp)
 178     return false;
 179
 180   return true;
 181 }
 182
 183 /* Checks whether the expression EXPR in stmt AT is independent of the
 184    statement pointed by BSI (in a sense that we already know EXPR's value
 185    at BSI).  We use the fact that we are only called from the chain of
 186    basic blocks that have only single successor.  Returns the expression
 187    containing the value of EXPR at BSI.  */
 188
 189 static tree
 190 independent_of_stmt_p (tree expr, tree at, block_stmt_iterator bsi)
 191 {
 192   basic_block bb, call_bb, at_bb;
 193   edge e;
 194
 195   if (is_gimple_min_invariant (expr))
 196     return expr;
 197
 198   if (TREE_CODE (expr) != SSA_NAME)
 199     return NULL_TREE;
 200
 201   /* Mark the blocks in the chain leading to the end.  */
 202   at_bb = bb_for_stmt (at);
 203   call_bb = bb_for_stmt (bsi_stmt (bsi));
 204   for (bb = call_bb; bb != at_bb; bb = bb->succ->dest)
 205     bb->aux = &bb->aux;
 206   bb->aux = &bb->aux;
 207
 208   while (1)
 209     {
 210       at = SSA_NAME_DEF_STMT (expr);
 211       bb = bb_for_stmt (at);
 212
 213       /* The default defininition or defined before the chain.  */
 214       if (!bb || !bb->aux)
 215         break;
 216
 217       if (bb == call_bb)
 218         {
 219           for (; !bsi_end_p (bsi); bsi_next (&bsi))
 220             if (bsi_stmt (bsi) == at)
 221               break;
 222
 223           if (!bsi_end_p (bsi))
 224             expr = NULL_TREE;
 225           break;
 226         }
 227
 228       if (TREE_CODE (at) != PHI_NODE)
 229         {
 230           expr = NULL_TREE;
 231           break;
 232         }
 233
 234       for (e = bb->pred; e; e = e->pred_next)
 235         if (e->src->aux)
 236           break;
 237       if (!e)
 238         abort ();
 239
 240       expr = phi_element_for_edge (at, e)->def;
 241     }
 242
 243   /* Unmark the blocks.  */
 244   for (bb = call_bb; bb != at_bb; bb = bb->succ->dest)
 245     bb->aux = NULL;
 246   bb->aux = NULL;
 247
 248   return expr;
 249 }
 250
 251 /* Simulates the effect of an assignment of ASS in STMT on the return value
 252    of the tail recursive CALL passed in ASS_VAR.  M and A are the
 253    multiplicative and the additive factor for the real return value.  */
 254
 255 static bool
 256 process_assignment (tree ass, tree stmt, block_stmt_iterator call, tree *m,
 257                     tree *a, tree *ass_var)
 258 {
 259   tree op0, op1, non_ass_var;
 260   tree dest = TREE_OPERAND (ass, 0);
 261   tree src = TREE_OPERAND (ass, 1);
 262   enum tree_code code = TREE_CODE (src);
 263   tree src_var = src;
 264
 265   /* See if this is a simple copy operation of an SSA name to the function
 266      result.  In that case we may have a simple tail call.  Ignore type
 267      conversions that can never produce extra code between the function
 268      call and the function return.  */
 269   STRIP_NOPS (src_var);
 270   if (TREE_CODE (src_var) == SSA_NAME)
 271     {
 272       if (src_var != *ass_var)
 273         return false;
 274
 275       *ass_var = dest;
 276       return true;
 277     }
 278
 279   if (TREE_CODE_CLASS (code) != '2')
 280     return false;
 281
 282   /* We only handle the code like
 283
 284      x = call ();
 285      y = m * x;
 286      z = y + a;
 287      return z;
 288
 289      TODO -- Extend it for cases where the linear transformation of the output
 290      is expressed in a more complicated way.  */
 291
 292   op0 = TREE_OPERAND (src, 0);
 293   op1 = TREE_OPERAND (src, 1);
 294
 295   if (op0 == *ass_var
 296       && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
 297     ;
 298   else if (op1 == *ass_var
 299            && (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
 300     ;
 301   else
 302     return false;
 303
 304   switch (code)
 305     {
 306     case PLUS_EXPR:
 307       /* There should be no previous addition.  TODO -- it should be fairly
 308          straightforward to lift this restriction -- just allow storing
 309          more complicated expressions in *A, and gimplify it in
 310          adjust_accumulator_values.  */
 311       if (*a)
 312         return false;
 313       *a = non_ass_var;
 314       *ass_var = dest;
 315       return true;
 316
 317     case MULT_EXPR:
 318       /* Similar remark applies here.  Handling multiplication after addition
 319          is just slightly more complicated -- we need to multiply both *A and
 320          *M.  */
 321       if (*a || *m)
 322         return false;
 323       *m = non_ass_var;
 324       *ass_var = dest;
 325       return true;
 326
 327       /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR).  */
 328
 329     default:
 330       return false;
 331     }
 332 }
 333
 334 /* Propagate VAR through phis on edge E.  */
 335
 336 static tree
 337 propagate_through_phis (tree var, edge e)
 338 {
 339   basic_block dest = e->dest;
 340   tree phi;
 341
 342   for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
 343     if (phi_element_for_edge (phi, e)->def == var)
 344       return PHI_RESULT (phi);
 345
 346   return var;
 347 }
 348
 349 /* Finds tailcalls falling into basic block BB. The list of found tailcalls is
 350    added to the start of RET.  */
 351
 352 static void
 353 find_tail_calls (basic_block bb, struct tailcall **ret)
 354 {
 355   tree ass_var, ret_var, stmt, func, param, args, call = NULL_TREE;
 356   block_stmt_iterator bsi, absi;
 357   bool tail_recursion;
 358   struct tailcall *nw;
 359   edge e;
 360   tree m, a;
 361   basic_block abb;
 362   stmt_ann_t ann;
 363
 364   if (bb->succ->succ_next)
 365     return;
 366
 367   for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
 368     {
 369       stmt = bsi_stmt (bsi);
 370
 371       /* Ignore labels.  */
 372       if (TREE_CODE (stmt) == LABEL_EXPR)
 373         continue;
 374
 375       get_stmt_operands (stmt);
 376
 377       /* Check for a call.  */
 378       if (TREE_CODE (stmt) == MODIFY_EXPR)
 379         {
 380           ass_var = TREE_OPERAND (stmt, 0);
 381           call = TREE_OPERAND (stmt, 1);
 382         }
 383       else
 384         {
 385           ass_var = NULL_TREE;
 386           call = stmt;
 387         }
 388
 389       if (TREE_CODE (call) == CALL_EXPR)
 390         break;
 391
 392       /* If the statement has virtual operands, fail.  */
 393       ann = stmt_ann (stmt);
 394       if (NUM_VDEFS (VDEF_OPS (ann))
 395           || NUM_VUSES (VUSE_OPS (ann)))
 396         return;
 397     }
 398
 399   if (bsi_end_p (bsi))
 400     {
 401       /* Recurse to the predecessors.  */
 402       for (e = bb->pred; e; e = e->pred_next)
 403         find_tail_calls (e->src, ret);
 404
 405       return;
 406     }
 407
 408   /* We found the call, check whether it is suitable.  */
 409   tail_recursion = false;
 410   func = get_callee_fndecl (call);
 411   if (func == current_function_decl)
 412     {
 413       for (param = DECL_ARGUMENTS (func), args = TREE_OPERAND (call, 1);
 414            param && args;
 415            param = TREE_CHAIN (param), args = TREE_CHAIN (args))
 416         {
 417           tree arg = TREE_VALUE (args);
 418           if (param != arg
 419               /* Make sure there are no problems with copying.  Note we must
 420                  have a copyable type and the two arguments must have reasonably
 421                  equivalent types.  The latter requirement could be relaxed if
 422                  we emitted a suitable type conversion statement.  */
 423               && (!is_gimple_reg_type (TREE_TYPE (param))
 424                   || !lang_hooks.types_compatible_p (TREE_TYPE (param),
 425                                                      TREE_TYPE (arg))))
 426             break;
 427         }
 428       if (!args && !param)
 429         tail_recursion = true;
 430     }
 431
 432   /* Now check the statements after the call.  None of them has virtual
 433      operands, so they may only depend on the call through its return
 434      value.  The return value should also be dependent on each of them,
 435      since we are running after dce.  */
 436   m = NULL_TREE;
 437   a = NULL_TREE;
 438
 439   abb = bb;
 440   absi = bsi;
 441   while (1)
 442     {
 443       bsi_next (&absi);
 444
 445       while (bsi_end_p (absi))
 446         {
 447           ass_var = propagate_through_phis (ass_var, abb->succ);
 448           abb = abb->succ->dest;
 449           absi = bsi_start (abb);
 450         }
 451
 452       stmt = bsi_stmt (absi);
 453
 454       if (TREE_CODE (stmt) == LABEL_EXPR)
 455         continue;
 456
 457       if (TREE_CODE (stmt) == RETURN_EXPR)
 458         break;
 459
 460       if (TREE_CODE (stmt) != MODIFY_EXPR)
 461         return;
 462
 463       /* Unless this is a tail recursive call, we cannot do anything with
 464          the statement anyway.  */
 465       if (!tail_recursion)
 466         return;
 467
 468       if (!process_assignment (stmt, stmt, bsi, &m, &a, &ass_var))
 469         return;
 470     }
 471
 472   /* See if this is a tail call we can handle.  */
 473   ret_var = TREE_OPERAND (stmt, 0);
 474   if (ret_var
 475       && TREE_CODE (ret_var) == MODIFY_EXPR)
 476     {
 477       tree ret_op = TREE_OPERAND (ret_var, 1);
 478       STRIP_NOPS (ret_op);
 479       if (!tail_recursion
 480           && TREE_CODE (ret_op) != SSA_NAME)
 481         return;
 482
 483       if (!process_assignment (ret_var, stmt, bsi, &m, &a, &ass_var))
 484         return;
 485       ret_var = TREE_OPERAND (ret_var, 0);
 486     }
 487
 488   /* We may proceed if there either is no return value, or the return value
 489      is identical to the call's return.  */
 490   if (ret_var
 491       && (ret_var != ass_var))
 492     return;
 493
 494   nw = xmalloc (sizeof (struct tailcall));
 495
 496   nw->call_block = bb;
 497   nw->call_bsi = bsi;
 498
 499   nw->tail_recursion = tail_recursion;
 500
 501   nw->mult = m;
 502   nw->add = a;
 503
 504   nw->next = *ret;
 505   *ret = nw;
 506 }
 507
 508 /* Adjust the accumulator values according to A and M after BSI, and update
 509    the phi nodes on edge BACK.  */
 510
 511 static void
 512 adjust_accumulator_values (block_stmt_iterator bsi, tree m, tree a, edge back)
 513 {
 514   tree stmt, var, phi, tmp;
 515   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 516   tree a_acc_arg = a_acc, m_acc_arg = m_acc;
 517
 518   if (a)
 519     {
 520       if (m_acc)
 521         {
 522           if (integer_onep (a))
 523             var = m_acc;
 524           else
 525             {
 526               stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 527                             build (MULT_EXPR, ret_type, m_acc, a));
 528
 529               tmp = create_tmp_var (ret_type, "acc_tmp");
 530               add_referenced_tmp_var (tmp);
 531
 532               var = make_ssa_name (tmp, stmt);
 533               TREE_OPERAND (stmt, 0) = var;
 534               bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 535             }
 536         }
 537       else
 538         var = a;
 539
 540       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 541                     build (PLUS_EXPR, ret_type, a_acc, var));
 542       var = make_ssa_name (SSA_NAME_VAR (a_acc), stmt);
 543       TREE_OPERAND (stmt, 0) = var;
 544       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 545       a_acc_arg = var;
 546     }
 547
 548   if (m)
 549     {
 550       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 551                     build (MULT_EXPR, ret_type, m_acc, m));
 552       var = make_ssa_name (SSA_NAME_VAR (m_acc), stmt);
 553       TREE_OPERAND (stmt, 0) = var;
 554       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
 555       m_acc_arg = var;
 556     }
 557
 558   if (a_acc)
 559     {
 560       for (phi = phi_nodes (back->dest); phi; phi = TREE_CHAIN (phi))
 561         if (PHI_RESULT (phi) == a_acc)
 562           break;
 563
 564       add_phi_arg (&phi, a_acc_arg, back);
 565     }
 566
 567   if (m_acc)
 568     {
 569       for (phi = phi_nodes (back->dest); phi; phi = TREE_CHAIN (phi))
 570         if (PHI_RESULT (phi) == m_acc)
 571           break;
 572
 573       add_phi_arg (&phi, m_acc_arg, back);
 574     }
 575 }
 576
 577 /* Adjust value of the return at the end of BB accodring to M and A
 578    accumulators.  */
 579
 580 static void
 581 adjust_return_value (basic_block bb, tree m, tree a)
 582 {
 583   tree ret_stmt = last_stmt (bb), ret_var, var, stmt, tmp;
 584   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 585   block_stmt_iterator bsi = bsi_last (bb);
 586
 587   if (TREE_CODE (ret_stmt) != RETURN_EXPR)
 588     abort ();
 589
 590   ret_var = TREE_OPERAND (ret_stmt, 0);
 591   if (!ret_var)
 592     return;
 593
 594   if (TREE_CODE (ret_var) == MODIFY_EXPR)
 595     {
 596       ret_var->common.ann = (tree_ann) stmt_ann (ret_stmt);
 597       bsi_replace (&bsi, ret_var, true);
 598       SSA_NAME_DEF_STMT (TREE_OPERAND (ret_var, 0)) = ret_var;
 599       ret_var = TREE_OPERAND (ret_var, 0);
 600       ret_stmt = build1 (RETURN_EXPR, TREE_TYPE (ret_stmt), ret_var);
 601       bsi_insert_after (&bsi, ret_stmt, BSI_NEW_STMT);
 602     }
 603
 604   if (m)
 605     {
 606       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 607                     build (MULT_EXPR, ret_type, m_acc, ret_var));
 608
 609       tmp = create_tmp_var (ret_type, "acc_tmp");
 610       add_referenced_tmp_var (tmp);
 611
 612       var = make_ssa_name (tmp, stmt);
 613       TREE_OPERAND (stmt, 0) = var;
 614       bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
 615     }
 616   else
 617     var = ret_var;
 618
 619   if (a)
 620     {
 621       stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
 622                     build (PLUS_EXPR, ret_type, a_acc, var));
 623
 624       tmp = create_tmp_var (ret_type, "acc_tmp");
 625       add_referenced_tmp_var (tmp);
 626
 627       var = make_ssa_name (tmp, stmt);
 628       TREE_OPERAND (stmt, 0) = var;
 629       bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
 630     }
 631
 632   TREE_OPERAND (ret_stmt, 0) = var;
 633   modify_stmt (ret_stmt);
 634 }
 635
 636 /* Eliminates tail call described by T.  TMP_VARS is a list of
 637    temporary variables used to copy the function arguments.  */
 638
 639 static void
 640 eliminate_tail_call (struct tailcall *t)
 641 {
 642   tree param, stmt, args, rslt, call;
 643   basic_block bb, first;
 644   edge e;
 645   tree phi;
 646   stmt_ann_t ann;
 647   vdef_optype vdefs;
 648   unsigned i;
 649
 650   stmt = bsi_stmt (t->call_bsi);
 651   get_stmt_operands (stmt);
 652   ann = stmt_ann (stmt);
 653   bb = t->call_block;
 654
 655   if (dump_file && (dump_flags & TDF_DETAILS))
 656     {
 657       fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
 658                bb->index);
 659       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 660       fprintf (dump_file, "\n");
 661     }
 662
 663   if (TREE_CODE (stmt) == MODIFY_EXPR)
 664     stmt = TREE_OPERAND (stmt, 1);
 665
 666   first = ENTRY_BLOCK_PTR->succ->dest;
 667
 668   /* Replace the call by a jump to the start of function.  */
 669   e = redirect_edge_and_branch (t->call_block->succ, first);
 670   if (!e)
 671     abort ();
 672   PENDING_STMT (e) = NULL_TREE;
 673
 674   /* Add phi node entries for arguments.  Not every PHI node corresponds to
 675      a function argument (there may be PHI nodes for virtual definitions of the
 676      eliminated calls), so we search for a PHI corresponding to each argument
 677      rather than searching for which argument a PHI node corresponds to.  */
 678
 679   for (param = DECL_ARGUMENTS (current_function_decl),
 680        args = TREE_OPERAND (stmt, 1);
 681        param;
 682        param = TREE_CHAIN (param),
 683        args = TREE_CHAIN (args))
 684     {
 685
 686       for (phi = phi_nodes (first); phi; phi = TREE_CHAIN (phi))
 687         if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
 688           break;
 689
 690       /* The phi node indeed does not have to be there, in case the operand is
 691          invariant in the function.  */
 692       if (!phi)
 693         continue;
 694
 695       add_phi_arg (&phi, TREE_VALUE (args), e);
 696     }
 697
 698   /* Add phi nodes for the call clobbered variables.  */
 699   vdefs = VDEF_OPS (ann);
 700   for (i = 0; i < NUM_VDEFS (vdefs); i++)
 701     {
 702       param = SSA_NAME_VAR (VDEF_RESULT (vdefs, i));
 703       for (phi = phi_nodes (first); phi; phi = TREE_CHAIN (phi))
 704         if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
 705           break;
 706
 707       if (!phi)
 708         {
 709           tree name = var_ann (param)->default_def;
 710           tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
 711
 712           var_ann (param)->default_def = new_name;
 713           phi = create_phi_node (name, first);
 714           SSA_NAME_DEF_STMT (name) = phi;
 715           add_phi_arg (&phi, new_name, ENTRY_BLOCK_PTR->succ);
 716
 717           /* For all calls the same set of variables should be clobbered.  This
 718              means that there always should be the appropriate phi node except
 719              for the first time we eliminate the call.  */
 720           if (first->pred->pred_next->pred_next)
 721             abort ();
 722         }
 723
 724       add_phi_arg (&phi, VDEF_OP (vdefs, i), e);
 725     }
 726
 727   /* Update the values of accumulators.  */
 728   adjust_accumulator_values (t->call_bsi, t->mult, t->add, e);
 729
 730   call = bsi_stmt (t->call_bsi);
 731   if (TREE_CODE (call) == MODIFY_EXPR)
 732     {
 733       rslt = TREE_OPERAND (call, 0);
 734
 735       /* Result of the call will no longer be defined.  So adjust the
 736          SSA_NAME_DEF_STMT accordingly.  */
 737       SSA_NAME_DEF_STMT (rslt) = build_empty_stmt ();
 738     }
 739
 740   bsi_remove (&t->call_bsi);
 741 }
 742
 743 /* Optimizes the tailcall described by T.  If OPT_TAILCALLS is true, also
 744    mark the tailcalls for the sibcall optimization.  */
 745
 746 static bool
 747 optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
 748 {
 749   if (t->tail_recursion)
 750     {
 751       eliminate_tail_call (t);
 752       return true;
 753     }
 754
 755   if (opt_tailcalls)
 756     {
 757       tree stmt = bsi_stmt (t->call_bsi);
 758
 759       if (TREE_CODE (stmt) == MODIFY_EXPR)
 760         stmt = TREE_OPERAND (stmt, 1);
 761       if (TREE_CODE (stmt) != CALL_EXPR)
 762         abort ();
 763       CALL_EXPR_TAILCALL (stmt) = 1;
 764       if (dump_file && (dump_flags & TDF_DETAILS))
 765         {
 766           fprintf (dump_file, "Found tail call ");
 767           print_generic_expr (dump_file, stmt, dump_flags);
 768           fprintf (dump_file, " in bb %i\n", t->call_block->index);
 769         }
 770     }
 771
 772   return false;
 773 }
 774
 775 /* Optimizes tail calls in the function, turning the tail recursion
 776    into iteration.  */
 777
 778 static void
 779 tree_optimize_tail_calls_1 (bool opt_tailcalls)
 780 {
 781   edge e;
 782   bool phis_constructed = false;
 783   struct tailcall *tailcalls = NULL, *act, *next;
 784   bool changed = false;
 785   basic_block first = ENTRY_BLOCK_PTR->succ->dest;
 786   tree stmt, param, ret_type, tmp, phi;
 787
 788   if (!suitable_for_tail_opt_p ())
 789     return;
 790   if (opt_tailcalls)
 791     opt_tailcalls = suitable_for_tail_call_opt_p ();
 792
 793   for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
 794     {
 795       /* Only traverse the normal exits, i.e. those that end with return
 796          statement.  */
 797       stmt = last_stmt (e->src);
 798
 799       if (stmt
 800           && TREE_CODE (stmt) == RETURN_EXPR)
 801         find_tail_calls (e->src, &tailcalls);
 802     }
 803
 804   /* Construct the phi nodes and accumulators if necessary.  */
 805   a_acc = m_acc = NULL_TREE;
 806   for (act = tailcalls; act; act = act->next)
 807     {
 808       if (!act->tail_recursion)
 809         continue;
 810
 811       if (!phis_constructed)
 812         {
 813           /* Ensure that there is only one predecessor of the block.  */
 814           if (first->pred->pred_next)
 815             first = split_edge (ENTRY_BLOCK_PTR->succ);
 816
 817           /* Copy the args if needed.  */
 818           for (param = DECL_ARGUMENTS (current_function_decl);
 819                param;
 820                param = TREE_CHAIN (param))
 821             if (var_ann (param)
 822                 /* Also parameters that are only defined but never used need not
 823                    be copied.  */
 824                 && (var_ann (param)->default_def
 825                     && TREE_CODE (var_ann (param)->default_def) == SSA_NAME))
 826             {
 827               tree name = var_ann (param)->default_def;
 828               tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
 829               tree phi;
 830
 831               var_ann (param)->default_def = new_name;
 832               phi = create_phi_node (name, first);
 833               SSA_NAME_DEF_STMT (name) = phi;
 834               add_phi_arg (&phi, new_name, first->pred);
 835             }
 836           phis_constructed = true;
 837         }
 838
 839       if (act->add && !a_acc)
 840         {
 841           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 842
 843           tmp = create_tmp_var (ret_type, "add_acc");
 844           add_referenced_tmp_var (tmp);
 845
 846           phi = create_phi_node (tmp, first);
 847           add_phi_arg (&phi, convert (ret_type, integer_zero_node),
 848                        first->pred);
 849           a_acc = PHI_RESULT (phi);
 850         }
 851
 852       if (act->mult && !m_acc)
 853         {
 854           ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
 855
 856           tmp = create_tmp_var (ret_type, "mult_acc");
 857           add_referenced_tmp_var (tmp);
 858
 859           phi = create_phi_node (tmp, first);
 860           add_phi_arg (&phi, convert (ret_type, integer_one_node),
 861                        first->pred);
 862           m_acc = PHI_RESULT (phi);
 863         }
 864     }
 865
 866   for (; tailcalls; tailcalls = next)
 867     {
 868       next = tailcalls->next;
 869       changed |= optimize_tail_call (tailcalls, opt_tailcalls);
 870       free (tailcalls);
 871     }
 872
 873   if (a_acc || m_acc)
 874     {
 875       /* Modify the remaining return statements.  */
 876       for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
 877         {
 878           stmt = last_stmt (e->src);
 879
 880           if (stmt
 881               && TREE_CODE (stmt) == RETURN_EXPR)
 882             adjust_return_value (e->src, m_acc, a_acc);
 883         }
 884     }
 885
 886   if (changed)
 887     {
 888       free_dominance_info (CDI_DOMINATORS);
 889       cleanup_tree_cfg ();
 890     }
 891 }
 892
 893 static void
 894 execute_tail_recursion (void)
 895 {
 896   tree_optimize_tail_calls_1 (false);
 897 }
 898
 899 static bool
 900 gate_tail_calls (void)
 901 {
 902   return flag_optimize_sibling_calls != 0;
 903 }
 904
 905 static void
 906 execute_tail_calls (void)
 907 {
 908   tree_optimize_tail_calls_1 (true);
 909 }
 910
 911 struct tree_opt_pass pass_tail_recursion =
 912 {
 913   "tailr",                              /* name */
 914   NULL,                                 /* gate */
 915   execute_tail_recursion,               /* execute */
 916   NULL,                                 /* sub */
 917   NULL,                                 /* next */
 918   0,                                    /* static_pass_number */
 919   0,                                    /* tv_id */
 920   PROP_cfg | PROP_ssa,                  /* properties_required */
 921   0,                                    /* properties_provided */
 922   0,                                    /* properties_destroyed */
 923   0,                                    /* todo_flags_start */
 924   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
 925 };
 926
 927 struct tree_opt_pass pass_tail_calls =
 928 {
 929   "tailc",                              /* name */
 930   gate_tail_calls,                      /* gate */
 931   execute_tail_calls,                   /* execute */
 932   NULL,                                 /* sub */
 933   NULL,                                 /* next */
 934   0,                                    /* static_pass_number */
 935   0,                                    /* tv_id */
 936   PROP_cfg | PROP_ssa,                  /* properties_required */
 937   0,                                    /* properties_provided */
 938   0,                                    /* properties_destroyed */
 939   0,                                    /* todo_flags_start */
 940   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
 941 };