1 /* Full and partial redundancy elimination and code hoisting on SSA GIMPLE. 2 Copyright (C) 2001-2018 Free Software Foundation, Inc. 3 Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher 4 <stevenb@suse.de> 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 3, or (at your option) 11 any later version. 12 13 GCC is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 #include "config.h" 23 #include "system.h" 24 #include "coretypes.h" 25 #include "backend.h" 26 #include "rtl.h" 27 #include "tree.h" 28 #include "gimple.h" 29 #include "predict.h" 30 #include "alloc-pool.h" 31 #include "tree-pass.h" 32 #include "ssa.h" 33 #include "cgraph.h" 34 #include "gimple-pretty-print.h" 35 #include "fold-const.h" 36 #include "cfganal.h" 37 #include "gimple-fold.h" 38 #include "tree-eh.h" 39 #include "gimplify.h" 40 #include "gimple-iterator.h" 41 #include "tree-cfg.h" 42 #include "tree-into-ssa.h" 43 #include "tree-dfa.h" 44 #include "tree-ssa.h" 45 #include "cfgloop.h" 46 #include "tree-ssa-sccvn.h" 47 #include "tree-scalar-evolution.h" 48 #include "params.h" 49 #include "dbgcnt.h" 50 #include "domwalk.h" 51 #include "tree-ssa-propagate.h" 52 #include "tree-ssa-dce.h" 53 #include "tree-cfgcleanup.h" 54 #include "alias.h" 55 56 /* Even though this file is called tree-ssa-pre.c, we actually 57 implement a bit more than just PRE here. All of them piggy-back 58 on GVN which is implemented in tree-ssa-sccvn.c. 59 60 1. Full Redundancy Elimination (FRE) 61 This is the elimination phase of GVN. 62 63 2. Partial Redundancy Elimination (PRE) 64 This is adds computation of AVAIL_OUT and ANTIC_IN and 65 doing expression insertion to form GVN-PRE. 66 67 3. Code hoisting 68 This optimization uses the ANTIC_IN sets computed for PRE 69 to move expressions further up than PRE would do, to make 70 multiple computations of the same value fully redundant. 71 This pass is explained below (after the explanation of the 72 basic algorithm for PRE). 73 */ 74 75 /* TODO: 76 77 1. Avail sets can be shared by making an avail_find_leader that 78 walks up the dominator tree and looks in those avail sets. 79 This might affect code optimality, it's unclear right now. 80 Currently the AVAIL_OUT sets are the remaining quadraticness in 81 memory of GVN-PRE. 82 2. Strength reduction can be performed by anticipating expressions 83 we can repair later on. 84 3. We can do back-substitution or smarter value numbering to catch 85 commutative expressions split up over multiple statements. 86 */ 87 88 /* For ease of terminology, "expression node" in the below refers to 89 every expression node but GIMPLE_ASSIGN, because GIMPLE_ASSIGNs 90 represent the actual statement containing the expressions we care about, 91 and we cache the value number by putting it in the expression. */ 92 93 /* Basic algorithm for Partial Redundancy Elimination: 94 95 First we walk the statements to generate the AVAIL sets, the 96 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the 97 generation of values/expressions by a given block. We use them 98 when computing the ANTIC sets. The AVAIL sets consist of 99 SSA_NAME's that represent values, so we know what values are 100 available in what blocks. AVAIL is a forward dataflow problem. In 101 SSA, values are never killed, so we don't need a kill set, or a 102 fixpoint iteration, in order to calculate the AVAIL sets. In 103 traditional parlance, AVAIL sets tell us the downsafety of the 104 expressions/values. 105 106 Next, we generate the ANTIC sets. These sets represent the 107 anticipatable expressions. ANTIC is a backwards dataflow 108 problem. An expression is anticipatable in a given block if it could 109 be generated in that block. This means that if we had to perform 110 an insertion in that block, of the value of that expression, we 111 could. Calculating the ANTIC sets requires phi translation of 112 expressions, because the flow goes backwards through phis. We must 113 iterate to a fixpoint of the ANTIC sets, because we have a kill 114 set. Even in SSA form, values are not live over the entire 115 function, only from their definition point onwards. So we have to 116 remove values from the ANTIC set once we go past the definition 117 point of the leaders that make them up. 118 compute_antic/compute_antic_aux performs this computation. 119 120 Third, we perform insertions to make partially redundant 121 expressions fully redundant. 122 123 An expression is partially redundant (excluding partial 124 anticipation) if: 125 126 1. It is AVAIL in some, but not all, of the predecessors of a 127 given block. 128 2. It is ANTIC in all the predecessors. 129 130 In order to make it fully redundant, we insert the expression into 131 the predecessors where it is not available, but is ANTIC. 132 133 When optimizing for size, we only eliminate the partial redundancy 134 if we need to insert in only one predecessor. This avoids almost 135 completely the code size increase that PRE usually causes. 136 137 For the partial anticipation case, we only perform insertion if it 138 is partially anticipated in some block, and fully available in all 139 of the predecessors. 140 141 do_pre_regular_insertion/do_pre_partial_partial_insertion 142 performs these steps, driven by insert/insert_aux. 143 144 Fourth, we eliminate fully redundant expressions. 145 This is a simple statement walk that replaces redundant 146 calculations with the now available values. */ 147 148 /* Basic algorithm for Code Hoisting: 149 150 Code hoisting is: Moving value computations up in the control flow 151 graph to make multiple copies redundant. Typically this is a size 152 optimization, but there are cases where it also is helpful for speed. 153 154 A simple code hoisting algorithm is implemented that piggy-backs on 155 the PRE infrastructure. For code hoisting, we have to know ANTIC_OUT 156 which is effectively ANTIC_IN - AVAIL_OUT. The latter two have to be 157 computed for PRE, and we can use them to perform a limited version of 158 code hoisting, too. 159 160 For the purpose of this implementation, a value is hoistable to a basic 161 block B if the following properties are met: 162 163 1. The value is in ANTIC_IN(B) -- the value will be computed on all 164 paths from B to function exit and it can be computed in B); 165 166 2. The value is not in AVAIL_OUT(B) -- there would be no need to 167 compute the value again and make it available twice; 168 169 3. All successors of B are dominated by B -- makes sure that inserting 170 a computation of the value in B will make the remaining 171 computations fully redundant; 172 173 4. At least one successor has the value in AVAIL_OUT -- to avoid 174 hoisting values up too far; 175 176 5. There are at least two successors of B -- hoisting in straight 177 line code is pointless. 178 179 The third condition is not strictly necessary, but it would complicate 180 the hoisting pass a lot. In fact, I don't know of any code hoisting 181 algorithm that does not have this requirement. Fortunately, experiments 182 have show that most candidate hoistable values are in regions that meet 183 this condition (e.g. diamond-shape regions). 184 185 The forth condition is necessary to avoid hoisting things up too far 186 away from the uses of the value. Nothing else limits the algorithm 187 from hoisting everything up as far as ANTIC_IN allows. Experiments 188 with SPEC and CSiBE have shown that hoisting up too far results in more 189 spilling, less benefits for code size, and worse benchmark scores. 190 Fortunately, in practice most of the interesting hoisting opportunities 191 are caught despite this limitation. 192 193 For hoistable values that meet all conditions, expressions are inserted 194 to make the calculation of the hoistable value fully redundant. We 195 perform code hoisting insertions after each round of PRE insertions, 196 because code hoisting never exposes new PRE opportunities, but PRE can 197 create new code hoisting opportunities. 198 199 The code hoisting algorithm is implemented in do_hoist_insert, driven 200 by insert/insert_aux. */ 201 202 /* Representations of value numbers: 203 204 Value numbers are represented by a representative SSA_NAME. We 205 will create fake SSA_NAME's in situations where we need a 206 representative but do not have one (because it is a complex 207 expression). In order to facilitate storing the value numbers in 208 bitmaps, and keep the number of wasted SSA_NAME's down, we also 209 associate a value_id with each value number, and create full blown 210 ssa_name's only where we actually need them (IE in operands of 211 existing expressions). 212 213 Theoretically you could replace all the value_id's with 214 SSA_NAME_VERSION, but this would allocate a large number of 215 SSA_NAME's (which are each > 30 bytes) just to get a 4 byte number. 216 It would also require an additional indirection at each point we 217 use the value id. */ 218 219 /* Representation of expressions on value numbers: 220 221 Expressions consisting of value numbers are represented the same 222 way as our VN internally represents them, with an additional 223 "pre_expr" wrapping around them in order to facilitate storing all 224 of the expressions in the same sets. */ 225 226 /* Representation of sets: 227 228 The dataflow sets do not need to be sorted in any particular order 229 for the majority of their lifetime, are simply represented as two 230 bitmaps, one that keeps track of values present in the set, and one 231 that keeps track of expressions present in the set. 232 233 When we need them in topological order, we produce it on demand by 234 transforming the bitmap into an array and sorting it into topo 235 order. */ 236 237 /* Type of expression, used to know which member of the PRE_EXPR union 238 is valid. */ 239 240 enum pre_expr_kind 241 { 242 NAME, 243 NARY, 244 REFERENCE, 245 CONSTANT 246 }; 247 248 union pre_expr_union 249 { 250 tree name; 251 tree constant; 252 vn_nary_op_t nary; 253 vn_reference_t reference; 254 }; 255 256 typedef struct pre_expr_d : nofree_ptr_hash <pre_expr_d> 257 { 258 enum pre_expr_kind kind; 259 unsigned int id; 260 pre_expr_union u; 261 262 /* hash_table support. */ 263 static inline hashval_t hash (const pre_expr_d *); 264 static inline int equal (const pre_expr_d *, const pre_expr_d *); 265 } *pre_expr; 266 267 #define PRE_EXPR_NAME(e) (e)->u.name 268 #define PRE_EXPR_NARY(e) (e)->u.nary 269 #define PRE_EXPR_REFERENCE(e) (e)->u.reference 270 #define PRE_EXPR_CONSTANT(e) (e)->u.constant 271 272 /* Compare E1 and E1 for equality. */ 273 274 inline int 275 pre_expr_d::equal (const pre_expr_d *e1, const pre_expr_d *e2) 276 { 277 if (e1->kind != e2->kind) 278 return false; 279 280 switch (e1->kind) 281 { 282 case CONSTANT: 283 return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1), 284 PRE_EXPR_CONSTANT (e2)); 285 case NAME: 286 return PRE_EXPR_NAME (e1) == PRE_EXPR_NAME (e2); 287 case NARY: 288 return vn_nary_op_eq (PRE_EXPR_NARY (e1), PRE_EXPR_NARY (e2)); 289 case REFERENCE: 290 return vn_reference_eq (PRE_EXPR_REFERENCE (e1), 291 PRE_EXPR_REFERENCE (e2)); 292 default: 293 gcc_unreachable (); 294 } 295 } 296 297 /* Hash E. */ 298 299 inline hashval_t 300 pre_expr_d::hash (const pre_expr_d *e) 301 { 302 switch (e->kind) 303 { 304 case CONSTANT: 305 return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e)); 306 case NAME: 307 return SSA_NAME_VERSION (PRE_EXPR_NAME (e)); 308 case NARY: 309 return PRE_EXPR_NARY (e)->hashcode; 310 case REFERENCE: 311 return PRE_EXPR_REFERENCE (e)->hashcode; 312 default: 313 gcc_unreachable (); 314 } 315 } 316 317 /* Next global expression id number. */ 318 static unsigned int next_expression_id; 319 320 /* Mapping from expression to id number we can use in bitmap sets. */ 321 static vec<pre_expr> expressions; 322 static hash_table<pre_expr_d> *expression_to_id; 323 static vec<unsigned> name_to_id; 324 325 /* Allocate an expression id for EXPR. */ 326 327 static inline unsigned int 328 alloc_expression_id (pre_expr expr) 329 { 330 struct pre_expr_d **slot; 331 /* Make sure we won't overflow. */ 332 gcc_assert (next_expression_id + 1 > next_expression_id); 333 expr->id = next_expression_id++; 334 expressions.safe_push (expr); 335 if (expr->kind == NAME) 336 { 337 unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr)); 338 /* vec::safe_grow_cleared allocates no headroom. Avoid frequent 339 re-allocations by using vec::reserve upfront. */ 340 unsigned old_len = name_to_id.length (); 341 name_to_id.reserve (num_ssa_names - old_len); 342 name_to_id.quick_grow_cleared (num_ssa_names); 343 gcc_assert (name_to_id[version] == 0); 344 name_to_id[version] = expr->id; 345 } 346 else 347 { 348 slot = expression_to_id->find_slot (expr, INSERT); 349 gcc_assert (!*slot); 350 *slot = expr; 351 } 352 return next_expression_id - 1; 353 } 354 355 /* Return the expression id for tree EXPR. */ 356 357 static inline unsigned int 358 get_expression_id (const pre_expr expr) 359 { 360 return expr->id; 361 } 362 363 static inline unsigned int 364 lookup_expression_id (const pre_expr expr) 365 { 366 struct pre_expr_d **slot; 367 368 if (expr->kind == NAME) 369 { 370 unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr)); 371 if (name_to_id.length () <= version) 372 return 0; 373 return name_to_id[version]; 374 } 375 else 376 { 377 slot = expression_to_id->find_slot (expr, NO_INSERT); 378 if (!slot) 379 return 0; 380 return ((pre_expr)*slot)->id; 381 } 382 } 383 384 /* Return the existing expression id for EXPR, or create one if one 385 does not exist yet. */ 386 387 static inline unsigned int 388 get_or_alloc_expression_id (pre_expr expr) 389 { 390 unsigned int id = lookup_expression_id (expr); 391 if (id == 0) 392 return alloc_expression_id (expr); 393 return expr->id = id; 394 } 395 396 /* Return the expression that has expression id ID */ 397 398 static inline pre_expr 399 expression_for_id (unsigned int id) 400 { 401 return expressions[id]; 402 } 403 404 static object_allocator<pre_expr_d> pre_expr_pool ("pre_expr nodes"); 405 406 /* Given an SSA_NAME NAME, get or create a pre_expr to represent it. */ 407 408 static pre_expr 409 get_or_alloc_expr_for_name (tree name) 410 { 411 struct pre_expr_d expr; 412 pre_expr result; 413 unsigned int result_id; 414 415 expr.kind = NAME; 416 expr.id = 0; 417 PRE_EXPR_NAME (&expr) = name; 418 result_id = lookup_expression_id (&expr); 419 if (result_id != 0) 420 return expression_for_id (result_id); 421 422 result = pre_expr_pool.allocate (); 423 result->kind = NAME; 424 PRE_EXPR_NAME (result) = name; 425 alloc_expression_id (result); 426 return result; 427 } 428 429 /* An unordered bitmap set. One bitmap tracks values, the other, 430 expressions. */ 431 typedef struct bitmap_set 432 { 433 bitmap_head expressions; 434 bitmap_head values; 435 } *bitmap_set_t; 436 437 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \ 438 EXECUTE_IF_SET_IN_BITMAP (&(set)->expressions, 0, (id), (bi)) 439 440 #define FOR_EACH_VALUE_ID_IN_SET(set, id, bi) \ 441 EXECUTE_IF_SET_IN_BITMAP (&(set)->values, 0, (id), (bi)) 442 443 /* Mapping from value id to expressions with that value_id. */ 444 static vec<bitmap> value_expressions; 445 446 /* Sets that we need to keep track of. */ 447 typedef struct bb_bitmap_sets 448 { 449 /* The EXP_GEN set, which represents expressions/values generated in 450 a basic block. */ 451 bitmap_set_t exp_gen; 452 453 /* The PHI_GEN set, which represents PHI results generated in a 454 basic block. */ 455 bitmap_set_t phi_gen; 456 457 /* The TMP_GEN set, which represents results/temporaries generated 458 in a basic block. IE the LHS of an expression. */ 459 bitmap_set_t tmp_gen; 460 461 /* The AVAIL_OUT set, which represents which values are available in 462 a given basic block. */ 463 bitmap_set_t avail_out; 464 465 /* The ANTIC_IN set, which represents which values are anticipatable 466 in a given basic block. */ 467 bitmap_set_t antic_in; 468 469 /* The PA_IN set, which represents which values are 470 partially anticipatable in a given basic block. */ 471 bitmap_set_t pa_in; 472 473 /* The NEW_SETS set, which is used during insertion to augment the 474 AVAIL_OUT set of blocks with the new insertions performed during 475 the current iteration. */ 476 bitmap_set_t new_sets; 477 478 /* A cache for value_dies_in_block_x. */ 479 bitmap expr_dies; 480 481 /* The live virtual operand on successor edges. */ 482 tree vop_on_exit; 483 484 /* True if we have visited this block during ANTIC calculation. */ 485 unsigned int visited : 1; 486 487 /* True when the block contains a call that might not return. */ 488 unsigned int contains_may_not_return_call : 1; 489 } *bb_value_sets_t; 490 491 #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen 492 #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen 493 #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen 494 #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out 495 #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in 496 #define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in 497 #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets 498 #define EXPR_DIES(BB) ((bb_value_sets_t) ((BB)->aux))->expr_dies 499 #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited 500 #define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call 501 #define BB_LIVE_VOP_ON_EXIT(BB) ((bb_value_sets_t) ((BB)->aux))->vop_on_exit 502 503 504 /* This structure is used to keep track of statistics on what 505 optimization PRE was able to perform. */ 506 static struct 507 { 508 /* The number of new expressions/temporaries generated by PRE. */ 509 int insertions; 510 511 /* The number of inserts found due to partial anticipation */ 512 int pa_insert; 513 514 /* The number of inserts made for code hoisting. */ 515 int hoist_insert; 516 517 /* The number of new PHI nodes added by PRE. */ 518 int phis; 519 } pre_stats; 520 521 static bool do_partial_partial; 522 static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int); 523 static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr); 524 static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr); 525 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t); 526 static bool bitmap_set_contains_value (bitmap_set_t, unsigned int); 527 static void bitmap_insert_into_set (bitmap_set_t, pre_expr); 528 static bitmap_set_t bitmap_set_new (void); 529 static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *, 530 tree); 531 static tree find_or_generate_expression (basic_block, tree, gimple_seq *); 532 static unsigned int get_expr_value_id (pre_expr); 533 534 /* We can add and remove elements and entries to and from sets 535 and hash tables, so we use alloc pools for them. */ 536 537 static object_allocator<bitmap_set> bitmap_set_pool ("Bitmap sets"); 538 static bitmap_obstack grand_bitmap_obstack; 539 540 /* A three tuple {e, pred, v} used to cache phi translations in the 541 phi_translate_table. */ 542 543 typedef struct expr_pred_trans_d : free_ptr_hash<expr_pred_trans_d> 544 { 545 /* The expression. */ 546 pre_expr e; 547 548 /* The predecessor block along which we translated the expression. */ 549 basic_block pred; 550 551 /* The value that resulted from the translation. */ 552 pre_expr v; 553 554 /* The hashcode for the expression, pred pair. This is cached for 555 speed reasons. */ 556 hashval_t hashcode; 557 558 /* hash_table support. */ 559 static inline hashval_t hash (const expr_pred_trans_d *); 560 static inline int equal (const expr_pred_trans_d *, const expr_pred_trans_d *); 561 } *expr_pred_trans_t; 562 typedef const struct expr_pred_trans_d *const_expr_pred_trans_t; 563 564 inline hashval_t 565 expr_pred_trans_d::hash (const expr_pred_trans_d *e) 566 { 567 return e->hashcode; 568 } 569 570 inline int 571 expr_pred_trans_d::equal (const expr_pred_trans_d *ve1, 572 const expr_pred_trans_d *ve2) 573 { 574 basic_block b1 = ve1->pred; 575 basic_block b2 = ve2->pred; 576 577 /* If they are not translations for the same basic block, they can't 578 be equal. */ 579 if (b1 != b2) 580 return false; 581 return pre_expr_d::equal (ve1->e, ve2->e); 582 } 583 584 /* The phi_translate_table caches phi translations for a given 585 expression and predecessor. */ 586 static hash_table<expr_pred_trans_d> *phi_translate_table; 587 588 /* Add the tuple mapping from {expression E, basic block PRED} to 589 the phi translation table and return whether it pre-existed. */ 590 591 static inline bool 592 phi_trans_add (expr_pred_trans_t *entry, pre_expr e, basic_block pred) 593 { 594 expr_pred_trans_t *slot; 595 expr_pred_trans_d tem; 596 hashval_t hash = iterative_hash_hashval_t (pre_expr_d::hash (e), 597 pred->index); 598 tem.e = e; 599 tem.pred = pred; 600 tem.hashcode = hash; 601 slot = phi_translate_table->find_slot_with_hash (&tem, hash, INSERT); 602 if (*slot) 603 { 604 *entry = *slot; 605 return true; 606 } 607 608 *entry = *slot = XNEW (struct expr_pred_trans_d); 609 (*entry)->e = e; 610 (*entry)->pred = pred; 611 (*entry)->hashcode = hash; 612 return false; 613 } 614 615 616 /* Add expression E to the expression set of value id V. */ 617 618 static void 619 add_to_value (unsigned int v, pre_expr e) 620 { 621 bitmap set; 622 623 gcc_checking_assert (get_expr_value_id (e) == v); 624 625 if (v >= value_expressions.length ()) 626 { 627 value_expressions.safe_grow_cleared (v + 1); 628 } 629 630 set = value_expressions[v]; 631 if (!set) 632 { 633 set = BITMAP_ALLOC (&grand_bitmap_obstack); 634 value_expressions[v] = set; 635 } 636 637 bitmap_set_bit (set, get_or_alloc_expression_id (e)); 638 } 639 640 /* Create a new bitmap set and return it. */ 641 642 static bitmap_set_t 643 bitmap_set_new (void) 644 { 645 bitmap_set_t ret = bitmap_set_pool.allocate (); 646 bitmap_initialize (&ret->expressions, &grand_bitmap_obstack); 647 bitmap_initialize (&ret->values, &grand_bitmap_obstack); 648 return ret; 649 } 650 651 /* Return the value id for a PRE expression EXPR. */ 652 653 static unsigned int 654 get_expr_value_id (pre_expr expr) 655 { 656 unsigned int id; 657 switch (expr->kind) 658 { 659 case CONSTANT: 660 id = get_constant_value_id (PRE_EXPR_CONSTANT (expr)); 661 break; 662 case NAME: 663 id = VN_INFO (PRE_EXPR_NAME (expr))->value_id; 664 break; 665 case NARY: 666 id = PRE_EXPR_NARY (expr)->value_id; 667 break; 668 case REFERENCE: 669 id = PRE_EXPR_REFERENCE (expr)->value_id; 670 break; 671 default: 672 gcc_unreachable (); 673 } 674 /* ??? We cannot assert that expr has a value-id (it can be 0), because 675 we assign value-ids only to expressions that have a result 676 in set_hashtable_value_ids. */ 677 return id; 678 } 679 680 /* Return a SCCVN valnum (SSA name or constant) for the PRE value-id VAL. */ 681 682 static tree 683 sccvn_valnum_from_value_id (unsigned int val) 684 { 685 bitmap_iterator bi; 686 unsigned int i; 687 bitmap exprset = value_expressions[val]; 688 EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi) 689 { 690 pre_expr vexpr = expression_for_id (i); 691 if (vexpr->kind == NAME) 692 return VN_INFO (PRE_EXPR_NAME (vexpr))->valnum; 693 else if (vexpr->kind == CONSTANT) 694 return PRE_EXPR_CONSTANT (vexpr); 695 } 696 return NULL_TREE; 697 } 698 699 /* Insert an expression EXPR into a bitmapped set. */ 700 701 static void 702 bitmap_insert_into_set (bitmap_set_t set, pre_expr expr) 703 { 704 unsigned int val = get_expr_value_id (expr); 705 if (! value_id_constant_p (val)) 706 { 707 /* Note this is the only function causing multiple expressions 708 for the same value to appear in a set. This is needed for 709 TMP_GEN, PHI_GEN and NEW_SETs. */ 710 bitmap_set_bit (&set->values, val); 711 bitmap_set_bit (&set->expressions, get_or_alloc_expression_id (expr)); 712 } 713 } 714 715 /* Copy a bitmapped set ORIG, into bitmapped set DEST. */ 716 717 static void 718 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig) 719 { 720 bitmap_copy (&dest->expressions, &orig->expressions); 721 bitmap_copy (&dest->values, &orig->values); 722 } 723 724 725 /* Free memory used up by SET. */ 726 static void 727 bitmap_set_free (bitmap_set_t set) 728 { 729 bitmap_clear (&set->expressions); 730 bitmap_clear (&set->values); 731 } 732 733 734 /* Generate an topological-ordered array of bitmap set SET. */ 735 736 static vec<pre_expr> 737 sorted_array_from_bitmap_set (bitmap_set_t set) 738 { 739 unsigned int i, j; 740 bitmap_iterator bi, bj; 741 vec<pre_expr> result; 742 743 /* Pre-allocate enough space for the array. */ 744 result.create (bitmap_count_bits (&set->expressions)); 745 746 FOR_EACH_VALUE_ID_IN_SET (set, i, bi) 747 { 748 /* The number of expressions having a given value is usually 749 relatively small. Thus, rather than making a vector of all 750 the expressions and sorting it by value-id, we walk the values 751 and check in the reverse mapping that tells us what expressions 752 have a given value, to filter those in our set. As a result, 753 the expressions are inserted in value-id order, which means 754 topological order. 755 756 If this is somehow a significant lose for some cases, we can 757 choose which set to walk based on the set size. */ 758 bitmap exprset = value_expressions[i]; 759 EXECUTE_IF_SET_IN_BITMAP (exprset, 0, j, bj) 760 { 761 if (bitmap_bit_p (&set->expressions, j)) 762 result.quick_push (expression_for_id (j)); 763 } 764 } 765 766 return result; 767 } 768 769 /* Subtract all expressions contained in ORIG from DEST. */ 770 771 static bitmap_set_t 772 bitmap_set_subtract_expressions (bitmap_set_t dest, bitmap_set_t orig) 773 { 774 bitmap_set_t result = bitmap_set_new (); 775 bitmap_iterator bi; 776 unsigned int i; 777 778 bitmap_and_compl (&result->expressions, &dest->expressions, 779 &orig->expressions); 780 781 FOR_EACH_EXPR_ID_IN_SET (result, i, bi) 782 { 783 pre_expr expr = expression_for_id (i); 784 unsigned int value_id = get_expr_value_id (expr); 785 bitmap_set_bit (&result->values, value_id); 786 } 787 788 return result; 789 } 790 791 /* Subtract all values in bitmap set B from bitmap set A. */ 792 793 static void 794 bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b) 795 { 796 unsigned int i; 797 bitmap_iterator bi; 798 unsigned to_remove = -1U; 799 bitmap_and_compl_into (&a->values, &b->values); 800 FOR_EACH_EXPR_ID_IN_SET (a, i, bi) 801 { 802 if (to_remove != -1U) 803 { 804 bitmap_clear_bit (&a->expressions, to_remove); 805 to_remove = -1U; 806 } 807 pre_expr expr = expression_for_id (i); 808 if (! bitmap_bit_p (&a->values, get_expr_value_id (expr))) 809 to_remove = i; 810 } 811 if (to_remove != -1U) 812 bitmap_clear_bit (&a->expressions, to_remove); 813 } 814 815 816 /* Return true if bitmapped set SET contains the value VALUE_ID. */ 817 818 static bool 819 bitmap_set_contains_value (bitmap_set_t set, unsigned int value_id) 820 { 821 if (value_id_constant_p (value_id)) 822 return true; 823 824 return bitmap_bit_p (&set->values, value_id); 825 } 826 827 static inline bool 828 bitmap_set_contains_expr (bitmap_set_t set, const pre_expr expr) 829 { 830 return bitmap_bit_p (&set->expressions, get_expression_id (expr)); 831 } 832 833 /* Return true if two bitmap sets are equal. */ 834 835 static bool 836 bitmap_set_equal (bitmap_set_t a, bitmap_set_t b) 837 { 838 return bitmap_equal_p (&a->values, &b->values); 839 } 840 841 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists, 842 and add it otherwise. */ 843 844 static void 845 bitmap_value_replace_in_set (bitmap_set_t set, pre_expr expr) 846 { 847 unsigned int val = get_expr_value_id (expr); 848 if (value_id_constant_p (val)) 849 return; 850 851 if (bitmap_set_contains_value (set, val)) 852 { 853 /* The number of expressions having a given value is usually 854 significantly less than the total number of expressions in SET. 855 Thus, rather than check, for each expression in SET, whether it 856 has the value LOOKFOR, we walk the reverse mapping that tells us 857 what expressions have a given value, and see if any of those 858 expressions are in our set. For large testcases, this is about 859 5-10x faster than walking the bitmap. If this is somehow a 860 significant lose for some cases, we can choose which set to walk 861 based on the set size. */ 862 unsigned int i; 863 bitmap_iterator bi; 864 bitmap exprset = value_expressions[val]; 865 EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi) 866 { 867 if (bitmap_clear_bit (&set->expressions, i)) 868 { 869 bitmap_set_bit (&set->expressions, get_expression_id (expr)); 870 return; 871 } 872 } 873 gcc_unreachable (); 874 } 875 else 876 bitmap_insert_into_set (set, expr); 877 } 878 879 /* Insert EXPR into SET if EXPR's value is not already present in 880 SET. */ 881 882 static void 883 bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr) 884 { 885 unsigned int val = get_expr_value_id (expr); 886 887 gcc_checking_assert (expr->id == get_or_alloc_expression_id (expr)); 888 889 /* Constant values are always considered to be part of the set. */ 890 if (value_id_constant_p (val)) 891 return; 892 893 /* If the value membership changed, add the expression. */ 894 if (bitmap_set_bit (&set->values, val)) 895 bitmap_set_bit (&set->expressions, expr->id); 896 } 897 898 /* Print out EXPR to outfile. */ 899 900 static void 901 print_pre_expr (FILE *outfile, const pre_expr expr) 902 { 903 if (! expr) 904 { 905 fprintf (outfile, "NULL"); 906 return; 907 } 908 switch (expr->kind) 909 { 910 case CONSTANT: 911 print_generic_expr (outfile, PRE_EXPR_CONSTANT (expr)); 912 break; 913 case NAME: 914 print_generic_expr (outfile, PRE_EXPR_NAME (expr)); 915 break; 916 case NARY: 917 { 918 unsigned int i; 919 vn_nary_op_t nary = PRE_EXPR_NARY (expr); 920 fprintf (outfile, "{%s,", get_tree_code_name (nary->opcode)); 921 for (i = 0; i < nary->length; i++) 922 { 923 print_generic_expr (outfile, nary->op[i]); 924 if (i != (unsigned) nary->length - 1) 925 fprintf (outfile, ","); 926 } 927 fprintf (outfile, "}"); 928 } 929 break; 930 931 case REFERENCE: 932 { 933 vn_reference_op_t vro; 934 unsigned int i; 935 vn_reference_t ref = PRE_EXPR_REFERENCE (expr); 936 fprintf (outfile, "{"); 937 for (i = 0; 938 ref->operands.iterate (i, &vro); 939 i++) 940 { 941 bool closebrace = false; 942 if (vro->opcode != SSA_NAME 943 && TREE_CODE_CLASS (vro->opcode) != tcc_declaration) 944 { 945 fprintf (outfile, "%s", get_tree_code_name (vro->opcode)); 946 if (vro->op0) 947 { 948 fprintf (outfile, "<"); 949 closebrace = true; 950 } 951 } 952 if (vro->op0) 953 { 954 print_generic_expr (outfile, vro->op0); 955 if (vro->op1) 956 { 957 fprintf (outfile, ","); 958 print_generic_expr (outfile, vro->op1); 959 } 960 if (vro->op2) 961 { 962 fprintf (outfile, ","); 963 print_generic_expr (outfile, vro->op2); 964 } 965 } 966 if (closebrace) 967 fprintf (outfile, ">"); 968 if (i != ref->operands.length () - 1) 969 fprintf (outfile, ","); 970 } 971 fprintf (outfile, "}"); 972 if (ref->vuse) 973 { 974 fprintf (outfile, "@"); 975 print_generic_expr (outfile, ref->vuse); 976 } 977 } 978 break; 979 } 980 } 981 void debug_pre_expr (pre_expr); 982 983 /* Like print_pre_expr but always prints to stderr. */ 984 DEBUG_FUNCTION void 985 debug_pre_expr (pre_expr e) 986 { 987 print_pre_expr (stderr, e); 988 fprintf (stderr, "\n"); 989 } 990 991 /* Print out SET to OUTFILE. */ 992 993 static void 994 print_bitmap_set (FILE *outfile, bitmap_set_t set, 995 const char *setname, int blockindex) 996 { 997 fprintf (outfile, "%s[%d] := { ", setname, blockindex); 998 if (set) 999 { 1000 bool first = true; 1001 unsigned i; 1002 bitmap_iterator bi; 1003 1004 FOR_EACH_EXPR_ID_IN_SET (set, i, bi) 1005 { 1006 const pre_expr expr = expression_for_id (i); 1007 1008 if (!first) 1009 fprintf (outfile, ", "); 1010 first = false; 1011 print_pre_expr (outfile, expr); 1012 1013 fprintf (outfile, " (%04d)", get_expr_value_id (expr)); 1014 } 1015 } 1016 fprintf (outfile, " }\n"); 1017 } 1018 1019 void debug_bitmap_set (bitmap_set_t); 1020 1021 DEBUG_FUNCTION void 1022 debug_bitmap_set (bitmap_set_t set) 1023 { 1024 print_bitmap_set (stderr, set, "debug", 0); 1025 } 1026 1027 void debug_bitmap_sets_for (basic_block); 1028 1029 DEBUG_FUNCTION void 1030 debug_bitmap_sets_for (basic_block bb) 1031 { 1032 print_bitmap_set (stderr, AVAIL_OUT (bb), "avail_out", bb->index); 1033 print_bitmap_set (stderr, EXP_GEN (bb), "exp_gen", bb->index); 1034 print_bitmap_set (stderr, PHI_GEN (bb), "phi_gen", bb->index); 1035 print_bitmap_set (stderr, TMP_GEN (bb), "tmp_gen", bb->index); 1036 print_bitmap_set (stderr, ANTIC_IN (bb), "antic_in", bb->index); 1037 if (do_partial_partial) 1038 print_bitmap_set (stderr, PA_IN (bb), "pa_in", bb->index); 1039 print_bitmap_set (stderr, NEW_SETS (bb), "new_sets", bb->index); 1040 } 1041 1042 /* Print out the expressions that have VAL to OUTFILE. */ 1043 1044 static void 1045 print_value_expressions (FILE *outfile, unsigned int val) 1046 { 1047 bitmap set = value_expressions[val]; 1048 if (set) 1049 { 1050 bitmap_set x; 1051 char s[10]; 1052 sprintf (s, "%04d", val); 1053 x.expressions = *set; 1054 print_bitmap_set (outfile, &x, s, 0); 1055 } 1056 } 1057 1058 1059 DEBUG_FUNCTION void 1060 debug_value_expressions (unsigned int val) 1061 { 1062 print_value_expressions (stderr, val); 1063 } 1064 1065 /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to 1066 represent it. */ 1067 1068 static pre_expr 1069 get_or_alloc_expr_for_constant (tree constant) 1070 { 1071 unsigned int result_id; 1072 unsigned int value_id; 1073 struct pre_expr_d expr; 1074 pre_expr newexpr; 1075 1076 expr.kind = CONSTANT; 1077 PRE_EXPR_CONSTANT (&expr) = constant; 1078 result_id = lookup_expression_id (&expr); 1079 if (result_id != 0) 1080 return expression_for_id (result_id); 1081 1082 newexpr = pre_expr_pool.allocate (); 1083 newexpr->kind = CONSTANT; 1084 PRE_EXPR_CONSTANT (newexpr) = constant; 1085 alloc_expression_id (newexpr); 1086 value_id = get_or_alloc_constant_value_id (constant); 1087 add_to_value (value_id, newexpr); 1088 return newexpr; 1089 } 1090 1091 /* Get or allocate a pre_expr for a piece of GIMPLE, and return it. 1092 Currently only supports constants and SSA_NAMES. */ 1093 static pre_expr 1094 get_or_alloc_expr_for (tree t) 1095 { 1096 if (TREE_CODE (t) == SSA_NAME) 1097 return get_or_alloc_expr_for_name (t); 1098 else if (is_gimple_min_invariant (t)) 1099 return get_or_alloc_expr_for_constant (t); 1100 gcc_unreachable (); 1101 } 1102 1103 /* Return the folded version of T if T, when folded, is a gimple 1104 min_invariant or an SSA name. Otherwise, return T. */ 1105 1106 static pre_expr 1107 fully_constant_expression (pre_expr e) 1108 { 1109 switch (e->kind) 1110 { 1111 case CONSTANT: 1112 return e; 1113 case NARY: 1114 { 1115 vn_nary_op_t nary = PRE_EXPR_NARY (e); 1116 tree res = vn_nary_simplify (nary); 1117 if (!res) 1118 return e; 1119 if (is_gimple_min_invariant (res)) 1120 return get_or_alloc_expr_for_constant (res); 1121 if (TREE_CODE (res) == SSA_NAME) 1122 return get_or_alloc_expr_for_name (res); 1123 return e; 1124 } 1125 case REFERENCE: 1126 { 1127 vn_reference_t ref = PRE_EXPR_REFERENCE (e); 1128 tree folded; 1129 if ((folded = fully_constant_vn_reference_p (ref))) 1130 return get_or_alloc_expr_for_constant (folded); 1131 return e; 1132 } 1133 default: 1134 return e; 1135 } 1136 return e; 1137 } 1138 1139 /* Translate the VUSE backwards through phi nodes in PHIBLOCK, so that 1140 it has the value it would have in BLOCK. Set *SAME_VALID to true 1141 in case the new vuse doesn't change the value id of the OPERANDS. */ 1142 1143 static tree 1144 translate_vuse_through_block (vec<vn_reference_op_s> operands, 1145 alias_set_type set, tree type, tree vuse, 1146 basic_block phiblock, 1147 basic_block block, bool *same_valid) 1148 { 1149 gimple *phi = SSA_NAME_DEF_STMT (vuse); 1150 ao_ref ref; 1151 edge e = NULL; 1152 bool use_oracle; 1153 1154 *same_valid = true; 1155 1156 if (gimple_bb (phi) != phiblock) 1157 return vuse; 1158 1159 use_oracle = ao_ref_init_from_vn_reference (&ref, set, type, operands); 1160 1161 /* Use the alias-oracle to find either the PHI node in this block, 1162 the first VUSE used in this block that is equivalent to vuse or 1163 the first VUSE which definition in this block kills the value. */ 1164 if (gimple_code (phi) == GIMPLE_PHI) 1165 e = find_edge (block, phiblock); 1166 else if (use_oracle) 1167 while (!stmt_may_clobber_ref_p_1 (phi, &ref)) 1168 { 1169 vuse = gimple_vuse (phi); 1170 phi = SSA_NAME_DEF_STMT (vuse); 1171 if (gimple_bb (phi) != phiblock) 1172 return vuse; 1173 if (gimple_code (phi) == GIMPLE_PHI) 1174 { 1175 e = find_edge (block, phiblock); 1176 break; 1177 } 1178 } 1179 else 1180 return NULL_TREE; 1181 1182 if (e) 1183 { 1184 if (use_oracle) 1185 { 1186 bitmap visited = NULL; 1187 unsigned int cnt; 1188 /* Try to find a vuse that dominates this phi node by skipping 1189 non-clobbering statements. */ 1190 vuse = get_continuation_for_phi (phi, &ref, &cnt, &visited, false, 1191 NULL, NULL); 1192 if (visited) 1193 BITMAP_FREE (visited); 1194 } 1195 else 1196 vuse = NULL_TREE; 1197 if (!vuse) 1198 { 1199 /* If we didn't find any, the value ID can't stay the same, 1200 but return the translated vuse. */ 1201 *same_valid = false; 1202 vuse = PHI_ARG_DEF (phi, e->dest_idx); 1203 } 1204 /* ??? We would like to return vuse here as this is the canonical 1205 upmost vdef that this reference is associated with. But during 1206 insertion of the references into the hash tables we only ever 1207 directly insert with their direct gimple_vuse, hence returning 1208 something else would make us not find the other expression. */ 1209 return PHI_ARG_DEF (phi, e->dest_idx); 1210 } 1211 1212 return NULL_TREE; 1213 } 1214 1215 /* Like bitmap_find_leader, but checks for the value existing in SET1 *or* 1216 SET2 *or* SET3. This is used to avoid making a set consisting of the union 1217 of PA_IN and ANTIC_IN during insert and phi-translation. */ 1218 1219 static inline pre_expr 1220 find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2, 1221 bitmap_set_t set3 = NULL) 1222 { 1223 pre_expr result = NULL; 1224 1225 if (set1) 1226 result = bitmap_find_leader (set1, val); 1227 if (!result && set2) 1228 result = bitmap_find_leader (set2, val); 1229 if (!result && set3) 1230 result = bitmap_find_leader (set3, val); 1231 return result; 1232 } 1233 1234 /* Get the tree type for our PRE expression e. */ 1235 1236 static tree 1237 get_expr_type (const pre_expr e) 1238 { 1239 switch (e->kind) 1240 { 1241 case NAME: 1242 return TREE_TYPE (PRE_EXPR_NAME (e)); 1243 case CONSTANT: 1244 return TREE_TYPE (PRE_EXPR_CONSTANT (e)); 1245 case REFERENCE: 1246 return PRE_EXPR_REFERENCE (e)->type; 1247 case NARY: 1248 return PRE_EXPR_NARY (e)->type; 1249 } 1250 gcc_unreachable (); 1251 } 1252 1253 /* Get a representative SSA_NAME for a given expression that is available in B. 1254 Since all of our sub-expressions are treated as values, we require 1255 them to be SSA_NAME's for simplicity. 1256 Prior versions of GVNPRE used to use "value handles" here, so that 1257 an expression would be VH.11 + VH.10 instead of d_3 + e_6. In 1258 either case, the operands are really values (IE we do not expect 1259 them to be usable without finding leaders). */ 1260 1261 static tree 1262 get_representative_for (const pre_expr e, basic_block b = NULL) 1263 { 1264 tree name, valnum = NULL_TREE; 1265 unsigned int value_id = get_expr_value_id (e); 1266 1267 switch (e->kind) 1268 { 1269 case NAME: 1270 return VN_INFO (PRE_EXPR_NAME (e))->valnum; 1271 case CONSTANT: 1272 return PRE_EXPR_CONSTANT (e); 1273 case NARY: 1274 case REFERENCE: 1275 { 1276 /* Go through all of the expressions representing this value 1277 and pick out an SSA_NAME. */ 1278 unsigned int i; 1279 bitmap_iterator bi; 1280 bitmap exprs = value_expressions[value_id]; 1281 EXECUTE_IF_SET_IN_BITMAP (exprs, 0, i, bi) 1282 { 1283 pre_expr rep = expression_for_id (i); 1284 if (rep->kind == NAME) 1285 { 1286 tree name = PRE_EXPR_NAME (rep); 1287 valnum = VN_INFO (name)->valnum; 1288 gimple *def = SSA_NAME_DEF_STMT (name); 1289 /* We have to return either a new representative or one 1290 that can be used for expression simplification and thus 1291 is available in B. */ 1292 if (! b 1293 || gimple_nop_p (def) 1294 || dominated_by_p (CDI_DOMINATORS, b, gimple_bb (def))) 1295 return name; 1296 } 1297 else if (rep->kind == CONSTANT) 1298 return PRE_EXPR_CONSTANT (rep); 1299 } 1300 } 1301 break; 1302 } 1303 1304 /* If we reached here we couldn't find an SSA_NAME. This can 1305 happen when we've discovered a value that has never appeared in 1306 the program as set to an SSA_NAME, as the result of phi translation. 1307 Create one here. 1308 ??? We should be able to re-use this when we insert the statement 1309 to compute it. */ 1310 name = make_temp_ssa_name (get_expr_type (e), gimple_build_nop (), "pretmp"); 1311 VN_INFO_GET (name)->value_id = value_id; 1312 VN_INFO (name)->valnum = valnum ? valnum : name; 1313 /* ??? For now mark this SSA name for release by SCCVN. */ 1314 VN_INFO (name)->needs_insertion = true; 1315 add_to_value (value_id, get_or_alloc_expr_for_name (name)); 1316 if (dump_file && (dump_flags & TDF_DETAILS)) 1317 { 1318 fprintf (dump_file, "Created SSA_NAME representative "); 1319 print_generic_expr (dump_file, name); 1320 fprintf (dump_file, " for expression:"); 1321 print_pre_expr (dump_file, e); 1322 fprintf (dump_file, " (%04d)\n", value_id); 1323 } 1324 1325 return name; 1326 } 1327 1328 1329 static pre_expr 1330 phi_translate (bitmap_set_t, pre_expr, bitmap_set_t, bitmap_set_t, edge); 1331 1332 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of 1333 the phis in PRED. Return NULL if we can't find a leader for each part 1334 of the translated expression. */ 1335 1336 static pre_expr 1337 phi_translate_1 (bitmap_set_t dest, 1338 pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, edge e) 1339 { 1340 basic_block pred = e->src; 1341 basic_block phiblock = e->dest; 1342 switch (expr->kind) 1343 { 1344 case NARY: 1345 { 1346 unsigned int i; 1347 bool changed = false; 1348 vn_nary_op_t nary = PRE_EXPR_NARY (expr); 1349 vn_nary_op_t newnary = XALLOCAVAR (struct vn_nary_op_s, 1350 sizeof_vn_nary_op (nary->length)); 1351 memcpy (newnary, nary, sizeof_vn_nary_op (nary->length)); 1352 1353 for (i = 0; i < newnary->length; i++) 1354 { 1355 if (TREE_CODE (newnary->op[i]) != SSA_NAME) 1356 continue; 1357 else 1358 { 1359 pre_expr leader, result; 1360 unsigned int op_val_id = VN_INFO (newnary->op[i])->value_id; 1361 leader = find_leader_in_sets (op_val_id, set1, set2); 1362 result = phi_translate (dest, leader, set1, set2, e); 1363 if (result && result != leader) 1364 /* If op has a leader in the sets we translate make 1365 sure to use the value of the translated expression. 1366 We might need a new representative for that. */ 1367 newnary->op[i] = get_representative_for (result, pred); 1368 else if (!result) 1369 return NULL; 1370 1371 changed |= newnary->op[i] != nary->op[i]; 1372 } 1373 } 1374 if (changed) 1375 { 1376 pre_expr constant; 1377 unsigned int new_val_id; 1378 1379 PRE_EXPR_NARY (expr) = newnary; 1380 constant = fully_constant_expression (expr); 1381 PRE_EXPR_NARY (expr) = nary; 1382 if (constant != expr) 1383 { 1384 /* For non-CONSTANTs we have to make sure we can eventually 1385 insert the expression. Which means we need to have a 1386 leader for it. */ 1387 if (constant->kind != CONSTANT) 1388 { 1389 /* Do not allow simplifications to non-constants over 1390 backedges as this will likely result in a loop PHI node 1391 to be inserted and increased register pressure. 1392 See PR77498 - this avoids doing predcoms work in 1393 a less efficient way. */ 1394 if (e->flags & EDGE_DFS_BACK) 1395 ; 1396 else 1397 { 1398 unsigned value_id = get_expr_value_id (constant); 1399 /* We want a leader in ANTIC_OUT or AVAIL_OUT here. 1400 dest has what we computed into ANTIC_OUT sofar 1401 so pick from that - since topological sorting 1402 by sorted_array_from_bitmap_set isn't perfect 1403 we may lose some cases here. */ 1404 constant = find_leader_in_sets (value_id, dest, 1405 AVAIL_OUT (pred)); 1406 if (constant) 1407 return constant; 1408 } 1409 } 1410 else 1411 return constant; 1412 } 1413 1414 /* vn_nary_* do not valueize operands. */ 1415 for (i = 0; i < newnary->length; ++i) 1416 if (TREE_CODE (newnary->op[i]) == SSA_NAME) 1417 newnary->op[i] = VN_INFO (newnary->op[i])->valnum; 1418 tree result = vn_nary_op_lookup_pieces (newnary->length, 1419 newnary->opcode, 1420 newnary->type, 1421 &newnary->op[0], 1422 &nary); 1423 if (result && is_gimple_min_invariant (result)) 1424 return get_or_alloc_expr_for_constant (result); 1425 1426 expr = pre_expr_pool.allocate (); 1427 expr->kind = NARY; 1428 expr->id = 0; 1429 if (nary) 1430 { 1431 PRE_EXPR_NARY (expr) = nary; 1432 new_val_id = nary->value_id; 1433 get_or_alloc_expression_id (expr); 1434 } 1435 else 1436 { 1437 new_val_id = get_next_value_id (); 1438 value_expressions.safe_grow_cleared (get_max_value_id () + 1); 1439 nary = vn_nary_op_insert_pieces (newnary->length, 1440 newnary->opcode, 1441 newnary->type, 1442 &newnary->op[0], 1443 result, new_val_id); 1444 PRE_EXPR_NARY (expr) = nary; 1445 get_or_alloc_expression_id (expr); 1446 } 1447 add_to_value (new_val_id, expr); 1448 } 1449 return expr; 1450 } 1451 break; 1452 1453 case REFERENCE: 1454 { 1455 vn_reference_t ref = PRE_EXPR_REFERENCE (expr); 1456 vec<vn_reference_op_s> operands = ref->operands; 1457 tree vuse = ref->vuse; 1458 tree newvuse = vuse; 1459 vec<vn_reference_op_s> newoperands = vNULL; 1460 bool changed = false, same_valid = true; 1461 unsigned int i, n; 1462 vn_reference_op_t operand; 1463 vn_reference_t newref; 1464 1465 for (i = 0; operands.iterate (i, &operand); i++) 1466 { 1467 pre_expr opresult; 1468 pre_expr leader; 1469 tree op[3]; 1470 tree type = operand->type; 1471 vn_reference_op_s newop = *operand; 1472 op[0] = operand->op0; 1473 op[1] = operand->op1; 1474 op[2] = operand->op2; 1475 for (n = 0; n < 3; ++n) 1476 { 1477 unsigned int op_val_id; 1478 if (!op[n]) 1479 continue; 1480 if (TREE_CODE (op[n]) != SSA_NAME) 1481 { 1482 /* We can't possibly insert these. */ 1483 if (n != 0 1484 && !is_gimple_min_invariant (op[n])) 1485 break; 1486 continue; 1487 } 1488 op_val_id = VN_INFO (op[n])->value_id; 1489 leader = find_leader_in_sets (op_val_id, set1, set2); 1490 opresult = phi_translate (dest, leader, set1, set2, e); 1491 if (opresult && opresult != leader) 1492 { 1493 tree name = get_representative_for (opresult); 1494 changed |= name != op[n]; 1495 op[n] = name; 1496 } 1497 else if (!opresult) 1498 break; 1499 } 1500 if (n != 3) 1501 { 1502 newoperands.release (); 1503 return NULL; 1504 } 1505 if (!changed) 1506 continue; 1507 if (!newoperands.exists ()) 1508 newoperands = operands.copy (); 1509 /* We may have changed from an SSA_NAME to a constant */ 1510 if (newop.opcode == SSA_NAME && TREE_CODE (op[0]) != SSA_NAME) 1511 newop.opcode = TREE_CODE (op[0]); 1512 newop.type = type; 1513 newop.op0 = op[0]; 1514 newop.op1 = op[1]; 1515 newop.op2 = op[2]; 1516 newoperands[i] = newop; 1517 } 1518 gcc_checking_assert (i == operands.length ()); 1519 1520 if (vuse) 1521 { 1522 newvuse = translate_vuse_through_block (newoperands.exists () 1523 ? newoperands : operands, 1524 ref->set, ref->type, 1525 vuse, phiblock, pred, 1526 &same_valid); 1527 if (newvuse == NULL_TREE) 1528 { 1529 newoperands.release (); 1530 return NULL; 1531 } 1532 } 1533 1534 if (changed || newvuse != vuse) 1535 { 1536 unsigned int new_val_id; 1537 1538 tree result = vn_reference_lookup_pieces (newvuse, ref->set, 1539 ref->type, 1540 newoperands.exists () 1541 ? newoperands : operands, 1542 &newref, VN_WALK); 1543 if (result) 1544 newoperands.release (); 1545 1546 /* We can always insert constants, so if we have a partial 1547 redundant constant load of another type try to translate it 1548 to a constant of appropriate type. */ 1549 if (result && is_gimple_min_invariant (result)) 1550 { 1551 tree tem = result; 1552 if (!useless_type_conversion_p (ref->type, TREE_TYPE (result))) 1553 { 1554 tem = fold_unary (VIEW_CONVERT_EXPR, ref->type, result); 1555 if (tem && !is_gimple_min_invariant (tem)) 1556 tem = NULL_TREE; 1557 } 1558 if (tem) 1559 return get_or_alloc_expr_for_constant (tem); 1560 } 1561 1562 /* If we'd have to convert things we would need to validate 1563 if we can insert the translated expression. So fail 1564 here for now - we cannot insert an alias with a different 1565 type in the VN tables either, as that would assert. */ 1566 if (result 1567 && !useless_type_conversion_p (ref->type, TREE_TYPE (result))) 1568 return NULL; 1569 else if (!result && newref 1570 && !useless_type_conversion_p (ref->type, newref->type)) 1571 { 1572 newoperands.release (); 1573 return NULL; 1574 } 1575 1576 expr = pre_expr_pool.allocate (); 1577 expr->kind = REFERENCE; 1578 expr->id = 0; 1579 1580 if (newref) 1581 new_val_id = newref->value_id; 1582 else 1583 { 1584 if (changed || !same_valid) 1585 { 1586 new_val_id = get_next_value_id (); 1587 value_expressions.safe_grow_cleared 1588 (get_max_value_id () + 1); 1589 } 1590 else 1591 new_val_id = ref->value_id; 1592 if (!newoperands.exists ()) 1593 newoperands = operands.copy (); 1594 newref = vn_reference_insert_pieces (newvuse, ref->set, 1595 ref->type, 1596 newoperands, 1597 result, new_val_id); 1598 newoperands = vNULL; 1599 } 1600 PRE_EXPR_REFERENCE (expr) = newref; 1601 get_or_alloc_expression_id (expr); 1602 add_to_value (new_val_id, expr); 1603 } 1604 newoperands.release (); 1605 return expr; 1606 } 1607 break; 1608 1609 case NAME: 1610 { 1611 tree name = PRE_EXPR_NAME (expr); 1612 gimple *def_stmt = SSA_NAME_DEF_STMT (name); 1613 /* If the SSA name is defined by a PHI node in this block, 1614 translate it. */ 1615 if (gimple_code (def_stmt) == GIMPLE_PHI 1616 && gimple_bb (def_stmt) == phiblock) 1617 { 1618 tree def = PHI_ARG_DEF (def_stmt, e->dest_idx); 1619 1620 /* Handle constant. */ 1621 if (is_gimple_min_invariant (def)) 1622 return get_or_alloc_expr_for_constant (def); 1623 1624 return get_or_alloc_expr_for_name (def); 1625 } 1626 /* Otherwise return it unchanged - it will get removed if its 1627 value is not available in PREDs AVAIL_OUT set of expressions 1628 by the subtraction of TMP_GEN. */ 1629 return expr; 1630 } 1631 1632 default: 1633 gcc_unreachable (); 1634 } 1635 } 1636 1637 /* Wrapper around phi_translate_1 providing caching functionality. */ 1638 1639 static pre_expr 1640 phi_translate (bitmap_set_t dest, pre_expr expr, 1641 bitmap_set_t set1, bitmap_set_t set2, edge e) 1642 { 1643 expr_pred_trans_t slot = NULL; 1644 pre_expr phitrans; 1645 1646 if (!expr) 1647 return NULL; 1648 1649 /* Constants contain no values that need translation. */ 1650 if (expr->kind == CONSTANT) 1651 return expr; 1652 1653 if (value_id_constant_p (get_expr_value_id (expr))) 1654 return expr; 1655 1656 /* Don't add translations of NAMEs as those are cheap to translate. */ 1657 if (expr->kind != NAME) 1658 { 1659 if (phi_trans_add (&slot, expr, e->src)) 1660 return slot->v; 1661 /* Store NULL for the value we want to return in the case of 1662 recursing. */ 1663 slot->v = NULL; 1664 } 1665 1666 /* Translate. */ 1667 phitrans = phi_translate_1 (dest, expr, set1, set2, e); 1668 1669 if (slot) 1670 { 1671 if (phitrans) 1672 slot->v = phitrans; 1673 else 1674 /* Remove failed translations again, they cause insert 1675 iteration to not pick up new opportunities reliably. */ 1676 phi_translate_table->remove_elt_with_hash (slot, slot->hashcode); 1677 } 1678 1679 return phitrans; 1680 } 1681 1682 1683 /* For each expression in SET, translate the values through phi nodes 1684 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting 1685 expressions in DEST. */ 1686 1687 static void 1688 phi_translate_set (bitmap_set_t dest, bitmap_set_t set, edge e) 1689 { 1690 vec<pre_expr> exprs; 1691 pre_expr expr; 1692 int i; 1693 1694 if (gimple_seq_empty_p (phi_nodes (e->dest))) 1695 { 1696 bitmap_set_copy (dest, set); 1697 return; 1698 } 1699 1700 exprs = sorted_array_from_bitmap_set (set); 1701 FOR_EACH_VEC_ELT (exprs, i, expr) 1702 { 1703 pre_expr translated; 1704 translated = phi_translate (dest, expr, set, NULL, e); 1705 if (!translated) 1706 continue; 1707 1708 bitmap_insert_into_set (dest, translated); 1709 } 1710 exprs.release (); 1711 } 1712 1713 /* Find the leader for a value (i.e., the name representing that 1714 value) in a given set, and return it. Return NULL if no leader 1715 is found. */ 1716 1717 static pre_expr 1718 bitmap_find_leader (bitmap_set_t set, unsigned int val) 1719 { 1720 if (value_id_constant_p (val)) 1721 { 1722 unsigned int i; 1723 bitmap_iterator bi; 1724 bitmap exprset = value_expressions[val]; 1725 1726 EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi) 1727 { 1728 pre_expr expr = expression_for_id (i); 1729 if (expr->kind == CONSTANT) 1730 return expr; 1731 } 1732 } 1733 if (bitmap_set_contains_value (set, val)) 1734 { 1735 /* Rather than walk the entire bitmap of expressions, and see 1736 whether any of them has the value we are looking for, we look 1737 at the reverse mapping, which tells us the set of expressions 1738 that have a given value (IE value->expressions with that 1739 value) and see if any of those expressions are in our set. 1740 The number of expressions per value is usually significantly 1741 less than the number of expressions in the set. In fact, for 1742 large testcases, doing it this way is roughly 5-10x faster 1743 than walking the bitmap. 1744 If this is somehow a significant lose for some cases, we can 1745 choose which set to walk based on which set is smaller. */ 1746 unsigned int i; 1747 bitmap_iterator bi; 1748 bitmap exprset = value_expressions[val]; 1749 1750 EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi) 1751 return expression_for_id (i); 1752 } 1753 return NULL; 1754 } 1755 1756 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of 1757 BLOCK by seeing if it is not killed in the block. Note that we are 1758 only determining whether there is a store that kills it. Because 1759 of the order in which clean iterates over values, we are guaranteed 1760 that altered operands will have caused us to be eliminated from the 1761 ANTIC_IN set already. */ 1762 1763 static bool 1764 value_dies_in_block_x (pre_expr expr, basic_block block) 1765 { 1766 tree vuse = PRE_EXPR_REFERENCE (expr)->vuse; 1767 vn_reference_t refx = PRE_EXPR_REFERENCE (expr); 1768 gimple *def; 1769 gimple_stmt_iterator gsi; 1770 unsigned id = get_expression_id (expr); 1771 bool res = false; 1772 ao_ref ref; 1773 1774 if (!vuse) 1775 return false; 1776 1777 /* Lookup a previously calculated result. */ 1778 if (EXPR_DIES (block) 1779 && bitmap_bit_p (EXPR_DIES (block), id * 2)) 1780 return bitmap_bit_p (EXPR_DIES (block), id * 2 + 1); 1781 1782 /* A memory expression {e, VUSE} dies in the block if there is a 1783 statement that may clobber e. If, starting statement walk from the 1784 top of the basic block, a statement uses VUSE there can be no kill 1785 inbetween that use and the original statement that loaded {e, VUSE}, 1786 so we can stop walking. */ 1787 ref.base = NULL_TREE; 1788 for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi)) 1789 { 1790 tree def_vuse, def_vdef; 1791 def = gsi_stmt (gsi); 1792 def_vuse = gimple_vuse (def); 1793 def_vdef = gimple_vdef (def); 1794 1795 /* Not a memory statement. */ 1796 if (!def_vuse) 1797 continue; 1798 1799 /* Not a may-def. */ 1800 if (!def_vdef) 1801 { 1802 /* A load with the same VUSE, we're done. */ 1803 if (def_vuse == vuse) 1804 break; 1805 1806 continue; 1807 } 1808 1809 /* Init ref only if we really need it. */ 1810 if (ref.base == NULL_TREE 1811 && !ao_ref_init_from_vn_reference (&ref, refx->set, refx->type, 1812 refx->operands)) 1813 { 1814 res = true; 1815 break; 1816 } 1817 /* If the statement may clobber expr, it dies. */ 1818 if (stmt_may_clobber_ref_p_1 (def, &ref)) 1819 { 1820 res = true; 1821 break; 1822 } 1823 } 1824 1825 /* Remember the result. */ 1826 if (!EXPR_DIES (block)) 1827 EXPR_DIES (block) = BITMAP_ALLOC (&grand_bitmap_obstack); 1828 bitmap_set_bit (EXPR_DIES (block), id * 2); 1829 if (res) 1830 bitmap_set_bit (EXPR_DIES (block), id * 2 + 1); 1831 1832 return res; 1833 } 1834 1835 1836 /* Determine if OP is valid in SET1 U SET2, which it is when the union 1837 contains its value-id. */ 1838 1839 static bool 1840 op_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, tree op) 1841 { 1842 if (op && TREE_CODE (op) == SSA_NAME) 1843 { 1844 unsigned int value_id = VN_INFO (op)->value_id; 1845 if (!(bitmap_set_contains_value (set1, value_id) 1846 || (set2 && bitmap_set_contains_value (set2, value_id)))) 1847 return false; 1848 } 1849 return true; 1850 } 1851 1852 /* Determine if the expression EXPR is valid in SET1 U SET2. 1853 ONLY SET2 CAN BE NULL. 1854 This means that we have a leader for each part of the expression 1855 (if it consists of values), or the expression is an SSA_NAME. 1856 For loads/calls, we also see if the vuse is killed in this block. */ 1857 1858 static bool 1859 valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr) 1860 { 1861 switch (expr->kind) 1862 { 1863 case NAME: 1864 /* By construction all NAMEs are available. Non-available 1865 NAMEs are removed by subtracting TMP_GEN from the sets. */ 1866 return true; 1867 case NARY: 1868 { 1869 unsigned int i; 1870 vn_nary_op_t nary = PRE_EXPR_NARY (expr); 1871 for (i = 0; i < nary->length; i++) 1872 if (!op_valid_in_sets (set1, set2, nary->op[i])) 1873 return false; 1874 return true; 1875 } 1876 break; 1877 case REFERENCE: 1878 { 1879 vn_reference_t ref = PRE_EXPR_REFERENCE (expr); 1880 vn_reference_op_t vro; 1881 unsigned int i; 1882 1883 FOR_EACH_VEC_ELT (ref->operands, i, vro) 1884 { 1885 if (!op_valid_in_sets (set1, set2, vro->op0) 1886 || !op_valid_in_sets (set1, set2, vro->op1) 1887 || !op_valid_in_sets (set1, set2, vro->op2)) 1888 return false; 1889 } 1890 return true; 1891 } 1892 default: 1893 gcc_unreachable (); 1894 } 1895 } 1896 1897 /* Clean the set of expressions SET1 that are no longer valid in SET1 or SET2. 1898 This means expressions that are made up of values we have no leaders for 1899 in SET1 or SET2. */ 1900 1901 static void 1902 clean (bitmap_set_t set1, bitmap_set_t set2 = NULL) 1903 { 1904 vec<pre_expr> exprs = sorted_array_from_bitmap_set (set1); 1905 pre_expr expr; 1906 int i; 1907 1908 FOR_EACH_VEC_ELT (exprs, i, expr) 1909 { 1910 if (!valid_in_sets (set1, set2, expr)) 1911 { 1912 unsigned int val = get_expr_value_id (expr); 1913 bitmap_clear_bit (&set1->expressions, get_expression_id (expr)); 1914 /* We are entered with possibly multiple expressions for a value 1915 so before removing a value from the set see if there's an 1916 expression for it left. */ 1917 if (! bitmap_find_leader (set1, val)) 1918 bitmap_clear_bit (&set1->values, val); 1919 } 1920 } 1921 exprs.release (); 1922 } 1923 1924 /* Clean the set of expressions that are no longer valid in SET because 1925 they are clobbered in BLOCK or because they trap and may not be executed. */ 1926 1927 static void 1928 prune_clobbered_mems (bitmap_set_t set, basic_block block) 1929 { 1930 bitmap_iterator bi; 1931 unsigned i; 1932 unsigned to_remove = -1U; 1933 bool any_removed = false; 1934 1935 FOR_EACH_EXPR_ID_IN_SET (set, i, bi) 1936 { 1937 /* Remove queued expr. */ 1938 if (to_remove != -1U) 1939 { 1940 bitmap_clear_bit (&set->expressions, to_remove); 1941 any_removed = true; 1942 to_remove = -1U; 1943 } 1944 1945 pre_expr expr = expression_for_id (i); 1946 if (expr->kind == REFERENCE) 1947 { 1948 vn_reference_t ref = PRE_EXPR_REFERENCE (expr); 1949 if (ref->vuse) 1950 { 1951 gimple *def_stmt = SSA_NAME_DEF_STMT (ref->vuse); 1952 if (!gimple_nop_p (def_stmt) 1953 && ((gimple_bb (def_stmt) != block 1954 && !dominated_by_p (CDI_DOMINATORS, 1955 block, gimple_bb (def_stmt))) 1956 || (gimple_bb (def_stmt) == block 1957 && value_dies_in_block_x (expr, block)))) 1958 to_remove = i; 1959 } 1960 } 1961 else if (expr->kind == NARY) 1962 { 1963 vn_nary_op_t nary = PRE_EXPR_NARY (expr); 1964 /* If the NARY may trap make sure the block does not contain 1965 a possible exit point. 1966 ??? This is overly conservative if we translate AVAIL_OUT 1967 as the available expression might be after the exit point. */ 1968 if (BB_MAY_NOTRETURN (block) 1969 && vn_nary_may_trap (nary)) 1970 to_remove = i; 1971 } 1972 } 1973 1974 /* Remove queued expr. */ 1975 if (to_remove != -1U) 1976 { 1977 bitmap_clear_bit (&set->expressions, to_remove); 1978 any_removed = true; 1979 } 1980 1981 /* Above we only removed expressions, now clean the set of values 1982 which no longer have any corresponding expression. We cannot 1983 clear the value at the time we remove an expression since there 1984 may be multiple expressions per value. 1985 If we'd queue possibly to be removed values we could use 1986 the bitmap_find_leader way to see if there's still an expression 1987 for it. For some ratio of to be removed values and number of 1988 values/expressions in the set this might be faster than rebuilding 1989 the value-set. */ 1990 if (any_removed) 1991 { 1992 bitmap_clear (&set->values); 1993 FOR_EACH_EXPR_ID_IN_SET (set, i, bi) 1994 { 1995 pre_expr expr = expression_for_id (i); 1996 unsigned int value_id = get_expr_value_id (expr); 1997 bitmap_set_bit (&set->values, value_id); 1998 } 1999 } 2000 } 2001 2002 static sbitmap has_abnormal_preds; 2003 2004 /* Compute the ANTIC set for BLOCK. 2005 2006 If succs(BLOCK) > 1 then 2007 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK) 2008 else if succs(BLOCK) == 1 then 2009 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) 2010 2011 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK]) 2012 2013 Note that clean() is deferred until after the iteration. */ 2014 2015 static bool 2016 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge) 2017 { 2018 bitmap_set_t S, old, ANTIC_OUT; 2019 edge e; 2020 edge_iterator ei; 2021 2022 bool was_visited = BB_VISITED (block); 2023 bool changed = ! BB_VISITED (block); 2024 BB_VISITED (block) = 1; 2025 old = ANTIC_OUT = S = NULL; 2026 2027 /* If any edges from predecessors are abnormal, antic_in is empty, 2028 so do nothing. */ 2029 if (block_has_abnormal_pred_edge) 2030 goto maybe_dump_sets; 2031 2032 old = ANTIC_IN (block); 2033 ANTIC_OUT = bitmap_set_new (); 2034 2035 /* If the block has no successors, ANTIC_OUT is empty. */ 2036 if (EDGE_COUNT (block->succs) == 0) 2037 ; 2038 /* If we have one successor, we could have some phi nodes to 2039 translate through. */ 2040 else if (single_succ_p (block)) 2041 { 2042 e = single_succ_edge (block); 2043 gcc_assert (BB_VISITED (e->dest)); 2044 phi_translate_set (ANTIC_OUT, ANTIC_IN (e->dest), e); 2045 } 2046 /* If we have multiple successors, we take the intersection of all of 2047 them. Note that in the case of loop exit phi nodes, we may have 2048 phis to translate through. */ 2049 else 2050 { 2051 size_t i; 2052 edge first = NULL; 2053 2054 auto_vec<edge> worklist (EDGE_COUNT (block->succs)); 2055 FOR_EACH_EDGE (e, ei, block->succs) 2056 { 2057 if (!first 2058 && BB_VISITED (e->dest)) 2059 first = e; 2060 else if (BB_VISITED (e->dest)) 2061 worklist.quick_push (e); 2062 else 2063 { 2064 /* Unvisited successors get their ANTIC_IN replaced by the 2065 maximal set to arrive at a maximum ANTIC_IN solution. 2066 We can ignore them in the intersection operation and thus 2067 need not explicitely represent that maximum solution. */ 2068 if (dump_file && (dump_flags & TDF_DETAILS)) 2069 fprintf (dump_file, "ANTIC_IN is MAX on %d->%d\n", 2070 e->src->index, e->dest->index); 2071 } 2072 } 2073 2074 /* Of multiple successors we have to have visited one already 2075 which is guaranteed by iteration order. */ 2076 gcc_assert (first != NULL); 2077 2078 phi_translate_set (ANTIC_OUT, ANTIC_IN (first->dest), first); 2079 2080 /* If we have multiple successors we need to intersect the ANTIC_OUT 2081 sets. For values that's a simple intersection but for 2082 expressions it is a union. Given we want to have a single 2083 expression per value in our sets we have to canonicalize. 2084 Avoid randomness and running into cycles like for PR82129 and 2085 canonicalize the expression we choose to the one with the 2086 lowest id. This requires we actually compute the union first. */ 2087 FOR_EACH_VEC_ELT (worklist, i, e) 2088 { 2089 if (!gimple_seq_empty_p (phi_nodes (e->dest))) 2090 { 2091 bitmap_set_t tmp = bitmap_set_new (); 2092 phi_translate_set (tmp, ANTIC_IN (e->dest), e); 2093 bitmap_and_into (&ANTIC_OUT->values, &tmp->values); 2094 bitmap_ior_into (&ANTIC_OUT->expressions, &tmp->expressions); 2095 bitmap_set_free (tmp); 2096 } 2097 else 2098 { 2099 bitmap_and_into (&ANTIC_OUT->values, &ANTIC_IN (e->dest)->values); 2100 bitmap_ior_into (&ANTIC_OUT->expressions, 2101 &ANTIC_IN (e->dest)->expressions); 2102 } 2103 } 2104 if (! worklist.is_empty ()) 2105 { 2106 /* Prune expressions not in the value set. */ 2107 bitmap_iterator bi; 2108 unsigned int i; 2109 unsigned int to_clear = -1U; 2110 FOR_EACH_EXPR_ID_IN_SET (ANTIC_OUT, i, bi) 2111 { 2112 if (to_clear != -1U) 2113 { 2114 bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear); 2115 to_clear = -1U; 2116 } 2117 pre_expr expr = expression_for_id (i); 2118 unsigned int value_id = get_expr_value_id (expr); 2119 if (!bitmap_bit_p (&ANTIC_OUT->values, value_id)) 2120 to_clear = i; 2121 } 2122 if (to_clear != -1U) 2123 bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear); 2124 } 2125 } 2126 2127 /* Prune expressions that are clobbered in block and thus become 2128 invalid if translated from ANTIC_OUT to ANTIC_IN. */ 2129 prune_clobbered_mems (ANTIC_OUT, block); 2130 2131 /* Generate ANTIC_OUT - TMP_GEN. */ 2132 S = bitmap_set_subtract_expressions (ANTIC_OUT, TMP_GEN (block)); 2133 2134 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */ 2135 ANTIC_IN (block) = bitmap_set_subtract_expressions (EXP_GEN (block), 2136 TMP_GEN (block)); 2137 2138 /* Then union in the ANTIC_OUT - TMP_GEN values, 2139 to get ANTIC_OUT U EXP_GEN - TMP_GEN */ 2140 bitmap_ior_into (&ANTIC_IN (block)->values, &S->values); 2141 bitmap_ior_into (&ANTIC_IN (block)->expressions, &S->expressions); 2142 2143 /* clean (ANTIC_IN (block)) is defered to after the iteration converged 2144 because it can cause non-convergence, see for example PR81181. */ 2145 2146 /* Intersect ANTIC_IN with the old ANTIC_IN. This is required until 2147 we properly represent the maximum expression set, thus not prune 2148 values without expressions during the iteration. */ 2149 if (was_visited 2150 && bitmap_and_into (&ANTIC_IN (block)->values, &old->values)) 2151 { 2152 if (dump_file && (dump_flags & TDF_DETAILS)) 2153 fprintf (dump_file, "warning: intersecting with old ANTIC_IN " 2154 "shrinks the set\n"); 2155 /* Prune expressions not in the value set. */ 2156 bitmap_iterator bi; 2157 unsigned int i; 2158 unsigned int to_clear = -1U; 2159 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (block), i, bi) 2160 { 2161 if (to_clear != -1U) 2162 { 2163 bitmap_clear_bit (&ANTIC_IN (block)->expressions, to_clear); 2164 to_clear = -1U; 2165 } 2166 pre_expr expr = expression_for_id (i); 2167 unsigned int value_id = get_expr_value_id (expr); 2168 if (!bitmap_bit_p (&ANTIC_IN (block)->values, value_id)) 2169 to_clear = i; 2170 } 2171 if (to_clear != -1U) 2172 bitmap_clear_bit (&ANTIC_IN (block)->expressions, to_clear); 2173 } 2174 2175 if (!bitmap_set_equal (old, ANTIC_IN (block))) 2176 changed = true; 2177 2178 maybe_dump_sets: 2179 if (dump_file && (dump_flags & TDF_DETAILS)) 2180 { 2181 if (ANTIC_OUT) 2182 print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index); 2183 2184 if (changed) 2185 fprintf (dump_file, "[changed] "); 2186 print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN", 2187 block->index); 2188 2189 if (S) 2190 print_bitmap_set (dump_file, S, "S", block->index); 2191 } 2192 if (old) 2193 bitmap_set_free (old); 2194 if (S) 2195 bitmap_set_free (S); 2196 if (ANTIC_OUT) 2197 bitmap_set_free (ANTIC_OUT); 2198 return changed; 2199 } 2200 2201 /* Compute PARTIAL_ANTIC for BLOCK. 2202 2203 If succs(BLOCK) > 1 then 2204 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not 2205 in ANTIC_OUT for all succ(BLOCK) 2206 else if succs(BLOCK) == 1 then 2207 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)]) 2208 2209 PA_IN[BLOCK] = clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK] - ANTIC_IN[BLOCK]) 2210 2211 */ 2212 static void 2213 compute_partial_antic_aux (basic_block block, 2214 bool block_has_abnormal_pred_edge) 2215 { 2216 bitmap_set_t old_PA_IN; 2217 bitmap_set_t PA_OUT; 2218 edge e; 2219 edge_iterator ei; 2220 unsigned long max_pa = PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH); 2221 2222 old_PA_IN = PA_OUT = NULL; 2223 2224 /* If any edges from predecessors are abnormal, antic_in is empty, 2225 so do nothing. */ 2226 if (block_has_abnormal_pred_edge) 2227 goto maybe_dump_sets; 2228 2229 /* If there are too many partially anticipatable values in the 2230 block, phi_translate_set can take an exponential time: stop 2231 before the translation starts. */ 2232 if (max_pa 2233 && single_succ_p (block) 2234 && bitmap_count_bits (&PA_IN (single_succ (block))->values) > max_pa) 2235 goto maybe_dump_sets; 2236 2237 old_PA_IN = PA_IN (block); 2238 PA_OUT = bitmap_set_new (); 2239 2240 /* If the block has no successors, ANTIC_OUT is empty. */ 2241 if (EDGE_COUNT (block->succs) == 0) 2242 ; 2243 /* If we have one successor, we could have some phi nodes to 2244 translate through. Note that we can't phi translate across DFS 2245 back edges in partial antic, because it uses a union operation on 2246 the successors. For recurrences like IV's, we will end up 2247 generating a new value in the set on each go around (i + 3 (VH.1) 2248 VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */ 2249 else if (single_succ_p (block)) 2250 { 2251 e = single_succ_edge (block); 2252 if (!(e->flags & EDGE_DFS_BACK)) 2253 phi_translate_set (PA_OUT, PA_IN (e->dest), e); 2254 } 2255 /* If we have multiple successors, we take the union of all of 2256 them. */ 2257 else 2258 { 2259 size_t i; 2260 2261 auto_vec<edge> worklist (EDGE_COUNT (block->succs)); 2262 FOR_EACH_EDGE (e, ei, block->succs) 2263 { 2264 if (e->flags & EDGE_DFS_BACK) 2265 continue; 2266 worklist.quick_push (e); 2267 } 2268 if (worklist.length () > 0) 2269 { 2270 FOR_EACH_VEC_ELT (worklist, i, e) 2271 { 2272 unsigned int i; 2273 bitmap_iterator bi; 2274 2275 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (e->dest), i, bi) 2276 bitmap_value_insert_into_set (PA_OUT, 2277 expression_for_id (i)); 2278 if (!gimple_seq_empty_p (phi_nodes (e->dest))) 2279 { 2280 bitmap_set_t pa_in = bitmap_set_new (); 2281 phi_translate_set (pa_in, PA_IN (e->dest), e); 2282 FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi) 2283 bitmap_value_insert_into_set (PA_OUT, 2284 expression_for_id (i)); 2285 bitmap_set_free (pa_in); 2286 } 2287 else 2288 FOR_EACH_EXPR_ID_IN_SET (PA_IN (e->dest), i, bi) 2289 bitmap_value_insert_into_set (PA_OUT, 2290 expression_for_id (i)); 2291 } 2292 } 2293 } 2294 2295 /* Prune expressions that are clobbered in block and thus become 2296 invalid if translated from PA_OUT to PA_IN. */ 2297 prune_clobbered_mems (PA_OUT, block); 2298 2299 /* PA_IN starts with PA_OUT - TMP_GEN. 2300 Then we subtract things from ANTIC_IN. */ 2301 PA_IN (block) = bitmap_set_subtract_expressions (PA_OUT, TMP_GEN (block)); 2302 2303 /* For partial antic, we want to put back in the phi results, since 2304 we will properly avoid making them partially antic over backedges. */ 2305 bitmap_ior_into (&PA_IN (block)->values, &PHI_GEN (block)->values); 2306 bitmap_ior_into (&PA_IN (block)->expressions, &PHI_GEN (block)->expressions); 2307 2308 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */ 2309 bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block)); 2310 2311 clean (PA_IN (block), ANTIC_IN (block)); 2312 2313 maybe_dump_sets: 2314 if (dump_file && (dump_flags & TDF_DETAILS)) 2315 { 2316 if (PA_OUT) 2317 print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index); 2318 2319 print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index); 2320 } 2321 if (old_PA_IN) 2322 bitmap_set_free (old_PA_IN); 2323 if (PA_OUT) 2324 bitmap_set_free (PA_OUT); 2325 } 2326 2327 /* Compute ANTIC and partial ANTIC sets. */ 2328 2329 static void 2330 compute_antic (void) 2331 { 2332 bool changed = true; 2333 int num_iterations = 0; 2334 basic_block block; 2335 int i; 2336 edge_iterator ei; 2337 edge e; 2338 2339 /* If any predecessor edges are abnormal, we punt, so antic_in is empty. 2340 We pre-build the map of blocks with incoming abnormal edges here. */ 2341 has_abnormal_preds = sbitmap_alloc (last_basic_block_for_fn (cfun)); 2342 bitmap_clear (has_abnormal_preds); 2343 2344 FOR_ALL_BB_FN (block, cfun) 2345 { 2346 BB_VISITED (block) = 0; 2347 2348 FOR_EACH_EDGE (e, ei, block->preds) 2349 if (e->flags & EDGE_ABNORMAL) 2350 { 2351 bitmap_set_bit (has_abnormal_preds, block->index); 2352 break; 2353 } 2354 2355 /* While we are here, give empty ANTIC_IN sets to each block. */ 2356 ANTIC_IN (block) = bitmap_set_new (); 2357 if (do_partial_partial) 2358 PA_IN (block) = bitmap_set_new (); 2359 } 2360 2361 /* At the exit block we anticipate nothing. */ 2362 BB_VISITED (EXIT_BLOCK_PTR_FOR_FN (cfun)) = 1; 2363 2364 /* For ANTIC computation we need a postorder that also guarantees that 2365 a block with a single successor is visited after its successor. 2366 RPO on the inverted CFG has this property. */ 2367 auto_vec<int, 20> postorder; 2368 inverted_post_order_compute (&postorder); 2369 2370 auto_sbitmap worklist (last_basic_block_for_fn (cfun) + 1); 2371 bitmap_clear (worklist); 2372 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds) 2373 bitmap_set_bit (worklist, e->src->index); 2374 while (changed) 2375 { 2376 if (dump_file && (dump_flags & TDF_DETAILS)) 2377 fprintf (dump_file, "Starting iteration %d\n", num_iterations); 2378 /* ??? We need to clear our PHI translation cache here as the 2379 ANTIC sets shrink and we restrict valid translations to 2380 those having operands with leaders in ANTIC. Same below 2381 for PA ANTIC computation. */ 2382 num_iterations++; 2383 changed = false; 2384 for (i = postorder.length () - 1; i >= 0; i--) 2385 { 2386 if (bitmap_bit_p (worklist, postorder[i])) 2387 { 2388 basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]); 2389 bitmap_clear_bit (worklist, block->index); 2390 if (compute_antic_aux (block, 2391 bitmap_bit_p (has_abnormal_preds, 2392 block->index))) 2393 { 2394 FOR_EACH_EDGE (e, ei, block->preds) 2395 bitmap_set_bit (worklist, e->src->index); 2396 changed = true; 2397 } 2398 } 2399 } 2400 /* Theoretically possible, but *highly* unlikely. */ 2401 gcc_checking_assert (num_iterations < 500); 2402 } 2403 2404 /* We have to clean after the dataflow problem converged as cleaning 2405 can cause non-convergence because it is based on expressions 2406 rather than values. */ 2407 FOR_EACH_BB_FN (block, cfun) 2408 clean (ANTIC_IN (block)); 2409 2410 statistics_histogram_event (cfun, "compute_antic iterations", 2411 num_iterations); 2412 2413 if (do_partial_partial) 2414 { 2415 /* For partial antic we ignore backedges and thus we do not need 2416 to perform any iteration when we process blocks in postorder. */ 2417 int postorder_num 2418 = pre_and_rev_post_order_compute (NULL, postorder.address (), false); 2419 for (i = postorder_num - 1 ; i >= 0; i--) 2420 { 2421 basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]); 2422 compute_partial_antic_aux (block, 2423 bitmap_bit_p (has_abnormal_preds, 2424 block->index)); 2425 } 2426 } 2427 2428 sbitmap_free (has_abnormal_preds); 2429 } 2430 2431 2432 /* Inserted expressions are placed onto this worklist, which is used 2433 for performing quick dead code elimination of insertions we made 2434 that didn't turn out to be necessary. */ 2435 static bitmap inserted_exprs; 2436 2437 /* The actual worker for create_component_ref_by_pieces. */ 2438 2439 static tree 2440 create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref, 2441 unsigned int *operand, gimple_seq *stmts) 2442 { 2443 vn_reference_op_t currop = &ref->operands[*operand]; 2444 tree genop; 2445 ++*operand; 2446 switch (currop->opcode) 2447 { 2448 case CALL_EXPR: 2449 gcc_unreachable (); 2450 2451 case MEM_REF: 2452 { 2453 tree baseop = create_component_ref_by_pieces_1 (block, ref, operand, 2454 stmts); 2455 if (!baseop) 2456 return NULL_TREE; 2457 tree offset = currop->op0; 2458 if (TREE_CODE (baseop) == ADDR_EXPR 2459 && handled_component_p (TREE_OPERAND (baseop, 0))) 2460 { 2461 poly_int64 off; 2462 tree base; 2463 base = get_addr_base_and_unit_offset (TREE_OPERAND (baseop, 0), 2464 &off); 2465 gcc_assert (base); 2466 offset = int_const_binop (PLUS_EXPR, offset, 2467 build_int_cst (TREE_TYPE (offset), 2468 off)); 2469 baseop = build_fold_addr_expr (base); 2470 } 2471 genop = build2 (MEM_REF, currop->type, baseop, offset); 2472 MR_DEPENDENCE_CLIQUE (genop) = currop->clique; 2473 MR_DEPENDENCE_BASE (genop) = currop->base; 2474 REF_REVERSE_STORAGE_ORDER (genop) = currop->reverse; 2475 return genop; 2476 } 2477 2478 case TARGET_MEM_REF: 2479 { 2480 tree genop0 = NULL_TREE, genop1 = NULL_TREE; 2481 vn_reference_op_t nextop = &ref->operands[++*operand]; 2482 tree baseop = create_component_ref_by_pieces_1 (block, ref, operand, 2483 stmts); 2484 if (!baseop) 2485 return NULL_TREE; 2486 if (currop->op0) 2487 { 2488 genop0 = find_or_generate_expression (block, currop->op0, stmts); 2489 if (!genop0) 2490 return NULL_TREE; 2491 } 2492 if (nextop->op0) 2493 { 2494 genop1 = find_or_generate_expression (block, nextop->op0, stmts); 2495 if (!genop1) 2496 return NULL_TREE; 2497 } 2498 genop = build5 (TARGET_MEM_REF, currop->type, 2499 baseop, currop->op2, genop0, currop->op1, genop1); 2500 2501 MR_DEPENDENCE_CLIQUE (genop) = currop->clique; 2502 MR_DEPENDENCE_BASE (genop) = currop->base; 2503 return genop; 2504 } 2505 2506 case ADDR_EXPR: 2507 if (currop->op0) 2508 { 2509 gcc_assert (is_gimple_min_invariant (currop->op0)); 2510 return currop->op0; 2511 } 2512 /* Fallthrough. */ 2513 case REALPART_EXPR: 2514 case IMAGPART_EXPR: 2515 case VIEW_CONVERT_EXPR: 2516 { 2517 tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand, 2518 stmts); 2519 if (!genop0) 2520 return NULL_TREE; 2521 return fold_build1 (currop->opcode, currop->type, genop0); 2522 } 2523 2524 case WITH_SIZE_EXPR: 2525 { 2526 tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand, 2527 stmts); 2528 if (!genop0) 2529 return NULL_TREE; 2530 tree genop1 = find_or_generate_expression (block, currop->op0, stmts); 2531 if (!genop1) 2532 return NULL_TREE; 2533 return fold_build2 (currop->opcode, currop->type, genop0, genop1); 2534 } 2535 2536 case BIT_FIELD_REF: 2537 { 2538 tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand, 2539 stmts); 2540 if (!genop0) 2541 return NULL_TREE; 2542 tree op1 = currop->op0; 2543 tree op2 = currop->op1; 2544 tree t = build3 (BIT_FIELD_REF, currop->type, genop0, op1, op2); 2545 REF_REVERSE_STORAGE_ORDER (t) = currop->reverse; 2546 return fold (t); 2547 } 2548 2549 /* For array ref vn_reference_op's, operand 1 of the array ref 2550 is op0 of the reference op and operand 3 of the array ref is 2551 op1. */ 2552 case ARRAY_RANGE_REF: 2553 case ARRAY_REF: 2554 { 2555 tree genop0; 2556 tree genop1 = currop->op0; 2557 tree genop2 = currop->op1; 2558 tree genop3 = currop->op2; 2559 genop0 = create_component_ref_by_pieces_1 (block, ref, operand, 2560 stmts); 2561 if (!genop0) 2562 return NULL_TREE; 2563 genop1 = find_or_generate_expression (block, genop1, stmts); 2564 if (!genop1) 2565 return NULL_TREE; 2566 if (genop2) 2567 { 2568 tree domain_type = TYPE_DOMAIN (TREE_TYPE (genop0)); 2569 /* Drop zero minimum index if redundant. */ 2570 if (integer_zerop (genop2) 2571 && (!domain_type 2572 || integer_zerop (TYPE_MIN_VALUE (domain_type)))) 2573 genop2 = NULL_TREE; 2574 else 2575 { 2576 genop2 = find_or_generate_expression (block, genop2, stmts); 2577 if (!genop2) 2578 return NULL_TREE; 2579 } 2580 } 2581 if (genop3) 2582 { 2583 tree elmt_type = TREE_TYPE (TREE_TYPE (genop0)); 2584 /* We can't always put a size in units of the element alignment 2585 here as the element alignment may be not visible. See 2586 PR43783. Simply drop the element size for constant 2587 sizes. */ 2588 if (TREE_CODE (genop3) == INTEGER_CST 2589 && TREE_CODE (TYPE_SIZE_UNIT (elmt_type)) == INTEGER_CST 2590 && wi::eq_p (wi::to_offset (TYPE_SIZE_UNIT (elmt_type)), 2591 (wi::to_offset (genop3) 2592 * vn_ref_op_align_unit (currop)))) 2593 genop3 = NULL_TREE; 2594 else 2595 { 2596 genop3 = find_or_generate_expression (block, genop3, stmts); 2597 if (!genop3) 2598 return NULL_TREE; 2599 } 2600 } 2601 return build4 (currop->opcode, currop->type, genop0, genop1, 2602 genop2, genop3); 2603 } 2604 case COMPONENT_REF: 2605 { 2606 tree op0; 2607 tree op1; 2608 tree genop2 = currop->op1; 2609 op0 = create_component_ref_by_pieces_1 (block, ref, operand, stmts); 2610 if (!op0) 2611 return NULL_TREE; 2612 /* op1 should be a FIELD_DECL, which are represented by themselves. */ 2613 op1 = currop->op0; 2614 if (genop2) 2615 { 2616 genop2 = find_or_generate_expression (block, genop2, stmts); 2617 if (!genop2) 2618 return NULL_TREE; 2619 } 2620 return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1, genop2); 2621 } 2622 2623 case SSA_NAME: 2624 { 2625 genop = find_or_generate_expression (block, currop->op0, stmts); 2626 return genop; 2627 } 2628 case STRING_CST: 2629 case INTEGER_CST: 2630 case COMPLEX_CST: 2631 case VECTOR_CST: 2632 case REAL_CST: 2633 case CONSTRUCTOR: 2634 case VAR_DECL: 2635 case PARM_DECL: 2636 case CONST_DECL: 2637 case RESULT_DECL: 2638 case FUNCTION_DECL: 2639 return currop->op0; 2640 2641 default: 2642 gcc_unreachable (); 2643 } 2644 } 2645 2646 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the 2647 COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with 2648 trying to rename aggregates into ssa form directly, which is a no no. 2649 2650 Thus, this routine doesn't create temporaries, it just builds a 2651 single access expression for the array, calling 2652 find_or_generate_expression to build the innermost pieces. 2653 2654 This function is a subroutine of create_expression_by_pieces, and 2655 should not be called on it's own unless you really know what you 2656 are doing. */ 2657 2658 static tree 2659 create_component_ref_by_pieces (basic_block block, vn_reference_t ref, 2660 gimple_seq *stmts) 2661 { 2662 unsigned int op = 0; 2663 return create_component_ref_by_pieces_1 (block, ref, &op, stmts); 2664 } 2665 2666 /* Find a simple leader for an expression, or generate one using 2667 create_expression_by_pieces from a NARY expression for the value. 2668 BLOCK is the basic_block we are looking for leaders in. 2669 OP is the tree expression to find a leader for or generate. 2670 Returns the leader or NULL_TREE on failure. */ 2671 2672 static tree 2673 find_or_generate_expression (basic_block block, tree op, gimple_seq *stmts) 2674 { 2675 pre_expr expr = get_or_alloc_expr_for (op); 2676 unsigned int lookfor = get_expr_value_id (expr); 2677 pre_expr leader = bitmap_find_leader (AVAIL_OUT (block), lookfor); 2678 if (leader) 2679 { 2680 if (leader->kind == NAME) 2681 return PRE_EXPR_NAME (leader); 2682 else if (leader->kind == CONSTANT) 2683 return PRE_EXPR_CONSTANT (leader); 2684 2685 /* Defer. */ 2686 return NULL_TREE; 2687 } 2688 2689 /* It must be a complex expression, so generate it recursively. Note 2690 that this is only necessary to handle gcc.dg/tree-ssa/ssa-pre28.c 2691 where the insert algorithm fails to insert a required expression. */ 2692 bitmap exprset = value_expressions[lookfor]; 2693 bitmap_iterator bi; 2694 unsigned int i; 2695 EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi) 2696 { 2697 pre_expr temp = expression_for_id (i); 2698 /* We cannot insert random REFERENCE expressions at arbitrary 2699 places. We can insert NARYs which eventually re-materializes 2700 its operand values. */ 2701 if (temp->kind == NARY) 2702 return create_expression_by_pieces (block, temp, stmts, 2703 get_expr_type (expr)); 2704 } 2705 2706 /* Defer. */ 2707 return NULL_TREE; 2708 } 2709 2710 /* Create an expression in pieces, so that we can handle very complex 2711 expressions that may be ANTIC, but not necessary GIMPLE. 2712 BLOCK is the basic block the expression will be inserted into, 2713 EXPR is the expression to insert (in value form) 2714 STMTS is a statement list to append the necessary insertions into. 2715 2716 This function will die if we hit some value that shouldn't be 2717 ANTIC but is (IE there is no leader for it, or its components). 2718 The function returns NULL_TREE in case a different antic expression 2719 has to be inserted first. 2720 This function may also generate expressions that are themselves 2721 partially or fully redundant. Those that are will be either made 2722 fully redundant during the next iteration of insert (for partially 2723 redundant ones), or eliminated by eliminate (for fully redundant 2724 ones). */ 2725 2726 static tree 2727 create_expression_by_pieces (basic_block block, pre_expr expr, 2728 gimple_seq *stmts, tree type) 2729 { 2730 tree name; 2731 tree folded; 2732 gimple_seq forced_stmts = NULL; 2733 unsigned int value_id; 2734 gimple_stmt_iterator gsi; 2735 tree exprtype = type ? type : get_expr_type (expr); 2736 pre_expr nameexpr; 2737 gassign *newstmt; 2738 2739 switch (expr->kind) 2740 { 2741 /* We may hit the NAME/CONSTANT case if we have to convert types 2742 that value numbering saw through. */ 2743 case NAME: 2744 folded = PRE_EXPR_NAME (expr); 2745 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (folded)) 2746 return NULL_TREE; 2747 if (useless_type_conversion_p (exprtype, TREE_TYPE (folded))) 2748 return folded; 2749 break; 2750 case CONSTANT: 2751 { 2752 folded = PRE_EXPR_CONSTANT (expr); 2753 tree tem = fold_convert (exprtype, folded); 2754 if (is_gimple_min_invariant (tem)) 2755 return tem; 2756 break; 2757 } 2758 case REFERENCE: 2759 if (PRE_EXPR_REFERENCE (expr)->operands[0].opcode == CALL_EXPR) 2760 { 2761 vn_reference_t ref = PRE_EXPR_REFERENCE (expr); 2762 unsigned int operand = 1; 2763 vn_reference_op_t currop = &ref->operands[0]; 2764 tree sc = NULL_TREE; 2765 tree fn = find_or_generate_expression (block, currop->op0, stmts); 2766 if (!fn) 2767 return NULL_TREE; 2768 if (currop->op1) 2769 { 2770 sc = find_or_generate_expression (block, currop->op1, stmts); 2771 if (!sc) 2772 return NULL_TREE; 2773 } 2774 auto_vec<tree> args (ref->operands.length () - 1); 2775 while (operand < ref->operands.length ()) 2776 { 2777 tree arg = create_component_ref_by_pieces_1 (block, ref, 2778 &operand, stmts); 2779 if (!arg) 2780 return NULL_TREE; 2781 args.quick_push (arg); 2782 } 2783 gcall *call = gimple_build_call_vec (fn, args); 2784 gimple_call_set_with_bounds (call, currop->with_bounds); 2785 if (sc) 2786 gimple_call_set_chain (call, sc); 2787 tree forcedname = make_ssa_name (currop->type); 2788 gimple_call_set_lhs (call, forcedname); 2789 /* There's no CCP pass after PRE which would re-compute alignment 2790 information so make sure we re-materialize this here. */ 2791 if (gimple_call_builtin_p (call, BUILT_IN_ASSUME_ALIGNED) 2792 && args.length () - 2 <= 1 2793 && tree_fits_uhwi_p (args[1]) 2794 && (args.length () != 3 || tree_fits_uhwi_p (args[2]))) 2795 { 2796 unsigned HOST_WIDE_INT halign = tree_to_uhwi (args[1]); 2797 unsigned HOST_WIDE_INT hmisalign 2798 = args.length () == 3 ? tree_to_uhwi (args[2]) : 0; 2799 if ((halign & (halign - 1)) == 0 2800 && (hmisalign & ~(halign - 1)) == 0) 2801 set_ptr_info_alignment (get_ptr_info (forcedname), 2802 halign, hmisalign); 2803 } 2804 gimple_set_vuse (call, BB_LIVE_VOP_ON_EXIT (block)); 2805 gimple_seq_add_stmt_without_update (&forced_stmts, call); 2806 folded = forcedname; 2807 } 2808 else 2809 { 2810 folded = create_component_ref_by_pieces (block, 2811 PRE_EXPR_REFERENCE (expr), 2812 stmts); 2813 if (!folded) 2814 return NULL_TREE; 2815 name = make_temp_ssa_name (exprtype, NULL, "pretmp"); 2816 newstmt = gimple_build_assign (name, folded); 2817 gimple_seq_add_stmt_without_update (&forced_stmts, newstmt); 2818 gimple_set_vuse (newstmt, BB_LIVE_VOP_ON_EXIT (block)); 2819 folded = name; 2820 } 2821 break; 2822 case NARY: 2823 { 2824 vn_nary_op_t nary = PRE_EXPR_NARY (expr); 2825 tree *genop = XALLOCAVEC (tree, nary->length); 2826 unsigned i; 2827 for (i = 0; i < nary->length; ++i) 2828 { 2829 genop[i] = find_or_generate_expression (block, nary->op[i], stmts); 2830 if (!genop[i]) 2831 return NULL_TREE; 2832 /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR. It 2833 may have conversions stripped. */ 2834 if (nary->opcode == POINTER_PLUS_EXPR) 2835 { 2836 if (i == 0) 2837 genop[i] = gimple_convert (&forced_stmts, 2838 nary->type, genop[i]); 2839 else if (i == 1) 2840 genop[i] = gimple_convert (&forced_stmts, 2841 sizetype, genop[i]); 2842 } 2843 else 2844 genop[i] = gimple_convert (&forced_stmts, 2845 TREE_TYPE (nary->op[i]), genop[i]); 2846 } 2847 if (nary->opcode == CONSTRUCTOR) 2848 { 2849 vec<constructor_elt, va_gc> *elts = NULL; 2850 for (i = 0; i < nary->length; ++i) 2851 CONSTRUCTOR_APPEND_ELT (elts, NULL_TREE, genop[i]); 2852 folded = build_constructor (nary->type, elts); 2853 name = make_temp_ssa_name (exprtype, NULL, "pretmp"); 2854 newstmt = gimple_build_assign (name, folded); 2855 gimple_seq_add_stmt_without_update (&forced_stmts, newstmt); 2856 folded = name; 2857 } 2858 else 2859 { 2860 switch (nary->length) 2861 { 2862 case 1: 2863 folded = gimple_build (&forced_stmts, nary->opcode, nary->type, 2864 genop[0]); 2865 break; 2866 case 2: 2867 folded = gimple_build (&forced_stmts, nary->opcode, nary->type, 2868 genop[0], genop[1]); 2869 break; 2870 case 3: 2871 folded = gimple_build (&forced_stmts, nary->opcode, nary->type, 2872 genop[0], genop[1], genop[2]); 2873 break; 2874 default: 2875 gcc_unreachable (); 2876 } 2877 } 2878 } 2879 break; 2880 default: 2881 gcc_unreachable (); 2882 } 2883 2884 folded = gimple_convert (&forced_stmts, exprtype, folded); 2885 2886 /* If there is nothing to insert, return the simplified result. */ 2887 if (gimple_seq_empty_p (forced_stmts)) 2888 return folded; 2889 /* If we simplified to a constant return it and discard eventually 2890 built stmts. */ 2891 if (is_gimple_min_invariant (folded)) 2892 { 2893 gimple_seq_discard (forced_stmts); 2894 return folded; 2895 } 2896 /* Likewise if we simplified to sth not queued for insertion. */ 2897 bool found = false; 2898 gsi = gsi_last (forced_stmts); 2899 for (; !gsi_end_p (gsi); gsi_prev (&gsi)) 2900 { 2901 gimple *stmt = gsi_stmt (gsi); 2902 tree forcedname = gimple_get_lhs (stmt); 2903 if (forcedname == folded) 2904 { 2905 found = true; 2906 break; 2907 } 2908 } 2909 if (! found) 2910 { 2911 gimple_seq_discard (forced_stmts); 2912 return folded; 2913 } 2914 gcc_assert (TREE_CODE (folded) == SSA_NAME); 2915 2916 /* If we have any intermediate expressions to the value sets, add them 2917 to the value sets and chain them in the instruction stream. */ 2918 if (forced_stmts) 2919 { 2920 gsi = gsi_start (forced_stmts); 2921 for (; !gsi_end_p (gsi); gsi_next (&gsi)) 2922 { 2923 gimple *stmt = gsi_stmt (gsi); 2924 tree forcedname = gimple_get_lhs (stmt); 2925 pre_expr nameexpr; 2926 2927 if (forcedname != folded) 2928 { 2929 VN_INFO_GET (forcedname)->valnum = forcedname; 2930 VN_INFO (forcedname)->value_id = get_next_value_id (); 2931 nameexpr = get_or_alloc_expr_for_name (forcedname); 2932 add_to_value (VN_INFO (forcedname)->value_id, nameexpr); 2933 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr); 2934 bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr); 2935 } 2936 2937 bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname)); 2938 } 2939 gimple_seq_add_seq (stmts, forced_stmts); 2940 } 2941 2942 name = folded; 2943 2944 /* Fold the last statement. */ 2945 gsi = gsi_last (*stmts); 2946 if (fold_stmt_inplace (&gsi)) 2947 update_stmt (gsi_stmt (gsi)); 2948 2949 /* Add a value number to the temporary. 2950 The value may already exist in either NEW_SETS, or AVAIL_OUT, because 2951 we are creating the expression by pieces, and this particular piece of 2952 the expression may have been represented. There is no harm in replacing 2953 here. */ 2954 value_id = get_expr_value_id (expr); 2955 VN_INFO_GET (name)->value_id = value_id; 2956 VN_INFO (name)->valnum = sccvn_valnum_from_value_id (value_id); 2957 if (VN_INFO (name)->valnum == NULL_TREE) 2958 VN_INFO (name)->valnum = name; 2959 gcc_assert (VN_INFO (name)->valnum != NULL_TREE); 2960 nameexpr = get_or_alloc_expr_for_name (name); 2961 add_to_value (value_id, nameexpr); 2962 if (NEW_SETS (block)) 2963 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr); 2964 bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr); 2965 2966 pre_stats.insertions++; 2967 if (dump_file && (dump_flags & TDF_DETAILS)) 2968 { 2969 fprintf (dump_file, "Inserted "); 2970 print_gimple_stmt (dump_file, gsi_stmt (gsi_last (*stmts)), 0); 2971 fprintf (dump_file, " in predecessor %d (%04d)\n", 2972 block->index, value_id); 2973 } 2974 2975 return name; 2976 } 2977 2978 2979 /* Insert the to-be-made-available values of expression EXPRNUM for each 2980 predecessor, stored in AVAIL, into the predecessors of BLOCK, and 2981 merge the result with a phi node, given the same value number as 2982 NODE. Return true if we have inserted new stuff. */ 2983 2984 static bool 2985 insert_into_preds_of_block (basic_block block, unsigned int exprnum, 2986 vec<pre_expr> avail) 2987 { 2988 pre_expr expr = expression_for_id (exprnum); 2989 pre_expr newphi; 2990 unsigned int val = get_expr_value_id (expr); 2991 edge pred; 2992 bool insertions = false; 2993 bool nophi = false; 2994 basic_block bprime; 2995 pre_expr eprime; 2996 edge_iterator ei; 2997 tree type = get_expr_type (expr); 2998 tree temp; 2999 gphi *phi; 3000 3001 /* Make sure we aren't creating an induction variable. */ 3002 if (bb_loop_depth (block) > 0 && EDGE_COUNT (block->preds) == 2) 3003 { 3004 bool firstinsideloop = false; 3005 bool secondinsideloop = false; 3006 firstinsideloop = flow_bb_inside_loop_p (block->loop_father, 3007 EDGE_PRED (block, 0)->src); 3008 secondinsideloop = flow_bb_inside_loop_p (block->loop_father, 3009 EDGE_PRED (block, 1)->src); 3010 /* Induction variables only have one edge inside the loop. */ 3011 if ((firstinsideloop ^ secondinsideloop) 3012 && expr->kind != REFERENCE) 3013 { 3014 if (dump_file && (dump_flags & TDF_DETAILS)) 3015 fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n"); 3016 nophi = true; 3017 } 3018 } 3019 3020 /* Make the necessary insertions. */ 3021 FOR_EACH_EDGE (pred, ei, block->preds) 3022 { 3023 gimple_seq stmts = NULL; 3024 tree builtexpr; 3025 bprime = pred->src; 3026 eprime = avail[pred->dest_idx]; 3027 builtexpr = create_expression_by_pieces (bprime, eprime, 3028 &stmts, type); 3029 gcc_assert (!(pred->flags & EDGE_ABNORMAL)); 3030 if (!gimple_seq_empty_p (stmts)) 3031 { 3032 basic_block new_bb = gsi_insert_seq_on_edge_immediate (pred, stmts); 3033 gcc_assert (! new_bb); 3034 insertions = true; 3035 } 3036 if (!builtexpr) 3037 { 3038 /* We cannot insert a PHI node if we failed to insert 3039 on one edge. */ 3040 nophi = true; 3041 continue; 3042 } 3043 if (is_gimple_min_invariant (builtexpr)) 3044 avail[pred->dest_idx] = get_or_alloc_expr_for_constant (builtexpr); 3045 else 3046 avail[pred->dest_idx] = get_or_alloc_expr_for_name (builtexpr); 3047 } 3048 /* If we didn't want a phi node, and we made insertions, we still have 3049 inserted new stuff, and thus return true. If we didn't want a phi node, 3050 and didn't make insertions, we haven't added anything new, so return 3051 false. */ 3052 if (nophi && insertions) 3053 return true; 3054 else if (nophi && !insertions) 3055 return false; 3056 3057 /* Now build a phi for the new variable. */ 3058 temp = make_temp_ssa_name (type, NULL, "prephitmp"); 3059 phi = create_phi_node (temp, block); 3060 3061 VN_INFO_GET (temp)->value_id = val; 3062 VN_INFO (temp)->valnum = sccvn_valnum_from_value_id (val); 3063 if (VN_INFO (temp)->valnum == NULL_TREE) 3064 VN_INFO (temp)->valnum = temp; 3065 bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp)); 3066 FOR_EACH_EDGE (pred, ei, block->preds) 3067 { 3068 pre_expr ae = avail[pred->dest_idx]; 3069 gcc_assert (get_expr_type (ae) == type 3070 || useless_type_conversion_p (type, get_expr_type (ae))); 3071 if (ae->kind == CONSTANT) 3072 add_phi_arg (phi, unshare_expr (PRE_EXPR_CONSTANT (ae)), 3073 pred, UNKNOWN_LOCATION); 3074 else 3075 add_phi_arg (phi, PRE_EXPR_NAME (ae), pred, UNKNOWN_LOCATION); 3076 } 3077 3078 newphi = get_or_alloc_expr_for_name (temp); 3079 add_to_value (val, newphi); 3080 3081 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing 3082 this insertion, since we test for the existence of this value in PHI_GEN 3083 before proceeding with the partial redundancy checks in insert_aux. 3084 3085 The value may exist in AVAIL_OUT, in particular, it could be represented 3086 by the expression we are trying to eliminate, in which case we want the 3087 replacement to occur. If it's not existing in AVAIL_OUT, we want it 3088 inserted there. 3089 3090 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of 3091 this block, because if it did, it would have existed in our dominator's 3092 AVAIL_OUT, and would have been skipped due to the full redundancy check. 3093 */ 3094 3095 bitmap_insert_into_set (PHI_GEN (block), newphi); 3096 bitmap_value_replace_in_set (AVAIL_OUT (block), 3097 newphi); 3098 bitmap_insert_into_set (NEW_SETS (block), 3099 newphi); 3100 3101 /* If we insert a PHI node for a conversion of another PHI node 3102 in the same basic-block try to preserve range information. 3103 This is important so that followup loop passes receive optimal 3104 number of iteration analysis results. See PR61743. */ 3105 if (expr->kind == NARY 3106 && CONVERT_EXPR_CODE_P (expr->u.nary->opcode) 3107 && TREE_CODE (expr->u.nary->op[0]) == SSA_NAME 3108 && gimple_bb (SSA_NAME_DEF_STMT (expr->u.nary->op[0])) == block 3109 && INTEGRAL_TYPE_P (type) 3110 && INTEGRAL_TYPE_P (TREE_TYPE (expr->u.nary->op[0])) 3111 && (TYPE_PRECISION (type) 3112 >= TYPE_PRECISION (TREE_TYPE (expr->u.nary->op[0]))) 3113 && SSA_NAME_RANGE_INFO (expr->u.nary->op[0])) 3114 { 3115 wide_int min, max; 3116 if (get_range_info (expr->u.nary->op[0], &min, &max) == VR_RANGE 3117 && !wi::neg_p (min, SIGNED) 3118 && !wi::neg_p (max, SIGNED)) 3119 /* Just handle extension and sign-changes of all-positive ranges. */ 3120 set_range_info (temp, 3121 SSA_NAME_RANGE_TYPE (expr->u.nary->op[0]), 3122 wide_int_storage::from (min, TYPE_PRECISION (type), 3123 TYPE_SIGN (type)), 3124 wide_int_storage::from (max, TYPE_PRECISION (type), 3125 TYPE_SIGN (type))); 3126 } 3127 3128 if (dump_file && (dump_flags & TDF_DETAILS)) 3129 { 3130 fprintf (dump_file, "Created phi "); 3131 print_gimple_stmt (dump_file, phi, 0); 3132 fprintf (dump_file, " in block %d (%04d)\n", block->index, val); 3133 } 3134 pre_stats.phis++; 3135 return true; 3136 } 3137 3138 3139 3140 /* Perform insertion of partially redundant or hoistable values. 3141 For BLOCK, do the following: 3142 1. Propagate the NEW_SETS of the dominator into the current block. 3143 If the block has multiple predecessors, 3144 2a. Iterate over the ANTIC expressions for the block to see if 3145 any of them are partially redundant. 3146 2b. If so, insert them into the necessary predecessors to make 3147 the expression fully redundant. 3148 2c. Insert a new PHI merging the values of the predecessors. 3149 2d. Insert the new PHI, and the new expressions, into the 3150 NEW_SETS set. 3151 If the block has multiple successors, 3152 3a. Iterate over the ANTIC values for the block to see if 3153 any of them are good candidates for hoisting. 3154 3b. If so, insert expressions computing the values in BLOCK, 3155 and add the new expressions into the NEW_SETS set. 3156 4. Recursively call ourselves on the dominator children of BLOCK. 3157 3158 Steps 1, 2a, and 4 are done by insert_aux. 2b, 2c and 2d are done by 3159 do_pre_regular_insertion and do_partial_insertion. 3a and 3b are 3160 done in do_hoist_insertion. 3161 */ 3162 3163 static bool 3164 do_pre_regular_insertion (basic_block block, basic_block dom) 3165 { 3166 bool new_stuff = false; 3167 vec<pre_expr> exprs; 3168 pre_expr expr; 3169 auto_vec<pre_expr> avail; 3170 int i; 3171 3172 exprs = sorted_array_from_bitmap_set (ANTIC_IN (block)); 3173 avail.safe_grow (EDGE_COUNT (block->preds)); 3174 3175 FOR_EACH_VEC_ELT (exprs, i, expr) 3176 { 3177 if (expr->kind == NARY 3178 || expr->kind == REFERENCE) 3179 { 3180 unsigned int val; 3181 bool by_some = false; 3182 bool cant_insert = false; 3183 bool all_same = true; 3184 pre_expr first_s = NULL; 3185 edge pred; 3186 basic_block bprime; 3187 pre_expr eprime = NULL; 3188 edge_iterator ei; 3189 pre_expr edoubleprime = NULL; 3190 bool do_insertion = false; 3191 3192 val = get_expr_value_id (expr); 3193 if (bitmap_set_contains_value (PHI_GEN (block), val)) 3194 continue; 3195 if (bitmap_set_contains_value (AVAIL_OUT (dom), val)) 3196 { 3197 if (dump_file && (dump_flags & TDF_DETAILS)) 3198 { 3199 fprintf (dump_file, "Found fully redundant value: "); 3200 print_pre_expr (dump_file, expr); 3201 fprintf (dump_file, "\n"); 3202 } 3203 continue; 3204 } 3205 3206 FOR_EACH_EDGE (pred, ei, block->preds) 3207 { 3208 unsigned int vprime; 3209 3210 /* We should never run insertion for the exit block 3211 and so not come across fake pred edges. */ 3212 gcc_assert (!(pred->flags & EDGE_FAKE)); 3213 bprime = pred->src; 3214 /* We are looking at ANTIC_OUT of bprime. */ 3215 eprime = phi_translate (NULL, expr, ANTIC_IN (block), NULL, pred); 3216 3217 /* eprime will generally only be NULL if the 3218 value of the expression, translated 3219 through the PHI for this predecessor, is 3220 undefined. If that is the case, we can't 3221 make the expression fully redundant, 3222 because its value is undefined along a 3223 predecessor path. We can thus break out 3224 early because it doesn't matter what the 3225 rest of the results are. */ 3226 if (eprime == NULL) 3227 { 3228 avail[pred->dest_idx] = NULL; 3229 cant_insert = true; 3230 break; 3231 } 3232 3233 vprime = get_expr_value_id (eprime); 3234 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), 3235 vprime); 3236 if (edoubleprime == NULL) 3237 { 3238 avail[pred->dest_idx] = eprime; 3239 all_same = false; 3240 } 3241 else 3242 { 3243 avail[pred->dest_idx] = edoubleprime; 3244 by_some = true; 3245 /* We want to perform insertions to remove a redundancy on 3246 a path in the CFG we want to optimize for speed. */ 3247 if (optimize_edge_for_speed_p (pred)) 3248 do_insertion = true; 3249 if (first_s == NULL) 3250 first_s = edoubleprime; 3251 else if (!pre_expr_d::equal (first_s, edoubleprime)) 3252 all_same = false; 3253 } 3254 } 3255 /* If we can insert it, it's not the same value 3256 already existing along every predecessor, and 3257 it's defined by some predecessor, it is 3258 partially redundant. */ 3259 if (!cant_insert && !all_same && by_some) 3260 { 3261 if (!do_insertion) 3262 { 3263 if (dump_file && (dump_flags & TDF_DETAILS)) 3264 { 3265 fprintf (dump_file, "Skipping partial redundancy for " 3266 "expression "); 3267 print_pre_expr (dump_file, expr); 3268 fprintf (dump_file, " (%04d), no redundancy on to be " 3269 "optimized for speed edge\n", val); 3270 } 3271 } 3272 else if (dbg_cnt (treepre_insert)) 3273 { 3274 if (dump_file && (dump_flags & TDF_DETAILS)) 3275 { 3276 fprintf (dump_file, "Found partial redundancy for " 3277 "expression "); 3278 print_pre_expr (dump_file, expr); 3279 fprintf (dump_file, " (%04d)\n", 3280 get_expr_value_id (expr)); 3281 } 3282 if (insert_into_preds_of_block (block, 3283 get_expression_id (expr), 3284 avail)) 3285 new_stuff = true; 3286 } 3287 } 3288 /* If all edges produce the same value and that value is 3289 an invariant, then the PHI has the same value on all 3290 edges. Note this. */ 3291 else if (!cant_insert && all_same) 3292 { 3293 gcc_assert (edoubleprime->kind == CONSTANT 3294 || edoubleprime->kind == NAME); 3295 3296 tree temp = make_temp_ssa_name (get_expr_type (expr), 3297 NULL, "pretmp"); 3298 gassign *assign 3299 = gimple_build_assign (temp, 3300 edoubleprime->kind == CONSTANT ? 3301 PRE_EXPR_CONSTANT (edoubleprime) : 3302 PRE_EXPR_NAME (edoubleprime)); 3303 gimple_stmt_iterator gsi = gsi_after_labels (block); 3304 gsi_insert_before (&gsi, assign, GSI_NEW_STMT); 3305 3306 VN_INFO_GET (temp)->value_id = val; 3307 VN_INFO (temp)->valnum = sccvn_valnum_from_value_id (val); 3308 if (VN_INFO (temp)->valnum == NULL_TREE) 3309 VN_INFO (temp)->valnum = temp; 3310 bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp)); 3311 pre_expr newe = get_or_alloc_expr_for_name (temp); 3312 add_to_value (val, newe); 3313 bitmap_value_replace_in_set (AVAIL_OUT (block), newe); 3314 bitmap_insert_into_set (NEW_SETS (block), newe); 3315 } 3316 } 3317 } 3318 3319 exprs.release (); 3320 return new_stuff; 3321 } 3322 3323 3324 /* Perform insertion for partially anticipatable expressions. There 3325 is only one case we will perform insertion for these. This case is 3326 if the expression is partially anticipatable, and fully available. 3327 In this case, we know that putting it earlier will enable us to 3328 remove the later computation. */ 3329 3330 static bool 3331 do_pre_partial_partial_insertion (basic_block block, basic_block dom) 3332 { 3333 bool new_stuff = false; 3334 vec<pre_expr> exprs; 3335 pre_expr expr; 3336 auto_vec<pre_expr> avail; 3337 int i; 3338 3339 exprs = sorted_array_from_bitmap_set (PA_IN (block)); 3340 avail.safe_grow (EDGE_COUNT (block->preds)); 3341 3342 FOR_EACH_VEC_ELT (exprs, i, expr) 3343 { 3344 if (expr->kind == NARY 3345 || expr->kind == REFERENCE) 3346 { 3347 unsigned int val; 3348 bool by_all = true; 3349 bool cant_insert = false; 3350 edge pred; 3351 basic_block bprime; 3352 pre_expr eprime = NULL; 3353 edge_iterator ei; 3354 3355 val = get_expr_value_id (expr); 3356 if (bitmap_set_contains_value (PHI_GEN (block), val)) 3357 continue; 3358 if (bitmap_set_contains_value (AVAIL_OUT (dom), val)) 3359 continue; 3360 3361 FOR_EACH_EDGE (pred, ei, block->preds) 3362 { 3363 unsigned int vprime; 3364 pre_expr edoubleprime; 3365 3366 /* We should never run insertion for the exit block 3367 and so not come across fake pred edges. */ 3368 gcc_assert (!(pred->flags & EDGE_FAKE)); 3369 bprime = pred->src; 3370 eprime = phi_translate (NULL, expr, ANTIC_IN (block), 3371 PA_IN (block), pred); 3372 3373 /* eprime will generally only be NULL if the 3374 value of the expression, translated 3375 through the PHI for this predecessor, is 3376 undefined. If that is the case, we can't 3377 make the expression fully redundant, 3378 because its value is undefined along a 3379 predecessor path. We can thus break out 3380 early because it doesn't matter what the 3381 rest of the results are. */ 3382 if (eprime == NULL) 3383 { 3384 avail[pred->dest_idx] = NULL; 3385 cant_insert = true; 3386 break; 3387 } 3388 3389 vprime = get_expr_value_id (eprime); 3390 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), vprime); 3391 avail[pred->dest_idx] = edoubleprime; 3392 if (edoubleprime == NULL) 3393 { 3394 by_all = false; 3395 break; 3396 } 3397 } 3398 3399 /* If we can insert it, it's not the same value 3400 already existing along every predecessor, and 3401 it's defined by some predecessor, it is 3402 partially redundant. */ 3403 if (!cant_insert && by_all) 3404 { 3405 edge succ; 3406 bool do_insertion = false; 3407 3408 /* Insert only if we can remove a later expression on a path 3409 that we want to optimize for speed. 3410 The phi node that we will be inserting in BLOCK is not free, 3411 and inserting it for the sake of !optimize_for_speed successor 3412 may cause regressions on the speed path. */ 3413 FOR_EACH_EDGE (succ, ei, block->succs) 3414 { 3415 if (bitmap_set_contains_value (PA_IN (succ->dest), val) 3416 || bitmap_set_contains_value (ANTIC_IN (succ->dest), val)) 3417 { 3418 if (optimize_edge_for_speed_p (succ)) 3419 do_insertion = true; 3420 } 3421 } 3422 3423 if (!do_insertion) 3424 { 3425 if (dump_file && (dump_flags & TDF_DETAILS)) 3426 { 3427 fprintf (dump_file, "Skipping partial partial redundancy " 3428 "for expression "); 3429 print_pre_expr (dump_file, expr); 3430 fprintf (dump_file, " (%04d), not (partially) anticipated " 3431 "on any to be optimized for speed edges\n", val); 3432 } 3433 } 3434 else if (dbg_cnt (treepre_insert)) 3435 { 3436 pre_stats.pa_insert++; 3437 if (dump_file && (dump_flags & TDF_DETAILS)) 3438 { 3439 fprintf (dump_file, "Found partial partial redundancy " 3440 "for expression "); 3441 print_pre_expr (dump_file, expr); 3442 fprintf (dump_file, " (%04d)\n", 3443 get_expr_value_id (expr)); 3444 } 3445 if (insert_into_preds_of_block (block, 3446 get_expression_id (expr), 3447 avail)) 3448 new_stuff = true; 3449 } 3450 } 3451 } 3452 } 3453 3454 exprs.release (); 3455 return new_stuff; 3456 } 3457 3458 /* Insert expressions in BLOCK to compute hoistable values up. 3459 Return TRUE if something was inserted, otherwise return FALSE. 3460 The caller has to make sure that BLOCK has at least two successors. */ 3461 3462 static bool 3463 do_hoist_insertion (basic_block block) 3464 { 3465 edge e; 3466 edge_iterator ei; 3467 bool new_stuff = false; 3468 unsigned i; 3469 gimple_stmt_iterator last; 3470 3471 /* At least two successors, or else... */ 3472 gcc_assert (EDGE_COUNT (block->succs) >= 2); 3473 3474 /* Check that all successors of BLOCK are dominated by block. 3475 We could use dominated_by_p() for this, but actually there is a much 3476 quicker check: any successor that is dominated by BLOCK can't have 3477 more than one predecessor edge. */ 3478 FOR_EACH_EDGE (e, ei, block->succs) 3479 if (! single_pred_p (e->dest)) 3480 return false; 3481 3482 /* Determine the insertion point. If we cannot safely insert before 3483 the last stmt if we'd have to, bail out. */ 3484 last = gsi_last_bb (block); 3485 if (!gsi_end_p (last) 3486 && !is_ctrl_stmt (gsi_stmt (last)) 3487 && stmt_ends_bb_p (gsi_stmt (last))) 3488 return false; 3489 3490 /* Compute the set of hoistable expressions from ANTIC_IN. First compute 3491 hoistable values. */ 3492 bitmap_set hoistable_set; 3493 3494 /* A hoistable value must be in ANTIC_IN(block) 3495 but not in AVAIL_OUT(BLOCK). */ 3496 bitmap_initialize (&hoistable_set.values, &grand_bitmap_obstack); 3497 bitmap_and_compl (&hoistable_set.values, 3498 &ANTIC_IN (block)->values, &AVAIL_OUT (block)->values); 3499 3500 /* Short-cut for a common case: hoistable_set is empty. */ 3501 if (bitmap_empty_p (&hoistable_set.values)) 3502 return false; 3503 3504 /* Compute which of the hoistable values is in AVAIL_OUT of 3505 at least one of the successors of BLOCK. */ 3506 bitmap_head availout_in_some; 3507 bitmap_initialize (&availout_in_some, &grand_bitmap_obstack); 3508 FOR_EACH_EDGE (e, ei, block->succs) 3509 /* Do not consider expressions solely because their availability 3510 on loop exits. They'd be ANTIC-IN throughout the whole loop 3511 and thus effectively hoisted across loops by combination of 3512 PRE and hoisting. */ 3513 if (! loop_exit_edge_p (block->loop_father, e)) 3514 bitmap_ior_and_into (&availout_in_some, &hoistable_set.values, 3515 &AVAIL_OUT (e->dest)->values); 3516 bitmap_clear (&hoistable_set.values); 3517 3518 /* Short-cut for a common case: availout_in_some is empty. */ 3519 if (bitmap_empty_p (&availout_in_some)) 3520 return false; 3521 3522 /* Hack hoitable_set in-place so we can use sorted_array_from_bitmap_set. */ 3523 hoistable_set.values = availout_in_some; 3524 hoistable_set.expressions = ANTIC_IN (block)->expressions; 3525 3526 /* Now finally construct the topological-ordered expression set. */ 3527 vec<pre_expr> exprs = sorted_array_from_bitmap_set (&hoistable_set); 3528 3529 bitmap_clear (&hoistable_set.values); 3530 3531 /* If there are candidate values for hoisting, insert expressions 3532 strategically to make the hoistable expressions fully redundant. */ 3533 pre_expr expr; 3534 FOR_EACH_VEC_ELT (exprs, i, expr) 3535 { 3536 /* While we try to sort expressions topologically above the 3537 sorting doesn't work out perfectly. Catch expressions we 3538 already inserted. */ 3539 unsigned int value_id = get_expr_value_id (expr); 3540 if (bitmap_set_contains_value (AVAIL_OUT (block), value_id)) 3541 { 3542 if (dump_file && (dump_flags & TDF_DETAILS)) 3543 { 3544 fprintf (dump_file, 3545 "Already inserted expression for "); 3546 print_pre_expr (dump_file, expr); 3547 fprintf (dump_file, " (%04d)\n", value_id); 3548 } 3549 continue; 3550 } 3551 3552 /* OK, we should hoist this value. Perform the transformation. */ 3553 pre_stats.hoist_insert++; 3554 if (dump_file && (dump_flags & TDF_DETAILS)) 3555 { 3556 fprintf (dump_file, 3557 "Inserting expression in block %d for code hoisting: ", 3558 block->index); 3559 print_pre_expr (dump_file, expr); 3560 fprintf (dump_file, " (%04d)\n", value_id); 3561 } 3562 3563 gimple_seq stmts = NULL; 3564 tree res = create_expression_by_pieces (block, expr, &stmts, 3565 get_expr_type (expr)); 3566 3567 /* Do not return true if expression creation ultimately 3568 did not insert any statements. */ 3569 if (gimple_seq_empty_p (stmts)) 3570 res = NULL_TREE; 3571 else 3572 { 3573 if (gsi_end_p (last) || is_ctrl_stmt (gsi_stmt (last))) 3574 gsi_insert_seq_before (&last, stmts, GSI_SAME_STMT); 3575 else 3576 gsi_insert_seq_after (&last, stmts, GSI_NEW_STMT); 3577 } 3578 3579 /* Make sure to not return true if expression creation ultimately 3580 failed but also make sure to insert any stmts produced as they 3581 are tracked in inserted_exprs. */ 3582 if (! res) 3583 continue; 3584 3585 new_stuff = true; 3586 } 3587 3588 exprs.release (); 3589 3590 return new_stuff; 3591 } 3592 3593 /* Do a dominator walk on the control flow graph, and insert computations 3594 of values as necessary for PRE and hoisting. */ 3595 3596 static bool 3597 insert_aux (basic_block block, bool do_pre, bool do_hoist) 3598 { 3599 basic_block son; 3600 bool new_stuff = false; 3601 3602 if (block) 3603 { 3604 basic_block dom; 3605 dom = get_immediate_dominator (CDI_DOMINATORS, block); 3606 if (dom) 3607 { 3608 unsigned i; 3609 bitmap_iterator bi; 3610 bitmap_set_t newset; 3611 3612 /* First, update the AVAIL_OUT set with anything we may have 3613 inserted higher up in the dominator tree. */ 3614 newset = NEW_SETS (dom); 3615 if (newset) 3616 { 3617 /* Note that we need to value_replace both NEW_SETS, and 3618 AVAIL_OUT. For both the case of NEW_SETS, the value may be 3619 represented by some non-simple expression here that we want 3620 to replace it with. */ 3621 FOR_EACH_EXPR_ID_IN_SET (newset, i, bi) 3622 { 3623 pre_expr expr = expression_for_id (i); 3624 bitmap_value_replace_in_set (NEW_SETS (block), expr); 3625 bitmap_value_replace_in_set (AVAIL_OUT (block), expr); 3626 } 3627 } 3628 3629 /* Insert expressions for partial redundancies. */ 3630 if (do_pre && !single_pred_p (block)) 3631 { 3632 new_stuff |= do_pre_regular_insertion (block, dom); 3633 if (do_partial_partial) 3634 new_stuff |= do_pre_partial_partial_insertion (block, dom); 3635 } 3636 3637 /* Insert expressions for hoisting. */ 3638 if (do_hoist && EDGE_COUNT (block->succs) >= 2) 3639 new_stuff |= do_hoist_insertion (block); 3640 } 3641 } 3642 for (son = first_dom_son (CDI_DOMINATORS, block); 3643 son; 3644 son = next_dom_son (CDI_DOMINATORS, son)) 3645 { 3646 new_stuff |= insert_aux (son, do_pre, do_hoist); 3647 } 3648 3649 return new_stuff; 3650 } 3651 3652 /* Perform insertion of partially redundant and hoistable values. */ 3653 3654 static void 3655 insert (void) 3656 { 3657 bool new_stuff = true; 3658 basic_block bb; 3659 int num_iterations = 0; 3660 3661 FOR_ALL_BB_FN (bb, cfun) 3662 NEW_SETS (bb) = bitmap_set_new (); 3663 3664 while (new_stuff) 3665 { 3666 num_iterations++; 3667 if (dump_file && dump_flags & TDF_DETAILS) 3668 fprintf (dump_file, "Starting insert iteration %d\n", num_iterations); 3669 new_stuff = insert_aux (ENTRY_BLOCK_PTR_FOR_FN (cfun), flag_tree_pre, 3670 flag_code_hoisting); 3671 3672 /* Clear the NEW sets before the next iteration. We have already 3673 fully propagated its contents. */ 3674 if (new_stuff) 3675 FOR_ALL_BB_FN (bb, cfun) 3676 bitmap_set_free (NEW_SETS (bb)); 3677 } 3678 statistics_histogram_event (cfun, "insert iterations", num_iterations); 3679 } 3680 3681 3682 /* Compute the AVAIL set for all basic blocks. 3683 3684 This function performs value numbering of the statements in each basic 3685 block. The AVAIL sets are built from information we glean while doing 3686 this value numbering, since the AVAIL sets contain only one entry per 3687 value. 3688 3689 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)]. 3690 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */ 3691 3692 static void 3693 compute_avail (void) 3694 { 3695 3696 basic_block block, son; 3697 basic_block *worklist; 3698 size_t sp = 0; 3699 unsigned i; 3700 tree name; 3701 3702 /* We pretend that default definitions are defined in the entry block. 3703 This includes function arguments and the static chain decl. */ 3704 FOR_EACH_SSA_NAME (i, name, cfun) 3705 { 3706 pre_expr e; 3707 if (!SSA_NAME_IS_DEFAULT_DEF (name) 3708 || has_zero_uses (name) 3709 || virtual_operand_p (name)) 3710 continue; 3711 3712 e = get_or_alloc_expr_for_name (name); 3713 add_to_value (get_expr_value_id (e), e); 3714 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (cfun)), e); 3715 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (cfun)), 3716 e); 3717 } 3718 3719 if (dump_file && (dump_flags & TDF_DETAILS)) 3720 { 3721 print_bitmap_set (dump_file, TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (cfun)), 3722 "tmp_gen", ENTRY_BLOCK); 3723 print_bitmap_set (dump_file, AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (cfun)), 3724 "avail_out", ENTRY_BLOCK); 3725 } 3726 3727 /* Allocate the worklist. */ 3728 worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun)); 3729 3730 /* Seed the algorithm by putting the dominator children of the entry 3731 block on the worklist. */ 3732 for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR_FOR_FN (cfun)); 3733 son; 3734 son = next_dom_son (CDI_DOMINATORS, son)) 3735 worklist[sp++] = son; 3736 3737 BB_LIVE_VOP_ON_EXIT (ENTRY_BLOCK_PTR_FOR_FN (cfun)) 3738 = ssa_default_def (cfun, gimple_vop (cfun)); 3739 3740 /* Loop until the worklist is empty. */ 3741 while (sp) 3742 { 3743 gimple *stmt; 3744 basic_block dom; 3745 3746 /* Pick a block from the worklist. */ 3747 block = worklist[--sp]; 3748 3749 /* Initially, the set of available values in BLOCK is that of 3750 its immediate dominator. */ 3751 dom = get_immediate_dominator (CDI_DOMINATORS, block); 3752 if (dom) 3753 { 3754 bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom)); 3755 BB_LIVE_VOP_ON_EXIT (block) = BB_LIVE_VOP_ON_EXIT (dom); 3756 } 3757 3758 /* Generate values for PHI nodes. */ 3759 for (gphi_iterator gsi = gsi_start_phis (block); !gsi_end_p (gsi); 3760 gsi_next (&gsi)) 3761 { 3762 tree result = gimple_phi_result (gsi.phi ()); 3763 3764 /* We have no need for virtual phis, as they don't represent 3765 actual computations. */ 3766 if (virtual_operand_p (result)) 3767 { 3768 BB_LIVE_VOP_ON_EXIT (block) = result; 3769 continue; 3770 } 3771 3772 pre_expr e = get_or_alloc_expr_for_name (result); 3773 add_to_value (get_expr_value_id (e), e); 3774 bitmap_value_insert_into_set (AVAIL_OUT (block), e); 3775 bitmap_insert_into_set (PHI_GEN (block), e); 3776 } 3777 3778 BB_MAY_NOTRETURN (block) = 0; 3779 3780 /* Now compute value numbers and populate value sets with all 3781 the expressions computed in BLOCK. */ 3782 for (gimple_stmt_iterator gsi = gsi_start_bb (block); !gsi_end_p (gsi); 3783 gsi_next (&gsi)) 3784 { 3785 ssa_op_iter iter; 3786 tree op; 3787 3788 stmt = gsi_stmt (gsi); 3789 3790 /* Cache whether the basic-block has any non-visible side-effect 3791 or control flow. 3792 If this isn't a call or it is the last stmt in the 3793 basic-block then the CFG represents things correctly. */ 3794 if (is_gimple_call (stmt) && !stmt_ends_bb_p (stmt)) 3795 { 3796 /* Non-looping const functions always return normally. 3797 Otherwise the call might not return or have side-effects 3798 that forbids hoisting possibly trapping expressions 3799 before it. */ 3800 int flags = gimple_call_flags (stmt); 3801 if (!(flags & ECF_CONST) 3802 || (flags & ECF_LOOPING_CONST_OR_PURE)) 3803 BB_MAY_NOTRETURN (block) = 1; 3804 } 3805 3806 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF) 3807 { 3808 pre_expr e = get_or_alloc_expr_for_name (op); 3809 3810 add_to_value (get_expr_value_id (e), e); 3811 bitmap_insert_into_set (TMP_GEN (block), e); 3812 bitmap_value_insert_into_set (AVAIL_OUT (block), e); 3813 } 3814 3815 if (gimple_vdef (stmt)) 3816 BB_LIVE_VOP_ON_EXIT (block) = gimple_vdef (stmt); 3817 3818 if (gimple_has_side_effects (stmt) 3819 || stmt_could_throw_p (stmt) 3820 || is_gimple_debug (stmt)) 3821 continue; 3822 3823 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE) 3824 { 3825 if (ssa_undefined_value_p (op)) 3826 continue; 3827 pre_expr e = get_or_alloc_expr_for_name (op); 3828 bitmap_value_insert_into_set (EXP_GEN (block), e); 3829 } 3830 3831 switch (gimple_code (stmt)) 3832 { 3833 case GIMPLE_RETURN: 3834 continue; 3835 3836 case GIMPLE_CALL: 3837 { 3838 vn_reference_t ref; 3839 vn_reference_s ref1; 3840 pre_expr result = NULL; 3841 3842 /* We can value number only calls to real functions. */ 3843 if (gimple_call_internal_p (stmt)) 3844 continue; 3845 3846 vn_reference_lookup_call (as_a <gcall *> (stmt), &ref, &ref1); 3847 if (!ref) 3848 continue; 3849 3850 /* If the value of the call is not invalidated in 3851 this block until it is computed, add the expression 3852 to EXP_GEN. */ 3853 if (!gimple_vuse (stmt) 3854 || gimple_code 3855 (SSA_NAME_DEF_STMT (gimple_vuse (stmt))) == GIMPLE_PHI 3856 || gimple_bb (SSA_NAME_DEF_STMT 3857 (gimple_vuse (stmt))) != block) 3858 { 3859 result = pre_expr_pool.allocate (); 3860 result->kind = REFERENCE; 3861 result->id = 0; 3862 PRE_EXPR_REFERENCE (result) = ref; 3863 3864 get_or_alloc_expression_id (result); 3865 add_to_value (get_expr_value_id (result), result); 3866 bitmap_value_insert_into_set (EXP_GEN (block), result); 3867 } 3868 continue; 3869 } 3870 3871 case GIMPLE_ASSIGN: 3872 { 3873 pre_expr result = NULL; 3874 switch (vn_get_stmt_kind (stmt)) 3875 { 3876 case VN_NARY: 3877 { 3878 enum tree_code code = gimple_assign_rhs_code (stmt); 3879 vn_nary_op_t nary; 3880 3881 /* COND_EXPR and VEC_COND_EXPR are awkward in 3882 that they contain an embedded complex expression. 3883 Don't even try to shove those through PRE. */ 3884 if (code == COND_EXPR 3885 || code == VEC_COND_EXPR) 3886 continue; 3887 3888 vn_nary_op_lookup_stmt (stmt, &nary); 3889 if (!nary) 3890 continue; 3891 3892 /* If the NARY traps and there was a preceding 3893 point in the block that might not return avoid 3894 adding the nary to EXP_GEN. */ 3895 if (BB_MAY_NOTRETURN (block) 3896 && vn_nary_may_trap (nary)) 3897 continue; 3898 3899 result = pre_expr_pool.allocate (); 3900 result->kind = NARY; 3901 result->id = 0; 3902 PRE_EXPR_NARY (result) = nary; 3903 break; 3904 } 3905 3906 case VN_REFERENCE: 3907 { 3908 tree rhs1 = gimple_assign_rhs1 (stmt); 3909 alias_set_type set = get_alias_set (rhs1); 3910 vec<vn_reference_op_s> operands 3911 = vn_reference_operands_for_lookup (rhs1); 3912 vn_reference_t ref; 3913 vn_reference_lookup_pieces (gimple_vuse (stmt), set, 3914 TREE_TYPE (rhs1), 3915 operands, &ref, VN_WALK); 3916 if (!ref) 3917 { 3918 operands.release (); 3919 continue; 3920 } 3921 3922 /* If the value of the reference is not invalidated in 3923 this block until it is computed, add the expression 3924 to EXP_GEN. */ 3925 if (gimple_vuse (stmt)) 3926 { 3927 gimple *def_stmt; 3928 bool ok = true; 3929 def_stmt = SSA_NAME_DEF_STMT (gimple_vuse (stmt)); 3930 while (!gimple_nop_p (def_stmt) 3931 && gimple_code (def_stmt) != GIMPLE_PHI 3932 && gimple_bb (def_stmt) == block) 3933 { 3934 if (stmt_may_clobber_ref_p 3935 (def_stmt, gimple_assign_rhs1 (stmt))) 3936 { 3937 ok = false; 3938 break; 3939 } 3940 def_stmt 3941 = SSA_NAME_DEF_STMT (gimple_vuse (def_stmt)); 3942 } 3943 if (!ok) 3944 { 3945 operands.release (); 3946 continue; 3947 } 3948 } 3949 3950 /* If the load was value-numbered to another 3951 load make sure we do not use its expression 3952 for insertion if it wouldn't be a valid 3953 replacement. */ 3954 /* At the momemt we have a testcase 3955 for hoist insertion of aligned vs. misaligned 3956 variants in gcc.dg/torture/pr65270-1.c thus 3957 with just alignment to be considered we can 3958 simply replace the expression in the hashtable 3959 with the most conservative one. */ 3960 vn_reference_op_t ref1 = &ref->operands.last (); 3961 while (ref1->opcode != TARGET_MEM_REF 3962 && ref1->opcode != MEM_REF 3963 && ref1 != &ref->operands[0]) 3964 --ref1; 3965 vn_reference_op_t ref2 = &operands.last (); 3966 while (ref2->opcode != TARGET_MEM_REF 3967 && ref2->opcode != MEM_REF 3968 && ref2 != &operands[0]) 3969 --ref2; 3970 if ((ref1->opcode == TARGET_MEM_REF 3971 || ref1->opcode == MEM_REF) 3972 && (TYPE_ALIGN (ref1->type) 3973 > TYPE_ALIGN (ref2->type))) 3974 ref1->type 3975 = build_aligned_type (ref1->type, 3976 TYPE_ALIGN (ref2->type)); 3977 /* TBAA behavior is an obvious part so make sure 3978 that the hashtable one covers this as well 3979 by adjusting the ref alias set and its base. */ 3980 if (ref->set == set 3981 || alias_set_subset_of (set, ref->set)) 3982 ; 3983 else if (alias_set_subset_of (ref->set, set)) 3984 { 3985 ref->set = set; 3986 if (ref1->opcode == MEM_REF) 3987 ref1->op0 3988 = wide_int_to_tree (TREE_TYPE (ref2->op0), 3989 wi::to_wide (ref1->op0)); 3990 else 3991 ref1->op2 3992 = wide_int_to_tree (TREE_TYPE (ref2->op2), 3993 wi::to_wide (ref1->op2)); 3994 } 3995 else 3996 { 3997 ref->set = 0; 3998 if (ref1->opcode == MEM_REF) 3999 ref1->op0 4000 = wide_int_to_tree (ptr_type_node, 4001 wi::to_wide (ref1->op0)); 4002 else 4003 ref1->op2 4004 = wide_int_to_tree (ptr_type_node, 4005 wi::to_wide (ref1->op2)); 4006 } 4007 operands.release (); 4008 4009 result = pre_expr_pool.allocate (); 4010 result->kind = REFERENCE; 4011 result->id = 0; 4012 PRE_EXPR_REFERENCE (result) = ref; 4013 break; 4014 } 4015 4016 default: 4017 continue; 4018 } 4019 4020 get_or_alloc_expression_id (result); 4021 add_to_value (get_expr_value_id (result), result); 4022 bitmap_value_insert_into_set (EXP_GEN (block), result); 4023 continue; 4024 } 4025 default: 4026 break; 4027 } 4028 } 4029 4030 if (dump_file && (dump_flags & TDF_DETAILS)) 4031 { 4032 print_bitmap_set (dump_file, EXP_GEN (block), 4033 "exp_gen", block->index); 4034 print_bitmap_set (dump_file, PHI_GEN (block), 4035 "phi_gen", block->index); 4036 print_bitmap_set (dump_file, TMP_GEN (block), 4037 "tmp_gen", block->index); 4038 print_bitmap_set (dump_file, AVAIL_OUT (block), 4039 "avail_out", block->index); 4040 } 4041 4042 /* Put the dominator children of BLOCK on the worklist of blocks 4043 to compute available sets for. */ 4044 for (son = first_dom_son (CDI_DOMINATORS, block); 4045 son; 4046 son = next_dom_son (CDI_DOMINATORS, son)) 4047 worklist[sp++] = son; 4048 } 4049 4050 free (worklist); 4051 } 4052 4053 4054 /* Initialize data structures used by PRE. */ 4055 4056 static void 4057 init_pre (void) 4058 { 4059 basic_block bb; 4060 4061 next_expression_id = 1; 4062 expressions.create (0); 4063 expressions.safe_push (NULL); 4064 value_expressions.create (get_max_value_id () + 1); 4065 value_expressions.safe_grow_cleared (get_max_value_id () + 1); 4066 name_to_id.create (0); 4067 4068 inserted_exprs = BITMAP_ALLOC (NULL); 4069 4070 connect_infinite_loops_to_exit (); 4071 memset (&pre_stats, 0, sizeof (pre_stats)); 4072 4073 alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets)); 4074 4075 calculate_dominance_info (CDI_DOMINATORS); 4076 4077 bitmap_obstack_initialize (&grand_bitmap_obstack); 4078 phi_translate_table = new hash_table<expr_pred_trans_d> (5110); 4079 expression_to_id = new hash_table<pre_expr_d> (num_ssa_names * 3); 4080 FOR_ALL_BB_FN (bb, cfun) 4081 { 4082 EXP_GEN (bb) = bitmap_set_new (); 4083 PHI_GEN (bb) = bitmap_set_new (); 4084 TMP_GEN (bb) = bitmap_set_new (); 4085 AVAIL_OUT (bb) = bitmap_set_new (); 4086 } 4087 } 4088 4089 4090 /* Deallocate data structures used by PRE. */ 4091 4092 static void 4093 fini_pre () 4094 { 4095 value_expressions.release (); 4096 expressions.release (); 4097 BITMAP_FREE (inserted_exprs); 4098 bitmap_obstack_release (&grand_bitmap_obstack); 4099 bitmap_set_pool.release (); 4100 pre_expr_pool.release (); 4101 delete phi_translate_table; 4102 phi_translate_table = NULL; 4103 delete expression_to_id; 4104 expression_to_id = NULL; 4105 name_to_id.release (); 4106 4107 free_aux_for_blocks (); 4108 } 4109 4110 namespace { 4111 4112 const pass_data pass_data_pre = 4113 { 4114 GIMPLE_PASS, /* type */ 4115 "pre", /* name */ 4116 OPTGROUP_NONE, /* optinfo_flags */ 4117 TV_TREE_PRE, /* tv_id */ 4118 ( PROP_cfg | PROP_ssa ), /* properties_required */ 4119 0, /* properties_provided */ 4120 0, /* properties_destroyed */ 4121 TODO_rebuild_alias, /* todo_flags_start */ 4122 0, /* todo_flags_finish */ 4123 }; 4124 4125 class pass_pre : public gimple_opt_pass 4126 { 4127 public: 4128 pass_pre (gcc::context *ctxt) 4129 : gimple_opt_pass (pass_data_pre, ctxt) 4130 {} 4131 4132 /* opt_pass methods: */ 4133 virtual bool gate (function *) 4134 { return flag_tree_pre != 0 || flag_code_hoisting != 0; } 4135 virtual unsigned int execute (function *); 4136 4137 }; // class pass_pre 4138 4139 unsigned int 4140 pass_pre::execute (function *fun) 4141 { 4142 unsigned int todo = 0; 4143 4144 do_partial_partial = 4145 flag_tree_partial_pre && optimize_function_for_speed_p (fun); 4146 4147 /* This has to happen before SCCVN runs because 4148 loop_optimizer_init may create new phis, etc. */ 4149 loop_optimizer_init (LOOPS_NORMAL); 4150 split_critical_edges (); 4151 scev_initialize (); 4152 4153 run_scc_vn (VN_WALK); 4154 4155 init_pre (); 4156 4157 /* Insert can get quite slow on an incredibly large number of basic 4158 blocks due to some quadratic behavior. Until this behavior is 4159 fixed, don't run it when he have an incredibly large number of 4160 bb's. If we aren't going to run insert, there is no point in 4161 computing ANTIC, either, even though it's plenty fast nor do 4162 we require AVAIL. */ 4163 if (n_basic_blocks_for_fn (fun) < 4000) 4164 { 4165 compute_avail (); 4166 compute_antic (); 4167 insert (); 4168 } 4169 4170 /* Make sure to remove fake edges before committing our inserts. 4171 This makes sure we don't end up with extra critical edges that 4172 we would need to split. */ 4173 remove_fake_exit_edges (); 4174 gsi_commit_edge_inserts (); 4175 4176 /* Eliminate folds statements which might (should not...) end up 4177 not keeping virtual operands up-to-date. */ 4178 gcc_assert (!need_ssa_update_p (fun)); 4179 4180 statistics_counter_event (fun, "Insertions", pre_stats.insertions); 4181 statistics_counter_event (fun, "PA inserted", pre_stats.pa_insert); 4182 statistics_counter_event (fun, "HOIST inserted", pre_stats.hoist_insert); 4183 statistics_counter_event (fun, "New PHIs", pre_stats.phis); 4184 4185 /* Remove all the redundant expressions. */ 4186 todo |= vn_eliminate (inserted_exprs); 4187 4188 /* Because we don't follow exactly the standard PRE algorithm, and decide not 4189 to insert PHI nodes sometimes, and because value numbering of casts isn't 4190 perfect, we sometimes end up inserting dead code. This simple DCE-like 4191 pass removes any insertions we made that weren't actually used. */ 4192 simple_dce_from_worklist (inserted_exprs); 4193 4194 fini_pre (); 4195 4196 scev_finalize (); 4197 loop_optimizer_finalize (); 4198 4199 /* Restore SSA info before tail-merging as that resets it as well. */ 4200 scc_vn_restore_ssa_info (); 4201 4202 /* TODO: tail_merge_optimize may merge all predecessors of a block, in which 4203 case we can merge the block with the remaining predecessor of the block. 4204 It should either: 4205 - call merge_blocks after each tail merge iteration 4206 - call merge_blocks after all tail merge iterations 4207 - mark TODO_cleanup_cfg when necessary 4208 - share the cfg cleanup with fini_pre. */ 4209 todo |= tail_merge_optimize (todo); 4210 4211 free_scc_vn (); 4212 4213 /* Tail merging invalidates the virtual SSA web, together with 4214 cfg-cleanup opportunities exposed by PRE this will wreck the 4215 SSA updating machinery. So make sure to run update-ssa 4216 manually, before eventually scheduling cfg-cleanup as part of 4217 the todo. */ 4218 update_ssa (TODO_update_ssa_only_virtuals); 4219 4220 return todo; 4221 } 4222 4223 } // anon namespace 4224 4225 gimple_opt_pass * 4226 make_pass_pre (gcc::context *ctxt) 4227 { 4228 return new pass_pre (ctxt); 4229 } 4230