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