1/* SSA Jump Threading 2 Copyright (C) 2005-2020 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 3, 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 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 "predict.h" 25#include "tree.h" 26#include "gimple.h" 27#include "fold-const.h" 28#include "cfgloop.h" 29#include "gimple-iterator.h" 30#include "tree-cfg.h" 31#include "tree-ssa-threadupdate.h" 32#include "tree-ssa-loop.h" 33#include "cfganal.h" 34#include "tree-pass.h" 35#include "gimple-ssa.h" 36#include "tree-phinodes.h" 37#include "tree-inline.h" 38#include "tree-vectorizer.h" 39 40class thread_jumps 41{ 42 public: 43 void find_jump_threads_backwards (basic_block bb, bool speed_p); 44 private: 45 edge profitable_jump_thread_path (basic_block bbi, tree name, tree arg, 46 bool *creates_irreducible_loop); 47 void convert_and_register_current_path (edge taken_edge); 48 void register_jump_thread_path_if_profitable (tree name, tree arg, 49 basic_block def_bb); 50 void handle_assignment (gimple *stmt, tree name, basic_block def_bb); 51 void handle_phi (gphi *phi, tree name, basic_block def_bb); 52 void fsm_find_control_statement_thread_paths (tree name); 53 bool check_subpath_and_update_thread_path (basic_block last_bb, 54 basic_block new_bb, 55 int *next_path_length); 56 57 /* Maximum number of BBs we are allowed to thread. */ 58 int m_max_threaded_paths; 59 /* Hash to keep track of seen bbs. */ 60 hash_set<basic_block> m_visited_bbs; 61 /* Current path we're analyzing. */ 62 auto_vec<basic_block> m_path; 63 /* Tracks if we have recursed through a loop PHI node. */ 64 bool m_seen_loop_phi; 65 /* Indicate that we could increase code size to improve the 66 code path. */ 67 bool m_speed_p; 68}; 69 70/* Simple helper to get the last statement from BB, which is assumed 71 to be a control statement. Return NULL if the last statement is 72 not a control statement. */ 73 74static gimple * 75get_gimple_control_stmt (basic_block bb) 76{ 77 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb); 78 79 if (gsi_end_p (gsi)) 80 return NULL; 81 82 gimple *stmt = gsi_stmt (gsi); 83 enum gimple_code code = gimple_code (stmt); 84 if (code == GIMPLE_COND || code == GIMPLE_SWITCH || code == GIMPLE_GOTO) 85 return stmt; 86 return NULL; 87} 88 89/* Return true if the CFG contains at least one path from START_BB to 90 END_BB. When a path is found, record in PATH the blocks from 91 END_BB to START_BB. LOCAL_VISITED_BBS is used to make sure we 92 don't fall into an infinite loop. Bound the recursion to basic 93 blocks belonging to LOOP. */ 94 95static bool 96fsm_find_thread_path (basic_block start_bb, basic_block end_bb, 97 vec<basic_block> &path, 98 hash_set<basic_block> &local_visited_bbs, 99 loop_p loop) 100{ 101 if (loop != start_bb->loop_father) 102 return false; 103 104 if (start_bb == end_bb) 105 { 106 path.safe_push (start_bb); 107 return true; 108 } 109 110 if (!local_visited_bbs.add (start_bb)) 111 { 112 edge e; 113 edge_iterator ei; 114 FOR_EACH_EDGE (e, ei, start_bb->succs) 115 if (fsm_find_thread_path (e->dest, end_bb, path, local_visited_bbs, 116 loop)) 117 { 118 path.safe_push (start_bb); 119 return true; 120 } 121 } 122 123 return false; 124} 125 126/* Examine jump threading path PATH to which we want to add BBI. 127 128 If the resulting path is profitable to thread, then return the 129 final taken edge from the path, NULL otherwise. 130 131 NAME is the SSA_NAME of the variable we found to have a constant 132 value on PATH. ARG is the constant value of NAME on that path. 133 134 BBI will be appended to PATH when we have a profitable jump 135 threading path. Callers are responsible for removing BBI from PATH 136 in that case. */ 137 138edge 139thread_jumps::profitable_jump_thread_path (basic_block bbi, tree name, 140 tree arg, 141 bool *creates_irreducible_loop) 142{ 143 /* Note BBI is not in the path yet, hence the +1 in the test below 144 to make sure BBI is accounted for in the path length test. */ 145 146 /* We can get a length of 0 here when the statement that 147 makes a conditional generate a compile-time constant 148 result is in the same block as the conditional. 149 150 That's not really a jump threading opportunity, but instead is 151 simple cprop & simplification. We could handle it here if we 152 wanted by wiring up all the incoming edges. If we run this 153 early in IPA, that might be worth doing. For now we just 154 reject that case. */ 155 if (m_path.is_empty ()) 156 return NULL; 157 158 if (m_path.length () + 1 159 > (unsigned) param_max_fsm_thread_length) 160 { 161 if (dump_file && (dump_flags & TDF_DETAILS)) 162 fprintf (dump_file, "FSM jump-thread path not considered: " 163 "the number of basic blocks on the path " 164 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n"); 165 return NULL; 166 } 167 168 if (m_max_threaded_paths <= 0) 169 { 170 if (dump_file && (dump_flags & TDF_DETAILS)) 171 fprintf (dump_file, "FSM jump-thread path not considered: " 172 "the number of previously recorded FSM paths to " 173 "thread exceeds PARAM_MAX_FSM_THREAD_PATHS.\n"); 174 return NULL; 175 } 176 177 /* Add BBI to the path. 178 From this point onward, if we decide we the path is not profitable 179 to thread, we must remove BBI from the path. */ 180 m_path.safe_push (bbi); 181 182 int n_insns = 0; 183 gimple_stmt_iterator gsi; 184 loop_p loop = m_path[0]->loop_father; 185 bool path_crosses_loops = false; 186 bool threaded_through_latch = false; 187 bool multiway_branch_in_path = false; 188 bool threaded_multiway_branch = false; 189 bool contains_hot_bb = false; 190 191 if (dump_file && (dump_flags & TDF_DETAILS)) 192 fprintf (dump_file, "Checking profitability of path (backwards): "); 193 194 /* Count the number of instructions on the path: as these instructions 195 will have to be duplicated, we will not record the path if there 196 are too many instructions on the path. Also check that all the 197 blocks in the path belong to a single loop. */ 198 for (unsigned j = 0; j < m_path.length (); j++) 199 { 200 basic_block bb = m_path[j]; 201 202 if (dump_file && (dump_flags & TDF_DETAILS)) 203 fprintf (dump_file, " bb:%i", bb->index); 204 /* Remember, blocks in the path are stored in opposite order 205 in the PATH array. The last entry in the array represents 206 the block with an outgoing edge that we will redirect to the 207 jump threading path. Thus we don't care about that block's 208 loop father, nor how many statements are in that block because 209 it will not be copied or whether or not it ends in a multiway 210 branch. */ 211 if (j < m_path.length () - 1) 212 { 213 int orig_n_insns = n_insns; 214 if (bb->loop_father != loop) 215 { 216 path_crosses_loops = true; 217 break; 218 } 219 220 /* PHIs in the path will create degenerate PHIS in the 221 copied path which will then get propagated away, so 222 looking at just the duplicate path the PHIs would 223 seem unimportant. 224 225 But those PHIs, because they're assignments to objects 226 typically with lives that exist outside the thread path, 227 will tend to generate PHIs (or at least new PHI arguments) 228 at points where we leave the thread path and rejoin 229 the original blocks. So we do want to account for them. 230 231 We ignore virtual PHIs. We also ignore cases where BB 232 has a single incoming edge. That's the most common 233 degenerate PHI we'll see here. Finally we ignore PHIs 234 that are associated with the value we're tracking as 235 that object likely dies. */ 236 if (EDGE_COUNT (bb->succs) > 1 && EDGE_COUNT (bb->preds) > 1) 237 { 238 for (gphi_iterator gsip = gsi_start_phis (bb); 239 !gsi_end_p (gsip); 240 gsi_next (&gsip)) 241 { 242 gphi *phi = gsip.phi (); 243 tree dst = gimple_phi_result (phi); 244 245 /* Note that if both NAME and DST are anonymous 246 SSA_NAMEs, then we do not have enough information 247 to consider them associated. */ 248 if (dst != name 249 && (SSA_NAME_VAR (dst) != SSA_NAME_VAR (name) 250 || !SSA_NAME_VAR (dst)) 251 && !virtual_operand_p (dst)) 252 ++n_insns; 253 } 254 } 255 256 if (!contains_hot_bb && m_speed_p) 257 contains_hot_bb |= optimize_bb_for_speed_p (bb); 258 for (gsi = gsi_after_labels (bb); 259 !gsi_end_p (gsi); 260 gsi_next_nondebug (&gsi)) 261 { 262 gimple *stmt = gsi_stmt (gsi); 263 if (gimple_call_internal_p (stmt, IFN_UNIQUE)) 264 { 265 m_path.pop (); 266 return NULL; 267 } 268 /* Do not count empty statements and labels. */ 269 if (gimple_code (stmt) != GIMPLE_NOP 270 && !(gimple_code (stmt) == GIMPLE_ASSIGN 271 && gimple_assign_rhs_code (stmt) == ASSERT_EXPR) 272 && !is_gimple_debug (stmt)) 273 n_insns += estimate_num_insns (stmt, &eni_size_weights); 274 } 275 if (dump_file && (dump_flags & TDF_DETAILS)) 276 fprintf (dump_file, " (%i insns)", n_insns-orig_n_insns); 277 278 /* We do not look at the block with the threaded branch 279 in this loop. So if any block with a last statement that 280 is a GIMPLE_SWITCH or GIMPLE_GOTO is seen, then we have a 281 multiway branch on our path. 282 283 The block in PATH[0] is special, it's the block were we're 284 going to be able to eliminate its branch. */ 285 gimple *last = last_stmt (bb); 286 if (last && (gimple_code (last) == GIMPLE_SWITCH 287 || gimple_code (last) == GIMPLE_GOTO)) 288 { 289 if (j == 0) 290 threaded_multiway_branch = true; 291 else 292 multiway_branch_in_path = true; 293 } 294 } 295 296 /* Note if we thread through the latch, we will want to include 297 the last entry in the array when determining if we thread 298 through the loop latch. */ 299 if (loop->latch == bb) 300 threaded_through_latch = true; 301 } 302 303 gimple *stmt = get_gimple_control_stmt (m_path[0]); 304 gcc_assert (stmt); 305 306 /* We are going to remove the control statement at the end of the 307 last block in the threading path. So don't count it against our 308 statement count. */ 309 310 int stmt_insns = estimate_num_insns (stmt, &eni_size_weights); 311 n_insns-= stmt_insns; 312 313 if (dump_file && (dump_flags & TDF_DETAILS)) 314 fprintf (dump_file, "\n Control statement insns: %i\n" 315 " Overall: %i insns\n", 316 stmt_insns, n_insns); 317 318 /* We have found a constant value for ARG. For GIMPLE_SWITCH 319 and GIMPLE_GOTO, we use it as-is. However, for a GIMPLE_COND 320 we need to substitute, fold and simplify so we can determine 321 the edge taken out of the last block. */ 322 if (gimple_code (stmt) == GIMPLE_COND) 323 { 324 enum tree_code cond_code = gimple_cond_code (stmt); 325 326 /* We know the underyling format of the condition. */ 327 arg = fold_binary (cond_code, boolean_type_node, 328 arg, gimple_cond_rhs (stmt)); 329 } 330 331 /* If this path threaded through the loop latch back into the 332 same loop and the destination does not dominate the loop 333 latch, then this thread would create an irreducible loop. 334 335 We have to know the outgoing edge to figure this out. */ 336 edge taken_edge = find_taken_edge (m_path[0], arg); 337 338 /* There are cases where we may not be able to extract the 339 taken edge. For example, a computed goto to an absolute 340 address. Handle those cases gracefully. */ 341 if (taken_edge == NULL) 342 { 343 m_path.pop (); 344 return NULL; 345 } 346 347 *creates_irreducible_loop = false; 348 if (threaded_through_latch 349 && loop == taken_edge->dest->loop_father 350 && (determine_bb_domination_status (loop, taken_edge->dest) 351 == DOMST_NONDOMINATING)) 352 *creates_irreducible_loop = true; 353 354 if (path_crosses_loops) 355 { 356 if (dump_file && (dump_flags & TDF_DETAILS)) 357 fprintf (dump_file, "FSM jump-thread path not considered: " 358 "the path crosses loops.\n"); 359 m_path.pop (); 360 return NULL; 361 } 362 363 /* Threading is profitable if the path duplicated is hot but also 364 in a case we separate cold path from hot path and permit optimization 365 of the hot path later. Be on the agressive side here. In some testcases, 366 as in PR 78407 this leads to noticeable improvements. */ 367 if (m_speed_p && (optimize_edge_for_speed_p (taken_edge) || contains_hot_bb)) 368 { 369 if (n_insns >= param_max_fsm_thread_path_insns) 370 { 371 if (dump_file && (dump_flags & TDF_DETAILS)) 372 fprintf (dump_file, "FSM jump-thread path not considered: " 373 "the number of instructions on the path " 374 "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n"); 375 m_path.pop (); 376 return NULL; 377 } 378 } 379 else if (n_insns > 1) 380 { 381 if (dump_file && (dump_flags & TDF_DETAILS)) 382 fprintf (dump_file, "FSM jump-thread path not considered: " 383 "duplication of %i insns is needed and optimizing for size.\n", 384 n_insns); 385 m_path.pop (); 386 return NULL; 387 } 388 389 /* We avoid creating irreducible inner loops unless we thread through 390 a multiway branch, in which case we have deemed it worth losing 391 other loop optimizations later. 392 393 We also consider it worth creating an irreducible inner loop if 394 the number of copied statement is low relative to the length of 395 the path -- in that case there's little the traditional loop 396 optimizer would have done anyway, so an irreducible loop is not 397 so bad. */ 398 if (!threaded_multiway_branch && *creates_irreducible_loop 399 && (n_insns * (unsigned) param_fsm_scale_path_stmts 400 > (m_path.length () * 401 (unsigned) param_fsm_scale_path_blocks))) 402 403 { 404 if (dump_file && (dump_flags & TDF_DETAILS)) 405 fprintf (dump_file, 406 "FSM would create irreducible loop without threading " 407 "multiway branch.\n"); 408 m_path.pop (); 409 return NULL; 410 } 411 412 413 /* If this path does not thread through the loop latch, then we are 414 using the FSM threader to find old style jump threads. This 415 is good, except the FSM threader does not re-use an existing 416 threading path to reduce code duplication. 417 418 So for that case, drastically reduce the number of statements 419 we are allowed to copy. */ 420 if (!(threaded_through_latch && threaded_multiway_branch) 421 && (n_insns * param_fsm_scale_path_stmts 422 >= param_max_jump_thread_duplication_stmts)) 423 { 424 if (dump_file && (dump_flags & TDF_DETAILS)) 425 fprintf (dump_file, 426 "FSM did not thread around loop and would copy too " 427 "many statements.\n"); 428 m_path.pop (); 429 return NULL; 430 } 431 432 /* When there is a multi-way branch on the path, then threading can 433 explode the CFG due to duplicating the edges for that multi-way 434 branch. So like above, only allow a multi-way branch on the path 435 if we actually thread a multi-way branch. */ 436 if (!threaded_multiway_branch && multiway_branch_in_path) 437 { 438 if (dump_file && (dump_flags & TDF_DETAILS)) 439 fprintf (dump_file, 440 "FSM Thread through multiway branch without threading " 441 "a multiway branch.\n"); 442 m_path.pop (); 443 return NULL; 444 } 445 return taken_edge; 446} 447 448/* The current path PATH is a vector of blocks forming a jump threading 449 path in reverse order. TAKEN_EDGE is the edge taken from path[0]. 450 451 Convert the current path into the form used by register_jump_thread and 452 register it. */ 453 454void 455thread_jumps::convert_and_register_current_path (edge taken_edge) 456{ 457 vec<jump_thread_edge *> *jump_thread_path = new vec<jump_thread_edge *> (); 458 459 /* Record the edges between the blocks in PATH. */ 460 for (unsigned int j = 0; j + 1 < m_path.length (); j++) 461 { 462 basic_block bb1 = m_path[m_path.length () - j - 1]; 463 basic_block bb2 = m_path[m_path.length () - j - 2]; 464 465 edge e = find_edge (bb1, bb2); 466 gcc_assert (e); 467 jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD); 468 jump_thread_path->safe_push (x); 469 } 470 471 /* Add the edge taken when the control variable has value ARG. */ 472 jump_thread_edge *x 473 = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK); 474 jump_thread_path->safe_push (x); 475 476 register_jump_thread (jump_thread_path); 477 --m_max_threaded_paths; 478} 479 480/* While following a chain of SSA_NAME definitions, we jumped from a 481 definition in LAST_BB to a definition in NEW_BB (walking 482 backwards). 483 484 Verify there is a single path between the blocks and none of the 485 blocks in the path is already in VISITED_BBS. If so, then update 486 VISISTED_BBS, add the new blocks to PATH and return TRUE. 487 Otherwise return FALSE. 488 489 Store the length of the subpath in NEXT_PATH_LENGTH. */ 490 491bool 492thread_jumps::check_subpath_and_update_thread_path (basic_block last_bb, 493 basic_block new_bb, 494 int *next_path_length) 495{ 496 edge e; 497 int e_count = 0; 498 edge_iterator ei; 499 auto_vec<basic_block> next_path; 500 501 FOR_EACH_EDGE (e, ei, last_bb->preds) 502 { 503 hash_set<basic_block> local_visited_bbs; 504 505 if (fsm_find_thread_path (new_bb, e->src, next_path, 506 local_visited_bbs, e->src->loop_father)) 507 ++e_count; 508 509 /* If there is more than one path, stop. */ 510 if (e_count > 1) 511 return false; 512 } 513 514 /* Stop if we have not found a path: this could occur when the recursion 515 is stopped by one of the bounds. */ 516 if (e_count == 0) 517 return false; 518 519 /* Make sure we haven't already visited any of the nodes in 520 NEXT_PATH. Don't add them here to avoid pollution. */ 521 for (unsigned int i = 0; i + 1 < next_path.length (); i++) 522 { 523 if (m_visited_bbs.contains (next_path[i])) 524 return false; 525 } 526 527 /* Now add the nodes to VISISTED_BBS. */ 528 for (unsigned int i = 0; i + 1 < next_path.length (); i++) 529 m_visited_bbs.add (next_path[i]); 530 531 /* Append all the nodes from NEXT_PATH to PATH. */ 532 m_path.safe_splice (next_path); 533 *next_path_length = next_path.length (); 534 535 return true; 536} 537 538/* If this is a profitable jump thread path, register it. 539 540 NAME is an SSA NAME with a possible constant value of ARG on PATH. 541 542 DEF_BB is the basic block that ultimately defines the constant. */ 543 544void 545thread_jumps::register_jump_thread_path_if_profitable (tree name, tree arg, 546 basic_block def_bb) 547{ 548 if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant) 549 return; 550 551 bool irreducible = false; 552 edge taken_edge = profitable_jump_thread_path (def_bb, name, arg, 553 &irreducible); 554 if (taken_edge) 555 { 556 convert_and_register_current_path (taken_edge); 557 m_path.pop (); 558 559 if (irreducible) 560 vect_free_loop_info_assumptions (m_path[0]->loop_father); 561 } 562} 563 564/* Given PHI which defines NAME in block DEF_BB, recurse through the 565 PHI's arguments searching for paths where NAME will ultimately have 566 a constant value. 567 568 PATH contains the series of blocks to traverse that will result in 569 NAME having a constant value. */ 570 571void 572thread_jumps::handle_phi (gphi *phi, tree name, basic_block def_bb) 573{ 574 /* Iterate over the arguments of PHI. */ 575 for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++) 576 { 577 tree arg = gimple_phi_arg_def (phi, i); 578 basic_block bbi = gimple_phi_arg_edge (phi, i)->src; 579 580 /* Skip edges pointing outside the current loop. */ 581 if (!arg || def_bb->loop_father != bbi->loop_father) 582 continue; 583 584 if (TREE_CODE (arg) == SSA_NAME) 585 { 586 m_path.safe_push (bbi); 587 /* Recursively follow SSA_NAMEs looking for a constant 588 definition. */ 589 fsm_find_control_statement_thread_paths (arg); 590 591 m_path.pop (); 592 continue; 593 } 594 595 register_jump_thread_path_if_profitable (name, arg, bbi); 596 } 597} 598 599/* Return TRUE if STMT is a gimple assignment we want to either directly 600 handle or recurse through. Return FALSE otherwise. 601 602 Note that adding more cases here requires adding cases to handle_assignment 603 below. */ 604 605static bool 606handle_assignment_p (gimple *stmt) 607{ 608 if (is_gimple_assign (stmt)) 609 { 610 enum tree_code def_code = gimple_assign_rhs_code (stmt); 611 612 /* If the RHS is an SSA_NAME, then we will recurse through it. 613 Go ahead and filter out cases where the SSA_NAME is a default 614 definition. There's little to be gained by trying to handle that. */ 615 if (def_code == SSA_NAME 616 && !SSA_NAME_IS_DEFAULT_DEF (gimple_assign_rhs1 (stmt))) 617 return true; 618 619 /* If the RHS is a constant, then it's a terminal that we'll want 620 to handle as well. */ 621 if (TREE_CODE_CLASS (def_code) == tcc_constant) 622 return true; 623 } 624 625 /* Anything not explicitly allowed is not handled. */ 626 return false; 627} 628 629/* Given STMT which defines NAME in block DEF_BB, recurse through the 630 PHI's arguments searching for paths where NAME will ultimately have 631 a constant value. 632 633 PATH contains the series of blocks to traverse that will result in 634 NAME having a constant value. */ 635 636void 637thread_jumps::handle_assignment (gimple *stmt, tree name, basic_block def_bb) 638{ 639 tree arg = gimple_assign_rhs1 (stmt); 640 641 if (TREE_CODE (arg) == SSA_NAME) 642 fsm_find_control_statement_thread_paths (arg); 643 644 else 645 { 646 /* register_jump_thread_path_if_profitable will push the current 647 block onto the path. But the path will always have the current 648 block at this point. So we can just pop it. */ 649 m_path.pop (); 650 651 register_jump_thread_path_if_profitable (name, arg, def_bb); 652 653 /* And put the current block back onto the path so that the 654 state of the stack is unchanged when we leave. */ 655 m_path.safe_push (def_bb); 656 } 657} 658 659/* We trace the value of the SSA_NAME NAME back through any phi nodes 660 looking for places where it gets a constant value and save the 661 path. */ 662 663void 664thread_jumps::fsm_find_control_statement_thread_paths (tree name) 665{ 666 /* If NAME appears in an abnormal PHI, then don't try to trace its 667 value back through PHI nodes. */ 668 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) 669 return; 670 671 gimple *def_stmt = SSA_NAME_DEF_STMT (name); 672 basic_block def_bb = gimple_bb (def_stmt); 673 674 if (def_bb == NULL) 675 return; 676 677 /* We allow the SSA chain to contains PHIs and simple copies and constant 678 initializations. */ 679 if (gimple_code (def_stmt) != GIMPLE_PHI 680 && gimple_code (def_stmt) != GIMPLE_ASSIGN) 681 return; 682 683 if (gimple_code (def_stmt) == GIMPLE_PHI 684 && (gimple_phi_num_args (def_stmt) 685 >= (unsigned) param_fsm_maximum_phi_arguments)) 686 return; 687 688 if (is_gimple_assign (def_stmt) 689 && ! handle_assignment_p (def_stmt)) 690 return; 691 692 /* Avoid infinite recursion. */ 693 if (m_visited_bbs.add (def_bb)) 694 return; 695 696 int next_path_length = 0; 697 basic_block last_bb_in_path = m_path.last (); 698 699 if (loop_containing_stmt (def_stmt)->header == gimple_bb (def_stmt)) 700 { 701 /* Do not walk through more than one loop PHI node. */ 702 if (m_seen_loop_phi) 703 return; 704 m_seen_loop_phi = true; 705 } 706 707 /* Following the chain of SSA_NAME definitions, we jumped from a definition in 708 LAST_BB_IN_PATH to a definition in DEF_BB. When these basic blocks are 709 different, append to PATH the blocks from LAST_BB_IN_PATH to DEF_BB. */ 710 if (def_bb != last_bb_in_path) 711 { 712 /* When DEF_BB == LAST_BB_IN_PATH, then the first block in the path 713 will already be in VISITED_BBS. When they are not equal, then we 714 must ensure that first block is accounted for to ensure we do not 715 create bogus jump threading paths. */ 716 m_visited_bbs.add (m_path[0]); 717 if (!check_subpath_and_update_thread_path (last_bb_in_path, def_bb, 718 &next_path_length)) 719 return; 720 } 721 722 gcc_assert (m_path.last () == def_bb); 723 724 if (gimple_code (def_stmt) == GIMPLE_PHI) 725 handle_phi (as_a <gphi *> (def_stmt), name, def_bb); 726 else if (gimple_code (def_stmt) == GIMPLE_ASSIGN) 727 handle_assignment (def_stmt, name, def_bb); 728 729 /* Remove all the nodes that we added from NEXT_PATH. */ 730 if (next_path_length) 731 m_path.truncate (m_path.length () - next_path_length); 732} 733 734/* Search backwards from BB looking for paths where NAME (an SSA_NAME) 735 is a constant. Record such paths for jump threading. 736 737 It is assumed that BB ends with a control statement and that by 738 finding a path where NAME is a constant, we can thread the path. 739 SPEED_P indicates that we could increase code size to improve the 740 code path. */ 741 742void 743thread_jumps::find_jump_threads_backwards (basic_block bb, bool speed_p) 744{ 745 gimple *stmt = get_gimple_control_stmt (bb); 746 if (!stmt) 747 return; 748 749 enum gimple_code code = gimple_code (stmt); 750 tree name = NULL; 751 if (code == GIMPLE_SWITCH) 752 name = gimple_switch_index (as_a <gswitch *> (stmt)); 753 else if (code == GIMPLE_GOTO) 754 name = gimple_goto_dest (stmt); 755 else if (code == GIMPLE_COND) 756 { 757 if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME 758 && TREE_CODE_CLASS (TREE_CODE (gimple_cond_rhs (stmt))) == tcc_constant 759 && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))) 760 || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))))) 761 name = gimple_cond_lhs (stmt); 762 } 763 764 if (!name || TREE_CODE (name) != SSA_NAME) 765 return; 766 767 /* Initialize pass local data that's different for each BB. */ 768 m_path.truncate (0); 769 m_path.safe_push (bb); 770 m_visited_bbs.empty (); 771 m_seen_loop_phi = false; 772 m_speed_p = speed_p; 773 m_max_threaded_paths = param_max_fsm_thread_paths; 774 775 fsm_find_control_statement_thread_paths (name); 776} 777 778namespace { 779 780const pass_data pass_data_thread_jumps = 781{ 782 GIMPLE_PASS, 783 "thread", 784 OPTGROUP_NONE, 785 TV_TREE_SSA_THREAD_JUMPS, 786 ( PROP_cfg | PROP_ssa ), 787 0, 788 0, 789 0, 790 TODO_update_ssa, 791}; 792 793class pass_thread_jumps : public gimple_opt_pass 794{ 795public: 796 pass_thread_jumps (gcc::context *ctxt) 797 : gimple_opt_pass (pass_data_thread_jumps, ctxt) 798 {} 799 800 opt_pass * clone (void) { return new pass_thread_jumps (m_ctxt); } 801 virtual bool gate (function *); 802 virtual unsigned int execute (function *); 803}; 804 805bool 806pass_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED) 807{ 808 return flag_expensive_optimizations; 809} 810 811 812unsigned int 813pass_thread_jumps::execute (function *fun) 814{ 815 loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES); 816 817 /* Try to thread each block with more than one successor. */ 818 thread_jumps threader; 819 basic_block bb; 820 FOR_EACH_BB_FN (bb, fun) 821 { 822 if (EDGE_COUNT (bb->succs) > 1) 823 threader.find_jump_threads_backwards (bb, true); 824 } 825 bool changed = thread_through_all_blocks (true); 826 827 loop_optimizer_finalize (); 828 return changed ? TODO_cleanup_cfg : 0; 829} 830 831} 832 833gimple_opt_pass * 834make_pass_thread_jumps (gcc::context *ctxt) 835{ 836 return new pass_thread_jumps (ctxt); 837} 838 839namespace { 840 841const pass_data pass_data_early_thread_jumps = 842{ 843 GIMPLE_PASS, 844 "ethread", 845 OPTGROUP_NONE, 846 TV_TREE_SSA_THREAD_JUMPS, 847 ( PROP_cfg | PROP_ssa ), 848 0, 849 0, 850 0, 851 ( TODO_cleanup_cfg | TODO_update_ssa ), 852}; 853 854class pass_early_thread_jumps : public gimple_opt_pass 855{ 856public: 857 pass_early_thread_jumps (gcc::context *ctxt) 858 : gimple_opt_pass (pass_data_early_thread_jumps, ctxt) 859 {} 860 861 opt_pass * clone (void) { return new pass_early_thread_jumps (m_ctxt); } 862 virtual bool gate (function *); 863 virtual unsigned int execute (function *); 864}; 865 866bool 867pass_early_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED) 868{ 869 return true; 870} 871 872 873unsigned int 874pass_early_thread_jumps::execute (function *fun) 875{ 876 loop_optimizer_init (AVOID_CFG_MODIFICATIONS); 877 878 /* Try to thread each block with more than one successor. */ 879 thread_jumps threader; 880 basic_block bb; 881 FOR_EACH_BB_FN (bb, fun) 882 { 883 if (EDGE_COUNT (bb->succs) > 1) 884 threader.find_jump_threads_backwards (bb, false); 885 } 886 thread_through_all_blocks (true); 887 888 loop_optimizer_finalize (); 889 return 0; 890} 891 892} 893 894gimple_opt_pass * 895make_pass_early_thread_jumps (gcc::context *ctxt) 896{ 897 return new pass_early_thread_jumps (ctxt); 898} 899