1/* Tail call optimization on trees. 2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 3 Free Software Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 3, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 21#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "tm.h" 25#include "tree.h" 26#include "rtl.h" 27#include "tm_p.h" 28#include "hard-reg-set.h" 29#include "basic-block.h" 30#include "function.h" 31#include "tree-flow.h" 32#include "tree-dump.h" 33#include "diagnostic.h" 34#include "except.h" 35#include "tree-pass.h" 36#include "flags.h" 37#include "langhooks.h" 38#include "dbgcnt.h" 39 40/* The file implements the tail recursion elimination. It is also used to 41 analyze the tail calls in general, passing the results to the rtl level 42 where they are used for sibcall optimization. 43 44 In addition to the standard tail recursion elimination, we handle the most 45 trivial cases of making the call tail recursive by creating accumulators. 46 For example the following function 47 48 int sum (int n) 49 { 50 if (n > 0) 51 return n + sum (n - 1); 52 else 53 return 0; 54 } 55 56 is transformed into 57 58 int sum (int n) 59 { 60 int acc = 0; 61 62 while (n > 0) 63 acc += n--; 64 65 return acc; 66 } 67 68 To do this, we maintain two accumulators (a_acc and m_acc) that indicate 69 when we reach the return x statement, we should return a_acc + x * m_acc 70 instead. They are initially initialized to 0 and 1, respectively, 71 so the semantics of the function is obviously preserved. If we are 72 guaranteed that the value of the accumulator never change, we 73 omit the accumulator. 74 75 There are three cases how the function may exit. The first one is 76 handled in adjust_return_value, the other two in adjust_accumulator_values 77 (the second case is actually a special case of the third one and we 78 present it separately just for clarity): 79 80 1) Just return x, where x is not in any of the remaining special shapes. 81 We rewrite this to a gimple equivalent of return m_acc * x + a_acc. 82 83 2) return f (...), where f is the current function, is rewritten in a 84 classical tail-recursion elimination way, into assignment of arguments 85 and jump to the start of the function. Values of the accumulators 86 are unchanged. 87 88 3) return a + m * f(...), where a and m do not depend on call to f. 89 To preserve the semantics described before we want this to be rewritten 90 in such a way that we finally return 91 92 a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...). 93 94 I.e. we increase a_acc by a * m_acc, multiply m_acc by m and 95 eliminate the tail call to f. Special cases when the value is just 96 added or just multiplied are obtained by setting a = 0 or m = 1. 97 98 TODO -- it is possible to do similar tricks for other operations. */ 99 100/* A structure that describes the tailcall. */ 101 102struct tailcall 103{ 104 /* The iterator pointing to the call statement. */ 105 gimple_stmt_iterator call_gsi; 106 107 /* True if it is a call to the current function. */ 108 bool tail_recursion; 109 110 /* The return value of the caller is mult * f + add, where f is the return 111 value of the call. */ 112 tree mult, add; 113 114 /* Next tailcall in the chain. */ 115 struct tailcall *next; 116}; 117 118/* The variables holding the value of multiplicative and additive 119 accumulator. */ 120static tree m_acc, a_acc; 121 122static bool suitable_for_tail_opt_p (void); 123static bool optimize_tail_call (struct tailcall *, bool); 124static void eliminate_tail_call (struct tailcall *); 125static void find_tail_calls (basic_block, struct tailcall **); 126 127/* Returns false when the function is not suitable for tail call optimization 128 from some reason (e.g. if it takes variable number of arguments). */ 129 130static bool 131suitable_for_tail_opt_p (void) 132{ 133 referenced_var_iterator rvi; 134 tree var; 135 136 if (cfun->stdarg) 137 return false; 138 139 /* No local variable nor structure field should be call-used. */ 140 FOR_EACH_REFERENCED_VAR (var, rvi) 141 { 142 if (!is_global_var (var) 143 && is_call_used (var)) 144 return false; 145 } 146 147 return true; 148} 149/* Returns false when the function is not suitable for tail call optimization 150 from some reason (e.g. if it takes variable number of arguments). 151 This test must pass in addition to suitable_for_tail_opt_p in order to make 152 tail call discovery happen. */ 153 154static bool 155suitable_for_tail_call_opt_p (void) 156{ 157 tree param; 158 159 /* alloca (until we have stack slot life analysis) inhibits 160 sibling call optimizations, but not tail recursion. */ 161 if (cfun->calls_alloca) 162 return false; 163 164 /* If we are using sjlj exceptions, we may need to add a call to 165 _Unwind_SjLj_Unregister at exit of the function. Which means 166 that we cannot do any sibcall transformations. */ 167 if (USING_SJLJ_EXCEPTIONS && current_function_has_exception_handlers ()) 168 return false; 169 170 /* Any function that calls setjmp might have longjmp called from 171 any called function. ??? We really should represent this 172 properly in the CFG so that this needn't be special cased. */ 173 if (cfun->calls_setjmp) 174 return false; 175 176 /* ??? It is OK if the argument of a function is taken in some cases, 177 but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */ 178 for (param = DECL_ARGUMENTS (current_function_decl); 179 param; 180 param = TREE_CHAIN (param)) 181 if (TREE_ADDRESSABLE (param)) 182 return false; 183 184 return true; 185} 186 187/* Checks whether the expression EXPR in stmt AT is independent of the 188 statement pointed to by GSI (in a sense that we already know EXPR's value 189 at GSI). We use the fact that we are only called from the chain of 190 basic blocks that have only single successor. Returns the expression 191 containing the value of EXPR at GSI. */ 192 193static tree 194independent_of_stmt_p (tree expr, gimple at, gimple_stmt_iterator gsi) 195{ 196 basic_block bb, call_bb, at_bb; 197 edge e; 198 edge_iterator ei; 199 200 if (is_gimple_min_invariant (expr)) 201 return expr; 202 203 if (TREE_CODE (expr) != SSA_NAME) 204 return NULL_TREE; 205 206 /* Mark the blocks in the chain leading to the end. */ 207 at_bb = gimple_bb (at); 208 call_bb = gimple_bb (gsi_stmt (gsi)); 209 for (bb = call_bb; bb != at_bb; bb = single_succ (bb)) 210 bb->aux = &bb->aux; 211 bb->aux = &bb->aux; 212 213 while (1) 214 { 215 at = SSA_NAME_DEF_STMT (expr); 216 bb = gimple_bb (at); 217 218 /* The default definition or defined before the chain. */ 219 if (!bb || !bb->aux) 220 break; 221 222 if (bb == call_bb) 223 { 224 for (; !gsi_end_p (gsi); gsi_next (&gsi)) 225 if (gsi_stmt (gsi) == at) 226 break; 227 228 if (!gsi_end_p (gsi)) 229 expr = NULL_TREE; 230 break; 231 } 232 233 if (gimple_code (at) != GIMPLE_PHI) 234 { 235 expr = NULL_TREE; 236 break; 237 } 238 239 FOR_EACH_EDGE (e, ei, bb->preds) 240 if (e->src->aux) 241 break; 242 gcc_assert (e); 243 244 expr = PHI_ARG_DEF_FROM_EDGE (at, e); 245 if (TREE_CODE (expr) != SSA_NAME) 246 { 247 /* The value is a constant. */ 248 break; 249 } 250 } 251 252 /* Unmark the blocks. */ 253 for (bb = call_bb; bb != at_bb; bb = single_succ (bb)) 254 bb->aux = NULL; 255 bb->aux = NULL; 256 257 return expr; 258} 259 260/* Simulates the effect of an assignment STMT on the return value of the tail 261 recursive CALL passed in ASS_VAR. M and A are the multiplicative and the 262 additive factor for the real return value. */ 263 264static bool 265process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m, 266 tree *a, tree *ass_var) 267{ 268 tree op0, op1, non_ass_var; 269 tree dest = gimple_assign_lhs (stmt); 270 enum tree_code code = gimple_assign_rhs_code (stmt); 271 enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code); 272 tree src_var = gimple_assign_rhs1 (stmt); 273 274 /* See if this is a simple copy operation of an SSA name to the function 275 result. In that case we may have a simple tail call. Ignore type 276 conversions that can never produce extra code between the function 277 call and the function return. */ 278 if ((rhs_class == GIMPLE_SINGLE_RHS || gimple_assign_cast_p (stmt)) 279 && (TREE_CODE (src_var) == SSA_NAME)) 280 { 281 /* Reject a tailcall if the type conversion might need 282 additional code. */ 283 if (gimple_assign_cast_p (stmt) 284 && TYPE_MODE (TREE_TYPE (dest)) != TYPE_MODE (TREE_TYPE (src_var))) 285 return false; 286 287 if (src_var != *ass_var) 288 return false; 289 290 *ass_var = dest; 291 return true; 292 } 293 294 if (rhs_class != GIMPLE_BINARY_RHS) 295 return false; 296 297 /* Accumulator optimizations will reverse the order of operations. 298 We can only do that for floating-point types if we're assuming 299 that addition and multiplication are associative. */ 300 if (!flag_associative_math) 301 if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl)))) 302 return false; 303 304 /* We only handle the code like 305 306 x = call (); 307 y = m * x; 308 z = y + a; 309 return z; 310 311 TODO -- Extend it for cases where the linear transformation of the output 312 is expressed in a more complicated way. */ 313 314 op0 = gimple_assign_rhs1 (stmt); 315 op1 = gimple_assign_rhs2 (stmt); 316 317 if (op0 == *ass_var 318 && (non_ass_var = independent_of_stmt_p (op1, stmt, call))) 319 ; 320 else if (op1 == *ass_var 321 && (non_ass_var = independent_of_stmt_p (op0, stmt, call))) 322 ; 323 else 324 return false; 325 326 switch (code) 327 { 328 case PLUS_EXPR: 329 *a = non_ass_var; 330 *ass_var = dest; 331 return true; 332 333 case MULT_EXPR: 334 *m = non_ass_var; 335 *ass_var = dest; 336 return true; 337 338 /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR, 339 POINTER_PLUS_EXPR). */ 340 341 default: 342 return false; 343 } 344} 345 346/* Propagate VAR through phis on edge E. */ 347 348static tree 349propagate_through_phis (tree var, edge e) 350{ 351 basic_block dest = e->dest; 352 gimple_stmt_iterator gsi; 353 354 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi)) 355 { 356 gimple phi = gsi_stmt (gsi); 357 if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var) 358 return PHI_RESULT (phi); 359 } 360 return var; 361} 362 363/* Finds tailcalls falling into basic block BB. The list of found tailcalls is 364 added to the start of RET. */ 365 366static void 367find_tail_calls (basic_block bb, struct tailcall **ret) 368{ 369 tree ass_var = NULL_TREE, ret_var, func, param; 370 gimple stmt, call = NULL; 371 gimple_stmt_iterator gsi, agsi; 372 bool tail_recursion; 373 struct tailcall *nw; 374 edge e; 375 tree m, a; 376 basic_block abb; 377 size_t idx; 378 tree var; 379 referenced_var_iterator rvi; 380 381 if (!single_succ_p (bb)) 382 return; 383 384 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi)) 385 { 386 stmt = gsi_stmt (gsi); 387 388 /* Ignore labels. */ 389 if (gimple_code (stmt) == GIMPLE_LABEL || is_gimple_debug (stmt)) 390 continue; 391 392 /* Check for a call. */ 393 if (is_gimple_call (stmt)) 394 { 395 call = stmt; 396 ass_var = gimple_call_lhs (stmt); 397 break; 398 } 399 400 /* If the statement references memory or volatile operands, fail. */ 401 if (gimple_references_memory_p (stmt) 402 || gimple_has_volatile_ops (stmt)) 403 return; 404 } 405 406 if (gsi_end_p (gsi)) 407 { 408 edge_iterator ei; 409 /* Recurse to the predecessors. */ 410 FOR_EACH_EDGE (e, ei, bb->preds) 411 find_tail_calls (e->src, ret); 412 413 return; 414 } 415 416 /* If the LHS of our call is not just a simple register, we can't 417 transform this into a tail or sibling call. This situation happens, 418 in (e.g.) "*p = foo()" where foo returns a struct. In this case 419 we won't have a temporary here, but we need to carry out the side 420 effect anyway, so tailcall is impossible. 421 422 ??? In some situations (when the struct is returned in memory via 423 invisible argument) we could deal with this, e.g. by passing 'p' 424 itself as that argument to foo, but it's too early to do this here, 425 and expand_call() will not handle it anyway. If it ever can, then 426 we need to revisit this here, to allow that situation. */ 427 if (ass_var && !is_gimple_reg (ass_var)) 428 return; 429 430 /* We found the call, check whether it is suitable. */ 431 tail_recursion = false; 432 func = gimple_call_fndecl (call); 433 if (func == current_function_decl) 434 { 435 tree arg; 436 for (param = DECL_ARGUMENTS (func), idx = 0; 437 param && idx < gimple_call_num_args (call); 438 param = TREE_CHAIN (param), idx ++) 439 { 440 arg = gimple_call_arg (call, idx); 441 if (param != arg) 442 { 443 /* Make sure there are no problems with copying. The parameter 444 have a copyable type and the two arguments must have reasonably 445 equivalent types. The latter requirement could be relaxed if 446 we emitted a suitable type conversion statement. */ 447 if (!is_gimple_reg_type (TREE_TYPE (param)) 448 || !useless_type_conversion_p (TREE_TYPE (param), 449 TREE_TYPE (arg))) 450 break; 451 452 /* The parameter should be a real operand, so that phi node 453 created for it at the start of the function has the meaning 454 of copying the value. This test implies is_gimple_reg_type 455 from the previous condition, however this one could be 456 relaxed by being more careful with copying the new value 457 of the parameter (emitting appropriate GIMPLE_ASSIGN and 458 updating the virtual operands). */ 459 if (!is_gimple_reg (param)) 460 break; 461 } 462 } 463 if (idx == gimple_call_num_args (call) && !param) 464 tail_recursion = true; 465 } 466 467 /* Make sure the tail invocation of this function does not refer 468 to local variables. */ 469 FOR_EACH_REFERENCED_VAR (var, rvi) 470 { 471 if (TREE_CODE (var) != PARM_DECL 472 && auto_var_in_fn_p (var, cfun->decl) 473 && ref_maybe_used_by_stmt_p (call, var)) 474 return; 475 } 476 477 /* Now check the statements after the call. None of them has virtual 478 operands, so they may only depend on the call through its return 479 value. The return value should also be dependent on each of them, 480 since we are running after dce. */ 481 m = NULL_TREE; 482 a = NULL_TREE; 483 484 abb = bb; 485 agsi = gsi; 486 while (1) 487 { 488 tree tmp_a = NULL_TREE; 489 tree tmp_m = NULL_TREE; 490 gsi_next (&agsi); 491 492 while (gsi_end_p (agsi)) 493 { 494 ass_var = propagate_through_phis (ass_var, single_succ_edge (abb)); 495 abb = single_succ (abb); 496 agsi = gsi_start_bb (abb); 497 } 498 499 stmt = gsi_stmt (agsi); 500 501 if (gimple_code (stmt) == GIMPLE_LABEL) 502 continue; 503 504 if (gimple_code (stmt) == GIMPLE_RETURN) 505 break; 506 507 if (is_gimple_debug (stmt)) 508 continue; 509 510 if (gimple_code (stmt) != GIMPLE_ASSIGN) 511 return; 512 513 /* This is a gimple assign. */ 514 if (! process_assignment (stmt, gsi, &tmp_m, &tmp_a, &ass_var)) 515 return; 516 517 if (tmp_a) 518 { 519 if (a) 520 a = fold_build2 (PLUS_EXPR, TREE_TYPE (tmp_a), a, tmp_a); 521 else 522 a = tmp_a; 523 } 524 if (tmp_m) 525 { 526 if (m) 527 m = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), m, tmp_m); 528 else 529 m = tmp_m; 530 531 if (a) 532 a = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), a, tmp_m); 533 } 534 } 535 536 /* See if this is a tail call we can handle. */ 537 ret_var = gimple_return_retval (stmt); 538 539 /* We may proceed if there either is no return value, or the return value 540 is identical to the call's return. */ 541 if (ret_var 542 && (ret_var != ass_var)) 543 return; 544 545 /* If this is not a tail recursive call, we cannot handle addends or 546 multiplicands. */ 547 if (!tail_recursion && (m || a)) 548 return; 549 550 nw = XNEW (struct tailcall); 551 552 nw->call_gsi = gsi; 553 554 nw->tail_recursion = tail_recursion; 555 556 nw->mult = m; 557 nw->add = a; 558 559 nw->next = *ret; 560 *ret = nw; 561} 562 563/* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */ 564 565static void 566add_successor_phi_arg (edge e, tree var, tree phi_arg) 567{ 568 gimple_stmt_iterator gsi; 569 570 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) 571 if (PHI_RESULT (gsi_stmt (gsi)) == var) 572 break; 573 574 gcc_assert (!gsi_end_p (gsi)); 575 add_phi_arg (gsi_stmt (gsi), phi_arg, e, UNKNOWN_LOCATION); 576} 577 578/* Creates a GIMPLE statement which computes the operation specified by 579 CODE, OP0 and OP1 to a new variable with name LABEL and inserts the 580 statement in the position specified by GSI and UPDATE. Returns the 581 tree node of the statement's result. */ 582 583static tree 584adjust_return_value_with_ops (enum tree_code code, const char *label, 585 tree acc, tree op1, gimple_stmt_iterator gsi) 586{ 587 588 tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl)); 589 tree tmp = create_tmp_var (ret_type, label); 590 gimple stmt; 591 tree result; 592 593 if (TREE_CODE (ret_type) == COMPLEX_TYPE 594 || TREE_CODE (ret_type) == VECTOR_TYPE) 595 DECL_GIMPLE_REG_P (tmp) = 1; 596 add_referenced_var (tmp); 597 598 if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1))) 599 stmt = gimple_build_assign_with_ops (code, tmp, acc, op1); 600 else 601 { 602 tree rhs = fold_convert (TREE_TYPE (acc), 603 fold_build2 (code, 604 TREE_TYPE (op1), 605 fold_convert (TREE_TYPE (op1), acc), 606 op1)); 607 rhs = force_gimple_operand_gsi (&gsi, rhs, 608 false, NULL, true, GSI_CONTINUE_LINKING); 609 stmt = gimple_build_assign (NULL_TREE, rhs); 610 } 611 612 result = make_ssa_name (tmp, stmt); 613 gimple_assign_set_lhs (stmt, result); 614 update_stmt (stmt); 615 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT); 616 return result; 617} 618 619/* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by 620 the computation specified by CODE and OP1 and insert the statement 621 at the position specified by GSI as a new statement. Returns new SSA name 622 of updated accumulator. */ 623 624static tree 625update_accumulator_with_ops (enum tree_code code, tree acc, tree op1, 626 gimple_stmt_iterator gsi) 627{ 628 gimple stmt; 629 tree var; 630 if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1))) 631 stmt = gimple_build_assign_with_ops (code, SSA_NAME_VAR (acc), acc, op1); 632 else 633 { 634 tree rhs = fold_convert (TREE_TYPE (acc), 635 fold_build2 (code, 636 TREE_TYPE (op1), 637 fold_convert (TREE_TYPE (op1), acc), 638 op1)); 639 rhs = force_gimple_operand_gsi (&gsi, rhs, 640 false, NULL, false, GSI_CONTINUE_LINKING); 641 stmt = gimple_build_assign (NULL_TREE, rhs); 642 } 643 var = make_ssa_name (SSA_NAME_VAR (acc), stmt); 644 gimple_assign_set_lhs (stmt, var); 645 update_stmt (stmt); 646 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT); 647 return var; 648} 649 650/* Adjust the accumulator values according to A and M after GSI, and update 651 the phi nodes on edge BACK. */ 652 653static void 654adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back) 655{ 656 tree var, a_acc_arg, m_acc_arg; 657 658 if (m) 659 m = force_gimple_operand_gsi (&gsi, m, true, NULL, true, GSI_SAME_STMT); 660 if (a) 661 a = force_gimple_operand_gsi (&gsi, a, true, NULL, true, GSI_SAME_STMT); 662 663 a_acc_arg = a_acc; 664 m_acc_arg = m_acc; 665 if (a) 666 { 667 if (m_acc) 668 { 669 if (integer_onep (a)) 670 var = m_acc; 671 else 672 var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc, 673 a, gsi); 674 } 675 else 676 var = a; 677 678 a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi); 679 } 680 681 if (m) 682 m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi); 683 684 if (a_acc) 685 add_successor_phi_arg (back, a_acc, a_acc_arg); 686 687 if (m_acc) 688 add_successor_phi_arg (back, m_acc, m_acc_arg); 689} 690 691/* Adjust value of the return at the end of BB according to M and A 692 accumulators. */ 693 694static void 695adjust_return_value (basic_block bb, tree m, tree a) 696{ 697 tree retval; 698 gimple ret_stmt = gimple_seq_last_stmt (bb_seq (bb)); 699 gimple_stmt_iterator gsi = gsi_last_bb (bb); 700 701 gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN); 702 703 retval = gimple_return_retval (ret_stmt); 704 if (!retval || retval == error_mark_node) 705 return; 706 707 if (m) 708 retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval, 709 gsi); 710 if (a) 711 retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval, 712 gsi); 713 gimple_return_set_retval (ret_stmt, retval); 714 update_stmt (ret_stmt); 715} 716 717/* Subtract COUNT and FREQUENCY from the basic block and it's 718 outgoing edge. */ 719static void 720decrease_profile (basic_block bb, gcov_type count, int frequency) 721{ 722 edge e; 723 bb->count -= count; 724 if (bb->count < 0) 725 bb->count = 0; 726 bb->frequency -= frequency; 727 if (bb->frequency < 0) 728 bb->frequency = 0; 729 if (!single_succ_p (bb)) 730 { 731 gcc_assert (!EDGE_COUNT (bb->succs)); 732 return; 733 } 734 e = single_succ_edge (bb); 735 e->count -= count; 736 if (e->count < 0) 737 e->count = 0; 738} 739 740/* Returns true if argument PARAM of the tail recursive call needs to be copied 741 when the call is eliminated. */ 742 743static bool 744arg_needs_copy_p (tree param) 745{ 746 tree def; 747 748 if (!is_gimple_reg (param) || !var_ann (param)) 749 return false; 750 751 /* Parameters that are only defined but never used need not be copied. */ 752 def = gimple_default_def (cfun, param); 753 if (!def) 754 return false; 755 756 return true; 757} 758 759/* Eliminates tail call described by T. TMP_VARS is a list of 760 temporary variables used to copy the function arguments. */ 761 762static void 763eliminate_tail_call (struct tailcall *t) 764{ 765 tree param, rslt; 766 gimple stmt, call; 767 tree arg; 768 size_t idx; 769 basic_block bb, first; 770 edge e; 771 gimple phi; 772 gimple_stmt_iterator gsi; 773 gimple orig_stmt; 774 775 stmt = orig_stmt = gsi_stmt (t->call_gsi); 776 bb = gsi_bb (t->call_gsi); 777 778 if (dump_file && (dump_flags & TDF_DETAILS)) 779 { 780 fprintf (dump_file, "Eliminated tail recursion in bb %d : ", 781 bb->index); 782 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 783 fprintf (dump_file, "\n"); 784 } 785 786 gcc_assert (is_gimple_call (stmt)); 787 788 first = single_succ (ENTRY_BLOCK_PTR); 789 790 /* Remove the code after call_gsi that will become unreachable. The 791 possibly unreachable code in other blocks is removed later in 792 cfg cleanup. */ 793 gsi = t->call_gsi; 794 gsi_next (&gsi); 795 while (!gsi_end_p (gsi)) 796 { 797 gimple t = gsi_stmt (gsi); 798 /* Do not remove the return statement, so that redirect_edge_and_branch 799 sees how the block ends. */ 800 if (gimple_code (t) == GIMPLE_RETURN) 801 break; 802 803 gsi_remove (&gsi, true); 804 release_defs (t); 805 } 806 807 /* Number of executions of function has reduced by the tailcall. */ 808 e = single_succ_edge (gsi_bb (t->call_gsi)); 809 decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e)); 810 decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e)); 811 if (e->dest != EXIT_BLOCK_PTR) 812 decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e)); 813 814 /* Replace the call by a jump to the start of function. */ 815 e = redirect_edge_and_branch (single_succ_edge (gsi_bb (t->call_gsi)), 816 first); 817 gcc_assert (e); 818 PENDING_STMT (e) = NULL; 819 820 /* Add phi node entries for arguments. The ordering of the phi nodes should 821 be the same as the ordering of the arguments. */ 822 for (param = DECL_ARGUMENTS (current_function_decl), 823 idx = 0, gsi = gsi_start_phis (first); 824 param; 825 param = TREE_CHAIN (param), idx++) 826 { 827 if (!arg_needs_copy_p (param)) 828 continue; 829 830 arg = gimple_call_arg (stmt, idx); 831 phi = gsi_stmt (gsi); 832 gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi))); 833 834 add_phi_arg (phi, arg, e, gimple_location (stmt)); 835 gsi_next (&gsi); 836 } 837 838 /* Update the values of accumulators. */ 839 adjust_accumulator_values (t->call_gsi, t->mult, t->add, e); 840 841 call = gsi_stmt (t->call_gsi); 842 rslt = gimple_call_lhs (call); 843 if (rslt != NULL_TREE) 844 { 845 /* Result of the call will no longer be defined. So adjust the 846 SSA_NAME_DEF_STMT accordingly. */ 847 SSA_NAME_DEF_STMT (rslt) = gimple_build_nop (); 848 } 849 850 gsi_remove (&t->call_gsi, true); 851 release_defs (call); 852} 853 854/* Add phi nodes for the virtual operands defined in the function to the 855 header of the loop created by tail recursion elimination. 856 857 Originally, we used to add phi nodes only for call clobbered variables, 858 as the value of the non-call clobbered ones obviously cannot be used 859 or changed within the recursive call. However, the local variables 860 from multiple calls now share the same location, so the virtual ssa form 861 requires us to say that the location dies on further iterations of the loop, 862 which requires adding phi nodes. 863*/ 864static void 865add_virtual_phis (void) 866{ 867 referenced_var_iterator rvi; 868 tree var; 869 870 /* The problematic part is that there is no way how to know what 871 to put into phi nodes (there in fact does not have to be such 872 ssa name available). A solution would be to have an artificial 873 use/kill for all virtual operands in EXIT node. Unless we have 874 this, we cannot do much better than to rebuild the ssa form for 875 possibly affected virtual ssa names from scratch. */ 876 877 FOR_EACH_REFERENCED_VAR (var, rvi) 878 { 879 if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE) 880 mark_sym_for_renaming (var); 881 } 882} 883 884/* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also 885 mark the tailcalls for the sibcall optimization. */ 886 887static bool 888optimize_tail_call (struct tailcall *t, bool opt_tailcalls) 889{ 890 if (t->tail_recursion) 891 { 892 eliminate_tail_call (t); 893 return true; 894 } 895 896 if (opt_tailcalls) 897 { 898 gimple stmt = gsi_stmt (t->call_gsi); 899 900 gimple_call_set_tail (stmt, true); 901 if (dump_file && (dump_flags & TDF_DETAILS)) 902 { 903 fprintf (dump_file, "Found tail call "); 904 print_gimple_stmt (dump_file, stmt, 0, dump_flags); 905 fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index); 906 } 907 } 908 909 return false; 910} 911 912/* Creates a tail-call accumulator of the same type as the return type of the 913 current function. LABEL is the name used to creating the temporary 914 variable for the accumulator. The accumulator will be inserted in the 915 phis of a basic block BB with single predecessor with an initial value 916 INIT converted to the current function return type. */ 917 918static tree 919create_tailcall_accumulator (const char *label, basic_block bb, tree init) 920{ 921 tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl)); 922 tree tmp = create_tmp_var (ret_type, label); 923 gimple phi; 924 925 if (TREE_CODE (ret_type) == COMPLEX_TYPE 926 || TREE_CODE (ret_type) == VECTOR_TYPE) 927 DECL_GIMPLE_REG_P (tmp) = 1; 928 add_referenced_var (tmp); 929 phi = create_phi_node (tmp, bb); 930 /* RET_TYPE can be a float when -ffast-maths is enabled. */ 931 add_phi_arg (phi, fold_convert (ret_type, init), single_pred_edge (bb), 932 UNKNOWN_LOCATION); 933 return PHI_RESULT (phi); 934} 935 936/* Optimizes tail calls in the function, turning the tail recursion 937 into iteration. */ 938 939static unsigned int 940tree_optimize_tail_calls_1 (bool opt_tailcalls) 941{ 942 edge e; 943 bool phis_constructed = false; 944 struct tailcall *tailcalls = NULL, *act, *next; 945 bool changed = false; 946 basic_block first = single_succ (ENTRY_BLOCK_PTR); 947 tree param; 948 gimple stmt; 949 edge_iterator ei; 950 951 if (!suitable_for_tail_opt_p ()) 952 return 0; 953 if (opt_tailcalls) 954 opt_tailcalls = suitable_for_tail_call_opt_p (); 955 956 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 957 { 958 /* Only traverse the normal exits, i.e. those that end with return 959 statement. */ 960 stmt = last_stmt (e->src); 961 962 if (stmt 963 && gimple_code (stmt) == GIMPLE_RETURN) 964 find_tail_calls (e->src, &tailcalls); 965 } 966 967 /* Construct the phi nodes and accumulators if necessary. */ 968 a_acc = m_acc = NULL_TREE; 969 for (act = tailcalls; act; act = act->next) 970 { 971 if (!act->tail_recursion) 972 continue; 973 974 if (!phis_constructed) 975 { 976 /* Ensure that there is only one predecessor of the block 977 or if there are existing degenerate PHI nodes. */ 978 if (!single_pred_p (first) 979 || !gimple_seq_empty_p (phi_nodes (first))) 980 first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR)); 981 982 /* Copy the args if needed. */ 983 for (param = DECL_ARGUMENTS (current_function_decl); 984 param; 985 param = TREE_CHAIN (param)) 986 if (arg_needs_copy_p (param)) 987 { 988 tree name = gimple_default_def (cfun, param); 989 tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name)); 990 gimple phi; 991 992 set_default_def (param, new_name); 993 phi = create_phi_node (name, first); 994 SSA_NAME_DEF_STMT (name) = phi; 995 add_phi_arg (phi, new_name, single_pred_edge (first), 996 EXPR_LOCATION (param)); 997 } 998 phis_constructed = true; 999 } 1000 1001 if (act->add && !a_acc) 1002 a_acc = create_tailcall_accumulator ("add_acc", first, 1003 integer_zero_node); 1004 1005 if (act->mult && !m_acc) 1006 m_acc = create_tailcall_accumulator ("mult_acc", first, 1007 integer_one_node); 1008 } 1009 1010 for (; tailcalls; tailcalls = next) 1011 { 1012 next = tailcalls->next; 1013 changed |= optimize_tail_call (tailcalls, opt_tailcalls); 1014 free (tailcalls); 1015 } 1016 1017 if (a_acc || m_acc) 1018 { 1019 /* Modify the remaining return statements. */ 1020 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 1021 { 1022 stmt = last_stmt (e->src); 1023 1024 if (stmt 1025 && gimple_code (stmt) == GIMPLE_RETURN) 1026 adjust_return_value (e->src, m_acc, a_acc); 1027 } 1028 } 1029 1030 if (changed) 1031 free_dominance_info (CDI_DOMINATORS); 1032 1033 if (phis_constructed) 1034 add_virtual_phis (); 1035 if (changed) 1036 return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals; 1037 return 0; 1038} 1039 1040static unsigned int 1041execute_tail_recursion (void) 1042{ 1043 return tree_optimize_tail_calls_1 (false); 1044} 1045 1046static bool 1047gate_tail_calls (void) 1048{ 1049 return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call); 1050} 1051 1052static unsigned int 1053execute_tail_calls (void) 1054{ 1055 return tree_optimize_tail_calls_1 (true); 1056} 1057 1058struct gimple_opt_pass pass_tail_recursion = 1059{ 1060 { 1061 GIMPLE_PASS, 1062 "tailr", /* name */ 1063 gate_tail_calls, /* gate */ 1064 execute_tail_recursion, /* execute */ 1065 NULL, /* sub */ 1066 NULL, /* next */ 1067 0, /* static_pass_number */ 1068 TV_NONE, /* tv_id */ 1069 PROP_cfg | PROP_ssa, /* properties_required */ 1070 0, /* properties_provided */ 1071 0, /* properties_destroyed */ 1072 0, /* todo_flags_start */ 1073 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */ 1074 } 1075}; 1076 1077struct gimple_opt_pass pass_tail_calls = 1078{ 1079 { 1080 GIMPLE_PASS, 1081 "tailc", /* name */ 1082 gate_tail_calls, /* gate */ 1083 execute_tail_calls, /* execute */ 1084 NULL, /* sub */ 1085 NULL, /* next */ 1086 0, /* static_pass_number */ 1087 TV_NONE, /* tv_id */ 1088 PROP_cfg | PROP_ssa, /* properties_required */ 1089 0, /* properties_provided */ 1090 0, /* properties_destroyed */ 1091 0, /* todo_flags_start */ 1092 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */ 1093 } 1094}; 1095