1169689Skan/* SSA-PRE for trees. 2169689Skan Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3169689Skan Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher 4169689Skan <stevenb@suse.de> 5169689Skan 6169689SkanThis file is part of GCC. 7169689Skan 8169689SkanGCC is free software; you can redistribute it and/or modify 9169689Skanit under the terms of the GNU General Public License as published by 10169689Skanthe Free Software Foundation; either version 2, or (at your option) 11169689Skanany later version. 12169689Skan 13169689SkanGCC is distributed in the hope that it will be useful, 14169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 15169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16169689SkanGNU General Public License for more details. 17169689Skan 18169689SkanYou should have received a copy of the GNU General Public License 19169689Skanalong with GCC; see the file COPYING. If not, write to 20169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 21169689SkanBoston, MA 02110-1301, USA. */ 22169689Skan 23169689Skan#include "config.h" 24169689Skan#include "system.h" 25169689Skan#include "coretypes.h" 26169689Skan#include "tm.h" 27169689Skan#include "ggc.h" 28169689Skan#include "tree.h" 29169689Skan#include "basic-block.h" 30169689Skan#include "diagnostic.h" 31169689Skan#include "tree-inline.h" 32169689Skan#include "tree-flow.h" 33169689Skan#include "tree-gimple.h" 34169689Skan#include "tree-dump.h" 35169689Skan#include "timevar.h" 36169689Skan#include "fibheap.h" 37169689Skan#include "hashtab.h" 38169689Skan#include "tree-iterator.h" 39169689Skan#include "real.h" 40169689Skan#include "alloc-pool.h" 41169689Skan#include "tree-pass.h" 42169689Skan#include "flags.h" 43169689Skan#include "bitmap.h" 44169689Skan#include "langhooks.h" 45169689Skan#include "cfgloop.h" 46169689Skan 47169689Skan/* TODO: 48169689Skan 49169689Skan 1. Avail sets can be shared by making an avail_find_leader that 50169689Skan walks up the dominator tree and looks in those avail sets. 51169689Skan This might affect code optimality, it's unclear right now. 52169689Skan 2. Strength reduction can be performed by anticipating expressions 53169689Skan we can repair later on. 54169689Skan 3. We can do back-substitution or smarter value numbering to catch 55169689Skan commutative expressions split up over multiple statements. 56169689Skan 4. ANTIC_SAFE_LOADS could be a lot smarter than it is now. 57169689Skan Right now, it is simply calculating loads that occur before 58169689Skan any store in a block, instead of loads that occur before 59169689Skan stores that affect them. This is relatively more expensive, and 60169689Skan it's not clear how much more it will buy us. 61169689Skan*/ 62169689Skan 63169689Skan/* For ease of terminology, "expression node" in the below refers to 64169689Skan every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent 65169689Skan the actual statement containing the expressions we care about, and 66169689Skan we cache the value number by putting it in the expression. */ 67169689Skan 68169689Skan/* Basic algorithm 69169689Skan 70169689Skan First we walk the statements to generate the AVAIL sets, the 71169689Skan EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the 72169689Skan generation of values/expressions by a given block. We use them 73169689Skan when computing the ANTIC sets. The AVAIL sets consist of 74169689Skan SSA_NAME's that represent values, so we know what values are 75169689Skan available in what blocks. AVAIL is a forward dataflow problem. In 76169689Skan SSA, values are never killed, so we don't need a kill set, or a 77169689Skan fixpoint iteration, in order to calculate the AVAIL sets. In 78169689Skan traditional parlance, AVAIL sets tell us the downsafety of the 79169689Skan expressions/values. 80169689Skan 81169689Skan Next, we generate the ANTIC sets. These sets represent the 82169689Skan anticipatable expressions. ANTIC is a backwards dataflow 83169689Skan problem.An expression is anticipatable in a given block if it could 84169689Skan be generated in that block. This means that if we had to perform 85169689Skan an insertion in that block, of the value of that expression, we 86169689Skan could. Calculating the ANTIC sets requires phi translation of 87169689Skan expressions, because the flow goes backwards through phis. We must 88169689Skan iterate to a fixpoint of the ANTIC sets, because we have a kill 89169689Skan set. Even in SSA form, values are not live over the entire 90169689Skan function, only from their definition point onwards. So we have to 91169689Skan remove values from the ANTIC set once we go past the definition 92169689Skan point of the leaders that make them up. 93169689Skan compute_antic/compute_antic_aux performs this computation. 94169689Skan 95169689Skan Third, we perform insertions to make partially redundant 96169689Skan expressions fully redundant. 97169689Skan 98169689Skan An expression is partially redundant (excluding partial 99169689Skan anticipation) if: 100169689Skan 101169689Skan 1. It is AVAIL in some, but not all, of the predecessors of a 102169689Skan given block. 103169689Skan 2. It is ANTIC in all the predecessors. 104169689Skan 105169689Skan In order to make it fully redundant, we insert the expression into 106169689Skan the predecessors where it is not available, but is ANTIC. 107169689Skan insert/insert_aux performs this insertion. 108169689Skan 109169689Skan Fourth, we eliminate fully redundant expressions. 110169689Skan This is a simple statement walk that replaces redundant 111169689Skan calculations with the now available values. */ 112169689Skan 113169689Skan/* Representations of value numbers: 114169689Skan 115169689Skan Value numbers are represented using the "value handle" approach. 116169689Skan This means that each SSA_NAME (and for other reasons to be 117169689Skan disclosed in a moment, expression nodes) has a value handle that 118169689Skan can be retrieved through get_value_handle. This value handle, *is* 119169689Skan the value number of the SSA_NAME. You can pointer compare the 120169689Skan value handles for equivalence purposes. 121169689Skan 122169689Skan For debugging reasons, the value handle is internally more than 123169689Skan just a number, it is a VAR_DECL named "value.x", where x is a 124169689Skan unique number for each value number in use. This allows 125169689Skan expressions with SSA_NAMES replaced by value handles to still be 126169689Skan pretty printed in a sane way. They simply print as "value.3 * 127169689Skan value.5", etc. 128169689Skan 129169689Skan Expression nodes have value handles associated with them as a 130169689Skan cache. Otherwise, we'd have to look them up again in the hash 131169689Skan table This makes significant difference (factor of two or more) on 132169689Skan some test cases. They can be thrown away after the pass is 133169689Skan finished. */ 134169689Skan 135169689Skan/* Representation of expressions on value numbers: 136169689Skan 137169689Skan In some portions of this code, you will notice we allocate "fake" 138169689Skan analogues to the expression we are value numbering, and replace the 139169689Skan operands with the values of the expression. Since we work on 140169689Skan values, and not just names, we canonicalize expressions to value 141169689Skan expressions for use in the ANTIC sets, the EXP_GEN set, etc. 142169689Skan 143169689Skan This is theoretically unnecessary, it just saves a bunch of 144169689Skan repeated get_value_handle and find_leader calls in the remainder of 145169689Skan the code, trading off temporary memory usage for speed. The tree 146169689Skan nodes aren't actually creating more garbage, since they are 147169689Skan allocated in a special pools which are thrown away at the end of 148169689Skan this pass. 149169689Skan 150169689Skan All of this also means that if you print the EXP_GEN or ANTIC sets, 151169689Skan you will see "value.5 + value.7" in the set, instead of "a_55 + 152169689Skan b_66" or something. The only thing that actually cares about 153169689Skan seeing the value leaders is phi translation, and it needs to be 154169689Skan able to find the leader for a value in an arbitrary block, so this 155169689Skan "value expression" form is perfect for it (otherwise you'd do 156169689Skan get_value_handle->find_leader->translate->get_value_handle->find_leader).*/ 157169689Skan 158169689Skan 159169689Skan/* Representation of sets: 160169689Skan 161169689Skan There are currently two types of sets used, hopefully to be unified soon. 162169689Skan The AVAIL sets do not need to be sorted in any particular order, 163169689Skan and thus, are simply represented as two bitmaps, one that keeps 164169689Skan track of values present in the set, and one that keeps track of 165169689Skan expressions present in the set. 166169689Skan 167169689Skan The other sets are represented as doubly linked lists kept in topological 168169689Skan order, with an optional supporting bitmap of values present in the 169169689Skan set. The sets represent values, and the elements can be values or 170169689Skan expressions. The elements can appear in different sets, but each 171169689Skan element can only appear once in each set. 172169689Skan 173169689Skan Since each node in the set represents a value, we also want to be 174169689Skan able to map expression, set pairs to something that tells us 175169689Skan whether the value is present is a set. We use a per-set bitmap for 176169689Skan that. The value handles also point to a linked list of the 177169689Skan expressions they represent via a tree annotation. This is mainly 178169689Skan useful only for debugging, since we don't do identity lookups. */ 179169689Skan 180169689Skan 181169689Skanstatic bool in_fre = false; 182169689Skan 183169689Skan/* A value set element. Basically a single linked list of 184169689Skan expressions/values. */ 185169689Skantypedef struct value_set_node 186169689Skan{ 187169689Skan /* An expression. */ 188169689Skan tree expr; 189169689Skan 190169689Skan /* A pointer to the next element of the value set. */ 191169689Skan struct value_set_node *next; 192169689Skan} *value_set_node_t; 193169689Skan 194169689Skan 195169689Skan/* A value set. This is a singly linked list of value_set_node 196169689Skan elements with a possible bitmap that tells us what values exist in 197169689Skan the set. This set must be kept in topologically sorted order. */ 198169689Skantypedef struct value_set 199169689Skan{ 200169689Skan /* The head of the list. Used for iterating over the list in 201169689Skan order. */ 202169689Skan value_set_node_t head; 203169689Skan 204169689Skan /* The tail of the list. Used for tail insertions, which are 205169689Skan necessary to keep the set in topologically sorted order because 206169689Skan of how the set is built. */ 207169689Skan value_set_node_t tail; 208169689Skan 209169689Skan /* The length of the list. */ 210169689Skan size_t length; 211169689Skan 212169689Skan /* True if the set is indexed, which means it contains a backing 213169689Skan bitmap for quick determination of whether certain values exist in the 214169689Skan set. */ 215169689Skan bool indexed; 216169689Skan 217169689Skan /* The bitmap of values that exist in the set. May be NULL in an 218169689Skan empty or non-indexed set. */ 219169689Skan bitmap values; 220169689Skan 221169689Skan} *value_set_t; 222169689Skan 223169689Skan 224169689Skan/* An unordered bitmap set. One bitmap tracks values, the other, 225169689Skan expressions. */ 226169689Skantypedef struct bitmap_set 227169689Skan{ 228169689Skan bitmap expressions; 229169689Skan bitmap values; 230169689Skan} *bitmap_set_t; 231169689Skan 232169689Skan/* Sets that we need to keep track of. */ 233169689Skantypedef struct bb_value_sets 234169689Skan{ 235169689Skan /* The EXP_GEN set, which represents expressions/values generated in 236169689Skan a basic block. */ 237169689Skan value_set_t exp_gen; 238169689Skan 239169689Skan /* The PHI_GEN set, which represents PHI results generated in a 240169689Skan basic block. */ 241169689Skan bitmap_set_t phi_gen; 242169689Skan 243169689Skan /* The TMP_GEN set, which represents results/temporaries generated 244169689Skan in a basic block. IE the LHS of an expression. */ 245169689Skan bitmap_set_t tmp_gen; 246169689Skan 247169689Skan /* The AVAIL_OUT set, which represents which values are available in 248169689Skan a given basic block. */ 249169689Skan bitmap_set_t avail_out; 250169689Skan 251169689Skan /* The ANTIC_IN set, which represents which values are anticipatable 252169689Skan in a given basic block. */ 253169689Skan value_set_t antic_in; 254169689Skan 255169689Skan /* The NEW_SETS set, which is used during insertion to augment the 256169689Skan AVAIL_OUT set of blocks with the new insertions performed during 257169689Skan the current iteration. */ 258169689Skan bitmap_set_t new_sets; 259169689Skan 260169689Skan /* The RVUSE sets, which are used during ANTIC computation to ensure 261169689Skan that we don't mark loads ANTIC once they have died. */ 262169689Skan bitmap rvuse_in; 263169689Skan bitmap rvuse_out; 264169689Skan bitmap rvuse_gen; 265169689Skan bitmap rvuse_kill; 266169689Skan 267169689Skan /* For actually occurring loads, as long as they occur before all the 268169689Skan other stores in the block, we know they are antic at the top of 269169689Skan the block, regardless of RVUSE_KILL. */ 270169689Skan value_set_t antic_safe_loads; 271169689Skan} *bb_value_sets_t; 272169689Skan 273169689Skan#define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen 274169689Skan#define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen 275169689Skan#define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen 276169689Skan#define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out 277169689Skan#define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in 278169689Skan#define RVUSE_IN(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_in 279169689Skan#define RVUSE_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_gen 280169689Skan#define RVUSE_KILL(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_kill 281169689Skan#define RVUSE_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_out 282169689Skan#define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets 283169689Skan#define ANTIC_SAFE_LOADS(BB) ((bb_value_sets_t) ((BB)->aux))->antic_safe_loads 284169689Skan 285169689Skan/* This structure is used to keep track of statistics on what 286169689Skan optimization PRE was able to perform. */ 287169689Skanstatic struct 288169689Skan{ 289169689Skan /* The number of RHS computations eliminated by PRE. */ 290169689Skan int eliminations; 291169689Skan 292169689Skan /* The number of new expressions/temporaries generated by PRE. */ 293169689Skan int insertions; 294169689Skan 295169689Skan /* The number of new PHI nodes added by PRE. */ 296169689Skan int phis; 297169689Skan 298169689Skan /* The number of values found constant. */ 299169689Skan int constified; 300169689Skan 301169689Skan} pre_stats; 302169689Skan 303169689Skan 304169689Skanstatic tree bitmap_find_leader (bitmap_set_t, tree); 305169689Skanstatic tree find_leader (value_set_t, tree); 306169689Skanstatic void value_insert_into_set (value_set_t, tree); 307169689Skanstatic void bitmap_value_insert_into_set (bitmap_set_t, tree); 308169689Skanstatic void bitmap_value_replace_in_set (bitmap_set_t, tree); 309169689Skanstatic void insert_into_set (value_set_t, tree); 310169689Skanstatic void bitmap_set_copy (bitmap_set_t, bitmap_set_t); 311169689Skanstatic bool bitmap_set_contains_value (bitmap_set_t, tree); 312169689Skanstatic bitmap_set_t bitmap_set_new (void); 313169689Skanstatic value_set_t set_new (bool); 314169689Skanstatic bool is_undefined_value (tree); 315169689Skanstatic tree create_expression_by_pieces (basic_block, tree, tree); 316169689Skanstatic tree find_or_generate_expression (basic_block, tree, tree); 317169689Skan 318169689Skan 319169689Skan/* We can add and remove elements and entries to and from sets 320169689Skan and hash tables, so we use alloc pools for them. */ 321169689Skan 322169689Skanstatic alloc_pool value_set_pool; 323169689Skanstatic alloc_pool bitmap_set_pool; 324169689Skanstatic alloc_pool value_set_node_pool; 325169689Skanstatic alloc_pool binary_node_pool; 326169689Skanstatic alloc_pool unary_node_pool; 327169689Skanstatic alloc_pool reference_node_pool; 328169689Skanstatic alloc_pool comparison_node_pool; 329169689Skanstatic alloc_pool expression_node_pool; 330169689Skanstatic alloc_pool list_node_pool; 331169689Skanstatic alloc_pool modify_expr_node_pool; 332169689Skanstatic bitmap_obstack grand_bitmap_obstack; 333169689Skan 334169689Skan/* To avoid adding 300 temporary variables when we only need one, we 335169689Skan only create one temporary variable, on demand, and build ssa names 336169689Skan off that. We do have to change the variable if the types don't 337169689Skan match the current variable's type. */ 338169689Skanstatic tree pretemp; 339169689Skanstatic tree storetemp; 340169689Skanstatic tree mergephitemp; 341169689Skanstatic tree prephitemp; 342169689Skan 343169689Skan/* Set of blocks with statements that have had its EH information 344169689Skan cleaned up. */ 345169689Skanstatic bitmap need_eh_cleanup; 346169689Skan 347169689Skan/* The phi_translate_table caches phi translations for a given 348169689Skan expression and predecessor. */ 349169689Skan 350169689Skanstatic htab_t phi_translate_table; 351169689Skan 352169689Skan/* A three tuple {e, pred, v} used to cache phi translations in the 353169689Skan phi_translate_table. */ 354169689Skan 355169689Skantypedef struct expr_pred_trans_d 356169689Skan{ 357169689Skan /* The expression. */ 358169689Skan tree e; 359169689Skan 360169689Skan /* The predecessor block along which we translated the expression. */ 361169689Skan basic_block pred; 362169689Skan 363169689Skan /* vuses associated with the expression. */ 364169689Skan VEC (tree, gc) *vuses; 365169689Skan 366169689Skan /* The value that resulted from the translation. */ 367169689Skan tree v; 368169689Skan 369169689Skan 370169689Skan /* The hashcode for the expression, pred pair. This is cached for 371169689Skan speed reasons. */ 372169689Skan hashval_t hashcode; 373169689Skan} *expr_pred_trans_t; 374169689Skan 375169689Skan/* Return the hash value for a phi translation table entry. */ 376169689Skan 377169689Skanstatic hashval_t 378169689Skanexpr_pred_trans_hash (const void *p) 379169689Skan{ 380169689Skan const expr_pred_trans_t ve = (expr_pred_trans_t) p; 381169689Skan return ve->hashcode; 382169689Skan} 383169689Skan 384169689Skan/* Return true if two phi translation table entries are the same. 385169689Skan P1 and P2 should point to the expr_pred_trans_t's to be compared.*/ 386169689Skan 387169689Skanstatic int 388169689Skanexpr_pred_trans_eq (const void *p1, const void *p2) 389169689Skan{ 390169689Skan const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1; 391169689Skan const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2; 392169689Skan basic_block b1 = ve1->pred; 393169689Skan basic_block b2 = ve2->pred; 394169689Skan int i; 395169689Skan tree vuse1; 396169689Skan 397169689Skan /* If they are not translations for the same basic block, they can't 398169689Skan be equal. */ 399169689Skan if (b1 != b2) 400169689Skan return false; 401169689Skan 402169689Skan 403169689Skan /* If they are for the same basic block, determine if the 404169689Skan expressions are equal. */ 405169689Skan if (!expressions_equal_p (ve1->e, ve2->e)) 406169689Skan return false; 407169689Skan 408169689Skan /* Make sure the vuses are equivalent. */ 409169689Skan if (ve1->vuses == ve2->vuses) 410169689Skan return true; 411169689Skan 412169689Skan if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses)) 413169689Skan return false; 414169689Skan 415169689Skan for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++) 416169689Skan { 417169689Skan if (VEC_index (tree, ve2->vuses, i) != vuse1) 418169689Skan return false; 419169689Skan } 420169689Skan 421169689Skan return true; 422169689Skan} 423169689Skan 424169689Skan/* Search in the phi translation table for the translation of 425169689Skan expression E in basic block PRED with vuses VUSES. 426169689Skan Return the translated value, if found, NULL otherwise. */ 427169689Skan 428169689Skanstatic inline tree 429169689Skanphi_trans_lookup (tree e, basic_block pred, VEC (tree, gc) *vuses) 430169689Skan{ 431169689Skan void **slot; 432169689Skan struct expr_pred_trans_d ept; 433169689Skan 434169689Skan ept.e = e; 435169689Skan ept.pred = pred; 436169689Skan ept.vuses = vuses; 437169689Skan ept.hashcode = vn_compute (e, (unsigned long) pred); 438169689Skan slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode, 439169689Skan NO_INSERT); 440169689Skan if (!slot) 441169689Skan return NULL; 442169689Skan else 443169689Skan return ((expr_pred_trans_t) *slot)->v; 444169689Skan} 445169689Skan 446169689Skan 447169689Skan/* Add the tuple mapping from {expression E, basic block PRED, vuses VUSES} to 448169689Skan value V, to the phi translation table. */ 449169689Skan 450169689Skanstatic inline void 451169689Skanphi_trans_add (tree e, tree v, basic_block pred, VEC (tree, gc) *vuses) 452169689Skan{ 453169689Skan void **slot; 454169689Skan expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d); 455169689Skan new_pair->e = e; 456169689Skan new_pair->pred = pred; 457169689Skan new_pair->vuses = vuses; 458169689Skan new_pair->v = v; 459169689Skan new_pair->hashcode = vn_compute (e, (unsigned long) pred); 460169689Skan slot = htab_find_slot_with_hash (phi_translate_table, new_pair, 461169689Skan new_pair->hashcode, INSERT); 462169689Skan if (*slot) 463169689Skan free (*slot); 464169689Skan *slot = (void *) new_pair; 465169689Skan} 466169689Skan 467169689Skan 468169689Skan/* Add expression E to the expression set of value V. */ 469169689Skan 470169689Skanvoid 471169689Skanadd_to_value (tree v, tree e) 472169689Skan{ 473169689Skan /* Constants have no expression sets. */ 474169689Skan if (is_gimple_min_invariant (v)) 475169689Skan return; 476169689Skan 477169689Skan if (VALUE_HANDLE_EXPR_SET (v) == NULL) 478169689Skan VALUE_HANDLE_EXPR_SET (v) = set_new (false); 479169689Skan 480169689Skan insert_into_set (VALUE_HANDLE_EXPR_SET (v), e); 481169689Skan} 482169689Skan 483169689Skan 484169689Skan/* Return true if value V exists in the bitmap for SET. */ 485169689Skan 486169689Skanstatic inline bool 487169689Skanvalue_exists_in_set_bitmap (value_set_t set, tree v) 488169689Skan{ 489169689Skan if (!set->values) 490169689Skan return false; 491169689Skan 492169689Skan return bitmap_bit_p (set->values, VALUE_HANDLE_ID (v)); 493169689Skan} 494169689Skan 495169689Skan 496169689Skan/* Remove value V from the bitmap for SET. */ 497169689Skan 498169689Skanstatic void 499169689Skanvalue_remove_from_set_bitmap (value_set_t set, tree v) 500169689Skan{ 501169689Skan gcc_assert (set->indexed); 502169689Skan 503169689Skan if (!set->values) 504169689Skan return; 505169689Skan 506169689Skan bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v)); 507169689Skan} 508169689Skan 509169689Skan 510169689Skan/* Insert the value number V into the bitmap of values existing in 511169689Skan SET. */ 512169689Skan 513169689Skanstatic inline void 514169689Skanvalue_insert_into_set_bitmap (value_set_t set, tree v) 515169689Skan{ 516169689Skan gcc_assert (set->indexed); 517169689Skan 518169689Skan if (set->values == NULL) 519169689Skan set->values = BITMAP_ALLOC (&grand_bitmap_obstack); 520169689Skan 521169689Skan bitmap_set_bit (set->values, VALUE_HANDLE_ID (v)); 522169689Skan} 523169689Skan 524169689Skan 525169689Skan/* Create a new bitmap set and return it. */ 526169689Skan 527169689Skanstatic bitmap_set_t 528169689Skanbitmap_set_new (void) 529169689Skan{ 530169689Skan bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool); 531169689Skan ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack); 532169689Skan ret->values = BITMAP_ALLOC (&grand_bitmap_obstack); 533169689Skan return ret; 534169689Skan} 535169689Skan 536169689Skan/* Create a new set. */ 537169689Skan 538169689Skanstatic value_set_t 539169689Skanset_new (bool indexed) 540169689Skan{ 541169689Skan value_set_t ret; 542169689Skan ret = (value_set_t) pool_alloc (value_set_pool); 543169689Skan ret->head = ret->tail = NULL; 544169689Skan ret->length = 0; 545169689Skan ret->indexed = indexed; 546169689Skan ret->values = NULL; 547169689Skan return ret; 548169689Skan} 549169689Skan 550169689Skan/* Insert an expression EXPR into a bitmapped set. */ 551169689Skan 552169689Skanstatic void 553169689Skanbitmap_insert_into_set (bitmap_set_t set, tree expr) 554169689Skan{ 555169689Skan tree val; 556169689Skan /* XXX: For now, we only let SSA_NAMES into the bitmap sets. */ 557169689Skan gcc_assert (TREE_CODE (expr) == SSA_NAME); 558169689Skan val = get_value_handle (expr); 559169689Skan 560169689Skan gcc_assert (val); 561169689Skan if (!is_gimple_min_invariant (val)) 562169689Skan { 563169689Skan bitmap_set_bit (set->values, VALUE_HANDLE_ID (val)); 564169689Skan bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr)); 565169689Skan } 566169689Skan} 567169689Skan 568169689Skan/* Insert EXPR into SET. */ 569169689Skan 570169689Skanstatic void 571169689Skaninsert_into_set (value_set_t set, tree expr) 572169689Skan{ 573169689Skan value_set_node_t newnode = (value_set_node_t) pool_alloc (value_set_node_pool); 574169689Skan tree val = get_value_handle (expr); 575169689Skan gcc_assert (val); 576169689Skan 577169689Skan if (is_gimple_min_invariant (val)) 578169689Skan return; 579169689Skan 580169689Skan /* For indexed sets, insert the value into the set value bitmap. 581169689Skan For all sets, add it to the linked list and increment the list 582169689Skan length. */ 583169689Skan if (set->indexed) 584169689Skan value_insert_into_set_bitmap (set, val); 585169689Skan 586169689Skan newnode->next = NULL; 587169689Skan newnode->expr = expr; 588169689Skan set->length ++; 589169689Skan if (set->head == NULL) 590169689Skan { 591169689Skan set->head = set->tail = newnode; 592169689Skan } 593169689Skan else 594169689Skan { 595169689Skan set->tail->next = newnode; 596169689Skan set->tail = newnode; 597169689Skan } 598169689Skan} 599169689Skan 600169689Skan/* Copy a bitmapped set ORIG, into bitmapped set DEST. */ 601169689Skan 602169689Skanstatic void 603169689Skanbitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig) 604169689Skan{ 605169689Skan bitmap_copy (dest->expressions, orig->expressions); 606169689Skan bitmap_copy (dest->values, orig->values); 607169689Skan} 608169689Skan 609169689Skan/* Perform bitmapped set operation DEST &= ORIG. */ 610169689Skan 611169689Skanstatic void 612169689Skanbitmap_set_and (bitmap_set_t dest, bitmap_set_t orig) 613169689Skan{ 614169689Skan bitmap_iterator bi; 615169689Skan unsigned int i; 616169689Skan bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack); 617169689Skan 618169689Skan bitmap_and_into (dest->values, orig->values); 619169689Skan bitmap_copy (temp, dest->expressions); 620169689Skan EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi) 621169689Skan { 622169689Skan tree name = ssa_name (i); 623169689Skan tree val = get_value_handle (name); 624169689Skan if (!bitmap_bit_p (dest->values, VALUE_HANDLE_ID (val))) 625169689Skan bitmap_clear_bit (dest->expressions, i); 626169689Skan } 627169689Skan BITMAP_FREE (temp); 628169689Skan} 629169689Skan 630169689Skan/* Perform bitmapped value set operation DEST = DEST & ~ORIG. */ 631169689Skan 632169689Skanstatic void 633169689Skanbitmap_set_and_compl (bitmap_set_t dest, bitmap_set_t orig) 634169689Skan{ 635169689Skan bitmap_iterator bi; 636169689Skan unsigned int i; 637169689Skan bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack); 638169689Skan 639169689Skan bitmap_and_compl_into (dest->values, orig->values); 640169689Skan bitmap_copy (temp, dest->expressions); 641169689Skan EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi) 642169689Skan { 643169689Skan tree name = ssa_name (i); 644169689Skan tree val = get_value_handle (name); 645169689Skan if (!bitmap_bit_p (dest->values, VALUE_HANDLE_ID (val))) 646169689Skan bitmap_clear_bit (dest->expressions, i); 647169689Skan } 648169689Skan BITMAP_FREE (temp); 649169689Skan} 650169689Skan 651169689Skan/* Return true if the bitmap set SET is empty. */ 652169689Skan 653169689Skanstatic bool 654169689Skanbitmap_set_empty_p (bitmap_set_t set) 655169689Skan{ 656169689Skan return bitmap_empty_p (set->values); 657169689Skan} 658169689Skan 659169689Skan/* Copy the set ORIG to the set DEST. */ 660169689Skan 661169689Skanstatic void 662169689Skanset_copy (value_set_t dest, value_set_t orig) 663169689Skan{ 664169689Skan value_set_node_t node; 665169689Skan 666169689Skan if (!orig || !orig->head) 667169689Skan return; 668169689Skan 669169689Skan for (node = orig->head; 670169689Skan node; 671169689Skan node = node->next) 672169689Skan { 673169689Skan insert_into_set (dest, node->expr); 674169689Skan } 675169689Skan} 676169689Skan 677169689Skan/* Remove EXPR from SET. */ 678169689Skan 679169689Skanstatic void 680169689Skanset_remove (value_set_t set, tree expr) 681169689Skan{ 682169689Skan value_set_node_t node, prev; 683169689Skan 684169689Skan /* Remove the value of EXPR from the bitmap, decrement the set 685169689Skan length, and remove it from the actual double linked list. */ 686169689Skan value_remove_from_set_bitmap (set, get_value_handle (expr)); 687169689Skan set->length--; 688169689Skan prev = NULL; 689169689Skan for (node = set->head; 690169689Skan node != NULL; 691169689Skan prev = node, node = node->next) 692169689Skan { 693169689Skan if (node->expr == expr) 694169689Skan { 695169689Skan if (prev == NULL) 696169689Skan set->head = node->next; 697169689Skan else 698169689Skan prev->next= node->next; 699169689Skan 700169689Skan if (node == set->tail) 701169689Skan set->tail = prev; 702169689Skan pool_free (value_set_node_pool, node); 703169689Skan return; 704169689Skan } 705169689Skan } 706169689Skan} 707169689Skan 708169689Skan/* Return true if SET contains the value VAL. */ 709169689Skan 710169689Skanstatic bool 711169689Skanset_contains_value (value_set_t set, tree val) 712169689Skan{ 713169689Skan /* All constants are in every set. */ 714169689Skan if (is_gimple_min_invariant (val)) 715169689Skan return true; 716169689Skan 717169689Skan if (!set || set->length == 0) 718169689Skan return false; 719169689Skan 720169689Skan return value_exists_in_set_bitmap (set, val); 721169689Skan} 722169689Skan 723169689Skan/* Return true if bitmapped set SET contains the expression EXPR. */ 724169689Skanstatic bool 725169689Skanbitmap_set_contains (bitmap_set_t set, tree expr) 726169689Skan{ 727169689Skan /* All constants are in every set. */ 728169689Skan if (is_gimple_min_invariant (get_value_handle (expr))) 729169689Skan return true; 730169689Skan 731169689Skan /* XXX: Bitmapped sets only contain SSA_NAME's for now. */ 732169689Skan if (TREE_CODE (expr) != SSA_NAME) 733169689Skan return false; 734169689Skan return bitmap_bit_p (set->expressions, SSA_NAME_VERSION (expr)); 735169689Skan} 736169689Skan 737169689Skan 738169689Skan/* Return true if bitmapped set SET contains the value VAL. */ 739169689Skan 740169689Skanstatic bool 741169689Skanbitmap_set_contains_value (bitmap_set_t set, tree val) 742169689Skan{ 743169689Skan if (is_gimple_min_invariant (val)) 744169689Skan return true; 745169689Skan return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val)); 746169689Skan} 747169689Skan 748169689Skan/* Replace an instance of value LOOKFOR with expression EXPR in SET. */ 749169689Skan 750169689Skanstatic void 751169689Skanbitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr) 752169689Skan{ 753169689Skan value_set_t exprset; 754169689Skan value_set_node_t node; 755169689Skan if (is_gimple_min_invariant (lookfor)) 756169689Skan return; 757169689Skan if (!bitmap_set_contains_value (set, lookfor)) 758169689Skan return; 759169689Skan 760169689Skan /* The number of expressions having a given value is usually 761169689Skan significantly less than the total number of expressions in SET. 762169689Skan Thus, rather than check, for each expression in SET, whether it 763169689Skan has the value LOOKFOR, we walk the reverse mapping that tells us 764169689Skan what expressions have a given value, and see if any of those 765169689Skan expressions are in our set. For large testcases, this is about 766169689Skan 5-10x faster than walking the bitmap. If this is somehow a 767169689Skan significant lose for some cases, we can choose which set to walk 768169689Skan based on the set size. */ 769169689Skan exprset = VALUE_HANDLE_EXPR_SET (lookfor); 770169689Skan for (node = exprset->head; node; node = node->next) 771169689Skan { 772169689Skan if (TREE_CODE (node->expr) == SSA_NAME) 773169689Skan { 774169689Skan if (bitmap_bit_p (set->expressions, SSA_NAME_VERSION (node->expr))) 775169689Skan { 776169689Skan bitmap_clear_bit (set->expressions, SSA_NAME_VERSION (node->expr)); 777169689Skan bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr)); 778169689Skan return; 779169689Skan } 780169689Skan } 781169689Skan } 782169689Skan} 783169689Skan 784169689Skan/* Subtract bitmapped set B from value set A, and return the new set. */ 785169689Skan 786169689Skanstatic value_set_t 787169689Skanbitmap_set_subtract_from_value_set (value_set_t a, bitmap_set_t b, 788169689Skan bool indexed) 789169689Skan{ 790169689Skan value_set_t ret = set_new (indexed); 791169689Skan value_set_node_t node; 792169689Skan for (node = a->head; 793169689Skan node; 794169689Skan node = node->next) 795169689Skan { 796169689Skan if (!bitmap_set_contains (b, node->expr)) 797169689Skan insert_into_set (ret, node->expr); 798169689Skan } 799169689Skan return ret; 800169689Skan} 801169689Skan 802169689Skan/* Return true if two sets are equal. */ 803169689Skan 804169689Skanstatic bool 805169689Skanset_equal (value_set_t a, value_set_t b) 806169689Skan{ 807169689Skan value_set_node_t node; 808169689Skan 809169689Skan if (a->length != b->length) 810169689Skan return false; 811169689Skan for (node = a->head; 812169689Skan node; 813169689Skan node = node->next) 814169689Skan { 815169689Skan if (!set_contains_value (b, get_value_handle (node->expr))) 816169689Skan return false; 817169689Skan } 818169689Skan return true; 819169689Skan} 820169689Skan 821169689Skan/* Replace an instance of EXPR's VALUE with EXPR in SET if it exists, 822169689Skan and add it otherwise. */ 823169689Skan 824169689Skanstatic void 825169689Skanbitmap_value_replace_in_set (bitmap_set_t set, tree expr) 826169689Skan{ 827169689Skan tree val = get_value_handle (expr); 828169689Skan if (bitmap_set_contains_value (set, val)) 829169689Skan bitmap_set_replace_value (set, val, expr); 830169689Skan else 831169689Skan bitmap_insert_into_set (set, expr); 832169689Skan} 833169689Skan 834169689Skan/* Insert EXPR into SET if EXPR's value is not already present in 835169689Skan SET. */ 836169689Skan 837169689Skanstatic void 838169689Skanbitmap_value_insert_into_set (bitmap_set_t set, tree expr) 839169689Skan{ 840169689Skan tree val = get_value_handle (expr); 841169689Skan 842169689Skan if (is_gimple_min_invariant (val)) 843169689Skan return; 844169689Skan 845169689Skan if (!bitmap_set_contains_value (set, val)) 846169689Skan bitmap_insert_into_set (set, expr); 847169689Skan} 848169689Skan 849169689Skan/* Insert the value for EXPR into SET, if it doesn't exist already. */ 850169689Skan 851169689Skanstatic void 852169689Skanvalue_insert_into_set (value_set_t set, tree expr) 853169689Skan{ 854169689Skan tree val = get_value_handle (expr); 855169689Skan 856169689Skan /* Constant and invariant values exist everywhere, and thus, 857169689Skan actually keeping them in the sets is pointless. */ 858169689Skan if (is_gimple_min_invariant (val)) 859169689Skan return; 860169689Skan 861169689Skan if (!set_contains_value (set, val)) 862169689Skan insert_into_set (set, expr); 863169689Skan} 864169689Skan 865169689Skan 866169689Skan/* Print out SET to OUTFILE. */ 867169689Skan 868169689Skanstatic void 869169689Skanbitmap_print_value_set (FILE *outfile, bitmap_set_t set, 870169689Skan const char *setname, int blockindex) 871169689Skan{ 872169689Skan fprintf (outfile, "%s[%d] := { ", setname, blockindex); 873169689Skan if (set) 874169689Skan { 875169689Skan bool first = true; 876169689Skan unsigned i; 877169689Skan bitmap_iterator bi; 878169689Skan 879169689Skan EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i, bi) 880169689Skan { 881169689Skan if (!first) 882169689Skan fprintf (outfile, ", "); 883169689Skan first = false; 884169689Skan print_generic_expr (outfile, ssa_name (i), 0); 885169689Skan 886169689Skan fprintf (outfile, " ("); 887169689Skan print_generic_expr (outfile, get_value_handle (ssa_name (i)), 0); 888169689Skan fprintf (outfile, ") "); 889169689Skan } 890169689Skan } 891169689Skan fprintf (outfile, " }\n"); 892169689Skan} 893169689Skan/* Print out the value_set SET to OUTFILE. */ 894169689Skan 895169689Skanstatic void 896169689Skanprint_value_set (FILE *outfile, value_set_t set, 897169689Skan const char *setname, int blockindex) 898169689Skan{ 899169689Skan value_set_node_t node; 900169689Skan fprintf (outfile, "%s[%d] := { ", setname, blockindex); 901169689Skan if (set) 902169689Skan { 903169689Skan for (node = set->head; 904169689Skan node; 905169689Skan node = node->next) 906169689Skan { 907169689Skan print_generic_expr (outfile, node->expr, 0); 908169689Skan 909169689Skan fprintf (outfile, " ("); 910169689Skan print_generic_expr (outfile, get_value_handle (node->expr), 0); 911169689Skan fprintf (outfile, ") "); 912169689Skan 913169689Skan if (node->next) 914169689Skan fprintf (outfile, ", "); 915169689Skan } 916169689Skan } 917169689Skan 918169689Skan fprintf (outfile, " }\n"); 919169689Skan} 920169689Skan 921169689Skan/* Print out the expressions that have VAL to OUTFILE. */ 922169689Skan 923169689Skanvoid 924169689Skanprint_value_expressions (FILE *outfile, tree val) 925169689Skan{ 926169689Skan if (VALUE_HANDLE_EXPR_SET (val)) 927169689Skan { 928169689Skan char s[10]; 929169689Skan sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val)); 930169689Skan print_value_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0); 931169689Skan } 932169689Skan} 933169689Skan 934169689Skan 935169689Skanvoid 936169689Skandebug_value_expressions (tree val) 937169689Skan{ 938169689Skan print_value_expressions (stderr, val); 939169689Skan} 940169689Skan 941169689Skan 942169689Skanvoid debug_value_set (value_set_t, const char *, int); 943169689Skan 944169689Skanvoid 945169689Skandebug_value_set (value_set_t set, const char *setname, int blockindex) 946169689Skan{ 947169689Skan print_value_set (stderr, set, setname, blockindex); 948169689Skan} 949169689Skan 950169689Skan/* Return the folded version of T if T, when folded, is a gimple 951169689Skan min_invariant. Otherwise, return T. */ 952169689Skan 953169689Skanstatic tree 954169689Skanfully_constant_expression (tree t) 955169689Skan{ 956169689Skan tree folded; 957169689Skan folded = fold (t); 958169689Skan if (folded && is_gimple_min_invariant (folded)) 959169689Skan return folded; 960169689Skan return t; 961169689Skan} 962169689Skan 963169689Skan/* Return a copy of a chain of nodes, chained through the TREE_CHAIN field. 964169689Skan For example, this can copy a list made of TREE_LIST nodes. 965169689Skan Allocates the nodes in list_node_pool*/ 966169689Skan 967169689Skanstatic tree 968169689Skanpool_copy_list (tree list) 969169689Skan{ 970169689Skan tree head; 971169689Skan tree prev, next; 972169689Skan 973169689Skan if (list == 0) 974169689Skan return 0; 975169689Skan head = (tree) pool_alloc (list_node_pool); 976169689Skan 977169689Skan memcpy (head, list, tree_size (list)); 978169689Skan prev = head; 979169689Skan 980169689Skan next = TREE_CHAIN (list); 981169689Skan while (next) 982169689Skan { 983169689Skan TREE_CHAIN (prev) = (tree) pool_alloc (list_node_pool); 984169689Skan memcpy (TREE_CHAIN (prev), next, tree_size (next)); 985169689Skan prev = TREE_CHAIN (prev); 986169689Skan next = TREE_CHAIN (next); 987169689Skan } 988169689Skan return head; 989169689Skan} 990169689Skan 991169689Skan/* Translate the vuses in the VUSES vector backwards through phi 992169689Skan nodes, so that they have the value they would have in BLOCK. */ 993169689Skan 994169689Skanstatic VEC(tree, gc) * 995169689Skantranslate_vuses_through_block (VEC (tree, gc) *vuses, basic_block block) 996169689Skan{ 997169689Skan tree oldvuse; 998169689Skan VEC(tree, gc) *result = NULL; 999169689Skan int i; 1000169689Skan 1001169689Skan for (i = 0; VEC_iterate (tree, vuses, i, oldvuse); i++) 1002169689Skan { 1003169689Skan tree phi = SSA_NAME_DEF_STMT (oldvuse); 1004169689Skan if (TREE_CODE (phi) == PHI_NODE) 1005169689Skan { 1006169689Skan edge e = find_edge (block, bb_for_stmt (phi)); 1007169689Skan if (e) 1008169689Skan { 1009169689Skan tree def = PHI_ARG_DEF (phi, e->dest_idx); 1010169689Skan if (def != oldvuse) 1011169689Skan { 1012169689Skan if (!result) 1013169689Skan result = VEC_copy (tree, gc, vuses); 1014169689Skan VEC_replace (tree, result, i, def); 1015169689Skan } 1016169689Skan } 1017169689Skan } 1018169689Skan } 1019169689Skan if (result) 1020169689Skan { 1021169689Skan sort_vuses (result); 1022169689Skan return result; 1023169689Skan } 1024169689Skan return vuses; 1025169689Skan 1026169689Skan} 1027169689Skan/* Translate EXPR using phis in PHIBLOCK, so that it has the values of 1028169689Skan the phis in PRED. Return NULL if we can't find a leader for each 1029169689Skan part of the translated expression. */ 1030169689Skan 1031169689Skanstatic tree 1032169689Skanphi_translate (tree expr, value_set_t set, basic_block pred, 1033169689Skan basic_block phiblock) 1034169689Skan{ 1035169689Skan tree phitrans = NULL; 1036169689Skan tree oldexpr = expr; 1037169689Skan if (expr == NULL) 1038169689Skan return NULL; 1039169689Skan 1040169689Skan if (is_gimple_min_invariant (expr)) 1041169689Skan return expr; 1042169689Skan 1043169689Skan /* Phi translations of a given expression don't change. */ 1044169689Skan if (EXPR_P (expr)) 1045169689Skan { 1046169689Skan tree vh; 1047169689Skan 1048169689Skan vh = get_value_handle (expr); 1049169689Skan if (vh && TREE_CODE (vh) == VALUE_HANDLE) 1050169689Skan phitrans = phi_trans_lookup (expr, pred, VALUE_HANDLE_VUSES (vh)); 1051169689Skan else 1052169689Skan phitrans = phi_trans_lookup (expr, pred, NULL); 1053169689Skan } 1054169689Skan else 1055169689Skan phitrans = phi_trans_lookup (expr, pred, NULL); 1056169689Skan 1057169689Skan if (phitrans) 1058169689Skan return phitrans; 1059169689Skan 1060169689Skan switch (TREE_CODE_CLASS (TREE_CODE (expr))) 1061169689Skan { 1062169689Skan case tcc_expression: 1063169689Skan { 1064169689Skan if (TREE_CODE (expr) != CALL_EXPR) 1065169689Skan return NULL; 1066169689Skan else 1067169689Skan { 1068169689Skan tree oldop0 = TREE_OPERAND (expr, 0); 1069169689Skan tree oldarglist = TREE_OPERAND (expr, 1); 1070169689Skan tree oldop2 = TREE_OPERAND (expr, 2); 1071169689Skan tree newop0; 1072169689Skan tree newarglist; 1073169689Skan tree newop2 = NULL; 1074169689Skan tree oldwalker; 1075169689Skan tree newwalker; 1076169689Skan tree newexpr; 1077169689Skan tree vh = get_value_handle (expr); 1078169689Skan bool listchanged = false; 1079237406Spfg bool invariantarg = false; 1080169689Skan VEC (tree, gc) *vuses = VALUE_HANDLE_VUSES (vh); 1081169689Skan VEC (tree, gc) *tvuses; 1082169689Skan 1083169689Skan /* Call expressions are kind of weird because they have an 1084169689Skan argument list. We don't want to value number the list 1085169689Skan as one value number, because that doesn't make much 1086169689Skan sense, and just breaks the support functions we call, 1087169689Skan which expect TREE_OPERAND (call_expr, 2) to be a 1088169689Skan TREE_LIST. */ 1089169689Skan 1090169689Skan newop0 = phi_translate (find_leader (set, oldop0), 1091169689Skan set, pred, phiblock); 1092169689Skan if (newop0 == NULL) 1093169689Skan return NULL; 1094169689Skan if (oldop2) 1095169689Skan { 1096169689Skan newop2 = phi_translate (find_leader (set, oldop2), 1097169689Skan set, pred, phiblock); 1098169689Skan if (newop2 == NULL) 1099169689Skan return NULL; 1100169689Skan } 1101169689Skan 1102169689Skan /* phi translate the argument list piece by piece. 1103169689Skan 1104169689Skan We could actually build the list piece by piece here, 1105169689Skan but it's likely to not be worth the memory we will save, 1106169689Skan unless you have millions of call arguments. */ 1107169689Skan 1108169689Skan newarglist = pool_copy_list (oldarglist); 1109169689Skan for (oldwalker = oldarglist, newwalker = newarglist; 1110169689Skan oldwalker && newwalker; 1111169689Skan oldwalker = TREE_CHAIN (oldwalker), 1112169689Skan newwalker = TREE_CHAIN (newwalker)) 1113169689Skan { 1114169689Skan 1115169689Skan tree oldval = TREE_VALUE (oldwalker); 1116169689Skan tree newval; 1117169689Skan if (oldval) 1118169689Skan { 1119169689Skan /* This may seem like a weird place for this 1120169689Skan check, but it's actually the easiest place to 1121169689Skan do it. We can't do it lower on in the 1122169689Skan recursion because it's valid for pieces of a 1123169689Skan component ref to be of AGGREGATE_TYPE, as long 1124169689Skan as the outermost one is not. 1125169689Skan To avoid *that* case, we have a check for 1126169689Skan AGGREGATE_TYPE_P in insert_aux. However, that 1127169689Skan check will *not* catch this case because here 1128169689Skan it occurs in the argument list. */ 1129169689Skan if (AGGREGATE_TYPE_P (TREE_TYPE (oldval))) 1130169689Skan return NULL; 1131169689Skan newval = phi_translate (find_leader (set, oldval), 1132169689Skan set, pred, phiblock); 1133169689Skan if (newval == NULL) 1134169689Skan return NULL; 1135169689Skan if (newval != oldval) 1136169689Skan { 1137169689Skan listchanged = true; 1138237406Spfg invariantarg |= is_gimple_min_invariant (newval); 1139169689Skan TREE_VALUE (newwalker) = get_value_handle (newval); 1140169689Skan } 1141169689Skan } 1142169689Skan } 1143237406Spfg 1144237406Spfg /* In case of new invariant args we might try to fold the call 1145237406Spfg again. */ 1146237406Spfg if (invariantarg) 1147237406Spfg { 1148237406Spfg tree tmp = fold_ternary (CALL_EXPR, TREE_TYPE (expr), 1149237406Spfg newop0, newarglist, newop2); 1150237406Spfg if (tmp) 1151237406Spfg { 1152237406Spfg STRIP_TYPE_NOPS (tmp); 1153237406Spfg if (is_gimple_min_invariant (tmp)) 1154237406Spfg return tmp; 1155237406Spfg } 1156237406Spfg } 1157237406Spfg 1158169689Skan if (listchanged) 1159169689Skan vn_lookup_or_add (newarglist, NULL); 1160169689Skan 1161169689Skan tvuses = translate_vuses_through_block (vuses, pred); 1162169689Skan 1163169689Skan if (listchanged || (newop0 != oldop0) || (oldop2 != newop2) 1164169689Skan || vuses != tvuses) 1165169689Skan { 1166169689Skan newexpr = (tree) pool_alloc (expression_node_pool); 1167169689Skan memcpy (newexpr, expr, tree_size (expr)); 1168169689Skan TREE_OPERAND (newexpr, 0) = newop0 == oldop0 ? oldop0 : get_value_handle (newop0); 1169169689Skan TREE_OPERAND (newexpr, 1) = listchanged ? newarglist : oldarglist; 1170169689Skan TREE_OPERAND (newexpr, 2) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2); 1171169689Skan newexpr->common.ann = NULL; 1172169689Skan vn_lookup_or_add_with_vuses (newexpr, tvuses); 1173169689Skan expr = newexpr; 1174169689Skan phi_trans_add (oldexpr, newexpr, pred, tvuses); 1175169689Skan } 1176169689Skan } 1177169689Skan } 1178169689Skan return expr; 1179169689Skan 1180169689Skan case tcc_declaration: 1181169689Skan { 1182169689Skan VEC (tree, gc) * oldvuses = NULL; 1183169689Skan VEC (tree, gc) * newvuses = NULL; 1184169689Skan 1185169689Skan oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr)); 1186169689Skan if (oldvuses) 1187169689Skan newvuses = translate_vuses_through_block (oldvuses, pred); 1188169689Skan 1189169689Skan if (oldvuses != newvuses) 1190169689Skan vn_lookup_or_add_with_vuses (expr, newvuses); 1191169689Skan 1192169689Skan phi_trans_add (oldexpr, expr, pred, newvuses); 1193169689Skan } 1194169689Skan return expr; 1195169689Skan 1196169689Skan case tcc_reference: 1197169689Skan { 1198169689Skan tree oldop0 = TREE_OPERAND (expr, 0); 1199169689Skan tree oldop1 = NULL; 1200169689Skan tree newop0; 1201169689Skan tree newop1 = NULL; 1202169689Skan tree oldop2 = NULL; 1203169689Skan tree newop2 = NULL; 1204169689Skan tree oldop3 = NULL; 1205169689Skan tree newop3 = NULL; 1206169689Skan tree newexpr; 1207169689Skan VEC (tree, gc) * oldvuses = NULL; 1208169689Skan VEC (tree, gc) * newvuses = NULL; 1209169689Skan 1210169689Skan if (TREE_CODE (expr) != INDIRECT_REF 1211169689Skan && TREE_CODE (expr) != COMPONENT_REF 1212169689Skan && TREE_CODE (expr) != ARRAY_REF) 1213169689Skan return NULL; 1214169689Skan 1215169689Skan newop0 = phi_translate (find_leader (set, oldop0), 1216169689Skan set, pred, phiblock); 1217169689Skan if (newop0 == NULL) 1218169689Skan return NULL; 1219169689Skan 1220169689Skan if (TREE_CODE (expr) == ARRAY_REF) 1221169689Skan { 1222169689Skan oldop1 = TREE_OPERAND (expr, 1); 1223169689Skan newop1 = phi_translate (find_leader (set, oldop1), 1224169689Skan set, pred, phiblock); 1225169689Skan 1226169689Skan if (newop1 == NULL) 1227169689Skan return NULL; 1228169689Skan oldop2 = TREE_OPERAND (expr, 2); 1229169689Skan if (oldop2) 1230169689Skan { 1231169689Skan newop2 = phi_translate (find_leader (set, oldop2), 1232169689Skan set, pred, phiblock); 1233169689Skan 1234169689Skan if (newop2 == NULL) 1235169689Skan return NULL; 1236169689Skan } 1237169689Skan oldop3 = TREE_OPERAND (expr, 3); 1238169689Skan if (oldop3) 1239169689Skan { 1240169689Skan newop3 = phi_translate (find_leader (set, oldop3), 1241169689Skan set, pred, phiblock); 1242169689Skan 1243169689Skan if (newop3 == NULL) 1244169689Skan return NULL; 1245169689Skan } 1246169689Skan } 1247169689Skan 1248169689Skan oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr)); 1249169689Skan if (oldvuses) 1250169689Skan newvuses = translate_vuses_through_block (oldvuses, pred); 1251169689Skan 1252169689Skan if (newop0 != oldop0 || newvuses != oldvuses 1253169689Skan || newop1 != oldop1 1254169689Skan || newop2 != oldop2 1255169689Skan || newop3 != oldop3) 1256169689Skan { 1257169689Skan tree t; 1258169689Skan 1259169689Skan newexpr = pool_alloc (reference_node_pool); 1260169689Skan memcpy (newexpr, expr, tree_size (expr)); 1261169689Skan TREE_OPERAND (newexpr, 0) = get_value_handle (newop0); 1262169689Skan if (TREE_CODE (expr) == ARRAY_REF) 1263169689Skan { 1264169689Skan TREE_OPERAND (newexpr, 1) = get_value_handle (newop1); 1265169689Skan if (newop2) 1266169689Skan TREE_OPERAND (newexpr, 2) = get_value_handle (newop2); 1267169689Skan if (newop3) 1268169689Skan TREE_OPERAND (newexpr, 3) = get_value_handle (newop3); 1269169689Skan } 1270169689Skan 1271169689Skan t = fully_constant_expression (newexpr); 1272169689Skan 1273169689Skan if (t != newexpr) 1274169689Skan { 1275169689Skan pool_free (reference_node_pool, newexpr); 1276169689Skan newexpr = t; 1277169689Skan } 1278169689Skan else 1279169689Skan { 1280169689Skan newexpr->common.ann = NULL; 1281169689Skan vn_lookup_or_add_with_vuses (newexpr, newvuses); 1282169689Skan } 1283169689Skan expr = newexpr; 1284169689Skan phi_trans_add (oldexpr, newexpr, pred, newvuses); 1285169689Skan } 1286169689Skan } 1287169689Skan return expr; 1288169689Skan break; 1289169689Skan 1290169689Skan case tcc_binary: 1291169689Skan case tcc_comparison: 1292169689Skan { 1293169689Skan tree oldop1 = TREE_OPERAND (expr, 0); 1294169689Skan tree oldop2 = TREE_OPERAND (expr, 1); 1295169689Skan tree newop1; 1296169689Skan tree newop2; 1297169689Skan tree newexpr; 1298169689Skan 1299169689Skan newop1 = phi_translate (find_leader (set, oldop1), 1300169689Skan set, pred, phiblock); 1301169689Skan if (newop1 == NULL) 1302169689Skan return NULL; 1303169689Skan newop2 = phi_translate (find_leader (set, oldop2), 1304169689Skan set, pred, phiblock); 1305169689Skan if (newop2 == NULL) 1306169689Skan return NULL; 1307169689Skan if (newop1 != oldop1 || newop2 != oldop2) 1308169689Skan { 1309169689Skan tree t; 1310169689Skan newexpr = (tree) pool_alloc (binary_node_pool); 1311169689Skan memcpy (newexpr, expr, tree_size (expr)); 1312169689Skan TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1); 1313169689Skan TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2); 1314169689Skan t = fully_constant_expression (newexpr); 1315169689Skan if (t != newexpr) 1316169689Skan { 1317169689Skan pool_free (binary_node_pool, newexpr); 1318169689Skan newexpr = t; 1319169689Skan } 1320169689Skan else 1321169689Skan { 1322169689Skan newexpr->common.ann = NULL; 1323169689Skan vn_lookup_or_add (newexpr, NULL); 1324169689Skan } 1325169689Skan expr = newexpr; 1326169689Skan phi_trans_add (oldexpr, newexpr, pred, NULL); 1327169689Skan } 1328169689Skan } 1329169689Skan return expr; 1330169689Skan 1331169689Skan case tcc_unary: 1332169689Skan { 1333169689Skan tree oldop1 = TREE_OPERAND (expr, 0); 1334169689Skan tree newop1; 1335169689Skan tree newexpr; 1336169689Skan 1337169689Skan newop1 = phi_translate (find_leader (set, oldop1), 1338169689Skan set, pred, phiblock); 1339169689Skan if (newop1 == NULL) 1340169689Skan return NULL; 1341169689Skan if (newop1 != oldop1) 1342169689Skan { 1343169689Skan tree t; 1344169689Skan newexpr = (tree) pool_alloc (unary_node_pool); 1345169689Skan memcpy (newexpr, expr, tree_size (expr)); 1346169689Skan TREE_OPERAND (newexpr, 0) = get_value_handle (newop1); 1347169689Skan t = fully_constant_expression (newexpr); 1348169689Skan if (t != newexpr) 1349169689Skan { 1350169689Skan pool_free (unary_node_pool, newexpr); 1351169689Skan newexpr = t; 1352169689Skan } 1353169689Skan else 1354169689Skan { 1355169689Skan newexpr->common.ann = NULL; 1356169689Skan vn_lookup_or_add (newexpr, NULL); 1357169689Skan } 1358169689Skan expr = newexpr; 1359169689Skan phi_trans_add (oldexpr, newexpr, pred, NULL); 1360169689Skan } 1361169689Skan } 1362169689Skan return expr; 1363169689Skan 1364169689Skan case tcc_exceptional: 1365169689Skan { 1366169689Skan tree phi = NULL; 1367169689Skan edge e; 1368169689Skan gcc_assert (TREE_CODE (expr) == SSA_NAME); 1369169689Skan if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE) 1370169689Skan phi = SSA_NAME_DEF_STMT (expr); 1371169689Skan else 1372169689Skan return expr; 1373169689Skan 1374169689Skan e = find_edge (pred, bb_for_stmt (phi)); 1375169689Skan if (e) 1376169689Skan { 1377169689Skan if (is_undefined_value (PHI_ARG_DEF (phi, e->dest_idx))) 1378169689Skan return NULL; 1379169689Skan vn_lookup_or_add (PHI_ARG_DEF (phi, e->dest_idx), NULL); 1380169689Skan return PHI_ARG_DEF (phi, e->dest_idx); 1381169689Skan } 1382169689Skan } 1383169689Skan return expr; 1384169689Skan 1385169689Skan default: 1386169689Skan gcc_unreachable (); 1387169689Skan } 1388169689Skan} 1389169689Skan 1390169689Skan/* For each expression in SET, translate the value handles through phi nodes 1391169689Skan in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting 1392169689Skan expressions in DEST. */ 1393169689Skan 1394169689Skanstatic void 1395169689Skanphi_translate_set (value_set_t dest, value_set_t set, basic_block pred, 1396169689Skan basic_block phiblock) 1397169689Skan{ 1398169689Skan value_set_node_t node; 1399169689Skan for (node = set->head; 1400169689Skan node; 1401169689Skan node = node->next) 1402169689Skan { 1403169689Skan tree translated; 1404169689Skan 1405169689Skan translated = phi_translate (node->expr, set, pred, phiblock); 1406169689Skan 1407169689Skan /* Don't add constants or empty translations to the cache, since 1408169689Skan we won't look them up that way, or use the result, anyway. */ 1409169689Skan if (translated && !is_gimple_min_invariant (translated)) 1410169689Skan { 1411169689Skan tree vh = get_value_handle (translated); 1412169689Skan VEC (tree, gc) *vuses; 1413169689Skan 1414169689Skan /* The value handle itself may also be an invariant, in 1415169689Skan which case, it has no vuses. */ 1416169689Skan vuses = !is_gimple_min_invariant (vh) 1417169689Skan ? VALUE_HANDLE_VUSES (vh) : NULL; 1418169689Skan phi_trans_add (node->expr, translated, pred, vuses); 1419169689Skan } 1420169689Skan 1421169689Skan if (translated != NULL) 1422169689Skan value_insert_into_set (dest, translated); 1423169689Skan } 1424169689Skan} 1425169689Skan 1426169689Skan/* Find the leader for a value (i.e., the name representing that 1427169689Skan value) in a given set, and return it. Return NULL if no leader is 1428169689Skan found. */ 1429169689Skan 1430169689Skanstatic tree 1431169689Skanbitmap_find_leader (bitmap_set_t set, tree val) 1432169689Skan{ 1433169689Skan if (val == NULL) 1434169689Skan return NULL; 1435169689Skan 1436169689Skan if (is_gimple_min_invariant (val)) 1437169689Skan return val; 1438169689Skan if (bitmap_set_contains_value (set, val)) 1439169689Skan { 1440169689Skan /* Rather than walk the entire bitmap of expressions, and see 1441169689Skan whether any of them has the value we are looking for, we look 1442169689Skan at the reverse mapping, which tells us the set of expressions 1443169689Skan that have a given value (IE value->expressions with that 1444169689Skan value) and see if any of those expressions are in our set. 1445169689Skan The number of expressions per value is usually significantly 1446169689Skan less than the number of expressions in the set. In fact, for 1447169689Skan large testcases, doing it this way is roughly 5-10x faster 1448169689Skan than walking the bitmap. 1449169689Skan If this is somehow a significant lose for some cases, we can 1450169689Skan choose which set to walk based on which set is smaller. */ 1451169689Skan value_set_t exprset; 1452169689Skan value_set_node_t node; 1453169689Skan exprset = VALUE_HANDLE_EXPR_SET (val); 1454169689Skan for (node = exprset->head; node; node = node->next) 1455169689Skan { 1456169689Skan if (TREE_CODE (node->expr) == SSA_NAME) 1457169689Skan { 1458169689Skan if (bitmap_bit_p (set->expressions, 1459169689Skan SSA_NAME_VERSION (node->expr))) 1460169689Skan return node->expr; 1461169689Skan } 1462169689Skan } 1463169689Skan } 1464169689Skan return NULL; 1465169689Skan} 1466169689Skan 1467169689Skan 1468169689Skan/* Find the leader for a value (i.e., the name representing that 1469169689Skan value) in a given set, and return it. Return NULL if no leader is 1470169689Skan found. */ 1471169689Skan 1472169689Skanstatic tree 1473169689Skanfind_leader (value_set_t set, tree val) 1474169689Skan{ 1475169689Skan value_set_node_t node; 1476169689Skan 1477169689Skan if (val == NULL) 1478169689Skan return NULL; 1479169689Skan 1480169689Skan /* Constants represent themselves. */ 1481169689Skan if (is_gimple_min_invariant (val)) 1482169689Skan return val; 1483169689Skan 1484169689Skan if (set->length == 0) 1485169689Skan return NULL; 1486169689Skan 1487169689Skan if (value_exists_in_set_bitmap (set, val)) 1488169689Skan { 1489169689Skan for (node = set->head; 1490169689Skan node; 1491169689Skan node = node->next) 1492169689Skan { 1493169689Skan if (get_value_handle (node->expr) == val) 1494169689Skan return node->expr; 1495169689Skan } 1496169689Skan } 1497169689Skan 1498169689Skan return NULL; 1499169689Skan} 1500169689Skan 1501169689Skan/* Given the vuse representative map, MAP, and an SSA version number, 1502169689Skan ID, return the bitmap of names ID represents, or NULL, if none 1503169689Skan exists. */ 1504169689Skan 1505169689Skanstatic bitmap 1506169689Skanget_representative (bitmap *map, int id) 1507169689Skan{ 1508169689Skan if (map[id] != NULL) 1509169689Skan return map[id]; 1510169689Skan return NULL; 1511169689Skan} 1512169689Skan 1513169689Skan/* A vuse is anticipable at the top of block x, from the bottom of the 1514169689Skan block, if it reaches the top of the block, and is not killed in the 1515169689Skan block. In effect, we are trying to see if the vuse is transparent 1516169689Skan backwards in the block. */ 1517169689Skan 1518169689Skanstatic bool 1519169689Skanvuses_dies_in_block_x (VEC (tree, gc) *vuses, basic_block block) 1520169689Skan{ 1521169689Skan int i; 1522169689Skan tree vuse; 1523169689Skan 1524169689Skan for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++) 1525169689Skan { 1526169689Skan /* Any places where this is too conservative, are places 1527169689Skan where we created a new version and shouldn't have. */ 1528169689Skan 1529169689Skan if (!bitmap_bit_p (RVUSE_IN (block), SSA_NAME_VERSION (vuse)) 1530169689Skan || bitmap_bit_p (RVUSE_KILL (block), SSA_NAME_VERSION (vuse))) 1531169689Skan return true; 1532169689Skan } 1533169689Skan return false; 1534169689Skan} 1535169689Skan 1536169689Skan/* Determine if the expression EXPR is valid in SET. This means that 1537169689Skan we have a leader for each part of the expression (if it consists of 1538169689Skan values), or the expression is an SSA_NAME. 1539169689Skan 1540169689Skan NB: We never should run into a case where we have SSA_NAME + 1541169689Skan SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on, 1542169689Skan the ANTIC sets, will only ever have SSA_NAME's or value expressions 1543169689Skan (IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */ 1544169689Skan 1545169689Skanstatic bool 1546169689Skanvalid_in_set (value_set_t set, tree expr, basic_block block) 1547169689Skan{ 1548169689Skan tree vh = get_value_handle (expr); 1549169689Skan switch (TREE_CODE_CLASS (TREE_CODE (expr))) 1550169689Skan { 1551169689Skan case tcc_binary: 1552169689Skan case tcc_comparison: 1553169689Skan { 1554169689Skan tree op1 = TREE_OPERAND (expr, 0); 1555169689Skan tree op2 = TREE_OPERAND (expr, 1); 1556169689Skan return set_contains_value (set, op1) && set_contains_value (set, op2); 1557169689Skan } 1558169689Skan 1559169689Skan case tcc_unary: 1560169689Skan { 1561169689Skan tree op1 = TREE_OPERAND (expr, 0); 1562169689Skan return set_contains_value (set, op1); 1563169689Skan } 1564169689Skan 1565169689Skan case tcc_expression: 1566169689Skan { 1567169689Skan if (TREE_CODE (expr) == CALL_EXPR) 1568169689Skan { 1569169689Skan tree op0 = TREE_OPERAND (expr, 0); 1570169689Skan tree arglist = TREE_OPERAND (expr, 1); 1571169689Skan tree op2 = TREE_OPERAND (expr, 2); 1572169689Skan 1573169689Skan /* Check the non-list operands first. */ 1574169689Skan if (!set_contains_value (set, op0) 1575169689Skan || (op2 && !set_contains_value (set, op2))) 1576169689Skan return false; 1577169689Skan 1578169689Skan /* Now check the operands. */ 1579169689Skan for (; arglist; arglist = TREE_CHAIN (arglist)) 1580169689Skan { 1581169689Skan if (!set_contains_value (set, TREE_VALUE (arglist))) 1582169689Skan return false; 1583169689Skan } 1584169689Skan return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh), block); 1585169689Skan } 1586169689Skan return false; 1587169689Skan } 1588169689Skan 1589169689Skan case tcc_reference: 1590169689Skan { 1591169689Skan if (TREE_CODE (expr) == INDIRECT_REF 1592169689Skan || TREE_CODE (expr) == COMPONENT_REF 1593169689Skan || TREE_CODE (expr) == ARRAY_REF) 1594169689Skan { 1595169689Skan tree op0 = TREE_OPERAND (expr, 0); 1596169689Skan gcc_assert (is_gimple_min_invariant (op0) 1597169689Skan || TREE_CODE (op0) == VALUE_HANDLE); 1598169689Skan if (!set_contains_value (set, op0)) 1599169689Skan return false; 1600169689Skan if (TREE_CODE (expr) == ARRAY_REF) 1601169689Skan { 1602169689Skan tree op1 = TREE_OPERAND (expr, 1); 1603169689Skan tree op2 = TREE_OPERAND (expr, 2); 1604169689Skan tree op3 = TREE_OPERAND (expr, 3); 1605169689Skan gcc_assert (is_gimple_min_invariant (op1) 1606169689Skan || TREE_CODE (op1) == VALUE_HANDLE); 1607169689Skan if (!set_contains_value (set, op1)) 1608169689Skan return false; 1609169689Skan gcc_assert (!op2 || is_gimple_min_invariant (op2) 1610169689Skan || TREE_CODE (op2) == VALUE_HANDLE); 1611169689Skan if (op2 1612169689Skan && !set_contains_value (set, op2)) 1613169689Skan return false; 1614169689Skan gcc_assert (!op3 || is_gimple_min_invariant (op3) 1615169689Skan || TREE_CODE (op3) == VALUE_HANDLE); 1616169689Skan if (op3 1617169689Skan && !set_contains_value (set, op3)) 1618169689Skan return false; 1619169689Skan } 1620169689Skan return set_contains_value (ANTIC_SAFE_LOADS (block), 1621169689Skan vh) 1622169689Skan || !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh), 1623169689Skan block); 1624169689Skan } 1625169689Skan } 1626169689Skan return false; 1627169689Skan 1628169689Skan case tcc_exceptional: 1629169689Skan gcc_assert (TREE_CODE (expr) == SSA_NAME); 1630169689Skan return true; 1631169689Skan 1632169689Skan case tcc_declaration: 1633169689Skan return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh), block); 1634169689Skan 1635169689Skan default: 1636169689Skan /* No other cases should be encountered. */ 1637169689Skan gcc_unreachable (); 1638169689Skan } 1639169689Skan} 1640169689Skan 1641169689Skan/* Clean the set of expressions that are no longer valid in SET. This 1642169689Skan means expressions that are made up of values we have no leaders for 1643169689Skan in SET. */ 1644169689Skan 1645169689Skanstatic void 1646169689Skanclean (value_set_t set, basic_block block) 1647169689Skan{ 1648169689Skan value_set_node_t node; 1649169689Skan value_set_node_t next; 1650169689Skan node = set->head; 1651169689Skan while (node) 1652169689Skan { 1653169689Skan next = node->next; 1654169689Skan if (!valid_in_set (set, node->expr, block)) 1655169689Skan set_remove (set, node->expr); 1656169689Skan node = next; 1657169689Skan } 1658169689Skan} 1659169689Skan 1660169689Skanstatic sbitmap has_abnormal_preds; 1661169689Skan 1662169689Skan/* Compute the ANTIC set for BLOCK. 1663169689Skan 1664169689Skan If succs(BLOCK) > 1 then 1665169689Skan ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK) 1666169689Skan else if succs(BLOCK) == 1 then 1667169689Skan ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) 1668169689Skan 1669169689Skan ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK]) 1670169689Skan 1671169689Skan XXX: It would be nice to either write a set_clear, and use it for 1672169689Skan ANTIC_OUT, or to mark the antic_out set as deleted at the end 1673169689Skan of this routine, so that the pool can hand the same memory back out 1674169689Skan again for the next ANTIC_OUT. */ 1675169689Skan 1676169689Skanstatic bool 1677169689Skancompute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge) 1678169689Skan{ 1679169689Skan basic_block son; 1680169689Skan bool changed = false; 1681169689Skan value_set_t S, old, ANTIC_OUT; 1682169689Skan value_set_node_t node; 1683169689Skan 1684169689Skan ANTIC_OUT = S = NULL; 1685169689Skan 1686169689Skan /* If any edges from predecessors are abnormal, antic_in is empty, 1687169689Skan so do nothing. */ 1688169689Skan if (block_has_abnormal_pred_edge) 1689169689Skan goto maybe_dump_sets; 1690169689Skan 1691169689Skan old = set_new (false); 1692169689Skan set_copy (old, ANTIC_IN (block)); 1693169689Skan ANTIC_OUT = set_new (true); 1694169689Skan 1695169689Skan /* If the block has no successors, ANTIC_OUT is empty. */ 1696169689Skan if (EDGE_COUNT (block->succs) == 0) 1697169689Skan ; 1698169689Skan /* If we have one successor, we could have some phi nodes to 1699169689Skan translate through. */ 1700169689Skan else if (single_succ_p (block)) 1701169689Skan { 1702169689Skan phi_translate_set (ANTIC_OUT, ANTIC_IN (single_succ (block)), 1703169689Skan block, single_succ (block)); 1704169689Skan } 1705169689Skan /* If we have multiple successors, we take the intersection of all of 1706169689Skan them. */ 1707169689Skan else 1708169689Skan { 1709169689Skan VEC(basic_block, heap) * worklist; 1710169689Skan edge e; 1711169689Skan size_t i; 1712169689Skan basic_block bprime, first; 1713169689Skan edge_iterator ei; 1714169689Skan 1715169689Skan worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs)); 1716169689Skan FOR_EACH_EDGE (e, ei, block->succs) 1717169689Skan VEC_quick_push (basic_block, worklist, e->dest); 1718169689Skan first = VEC_index (basic_block, worklist, 0); 1719169689Skan set_copy (ANTIC_OUT, ANTIC_IN (first)); 1720169689Skan 1721169689Skan for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++) 1722169689Skan { 1723169689Skan node = ANTIC_OUT->head; 1724169689Skan while (node) 1725169689Skan { 1726169689Skan tree val; 1727169689Skan value_set_node_t next = node->next; 1728169689Skan 1729169689Skan val = get_value_handle (node->expr); 1730169689Skan if (!set_contains_value (ANTIC_IN (bprime), val)) 1731169689Skan set_remove (ANTIC_OUT, node->expr); 1732169689Skan node = next; 1733169689Skan } 1734169689Skan } 1735169689Skan VEC_free (basic_block, heap, worklist); 1736169689Skan } 1737169689Skan 1738169689Skan /* Generate ANTIC_OUT - TMP_GEN. */ 1739169689Skan S = bitmap_set_subtract_from_value_set (ANTIC_OUT, TMP_GEN (block), false); 1740169689Skan 1741169689Skan /* Start ANTIC_IN with EXP_GEN - TMP_GEN */ 1742169689Skan ANTIC_IN (block) = bitmap_set_subtract_from_value_set (EXP_GEN (block), 1743169689Skan TMP_GEN (block), 1744169689Skan true); 1745169689Skan 1746169689Skan /* Then union in the ANTIC_OUT - TMP_GEN values, 1747169689Skan to get ANTIC_OUT U EXP_GEN - TMP_GEN */ 1748169689Skan for (node = S->head; node; node = node->next) 1749169689Skan value_insert_into_set (ANTIC_IN (block), node->expr); 1750169689Skan 1751169689Skan clean (ANTIC_IN (block), block); 1752169689Skan if (!set_equal (old, ANTIC_IN (block))) 1753169689Skan changed = true; 1754169689Skan 1755169689Skan maybe_dump_sets: 1756169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1757169689Skan { 1758169689Skan if (ANTIC_OUT) 1759169689Skan print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index); 1760169689Skan 1761169689Skan if (ANTIC_SAFE_LOADS (block)) 1762169689Skan print_value_set (dump_file, ANTIC_SAFE_LOADS (block), 1763169689Skan "ANTIC_SAFE_LOADS", block->index); 1764169689Skan print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index); 1765169689Skan 1766169689Skan if (S) 1767169689Skan print_value_set (dump_file, S, "S", block->index); 1768169689Skan } 1769169689Skan 1770169689Skan for (son = first_dom_son (CDI_POST_DOMINATORS, block); 1771169689Skan son; 1772169689Skan son = next_dom_son (CDI_POST_DOMINATORS, son)) 1773169689Skan { 1774169689Skan changed |= compute_antic_aux (son, 1775169689Skan TEST_BIT (has_abnormal_preds, son->index)); 1776169689Skan } 1777169689Skan return changed; 1778169689Skan} 1779169689Skan 1780169689Skan/* Compute ANTIC sets. */ 1781169689Skan 1782169689Skanstatic void 1783169689Skancompute_antic (void) 1784169689Skan{ 1785169689Skan bool changed = true; 1786169689Skan int num_iterations = 0; 1787169689Skan basic_block block; 1788169689Skan 1789169689Skan /* If any predecessor edges are abnormal, we punt, so antic_in is empty. 1790169689Skan We pre-build the map of blocks with incoming abnormal edges here. */ 1791169689Skan has_abnormal_preds = sbitmap_alloc (last_basic_block); 1792169689Skan sbitmap_zero (has_abnormal_preds); 1793169689Skan FOR_EACH_BB (block) 1794169689Skan { 1795169689Skan edge_iterator ei; 1796169689Skan edge e; 1797169689Skan 1798169689Skan FOR_EACH_EDGE (e, ei, block->preds) 1799169689Skan if (e->flags & EDGE_ABNORMAL) 1800169689Skan { 1801169689Skan SET_BIT (has_abnormal_preds, block->index); 1802169689Skan break; 1803169689Skan } 1804169689Skan 1805169689Skan /* While we are here, give empty ANTIC_IN sets to each block. */ 1806169689Skan ANTIC_IN (block) = set_new (true); 1807169689Skan } 1808169689Skan /* At the exit block we anticipate nothing. */ 1809169689Skan ANTIC_IN (EXIT_BLOCK_PTR) = set_new (true); 1810169689Skan 1811169689Skan while (changed) 1812169689Skan { 1813169689Skan num_iterations++; 1814169689Skan changed = false; 1815169689Skan changed = compute_antic_aux (EXIT_BLOCK_PTR, false); 1816169689Skan } 1817169689Skan 1818169689Skan sbitmap_free (has_abnormal_preds); 1819169689Skan 1820169689Skan if (dump_file && (dump_flags & TDF_STATS)) 1821169689Skan fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations); 1822169689Skan} 1823169689Skan 1824169689Skan/* Print the names represented by the bitmap NAMES, to the file OUT. */ 1825169689Skanstatic void 1826169689Skandump_bitmap_of_names (FILE *out, bitmap names) 1827169689Skan{ 1828169689Skan bitmap_iterator bi; 1829169689Skan unsigned int i; 1830169689Skan 1831169689Skan fprintf (out, " { "); 1832169689Skan EXECUTE_IF_SET_IN_BITMAP (names, 0, i, bi) 1833169689Skan { 1834169689Skan print_generic_expr (out, ssa_name (i), 0); 1835169689Skan fprintf (out, " "); 1836169689Skan } 1837169689Skan fprintf (out, "}\n"); 1838169689Skan} 1839169689Skan 1840169689Skan /* Compute a set of representative vuse versions for each phi. This 1841169689Skan is so we can compute conservative kill sets in terms of all vuses 1842169689Skan that are killed, instead of continually walking chains. 1843169689Skan 1844169689Skan We also have to be able kill all names associated with a phi when 1845169689Skan the phi dies in order to ensure we don't generate overlapping 1846169689Skan live ranges, which are not allowed in virtual SSA. */ 1847169689Skan 1848169689Skanstatic bitmap *vuse_names; 1849169689Skanstatic void 1850169689Skancompute_vuse_representatives (void) 1851169689Skan{ 1852169689Skan tree phi; 1853169689Skan basic_block bb; 1854169689Skan VEC (tree, heap) *phis = NULL; 1855169689Skan bool changed = true; 1856169689Skan size_t i; 1857169689Skan 1858169689Skan FOR_EACH_BB (bb) 1859169689Skan { 1860169689Skan for (phi = phi_nodes (bb); 1861169689Skan phi; 1862169689Skan phi = PHI_CHAIN (phi)) 1863169689Skan if (!is_gimple_reg (PHI_RESULT (phi))) 1864169689Skan VEC_safe_push (tree, heap, phis, phi); 1865169689Skan } 1866169689Skan 1867169689Skan while (changed) 1868169689Skan { 1869169689Skan changed = false; 1870169689Skan 1871169689Skan for (i = 0; VEC_iterate (tree, phis, i, phi); i++) 1872169689Skan { 1873169689Skan size_t ver = SSA_NAME_VERSION (PHI_RESULT (phi)); 1874169689Skan use_operand_p usep; 1875169689Skan ssa_op_iter iter; 1876169689Skan 1877169689Skan if (vuse_names[ver] == NULL) 1878169689Skan { 1879169689Skan vuse_names[ver] = BITMAP_ALLOC (&grand_bitmap_obstack); 1880169689Skan bitmap_set_bit (vuse_names[ver], ver); 1881169689Skan } 1882169689Skan FOR_EACH_PHI_ARG (usep, phi, iter, SSA_OP_ALL_USES) 1883169689Skan { 1884169689Skan tree use = USE_FROM_PTR (usep); 1885169689Skan bitmap usebitmap = get_representative (vuse_names, 1886169689Skan SSA_NAME_VERSION (use)); 1887169689Skan if (usebitmap != NULL) 1888169689Skan { 1889169689Skan changed |= bitmap_ior_into (vuse_names[ver], 1890169689Skan usebitmap); 1891169689Skan } 1892169689Skan else 1893169689Skan { 1894169689Skan changed |= !bitmap_bit_p (vuse_names[ver], 1895169689Skan SSA_NAME_VERSION (use)); 1896169689Skan if (changed) 1897169689Skan bitmap_set_bit (vuse_names[ver], 1898169689Skan SSA_NAME_VERSION (use)); 1899169689Skan } 1900169689Skan } 1901169689Skan } 1902169689Skan } 1903169689Skan 1904169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1905169689Skan for (i = 0; VEC_iterate (tree, phis, i, phi); i++) 1906169689Skan { 1907169689Skan bitmap reps = get_representative (vuse_names, 1908169689Skan SSA_NAME_VERSION (PHI_RESULT (phi))); 1909169689Skan if (reps) 1910169689Skan { 1911169689Skan print_generic_expr (dump_file, PHI_RESULT (phi), 0); 1912169689Skan fprintf (dump_file, " represents "); 1913169689Skan dump_bitmap_of_names (dump_file, reps); 1914169689Skan } 1915169689Skan } 1916169689Skan VEC_free (tree, heap, phis); 1917169689Skan} 1918169689Skan 1919169689Skan/* Compute reaching vuses and antic safe loads. RVUSE computation is 1920169689Skan is a small bit of iterative dataflow to determine what virtual uses 1921169689Skan reach what blocks. Because we can't generate overlapping virtual 1922169689Skan uses, and virtual uses *do* actually die, this ends up being faster 1923169689Skan in most cases than continually walking the virtual use/def chains 1924169689Skan to determine whether we are inside a block where a given virtual is 1925169689Skan still available to be used. 1926169689Skan 1927169689Skan ANTIC_SAFE_LOADS are those loads that actually occur before any kill to 1928169689Skan their vuses in the block,and thus, are safe at the top of the 1929169689Skan block. 1930169689Skan 1931169689Skan An example: 1932169689Skan 1933169689Skan <block begin> 1934169689Skan b = *a 1935169689Skan *a = 9 1936169689Skan <block end> 1937169689Skan 1938169689Skan b = *a is an antic safe load because it still safe to consider it 1939169689Skan ANTIC at the top of the block. 1940169689Skan 1941169689Skan We currently compute a conservative approximation to 1942169689Skan ANTIC_SAFE_LOADS. We compute those loads that occur before *any* 1943169689Skan stores in the block. This is not because it is difficult to 1944169689Skan compute the precise answer, but because it is expensive. More 1945169689Skan testing is necessary to determine whether it is worth computing the 1946169689Skan precise answer. */ 1947169689Skan 1948169689Skanstatic void 1949169689Skancompute_rvuse_and_antic_safe (void) 1950169689Skan{ 1951169689Skan 1952169689Skan size_t i; 1953169689Skan tree phi; 1954169689Skan basic_block bb; 1955169689Skan int *postorder; 1956169689Skan bool changed = true; 1957169689Skan unsigned int *first_store_uid; 1958169689Skan 1959169689Skan first_store_uid = xcalloc (n_basic_blocks, sizeof (unsigned int)); 1960169689Skan 1961169689Skan compute_vuse_representatives (); 1962169689Skan 1963169689Skan FOR_ALL_BB (bb) 1964169689Skan { 1965169689Skan RVUSE_IN (bb) = BITMAP_ALLOC (&grand_bitmap_obstack); 1966169689Skan RVUSE_GEN (bb) = BITMAP_ALLOC (&grand_bitmap_obstack); 1967169689Skan RVUSE_KILL (bb) = BITMAP_ALLOC (&grand_bitmap_obstack); 1968169689Skan RVUSE_OUT (bb) = BITMAP_ALLOC (&grand_bitmap_obstack); 1969169689Skan ANTIC_SAFE_LOADS (bb) = NULL; 1970169689Skan } 1971169689Skan 1972169689Skan /* Mark live on entry */ 1973169689Skan for (i = 0; i < num_ssa_names; i++) 1974169689Skan { 1975169689Skan tree name = ssa_name (i); 1976169689Skan if (name && !is_gimple_reg (name) 1977169689Skan && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (name))) 1978169689Skan bitmap_set_bit (RVUSE_OUT (ENTRY_BLOCK_PTR), 1979169689Skan SSA_NAME_VERSION (name)); 1980169689Skan } 1981169689Skan 1982169689Skan /* Compute local sets for reaching vuses. 1983169689Skan GEN(block) = generated in block and not locally killed. 1984169689Skan KILL(block) = set of vuses killed in block. 1985169689Skan */ 1986169689Skan 1987169689Skan FOR_EACH_BB (bb) 1988169689Skan { 1989169689Skan block_stmt_iterator bsi; 1990169689Skan ssa_op_iter iter; 1991169689Skan def_operand_p defp; 1992169689Skan use_operand_p usep; 1993169689Skan 1994169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 1995169689Skan { 1996169689Skan tree stmt = bsi_stmt (bsi); 1997169689Skan 1998169689Skan if (first_store_uid[bb->index] == 0 1999169689Skan && !ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYUSE | SSA_OP_VMAYDEF 2000169689Skan | SSA_OP_VMUSTDEF | SSA_OP_VMUSTKILL)) 2001169689Skan { 2002169689Skan first_store_uid[bb->index] = stmt_ann (stmt)->uid; 2003169689Skan } 2004169689Skan 2005169689Skan 2006169689Skan FOR_EACH_SSA_USE_OPERAND (usep, stmt, iter, SSA_OP_VIRTUAL_KILLS 2007169689Skan | SSA_OP_VMAYUSE) 2008169689Skan { 2009169689Skan tree use = USE_FROM_PTR (usep); 2010169689Skan bitmap repbit = get_representative (vuse_names, 2011169689Skan SSA_NAME_VERSION (use)); 2012169689Skan if (repbit != NULL) 2013169689Skan { 2014169689Skan bitmap_and_compl_into (RVUSE_GEN (bb), repbit); 2015169689Skan bitmap_ior_into (RVUSE_KILL (bb), repbit); 2016169689Skan } 2017169689Skan else 2018169689Skan { 2019169689Skan bitmap_set_bit (RVUSE_KILL (bb), SSA_NAME_VERSION (use)); 2020169689Skan bitmap_clear_bit (RVUSE_GEN (bb), SSA_NAME_VERSION (use)); 2021169689Skan } 2022169689Skan } 2023169689Skan FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS) 2024169689Skan { 2025169689Skan tree def = DEF_FROM_PTR (defp); 2026169689Skan bitmap_set_bit (RVUSE_GEN (bb), SSA_NAME_VERSION (def)); 2027169689Skan } 2028169689Skan } 2029169689Skan } 2030169689Skan 2031169689Skan FOR_EACH_BB (bb) 2032169689Skan { 2033169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 2034169689Skan { 2035169689Skan if (!is_gimple_reg (PHI_RESULT (phi))) 2036169689Skan { 2037169689Skan edge e; 2038169689Skan edge_iterator ei; 2039169689Skan 2040169689Skan tree def = PHI_RESULT (phi); 2041169689Skan /* In reality, the PHI result is generated at the end of 2042169689Skan each predecessor block. This will make the value 2043169689Skan LVUSE_IN for the bb containing the PHI, which is 2044169689Skan correct. */ 2045169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 2046169689Skan bitmap_set_bit (RVUSE_GEN (e->src), SSA_NAME_VERSION (def)); 2047169689Skan } 2048169689Skan } 2049169689Skan } 2050169689Skan 2051169689Skan /* Solve reaching vuses. 2052169689Skan 2053169689Skan RVUSE_IN[BB] = Union of RVUSE_OUT of predecessors. 2054169689Skan RVUSE_OUT[BB] = RVUSE_GEN[BB] U (RVUSE_IN[BB] - RVUSE_KILL[BB]) 2055169689Skan */ 2056169689Skan postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS); 2057169689Skan pre_and_rev_post_order_compute (NULL, postorder, false); 2058169689Skan 2059169689Skan changed = true; 2060169689Skan while (changed) 2061169689Skan { 2062169689Skan int j; 2063169689Skan changed = false; 2064169689Skan for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++) 2065169689Skan { 2066169689Skan edge e; 2067169689Skan edge_iterator ei; 2068169689Skan bb = BASIC_BLOCK (postorder[j]); 2069169689Skan 2070169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 2071169689Skan bitmap_ior_into (RVUSE_IN (bb), RVUSE_OUT (e->src)); 2072169689Skan 2073169689Skan changed |= bitmap_ior_and_compl (RVUSE_OUT (bb), 2074169689Skan RVUSE_GEN (bb), 2075169689Skan RVUSE_IN (bb), 2076169689Skan RVUSE_KILL (bb)); 2077169689Skan } 2078169689Skan } 2079169689Skan free (postorder); 2080169689Skan 2081169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2082169689Skan { 2083169689Skan FOR_ALL_BB (bb) 2084169689Skan { 2085169689Skan fprintf (dump_file, "RVUSE_IN (%d) =", bb->index); 2086169689Skan dump_bitmap_of_names (dump_file, RVUSE_IN (bb)); 2087169689Skan 2088169689Skan fprintf (dump_file, "RVUSE_KILL (%d) =", bb->index); 2089169689Skan dump_bitmap_of_names (dump_file, RVUSE_KILL (bb)); 2090169689Skan 2091169689Skan fprintf (dump_file, "RVUSE_GEN (%d) =", bb->index); 2092169689Skan dump_bitmap_of_names (dump_file, RVUSE_GEN (bb)); 2093169689Skan 2094169689Skan fprintf (dump_file, "RVUSE_OUT (%d) =", bb->index); 2095169689Skan dump_bitmap_of_names (dump_file, RVUSE_OUT (bb)); 2096169689Skan } 2097169689Skan } 2098169689Skan 2099169689Skan FOR_EACH_BB (bb) 2100169689Skan { 2101169689Skan value_set_node_t node; 2102169689Skan if (bitmap_empty_p (RVUSE_KILL (bb))) 2103169689Skan continue; 2104169689Skan 2105169689Skan for (node = EXP_GEN (bb)->head; node; node = node->next) 2106169689Skan { 2107169689Skan if (REFERENCE_CLASS_P (node->expr)) 2108169689Skan { 2109169689Skan tree vh = get_value_handle (node->expr); 2110169689Skan tree maybe = bitmap_find_leader (AVAIL_OUT (bb), vh); 2111169689Skan 2112169689Skan if (maybe) 2113169689Skan { 2114169689Skan tree def = SSA_NAME_DEF_STMT (maybe); 2115169689Skan 2116169689Skan if (bb_for_stmt (def) != bb) 2117169689Skan continue; 2118169689Skan 2119169689Skan if (TREE_CODE (def) == PHI_NODE 2120169689Skan || stmt_ann (def)->uid < first_store_uid[bb->index]) 2121169689Skan { 2122169689Skan if (ANTIC_SAFE_LOADS (bb) == NULL) 2123169689Skan ANTIC_SAFE_LOADS (bb) = set_new (true); 2124169689Skan value_insert_into_set (ANTIC_SAFE_LOADS (bb), 2125169689Skan node->expr); 2126169689Skan } 2127169689Skan } 2128169689Skan } 2129169689Skan } 2130169689Skan } 2131169689Skan free (first_store_uid); 2132169689Skan} 2133169689Skan 2134169689Skan/* Return true if we can value number the call in STMT. This is true 2135169689Skan if we have a pure or constant call. */ 2136169689Skan 2137169689Skanstatic bool 2138169689Skancan_value_number_call (tree stmt) 2139169689Skan{ 2140169689Skan tree call = get_call_expr_in (stmt); 2141169689Skan 2142169689Skan if (call_expr_flags (call) & (ECF_PURE | ECF_CONST)) 2143169689Skan return true; 2144169689Skan return false; 2145169689Skan} 2146169689Skan 2147169689Skan/* Return true if OP is a tree which we can perform value numbering 2148169689Skan on. */ 2149169689Skan 2150169689Skanstatic bool 2151169689Skancan_value_number_operation (tree op) 2152169689Skan{ 2153169689Skan return UNARY_CLASS_P (op) 2154169689Skan || BINARY_CLASS_P (op) 2155169689Skan || COMPARISON_CLASS_P (op) 2156169689Skan || REFERENCE_CLASS_P (op) 2157169689Skan || (TREE_CODE (op) == CALL_EXPR 2158169689Skan && can_value_number_call (op)); 2159169689Skan} 2160169689Skan 2161169689Skan 2162169689Skan/* Return true if OP is a tree which we can perform PRE on 2163169689Skan on. This may not match the operations we can value number, but in 2164169689Skan a perfect world would. */ 2165169689Skan 2166169689Skanstatic bool 2167169689Skancan_PRE_operation (tree op) 2168169689Skan{ 2169169689Skan return UNARY_CLASS_P (op) 2170169689Skan || BINARY_CLASS_P (op) 2171169689Skan || COMPARISON_CLASS_P (op) 2172169689Skan || TREE_CODE (op) == INDIRECT_REF 2173169689Skan || TREE_CODE (op) == COMPONENT_REF 2174169689Skan || TREE_CODE (op) == CALL_EXPR 2175169689Skan || TREE_CODE (op) == ARRAY_REF; 2176169689Skan} 2177169689Skan 2178169689Skan 2179169689Skan/* Inserted expressions are placed onto this worklist, which is used 2180169689Skan for performing quick dead code elimination of insertions we made 2181169689Skan that didn't turn out to be necessary. */ 2182169689Skanstatic VEC(tree,heap) *inserted_exprs; 2183169689Skan 2184169689Skan/* Pool allocated fake store expressions are placed onto this 2185169689Skan worklist, which, after performing dead code elimination, is walked 2186169689Skan to see which expressions need to be put into GC'able memory */ 2187169689Skanstatic VEC(tree, heap) *need_creation; 2188169689Skan 2189169689Skan/* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the 2190169689Skan COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with 2191169689Skan trying to rename aggregates into ssa form directly, which is a no 2192169689Skan no. 2193169689Skan 2194169689Skan Thus, this routine doesn't create temporaries, it just builds a 2195169689Skan single access expression for the array, calling 2196169689Skan find_or_generate_expression to build the innermost pieces. 2197169689Skan 2198169689Skan This function is a subroutine of create_expression_by_pieces, and 2199169689Skan should not be called on it's own unless you really know what you 2200169689Skan are doing. 2201169689Skan*/ 2202169689Skanstatic tree 2203169689Skancreate_component_ref_by_pieces (basic_block block, tree expr, tree stmts) 2204169689Skan{ 2205169689Skan tree genop = expr; 2206169689Skan tree folded; 2207169689Skan 2208169689Skan if (TREE_CODE (genop) == VALUE_HANDLE) 2209169689Skan { 2210169689Skan tree found = bitmap_find_leader (AVAIL_OUT (block), expr); 2211169689Skan if (found) 2212169689Skan return found; 2213169689Skan } 2214169689Skan 2215169689Skan if (TREE_CODE (genop) == VALUE_HANDLE) 2216169689Skan genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr; 2217169689Skan 2218169689Skan switch TREE_CODE (genop) 2219169689Skan { 2220169689Skan case ARRAY_REF: 2221169689Skan { 2222169689Skan tree op0; 2223169689Skan tree op1, op2, op3; 2224169689Skan op0 = create_component_ref_by_pieces (block, 2225169689Skan TREE_OPERAND (genop, 0), 2226169689Skan stmts); 2227169689Skan op1 = TREE_OPERAND (genop, 1); 2228169689Skan if (TREE_CODE (op1) == VALUE_HANDLE) 2229169689Skan op1 = find_or_generate_expression (block, op1, stmts); 2230169689Skan op2 = TREE_OPERAND (genop, 2); 2231169689Skan if (op2 && TREE_CODE (op2) == VALUE_HANDLE) 2232169689Skan op2 = find_or_generate_expression (block, op2, stmts); 2233169689Skan op3 = TREE_OPERAND (genop, 3); 2234169689Skan if (op3 && TREE_CODE (op3) == VALUE_HANDLE) 2235169689Skan op3 = find_or_generate_expression (block, op3, stmts); 2236169689Skan folded = build4 (ARRAY_REF, TREE_TYPE (genop), op0, op1, 2237169689Skan op2, op3); 2238169689Skan return folded; 2239169689Skan } 2240169689Skan case COMPONENT_REF: 2241169689Skan { 2242169689Skan tree op0; 2243169689Skan tree op1; 2244169689Skan op0 = create_component_ref_by_pieces (block, 2245169689Skan TREE_OPERAND (genop, 0), 2246169689Skan stmts); 2247169689Skan op1 = VALUE_HANDLE_EXPR_SET (TREE_OPERAND (genop, 1))->head->expr; 2248169689Skan folded = fold_build3 (COMPONENT_REF, TREE_TYPE (genop), op0, op1, 2249169689Skan NULL_TREE); 2250169689Skan return folded; 2251169689Skan } 2252169689Skan break; 2253169689Skan case INDIRECT_REF: 2254169689Skan { 2255169689Skan tree op1 = TREE_OPERAND (genop, 0); 2256169689Skan tree genop1 = find_or_generate_expression (block, op1, stmts); 2257169689Skan 2258169689Skan folded = fold_build1 (TREE_CODE (genop), TREE_TYPE (genop), 2259169689Skan genop1); 2260169689Skan return folded; 2261169689Skan } 2262169689Skan break; 2263169689Skan case VAR_DECL: 2264169689Skan case PARM_DECL: 2265169689Skan case RESULT_DECL: 2266169689Skan case SSA_NAME: 2267169689Skan case STRING_CST: 2268169689Skan return genop; 2269169689Skan default: 2270169689Skan gcc_unreachable (); 2271169689Skan } 2272169689Skan 2273169689Skan return NULL_TREE; 2274169689Skan} 2275169689Skan 2276169689Skan/* Find a leader for an expression, or generate one using 2277169689Skan create_expression_by_pieces if it's ANTIC but 2278169689Skan complex. 2279169689Skan BLOCK is the basic_block we are looking for leaders in. 2280169689Skan EXPR is the expression to find a leader or generate for. 2281169689Skan STMTS is the statement list to put the inserted expressions on. 2282169689Skan Returns the SSA_NAME of the LHS of the generated expression or the 2283169689Skan leader. */ 2284169689Skan 2285169689Skanstatic tree 2286169689Skanfind_or_generate_expression (basic_block block, tree expr, tree stmts) 2287169689Skan{ 2288169689Skan tree genop = bitmap_find_leader (AVAIL_OUT (block), expr); 2289169689Skan 2290169689Skan /* If it's still NULL, it must be a complex expression, so generate 2291169689Skan it recursively. */ 2292169689Skan if (genop == NULL) 2293169689Skan { 2294169689Skan genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr; 2295169689Skan 2296169689Skan gcc_assert (can_PRE_operation (genop)); 2297169689Skan genop = create_expression_by_pieces (block, genop, stmts); 2298169689Skan } 2299169689Skan return genop; 2300169689Skan} 2301169689Skan 2302169689Skan#define NECESSARY(stmt) stmt->common.asm_written_flag 2303169689Skan/* Create an expression in pieces, so that we can handle very complex 2304169689Skan expressions that may be ANTIC, but not necessary GIMPLE. 2305169689Skan BLOCK is the basic block the expression will be inserted into, 2306169689Skan EXPR is the expression to insert (in value form) 2307169689Skan STMTS is a statement list to append the necessary insertions into. 2308169689Skan 2309169689Skan This function will die if we hit some value that shouldn't be 2310169689Skan ANTIC but is (IE there is no leader for it, or its components). 2311169689Skan This function may also generate expressions that are themselves 2312169689Skan partially or fully redundant. Those that are will be either made 2313169689Skan fully redundant during the next iteration of insert (for partially 2314169689Skan redundant ones), or eliminated by eliminate (for fully redundant 2315169689Skan ones). */ 2316169689Skan 2317169689Skanstatic tree 2318169689Skancreate_expression_by_pieces (basic_block block, tree expr, tree stmts) 2319169689Skan{ 2320169689Skan tree temp, name; 2321169689Skan tree folded, forced_stmts, newexpr; 2322169689Skan tree v; 2323169689Skan tree_stmt_iterator tsi; 2324169689Skan 2325169689Skan switch (TREE_CODE_CLASS (TREE_CODE (expr))) 2326169689Skan { 2327169689Skan case tcc_expression: 2328169689Skan { 2329169689Skan tree op0, op2; 2330169689Skan tree arglist; 2331169689Skan tree genop0, genop2; 2332169689Skan tree genarglist; 2333169689Skan tree walker, genwalker; 2334169689Skan 2335169689Skan gcc_assert (TREE_CODE (expr) == CALL_EXPR); 2336169689Skan genop2 = NULL; 2337169689Skan 2338169689Skan op0 = TREE_OPERAND (expr, 0); 2339169689Skan arglist = TREE_OPERAND (expr, 1); 2340169689Skan op2 = TREE_OPERAND (expr, 2); 2341169689Skan 2342169689Skan genop0 = find_or_generate_expression (block, op0, stmts); 2343169689Skan genarglist = copy_list (arglist); 2344169689Skan for (walker = arglist, genwalker = genarglist; 2345169689Skan genwalker && walker; 2346169689Skan genwalker = TREE_CHAIN (genwalker), walker = TREE_CHAIN (walker)) 2347169689Skan { 2348169689Skan TREE_VALUE (genwalker) 2349169689Skan = find_or_generate_expression (block, TREE_VALUE (walker), 2350169689Skan stmts); 2351169689Skan } 2352169689Skan 2353169689Skan if (op2) 2354169689Skan genop2 = find_or_generate_expression (block, op2, stmts); 2355169689Skan folded = fold_build3 (TREE_CODE (expr), TREE_TYPE (expr), 2356169689Skan genop0, genarglist, genop2); 2357169689Skan break; 2358169689Skan 2359169689Skan 2360169689Skan } 2361169689Skan break; 2362169689Skan case tcc_reference: 2363169689Skan { 2364169689Skan if (TREE_CODE (expr) == COMPONENT_REF 2365169689Skan || TREE_CODE (expr) == ARRAY_REF) 2366169689Skan { 2367169689Skan folded = create_component_ref_by_pieces (block, expr, stmts); 2368169689Skan } 2369169689Skan else 2370169689Skan { 2371169689Skan tree op1 = TREE_OPERAND (expr, 0); 2372169689Skan tree genop1 = find_or_generate_expression (block, op1, stmts); 2373169689Skan 2374169689Skan folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr), 2375169689Skan genop1); 2376169689Skan } 2377169689Skan break; 2378169689Skan } 2379169689Skan 2380169689Skan case tcc_binary: 2381169689Skan case tcc_comparison: 2382169689Skan { 2383169689Skan tree op1 = TREE_OPERAND (expr, 0); 2384169689Skan tree op2 = TREE_OPERAND (expr, 1); 2385169689Skan tree genop1 = find_or_generate_expression (block, op1, stmts); 2386169689Skan tree genop2 = find_or_generate_expression (block, op2, stmts); 2387169689Skan folded = fold_build2 (TREE_CODE (expr), TREE_TYPE (expr), 2388169689Skan genop1, genop2); 2389169689Skan break; 2390169689Skan } 2391169689Skan 2392169689Skan case tcc_unary: 2393169689Skan { 2394169689Skan tree op1 = TREE_OPERAND (expr, 0); 2395169689Skan tree genop1 = find_or_generate_expression (block, op1, stmts); 2396169689Skan folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr), 2397169689Skan genop1); 2398169689Skan break; 2399169689Skan } 2400169689Skan 2401169689Skan default: 2402169689Skan gcc_unreachable (); 2403169689Skan } 2404169689Skan 2405169689Skan /* Force the generated expression to be a sequence of GIMPLE 2406169689Skan statements. 2407169689Skan We have to call unshare_expr because force_gimple_operand may 2408169689Skan modify the tree we pass to it. */ 2409169689Skan newexpr = force_gimple_operand (unshare_expr (folded), &forced_stmts, 2410169689Skan false, NULL); 2411169689Skan 2412169689Skan /* If we have any intermediate expressions to the value sets, add them 2413169689Skan to the value sets and chain them on in the instruction stream. */ 2414169689Skan if (forced_stmts) 2415169689Skan { 2416169689Skan tsi = tsi_start (forced_stmts); 2417169689Skan for (; !tsi_end_p (tsi); tsi_next (&tsi)) 2418169689Skan { 2419169689Skan tree stmt = tsi_stmt (tsi); 2420169689Skan tree forcedname = TREE_OPERAND (stmt, 0); 2421169689Skan tree forcedexpr = TREE_OPERAND (stmt, 1); 2422169689Skan tree val = vn_lookup_or_add (forcedexpr, NULL); 2423169689Skan 2424169689Skan VEC_safe_push (tree, heap, inserted_exprs, stmt); 2425169689Skan vn_add (forcedname, val); 2426169689Skan bitmap_value_replace_in_set (NEW_SETS (block), forcedname); 2427169689Skan bitmap_value_replace_in_set (AVAIL_OUT (block), forcedname); 2428169689Skan mark_new_vars_to_rename (stmt); 2429169689Skan } 2430169689Skan tsi = tsi_last (stmts); 2431169689Skan tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING); 2432169689Skan } 2433169689Skan 2434169689Skan /* Build and insert the assignment of the end result to the temporary 2435169689Skan that we will return. */ 2436169689Skan if (!pretemp || TREE_TYPE (expr) != TREE_TYPE (pretemp)) 2437169689Skan { 2438169689Skan pretemp = create_tmp_var (TREE_TYPE (expr), "pretmp"); 2439169689Skan get_var_ann (pretemp); 2440169689Skan } 2441169689Skan 2442169689Skan temp = pretemp; 2443169689Skan add_referenced_var (temp); 2444169689Skan 2445169689Skan if (TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE) 2446169689Skan DECL_COMPLEX_GIMPLE_REG_P (temp) = 1; 2447169689Skan 2448169689Skan newexpr = build2 (MODIFY_EXPR, TREE_TYPE (expr), temp, newexpr); 2449169689Skan name = make_ssa_name (temp, newexpr); 2450169689Skan TREE_OPERAND (newexpr, 0) = name; 2451169689Skan NECESSARY (newexpr) = 0; 2452169689Skan 2453169689Skan tsi = tsi_last (stmts); 2454169689Skan tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING); 2455169689Skan VEC_safe_push (tree, heap, inserted_exprs, newexpr); 2456169689Skan mark_new_vars_to_rename (newexpr); 2457169689Skan 2458169689Skan /* Add a value handle to the temporary. 2459169689Skan The value may already exist in either NEW_SETS, or AVAIL_OUT, because 2460169689Skan we are creating the expression by pieces, and this particular piece of 2461169689Skan the expression may have been represented. There is no harm in replacing 2462169689Skan here. */ 2463169689Skan v = get_value_handle (expr); 2464169689Skan vn_add (name, v); 2465169689Skan bitmap_value_replace_in_set (NEW_SETS (block), name); 2466169689Skan bitmap_value_replace_in_set (AVAIL_OUT (block), name); 2467169689Skan 2468169689Skan pre_stats.insertions++; 2469169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2470169689Skan { 2471169689Skan fprintf (dump_file, "Inserted "); 2472169689Skan print_generic_expr (dump_file, newexpr, 0); 2473169689Skan fprintf (dump_file, " in predecessor %d\n", block->index); 2474169689Skan } 2475169689Skan 2476169689Skan return name; 2477169689Skan} 2478169689Skan 2479169689Skan/* Insert the to-be-made-available values of NODE for each 2480169689Skan predecessor, stored in AVAIL, into the predecessors of BLOCK, and 2481169689Skan merge the result with a phi node, given the same value handle as 2482169689Skan NODE. Return true if we have inserted new stuff. */ 2483169689Skan 2484169689Skanstatic bool 2485169689Skaninsert_into_preds_of_block (basic_block block, value_set_node_t node, 2486169689Skan tree *avail) 2487169689Skan{ 2488169689Skan tree val = get_value_handle (node->expr); 2489169689Skan edge pred; 2490169689Skan bool insertions = false; 2491169689Skan bool nophi = false; 2492169689Skan basic_block bprime; 2493169689Skan tree eprime; 2494169689Skan edge_iterator ei; 2495169689Skan tree type = TREE_TYPE (avail[EDGE_PRED (block, 0)->src->index]); 2496169689Skan tree temp; 2497169689Skan 2498169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2499169689Skan { 2500169689Skan fprintf (dump_file, "Found partial redundancy for expression "); 2501169689Skan print_generic_expr (dump_file, node->expr, 0); 2502169689Skan fprintf (dump_file, " ("); 2503169689Skan print_generic_expr (dump_file, val, 0); 2504169689Skan fprintf (dump_file, ")"); 2505169689Skan fprintf (dump_file, "\n"); 2506169689Skan } 2507169689Skan 2508169689Skan /* Make sure we aren't creating an induction variable. */ 2509169689Skan if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2 2510169689Skan && TREE_CODE_CLASS (TREE_CODE (node->expr)) != tcc_reference ) 2511169689Skan { 2512169689Skan bool firstinsideloop = false; 2513169689Skan bool secondinsideloop = false; 2514169689Skan firstinsideloop = flow_bb_inside_loop_p (block->loop_father, 2515169689Skan EDGE_PRED (block, 0)->src); 2516169689Skan secondinsideloop = flow_bb_inside_loop_p (block->loop_father, 2517169689Skan EDGE_PRED (block, 1)->src); 2518169689Skan /* Induction variables only have one edge inside the loop. */ 2519169689Skan if (firstinsideloop ^ secondinsideloop) 2520169689Skan { 2521169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2522169689Skan fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n"); 2523169689Skan nophi = true; 2524169689Skan } 2525169689Skan } 2526169689Skan 2527169689Skan 2528169689Skan /* Make the necessary insertions. */ 2529169689Skan FOR_EACH_EDGE (pred, ei, block->preds) 2530169689Skan { 2531169689Skan tree stmts = alloc_stmt_list (); 2532169689Skan tree builtexpr; 2533169689Skan bprime = pred->src; 2534169689Skan eprime = avail[bprime->index]; 2535169689Skan 2536169689Skan if (can_PRE_operation (eprime)) 2537169689Skan { 2538169689Skan#ifdef ENABLE_CHECKING 2539169689Skan tree vh; 2540169689Skan 2541169689Skan /* eprime may be an invariant. */ 2542169689Skan vh = TREE_CODE (eprime) == VALUE_HANDLE 2543169689Skan ? eprime 2544169689Skan : get_value_handle (eprime); 2545169689Skan 2546169689Skan /* ensure that the virtual uses we need reach our block. */ 2547169689Skan if (TREE_CODE (vh) == VALUE_HANDLE) 2548169689Skan { 2549169689Skan int i; 2550169689Skan tree vuse; 2551169689Skan for (i = 0; 2552169689Skan VEC_iterate (tree, VALUE_HANDLE_VUSES (vh), i, vuse); 2553169689Skan i++) 2554169689Skan { 2555169689Skan size_t id = SSA_NAME_VERSION (vuse); 2556169689Skan gcc_assert (bitmap_bit_p (RVUSE_OUT (bprime), id) 2557169689Skan || IS_EMPTY_STMT (SSA_NAME_DEF_STMT (vuse))); 2558169689Skan } 2559169689Skan } 2560169689Skan#endif 2561169689Skan builtexpr = create_expression_by_pieces (bprime, 2562169689Skan eprime, 2563169689Skan stmts); 2564169689Skan bsi_insert_on_edge (pred, stmts); 2565169689Skan avail[bprime->index] = builtexpr; 2566169689Skan insertions = true; 2567169689Skan } 2568169689Skan } 2569169689Skan /* If we didn't want a phi node, and we made insertions, we still have 2570169689Skan inserted new stuff, and thus return true. If we didn't want a phi node, 2571169689Skan and didn't make insertions, we haven't added anything new, so return 2572169689Skan false. */ 2573169689Skan if (nophi && insertions) 2574169689Skan return true; 2575169689Skan else if (nophi && !insertions) 2576169689Skan return false; 2577169689Skan 2578169689Skan /* Now build a phi for the new variable. */ 2579169689Skan if (!prephitemp || TREE_TYPE (prephitemp) != type) 2580169689Skan { 2581169689Skan prephitemp = create_tmp_var (type, "prephitmp"); 2582169689Skan get_var_ann (prephitemp); 2583169689Skan } 2584169689Skan 2585169689Skan temp = prephitemp; 2586169689Skan add_referenced_var (temp); 2587169689Skan 2588169689Skan if (TREE_CODE (type) == COMPLEX_TYPE) 2589169689Skan DECL_COMPLEX_GIMPLE_REG_P (temp) = 1; 2590169689Skan temp = create_phi_node (temp, block); 2591169689Skan 2592169689Skan NECESSARY (temp) = 0; 2593169689Skan VEC_safe_push (tree, heap, inserted_exprs, temp); 2594169689Skan FOR_EACH_EDGE (pred, ei, block->preds) 2595169689Skan add_phi_arg (temp, avail[pred->src->index], pred); 2596169689Skan 2597169689Skan vn_add (PHI_RESULT (temp), val); 2598169689Skan 2599169689Skan /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing 2600169689Skan this insertion, since we test for the existence of this value in PHI_GEN 2601169689Skan before proceeding with the partial redundancy checks in insert_aux. 2602169689Skan 2603169689Skan The value may exist in AVAIL_OUT, in particular, it could be represented 2604169689Skan by the expression we are trying to eliminate, in which case we want the 2605169689Skan replacement to occur. If it's not existing in AVAIL_OUT, we want it 2606169689Skan inserted there. 2607169689Skan 2608169689Skan Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of 2609169689Skan this block, because if it did, it would have existed in our dominator's 2610169689Skan AVAIL_OUT, and would have been skipped due to the full redundancy check. 2611169689Skan */ 2612169689Skan 2613169689Skan bitmap_insert_into_set (PHI_GEN (block), 2614169689Skan PHI_RESULT (temp)); 2615169689Skan bitmap_value_replace_in_set (AVAIL_OUT (block), 2616169689Skan PHI_RESULT (temp)); 2617169689Skan bitmap_insert_into_set (NEW_SETS (block), 2618169689Skan PHI_RESULT (temp)); 2619169689Skan 2620169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2621169689Skan { 2622169689Skan fprintf (dump_file, "Created phi "); 2623169689Skan print_generic_expr (dump_file, temp, 0); 2624169689Skan fprintf (dump_file, " in block %d\n", block->index); 2625169689Skan } 2626169689Skan pre_stats.phis++; 2627169689Skan return true; 2628169689Skan} 2629169689Skan 2630169689Skan 2631169689Skan 2632169689Skan/* Perform insertion of partially redundant values. 2633169689Skan For BLOCK, do the following: 2634169689Skan 1. Propagate the NEW_SETS of the dominator into the current block. 2635169689Skan If the block has multiple predecessors, 2636169689Skan 2a. Iterate over the ANTIC expressions for the block to see if 2637169689Skan any of them are partially redundant. 2638169689Skan 2b. If so, insert them into the necessary predecessors to make 2639169689Skan the expression fully redundant. 2640169689Skan 2c. Insert a new PHI merging the values of the predecessors. 2641169689Skan 2d. Insert the new PHI, and the new expressions, into the 2642169689Skan NEW_SETS set. 2643169689Skan 3. Recursively call ourselves on the dominator children of BLOCK. 2644169689Skan 2645169689Skan*/ 2646169689Skan 2647169689Skanstatic bool 2648169689Skaninsert_aux (basic_block block) 2649169689Skan{ 2650169689Skan basic_block son; 2651169689Skan bool new_stuff = false; 2652169689Skan 2653169689Skan if (block) 2654169689Skan { 2655169689Skan basic_block dom; 2656169689Skan dom = get_immediate_dominator (CDI_DOMINATORS, block); 2657169689Skan if (dom) 2658169689Skan { 2659169689Skan unsigned i; 2660169689Skan bitmap_iterator bi; 2661169689Skan bitmap_set_t newset = NEW_SETS (dom); 2662169689Skan if (newset) 2663169689Skan { 2664169689Skan /* Note that we need to value_replace both NEW_SETS, and 2665169689Skan AVAIL_OUT. For both the case of NEW_SETS, the value may be 2666169689Skan represented by some non-simple expression here that we want 2667169689Skan to replace it with. */ 2668169689Skan EXECUTE_IF_SET_IN_BITMAP (newset->expressions, 0, i, bi) 2669169689Skan { 2670169689Skan bitmap_value_replace_in_set (NEW_SETS (block), ssa_name (i)); 2671169689Skan bitmap_value_replace_in_set (AVAIL_OUT (block), ssa_name (i)); 2672169689Skan } 2673169689Skan } 2674169689Skan if (!single_pred_p (block)) 2675169689Skan { 2676169689Skan value_set_node_t node; 2677169689Skan for (node = ANTIC_IN (block)->head; 2678169689Skan node; 2679169689Skan node = node->next) 2680169689Skan { 2681169689Skan if (can_PRE_operation (node->expr) 2682169689Skan && !AGGREGATE_TYPE_P (TREE_TYPE (node->expr))) 2683169689Skan { 2684169689Skan tree *avail; 2685169689Skan tree val; 2686169689Skan bool by_some = false; 2687169689Skan bool cant_insert = false; 2688169689Skan bool all_same = true; 2689169689Skan tree first_s = NULL; 2690169689Skan edge pred; 2691169689Skan basic_block bprime; 2692169689Skan tree eprime = NULL_TREE; 2693169689Skan edge_iterator ei; 2694169689Skan 2695169689Skan val = get_value_handle (node->expr); 2696169689Skan if (bitmap_set_contains_value (PHI_GEN (block), val)) 2697169689Skan continue; 2698169689Skan if (bitmap_set_contains_value (AVAIL_OUT (dom), val)) 2699169689Skan { 2700169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2701169689Skan fprintf (dump_file, "Found fully redundant value\n"); 2702169689Skan continue; 2703169689Skan } 2704169689Skan 2705169689Skan avail = XCNEWVEC (tree, last_basic_block); 2706169689Skan FOR_EACH_EDGE (pred, ei, block->preds) 2707169689Skan { 2708169689Skan tree vprime; 2709169689Skan tree edoubleprime; 2710169689Skan 2711169689Skan /* This can happen in the very weird case 2712169689Skan that our fake infinite loop edges have caused a 2713169689Skan critical edge to appear. */ 2714169689Skan if (EDGE_CRITICAL_P (pred)) 2715169689Skan { 2716169689Skan cant_insert = true; 2717169689Skan break; 2718169689Skan } 2719169689Skan bprime = pred->src; 2720169689Skan eprime = phi_translate (node->expr, 2721169689Skan ANTIC_IN (block), 2722169689Skan bprime, block); 2723169689Skan 2724169689Skan /* eprime will generally only be NULL if the 2725169689Skan value of the expression, translated 2726169689Skan through the PHI for this predecessor, is 2727169689Skan undefined. If that is the case, we can't 2728169689Skan make the expression fully redundant, 2729169689Skan because its value is undefined along a 2730169689Skan predecessor path. We can thus break out 2731169689Skan early because it doesn't matter what the 2732169689Skan rest of the results are. */ 2733169689Skan if (eprime == NULL) 2734169689Skan { 2735169689Skan cant_insert = true; 2736169689Skan break; 2737169689Skan } 2738169689Skan 2739169689Skan eprime = fully_constant_expression (eprime); 2740169689Skan vprime = get_value_handle (eprime); 2741169689Skan gcc_assert (vprime); 2742169689Skan edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), 2743169689Skan vprime); 2744169689Skan if (edoubleprime == NULL) 2745169689Skan { 2746169689Skan avail[bprime->index] = eprime; 2747169689Skan all_same = false; 2748169689Skan } 2749169689Skan else 2750169689Skan { 2751169689Skan avail[bprime->index] = edoubleprime; 2752169689Skan by_some = true; 2753169689Skan if (first_s == NULL) 2754169689Skan first_s = edoubleprime; 2755169689Skan else if (!operand_equal_p (first_s, edoubleprime, 2756169689Skan 0)) 2757169689Skan all_same = false; 2758169689Skan } 2759169689Skan } 2760169689Skan /* If we can insert it, it's not the same value 2761169689Skan already existing along every predecessor, and 2762169689Skan it's defined by some predecessor, it is 2763169689Skan partially redundant. */ 2764169689Skan if (!cant_insert && !all_same && by_some) 2765169689Skan { 2766169689Skan if (insert_into_preds_of_block (block, node, avail)) 2767169689Skan new_stuff = true; 2768169689Skan } 2769169689Skan /* If all edges produce the same value and that value is 2770169689Skan an invariant, then the PHI has the same value on all 2771169689Skan edges. Note this. */ 2772169689Skan else if (!cant_insert && all_same && eprime 2773169689Skan && is_gimple_min_invariant (eprime) 2774169689Skan && !is_gimple_min_invariant (val)) 2775169689Skan { 2776169689Skan value_set_t exprset = VALUE_HANDLE_EXPR_SET (val); 2777169689Skan value_set_node_t node; 2778169689Skan 2779169689Skan for (node = exprset->head; node; node = node->next) 2780169689Skan { 2781169689Skan if (TREE_CODE (node->expr) == SSA_NAME) 2782169689Skan { 2783169689Skan vn_add (node->expr, eprime); 2784169689Skan pre_stats.constified++; 2785169689Skan } 2786169689Skan } 2787169689Skan } 2788169689Skan free (avail); 2789169689Skan } 2790169689Skan } 2791169689Skan } 2792169689Skan } 2793169689Skan } 2794169689Skan for (son = first_dom_son (CDI_DOMINATORS, block); 2795169689Skan son; 2796169689Skan son = next_dom_son (CDI_DOMINATORS, son)) 2797169689Skan { 2798169689Skan new_stuff |= insert_aux (son); 2799169689Skan } 2800169689Skan 2801169689Skan return new_stuff; 2802169689Skan} 2803169689Skan 2804169689Skan/* Perform insertion of partially redundant values. */ 2805169689Skan 2806169689Skanstatic void 2807169689Skaninsert (void) 2808169689Skan{ 2809169689Skan bool new_stuff = true; 2810169689Skan basic_block bb; 2811169689Skan int num_iterations = 0; 2812169689Skan 2813169689Skan FOR_ALL_BB (bb) 2814169689Skan NEW_SETS (bb) = bitmap_set_new (); 2815169689Skan 2816169689Skan while (new_stuff) 2817169689Skan { 2818169689Skan num_iterations++; 2819169689Skan new_stuff = false; 2820169689Skan new_stuff = insert_aux (ENTRY_BLOCK_PTR); 2821169689Skan } 2822169689Skan if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS)) 2823169689Skan fprintf (dump_file, "insert required %d iterations\n", num_iterations); 2824169689Skan} 2825169689Skan 2826169689Skan 2827169689Skan/* Return true if VAR is an SSA variable with no defining statement in 2828169689Skan this procedure, *AND* isn't a live-on-entry parameter. */ 2829169689Skan 2830169689Skanstatic bool 2831169689Skanis_undefined_value (tree expr) 2832169689Skan{ 2833169689Skan return (TREE_CODE (expr) == SSA_NAME 2834169689Skan && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr)) 2835169689Skan /* PARM_DECLs and hard registers are always defined. */ 2836169689Skan && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL); 2837169689Skan} 2838169689Skan 2839169689Skan 2840169689Skan/* Given an SSA variable VAR and an expression EXPR, compute the value 2841169689Skan number for EXPR and create a value handle (VAL) for it. If VAR and 2842169689Skan EXPR are not the same, associate VAL with VAR. Finally, add VAR to 2843169689Skan S1 and its value handle to S2. 2844169689Skan 2845169689Skan VUSES represent the virtual use operands associated with EXPR (if 2846169689Skan any). */ 2847169689Skan 2848169689Skanstatic inline void 2849169689Skanadd_to_sets (tree var, tree expr, tree stmt, bitmap_set_t s1, 2850169689Skan bitmap_set_t s2) 2851169689Skan{ 2852169689Skan tree val = vn_lookup_or_add (expr, stmt); 2853169689Skan 2854169689Skan /* VAR and EXPR may be the same when processing statements for which 2855169689Skan we are not computing value numbers (e.g., non-assignments, or 2856169689Skan statements that make aliased stores). In those cases, we are 2857169689Skan only interested in making VAR available as its own value. */ 2858169689Skan if (var != expr) 2859169689Skan vn_add (var, val); 2860169689Skan 2861169689Skan if (s1) 2862169689Skan bitmap_insert_into_set (s1, var); 2863169689Skan bitmap_value_insert_into_set (s2, var); 2864169689Skan} 2865169689Skan 2866169689Skan 2867169689Skan/* Given a unary or binary expression EXPR, create and return a new 2868169689Skan expression with the same structure as EXPR but with its operands 2869169689Skan replaced with the value handles of each of the operands of EXPR. 2870169689Skan 2871169689Skan VUSES represent the virtual use operands associated with EXPR (if 2872169689Skan any). Insert EXPR's operands into the EXP_GEN set for BLOCK. */ 2873169689Skan 2874169689Skanstatic inline tree 2875169689Skancreate_value_expr_from (tree expr, basic_block block, tree stmt) 2876169689Skan{ 2877169689Skan int i; 2878169689Skan enum tree_code code = TREE_CODE (expr); 2879169689Skan tree vexpr; 2880169689Skan alloc_pool pool; 2881169689Skan 2882169689Skan gcc_assert (TREE_CODE_CLASS (code) == tcc_unary 2883169689Skan || TREE_CODE_CLASS (code) == tcc_binary 2884169689Skan || TREE_CODE_CLASS (code) == tcc_comparison 2885169689Skan || TREE_CODE_CLASS (code) == tcc_reference 2886169689Skan || TREE_CODE_CLASS (code) == tcc_expression 2887169689Skan || TREE_CODE_CLASS (code) == tcc_exceptional 2888169689Skan || TREE_CODE_CLASS (code) == tcc_declaration); 2889169689Skan 2890169689Skan if (TREE_CODE_CLASS (code) == tcc_unary) 2891169689Skan pool = unary_node_pool; 2892169689Skan else if (TREE_CODE_CLASS (code) == tcc_reference) 2893169689Skan pool = reference_node_pool; 2894169689Skan else if (TREE_CODE_CLASS (code) == tcc_binary) 2895169689Skan pool = binary_node_pool; 2896169689Skan else if (TREE_CODE_CLASS (code) == tcc_comparison) 2897169689Skan pool = comparison_node_pool; 2898169689Skan else if (TREE_CODE_CLASS (code) == tcc_exceptional) 2899169689Skan { 2900169689Skan gcc_assert (code == TREE_LIST); 2901169689Skan pool = list_node_pool; 2902169689Skan } 2903169689Skan else 2904169689Skan { 2905169689Skan gcc_assert (code == CALL_EXPR); 2906169689Skan pool = expression_node_pool; 2907169689Skan } 2908169689Skan 2909169689Skan vexpr = (tree) pool_alloc (pool); 2910169689Skan memcpy (vexpr, expr, tree_size (expr)); 2911169689Skan 2912169689Skan /* This case is only for TREE_LIST's that appear as part of 2913169689Skan CALL_EXPR's. Anything else is a bug, but we can't easily verify 2914169689Skan this, hence this comment. TREE_LIST is not handled by the 2915169689Skan general case below is because they don't have a fixed length, or 2916169689Skan operands, so you can't access purpose/value/chain through 2917169689Skan TREE_OPERAND macros. */ 2918169689Skan 2919169689Skan if (code == TREE_LIST) 2920169689Skan { 2921169689Skan tree op = NULL_TREE; 2922169689Skan tree temp = NULL_TREE; 2923169689Skan if (TREE_CHAIN (vexpr)) 2924169689Skan temp = create_value_expr_from (TREE_CHAIN (vexpr), block, stmt); 2925169689Skan TREE_CHAIN (vexpr) = temp ? temp : TREE_CHAIN (vexpr); 2926169689Skan 2927169689Skan 2928169689Skan /* Recursively value-numberize reference ops. */ 2929169689Skan if (REFERENCE_CLASS_P (TREE_VALUE (vexpr))) 2930169689Skan { 2931169689Skan tree tempop; 2932169689Skan op = TREE_VALUE (vexpr); 2933169689Skan tempop = create_value_expr_from (op, block, stmt); 2934169689Skan op = tempop ? tempop : op; 2935169689Skan 2936169689Skan TREE_VALUE (vexpr) = vn_lookup_or_add (op, stmt); 2937169689Skan } 2938169689Skan else 2939169689Skan { 2940169689Skan op = TREE_VALUE (vexpr); 2941169689Skan TREE_VALUE (vexpr) = vn_lookup_or_add (TREE_VALUE (vexpr), NULL); 2942169689Skan } 2943169689Skan /* This is the equivalent of inserting op into EXP_GEN like we 2944169689Skan do below */ 2945169689Skan if (!is_undefined_value (op)) 2946169689Skan value_insert_into_set (EXP_GEN (block), op); 2947169689Skan 2948169689Skan return vexpr; 2949169689Skan } 2950169689Skan 2951169689Skan for (i = 0; i < TREE_CODE_LENGTH (code); i++) 2952169689Skan { 2953169689Skan tree val, op; 2954169689Skan 2955169689Skan op = TREE_OPERAND (expr, i); 2956169689Skan if (op == NULL_TREE) 2957169689Skan continue; 2958169689Skan 2959169689Skan /* Recursively value-numberize reference ops and tree lists. */ 2960169689Skan if (REFERENCE_CLASS_P (op)) 2961169689Skan { 2962169689Skan tree tempop = create_value_expr_from (op, block, stmt); 2963169689Skan op = tempop ? tempop : op; 2964169689Skan val = vn_lookup_or_add (op, stmt); 2965169689Skan } 2966169689Skan else if (TREE_CODE (op) == TREE_LIST) 2967169689Skan { 2968169689Skan tree tempop; 2969169689Skan 2970169689Skan gcc_assert (TREE_CODE (expr) == CALL_EXPR); 2971169689Skan tempop = create_value_expr_from (op, block, stmt); 2972169689Skan 2973169689Skan op = tempop ? tempop : op; 2974169689Skan vn_lookup_or_add (op, NULL); 2975169689Skan /* Unlike everywhere else, we do *not* want to replace the 2976169689Skan TREE_LIST itself with a value number, because support 2977169689Skan functions we call will blow up. */ 2978169689Skan val = op; 2979169689Skan } 2980169689Skan else 2981169689Skan /* Create a value handle for OP and add it to VEXPR. */ 2982169689Skan val = vn_lookup_or_add (op, NULL); 2983169689Skan 2984169689Skan if (!is_undefined_value (op) && TREE_CODE (op) != TREE_LIST) 2985169689Skan value_insert_into_set (EXP_GEN (block), op); 2986169689Skan 2987169689Skan if (TREE_CODE (val) == VALUE_HANDLE) 2988169689Skan TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i)); 2989169689Skan 2990169689Skan TREE_OPERAND (vexpr, i) = val; 2991169689Skan } 2992169689Skan 2993169689Skan return vexpr; 2994169689Skan} 2995169689Skan 2996169689Skan 2997169689Skan 2998169689Skan/* Insert extra phis to merge values that are fully available from 2999169689Skan preds of BLOCK, but have no dominating representative coming from 3000169689Skan block DOM. */ 3001169689Skan 3002169689Skanstatic void 3003169689Skaninsert_extra_phis (basic_block block, basic_block dom) 3004169689Skan{ 3005169689Skan 3006169689Skan if (!single_pred_p (block)) 3007169689Skan { 3008169689Skan edge e; 3009169689Skan edge_iterator ei; 3010169689Skan bool first = true; 3011169689Skan bitmap_set_t tempset = bitmap_set_new (); 3012169689Skan 3013169689Skan FOR_EACH_EDGE (e, ei, block->preds) 3014169689Skan { 3015169689Skan /* We cannot handle abnormal incoming edges correctly. */ 3016169689Skan if (e->flags & EDGE_ABNORMAL) 3017169689Skan return; 3018169689Skan 3019169689Skan if (first) 3020169689Skan { 3021169689Skan bitmap_set_copy (tempset, AVAIL_OUT (e->src)); 3022169689Skan first = false; 3023169689Skan } 3024169689Skan else 3025169689Skan bitmap_set_and (tempset, AVAIL_OUT (e->src)); 3026169689Skan } 3027169689Skan 3028169689Skan if (dom) 3029169689Skan bitmap_set_and_compl (tempset, AVAIL_OUT (dom)); 3030169689Skan 3031169689Skan if (!bitmap_set_empty_p (tempset)) 3032169689Skan { 3033169689Skan unsigned int i; 3034169689Skan bitmap_iterator bi; 3035169689Skan 3036169689Skan EXECUTE_IF_SET_IN_BITMAP (tempset->expressions, 0, i, bi) 3037169689Skan { 3038169689Skan tree name = ssa_name (i); 3039169689Skan tree val = get_value_handle (name); 3040169689Skan tree temp; 3041169689Skan 3042169689Skan if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) 3043169689Skan continue; 3044169689Skan 3045169689Skan if (!mergephitemp 3046169689Skan || TREE_TYPE (name) != TREE_TYPE (mergephitemp)) 3047169689Skan { 3048169689Skan mergephitemp = create_tmp_var (TREE_TYPE (name), 3049169689Skan "mergephitmp"); 3050169689Skan get_var_ann (mergephitemp); 3051169689Skan } 3052169689Skan temp = mergephitemp; 3053169689Skan 3054169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3055169689Skan { 3056169689Skan fprintf (dump_file, "Creating phi "); 3057169689Skan print_generic_expr (dump_file, temp, 0); 3058169689Skan fprintf (dump_file, " to merge available but not dominating values "); 3059169689Skan } 3060169689Skan 3061169689Skan add_referenced_var (temp); 3062169689Skan temp = create_phi_node (temp, block); 3063169689Skan NECESSARY (temp) = 0; 3064169689Skan VEC_safe_push (tree, heap, inserted_exprs, temp); 3065169689Skan 3066169689Skan FOR_EACH_EDGE (e, ei, block->preds) 3067169689Skan { 3068169689Skan tree leader = bitmap_find_leader (AVAIL_OUT (e->src), val); 3069169689Skan 3070169689Skan gcc_assert (leader); 3071169689Skan add_phi_arg (temp, leader, e); 3072169689Skan 3073169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3074169689Skan { 3075169689Skan print_generic_expr (dump_file, leader, 0); 3076169689Skan fprintf (dump_file, " in block %d,", e->src->index); 3077169689Skan } 3078169689Skan } 3079169689Skan 3080169689Skan vn_add (PHI_RESULT (temp), val); 3081169689Skan 3082169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3083169689Skan fprintf (dump_file, "\n"); 3084169689Skan } 3085169689Skan } 3086169689Skan } 3087169689Skan} 3088169689Skan 3089169689Skan/* Given a statement STMT and its right hand side which is a load, try 3090169689Skan to look for the expression stored in the location for the load, and 3091169689Skan return true if a useful equivalence was recorded for LHS. */ 3092169689Skan 3093169689Skanstatic bool 3094169689Skantry_look_through_load (tree lhs, tree mem_ref, tree stmt, basic_block block) 3095169689Skan{ 3096169689Skan tree store_stmt = NULL; 3097169689Skan tree rhs; 3098169689Skan ssa_op_iter i; 3099169689Skan tree vuse; 3100169689Skan 3101169689Skan FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES) 3102169689Skan { 3103169689Skan tree def_stmt; 3104169689Skan 3105169689Skan gcc_assert (TREE_CODE (vuse) == SSA_NAME); 3106169689Skan def_stmt = SSA_NAME_DEF_STMT (vuse); 3107169689Skan 3108169689Skan /* If there is no useful statement for this VUSE, we'll not find a 3109169689Skan useful expression to return either. Likewise, if there is a 3110169689Skan statement but it is not a simple assignment or it has virtual 3111169689Skan uses, we can stop right here. Note that this means we do 3112169689Skan not look through PHI nodes, which is intentional. */ 3113169689Skan if (!def_stmt 3114169689Skan || TREE_CODE (def_stmt) != MODIFY_EXPR 3115169689Skan || !ZERO_SSA_OPERANDS (def_stmt, SSA_OP_VIRTUAL_USES)) 3116169689Skan return false; 3117169689Skan 3118169689Skan /* If this is not the same statement as one we have looked at for 3119169689Skan another VUSE of STMT already, we have two statements producing 3120169689Skan something that reaches our STMT. */ 3121169689Skan if (store_stmt && store_stmt != def_stmt) 3122169689Skan return false; 3123169689Skan else 3124169689Skan { 3125169689Skan /* Is this a store to the exact same location as the one we are 3126169689Skan loading from in STMT? */ 3127169689Skan if (!operand_equal_p (TREE_OPERAND (def_stmt, 0), mem_ref, 0)) 3128169689Skan return false; 3129169689Skan 3130169689Skan /* Otherwise remember this statement and see if all other VUSEs 3131169689Skan come from the same statement. */ 3132169689Skan store_stmt = def_stmt; 3133169689Skan } 3134169689Skan } 3135169689Skan 3136169689Skan /* Alright then, we have visited all VUSEs of STMT and we've determined 3137169689Skan that all of them come from the same statement STORE_STMT. See if there 3138169689Skan is a useful expression we can deduce from STORE_STMT. */ 3139169689Skan rhs = TREE_OPERAND (store_stmt, 1); 3140169689Skan if ((TREE_CODE (rhs) == SSA_NAME 3141169689Skan && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs)) 3142169689Skan || is_gimple_min_invariant (rhs) 3143169689Skan || TREE_CODE (rhs) == ADDR_EXPR 3144169689Skan || TREE_INVARIANT (rhs)) 3145169689Skan { 3146169689Skan 3147169689Skan /* Yay! Compute a value number for the RHS of the statement and 3148169689Skan add its value to the AVAIL_OUT set for the block. Add the LHS 3149169689Skan to TMP_GEN. */ 3150169689Skan add_to_sets (lhs, rhs, store_stmt, TMP_GEN (block), AVAIL_OUT (block)); 3151169689Skan if (TREE_CODE (rhs) == SSA_NAME 3152169689Skan && !is_undefined_value (rhs)) 3153169689Skan value_insert_into_set (EXP_GEN (block), rhs); 3154169689Skan return true; 3155169689Skan } 3156169689Skan 3157169689Skan return false; 3158169689Skan} 3159169689Skan 3160169689Skan/* Return a copy of NODE that is stored in the temporary alloc_pool's. 3161169689Skan This is made recursively true, so that the operands are stored in 3162169689Skan the pool as well. */ 3163169689Skan 3164169689Skanstatic tree 3165169689Skanpoolify_tree (tree node) 3166169689Skan{ 3167169689Skan switch (TREE_CODE (node)) 3168169689Skan { 3169169689Skan case INDIRECT_REF: 3170169689Skan { 3171169689Skan tree temp = pool_alloc (reference_node_pool); 3172169689Skan memcpy (temp, node, tree_size (node)); 3173169689Skan TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0)); 3174169689Skan return temp; 3175169689Skan } 3176169689Skan break; 3177169689Skan case MODIFY_EXPR: 3178169689Skan { 3179169689Skan tree temp = pool_alloc (modify_expr_node_pool); 3180169689Skan memcpy (temp, node, tree_size (node)); 3181169689Skan TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0)); 3182169689Skan TREE_OPERAND (temp, 1) = poolify_tree (TREE_OPERAND (temp, 1)); 3183169689Skan return temp; 3184169689Skan } 3185169689Skan break; 3186169689Skan case SSA_NAME: 3187169689Skan case INTEGER_CST: 3188169689Skan case STRING_CST: 3189169689Skan case REAL_CST: 3190169689Skan case PARM_DECL: 3191169689Skan case VAR_DECL: 3192169689Skan case RESULT_DECL: 3193169689Skan return node; 3194169689Skan default: 3195169689Skan gcc_unreachable (); 3196169689Skan } 3197169689Skan} 3198169689Skan 3199169689Skanstatic tree modify_expr_template; 3200169689Skan 3201169689Skan/* Allocate a MODIFY_EXPR with TYPE, and operands OP1, OP2 in the 3202169689Skan alloc pools and return it. */ 3203169689Skanstatic tree 3204169689Skanpoolify_modify_expr (tree type, tree op1, tree op2) 3205169689Skan{ 3206169689Skan if (modify_expr_template == NULL) 3207169689Skan modify_expr_template = build2 (MODIFY_EXPR, type, op1, op2); 3208169689Skan 3209169689Skan TREE_OPERAND (modify_expr_template, 0) = op1; 3210169689Skan TREE_OPERAND (modify_expr_template, 1) = op2; 3211169689Skan TREE_TYPE (modify_expr_template) = type; 3212169689Skan 3213169689Skan return poolify_tree (modify_expr_template); 3214169689Skan} 3215169689Skan 3216169689Skan 3217169689Skan/* For each real store operation of the form 3218169689Skan *a = <value> that we see, create a corresponding fake store of the 3219169689Skan form storetmp_<version> = *a. 3220169689Skan 3221169689Skan This enables AVAIL computation to mark the results of stores as 3222169689Skan available. Without this, you'd need to do some computation to 3223169689Skan mark the result of stores as ANTIC and AVAIL at all the right 3224169689Skan points. 3225169689Skan To save memory, we keep the store 3226169689Skan statements pool allocated until we decide whether they are 3227169689Skan necessary or not. */ 3228169689Skan 3229169689Skanstatic void 3230169689Skaninsert_fake_stores (void) 3231169689Skan{ 3232169689Skan basic_block block; 3233169689Skan 3234169689Skan FOR_ALL_BB (block) 3235169689Skan { 3236169689Skan block_stmt_iterator bsi; 3237169689Skan for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi)) 3238169689Skan { 3239169689Skan tree stmt = bsi_stmt (bsi); 3240169689Skan 3241169689Skan /* We can't generate SSA names for stores that are complex 3242169689Skan or aggregate. We also want to ignore things whose 3243169689Skan virtual uses occur in abnormal phis. */ 3244169689Skan 3245169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR 3246169689Skan && TREE_CODE (TREE_OPERAND (stmt, 0)) == INDIRECT_REF 3247169689Skan && !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 0))) 3248169689Skan && TREE_CODE (TREE_TYPE (TREE_OPERAND (stmt, 0))) != COMPLEX_TYPE) 3249169689Skan { 3250169689Skan ssa_op_iter iter; 3251169689Skan def_operand_p defp; 3252169689Skan tree lhs = TREE_OPERAND (stmt, 0); 3253169689Skan tree rhs = TREE_OPERAND (stmt, 1); 3254169689Skan tree new; 3255169689Skan bool notokay = false; 3256169689Skan 3257169689Skan FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS) 3258169689Skan { 3259169689Skan tree defvar = DEF_FROM_PTR (defp); 3260169689Skan if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defvar)) 3261169689Skan { 3262169689Skan notokay = true; 3263169689Skan break; 3264169689Skan } 3265169689Skan } 3266169689Skan 3267169689Skan if (notokay) 3268169689Skan continue; 3269169689Skan 3270169689Skan if (!storetemp || TREE_TYPE (rhs) != TREE_TYPE (storetemp)) 3271169689Skan { 3272169689Skan storetemp = create_tmp_var (TREE_TYPE (rhs), "storetmp"); 3273169689Skan get_var_ann (storetemp); 3274169689Skan } 3275169689Skan 3276169689Skan new = poolify_modify_expr (TREE_TYPE (stmt), storetemp, lhs); 3277169689Skan 3278169689Skan lhs = make_ssa_name (storetemp, new); 3279169689Skan TREE_OPERAND (new, 0) = lhs; 3280169689Skan create_ssa_artficial_load_stmt (new, stmt); 3281169689Skan 3282169689Skan NECESSARY (new) = 0; 3283169689Skan VEC_safe_push (tree, heap, inserted_exprs, new); 3284169689Skan VEC_safe_push (tree, heap, need_creation, new); 3285169689Skan bsi_insert_after (&bsi, new, BSI_NEW_STMT); 3286169689Skan } 3287169689Skan } 3288169689Skan } 3289169689Skan} 3290169689Skan 3291169689Skan/* Turn the pool allocated fake stores that we created back into real 3292169689Skan GC allocated ones if they turned out to be necessary to PRE some 3293169689Skan expressions. */ 3294169689Skan 3295169689Skanstatic void 3296169689Skanrealify_fake_stores (void) 3297169689Skan{ 3298169689Skan unsigned int i; 3299169689Skan tree stmt; 3300169689Skan 3301169689Skan for (i = 0; VEC_iterate (tree, need_creation, i, stmt); i++) 3302169689Skan { 3303169689Skan if (NECESSARY (stmt)) 3304169689Skan { 3305169689Skan block_stmt_iterator bsi; 3306169689Skan tree newstmt; 3307169689Skan 3308169689Skan /* Mark the temp variable as referenced */ 3309169689Skan add_referenced_var (SSA_NAME_VAR (TREE_OPERAND (stmt, 0))); 3310169689Skan 3311169689Skan /* Put the new statement in GC memory, fix up the 3312169689Skan SSA_NAME_DEF_STMT on it, and then put it in place of 3313169689Skan the old statement before the store in the IR stream 3314169689Skan as a plain ssa name copy. */ 3315169689Skan bsi = bsi_for_stmt (stmt); 3316169689Skan bsi_prev (&bsi); 3317169689Skan newstmt = build2 (MODIFY_EXPR, void_type_node, 3318169689Skan TREE_OPERAND (stmt, 0), 3319169689Skan TREE_OPERAND (bsi_stmt (bsi), 1)); 3320169689Skan SSA_NAME_DEF_STMT (TREE_OPERAND (newstmt, 0)) = newstmt; 3321169689Skan bsi_insert_before (&bsi, newstmt, BSI_SAME_STMT); 3322169689Skan bsi = bsi_for_stmt (stmt); 3323169689Skan bsi_remove (&bsi, true); 3324169689Skan } 3325169689Skan else 3326169689Skan release_defs (stmt); 3327169689Skan } 3328169689Skan} 3329169689Skan 3330169689Skan/* Tree-combine a value number expression *EXPR_P that does a type 3331169689Skan conversion with the value number expression of its operand. 3332169689Skan Returns true, if *EXPR_P simplifies to a value number or 3333169689Skan gimple min-invariant expression different from EXPR_P and 3334169689Skan sets *EXPR_P to the simplified expression value number. 3335169689Skan Otherwise returns false and does not change *EXPR_P. */ 3336169689Skan 3337169689Skanstatic bool 3338169689Skantry_combine_conversion (tree *expr_p) 3339169689Skan{ 3340169689Skan tree expr = *expr_p; 3341169689Skan tree t; 3342169689Skan 3343169689Skan if (!((TREE_CODE (expr) == NOP_EXPR 3344169689Skan || TREE_CODE (expr) == CONVERT_EXPR) 3345169689Skan && TREE_CODE (TREE_OPERAND (expr, 0)) == VALUE_HANDLE 3346169689Skan && !VALUE_HANDLE_VUSES (TREE_OPERAND (expr, 0)))) 3347169689Skan return false; 3348169689Skan 3349169689Skan t = fold_unary (TREE_CODE (expr), TREE_TYPE (expr), 3350169689Skan VALUE_HANDLE_EXPR_SET (TREE_OPERAND (expr, 0))->head->expr); 3351169689Skan if (!t) 3352169689Skan return false; 3353169689Skan 3354169689Skan /* Strip useless type conversions, which is safe in the optimizers but 3355169689Skan not generally in fold. */ 3356169689Skan STRIP_USELESS_TYPE_CONVERSION (t); 3357169689Skan 3358169689Skan /* Disallow value expressions we have no value number for already, as 3359169689Skan we would miss a leader for it here. */ 3360169689Skan if (!(TREE_CODE (t) == VALUE_HANDLE 3361169689Skan || is_gimple_min_invariant (t))) 3362169689Skan t = vn_lookup (t, NULL); 3363169689Skan 3364169689Skan if (t && t != expr) 3365169689Skan { 3366169689Skan *expr_p = t; 3367169689Skan return true; 3368169689Skan } 3369169689Skan return false; 3370169689Skan} 3371169689Skan 3372169689Skan/* Compute the AVAIL set for all basic blocks. 3373169689Skan 3374169689Skan This function performs value numbering of the statements in each basic 3375169689Skan block. The AVAIL sets are built from information we glean while doing 3376169689Skan this value numbering, since the AVAIL sets contain only one entry per 3377169689Skan value. 3378169689Skan 3379169689Skan AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)]. 3380169689Skan AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */ 3381169689Skan 3382169689Skanstatic void 3383169689Skancompute_avail (void) 3384169689Skan{ 3385169689Skan basic_block block, son; 3386169689Skan basic_block *worklist; 3387169689Skan size_t sp = 0; 3388169689Skan tree param; 3389169689Skan /* For arguments with default definitions, we pretend they are 3390169689Skan defined in the entry block. */ 3391169689Skan for (param = DECL_ARGUMENTS (current_function_decl); 3392169689Skan param; 3393169689Skan param = TREE_CHAIN (param)) 3394169689Skan { 3395169689Skan if (default_def (param) != NULL) 3396169689Skan { 3397169689Skan tree def = default_def (param); 3398169689Skan vn_lookup_or_add (def, NULL); 3399169689Skan bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def); 3400169689Skan bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def); 3401169689Skan } 3402169689Skan } 3403169689Skan 3404169689Skan /* Likewise for the static chain decl. */ 3405169689Skan if (cfun->static_chain_decl) 3406169689Skan { 3407169689Skan param = cfun->static_chain_decl; 3408169689Skan if (default_def (param) != NULL) 3409169689Skan { 3410169689Skan tree def = default_def (param); 3411169689Skan vn_lookup_or_add (def, NULL); 3412169689Skan bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def); 3413169689Skan bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def); 3414169689Skan } 3415169689Skan } 3416169689Skan 3417169689Skan /* Allocate the worklist. */ 3418169689Skan worklist = XNEWVEC (basic_block, n_basic_blocks); 3419169689Skan 3420169689Skan /* Seed the algorithm by putting the dominator children of the entry 3421169689Skan block on the worklist. */ 3422169689Skan for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR); 3423169689Skan son; 3424169689Skan son = next_dom_son (CDI_DOMINATORS, son)) 3425169689Skan worklist[sp++] = son; 3426169689Skan 3427169689Skan /* Loop until the worklist is empty. */ 3428169689Skan while (sp) 3429169689Skan { 3430169689Skan block_stmt_iterator bsi; 3431169689Skan tree stmt, phi; 3432169689Skan basic_block dom; 3433169689Skan unsigned int stmt_uid = 1; 3434169689Skan 3435169689Skan /* Pick a block from the worklist. */ 3436169689Skan block = worklist[--sp]; 3437169689Skan 3438169689Skan /* Initially, the set of available values in BLOCK is that of 3439169689Skan its immediate dominator. */ 3440169689Skan dom = get_immediate_dominator (CDI_DOMINATORS, block); 3441169689Skan if (dom) 3442169689Skan bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom)); 3443169689Skan 3444169689Skan if (!in_fre) 3445169689Skan insert_extra_phis (block, dom); 3446169689Skan 3447169689Skan /* Generate values for PHI nodes. */ 3448169689Skan for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi)) 3449169689Skan /* We have no need for virtual phis, as they don't represent 3450169689Skan actual computations. */ 3451169689Skan if (is_gimple_reg (PHI_RESULT (phi))) 3452169689Skan add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL, 3453169689Skan PHI_GEN (block), AVAIL_OUT (block)); 3454169689Skan 3455169689Skan /* Now compute value numbers and populate value sets with all 3456169689Skan the expressions computed in BLOCK. */ 3457169689Skan for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi)) 3458169689Skan { 3459169689Skan stmt_ann_t ann; 3460169689Skan ssa_op_iter iter; 3461169689Skan tree op; 3462169689Skan 3463169689Skan stmt = bsi_stmt (bsi); 3464169689Skan ann = stmt_ann (stmt); 3465169689Skan 3466169689Skan ann->uid = stmt_uid++; 3467169689Skan 3468169689Skan /* For regular value numbering, we are only interested in 3469169689Skan assignments of the form X_i = EXPR, where EXPR represents 3470169689Skan an "interesting" computation, it has no volatile operands 3471169689Skan and X_i doesn't flow through an abnormal edge. */ 3472169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR 3473169689Skan && !ann->has_volatile_ops 3474169689Skan && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME 3475169689Skan && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt, 0))) 3476169689Skan { 3477169689Skan tree lhs = TREE_OPERAND (stmt, 0); 3478169689Skan tree rhs = TREE_OPERAND (stmt, 1); 3479169689Skan 3480169689Skan /* Try to look through loads. */ 3481169689Skan if (TREE_CODE (lhs) == SSA_NAME 3482169689Skan && !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES) 3483169689Skan && try_look_through_load (lhs, rhs, stmt, block)) 3484169689Skan continue; 3485169689Skan 3486169689Skan STRIP_USELESS_TYPE_CONVERSION (rhs); 3487169689Skan if (can_value_number_operation (rhs)) 3488169689Skan { 3489169689Skan /* For value numberable operation, create a 3490169689Skan duplicate expression with the operands replaced 3491169689Skan with the value handles of the original RHS. */ 3492169689Skan tree newt = create_value_expr_from (rhs, block, stmt); 3493169689Skan if (newt) 3494169689Skan { 3495169689Skan /* If we can combine a conversion expression 3496169689Skan with the expression for its operand just 3497169689Skan record the value number for it. */ 3498169689Skan if (try_combine_conversion (&newt)) 3499169689Skan vn_add (lhs, newt); 3500169689Skan else 3501169689Skan { 3502169689Skan tree val = vn_lookup_or_add (newt, stmt); 3503169689Skan vn_add (lhs, val); 3504169689Skan value_insert_into_set (EXP_GEN (block), newt); 3505169689Skan } 3506169689Skan bitmap_insert_into_set (TMP_GEN (block), lhs); 3507169689Skan bitmap_value_insert_into_set (AVAIL_OUT (block), lhs); 3508169689Skan continue; 3509169689Skan } 3510169689Skan } 3511169689Skan else if ((TREE_CODE (rhs) == SSA_NAME 3512169689Skan && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs)) 3513169689Skan || is_gimple_min_invariant (rhs) 3514169689Skan || TREE_CODE (rhs) == ADDR_EXPR 3515169689Skan || TREE_INVARIANT (rhs) 3516169689Skan || DECL_P (rhs)) 3517169689Skan { 3518169689Skan /* Compute a value number for the RHS of the statement 3519169689Skan and add its value to the AVAIL_OUT set for the block. 3520169689Skan Add the LHS to TMP_GEN. */ 3521169689Skan add_to_sets (lhs, rhs, stmt, TMP_GEN (block), 3522169689Skan AVAIL_OUT (block)); 3523169689Skan 3524169689Skan if (TREE_CODE (rhs) == SSA_NAME 3525169689Skan && !is_undefined_value (rhs)) 3526169689Skan value_insert_into_set (EXP_GEN (block), rhs); 3527169689Skan continue; 3528169689Skan } 3529169689Skan } 3530169689Skan 3531169689Skan /* For any other statement that we don't recognize, simply 3532169689Skan make the names generated by the statement available in 3533169689Skan AVAIL_OUT and TMP_GEN. */ 3534169689Skan FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF) 3535169689Skan add_to_sets (op, op, NULL, TMP_GEN (block), AVAIL_OUT (block)); 3536169689Skan 3537169689Skan FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE) 3538169689Skan add_to_sets (op, op, NULL, NULL , AVAIL_OUT (block)); 3539169689Skan } 3540169689Skan 3541169689Skan /* Put the dominator children of BLOCK on the worklist of blocks 3542169689Skan to compute available sets for. */ 3543169689Skan for (son = first_dom_son (CDI_DOMINATORS, block); 3544169689Skan son; 3545169689Skan son = next_dom_son (CDI_DOMINATORS, son)) 3546169689Skan worklist[sp++] = son; 3547169689Skan } 3548169689Skan 3549169689Skan free (worklist); 3550169689Skan} 3551169689Skan 3552169689Skan 3553169689Skan/* Eliminate fully redundant computations. */ 3554169689Skan 3555169689Skanstatic void 3556169689Skaneliminate (void) 3557169689Skan{ 3558169689Skan basic_block b; 3559169689Skan 3560169689Skan FOR_EACH_BB (b) 3561169689Skan { 3562169689Skan block_stmt_iterator i; 3563169689Skan 3564169689Skan for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i)) 3565169689Skan { 3566169689Skan tree stmt = bsi_stmt (i); 3567169689Skan 3568169689Skan /* Lookup the RHS of the expression, see if we have an 3569169689Skan available computation for it. If so, replace the RHS with 3570169689Skan the available computation. */ 3571169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR 3572169689Skan && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME 3573169689Skan && TREE_CODE (TREE_OPERAND (stmt ,1)) != SSA_NAME 3574169689Skan && !is_gimple_min_invariant (TREE_OPERAND (stmt, 1)) 3575169689Skan && !stmt_ann (stmt)->has_volatile_ops) 3576169689Skan { 3577169689Skan tree lhs = TREE_OPERAND (stmt, 0); 3578169689Skan tree *rhs_p = &TREE_OPERAND (stmt, 1); 3579169689Skan tree sprime; 3580169689Skan 3581169689Skan sprime = bitmap_find_leader (AVAIL_OUT (b), 3582169689Skan vn_lookup (lhs, NULL)); 3583169689Skan if (sprime 3584169689Skan && sprime != lhs 3585169689Skan && (TREE_CODE (*rhs_p) != SSA_NAME 3586169689Skan || may_propagate_copy (*rhs_p, sprime))) 3587169689Skan { 3588169689Skan gcc_assert (sprime != *rhs_p); 3589169689Skan 3590169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3591169689Skan { 3592169689Skan fprintf (dump_file, "Replaced "); 3593169689Skan print_generic_expr (dump_file, *rhs_p, 0); 3594169689Skan fprintf (dump_file, " with "); 3595169689Skan print_generic_expr (dump_file, sprime, 0); 3596169689Skan fprintf (dump_file, " in "); 3597169689Skan print_generic_stmt (dump_file, stmt, 0); 3598169689Skan } 3599169689Skan 3600169689Skan if (TREE_CODE (sprime) == SSA_NAME) 3601169689Skan NECESSARY (SSA_NAME_DEF_STMT (sprime)) = 1; 3602169689Skan /* We need to make sure the new and old types actually match, 3603169689Skan which may require adding a simple cast, which fold_convert 3604169689Skan will do for us. */ 3605169689Skan if (TREE_CODE (*rhs_p) != SSA_NAME 3606169689Skan && !tree_ssa_useless_type_conversion_1 (TREE_TYPE (*rhs_p), 3607169689Skan TREE_TYPE (sprime))) 3608169689Skan sprime = fold_convert (TREE_TYPE (*rhs_p), sprime); 3609169689Skan 3610169689Skan pre_stats.eliminations++; 3611169689Skan propagate_tree_value (rhs_p, sprime); 3612169689Skan update_stmt (stmt); 3613169689Skan 3614169689Skan /* If we removed EH side effects from the statement, clean 3615169689Skan its EH information. */ 3616169689Skan if (maybe_clean_or_replace_eh_stmt (stmt, stmt)) 3617169689Skan { 3618169689Skan bitmap_set_bit (need_eh_cleanup, 3619169689Skan bb_for_stmt (stmt)->index); 3620169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3621169689Skan fprintf (dump_file, " Removed EH side effects.\n"); 3622169689Skan } 3623169689Skan } 3624169689Skan } 3625169689Skan } 3626169689Skan } 3627169689Skan} 3628169689Skan 3629169689Skan/* Borrow a bit of tree-ssa-dce.c for the moment. 3630169689Skan XXX: In 4.1, we should be able to just run a DCE pass after PRE, though 3631169689Skan this may be a bit faster, and we may want critical edges kept split. */ 3632169689Skan 3633169689Skan/* If OP's defining statement has not already been determined to be necessary, 3634169689Skan mark that statement necessary. Return the stmt, if it is newly 3635169689Skan necessary. */ 3636169689Skan 3637169689Skanstatic inline tree 3638169689Skanmark_operand_necessary (tree op) 3639169689Skan{ 3640169689Skan tree stmt; 3641169689Skan 3642169689Skan gcc_assert (op); 3643169689Skan 3644169689Skan if (TREE_CODE (op) != SSA_NAME) 3645169689Skan return NULL; 3646169689Skan 3647169689Skan stmt = SSA_NAME_DEF_STMT (op); 3648169689Skan gcc_assert (stmt); 3649169689Skan 3650169689Skan if (NECESSARY (stmt) 3651169689Skan || IS_EMPTY_STMT (stmt)) 3652169689Skan return NULL; 3653169689Skan 3654169689Skan NECESSARY (stmt) = 1; 3655169689Skan return stmt; 3656169689Skan} 3657169689Skan 3658169689Skan/* Because we don't follow exactly the standard PRE algorithm, and decide not 3659169689Skan to insert PHI nodes sometimes, and because value numbering of casts isn't 3660169689Skan perfect, we sometimes end up inserting dead code. This simple DCE-like 3661169689Skan pass removes any insertions we made that weren't actually used. */ 3662169689Skan 3663169689Skanstatic void 3664169689Skanremove_dead_inserted_code (void) 3665169689Skan{ 3666169689Skan VEC(tree,heap) *worklist = NULL; 3667169689Skan int i; 3668169689Skan tree t; 3669169689Skan 3670169689Skan worklist = VEC_alloc (tree, heap, VEC_length (tree, inserted_exprs)); 3671169689Skan for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++) 3672169689Skan { 3673169689Skan if (NECESSARY (t)) 3674169689Skan VEC_quick_push (tree, worklist, t); 3675169689Skan } 3676169689Skan while (VEC_length (tree, worklist) > 0) 3677169689Skan { 3678169689Skan t = VEC_pop (tree, worklist); 3679169689Skan 3680169689Skan /* PHI nodes are somewhat special in that each PHI alternative has 3681169689Skan data and control dependencies. All the statements feeding the 3682169689Skan PHI node's arguments are always necessary. */ 3683169689Skan if (TREE_CODE (t) == PHI_NODE) 3684169689Skan { 3685169689Skan int k; 3686169689Skan 3687169689Skan VEC_reserve (tree, heap, worklist, PHI_NUM_ARGS (t)); 3688169689Skan for (k = 0; k < PHI_NUM_ARGS (t); k++) 3689169689Skan { 3690169689Skan tree arg = PHI_ARG_DEF (t, k); 3691169689Skan if (TREE_CODE (arg) == SSA_NAME) 3692169689Skan { 3693169689Skan arg = mark_operand_necessary (arg); 3694169689Skan if (arg) 3695169689Skan VEC_quick_push (tree, worklist, arg); 3696169689Skan } 3697169689Skan } 3698169689Skan } 3699169689Skan else 3700169689Skan { 3701169689Skan /* Propagate through the operands. Examine all the USE, VUSE and 3702169689Skan V_MAY_DEF operands in this statement. Mark all the statements 3703169689Skan which feed this statement's uses as necessary. */ 3704169689Skan ssa_op_iter iter; 3705169689Skan tree use; 3706169689Skan 3707169689Skan /* The operands of V_MAY_DEF expressions are also needed as they 3708169689Skan represent potential definitions that may reach this 3709169689Skan statement (V_MAY_DEF operands allow us to follow def-def 3710169689Skan links). */ 3711169689Skan 3712169689Skan FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES) 3713169689Skan { 3714169689Skan tree n = mark_operand_necessary (use); 3715169689Skan if (n) 3716169689Skan VEC_safe_push (tree, heap, worklist, n); 3717169689Skan } 3718169689Skan } 3719169689Skan } 3720169689Skan 3721169689Skan for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++) 3722169689Skan { 3723169689Skan if (!NECESSARY (t)) 3724169689Skan { 3725169689Skan block_stmt_iterator bsi; 3726169689Skan 3727169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3728169689Skan { 3729169689Skan fprintf (dump_file, "Removing unnecessary insertion:"); 3730169689Skan print_generic_stmt (dump_file, t, 0); 3731169689Skan } 3732169689Skan 3733169689Skan if (TREE_CODE (t) == PHI_NODE) 3734169689Skan { 3735169689Skan remove_phi_node (t, NULL); 3736169689Skan } 3737169689Skan else 3738169689Skan { 3739169689Skan bsi = bsi_for_stmt (t); 3740169689Skan bsi_remove (&bsi, true); 3741169689Skan release_defs (t); 3742169689Skan } 3743169689Skan } 3744169689Skan } 3745169689Skan VEC_free (tree, heap, worklist); 3746169689Skan} 3747169689Skan 3748169689Skan/* Initialize data structures used by PRE. */ 3749169689Skan 3750169689Skanstatic void 3751169689Skaninit_pre (bool do_fre) 3752169689Skan{ 3753169689Skan basic_block bb; 3754169689Skan 3755169689Skan in_fre = do_fre; 3756169689Skan 3757169689Skan inserted_exprs = NULL; 3758169689Skan need_creation = NULL; 3759169689Skan pretemp = NULL_TREE; 3760169689Skan storetemp = NULL_TREE; 3761169689Skan mergephitemp = NULL_TREE; 3762169689Skan prephitemp = NULL_TREE; 3763169689Skan 3764169689Skan vn_init (); 3765169689Skan if (!do_fre) 3766169689Skan current_loops = loop_optimizer_init (LOOPS_NORMAL); 3767169689Skan 3768169689Skan connect_infinite_loops_to_exit (); 3769169689Skan memset (&pre_stats, 0, sizeof (pre_stats)); 3770169689Skan 3771169689Skan /* If block 0 has more than one predecessor, it means that its PHI 3772169689Skan nodes will have arguments coming from block -1. This creates 3773169689Skan problems for several places in PRE that keep local arrays indexed 3774169689Skan by block number. To prevent this, we split the edge coming from 3775169689Skan ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number 3776169689Skan different than -1 we wouldn't have to hack this. tree-ssa-dce.c 3777169689Skan needs a similar change). */ 3778169689Skan if (!single_pred_p (single_succ (ENTRY_BLOCK_PTR))) 3779169689Skan if (!(single_succ_edge (ENTRY_BLOCK_PTR)->flags & EDGE_ABNORMAL)) 3780169689Skan split_edge (single_succ_edge (ENTRY_BLOCK_PTR)); 3781169689Skan 3782169689Skan FOR_ALL_BB (bb) 3783169689Skan bb->aux = xcalloc (1, sizeof (struct bb_value_sets)); 3784169689Skan 3785169689Skan bitmap_obstack_initialize (&grand_bitmap_obstack); 3786169689Skan phi_translate_table = htab_create (511, expr_pred_trans_hash, 3787169689Skan expr_pred_trans_eq, free); 3788169689Skan value_set_pool = create_alloc_pool ("Value sets", 3789169689Skan sizeof (struct value_set), 30); 3790169689Skan bitmap_set_pool = create_alloc_pool ("Bitmap sets", 3791169689Skan sizeof (struct bitmap_set), 30); 3792169689Skan value_set_node_pool = create_alloc_pool ("Value set nodes", 3793169689Skan sizeof (struct value_set_node), 30); 3794169689Skan calculate_dominance_info (CDI_POST_DOMINATORS); 3795169689Skan calculate_dominance_info (CDI_DOMINATORS); 3796169689Skan binary_node_pool = create_alloc_pool ("Binary tree nodes", 3797169689Skan tree_code_size (PLUS_EXPR), 30); 3798169689Skan unary_node_pool = create_alloc_pool ("Unary tree nodes", 3799169689Skan tree_code_size (NEGATE_EXPR), 30); 3800169689Skan reference_node_pool = create_alloc_pool ("Reference tree nodes", 3801169689Skan tree_code_size (ARRAY_REF), 30); 3802169689Skan expression_node_pool = create_alloc_pool ("Expression tree nodes", 3803169689Skan tree_code_size (CALL_EXPR), 30); 3804169689Skan list_node_pool = create_alloc_pool ("List tree nodes", 3805169689Skan tree_code_size (TREE_LIST), 30); 3806169689Skan comparison_node_pool = create_alloc_pool ("Comparison tree nodes", 3807169689Skan tree_code_size (EQ_EXPR), 30); 3808169689Skan modify_expr_node_pool = create_alloc_pool ("MODIFY_EXPR nodes", 3809169689Skan tree_code_size (MODIFY_EXPR), 3810169689Skan 30); 3811169689Skan modify_expr_template = NULL; 3812169689Skan 3813169689Skan FOR_ALL_BB (bb) 3814169689Skan { 3815169689Skan EXP_GEN (bb) = set_new (true); 3816169689Skan PHI_GEN (bb) = bitmap_set_new (); 3817169689Skan TMP_GEN (bb) = bitmap_set_new (); 3818169689Skan AVAIL_OUT (bb) = bitmap_set_new (); 3819169689Skan } 3820169689Skan 3821169689Skan need_eh_cleanup = BITMAP_ALLOC (NULL); 3822169689Skan} 3823169689Skan 3824169689Skan 3825169689Skan/* Deallocate data structures used by PRE. */ 3826169689Skan 3827169689Skanstatic void 3828169689Skanfini_pre (bool do_fre) 3829169689Skan{ 3830169689Skan basic_block bb; 3831169689Skan unsigned int i; 3832169689Skan 3833169689Skan VEC_free (tree, heap, inserted_exprs); 3834169689Skan VEC_free (tree, heap, need_creation); 3835169689Skan bitmap_obstack_release (&grand_bitmap_obstack); 3836169689Skan free_alloc_pool (value_set_pool); 3837169689Skan free_alloc_pool (bitmap_set_pool); 3838169689Skan free_alloc_pool (value_set_node_pool); 3839169689Skan free_alloc_pool (binary_node_pool); 3840169689Skan free_alloc_pool (reference_node_pool); 3841169689Skan free_alloc_pool (unary_node_pool); 3842169689Skan free_alloc_pool (list_node_pool); 3843169689Skan free_alloc_pool (expression_node_pool); 3844169689Skan free_alloc_pool (comparison_node_pool); 3845169689Skan free_alloc_pool (modify_expr_node_pool); 3846169689Skan htab_delete (phi_translate_table); 3847169689Skan remove_fake_exit_edges (); 3848169689Skan 3849169689Skan FOR_ALL_BB (bb) 3850169689Skan { 3851169689Skan free (bb->aux); 3852169689Skan bb->aux = NULL; 3853169689Skan } 3854169689Skan 3855169689Skan free_dominance_info (CDI_POST_DOMINATORS); 3856169689Skan vn_delete (); 3857169689Skan 3858169689Skan if (!bitmap_empty_p (need_eh_cleanup)) 3859169689Skan { 3860169689Skan tree_purge_all_dead_eh_edges (need_eh_cleanup); 3861169689Skan cleanup_tree_cfg (); 3862169689Skan } 3863169689Skan 3864169689Skan BITMAP_FREE (need_eh_cleanup); 3865169689Skan 3866169689Skan /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant 3867169689Skan future we will want them to be persistent though. */ 3868169689Skan for (i = 0; i < num_ssa_names; i++) 3869169689Skan { 3870169689Skan tree name = ssa_name (i); 3871169689Skan 3872169689Skan if (!name) 3873169689Skan continue; 3874169689Skan 3875169689Skan if (SSA_NAME_VALUE (name) 3876169689Skan && TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE) 3877169689Skan SSA_NAME_VALUE (name) = NULL; 3878169689Skan } 3879169689Skan if (!do_fre && current_loops) 3880169689Skan { 3881169689Skan loop_optimizer_finalize (current_loops); 3882169689Skan current_loops = NULL; 3883169689Skan } 3884169689Skan} 3885169689Skan 3886169689Skan/* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller 3887169689Skan only wants to do full redundancy elimination. */ 3888169689Skan 3889169689Skanstatic void 3890169689Skanexecute_pre (bool do_fre) 3891169689Skan{ 3892169689Skan init_pre (do_fre); 3893169689Skan 3894169689Skan if (!do_fre) 3895169689Skan insert_fake_stores (); 3896169689Skan 3897169689Skan /* Collect and value number expressions computed in each basic block. */ 3898169689Skan compute_avail (); 3899169689Skan 3900169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3901169689Skan { 3902169689Skan basic_block bb; 3903169689Skan 3904169689Skan FOR_ALL_BB (bb) 3905169689Skan { 3906169689Skan print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index); 3907169689Skan bitmap_print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", 3908169689Skan bb->index); 3909169689Skan bitmap_print_value_set (dump_file, AVAIL_OUT (bb), "avail_out", 3910169689Skan bb->index); 3911169689Skan } 3912169689Skan } 3913169689Skan 3914169689Skan /* Insert can get quite slow on an incredibly large number of basic 3915169689Skan blocks due to some quadratic behavior. Until this behavior is 3916169689Skan fixed, don't run it when he have an incredibly large number of 3917169689Skan bb's. If we aren't going to run insert, there is no point in 3918169689Skan computing ANTIC, either, even though it's plenty fast. */ 3919169689Skan if (!do_fre && n_basic_blocks < 4000) 3920169689Skan { 3921169689Skan vuse_names = XCNEWVEC (bitmap, num_ssa_names); 3922169689Skan compute_rvuse_and_antic_safe (); 3923169689Skan compute_antic (); 3924169689Skan insert (); 3925169689Skan free (vuse_names); 3926169689Skan } 3927169689Skan 3928169689Skan /* Remove all the redundant expressions. */ 3929169689Skan eliminate (); 3930169689Skan 3931169689Skan 3932169689Skan if (dump_file && (dump_flags & TDF_STATS)) 3933169689Skan { 3934169689Skan fprintf (dump_file, "Insertions: %d\n", pre_stats.insertions); 3935169689Skan fprintf (dump_file, "New PHIs: %d\n", pre_stats.phis); 3936169689Skan fprintf (dump_file, "Eliminated: %d\n", pre_stats.eliminations); 3937169689Skan fprintf (dump_file, "Constified: %d\n", pre_stats.constified); 3938169689Skan } 3939169689Skan 3940169689Skan bsi_commit_edge_inserts (); 3941169689Skan 3942169689Skan if (!do_fre) 3943169689Skan { 3944169689Skan remove_dead_inserted_code (); 3945169689Skan realify_fake_stores (); 3946169689Skan } 3947169689Skan 3948169689Skan fini_pre (do_fre); 3949169689Skan 3950169689Skan} 3951169689Skan 3952169689Skan/* Gate and execute functions for PRE. */ 3953169689Skan 3954169689Skanstatic unsigned int 3955169689Skando_pre (void) 3956169689Skan{ 3957169689Skan execute_pre (false); 3958169689Skan return 0; 3959169689Skan} 3960169689Skan 3961169689Skanstatic bool 3962169689Skangate_pre (void) 3963169689Skan{ 3964169689Skan return flag_tree_pre != 0; 3965169689Skan} 3966169689Skan 3967169689Skanstruct tree_opt_pass pass_pre = 3968169689Skan{ 3969169689Skan "pre", /* name */ 3970169689Skan gate_pre, /* gate */ 3971169689Skan do_pre, /* execute */ 3972169689Skan NULL, /* sub */ 3973169689Skan NULL, /* next */ 3974169689Skan 0, /* static_pass_number */ 3975169689Skan TV_TREE_PRE, /* tv_id */ 3976169689Skan PROP_no_crit_edges | PROP_cfg 3977169689Skan | PROP_ssa | PROP_alias, /* properties_required */ 3978169689Skan 0, /* properties_provided */ 3979169689Skan 0, /* properties_destroyed */ 3980169689Skan 0, /* todo_flags_start */ 3981169689Skan TODO_update_ssa_only_virtuals | TODO_dump_func | TODO_ggc_collect 3982169689Skan | TODO_verify_ssa, /* todo_flags_finish */ 3983169689Skan 0 /* letter */ 3984169689Skan}; 3985169689Skan 3986169689Skan 3987169689Skan/* Gate and execute functions for FRE. */ 3988169689Skan 3989169689Skanstatic unsigned int 3990169689Skanexecute_fre (void) 3991169689Skan{ 3992169689Skan execute_pre (true); 3993169689Skan return 0; 3994169689Skan} 3995169689Skan 3996169689Skanstatic bool 3997169689Skangate_fre (void) 3998169689Skan{ 3999169689Skan return flag_tree_fre != 0; 4000169689Skan} 4001169689Skan 4002169689Skanstruct tree_opt_pass pass_fre = 4003169689Skan{ 4004169689Skan "fre", /* name */ 4005169689Skan gate_fre, /* gate */ 4006169689Skan execute_fre, /* execute */ 4007169689Skan NULL, /* sub */ 4008169689Skan NULL, /* next */ 4009169689Skan 0, /* static_pass_number */ 4010169689Skan TV_TREE_FRE, /* tv_id */ 4011169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 4012169689Skan 0, /* properties_provided */ 4013169689Skan 0, /* properties_destroyed */ 4014169689Skan 0, /* todo_flags_start */ 4015169689Skan TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */ 4016169689Skan 0 /* letter */ 4017169689Skan}; 4018