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