gcc/tree-tailcall.c

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