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