1 /* Tail merging for gimple. 2 Copyright (C) 2011-2018 Free Software Foundation, Inc. 3 Contributed by Tom de Vries (tom@codesourcery.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 /* Pass overview. 22 23 24 MOTIVATIONAL EXAMPLE 25 26 gimple representation of gcc/testsuite/gcc.dg/pr43864.c at 27 28 hprofStartupp (charD.1 * outputFileNameD.2600, charD.1 * ctxD.2601) 29 { 30 struct FILED.1638 * fpD.2605; 31 charD.1 fileNameD.2604[1000]; 32 intD.0 D.3915; 33 const charD.1 * restrict outputFileName.0D.3914; 34 35 # BLOCK 2 freq:10000 36 # PRED: ENTRY [100.0%] (fallthru,exec) 37 # PT = nonlocal { D.3926 } (restr) 38 outputFileName.0D.3914_3 39 = (const charD.1 * restrict) outputFileNameD.2600_2(D); 40 # .MEMD.3923_13 = VDEF <.MEMD.3923_12(D)> 41 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr) 42 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr) 43 sprintfD.759 (&fileNameD.2604, outputFileName.0D.3914_3); 44 # .MEMD.3923_14 = VDEF <.MEMD.3923_13> 45 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr) 46 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr) 47 D.3915_4 = accessD.2606 (&fileNameD.2604, 1); 48 if (D.3915_4 == 0) 49 goto <bb 3>; 50 else 51 goto <bb 4>; 52 # SUCC: 3 [10.0%] (true,exec) 4 [90.0%] (false,exec) 53 54 # BLOCK 3 freq:1000 55 # PRED: 2 [10.0%] (true,exec) 56 # .MEMD.3923_15 = VDEF <.MEMD.3923_14> 57 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr) 58 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr) 59 freeD.898 (ctxD.2601_5(D)); 60 goto <bb 7>; 61 # SUCC: 7 [100.0%] (fallthru,exec) 62 63 # BLOCK 4 freq:9000 64 # PRED: 2 [90.0%] (false,exec) 65 # .MEMD.3923_16 = VDEF <.MEMD.3923_14> 66 # PT = nonlocal escaped 67 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr) 68 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr) 69 fpD.2605_8 = fopenD.1805 (&fileNameD.2604[0], 0B); 70 if (fpD.2605_8 == 0B) 71 goto <bb 5>; 72 else 73 goto <bb 6>; 74 # SUCC: 5 [1.9%] (true,exec) 6 [98.1%] (false,exec) 75 76 # BLOCK 5 freq:173 77 # PRED: 4 [1.9%] (true,exec) 78 # .MEMD.3923_17 = VDEF <.MEMD.3923_16> 79 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr) 80 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr) 81 freeD.898 (ctxD.2601_5(D)); 82 goto <bb 7>; 83 # SUCC: 7 [100.0%] (fallthru,exec) 84 85 # BLOCK 6 freq:8827 86 # PRED: 4 [98.1%] (false,exec) 87 # .MEMD.3923_18 = VDEF <.MEMD.3923_16> 88 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr) 89 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr) 90 fooD.2599 (outputFileNameD.2600_2(D), fpD.2605_8); 91 # SUCC: 7 [100.0%] (fallthru,exec) 92 93 # BLOCK 7 freq:10000 94 # PRED: 3 [100.0%] (fallthru,exec) 5 [100.0%] (fallthru,exec) 95 6 [100.0%] (fallthru,exec) 96 # PT = nonlocal null 97 98 # ctxD.2601_1 = PHI <0B(3), 0B(5), ctxD.2601_5(D)(6)> 99 # .MEMD.3923_11 = PHI <.MEMD.3923_15(3), .MEMD.3923_17(5), 100 .MEMD.3923_18(6)> 101 # VUSE <.MEMD.3923_11> 102 return ctxD.2601_1; 103 # SUCC: EXIT [100.0%] 104 } 105 106 bb 3 and bb 5 can be merged. The blocks have different predecessors, but the 107 same successors, and the same operations. 108 109 110 CONTEXT 111 112 A technique called tail merging (or cross jumping) can fix the example 113 above. For a block, we look for common code at the end (the tail) of the 114 predecessor blocks, and insert jumps from one block to the other. 115 The example is a special case for tail merging, in that 2 whole blocks 116 can be merged, rather than just the end parts of it. 117 We currently only focus on whole block merging, so in that sense 118 calling this pass tail merge is a bit of a misnomer. 119 120 We distinguish 2 kinds of situations in which blocks can be merged: 121 - same operations, same predecessors. The successor edges coming from one 122 block are redirected to come from the other block. 123 - same operations, same successors. The predecessor edges entering one block 124 are redirected to enter the other block. Note that this operation might 125 involve introducing phi operations. 126 127 For efficient implementation, we would like to value numbers the blocks, and 128 have a comparison operator that tells us whether the blocks are equal. 129 Besides being runtime efficient, block value numbering should also abstract 130 from irrelevant differences in order of operations, much like normal value 131 numbering abstracts from irrelevant order of operations. 132 133 For the first situation (same_operations, same predecessors), normal value 134 numbering fits well. We can calculate a block value number based on the 135 value numbers of the defs and vdefs. 136 137 For the second situation (same operations, same successors), this approach 138 doesn't work so well. We can illustrate this using the example. The calls 139 to free use different vdefs: MEMD.3923_16 and MEMD.3923_14, and these will 140 remain different in value numbering, since they represent different memory 141 states. So the resulting vdefs of the frees will be different in value 142 numbering, so the block value numbers will be different. 143 144 The reason why we call the blocks equal is not because they define the same 145 values, but because uses in the blocks use (possibly different) defs in the 146 same way. To be able to detect this efficiently, we need to do some kind of 147 reverse value numbering, meaning number the uses rather than the defs, and 148 calculate a block value number based on the value number of the uses. 149 Ideally, a block comparison operator will also indicate which phis are needed 150 to merge the blocks. 151 152 For the moment, we don't do block value numbering, but we do insn-by-insn 153 matching, using scc value numbers to match operations with results, and 154 structural comparison otherwise, while ignoring vop mismatches. 155 156 157 IMPLEMENTATION 158 159 1. The pass first determines all groups of blocks with the same successor 160 blocks. 161 2. Within each group, it tries to determine clusters of equal basic blocks. 162 3. The clusters are applied. 163 4. The same successor groups are updated. 164 5. This process is repeated from 2 onwards, until no more changes. 165 166 167 LIMITATIONS/TODO 168 169 - block only 170 - handles only 'same operations, same successors'. 171 It handles same predecessors as a special subcase though. 172 - does not implement the reverse value numbering and block value numbering. 173 - improve memory allocation: use garbage collected memory, obstacks, 174 allocpools where appropriate. 175 - no insertion of gimple_reg phis, We only introduce vop-phis. 176 - handle blocks with gimple_reg phi_nodes. 177 178 179 PASS PLACEMENT 180 This 'pass' is not a stand-alone gimple pass, but runs as part of 181 pass_pre, in order to share the value numbering. 182 183 184 SWITCHES 185 186 - ftree-tail-merge. On at -O2. We may have to enable it only at -Os. */ 187 188 #include "config.h" 189 #include "system.h" 190 #include "coretypes.h" 191 #include "backend.h" 192 #include "tree.h" 193 #include "gimple.h" 194 #include "cfghooks.h" 195 #include "tree-pass.h" 196 #include "ssa.h" 197 #include "fold-const.h" 198 #include "trans-mem.h" 199 #include "cfganal.h" 200 #include "cfgcleanup.h" 201 #include "gimple-iterator.h" 202 #include "tree-cfg.h" 203 #include "tree-into-ssa.h" 204 #include "params.h" 205 #include "tree-ssa-sccvn.h" 206 #include "cfgloop.h" 207 #include "tree-eh.h" 208 #include "tree-cfgcleanup.h" 209 210 const int ignore_edge_flags = EDGE_DFS_BACK | EDGE_EXECUTABLE; 211 212 /* Describes a group of bbs with the same successors. The successor bbs are 213 cached in succs, and the successor edge flags are cached in succ_flags. 214 If a bb has the EDGE_TRUE/FALSE_VALUE flags swapped compared to succ_flags, 215 it's marked in inverse. 216 Additionally, the hash value for the struct is cached in hashval, and 217 in_worklist indicates whether it's currently part of worklist. */ 218 219 struct same_succ : pointer_hash <same_succ> 220 { 221 /* The bbs that have the same successor bbs. */ 222 bitmap bbs; 223 /* The successor bbs. */ 224 bitmap succs; 225 /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for 226 bb. */ 227 bitmap inverse; 228 /* The edge flags for each of the successor bbs. */ 229 vec<int> succ_flags; 230 /* Indicates whether the struct is currently in the worklist. */ 231 bool in_worklist; 232 /* The hash value of the struct. */ 233 hashval_t hashval; 234 235 /* hash_table support. */ 236 static inline hashval_t hash (const same_succ *); 237 static int equal (const same_succ *, const same_succ *); 238 static void remove (same_succ *); 239 }; 240 241 /* hash routine for hash_table support, returns hashval of E. */ 242 243 inline hashval_t 244 same_succ::hash (const same_succ *e) 245 { 246 return e->hashval; 247 } 248 249 /* A group of bbs where 1 bb from bbs can replace the other bbs. */ 250 251 struct bb_cluster 252 { 253 /* The bbs in the cluster. */ 254 bitmap bbs; 255 /* The preds of the bbs in the cluster. */ 256 bitmap preds; 257 /* Index in all_clusters vector. */ 258 int index; 259 /* The bb to replace the cluster with. */ 260 basic_block rep_bb; 261 }; 262 263 /* Per bb-info. */ 264 265 struct aux_bb_info 266 { 267 /* The number of non-debug statements in the bb. */ 268 int size; 269 /* The same_succ that this bb is a member of. */ 270 same_succ *bb_same_succ; 271 /* The cluster that this bb is a member of. */ 272 bb_cluster *cluster; 273 /* The vop state at the exit of a bb. This is shortlived data, used to 274 communicate data between update_block_by and update_vuses. */ 275 tree vop_at_exit; 276 /* The bb that either contains or is dominated by the dependencies of the 277 bb. */ 278 basic_block dep_bb; 279 }; 280 281 /* Macros to access the fields of struct aux_bb_info. */ 282 283 #define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size) 284 #define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ) 285 #define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster) 286 #define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit) 287 #define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb) 288 289 /* Returns true if the only effect a statement STMT has, is to define locally 290 used SSA_NAMEs. */ 291 292 static bool 293 stmt_local_def (gimple *stmt) 294 { 295 basic_block bb, def_bb; 296 imm_use_iterator iter; 297 use_operand_p use_p; 298 tree val; 299 def_operand_p def_p; 300 301 if (gimple_vdef (stmt) != NULL_TREE 302 || gimple_has_side_effects (stmt) 303 || gimple_could_trap_p_1 (stmt, false, false) 304 || gimple_vuse (stmt) != NULL_TREE) 305 return false; 306 307 def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF); 308 if (def_p == NULL) 309 return false; 310 311 val = DEF_FROM_PTR (def_p); 312 if (val == NULL_TREE || TREE_CODE (val) != SSA_NAME) 313 return false; 314 315 def_bb = gimple_bb (stmt); 316 317 FOR_EACH_IMM_USE_FAST (use_p, iter, val) 318 { 319 if (is_gimple_debug (USE_STMT (use_p))) 320 continue; 321 bb = gimple_bb (USE_STMT (use_p)); 322 if (bb == def_bb) 323 continue; 324 325 if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI 326 && EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src == def_bb) 327 continue; 328 329 return false; 330 } 331 332 return true; 333 } 334 335 /* Let GSI skip forwards over local defs. */ 336 337 static void 338 gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator *gsi) 339 { 340 gimple *stmt; 341 342 while (true) 343 { 344 if (gsi_end_p (*gsi)) 345 return; 346 stmt = gsi_stmt (*gsi); 347 if (!stmt_local_def (stmt)) 348 return; 349 gsi_next_nondebug (gsi); 350 } 351 } 352 353 /* VAL1 and VAL2 are either: 354 - uses in BB1 and BB2, or 355 - phi alternatives for BB1 and BB2. 356 Return true if the uses have the same gvn value. */ 357 358 static bool 359 gvn_uses_equal (tree val1, tree val2) 360 { 361 gcc_checking_assert (val1 != NULL_TREE && val2 != NULL_TREE); 362 363 if (val1 == val2) 364 return true; 365 366 if (vn_valueize (val1) != vn_valueize (val2)) 367 return false; 368 369 return ((TREE_CODE (val1) == SSA_NAME || CONSTANT_CLASS_P (val1)) 370 && (TREE_CODE (val2) == SSA_NAME || CONSTANT_CLASS_P (val2))); 371 } 372 373 /* Prints E to FILE. */ 374 375 static void 376 same_succ_print (FILE *file, const same_succ *e) 377 { 378 unsigned int i; 379 bitmap_print (file, e->bbs, "bbs:", "\n"); 380 bitmap_print (file, e->succs, "succs:", "\n"); 381 bitmap_print (file, e->inverse, "inverse:", "\n"); 382 fprintf (file, "flags:"); 383 for (i = 0; i < e->succ_flags.length (); ++i) 384 fprintf (file, " %x", e->succ_flags[i]); 385 fprintf (file, "\n"); 386 } 387 388 /* Prints same_succ VE to VFILE. */ 389 390 inline int 391 ssa_same_succ_print_traverse (same_succ **pe, FILE *file) 392 { 393 const same_succ *e = *pe; 394 same_succ_print (file, e); 395 return 1; 396 } 397 398 /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */ 399 400 static void 401 update_dep_bb (basic_block use_bb, tree val) 402 { 403 basic_block dep_bb; 404 405 /* Not a dep. */ 406 if (TREE_CODE (val) != SSA_NAME) 407 return; 408 409 /* Skip use of global def. */ 410 if (SSA_NAME_IS_DEFAULT_DEF (val)) 411 return; 412 413 /* Skip use of local def. */ 414 dep_bb = gimple_bb (SSA_NAME_DEF_STMT (val)); 415 if (dep_bb == use_bb) 416 return; 417 418 if (BB_DEP_BB (use_bb) == NULL 419 || dominated_by_p (CDI_DOMINATORS, dep_bb, BB_DEP_BB (use_bb))) 420 BB_DEP_BB (use_bb) = dep_bb; 421 } 422 423 /* Update BB_DEP_BB, given the dependencies in STMT. */ 424 425 static void 426 stmt_update_dep_bb (gimple *stmt) 427 { 428 ssa_op_iter iter; 429 use_operand_p use; 430 431 FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE) 432 update_dep_bb (gimple_bb (stmt), USE_FROM_PTR (use)); 433 } 434 435 /* Calculates hash value for same_succ VE. */ 436 437 static hashval_t 438 same_succ_hash (const same_succ *e) 439 { 440 inchash::hash hstate (bitmap_hash (e->succs)); 441 int flags; 442 unsigned int i; 443 unsigned int first = bitmap_first_set_bit (e->bbs); 444 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, first); 445 int size = 0; 446 gimple *stmt; 447 tree arg; 448 unsigned int s; 449 bitmap_iterator bs; 450 451 for (gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb); 452 !gsi_end_p (gsi); gsi_next_nondebug (&gsi)) 453 { 454 stmt = gsi_stmt (gsi); 455 stmt_update_dep_bb (stmt); 456 if (stmt_local_def (stmt)) 457 continue; 458 size++; 459 460 hstate.add_int (gimple_code (stmt)); 461 if (is_gimple_assign (stmt)) 462 hstate.add_int (gimple_assign_rhs_code (stmt)); 463 if (!is_gimple_call (stmt)) 464 continue; 465 if (gimple_call_internal_p (stmt)) 466 hstate.add_int (gimple_call_internal_fn (stmt)); 467 else 468 { 469 inchash::add_expr (gimple_call_fn (stmt), hstate); 470 if (gimple_call_chain (stmt)) 471 inchash::add_expr (gimple_call_chain (stmt), hstate); 472 } 473 for (i = 0; i < gimple_call_num_args (stmt); i++) 474 { 475 arg = gimple_call_arg (stmt, i); 476 arg = vn_valueize (arg); 477 inchash::add_expr (arg, hstate); 478 } 479 } 480 481 hstate.add_int (size); 482 BB_SIZE (bb) = size; 483 484 hstate.add_int (bb->loop_father->num); 485 486 for (i = 0; i < e->succ_flags.length (); ++i) 487 { 488 flags = e->succ_flags[i]; 489 flags = flags & ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); 490 hstate.add_int (flags); 491 } 492 493 EXECUTE_IF_SET_IN_BITMAP (e->succs, 0, s, bs) 494 { 495 int n = find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, s))->dest_idx; 496 for (gphi_iterator gsi = gsi_start_phis (BASIC_BLOCK_FOR_FN (cfun, s)); 497 !gsi_end_p (gsi); 498 gsi_next (&gsi)) 499 { 500 gphi *phi = gsi.phi (); 501 tree lhs = gimple_phi_result (phi); 502 tree val = gimple_phi_arg_def (phi, n); 503 504 if (virtual_operand_p (lhs)) 505 continue; 506 update_dep_bb (bb, val); 507 } 508 } 509 510 return hstate.end (); 511 } 512 513 /* Returns true if E1 and E2 have 2 successors, and if the successor flags 514 are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for 515 the other edge flags. */ 516 517 static bool 518 inverse_flags (const same_succ *e1, const same_succ *e2) 519 { 520 int f1a, f1b, f2a, f2b; 521 int mask = ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); 522 523 if (e1->succ_flags.length () != 2) 524 return false; 525 526 f1a = e1->succ_flags[0]; 527 f1b = e1->succ_flags[1]; 528 f2a = e2->succ_flags[0]; 529 f2b = e2->succ_flags[1]; 530 531 if (f1a == f2a && f1b == f2b) 532 return false; 533 534 return (f1a & mask) == (f2a & mask) && (f1b & mask) == (f2b & mask); 535 } 536 537 /* Compares SAME_SUCCs E1 and E2. */ 538 539 int 540 same_succ::equal (const same_succ *e1, const same_succ *e2) 541 { 542 unsigned int i, first1, first2; 543 gimple_stmt_iterator gsi1, gsi2; 544 gimple *s1, *s2; 545 basic_block bb1, bb2; 546 547 if (e1 == e2) 548 return 1; 549 550 if (e1->hashval != e2->hashval) 551 return 0; 552 553 if (e1->succ_flags.length () != e2->succ_flags.length ()) 554 return 0; 555 556 if (!bitmap_equal_p (e1->succs, e2->succs)) 557 return 0; 558 559 if (!inverse_flags (e1, e2)) 560 { 561 for (i = 0; i < e1->succ_flags.length (); ++i) 562 if (e1->succ_flags[i] != e2->succ_flags[i]) 563 return 0; 564 } 565 566 first1 = bitmap_first_set_bit (e1->bbs); 567 first2 = bitmap_first_set_bit (e2->bbs); 568 569 bb1 = BASIC_BLOCK_FOR_FN (cfun, first1); 570 bb2 = BASIC_BLOCK_FOR_FN (cfun, first2); 571 572 if (BB_SIZE (bb1) != BB_SIZE (bb2)) 573 return 0; 574 575 if (bb1->loop_father != bb2->loop_father) 576 return 0; 577 578 gsi1 = gsi_start_nondebug_bb (bb1); 579 gsi2 = gsi_start_nondebug_bb (bb2); 580 gsi_advance_fw_nondebug_nonlocal (&gsi1); 581 gsi_advance_fw_nondebug_nonlocal (&gsi2); 582 while (!(gsi_end_p (gsi1) || gsi_end_p (gsi2))) 583 { 584 s1 = gsi_stmt (gsi1); 585 s2 = gsi_stmt (gsi2); 586 if (gimple_code (s1) != gimple_code (s2)) 587 return 0; 588 if (is_gimple_call (s1) && !gimple_call_same_target_p (s1, s2)) 589 return 0; 590 gsi_next_nondebug (&gsi1); 591 gsi_next_nondebug (&gsi2); 592 gsi_advance_fw_nondebug_nonlocal (&gsi1); 593 gsi_advance_fw_nondebug_nonlocal (&gsi2); 594 } 595 596 return 1; 597 } 598 599 /* Alloc and init a new SAME_SUCC. */ 600 601 static same_succ * 602 same_succ_alloc (void) 603 { 604 same_succ *same = XNEW (struct same_succ); 605 606 same->bbs = BITMAP_ALLOC (NULL); 607 same->succs = BITMAP_ALLOC (NULL); 608 same->inverse = BITMAP_ALLOC (NULL); 609 same->succ_flags.create (10); 610 same->in_worklist = false; 611 612 return same; 613 } 614 615 /* Delete same_succ E. */ 616 617 void 618 same_succ::remove (same_succ *e) 619 { 620 BITMAP_FREE (e->bbs); 621 BITMAP_FREE (e->succs); 622 BITMAP_FREE (e->inverse); 623 e->succ_flags.release (); 624 625 XDELETE (e); 626 } 627 628 /* Reset same_succ SAME. */ 629 630 static void 631 same_succ_reset (same_succ *same) 632 { 633 bitmap_clear (same->bbs); 634 bitmap_clear (same->succs); 635 bitmap_clear (same->inverse); 636 same->succ_flags.truncate (0); 637 } 638 639 static hash_table<same_succ> *same_succ_htab; 640 641 /* Array that is used to store the edge flags for a successor. */ 642 643 static int *same_succ_edge_flags; 644 645 /* Bitmap that is used to mark bbs that are recently deleted. */ 646 647 static bitmap deleted_bbs; 648 649 /* Bitmap that is used to mark predecessors of bbs that are 650 deleted. */ 651 652 static bitmap deleted_bb_preds; 653 654 /* Prints same_succ_htab to stderr. */ 655 656 extern void debug_same_succ (void); 657 DEBUG_FUNCTION void 658 debug_same_succ ( void) 659 { 660 same_succ_htab->traverse <FILE *, ssa_same_succ_print_traverse> (stderr); 661 } 662 663 664 /* Vector of bbs to process. */ 665 666 static vec<same_succ *> worklist; 667 668 /* Prints worklist to FILE. */ 669 670 static void 671 print_worklist (FILE *file) 672 { 673 unsigned int i; 674 for (i = 0; i < worklist.length (); ++i) 675 same_succ_print (file, worklist[i]); 676 } 677 678 /* Adds SAME to worklist. */ 679 680 static void 681 add_to_worklist (same_succ *same) 682 { 683 if (same->in_worklist) 684 return; 685 686 if (bitmap_count_bits (same->bbs) < 2) 687 return; 688 689 same->in_worklist = true; 690 worklist.safe_push (same); 691 } 692 693 /* Add BB to same_succ_htab. */ 694 695 static void 696 find_same_succ_bb (basic_block bb, same_succ **same_p) 697 { 698 unsigned int j; 699 bitmap_iterator bj; 700 same_succ *same = *same_p; 701 same_succ **slot; 702 edge_iterator ei; 703 edge e; 704 705 if (bb == NULL) 706 return; 707 bitmap_set_bit (same->bbs, bb->index); 708 FOR_EACH_EDGE (e, ei, bb->succs) 709 { 710 int index = e->dest->index; 711 bitmap_set_bit (same->succs, index); 712 same_succ_edge_flags[index] = (e->flags & ~ignore_edge_flags); 713 } 714 EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj) 715 same->succ_flags.safe_push (same_succ_edge_flags[j]); 716 717 same->hashval = same_succ_hash (same); 718 719 slot = same_succ_htab->find_slot_with_hash (same, same->hashval, INSERT); 720 if (*slot == NULL) 721 { 722 *slot = same; 723 BB_SAME_SUCC (bb) = same; 724 add_to_worklist (same); 725 *same_p = NULL; 726 } 727 else 728 { 729 bitmap_set_bit ((*slot)->bbs, bb->index); 730 BB_SAME_SUCC (bb) = *slot; 731 add_to_worklist (*slot); 732 if (inverse_flags (same, *slot)) 733 bitmap_set_bit ((*slot)->inverse, bb->index); 734 same_succ_reset (same); 735 } 736 } 737 738 /* Find bbs with same successors. */ 739 740 static void 741 find_same_succ (void) 742 { 743 same_succ *same = same_succ_alloc (); 744 basic_block bb; 745 746 FOR_EACH_BB_FN (bb, cfun) 747 { 748 find_same_succ_bb (bb, &same); 749 if (same == NULL) 750 same = same_succ_alloc (); 751 } 752 753 same_succ::remove (same); 754 } 755 756 /* Initializes worklist administration. */ 757 758 static void 759 init_worklist (void) 760 { 761 alloc_aux_for_blocks (sizeof (struct aux_bb_info)); 762 same_succ_htab = new hash_table<same_succ> (n_basic_blocks_for_fn (cfun)); 763 same_succ_edge_flags = XCNEWVEC (int, last_basic_block_for_fn (cfun)); 764 deleted_bbs = BITMAP_ALLOC (NULL); 765 deleted_bb_preds = BITMAP_ALLOC (NULL); 766 worklist.create (n_basic_blocks_for_fn (cfun)); 767 find_same_succ (); 768 769 if (dump_file && (dump_flags & TDF_DETAILS)) 770 { 771 fprintf (dump_file, "initial worklist:\n"); 772 print_worklist (dump_file); 773 } 774 } 775 776 /* Deletes worklist administration. */ 777 778 static void 779 delete_worklist (void) 780 { 781 free_aux_for_blocks (); 782 delete same_succ_htab; 783 same_succ_htab = NULL; 784 XDELETEVEC (same_succ_edge_flags); 785 same_succ_edge_flags = NULL; 786 BITMAP_FREE (deleted_bbs); 787 BITMAP_FREE (deleted_bb_preds); 788 worklist.release (); 789 } 790 791 /* Mark BB as deleted, and mark its predecessors. */ 792 793 static void 794 mark_basic_block_deleted (basic_block bb) 795 { 796 edge e; 797 edge_iterator ei; 798 799 bitmap_set_bit (deleted_bbs, bb->index); 800 801 FOR_EACH_EDGE (e, ei, bb->preds) 802 bitmap_set_bit (deleted_bb_preds, e->src->index); 803 } 804 805 /* Removes BB from its corresponding same_succ. */ 806 807 static void 808 same_succ_flush_bb (basic_block bb) 809 { 810 same_succ *same = BB_SAME_SUCC (bb); 811 if (! same) 812 return; 813 814 BB_SAME_SUCC (bb) = NULL; 815 if (bitmap_single_bit_set_p (same->bbs)) 816 same_succ_htab->remove_elt_with_hash (same, same->hashval); 817 else 818 bitmap_clear_bit (same->bbs, bb->index); 819 } 820 821 /* Removes all bbs in BBS from their corresponding same_succ. */ 822 823 static void 824 same_succ_flush_bbs (bitmap bbs) 825 { 826 unsigned int i; 827 bitmap_iterator bi; 828 829 EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi) 830 same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun, i)); 831 } 832 833 /* Release the last vdef in BB, either normal or phi result. */ 834 835 static void 836 release_last_vdef (basic_block bb) 837 { 838 for (gimple_stmt_iterator i = gsi_last_bb (bb); !gsi_end_p (i); 839 gsi_prev_nondebug (&i)) 840 { 841 gimple *stmt = gsi_stmt (i); 842 if (gimple_vdef (stmt) == NULL_TREE) 843 continue; 844 845 mark_virtual_operand_for_renaming (gimple_vdef (stmt)); 846 return; 847 } 848 849 for (gphi_iterator i = gsi_start_phis (bb); !gsi_end_p (i); 850 gsi_next (&i)) 851 { 852 gphi *phi = i.phi (); 853 tree res = gimple_phi_result (phi); 854 855 if (!virtual_operand_p (res)) 856 continue; 857 858 mark_virtual_phi_result_for_renaming (phi); 859 return; 860 } 861 } 862 863 /* For deleted_bb_preds, find bbs with same successors. */ 864 865 static void 866 update_worklist (void) 867 { 868 unsigned int i; 869 bitmap_iterator bi; 870 basic_block bb; 871 same_succ *same; 872 873 bitmap_and_compl_into (deleted_bb_preds, deleted_bbs); 874 bitmap_clear (deleted_bbs); 875 876 bitmap_clear_bit (deleted_bb_preds, ENTRY_BLOCK); 877 same_succ_flush_bbs (deleted_bb_preds); 878 879 same = same_succ_alloc (); 880 EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds, 0, i, bi) 881 { 882 bb = BASIC_BLOCK_FOR_FN (cfun, i); 883 gcc_assert (bb != NULL); 884 find_same_succ_bb (bb, &same); 885 if (same == NULL) 886 same = same_succ_alloc (); 887 } 888 same_succ::remove (same); 889 bitmap_clear (deleted_bb_preds); 890 } 891 892 /* Prints cluster C to FILE. */ 893 894 static void 895 print_cluster (FILE *file, bb_cluster *c) 896 { 897 if (c == NULL) 898 return; 899 bitmap_print (file, c->bbs, "bbs:", "\n"); 900 bitmap_print (file, c->preds, "preds:", "\n"); 901 } 902 903 /* Prints cluster C to stderr. */ 904 905 extern void debug_cluster (bb_cluster *); 906 DEBUG_FUNCTION void 907 debug_cluster (bb_cluster *c) 908 { 909 print_cluster (stderr, c); 910 } 911 912 /* Update C->rep_bb, given that BB is added to the cluster. */ 913 914 static void 915 update_rep_bb (bb_cluster *c, basic_block bb) 916 { 917 /* Initial. */ 918 if (c->rep_bb == NULL) 919 { 920 c->rep_bb = bb; 921 return; 922 } 923 924 /* Current needs no deps, keep it. */ 925 if (BB_DEP_BB (c->rep_bb) == NULL) 926 return; 927 928 /* Bb needs no deps, change rep_bb. */ 929 if (BB_DEP_BB (bb) == NULL) 930 { 931 c->rep_bb = bb; 932 return; 933 } 934 935 /* Bb needs last deps earlier than current, change rep_bb. A potential 936 problem with this, is that the first deps might also be earlier, which 937 would mean we prefer longer lifetimes for the deps. To be able to check 938 for this, we would have to trace BB_FIRST_DEP_BB as well, besides 939 BB_DEP_BB, which is really BB_LAST_DEP_BB. 940 The benefit of choosing the bb with last deps earlier, is that it can 941 potentially be used as replacement for more bbs. */ 942 if (dominated_by_p (CDI_DOMINATORS, BB_DEP_BB (c->rep_bb), BB_DEP_BB (bb))) 943 c->rep_bb = bb; 944 } 945 946 /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */ 947 948 static void 949 add_bb_to_cluster (bb_cluster *c, basic_block bb) 950 { 951 edge e; 952 edge_iterator ei; 953 954 bitmap_set_bit (c->bbs, bb->index); 955 956 FOR_EACH_EDGE (e, ei, bb->preds) 957 bitmap_set_bit (c->preds, e->src->index); 958 959 update_rep_bb (c, bb); 960 } 961 962 /* Allocate and init new cluster. */ 963 964 static bb_cluster * 965 new_cluster (void) 966 { 967 bb_cluster *c; 968 c = XCNEW (bb_cluster); 969 c->bbs = BITMAP_ALLOC (NULL); 970 c->preds = BITMAP_ALLOC (NULL); 971 c->rep_bb = NULL; 972 return c; 973 } 974 975 /* Delete clusters. */ 976 977 static void 978 delete_cluster (bb_cluster *c) 979 { 980 if (c == NULL) 981 return; 982 BITMAP_FREE (c->bbs); 983 BITMAP_FREE (c->preds); 984 XDELETE (c); 985 } 986 987 988 /* Array that contains all clusters. */ 989 990 static vec<bb_cluster *> all_clusters; 991 992 /* Allocate all cluster vectors. */ 993 994 static void 995 alloc_cluster_vectors (void) 996 { 997 all_clusters.create (n_basic_blocks_for_fn (cfun)); 998 } 999 1000 /* Reset all cluster vectors. */ 1001 1002 static void 1003 reset_cluster_vectors (void) 1004 { 1005 unsigned int i; 1006 basic_block bb; 1007 for (i = 0; i < all_clusters.length (); ++i) 1008 delete_cluster (all_clusters[i]); 1009 all_clusters.truncate (0); 1010 FOR_EACH_BB_FN (bb, cfun) 1011 BB_CLUSTER (bb) = NULL; 1012 } 1013 1014 /* Delete all cluster vectors. */ 1015 1016 static void 1017 delete_cluster_vectors (void) 1018 { 1019 unsigned int i; 1020 for (i = 0; i < all_clusters.length (); ++i) 1021 delete_cluster (all_clusters[i]); 1022 all_clusters.release (); 1023 } 1024 1025 /* Merge cluster C2 into C1. */ 1026 1027 static void 1028 merge_clusters (bb_cluster *c1, bb_cluster *c2) 1029 { 1030 bitmap_ior_into (c1->bbs, c2->bbs); 1031 bitmap_ior_into (c1->preds, c2->preds); 1032 } 1033 1034 /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in 1035 all_clusters, or merge c with existing cluster. */ 1036 1037 static void 1038 set_cluster (basic_block bb1, basic_block bb2) 1039 { 1040 basic_block merge_bb, other_bb; 1041 bb_cluster *merge, *old, *c; 1042 1043 if (BB_CLUSTER (bb1) == NULL && BB_CLUSTER (bb2) == NULL) 1044 { 1045 c = new_cluster (); 1046 add_bb_to_cluster (c, bb1); 1047 add_bb_to_cluster (c, bb2); 1048 BB_CLUSTER (bb1) = c; 1049 BB_CLUSTER (bb2) = c; 1050 c->index = all_clusters.length (); 1051 all_clusters.safe_push (c); 1052 } 1053 else if (BB_CLUSTER (bb1) == NULL || BB_CLUSTER (bb2) == NULL) 1054 { 1055 merge_bb = BB_CLUSTER (bb1) == NULL ? bb2 : bb1; 1056 other_bb = BB_CLUSTER (bb1) == NULL ? bb1 : bb2; 1057 merge = BB_CLUSTER (merge_bb); 1058 add_bb_to_cluster (merge, other_bb); 1059 BB_CLUSTER (other_bb) = merge; 1060 } 1061 else if (BB_CLUSTER (bb1) != BB_CLUSTER (bb2)) 1062 { 1063 unsigned int i; 1064 bitmap_iterator bi; 1065 1066 old = BB_CLUSTER (bb2); 1067 merge = BB_CLUSTER (bb1); 1068 merge_clusters (merge, old); 1069 EXECUTE_IF_SET_IN_BITMAP (old->bbs, 0, i, bi) 1070 BB_CLUSTER (BASIC_BLOCK_FOR_FN (cfun, i)) = merge; 1071 all_clusters[old->index] = NULL; 1072 update_rep_bb (merge, old->rep_bb); 1073 delete_cluster (old); 1074 } 1075 else 1076 gcc_unreachable (); 1077 } 1078 1079 /* Return true if gimple operands T1 and T2 have the same value. */ 1080 1081 static bool 1082 gimple_operand_equal_value_p (tree t1, tree t2) 1083 { 1084 if (t1 == t2) 1085 return true; 1086 1087 if (t1 == NULL_TREE 1088 || t2 == NULL_TREE) 1089 return false; 1090 1091 if (operand_equal_p (t1, t2, OEP_MATCH_SIDE_EFFECTS)) 1092 return true; 1093 1094 return gvn_uses_equal (t1, t2); 1095 } 1096 1097 /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and 1098 gimple_bb (s2) are members of SAME_SUCC. */ 1099 1100 static bool 1101 gimple_equal_p (same_succ *same_succ, gimple *s1, gimple *s2) 1102 { 1103 unsigned int i; 1104 tree lhs1, lhs2; 1105 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2); 1106 tree t1, t2; 1107 bool inv_cond; 1108 enum tree_code code1, code2; 1109 1110 if (gimple_code (s1) != gimple_code (s2)) 1111 return false; 1112 1113 switch (gimple_code (s1)) 1114 { 1115 case GIMPLE_CALL: 1116 if (!gimple_call_same_target_p (s1, s2)) 1117 return false; 1118 1119 t1 = gimple_call_chain (s1); 1120 t2 = gimple_call_chain (s2); 1121 if (!gimple_operand_equal_value_p (t1, t2)) 1122 return false; 1123 1124 if (gimple_call_num_args (s1) != gimple_call_num_args (s2)) 1125 return false; 1126 1127 for (i = 0; i < gimple_call_num_args (s1); ++i) 1128 { 1129 t1 = gimple_call_arg (s1, i); 1130 t2 = gimple_call_arg (s2, i); 1131 if (!gimple_operand_equal_value_p (t1, t2)) 1132 return false; 1133 } 1134 1135 lhs1 = gimple_get_lhs (s1); 1136 lhs2 = gimple_get_lhs (s2); 1137 if (lhs1 == NULL_TREE && lhs2 == NULL_TREE) 1138 return true; 1139 if (lhs1 == NULL_TREE || lhs2 == NULL_TREE) 1140 return false; 1141 if (TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME) 1142 return vn_valueize (lhs1) == vn_valueize (lhs2); 1143 return operand_equal_p (lhs1, lhs2, 0); 1144 1145 case GIMPLE_ASSIGN: 1146 lhs1 = gimple_get_lhs (s1); 1147 lhs2 = gimple_get_lhs (s2); 1148 if (TREE_CODE (lhs1) != SSA_NAME 1149 && TREE_CODE (lhs2) != SSA_NAME) 1150 return (operand_equal_p (lhs1, lhs2, 0) 1151 && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1), 1152 gimple_assign_rhs1 (s2))); 1153 else if (TREE_CODE (lhs1) == SSA_NAME 1154 && TREE_CODE (lhs2) == SSA_NAME) 1155 return operand_equal_p (gimple_assign_rhs1 (s1), 1156 gimple_assign_rhs1 (s2), 0); 1157 return false; 1158 1159 case GIMPLE_COND: 1160 t1 = gimple_cond_lhs (s1); 1161 t2 = gimple_cond_lhs (s2); 1162 if (!gimple_operand_equal_value_p (t1, t2)) 1163 return false; 1164 1165 t1 = gimple_cond_rhs (s1); 1166 t2 = gimple_cond_rhs (s2); 1167 if (!gimple_operand_equal_value_p (t1, t2)) 1168 return false; 1169 1170 code1 = gimple_expr_code (s1); 1171 code2 = gimple_expr_code (s2); 1172 inv_cond = (bitmap_bit_p (same_succ->inverse, bb1->index) 1173 != bitmap_bit_p (same_succ->inverse, bb2->index)); 1174 if (inv_cond) 1175 { 1176 bool honor_nans = HONOR_NANS (t1); 1177 code2 = invert_tree_comparison (code2, honor_nans); 1178 } 1179 return code1 == code2; 1180 1181 default: 1182 return false; 1183 } 1184 } 1185 1186 /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE. 1187 Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the 1188 processed statements. */ 1189 1190 static void 1191 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse, 1192 bool *vuse_escaped) 1193 { 1194 gimple *stmt; 1195 tree lvuse; 1196 1197 while (true) 1198 { 1199 if (gsi_end_p (*gsi)) 1200 return; 1201 stmt = gsi_stmt (*gsi); 1202 1203 lvuse = gimple_vuse (stmt); 1204 if (lvuse != NULL_TREE) 1205 { 1206 *vuse = lvuse; 1207 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_DEF)) 1208 *vuse_escaped = true; 1209 } 1210 1211 if (!stmt_local_def (stmt)) 1212 return; 1213 gsi_prev_nondebug (gsi); 1214 } 1215 } 1216 1217 /* Return true if equal (in the sense of gimple_equal_p) statements STMT1 and 1218 STMT2 are allowed to be merged. */ 1219 1220 static bool 1221 merge_stmts_p (gimple *stmt1, gimple *stmt2) 1222 { 1223 /* What could be better than this here is to blacklist the bb 1224 containing the stmt, when encountering the stmt f.i. in 1225 same_succ_hash. */ 1226 if (is_tm_ending (stmt1)) 1227 return false; 1228 1229 /* Verify EH landing pads. */ 1230 if (lookup_stmt_eh_lp_fn (cfun, stmt1) != lookup_stmt_eh_lp_fn (cfun, stmt2)) 1231 return false; 1232 1233 if (is_gimple_call (stmt1) 1234 && gimple_call_internal_p (stmt1)) 1235 switch (gimple_call_internal_fn (stmt1)) 1236 { 1237 case IFN_UBSAN_NULL: 1238 case IFN_UBSAN_BOUNDS: 1239 case IFN_UBSAN_VPTR: 1240 case IFN_UBSAN_CHECK_ADD: 1241 case IFN_UBSAN_CHECK_SUB: 1242 case IFN_UBSAN_CHECK_MUL: 1243 case IFN_UBSAN_OBJECT_SIZE: 1244 case IFN_UBSAN_PTR: 1245 case IFN_ASAN_CHECK: 1246 /* For these internal functions, gimple_location is an implicit 1247 parameter, which will be used explicitly after expansion. 1248 Merging these statements may cause confusing line numbers in 1249 sanitizer messages. */ 1250 return gimple_location (stmt1) == gimple_location (stmt2); 1251 default: 1252 break; 1253 } 1254 1255 return true; 1256 } 1257 1258 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so, 1259 clusters them. */ 1260 1261 static void 1262 find_duplicate (same_succ *same_succ, basic_block bb1, basic_block bb2) 1263 { 1264 gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1); 1265 gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2); 1266 tree vuse1 = NULL_TREE, vuse2 = NULL_TREE; 1267 bool vuse_escaped = false; 1268 1269 gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped); 1270 gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped); 1271 1272 while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2)) 1273 { 1274 gimple *stmt1 = gsi_stmt (gsi1); 1275 gimple *stmt2 = gsi_stmt (gsi2); 1276 1277 if (gimple_code (stmt1) == GIMPLE_LABEL 1278 && gimple_code (stmt2) == GIMPLE_LABEL) 1279 break; 1280 1281 if (!gimple_equal_p (same_succ, stmt1, stmt2)) 1282 return; 1283 1284 if (!merge_stmts_p (stmt1, stmt2)) 1285 return; 1286 1287 gsi_prev_nondebug (&gsi1); 1288 gsi_prev_nondebug (&gsi2); 1289 gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped); 1290 gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped); 1291 } 1292 1293 while (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL) 1294 { 1295 tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1))); 1296 if (DECL_NONLOCAL (label) || FORCED_LABEL (label)) 1297 return; 1298 gsi_prev (&gsi1); 1299 } 1300 while (!gsi_end_p (gsi2) && gimple_code (gsi_stmt (gsi2)) == GIMPLE_LABEL) 1301 { 1302 tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi2))); 1303 if (DECL_NONLOCAL (label) || FORCED_LABEL (label)) 1304 return; 1305 gsi_prev (&gsi2); 1306 } 1307 if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2))) 1308 return; 1309 1310 /* If the incoming vuses are not the same, and the vuse escaped into an 1311 SSA_OP_DEF, then merging the 2 blocks will change the value of the def, 1312 which potentially means the semantics of one of the blocks will be changed. 1313 TODO: make this check more precise. */ 1314 if (vuse_escaped && vuse1 != vuse2) 1315 return; 1316 1317 if (dump_file) 1318 fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n", 1319 bb1->index, bb2->index); 1320 1321 set_cluster (bb1, bb2); 1322 } 1323 1324 /* Returns whether for all phis in DEST the phi alternatives for E1 and 1325 E2 are equal. */ 1326 1327 static bool 1328 same_phi_alternatives_1 (basic_block dest, edge e1, edge e2) 1329 { 1330 int n1 = e1->dest_idx, n2 = e2->dest_idx; 1331 gphi_iterator gsi; 1332 1333 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi)) 1334 { 1335 gphi *phi = gsi.phi (); 1336 tree lhs = gimple_phi_result (phi); 1337 tree val1 = gimple_phi_arg_def (phi, n1); 1338 tree val2 = gimple_phi_arg_def (phi, n2); 1339 1340 if (virtual_operand_p (lhs)) 1341 continue; 1342 1343 if (operand_equal_for_phi_arg_p (val1, val2)) 1344 continue; 1345 if (gvn_uses_equal (val1, val2)) 1346 continue; 1347 1348 return false; 1349 } 1350 1351 return true; 1352 } 1353 1354 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the 1355 phi alternatives for BB1 and BB2 are equal. */ 1356 1357 static bool 1358 same_phi_alternatives (same_succ *same_succ, basic_block bb1, basic_block bb2) 1359 { 1360 unsigned int s; 1361 bitmap_iterator bs; 1362 edge e1, e2; 1363 basic_block succ; 1364 1365 EXECUTE_IF_SET_IN_BITMAP (same_succ->succs, 0, s, bs) 1366 { 1367 succ = BASIC_BLOCK_FOR_FN (cfun, s); 1368 e1 = find_edge (bb1, succ); 1369 e2 = find_edge (bb2, succ); 1370 if (e1->flags & EDGE_COMPLEX 1371 || e2->flags & EDGE_COMPLEX) 1372 return false; 1373 1374 /* For all phis in bb, the phi alternatives for e1 and e2 need to have 1375 the same value. */ 1376 if (!same_phi_alternatives_1 (succ, e1, e2)) 1377 return false; 1378 } 1379 1380 return true; 1381 } 1382 1383 /* Return true if BB has non-vop phis. */ 1384 1385 static bool 1386 bb_has_non_vop_phi (basic_block bb) 1387 { 1388 gimple_seq phis = phi_nodes (bb); 1389 gimple *phi; 1390 1391 if (phis == NULL) 1392 return false; 1393 1394 if (!gimple_seq_singleton_p (phis)) 1395 return true; 1396 1397 phi = gimple_seq_first_stmt (phis); 1398 return !virtual_operand_p (gimple_phi_result (phi)); 1399 } 1400 1401 /* Returns true if redirecting the incoming edges of FROM to TO maintains the 1402 invariant that uses in FROM are dominates by their defs. */ 1403 1404 static bool 1405 deps_ok_for_redirect_from_bb_to_bb (basic_block from, basic_block to) 1406 { 1407 basic_block cd, dep_bb = BB_DEP_BB (to); 1408 edge_iterator ei; 1409 edge e; 1410 1411 if (dep_bb == NULL) 1412 return true; 1413 1414 bitmap from_preds = BITMAP_ALLOC (NULL); 1415 FOR_EACH_EDGE (e, ei, from->preds) 1416 bitmap_set_bit (from_preds, e->src->index); 1417 cd = nearest_common_dominator_for_set (CDI_DOMINATORS, from_preds); 1418 BITMAP_FREE (from_preds); 1419 1420 return dominated_by_p (CDI_DOMINATORS, dep_bb, cd); 1421 } 1422 1423 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its 1424 replacement bb) and vice versa maintains the invariant that uses in the 1425 replacement are dominates by their defs. */ 1426 1427 static bool 1428 deps_ok_for_redirect (basic_block bb1, basic_block bb2) 1429 { 1430 if (BB_CLUSTER (bb1) != NULL) 1431 bb1 = BB_CLUSTER (bb1)->rep_bb; 1432 1433 if (BB_CLUSTER (bb2) != NULL) 1434 bb2 = BB_CLUSTER (bb2)->rep_bb; 1435 1436 return (deps_ok_for_redirect_from_bb_to_bb (bb1, bb2) 1437 && deps_ok_for_redirect_from_bb_to_bb (bb2, bb1)); 1438 } 1439 1440 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */ 1441 1442 static void 1443 find_clusters_1 (same_succ *same_succ) 1444 { 1445 basic_block bb1, bb2; 1446 unsigned int i, j; 1447 bitmap_iterator bi, bj; 1448 int nr_comparisons; 1449 int max_comparisons = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS); 1450 1451 EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, 0, i, bi) 1452 { 1453 bb1 = BASIC_BLOCK_FOR_FN (cfun, i); 1454 1455 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding 1456 phi-nodes in bb1 and bb2, with the same alternatives for the same 1457 preds. */ 1458 if (bb_has_non_vop_phi (bb1) || bb_has_eh_pred (bb1) 1459 || bb_has_abnormal_pred (bb1)) 1460 continue; 1461 1462 nr_comparisons = 0; 1463 EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, i + 1, j, bj) 1464 { 1465 bb2 = BASIC_BLOCK_FOR_FN (cfun, j); 1466 1467 if (bb_has_non_vop_phi (bb2) || bb_has_eh_pred (bb2) 1468 || bb_has_abnormal_pred (bb2)) 1469 continue; 1470 1471 if (BB_CLUSTER (bb1) != NULL && BB_CLUSTER (bb1) == BB_CLUSTER (bb2)) 1472 continue; 1473 1474 /* Limit quadratic behavior. */ 1475 nr_comparisons++; 1476 if (nr_comparisons > max_comparisons) 1477 break; 1478 1479 /* This is a conservative dependency check. We could test more 1480 precise for allowed replacement direction. */ 1481 if (!deps_ok_for_redirect (bb1, bb2)) 1482 continue; 1483 1484 if (!(same_phi_alternatives (same_succ, bb1, bb2))) 1485 continue; 1486 1487 find_duplicate (same_succ, bb1, bb2); 1488 } 1489 } 1490 } 1491 1492 /* Find clusters of bbs which can be merged. */ 1493 1494 static void 1495 find_clusters (void) 1496 { 1497 same_succ *same; 1498 1499 while (!worklist.is_empty ()) 1500 { 1501 same = worklist.pop (); 1502 same->in_worklist = false; 1503 if (dump_file && (dump_flags & TDF_DETAILS)) 1504 { 1505 fprintf (dump_file, "processing worklist entry\n"); 1506 same_succ_print (dump_file, same); 1507 } 1508 find_clusters_1 (same); 1509 } 1510 } 1511 1512 /* Returns the vop phi of BB, if any. */ 1513 1514 static gphi * 1515 vop_phi (basic_block bb) 1516 { 1517 gphi *stmt; 1518 gphi_iterator gsi; 1519 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1520 { 1521 stmt = gsi.phi (); 1522 if (! virtual_operand_p (gimple_phi_result (stmt))) 1523 continue; 1524 return stmt; 1525 } 1526 return NULL; 1527 } 1528 1529 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */ 1530 1531 static void 1532 replace_block_by (basic_block bb1, basic_block bb2) 1533 { 1534 edge pred_edge; 1535 unsigned int i; 1536 gphi *bb2_phi; 1537 1538 bb2_phi = vop_phi (bb2); 1539 1540 /* Mark the basic block as deleted. */ 1541 mark_basic_block_deleted (bb1); 1542 1543 /* Redirect the incoming edges of bb1 to bb2. */ 1544 for (i = EDGE_COUNT (bb1->preds); i > 0 ; --i) 1545 { 1546 pred_edge = EDGE_PRED (bb1, i - 1); 1547 pred_edge = redirect_edge_and_branch (pred_edge, bb2); 1548 gcc_assert (pred_edge != NULL); 1549 1550 if (bb2_phi == NULL) 1551 continue; 1552 1553 /* The phi might have run out of capacity when the redirect added an 1554 argument, which means it could have been replaced. Refresh it. */ 1555 bb2_phi = vop_phi (bb2); 1556 1557 add_phi_arg (bb2_phi, SSA_NAME_VAR (gimple_phi_result (bb2_phi)), 1558 pred_edge, UNKNOWN_LOCATION); 1559 } 1560 1561 1562 /* Merge the outgoing edge counts from bb1 onto bb2. */ 1563 edge e1, e2; 1564 edge_iterator ei; 1565 1566 if (bb2->count.initialized_p ()) 1567 FOR_EACH_EDGE (e1, ei, bb1->succs) 1568 { 1569 e2 = find_edge (bb2, e1->dest); 1570 gcc_assert (e2); 1571 1572 /* If probabilities are same, we are done. 1573 If counts are nonzero we can distribute accordingly. In remaining 1574 cases just avreage the values and hope for the best. */ 1575 e2->probability = e1->probability.combine_with_count 1576 (bb1->count, e2->probability, bb2->count); 1577 } 1578 bb2->count += bb1->count; 1579 1580 /* Move over any user labels from bb1 after the bb2 labels. */ 1581 gimple_stmt_iterator gsi1 = gsi_start_bb (bb1); 1582 if (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL) 1583 { 1584 gimple_stmt_iterator gsi2 = gsi_after_labels (bb2); 1585 while (!gsi_end_p (gsi1) 1586 && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL) 1587 { 1588 tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1))); 1589 gcc_assert (!DECL_NONLOCAL (label) && !FORCED_LABEL (label)); 1590 if (DECL_ARTIFICIAL (label)) 1591 gsi_next (&gsi1); 1592 else 1593 gsi_move_before (&gsi1, &gsi2); 1594 } 1595 } 1596 1597 /* Clear range info from all stmts in BB2 -- this transformation 1598 could make them out of date. */ 1599 reset_flow_sensitive_info_in_bb (bb2); 1600 1601 /* Do updates that use bb1, before deleting bb1. */ 1602 release_last_vdef (bb1); 1603 same_succ_flush_bb (bb1); 1604 1605 delete_basic_block (bb1); 1606 } 1607 1608 /* Bbs for which update_debug_stmt need to be called. */ 1609 1610 static bitmap update_bbs; 1611 1612 /* For each cluster in all_clusters, merge all cluster->bbs. Returns 1613 number of bbs removed. */ 1614 1615 static int 1616 apply_clusters (void) 1617 { 1618 basic_block bb1, bb2; 1619 bb_cluster *c; 1620 unsigned int i, j; 1621 bitmap_iterator bj; 1622 int nr_bbs_removed = 0; 1623 1624 for (i = 0; i < all_clusters.length (); ++i) 1625 { 1626 c = all_clusters[i]; 1627 if (c == NULL) 1628 continue; 1629 1630 bb2 = c->rep_bb; 1631 bitmap_set_bit (update_bbs, bb2->index); 1632 1633 bitmap_clear_bit (c->bbs, bb2->index); 1634 EXECUTE_IF_SET_IN_BITMAP (c->bbs, 0, j, bj) 1635 { 1636 bb1 = BASIC_BLOCK_FOR_FN (cfun, j); 1637 bitmap_clear_bit (update_bbs, bb1->index); 1638 1639 replace_block_by (bb1, bb2); 1640 nr_bbs_removed++; 1641 } 1642 } 1643 1644 return nr_bbs_removed; 1645 } 1646 1647 /* Resets debug statement STMT if it has uses that are not dominated by their 1648 defs. */ 1649 1650 static void 1651 update_debug_stmt (gimple *stmt) 1652 { 1653 use_operand_p use_p; 1654 ssa_op_iter oi; 1655 basic_block bbuse; 1656 1657 if (!gimple_debug_bind_p (stmt)) 1658 return; 1659 1660 bbuse = gimple_bb (stmt); 1661 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE) 1662 { 1663 tree name = USE_FROM_PTR (use_p); 1664 gimple *def_stmt = SSA_NAME_DEF_STMT (name); 1665 basic_block bbdef = gimple_bb (def_stmt); 1666 if (bbdef == NULL || bbuse == bbdef 1667 || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef)) 1668 continue; 1669 1670 gimple_debug_bind_reset_value (stmt); 1671 update_stmt (stmt); 1672 break; 1673 } 1674 } 1675 1676 /* Resets all debug statements that have uses that are not 1677 dominated by their defs. */ 1678 1679 static void 1680 update_debug_stmts (void) 1681 { 1682 basic_block bb; 1683 bitmap_iterator bi; 1684 unsigned int i; 1685 1686 EXECUTE_IF_SET_IN_BITMAP (update_bbs, 0, i, bi) 1687 { 1688 gimple *stmt; 1689 gimple_stmt_iterator gsi; 1690 1691 bb = BASIC_BLOCK_FOR_FN (cfun, i); 1692 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1693 { 1694 stmt = gsi_stmt (gsi); 1695 if (!is_gimple_debug (stmt)) 1696 continue; 1697 update_debug_stmt (stmt); 1698 } 1699 } 1700 } 1701 1702 /* Runs tail merge optimization. */ 1703 1704 unsigned int 1705 tail_merge_optimize (unsigned int todo) 1706 { 1707 int nr_bbs_removed_total = 0; 1708 int nr_bbs_removed; 1709 bool loop_entered = false; 1710 int iteration_nr = 0; 1711 int max_iterations = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS); 1712 1713 if (!flag_tree_tail_merge 1714 || max_iterations == 0) 1715 return 0; 1716 1717 timevar_push (TV_TREE_TAIL_MERGE); 1718 1719 /* We enter from PRE which has critical edges split. Elimination 1720 does not process trivially dead code so cleanup the CFG if we 1721 are told so. And re-split critical edges then. */ 1722 if (todo & TODO_cleanup_cfg) 1723 { 1724 cleanup_tree_cfg (); 1725 todo &= ~TODO_cleanup_cfg; 1726 split_critical_edges (); 1727 } 1728 1729 if (!dom_info_available_p (CDI_DOMINATORS)) 1730 { 1731 /* PRE can leave us with unreachable blocks, remove them now. */ 1732 delete_unreachable_blocks (); 1733 calculate_dominance_info (CDI_DOMINATORS); 1734 } 1735 init_worklist (); 1736 1737 while (!worklist.is_empty ()) 1738 { 1739 if (!loop_entered) 1740 { 1741 loop_entered = true; 1742 alloc_cluster_vectors (); 1743 update_bbs = BITMAP_ALLOC (NULL); 1744 } 1745 else 1746 reset_cluster_vectors (); 1747 1748 iteration_nr++; 1749 if (dump_file && (dump_flags & TDF_DETAILS)) 1750 fprintf (dump_file, "worklist iteration #%d\n", iteration_nr); 1751 1752 find_clusters (); 1753 gcc_assert (worklist.is_empty ()); 1754 if (all_clusters.is_empty ()) 1755 break; 1756 1757 nr_bbs_removed = apply_clusters (); 1758 nr_bbs_removed_total += nr_bbs_removed; 1759 if (nr_bbs_removed == 0) 1760 break; 1761 1762 free_dominance_info (CDI_DOMINATORS); 1763 1764 if (iteration_nr == max_iterations) 1765 break; 1766 1767 calculate_dominance_info (CDI_DOMINATORS); 1768 update_worklist (); 1769 } 1770 1771 if (dump_file && (dump_flags & TDF_DETAILS)) 1772 fprintf (dump_file, "htab collision / search: %f\n", 1773 same_succ_htab->collisions ()); 1774 1775 if (nr_bbs_removed_total > 0) 1776 { 1777 if (MAY_HAVE_DEBUG_BIND_STMTS) 1778 { 1779 calculate_dominance_info (CDI_DOMINATORS); 1780 update_debug_stmts (); 1781 } 1782 1783 if (dump_file && (dump_flags & TDF_DETAILS)) 1784 { 1785 fprintf (dump_file, "Before TODOs.\n"); 1786 dump_function_to_file (current_function_decl, dump_file, dump_flags); 1787 } 1788 1789 mark_virtual_operands_for_renaming (cfun); 1790 } 1791 1792 delete_worklist (); 1793 if (loop_entered) 1794 { 1795 delete_cluster_vectors (); 1796 BITMAP_FREE (update_bbs); 1797 } 1798 1799 timevar_pop (TV_TREE_TAIL_MERGE); 1800 1801 return todo; 1802 } 1803