1 /* SSA Jump Threading 2 Copyright (C) 2005-2016 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 "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 "params.h" 33 #include "tree-ssa-loop.h" 34 #include "cfganal.h" 35 #include "tree-pass.h" 36 37 static int max_threaded_paths; 38 39 /* Simple helper to get the last statement from BB, which is assumed 40 to be a control statement. Return NULL if the last statement is 41 not a control statement. */ 42 43 static gimple * 44 get_gimple_control_stmt (basic_block bb) 45 { 46 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb); 47 48 if (gsi_end_p (gsi)) 49 return NULL; 50 51 gimple *stmt = gsi_stmt (gsi); 52 enum gimple_code code = gimple_code (stmt); 53 if (code == GIMPLE_COND || code == GIMPLE_SWITCH || code == GIMPLE_GOTO) 54 return stmt; 55 return NULL; 56 } 57 58 /* Return true if the CFG contains at least one path from START_BB to END_BB. 59 When a path is found, record in PATH the blocks from END_BB to START_BB. 60 VISITED_BBS is used to make sure we don't fall into an infinite loop. Bound 61 the recursion to basic blocks belonging to LOOP. */ 62 63 static bool 64 fsm_find_thread_path (basic_block start_bb, basic_block end_bb, 65 vec<basic_block, va_gc> *&path, 66 hash_set<basic_block> *visited_bbs, loop_p loop) 67 { 68 if (loop != start_bb->loop_father) 69 return false; 70 71 if (start_bb == end_bb) 72 { 73 vec_safe_push (path, start_bb); 74 return true; 75 } 76 77 if (!visited_bbs->add (start_bb)) 78 { 79 edge e; 80 edge_iterator ei; 81 FOR_EACH_EDGE (e, ei, start_bb->succs) 82 if (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, loop)) 83 { 84 vec_safe_push (path, start_bb); 85 return true; 86 } 87 } 88 89 return false; 90 } 91 92 /* We trace the value of the SSA_NAME NAME back through any phi nodes looking 93 for places where it gets a constant value and save the path. Stop after 94 having recorded MAX_PATHS jump threading paths. */ 95 96 static void 97 fsm_find_control_statement_thread_paths (tree name, 98 hash_set<basic_block> *visited_bbs, 99 vec<basic_block, va_gc> *&path, 100 bool seen_loop_phi) 101 { 102 /* If NAME appears in an abnormal PHI, then don't try to trace its 103 value back through PHI nodes. */ 104 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) 105 return; 106 107 gimple *def_stmt = SSA_NAME_DEF_STMT (name); 108 basic_block var_bb = gimple_bb (def_stmt); 109 110 if (var_bb == NULL) 111 return; 112 113 /* For the moment we assume that an SSA chain only contains phi nodes, and 114 eventually one of the phi arguments will be an integer constant. In the 115 future, this could be extended to also handle simple assignments of 116 arithmetic operations. */ 117 if (gimple_code (def_stmt) != GIMPLE_PHI 118 || (gimple_phi_num_args (def_stmt) 119 >= (unsigned) PARAM_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS))) 120 return; 121 122 /* Avoid infinite recursion. */ 123 if (visited_bbs->add (var_bb)) 124 return; 125 126 gphi *phi = as_a <gphi *> (def_stmt); 127 int next_path_length = 0; 128 basic_block last_bb_in_path = path->last (); 129 130 if (loop_containing_stmt (phi)->header == gimple_bb (phi)) 131 { 132 /* Do not walk through more than one loop PHI node. */ 133 if (seen_loop_phi) 134 return; 135 seen_loop_phi = true; 136 } 137 138 /* Following the chain of SSA_NAME definitions, we jumped from a definition in 139 LAST_BB_IN_PATH to a definition in VAR_BB. When these basic blocks are 140 different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB. */ 141 if (var_bb != last_bb_in_path) 142 { 143 edge e; 144 int e_count = 0; 145 edge_iterator ei; 146 vec<basic_block, va_gc> *next_path; 147 vec_alloc (next_path, 10); 148 149 /* When VAR_BB == LAST_BB_IN_PATH, then the first block in the path 150 will already be in VISITED_BBS. When they are not equal, then we 151 must ensure that first block is accounted for to ensure we do not 152 create bogus jump threading paths. */ 153 visited_bbs->add ((*path)[0]); 154 FOR_EACH_EDGE (e, ei, last_bb_in_path->preds) 155 { 156 hash_set<basic_block> *visited_bbs = new hash_set<basic_block>; 157 158 if (fsm_find_thread_path (var_bb, e->src, next_path, visited_bbs, 159 e->src->loop_father)) 160 ++e_count; 161 162 delete visited_bbs; 163 164 /* If there is more than one path, stop. */ 165 if (e_count > 1) 166 { 167 vec_free (next_path); 168 return; 169 } 170 } 171 172 /* Stop if we have not found a path: this could occur when the recursion 173 is stopped by one of the bounds. */ 174 if (e_count == 0) 175 { 176 vec_free (next_path); 177 return; 178 } 179 180 /* Make sure we haven't already visited any of the nodes in 181 NEXT_PATH. Don't add them here to avoid pollution. */ 182 for (unsigned int i = 0; i < next_path->length () - 1; i++) 183 { 184 if (visited_bbs->contains ((*next_path)[i])) 185 { 186 vec_free (next_path); 187 return; 188 } 189 } 190 191 /* Now add the nodes to VISISTED_BBS. */ 192 for (unsigned int i = 0; i < next_path->length () - 1; i++) 193 visited_bbs->add ((*next_path)[i]); 194 195 /* Append all the nodes from NEXT_PATH to PATH. */ 196 vec_safe_splice (path, next_path); 197 next_path_length = next_path->length (); 198 vec_free (next_path); 199 } 200 201 gcc_assert (path->last () == var_bb); 202 203 /* Iterate over the arguments of PHI. */ 204 unsigned int i; 205 if (gimple_phi_num_args (phi) 206 < (unsigned) PARAM_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS)) 207 { 208 for (i = 0; i < gimple_phi_num_args (phi); i++) 209 { 210 tree arg = gimple_phi_arg_def (phi, i); 211 basic_block bbi = gimple_phi_arg_edge (phi, i)->src; 212 213 /* Skip edges pointing outside the current loop. */ 214 if (!arg || var_bb->loop_father != bbi->loop_father) 215 continue; 216 217 if (TREE_CODE (arg) == SSA_NAME) 218 { 219 vec_safe_push (path, bbi); 220 /* Recursively follow SSA_NAMEs looking for a constant 221 definition. */ 222 fsm_find_control_statement_thread_paths (arg, visited_bbs, path, 223 seen_loop_phi); 224 225 path->pop (); 226 continue; 227 } 228 229 if (TREE_CODE (arg) != INTEGER_CST) 230 continue; 231 232 /* Note BBI is not in the path yet, hence the +1 in the test below 233 to make sure BBI is accounted for in the path length test. */ 234 int path_length = path->length (); 235 if (path_length + 1 > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH)) 236 { 237 if (dump_file && (dump_flags & TDF_DETAILS)) 238 fprintf (dump_file, "FSM jump-thread path not considered: " 239 "the number of basic blocks on the path " 240 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n"); 241 continue; 242 } 243 244 if (max_threaded_paths <= 0) 245 { 246 if (dump_file && (dump_flags & TDF_DETAILS)) 247 fprintf (dump_file, "FSM jump-thread path not considered: " 248 "the number of previously recorded FSM paths to " 249 "thread exceeds PARAM_MAX_FSM_THREAD_PATHS.\n"); 250 continue; 251 } 252 253 /* Add BBI to the path. */ 254 vec_safe_push (path, bbi); 255 ++path_length; 256 257 int n_insns = 0; 258 gimple_stmt_iterator gsi; 259 int j; 260 loop_p loop = (*path)[0]->loop_father; 261 bool path_crosses_loops = false; 262 bool threaded_through_latch = false; 263 bool multiway_branch_in_path = false; 264 bool threaded_multiway_branch = false; 265 266 /* Count the number of instructions on the path: as these instructions 267 will have to be duplicated, we will not record the path if there 268 are too many instructions on the path. Also check that all the 269 blocks in the path belong to a single loop. */ 270 for (j = 0; j < path_length; j++) 271 { 272 basic_block bb = (*path)[j]; 273 274 /* Remember, blocks in the path are stored in opposite order 275 in the PATH array. The last entry in the array represents 276 the block with an outgoing edge that we will redirect to the 277 jump threading path. Thus we don't care about that block's 278 loop father, nor how many statements are in that block because 279 it will not be copied or whether or not it ends in a multiway 280 branch. */ 281 if (j < path_length - 1) 282 { 283 if (bb->loop_father != loop) 284 { 285 path_crosses_loops = true; 286 break; 287 } 288 289 /* PHIs in the path will create degenerate PHIS in the 290 copied path which will then get propagated away, so 291 looking at just the duplicate path the PHIs would 292 seem unimportant. 293 294 But those PHIs, because they're assignments to objects 295 typically with lives that exist outside the thread path, 296 will tend to generate PHIs (or at least new PHI arguments) 297 at points where we leave the thread path and rejoin 298 the original blocks. So we do want to account for them. 299 300 We ignore virtual PHIs. We also ignore cases where BB 301 has a single incoming edge. That's the most common 302 degenerate PHI we'll see here. Finally we ignore PHIs 303 that are associated with the value we're tracking as 304 that object likely dies. */ 305 if (EDGE_COUNT (bb->succs) > 1 && EDGE_COUNT (bb->preds) > 1) 306 { 307 for (gphi_iterator gsip = gsi_start_phis (bb); 308 !gsi_end_p (gsip); 309 gsi_next (&gsip)) 310 { 311 gphi *phi = gsip.phi (); 312 tree dst = gimple_phi_result (phi); 313 314 /* Note that if both NAME and DST are anonymous 315 SSA_NAMEs, then we do not have enough information 316 to consider them associated. */ 317 if ((SSA_NAME_VAR (dst) != SSA_NAME_VAR (name) 318 || !SSA_NAME_VAR (dst)) 319 && !virtual_operand_p (dst)) 320 ++n_insns; 321 } 322 } 323 324 for (gsi = gsi_after_labels (bb); 325 !gsi_end_p (gsi); 326 gsi_next_nondebug (&gsi)) 327 { 328 gimple *stmt = gsi_stmt (gsi); 329 /* Do not count empty statements and labels. */ 330 if (gimple_code (stmt) != GIMPLE_NOP 331 && !(gimple_code (stmt) == GIMPLE_ASSIGN 332 && gimple_assign_rhs_code (stmt) == ASSERT_EXPR) 333 && !is_gimple_debug (stmt)) 334 ++n_insns; 335 } 336 337 /* We do not look at the block with the threaded branch 338 in this loop. So if any block with a last statement that 339 is a GIMPLE_SWITCH or GIMPLE_GOTO is seen, then we have a 340 multiway branch on our path. 341 342 The block in PATH[0] is special, it's the block were we're 343 going to be able to eliminate its branch. */ 344 gimple *last = last_stmt (bb); 345 if (last && (gimple_code (last) == GIMPLE_SWITCH 346 || gimple_code (last) == GIMPLE_GOTO)) 347 { 348 if (j == 0) 349 threaded_multiway_branch = true; 350 else 351 multiway_branch_in_path = true; 352 } 353 } 354 355 /* Note if we thread through the latch, we will want to include 356 the last entry in the array when determining if we thread 357 through the loop latch. */ 358 if (loop->latch == bb) 359 threaded_through_latch = true; 360 } 361 362 /* We are going to remove the control statement at the end of the 363 last block in the threading path. So don't count it against our 364 statement count. */ 365 n_insns--; 366 367 gimple *stmt = get_gimple_control_stmt ((*path)[0]); 368 gcc_assert (stmt); 369 /* We have found a constant value for ARG. For GIMPLE_SWITCH 370 and GIMPLE_GOTO, we use it as-is. However, for a GIMPLE_COND 371 we need to substitute, fold and simplify so we can determine 372 the edge taken out of the last block. */ 373 if (gimple_code (stmt) == GIMPLE_COND) 374 { 375 enum tree_code cond_code = gimple_cond_code (stmt); 376 377 /* We know the underyling format of the condition. */ 378 arg = fold_binary (cond_code, boolean_type_node, 379 arg, gimple_cond_rhs (stmt)); 380 } 381 382 /* If this path threaded through the loop latch back into the 383 same loop and the destination does not dominate the loop 384 latch, then this thread would create an irreducible loop. 385 386 We have to know the outgoing edge to figure this out. */ 387 edge taken_edge = find_taken_edge ((*path)[0], arg); 388 389 /* There are cases where we may not be able to extract the 390 taken edge. For example, a computed goto to an absolute 391 address. Handle those cases gracefully. */ 392 if (taken_edge == NULL) 393 { 394 path->pop (); 395 continue; 396 } 397 398 bool creates_irreducible_loop = false; 399 if (threaded_through_latch 400 && loop == taken_edge->dest->loop_father 401 && (determine_bb_domination_status (loop, taken_edge->dest) 402 == DOMST_NONDOMINATING)) 403 creates_irreducible_loop = true; 404 405 if (path_crosses_loops) 406 { 407 if (dump_file && (dump_flags & TDF_DETAILS)) 408 fprintf (dump_file, "FSM jump-thread path not considered: " 409 "the path crosses loops.\n"); 410 path->pop (); 411 continue; 412 } 413 414 if (n_insns >= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS)) 415 { 416 if (dump_file && (dump_flags & TDF_DETAILS)) 417 fprintf (dump_file, "FSM jump-thread path not considered: " 418 "the number of instructions on the path " 419 "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n"); 420 path->pop (); 421 continue; 422 } 423 424 /* We avoid creating irreducible inner loops unless we thread through 425 a multiway branch, in which case we have deemed it worth losing 426 other loop optimizations later. 427 428 We also consider it worth creating an irreducible inner loop if 429 the number of copied statement is low relative to the length of 430 the path -- in that case there's little the traditional loop 431 optimizer would have done anyway, so an irreducible loop is not 432 so bad. */ 433 if (!threaded_multiway_branch && creates_irreducible_loop 434 && (n_insns * PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS) 435 > path_length * PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS))) 436 437 { 438 if (dump_file && (dump_flags & TDF_DETAILS)) 439 fprintf (dump_file, 440 "FSM would create irreducible loop without threading " 441 "multiway branch.\n"); 442 path->pop (); 443 continue; 444 } 445 446 447 /* If this path does not thread through the loop latch, then we are 448 using the FSM threader to find old style jump threads. This 449 is good, except the FSM threader does not re-use an existing 450 threading path to reduce code duplication. 451 452 So for that case, drastically reduce the number of statements 453 we are allowed to copy. */ 454 if (!(threaded_through_latch && threaded_multiway_branch) 455 && (n_insns * PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS) 456 >= PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS))) 457 { 458 if (dump_file && (dump_flags & TDF_DETAILS)) 459 fprintf (dump_file, 460 "FSM did not thread around loop and would copy too " 461 "many statements.\n"); 462 path->pop (); 463 continue; 464 } 465 466 /* When there is a multi-way branch on the path, then threading can 467 explode the CFG due to duplicating the edges for that multi-way 468 branch. So like above, only allow a multi-way branch on the path 469 if we actually thread a multi-way branch. */ 470 if (!threaded_multiway_branch && multiway_branch_in_path) 471 { 472 if (dump_file && (dump_flags & TDF_DETAILS)) 473 fprintf (dump_file, 474 "FSM Thread through multiway branch without threading " 475 "a multiway branch.\n"); 476 path->pop (); 477 continue; 478 } 479 480 vec<jump_thread_edge *> *jump_thread_path 481 = new vec<jump_thread_edge *> (); 482 483 /* Record the edges between the blocks in PATH. */ 484 for (j = 0; j < path_length - 1; j++) 485 { 486 edge e = find_edge ((*path)[path_length - j - 1], 487 (*path)[path_length - j - 2]); 488 gcc_assert (e); 489 jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD); 490 jump_thread_path->safe_push (x); 491 } 492 493 /* Add the edge taken when the control variable has value ARG. */ 494 jump_thread_edge *x 495 = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK); 496 jump_thread_path->safe_push (x); 497 498 register_jump_thread (jump_thread_path); 499 --max_threaded_paths; 500 501 /* Remove BBI from the path. */ 502 path->pop (); 503 } 504 } 505 506 /* Remove all the nodes that we added from NEXT_PATH. */ 507 if (next_path_length) 508 vec_safe_truncate (path, (path->length () - next_path_length)); 509 } 510 511 /* Search backwards from BB looking for paths where NAME (an SSA_NAME) 512 is a constant. Record such paths for jump threading. 513 514 It is assumed that BB ends with a control statement and that by 515 finding a path where NAME is a constant, we can thread the path. */ 516 517 void 518 find_jump_threads_backwards (edge e) 519 { 520 if (!flag_expensive_optimizations 521 || optimize_function_for_size_p (cfun) 522 || e->dest->loop_father != e->src->loop_father 523 || loop_depth (e->dest->loop_father) == 0) 524 return; 525 526 gimple *stmt = get_gimple_control_stmt (e->dest); 527 if (!stmt) 528 return; 529 530 enum gimple_code code = gimple_code (stmt); 531 tree name = NULL; 532 if (code == GIMPLE_SWITCH) 533 name = gimple_switch_index (as_a <gswitch *> (stmt)); 534 else if (code == GIMPLE_GOTO) 535 name = gimple_goto_dest (stmt); 536 else if (code == GIMPLE_COND) 537 { 538 if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME 539 && TREE_CODE (gimple_cond_rhs (stmt)) == INTEGER_CST 540 && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))) 541 || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))))) 542 name = gimple_cond_lhs (stmt); 543 } 544 545 if (!name || TREE_CODE (name) != SSA_NAME) 546 return; 547 548 vec<basic_block, va_gc> *bb_path; 549 vec_alloc (bb_path, 10); 550 vec_safe_push (bb_path, e->dest); 551 hash_set<basic_block> *visited_bbs = new hash_set<basic_block>; 552 553 max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS); 554 fsm_find_control_statement_thread_paths (name, visited_bbs, bb_path, false); 555 556 delete visited_bbs; 557 vec_free (bb_path); 558 } 559