1 /* SSA Jump Threading 2 Copyright (C) 2005-2015 Free Software Foundation, Inc. 3 Contributed by Jeff Law <law@redhat.com> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "tm.h" 25 #include "hash-set.h" 26 #include "machmode.h" 27 #include "vec.h" 28 #include "double-int.h" 29 #include "input.h" 30 #include "alias.h" 31 #include "symtab.h" 32 #include "wide-int.h" 33 #include "inchash.h" 34 #include "tree.h" 35 #include "fold-const.h" 36 #include "flags.h" 37 #include "tm_p.h" 38 #include "predict.h" 39 #include "hard-reg-set.h" 40 #include "input.h" 41 #include "function.h" 42 #include "dominance.h" 43 #include "basic-block.h" 44 #include "cfgloop.h" 45 #include "timevar.h" 46 #include "dumpfile.h" 47 #include "tree-ssa-alias.h" 48 #include "internal-fn.h" 49 #include "gimple-expr.h" 50 #include "is-a.h" 51 #include "gimple.h" 52 #include "gimple-iterator.h" 53 #include "gimple-ssa.h" 54 #include "tree-cfg.h" 55 #include "tree-phinodes.h" 56 #include "ssa-iterators.h" 57 #include "stringpool.h" 58 #include "tree-ssanames.h" 59 #include "tree-ssa-propagate.h" 60 #include "tree-ssa-threadupdate.h" 61 #include "langhooks.h" 62 #include "params.h" 63 #include "tree-ssa-threadedge.h" 64 #include "tree-ssa-loop.h" 65 #include "builtins.h" 66 #include "cfg.h" 67 #include "cfganal.h" 68 69 /* To avoid code explosion due to jump threading, we limit the 70 number of statements we are going to copy. This variable 71 holds the number of statements currently seen that we'll have 72 to copy as part of the jump threading process. */ 73 static int stmt_count; 74 75 /* Array to record value-handles per SSA_NAME. */ 76 vec<tree> ssa_name_values; 77 78 /* Set the value for the SSA name NAME to VALUE. */ 79 80 void 81 set_ssa_name_value (tree name, tree value) 82 { 83 if (SSA_NAME_VERSION (name) >= ssa_name_values.length ()) 84 ssa_name_values.safe_grow_cleared (SSA_NAME_VERSION (name) + 1); 85 if (value && TREE_OVERFLOW_P (value)) 86 value = drop_tree_overflow (value); 87 ssa_name_values[SSA_NAME_VERSION (name)] = value; 88 } 89 90 /* Initialize the per SSA_NAME value-handles array. Returns it. */ 91 void 92 threadedge_initialize_values (void) 93 { 94 gcc_assert (!ssa_name_values.exists ()); 95 ssa_name_values.create (num_ssa_names); 96 } 97 98 /* Free the per SSA_NAME value-handle array. */ 99 void 100 threadedge_finalize_values (void) 101 { 102 ssa_name_values.release (); 103 } 104 105 /* Return TRUE if we may be able to thread an incoming edge into 106 BB to an outgoing edge from BB. Return FALSE otherwise. */ 107 108 bool 109 potentially_threadable_block (basic_block bb) 110 { 111 gimple_stmt_iterator gsi; 112 113 /* Special case. We can get blocks that are forwarders, but are 114 not optimized away because they forward from outside a loop 115 to the loop header. We want to thread through them as we can 116 sometimes thread to the loop exit, which is obviously profitable. 117 the interesting case here is when the block has PHIs. */ 118 if (gsi_end_p (gsi_start_nondebug_bb (bb)) 119 && !gsi_end_p (gsi_start_phis (bb))) 120 return true; 121 122 /* If BB has a single successor or a single predecessor, then 123 there is no threading opportunity. */ 124 if (single_succ_p (bb) || single_pred_p (bb)) 125 return false; 126 127 /* If BB does not end with a conditional, switch or computed goto, 128 then there is no threading opportunity. */ 129 gsi = gsi_last_bb (bb); 130 if (gsi_end_p (gsi) 131 || ! gsi_stmt (gsi) 132 || (gimple_code (gsi_stmt (gsi)) != GIMPLE_COND 133 && gimple_code (gsi_stmt (gsi)) != GIMPLE_GOTO 134 && gimple_code (gsi_stmt (gsi)) != GIMPLE_SWITCH)) 135 return false; 136 137 return true; 138 } 139 140 /* Return the LHS of any ASSERT_EXPR where OP appears as the first 141 argument to the ASSERT_EXPR and in which the ASSERT_EXPR dominates 142 BB. If no such ASSERT_EXPR is found, return OP. */ 143 144 static tree 145 lhs_of_dominating_assert (tree op, basic_block bb, gimple stmt) 146 { 147 imm_use_iterator imm_iter; 148 gimple use_stmt; 149 use_operand_p use_p; 150 151 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, op) 152 { 153 use_stmt = USE_STMT (use_p); 154 if (use_stmt != stmt 155 && gimple_assign_single_p (use_stmt) 156 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ASSERT_EXPR 157 && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == op 158 && dominated_by_p (CDI_DOMINATORS, bb, gimple_bb (use_stmt))) 159 { 160 return gimple_assign_lhs (use_stmt); 161 } 162 } 163 return op; 164 } 165 166 /* We record temporary equivalences created by PHI nodes or 167 statements within the target block. Doing so allows us to 168 identify more jump threading opportunities, even in blocks 169 with side effects. 170 171 We keep track of those temporary equivalences in a stack 172 structure so that we can unwind them when we're done processing 173 a particular edge. This routine handles unwinding the data 174 structures. */ 175 176 static void 177 remove_temporary_equivalences (vec<tree> *stack) 178 { 179 while (stack->length () > 0) 180 { 181 tree prev_value, dest; 182 183 dest = stack->pop (); 184 185 /* A NULL value indicates we should stop unwinding, otherwise 186 pop off the next entry as they're recorded in pairs. */ 187 if (dest == NULL) 188 break; 189 190 prev_value = stack->pop (); 191 set_ssa_name_value (dest, prev_value); 192 } 193 } 194 195 /* Record a temporary equivalence, saving enough information so that 196 we can restore the state of recorded equivalences when we're 197 done processing the current edge. */ 198 199 static void 200 record_temporary_equivalence (tree x, tree y, vec<tree> *stack) 201 { 202 tree prev_x = SSA_NAME_VALUE (x); 203 204 /* Y may be NULL if we are invalidating entries in the table. */ 205 if (y && TREE_CODE (y) == SSA_NAME) 206 { 207 tree tmp = SSA_NAME_VALUE (y); 208 y = tmp ? tmp : y; 209 } 210 211 set_ssa_name_value (x, y); 212 stack->reserve (2); 213 stack->quick_push (prev_x); 214 stack->quick_push (x); 215 } 216 217 /* Record temporary equivalences created by PHIs at the target of the 218 edge E. Record unwind information for the equivalences onto STACK. 219 220 If a PHI which prevents threading is encountered, then return FALSE 221 indicating we should not thread this edge, else return TRUE. 222 223 If SRC_MAP/DST_MAP exist, then mark the source and destination SSA_NAMEs 224 of any equivalences recorded. We use this to make invalidation after 225 traversing back edges less painful. */ 226 227 static bool 228 record_temporary_equivalences_from_phis (edge e, vec<tree> *stack) 229 { 230 gphi_iterator gsi; 231 232 /* Each PHI creates a temporary equivalence, record them. 233 These are context sensitive equivalences and will be removed 234 later. */ 235 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) 236 { 237 gphi *phi = gsi.phi (); 238 tree src = PHI_ARG_DEF_FROM_EDGE (phi, e); 239 tree dst = gimple_phi_result (phi); 240 241 /* If the desired argument is not the same as this PHI's result 242 and it is set by a PHI in E->dest, then we can not thread 243 through E->dest. */ 244 if (src != dst 245 && TREE_CODE (src) == SSA_NAME 246 && gimple_code (SSA_NAME_DEF_STMT (src)) == GIMPLE_PHI 247 && gimple_bb (SSA_NAME_DEF_STMT (src)) == e->dest) 248 return false; 249 250 /* We consider any non-virtual PHI as a statement since it 251 count result in a constant assignment or copy operation. */ 252 if (!virtual_operand_p (dst)) 253 stmt_count++; 254 255 record_temporary_equivalence (dst, src, stack); 256 } 257 return true; 258 } 259 260 /* Fold the RHS of an assignment statement and return it as a tree. 261 May return NULL_TREE if no simplification is possible. */ 262 263 static tree 264 fold_assignment_stmt (gimple stmt) 265 { 266 enum tree_code subcode = gimple_assign_rhs_code (stmt); 267 268 switch (get_gimple_rhs_class (subcode)) 269 { 270 case GIMPLE_SINGLE_RHS: 271 return fold (gimple_assign_rhs1 (stmt)); 272 273 case GIMPLE_UNARY_RHS: 274 { 275 tree lhs = gimple_assign_lhs (stmt); 276 tree op0 = gimple_assign_rhs1 (stmt); 277 return fold_unary (subcode, TREE_TYPE (lhs), op0); 278 } 279 280 case GIMPLE_BINARY_RHS: 281 { 282 tree lhs = gimple_assign_lhs (stmt); 283 tree op0 = gimple_assign_rhs1 (stmt); 284 tree op1 = gimple_assign_rhs2 (stmt); 285 return fold_binary (subcode, TREE_TYPE (lhs), op0, op1); 286 } 287 288 case GIMPLE_TERNARY_RHS: 289 { 290 tree lhs = gimple_assign_lhs (stmt); 291 tree op0 = gimple_assign_rhs1 (stmt); 292 tree op1 = gimple_assign_rhs2 (stmt); 293 tree op2 = gimple_assign_rhs3 (stmt); 294 295 /* Sadly, we have to handle conditional assignments specially 296 here, because fold expects all the operands of an expression 297 to be folded before the expression itself is folded, but we 298 can't just substitute the folded condition here. */ 299 if (gimple_assign_rhs_code (stmt) == COND_EXPR) 300 op0 = fold (op0); 301 302 return fold_ternary (subcode, TREE_TYPE (lhs), op0, op1, op2); 303 } 304 305 default: 306 gcc_unreachable (); 307 } 308 } 309 310 /* A new value has been assigned to LHS. If necessary, invalidate any 311 equivalences that are no longer valid. This includes invaliding 312 LHS and any objects that are currently equivalent to LHS. 313 314 Finding the objects that are currently marked as equivalent to LHS 315 is a bit tricky. We could walk the ssa names and see if any have 316 SSA_NAME_VALUE that is the same as LHS. That's expensive. 317 318 However, it's far more efficient to look at the unwinding stack as 319 that will have all context sensitive equivalences which are the only 320 ones that we really have to worry about here. */ 321 static void 322 invalidate_equivalences (tree lhs, vec<tree> *stack) 323 { 324 325 /* The stack is an unwinding stack. If the current element is NULL 326 then it's a "stop unwinding" marker. Else the current marker is 327 the SSA_NAME with an equivalence and the prior entry in the stack 328 is what the current element is equivalent to. */ 329 for (int i = stack->length() - 1; i >= 0; i--) 330 { 331 /* Ignore the stop unwinding markers. */ 332 if ((*stack)[i] == NULL) 333 continue; 334 335 /* We want to check the current value of stack[i] to see if 336 it matches LHS. If so, then invalidate. */ 337 if (SSA_NAME_VALUE ((*stack)[i]) == lhs) 338 record_temporary_equivalence ((*stack)[i], NULL_TREE, stack); 339 340 /* Remember, we're dealing with two elements in this case. */ 341 i--; 342 } 343 344 /* And invalidate any known value for LHS itself. */ 345 if (SSA_NAME_VALUE (lhs)) 346 record_temporary_equivalence (lhs, NULL_TREE, stack); 347 } 348 349 /* Try to simplify each statement in E->dest, ultimately leading to 350 a simplification of the COND_EXPR at the end of E->dest. 351 352 Record unwind information for temporary equivalences onto STACK. 353 354 Use SIMPLIFY (a pointer to a callback function) to further simplify 355 statements using pass specific information. 356 357 We might consider marking just those statements which ultimately 358 feed the COND_EXPR. It's not clear if the overhead of bookkeeping 359 would be recovered by trying to simplify fewer statements. 360 361 If we are able to simplify a statement into the form 362 SSA_NAME = (SSA_NAME | gimple invariant), then we can record 363 a context sensitive equivalence which may help us simplify 364 later statements in E->dest. */ 365 366 static gimple 367 record_temporary_equivalences_from_stmts_at_dest (edge e, 368 vec<tree> *stack, 369 tree (*simplify) (gimple, 370 gimple), 371 bool backedge_seen) 372 { 373 gimple stmt = NULL; 374 gimple_stmt_iterator gsi; 375 int max_stmt_count; 376 377 max_stmt_count = PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS); 378 379 /* Walk through each statement in the block recording equivalences 380 we discover. Note any equivalences we discover are context 381 sensitive (ie, are dependent on traversing E) and must be unwound 382 when we're finished processing E. */ 383 for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) 384 { 385 tree cached_lhs = NULL; 386 387 stmt = gsi_stmt (gsi); 388 389 /* Ignore empty statements and labels. */ 390 if (gimple_code (stmt) == GIMPLE_NOP 391 || gimple_code (stmt) == GIMPLE_LABEL 392 || is_gimple_debug (stmt)) 393 continue; 394 395 /* If the statement has volatile operands, then we assume we 396 can not thread through this block. This is overly 397 conservative in some ways. */ 398 if (gimple_code (stmt) == GIMPLE_ASM 399 && gimple_asm_volatile_p (as_a <gasm *> (stmt))) 400 return NULL; 401 402 /* If duplicating this block is going to cause too much code 403 expansion, then do not thread through this block. */ 404 stmt_count++; 405 if (stmt_count > max_stmt_count) 406 return NULL; 407 408 /* If this is not a statement that sets an SSA_NAME to a new 409 value, then do not try to simplify this statement as it will 410 not simplify in any way that is helpful for jump threading. */ 411 if ((gimple_code (stmt) != GIMPLE_ASSIGN 412 || TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME) 413 && (gimple_code (stmt) != GIMPLE_CALL 414 || gimple_call_lhs (stmt) == NULL_TREE 415 || TREE_CODE (gimple_call_lhs (stmt)) != SSA_NAME)) 416 { 417 /* STMT might still have DEFS and we need to invalidate any known 418 equivalences for them. 419 420 Consider if STMT is a GIMPLE_ASM with one or more outputs that 421 feeds a conditional inside a loop. We might derive an equivalence 422 due to the conditional. */ 423 tree op; 424 ssa_op_iter iter; 425 426 if (backedge_seen) 427 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF) 428 invalidate_equivalences (op, stack); 429 430 continue; 431 } 432 433 /* The result of __builtin_object_size depends on all the arguments 434 of a phi node. Temporarily using only one edge produces invalid 435 results. For example 436 437 if (x < 6) 438 goto l; 439 else 440 goto l; 441 442 l: 443 r = PHI <&w[2].a[1](2), &a.a[6](3)> 444 __builtin_object_size (r, 0) 445 446 The result of __builtin_object_size is defined to be the maximum of 447 remaining bytes. If we use only one edge on the phi, the result will 448 change to be the remaining bytes for the corresponding phi argument. 449 450 Similarly for __builtin_constant_p: 451 452 r = PHI <1(2), 2(3)> 453 __builtin_constant_p (r) 454 455 Both PHI arguments are constant, but x ? 1 : 2 is still not 456 constant. */ 457 458 if (is_gimple_call (stmt)) 459 { 460 tree fndecl = gimple_call_fndecl (stmt); 461 if (fndecl 462 && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_OBJECT_SIZE 463 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P)) 464 { 465 if (backedge_seen) 466 { 467 tree lhs = gimple_get_lhs (stmt); 468 invalidate_equivalences (lhs, stack); 469 } 470 continue; 471 } 472 } 473 474 /* At this point we have a statement which assigns an RHS to an 475 SSA_VAR on the LHS. We want to try and simplify this statement 476 to expose more context sensitive equivalences which in turn may 477 allow us to simplify the condition at the end of the loop. 478 479 Handle simple copy operations as well as implied copies from 480 ASSERT_EXPRs. */ 481 if (gimple_assign_single_p (stmt) 482 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME) 483 cached_lhs = gimple_assign_rhs1 (stmt); 484 else if (gimple_assign_single_p (stmt) 485 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR) 486 cached_lhs = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0); 487 else 488 { 489 /* A statement that is not a trivial copy or ASSERT_EXPR. 490 We're going to temporarily copy propagate the operands 491 and see if that allows us to simplify this statement. */ 492 tree *copy; 493 ssa_op_iter iter; 494 use_operand_p use_p; 495 unsigned int num, i = 0; 496 497 num = NUM_SSA_OPERANDS (stmt, (SSA_OP_USE | SSA_OP_VUSE)); 498 copy = XCNEWVEC (tree, num); 499 500 /* Make a copy of the uses & vuses into USES_COPY, then cprop into 501 the operands. */ 502 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE) 503 { 504 tree tmp = NULL; 505 tree use = USE_FROM_PTR (use_p); 506 507 copy[i++] = use; 508 if (TREE_CODE (use) == SSA_NAME) 509 tmp = SSA_NAME_VALUE (use); 510 if (tmp) 511 SET_USE (use_p, tmp); 512 } 513 514 /* Try to fold/lookup the new expression. Inserting the 515 expression into the hash table is unlikely to help. */ 516 if (is_gimple_call (stmt)) 517 cached_lhs = fold_call_stmt (as_a <gcall *> (stmt), false); 518 else 519 cached_lhs = fold_assignment_stmt (stmt); 520 521 if (!cached_lhs 522 || (TREE_CODE (cached_lhs) != SSA_NAME 523 && !is_gimple_min_invariant (cached_lhs))) 524 cached_lhs = (*simplify) (stmt, stmt); 525 526 /* Restore the statement's original uses/defs. */ 527 i = 0; 528 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE) 529 SET_USE (use_p, copy[i++]); 530 531 free (copy); 532 } 533 534 /* Record the context sensitive equivalence if we were able 535 to simplify this statement. 536 537 If we have traversed a backedge at some point during threading, 538 then always enter something here. Either a real equivalence, 539 or a NULL_TREE equivalence which is effectively invalidation of 540 prior equivalences. */ 541 if (cached_lhs 542 && (TREE_CODE (cached_lhs) == SSA_NAME 543 || is_gimple_min_invariant (cached_lhs))) 544 record_temporary_equivalence (gimple_get_lhs (stmt), cached_lhs, stack); 545 else if (backedge_seen) 546 invalidate_equivalences (gimple_get_lhs (stmt), stack); 547 } 548 return stmt; 549 } 550 551 /* Once we have passed a backedge in the CFG when threading, we do not want to 552 utilize edge equivalences for simplification purpose. They are no longer 553 necessarily valid. We use this callback rather than the ones provided by 554 DOM/VRP to achieve that effect. */ 555 static tree 556 dummy_simplify (gimple stmt1 ATTRIBUTE_UNUSED, gimple stmt2 ATTRIBUTE_UNUSED) 557 { 558 return NULL_TREE; 559 } 560 561 /* Simplify the control statement at the end of the block E->dest. 562 563 To avoid allocating memory unnecessarily, a scratch GIMPLE_COND 564 is available to use/clobber in DUMMY_COND. 565 566 Use SIMPLIFY (a pointer to a callback function) to further simplify 567 a condition using pass specific information. 568 569 Return the simplified condition or NULL if simplification could 570 not be performed. */ 571 572 static tree 573 simplify_control_stmt_condition (edge e, 574 gimple stmt, 575 gcond *dummy_cond, 576 tree (*simplify) (gimple, gimple), 577 bool handle_dominating_asserts, 578 bool backedge_seen) 579 { 580 tree cond, cached_lhs; 581 enum gimple_code code = gimple_code (stmt); 582 583 /* For comparisons, we have to update both operands, then try 584 to simplify the comparison. */ 585 if (code == GIMPLE_COND) 586 { 587 tree op0, op1; 588 enum tree_code cond_code; 589 590 op0 = gimple_cond_lhs (stmt); 591 op1 = gimple_cond_rhs (stmt); 592 cond_code = gimple_cond_code (stmt); 593 594 /* Get the current value of both operands. */ 595 if (TREE_CODE (op0) == SSA_NAME) 596 { 597 for (int i = 0; i < (backedge_seen ? 1 : 2); i++) 598 { 599 if (TREE_CODE (op0) == SSA_NAME 600 && SSA_NAME_VALUE (op0)) 601 op0 = SSA_NAME_VALUE (op0); 602 else 603 break; 604 } 605 } 606 607 if (TREE_CODE (op1) == SSA_NAME) 608 { 609 for (int i = 0; i < (backedge_seen ? 1 : 2); i++) 610 { 611 if (TREE_CODE (op1) == SSA_NAME 612 && SSA_NAME_VALUE (op1)) 613 op1 = SSA_NAME_VALUE (op1); 614 else 615 break; 616 } 617 } 618 619 if (handle_dominating_asserts) 620 { 621 /* Now see if the operand was consumed by an ASSERT_EXPR 622 which dominates E->src. If so, we want to replace the 623 operand with the LHS of the ASSERT_EXPR. */ 624 if (TREE_CODE (op0) == SSA_NAME) 625 op0 = lhs_of_dominating_assert (op0, e->src, stmt); 626 627 if (TREE_CODE (op1) == SSA_NAME) 628 op1 = lhs_of_dominating_assert (op1, e->src, stmt); 629 } 630 631 /* We may need to canonicalize the comparison. For 632 example, op0 might be a constant while op1 is an 633 SSA_NAME. Failure to canonicalize will cause us to 634 miss threading opportunities. */ 635 if (tree_swap_operands_p (op0, op1, false)) 636 { 637 tree tmp; 638 cond_code = swap_tree_comparison (cond_code); 639 tmp = op0; 640 op0 = op1; 641 op1 = tmp; 642 } 643 644 /* Stuff the operator and operands into our dummy conditional 645 expression. */ 646 gimple_cond_set_code (dummy_cond, cond_code); 647 gimple_cond_set_lhs (dummy_cond, op0); 648 gimple_cond_set_rhs (dummy_cond, op1); 649 650 /* We absolutely do not care about any type conversions 651 we only care about a zero/nonzero value. */ 652 fold_defer_overflow_warnings (); 653 654 cached_lhs = fold_binary (cond_code, boolean_type_node, op0, op1); 655 if (cached_lhs) 656 while (CONVERT_EXPR_P (cached_lhs)) 657 cached_lhs = TREE_OPERAND (cached_lhs, 0); 658 659 fold_undefer_overflow_warnings ((cached_lhs 660 && is_gimple_min_invariant (cached_lhs)), 661 stmt, WARN_STRICT_OVERFLOW_CONDITIONAL); 662 663 /* If we have not simplified the condition down to an invariant, 664 then use the pass specific callback to simplify the condition. */ 665 if (!cached_lhs 666 || !is_gimple_min_invariant (cached_lhs)) 667 cached_lhs = (*simplify) (dummy_cond, stmt); 668 669 return cached_lhs; 670 } 671 672 if (code == GIMPLE_SWITCH) 673 cond = gimple_switch_index (as_a <gswitch *> (stmt)); 674 else if (code == GIMPLE_GOTO) 675 cond = gimple_goto_dest (stmt); 676 else 677 gcc_unreachable (); 678 679 /* We can have conditionals which just test the state of a variable 680 rather than use a relational operator. These are simpler to handle. */ 681 if (TREE_CODE (cond) == SSA_NAME) 682 { 683 tree original_lhs = cond; 684 cached_lhs = cond; 685 686 /* Get the variable's current value from the equivalence chains. 687 688 It is possible to get loops in the SSA_NAME_VALUE chains 689 (consider threading the backedge of a loop where we have 690 a loop invariant SSA_NAME used in the condition. */ 691 if (cached_lhs) 692 { 693 for (int i = 0; i < (backedge_seen ? 1 : 2); i++) 694 { 695 if (TREE_CODE (cached_lhs) == SSA_NAME 696 && SSA_NAME_VALUE (cached_lhs)) 697 cached_lhs = SSA_NAME_VALUE (cached_lhs); 698 else 699 break; 700 } 701 } 702 703 /* If we're dominated by a suitable ASSERT_EXPR, then 704 update CACHED_LHS appropriately. */ 705 if (handle_dominating_asserts && TREE_CODE (cached_lhs) == SSA_NAME) 706 cached_lhs = lhs_of_dominating_assert (cached_lhs, e->src, stmt); 707 708 /* If we haven't simplified to an invariant yet, then use the 709 pass specific callback to try and simplify it further. */ 710 if (cached_lhs && ! is_gimple_min_invariant (cached_lhs)) 711 cached_lhs = (*simplify) (stmt, stmt); 712 713 /* We couldn't find an invariant. But, callers of this 714 function may be able to do something useful with the 715 unmodified destination. */ 716 if (!cached_lhs) 717 cached_lhs = original_lhs; 718 } 719 else 720 cached_lhs = NULL; 721 722 return cached_lhs; 723 } 724 725 /* Copy debug stmts from DEST's chain of single predecessors up to 726 SRC, so that we don't lose the bindings as PHI nodes are introduced 727 when DEST gains new predecessors. */ 728 void 729 propagate_threaded_block_debug_into (basic_block dest, basic_block src) 730 { 731 if (!MAY_HAVE_DEBUG_STMTS) 732 return; 733 734 if (!single_pred_p (dest)) 735 return; 736 737 gcc_checking_assert (dest != src); 738 739 gimple_stmt_iterator gsi = gsi_after_labels (dest); 740 int i = 0; 741 const int alloc_count = 16; // ?? Should this be a PARAM? 742 743 /* Estimate the number of debug vars overridden in the beginning of 744 DEST, to tell how many we're going to need to begin with. */ 745 for (gimple_stmt_iterator si = gsi; 746 i * 4 <= alloc_count * 3 && !gsi_end_p (si); gsi_next (&si)) 747 { 748 gimple stmt = gsi_stmt (si); 749 if (!is_gimple_debug (stmt)) 750 break; 751 i++; 752 } 753 754 auto_vec<tree, alloc_count> fewvars; 755 hash_set<tree> *vars = NULL; 756 757 /* If we're already starting with 3/4 of alloc_count, go for a 758 hash_set, otherwise start with an unordered stack-allocated 759 VEC. */ 760 if (i * 4 > alloc_count * 3) 761 vars = new hash_set<tree>; 762 763 /* Now go through the initial debug stmts in DEST again, this time 764 actually inserting in VARS or FEWVARS. Don't bother checking for 765 duplicates in FEWVARS. */ 766 for (gimple_stmt_iterator si = gsi; !gsi_end_p (si); gsi_next (&si)) 767 { 768 gimple stmt = gsi_stmt (si); 769 if (!is_gimple_debug (stmt)) 770 break; 771 772 tree var; 773 774 if (gimple_debug_bind_p (stmt)) 775 var = gimple_debug_bind_get_var (stmt); 776 else if (gimple_debug_source_bind_p (stmt)) 777 var = gimple_debug_source_bind_get_var (stmt); 778 else 779 gcc_unreachable (); 780 781 if (vars) 782 vars->add (var); 783 else 784 fewvars.quick_push (var); 785 } 786 787 basic_block bb = dest; 788 789 do 790 { 791 bb = single_pred (bb); 792 for (gimple_stmt_iterator si = gsi_last_bb (bb); 793 !gsi_end_p (si); gsi_prev (&si)) 794 { 795 gimple stmt = gsi_stmt (si); 796 if (!is_gimple_debug (stmt)) 797 continue; 798 799 tree var; 800 801 if (gimple_debug_bind_p (stmt)) 802 var = gimple_debug_bind_get_var (stmt); 803 else if (gimple_debug_source_bind_p (stmt)) 804 var = gimple_debug_source_bind_get_var (stmt); 805 else 806 gcc_unreachable (); 807 808 /* Discard debug bind overlaps. ??? Unlike stmts from src, 809 copied into a new block that will precede BB, debug bind 810 stmts in bypassed BBs may actually be discarded if 811 they're overwritten by subsequent debug bind stmts, which 812 might be a problem once we introduce stmt frontier notes 813 or somesuch. Adding `&& bb == src' to the condition 814 below will preserve all potentially relevant debug 815 notes. */ 816 if (vars && vars->add (var)) 817 continue; 818 else if (!vars) 819 { 820 int i = fewvars.length (); 821 while (i--) 822 if (fewvars[i] == var) 823 break; 824 if (i >= 0) 825 continue; 826 827 if (fewvars.length () < (unsigned) alloc_count) 828 fewvars.quick_push (var); 829 else 830 { 831 vars = new hash_set<tree>; 832 for (i = 0; i < alloc_count; i++) 833 vars->add (fewvars[i]); 834 fewvars.release (); 835 vars->add (var); 836 } 837 } 838 839 stmt = gimple_copy (stmt); 840 /* ??? Should we drop the location of the copy to denote 841 they're artificial bindings? */ 842 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT); 843 } 844 } 845 while (bb != src && single_pred_p (bb)); 846 847 if (vars) 848 delete vars; 849 else if (fewvars.exists ()) 850 fewvars.release (); 851 } 852 853 /* See if TAKEN_EDGE->dest is a threadable block with no side effecs (ie, it 854 need not be duplicated as part of the CFG/SSA updating process). 855 856 If it is threadable, add it to PATH and VISITED and recurse, ultimately 857 returning TRUE from the toplevel call. Otherwise do nothing and 858 return false. 859 860 DUMMY_COND, HANDLE_DOMINATING_ASSERTS and SIMPLIFY are used to 861 try and simplify the condition at the end of TAKEN_EDGE->dest. */ 862 static bool 863 thread_around_empty_blocks (edge taken_edge, 864 gcond *dummy_cond, 865 bool handle_dominating_asserts, 866 tree (*simplify) (gimple, gimple), 867 bitmap visited, 868 vec<jump_thread_edge *> *path, 869 bool *backedge_seen_p) 870 { 871 basic_block bb = taken_edge->dest; 872 gimple_stmt_iterator gsi; 873 gimple stmt; 874 tree cond; 875 876 /* The key property of these blocks is that they need not be duplicated 877 when threading. Thus they can not have visible side effects such 878 as PHI nodes. */ 879 if (!gsi_end_p (gsi_start_phis (bb))) 880 return false; 881 882 /* Skip over DEBUG statements at the start of the block. */ 883 gsi = gsi_start_nondebug_bb (bb); 884 885 /* If the block has no statements, but does have a single successor, then 886 it's just a forwarding block and we can thread through it trivially. 887 888 However, note that just threading through empty blocks with single 889 successors is not inherently profitable. For the jump thread to 890 be profitable, we must avoid a runtime conditional. 891 892 By taking the return value from the recursive call, we get the 893 desired effect of returning TRUE when we found a profitable jump 894 threading opportunity and FALSE otherwise. 895 896 This is particularly important when this routine is called after 897 processing a joiner block. Returning TRUE too aggressively in 898 that case results in pointless duplication of the joiner block. */ 899 if (gsi_end_p (gsi)) 900 { 901 if (single_succ_p (bb)) 902 { 903 taken_edge = single_succ_edge (bb); 904 if (!bitmap_bit_p (visited, taken_edge->dest->index)) 905 { 906 jump_thread_edge *x 907 = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK); 908 path->safe_push (x); 909 bitmap_set_bit (visited, taken_edge->dest->index); 910 *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0); 911 if (*backedge_seen_p) 912 simplify = dummy_simplify; 913 return thread_around_empty_blocks (taken_edge, 914 dummy_cond, 915 handle_dominating_asserts, 916 simplify, 917 visited, 918 path, 919 backedge_seen_p); 920 } 921 } 922 923 /* We have a block with no statements, but multiple successors? */ 924 return false; 925 } 926 927 /* The only real statements this block can have are a control 928 flow altering statement. Anything else stops the thread. */ 929 stmt = gsi_stmt (gsi); 930 if (gimple_code (stmt) != GIMPLE_COND 931 && gimple_code (stmt) != GIMPLE_GOTO 932 && gimple_code (stmt) != GIMPLE_SWITCH) 933 return false; 934 935 /* If we have traversed a backedge, then we do not want to look 936 at certain expressions in the table that can not be relied upon. 937 Luckily the only code that looked at those expressions is the 938 SIMPLIFY callback, which we replace if we can no longer use it. */ 939 if (*backedge_seen_p) 940 simplify = dummy_simplify; 941 942 /* Extract and simplify the condition. */ 943 cond = simplify_control_stmt_condition (taken_edge, stmt, dummy_cond, 944 simplify, handle_dominating_asserts, 945 *backedge_seen_p); 946 947 /* If the condition can be statically computed and we have not already 948 visited the destination edge, then add the taken edge to our thread 949 path. */ 950 if (cond && is_gimple_min_invariant (cond)) 951 { 952 taken_edge = find_taken_edge (bb, cond); 953 954 if (bitmap_bit_p (visited, taken_edge->dest->index)) 955 return false; 956 bitmap_set_bit (visited, taken_edge->dest->index); 957 958 jump_thread_edge *x 959 = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK); 960 path->safe_push (x); 961 *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0); 962 if (*backedge_seen_p) 963 simplify = dummy_simplify; 964 965 thread_around_empty_blocks (taken_edge, 966 dummy_cond, 967 handle_dominating_asserts, 968 simplify, 969 visited, 970 path, 971 backedge_seen_p); 972 return true; 973 } 974 975 return false; 976 } 977 978 /* Return true if the CFG contains at least one path from START_BB to END_BB. 979 When a path is found, record in PATH the blocks from END_BB to START_BB. 980 VISITED_BBS is used to make sure we don't fall into an infinite loop. Bound 981 the recursion to basic blocks belonging to LOOP. */ 982 983 static bool 984 fsm_find_thread_path (basic_block start_bb, basic_block end_bb, 985 vec<basic_block, va_gc> *&path, 986 hash_set<basic_block> *visited_bbs, loop_p loop) 987 { 988 if (loop != start_bb->loop_father) 989 return false; 990 991 if (start_bb == end_bb) 992 { 993 vec_safe_push (path, start_bb); 994 return true; 995 } 996 997 if (!visited_bbs->add (start_bb)) 998 { 999 edge e; 1000 edge_iterator ei; 1001 FOR_EACH_EDGE (e, ei, start_bb->succs) 1002 if (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, loop)) 1003 { 1004 vec_safe_push (path, start_bb); 1005 return true; 1006 } 1007 } 1008 1009 return false; 1010 } 1011 1012 static int max_threaded_paths; 1013 1014 /* We trace the value of the variable EXPR back through any phi nodes looking 1015 for places where it gets a constant value and save the path. Stop after 1016 having recorded MAX_PATHS jump threading paths. */ 1017 1018 static void 1019 fsm_find_control_statement_thread_paths (tree expr, 1020 hash_set<basic_block> *visited_bbs, 1021 vec<basic_block, va_gc> *&path, 1022 bool seen_loop_phi) 1023 { 1024 tree var = SSA_NAME_VAR (expr); 1025 gimple def_stmt = SSA_NAME_DEF_STMT (expr); 1026 basic_block var_bb = gimple_bb (def_stmt); 1027 1028 if (var == NULL || var_bb == NULL) 1029 return; 1030 1031 /* For the moment we assume that an SSA chain only contains phi nodes, and 1032 eventually one of the phi arguments will be an integer constant. In the 1033 future, this could be extended to also handle simple assignments of 1034 arithmetic operations. */ 1035 if (gimple_code (def_stmt) != GIMPLE_PHI) 1036 return; 1037 1038 /* Avoid infinite recursion. */ 1039 if (visited_bbs->add (var_bb)) 1040 return; 1041 1042 gphi *phi = as_a <gphi *> (def_stmt); 1043 int next_path_length = 0; 1044 basic_block last_bb_in_path = path->last (); 1045 1046 if (loop_containing_stmt (phi)->header == gimple_bb (phi)) 1047 { 1048 /* Do not walk through more than one loop PHI node. */ 1049 if (seen_loop_phi) 1050 return; 1051 seen_loop_phi = true; 1052 } 1053 1054 /* Following the chain of SSA_NAME definitions, we jumped from a definition in 1055 LAST_BB_IN_PATH to a definition in VAR_BB. When these basic blocks are 1056 different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB. */ 1057 if (var_bb != last_bb_in_path) 1058 { 1059 edge e; 1060 int e_count = 0; 1061 edge_iterator ei; 1062 vec<basic_block, va_gc> *next_path; 1063 vec_alloc (next_path, n_basic_blocks_for_fn (cfun)); 1064 1065 FOR_EACH_EDGE (e, ei, last_bb_in_path->preds) 1066 { 1067 hash_set<basic_block> *visited_bbs = new hash_set<basic_block>; 1068 1069 if (fsm_find_thread_path (var_bb, e->src, next_path, visited_bbs, 1070 e->src->loop_father)) 1071 ++e_count; 1072 1073 delete visited_bbs; 1074 1075 /* If there is more than one path, stop. */ 1076 if (e_count > 1) 1077 { 1078 vec_free (next_path); 1079 return; 1080 } 1081 } 1082 1083 /* Stop if we have not found a path: this could occur when the recursion 1084 is stopped by one of the bounds. */ 1085 if (e_count == 0) 1086 { 1087 vec_free (next_path); 1088 return; 1089 } 1090 1091 /* Append all the nodes from NEXT_PATH to PATH. */ 1092 vec_safe_splice (path, next_path); 1093 next_path_length = next_path->length (); 1094 vec_free (next_path); 1095 } 1096 1097 gcc_assert (path->last () == var_bb); 1098 1099 /* Iterate over the arguments of PHI. */ 1100 unsigned int i; 1101 for (i = 0; i < gimple_phi_num_args (phi); i++) 1102 { 1103 tree arg = gimple_phi_arg_def (phi, i); 1104 basic_block bbi = gimple_phi_arg_edge (phi, i)->src; 1105 1106 /* Skip edges pointing outside the current loop. */ 1107 if (!arg || var_bb->loop_father != bbi->loop_father) 1108 continue; 1109 1110 if (TREE_CODE (arg) == SSA_NAME) 1111 { 1112 vec_safe_push (path, bbi); 1113 /* Recursively follow SSA_NAMEs looking for a constant definition. */ 1114 fsm_find_control_statement_thread_paths (arg, visited_bbs, path, 1115 seen_loop_phi); 1116 1117 path->pop (); 1118 continue; 1119 } 1120 1121 if (TREE_CODE (arg) != INTEGER_CST) 1122 continue; 1123 1124 int path_length = path->length (); 1125 /* A path with less than 2 basic blocks should not be jump-threaded. */ 1126 if (path_length < 2) 1127 continue; 1128 1129 if (path_length > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH)) 1130 { 1131 if (dump_file && (dump_flags & TDF_DETAILS)) 1132 fprintf (dump_file, "FSM jump-thread path not considered: " 1133 "the number of basic blocks on the path " 1134 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n"); 1135 continue; 1136 } 1137 1138 if (max_threaded_paths <= 0) 1139 { 1140 if (dump_file && (dump_flags & TDF_DETAILS)) 1141 fprintf (dump_file, "FSM jump-thread path not considered: " 1142 "the number of previously recorded FSM paths to thread " 1143 "exceeds PARAM_MAX_FSM_THREAD_PATHS.\n"); 1144 continue; 1145 } 1146 1147 /* Add BBI to the path. */ 1148 vec_safe_push (path, bbi); 1149 ++path_length; 1150 1151 int n_insns = 0; 1152 gimple_stmt_iterator gsi; 1153 int j; 1154 loop_p loop = (*path)[0]->loop_father; 1155 bool path_crosses_loops = false; 1156 1157 /* Count the number of instructions on the path: as these instructions 1158 will have to be duplicated, we will not record the path if there are 1159 too many instructions on the path. Also check that all the blocks in 1160 the path belong to a single loop. */ 1161 for (j = 1; j < path_length - 1; j++) 1162 { 1163 basic_block bb = (*path)[j]; 1164 1165 if (bb->loop_father != loop) 1166 { 1167 path_crosses_loops = true; 1168 break; 1169 } 1170 1171 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1172 { 1173 gimple stmt = gsi_stmt (gsi); 1174 /* Do not count empty statements and labels. */ 1175 if (gimple_code (stmt) != GIMPLE_NOP 1176 && gimple_code (stmt) != GIMPLE_LABEL 1177 && !is_gimple_debug (stmt)) 1178 ++n_insns; 1179 } 1180 } 1181 1182 if (path_crosses_loops) 1183 { 1184 if (dump_file && (dump_flags & TDF_DETAILS)) 1185 fprintf (dump_file, "FSM jump-thread path not considered: " 1186 "the path crosses loops.\n"); 1187 path->pop (); 1188 continue; 1189 } 1190 1191 if (n_insns >= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS)) 1192 { 1193 if (dump_file && (dump_flags & TDF_DETAILS)) 1194 fprintf (dump_file, "FSM jump-thread path not considered: " 1195 "the number of instructions on the path " 1196 "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n"); 1197 path->pop (); 1198 continue; 1199 } 1200 1201 vec<jump_thread_edge *> *jump_thread_path 1202 = new vec<jump_thread_edge *> (); 1203 1204 /* Record the edges between the blocks in PATH. */ 1205 for (j = 0; j < path_length - 1; j++) 1206 { 1207 edge e = find_edge ((*path)[path_length - j - 1], 1208 (*path)[path_length - j - 2]); 1209 gcc_assert (e); 1210 jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD); 1211 jump_thread_path->safe_push (x); 1212 } 1213 1214 /* Add the edge taken when the control variable has value ARG. */ 1215 edge taken_edge = find_taken_edge ((*path)[0], arg); 1216 jump_thread_edge *x 1217 = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK); 1218 jump_thread_path->safe_push (x); 1219 1220 register_jump_thread (jump_thread_path); 1221 --max_threaded_paths; 1222 1223 /* Remove BBI from the path. */ 1224 path->pop (); 1225 } 1226 1227 /* Remove all the nodes that we added from NEXT_PATH. */ 1228 if (next_path_length) 1229 vec_safe_truncate (path, (path->length () - next_path_length)); 1230 } 1231 1232 /* We are exiting E->src, see if E->dest ends with a conditional 1233 jump which has a known value when reached via E. 1234 1235 E->dest can have arbitrary side effects which, if threading is 1236 successful, will be maintained. 1237 1238 Special care is necessary if E is a back edge in the CFG as we 1239 may have already recorded equivalences for E->dest into our 1240 various tables, including the result of the conditional at 1241 the end of E->dest. Threading opportunities are severely 1242 limited in that case to avoid short-circuiting the loop 1243 incorrectly. 1244 1245 DUMMY_COND is a shared cond_expr used by condition simplification as scratch, 1246 to avoid allocating memory. 1247 1248 HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of 1249 the simplified condition with left-hand sides of ASSERT_EXPRs they are 1250 used in. 1251 1252 STACK is used to undo temporary equivalences created during the walk of 1253 E->dest. 1254 1255 SIMPLIFY is a pass-specific function used to simplify statements. 1256 1257 Our caller is responsible for restoring the state of the expression 1258 and const_and_copies stacks. 1259 1260 Positive return value is success. Zero return value is failure, but 1261 the block can still be duplicated as a joiner in a jump thread path, 1262 negative indicates the block should not be duplicated and thus is not 1263 suitable for a joiner in a jump threading path. */ 1264 1265 static int 1266 thread_through_normal_block (edge e, 1267 gcond *dummy_cond, 1268 bool handle_dominating_asserts, 1269 vec<tree> *stack, 1270 tree (*simplify) (gimple, gimple), 1271 vec<jump_thread_edge *> *path, 1272 bitmap visited, 1273 bool *backedge_seen_p) 1274 { 1275 /* If we have traversed a backedge, then we do not want to look 1276 at certain expressions in the table that can not be relied upon. 1277 Luckily the only code that looked at those expressions is the 1278 SIMPLIFY callback, which we replace if we can no longer use it. */ 1279 if (*backedge_seen_p) 1280 simplify = dummy_simplify; 1281 1282 /* PHIs create temporary equivalences. 1283 Note that if we found a PHI that made the block non-threadable, then 1284 we need to bubble that up to our caller in the same manner we do 1285 when we prematurely stop processing statements below. */ 1286 if (!record_temporary_equivalences_from_phis (e, stack)) 1287 return -1; 1288 1289 /* Now walk each statement recording any context sensitive 1290 temporary equivalences we can detect. */ 1291 gimple stmt 1292 = record_temporary_equivalences_from_stmts_at_dest (e, stack, simplify, 1293 *backedge_seen_p); 1294 1295 /* There's two reasons STMT might be null, and distinguishing 1296 between them is important. 1297 1298 First the block may not have had any statements. For example, it 1299 might have some PHIs and unconditionally transfer control elsewhere. 1300 Such blocks are suitable for jump threading, particularly as a 1301 joiner block. 1302 1303 The second reason would be if we did not process all the statements 1304 in the block (because there were too many to make duplicating the 1305 block profitable. If we did not look at all the statements, then 1306 we may not have invalidated everything needing invalidation. Thus 1307 we must signal to our caller that this block is not suitable for 1308 use as a joiner in a threading path. */ 1309 if (!stmt) 1310 { 1311 /* First case. The statement simply doesn't have any instructions, but 1312 does have PHIs. */ 1313 if (gsi_end_p (gsi_start_nondebug_bb (e->dest)) 1314 && !gsi_end_p (gsi_start_phis (e->dest))) 1315 return 0; 1316 1317 /* Second case. */ 1318 return -1; 1319 } 1320 1321 /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm 1322 will be taken. */ 1323 if (gimple_code (stmt) == GIMPLE_COND 1324 || gimple_code (stmt) == GIMPLE_GOTO 1325 || gimple_code (stmt) == GIMPLE_SWITCH) 1326 { 1327 tree cond; 1328 1329 /* Extract and simplify the condition. */ 1330 cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify, 1331 handle_dominating_asserts, 1332 *backedge_seen_p); 1333 1334 if (!cond) 1335 return 0; 1336 1337 if (is_gimple_min_invariant (cond)) 1338 { 1339 edge taken_edge = find_taken_edge (e->dest, cond); 1340 basic_block dest = (taken_edge ? taken_edge->dest : NULL); 1341 1342 /* DEST could be NULL for a computed jump to an absolute 1343 address. */ 1344 if (dest == NULL 1345 || dest == e->dest 1346 || bitmap_bit_p (visited, dest->index)) 1347 return 0; 1348 1349 /* Only push the EDGE_START_JUMP_THREAD marker if this is 1350 first edge on the path. */ 1351 if (path->length () == 0) 1352 { 1353 jump_thread_edge *x 1354 = new jump_thread_edge (e, EDGE_START_JUMP_THREAD); 1355 path->safe_push (x); 1356 *backedge_seen_p |= ((e->flags & EDGE_DFS_BACK) != 0); 1357 } 1358 1359 jump_thread_edge *x 1360 = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_BLOCK); 1361 path->safe_push (x); 1362 *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0); 1363 if (*backedge_seen_p) 1364 simplify = dummy_simplify; 1365 1366 /* See if we can thread through DEST as well, this helps capture 1367 secondary effects of threading without having to re-run DOM or 1368 VRP. 1369 1370 We don't want to thread back to a block we have already 1371 visited. This may be overly conservative. */ 1372 bitmap_set_bit (visited, dest->index); 1373 bitmap_set_bit (visited, e->dest->index); 1374 thread_around_empty_blocks (taken_edge, 1375 dummy_cond, 1376 handle_dominating_asserts, 1377 simplify, 1378 visited, 1379 path, 1380 backedge_seen_p); 1381 return 1; 1382 } 1383 1384 if (!flag_expensive_optimizations 1385 || optimize_function_for_size_p (cfun) 1386 || TREE_CODE (cond) != SSA_NAME 1387 || e->dest->loop_father != e->src->loop_father 1388 || loop_depth (e->dest->loop_father) == 0) 1389 return 0; 1390 1391 /* When COND cannot be simplified, try to find paths from a control 1392 statement back through the PHI nodes which would affect that control 1393 statement. */ 1394 vec<basic_block, va_gc> *bb_path; 1395 vec_alloc (bb_path, n_basic_blocks_for_fn (cfun)); 1396 vec_safe_push (bb_path, e->dest); 1397 hash_set<basic_block> *visited_bbs = new hash_set<basic_block>; 1398 1399 max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS); 1400 fsm_find_control_statement_thread_paths (cond, visited_bbs, bb_path, 1401 false); 1402 1403 delete visited_bbs; 1404 vec_free (bb_path); 1405 } 1406 return 0; 1407 } 1408 1409 /* We are exiting E->src, see if E->dest ends with a conditional 1410 jump which has a known value when reached via E. 1411 1412 Special care is necessary if E is a back edge in the CFG as we 1413 may have already recorded equivalences for E->dest into our 1414 various tables, including the result of the conditional at 1415 the end of E->dest. Threading opportunities are severely 1416 limited in that case to avoid short-circuiting the loop 1417 incorrectly. 1418 1419 Note it is quite common for the first block inside a loop to 1420 end with a conditional which is either always true or always 1421 false when reached via the loop backedge. Thus we do not want 1422 to blindly disable threading across a loop backedge. 1423 1424 DUMMY_COND is a shared cond_expr used by condition simplification as scratch, 1425 to avoid allocating memory. 1426 1427 HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of 1428 the simplified condition with left-hand sides of ASSERT_EXPRs they are 1429 used in. 1430 1431 STACK is used to undo temporary equivalences created during the walk of 1432 E->dest. 1433 1434 SIMPLIFY is a pass-specific function used to simplify statements. */ 1435 1436 void 1437 thread_across_edge (gcond *dummy_cond, 1438 edge e, 1439 bool handle_dominating_asserts, 1440 vec<tree> *stack, 1441 tree (*simplify) (gimple, gimple)) 1442 { 1443 bitmap visited = BITMAP_ALLOC (NULL); 1444 bool backedge_seen; 1445 1446 stmt_count = 0; 1447 1448 vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> (); 1449 bitmap_clear (visited); 1450 bitmap_set_bit (visited, e->src->index); 1451 bitmap_set_bit (visited, e->dest->index); 1452 backedge_seen = ((e->flags & EDGE_DFS_BACK) != 0); 1453 if (backedge_seen) 1454 simplify = dummy_simplify; 1455 1456 int threaded = thread_through_normal_block (e, dummy_cond, 1457 handle_dominating_asserts, 1458 stack, simplify, path, 1459 visited, &backedge_seen); 1460 if (threaded > 0) 1461 { 1462 propagate_threaded_block_debug_into (path->last ()->e->dest, 1463 e->dest); 1464 remove_temporary_equivalences (stack); 1465 BITMAP_FREE (visited); 1466 register_jump_thread (path); 1467 return; 1468 } 1469 else 1470 { 1471 /* Negative and zero return values indicate no threading was possible, 1472 thus there should be no edges on the thread path and no need to walk 1473 through the vector entries. */ 1474 gcc_assert (path->length () == 0); 1475 path->release (); 1476 delete path; 1477 1478 /* A negative status indicates the target block was deemed too big to 1479 duplicate. Just quit now rather than trying to use the block as 1480 a joiner in a jump threading path. 1481 1482 This prevents unnecessary code growth, but more importantly if we 1483 do not look at all the statements in the block, then we may have 1484 missed some invalidations if we had traversed a backedge! */ 1485 if (threaded < 0) 1486 { 1487 BITMAP_FREE (visited); 1488 remove_temporary_equivalences (stack); 1489 return; 1490 } 1491 } 1492 1493 /* We were unable to determine what out edge from E->dest is taken. However, 1494 we might still be able to thread through successors of E->dest. This 1495 often occurs when E->dest is a joiner block which then fans back out 1496 based on redundant tests. 1497 1498 If so, we'll copy E->dest and redirect the appropriate predecessor to 1499 the copy. Within the copy of E->dest, we'll thread one or more edges 1500 to points deeper in the CFG. 1501 1502 This is a stopgap until we have a more structured approach to path 1503 isolation. */ 1504 { 1505 edge taken_edge; 1506 edge_iterator ei; 1507 bool found; 1508 1509 /* If E->dest has abnormal outgoing edges, then there's no guarantee 1510 we can safely redirect any of the edges. Just punt those cases. */ 1511 FOR_EACH_EDGE (taken_edge, ei, e->dest->succs) 1512 if (taken_edge->flags & EDGE_ABNORMAL) 1513 { 1514 remove_temporary_equivalences (stack); 1515 BITMAP_FREE (visited); 1516 return; 1517 } 1518 1519 /* Look at each successor of E->dest to see if we can thread through it. */ 1520 FOR_EACH_EDGE (taken_edge, ei, e->dest->succs) 1521 { 1522 /* Push a fresh marker so we can unwind the equivalences created 1523 for each of E->dest's successors. */ 1524 stack->safe_push (NULL_TREE); 1525 1526 /* Avoid threading to any block we have already visited. */ 1527 bitmap_clear (visited); 1528 bitmap_set_bit (visited, e->src->index); 1529 bitmap_set_bit (visited, e->dest->index); 1530 bitmap_set_bit (visited, taken_edge->dest->index); 1531 vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> (); 1532 1533 /* Record whether or not we were able to thread through a successor 1534 of E->dest. */ 1535 jump_thread_edge *x = new jump_thread_edge (e, EDGE_START_JUMP_THREAD); 1536 path->safe_push (x); 1537 1538 x = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_JOINER_BLOCK); 1539 path->safe_push (x); 1540 found = false; 1541 backedge_seen = ((e->flags & EDGE_DFS_BACK) != 0); 1542 backedge_seen |= ((taken_edge->flags & EDGE_DFS_BACK) != 0); 1543 if (backedge_seen) 1544 simplify = dummy_simplify; 1545 found = thread_around_empty_blocks (taken_edge, 1546 dummy_cond, 1547 handle_dominating_asserts, 1548 simplify, 1549 visited, 1550 path, 1551 &backedge_seen); 1552 1553 if (backedge_seen) 1554 simplify = dummy_simplify; 1555 1556 if (!found) 1557 found = thread_through_normal_block (path->last ()->e, dummy_cond, 1558 handle_dominating_asserts, 1559 stack, simplify, path, visited, 1560 &backedge_seen) > 0; 1561 1562 /* If we were able to thread through a successor of E->dest, then 1563 record the jump threading opportunity. */ 1564 if (found) 1565 { 1566 propagate_threaded_block_debug_into (path->last ()->e->dest, 1567 taken_edge->dest); 1568 register_jump_thread (path); 1569 } 1570 else 1571 { 1572 delete_jump_thread_path (path); 1573 } 1574 1575 /* And unwind the equivalence table. */ 1576 remove_temporary_equivalences (stack); 1577 } 1578 BITMAP_FREE (visited); 1579 } 1580 1581 remove_temporary_equivalences (stack); 1582 } 1583