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