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