1169689Skan/* SSA Dominator optimizations for trees 2169689Skan Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 3169689Skan Free Software Foundation, Inc. 4169689Skan Contributed by Diego Novillo <dnovillo@redhat.com> 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 "tree.h" 28169689Skan#include "flags.h" 29169689Skan#include "rtl.h" 30169689Skan#include "tm_p.h" 31169689Skan#include "ggc.h" 32169689Skan#include "basic-block.h" 33169689Skan#include "cfgloop.h" 34169689Skan#include "output.h" 35169689Skan#include "expr.h" 36169689Skan#include "function.h" 37169689Skan#include "diagnostic.h" 38169689Skan#include "timevar.h" 39169689Skan#include "tree-dump.h" 40169689Skan#include "tree-flow.h" 41169689Skan#include "domwalk.h" 42169689Skan#include "real.h" 43169689Skan#include "tree-pass.h" 44169689Skan#include "tree-ssa-propagate.h" 45169689Skan#include "langhooks.h" 46169689Skan#include "params.h" 47169689Skan 48169689Skan/* This file implements optimizations on the dominator tree. */ 49169689Skan 50169689Skan 51169689Skan/* Structure for recording edge equivalences as well as any pending 52169689Skan edge redirections during the dominator optimizer. 53169689Skan 54169689Skan Computing and storing the edge equivalences instead of creating 55169689Skan them on-demand can save significant amounts of time, particularly 56169689Skan for pathological cases involving switch statements. 57169689Skan 58169689Skan These structures live for a single iteration of the dominator 59169689Skan optimizer in the edge's AUX field. At the end of an iteration we 60169689Skan free each of these structures and update the AUX field to point 61169689Skan to any requested redirection target (the code for updating the 62169689Skan CFG and SSA graph for edge redirection expects redirection edge 63169689Skan targets to be in the AUX field for each edge. */ 64169689Skan 65169689Skanstruct edge_info 66169689Skan{ 67169689Skan /* If this edge creates a simple equivalence, the LHS and RHS of 68169689Skan the equivalence will be stored here. */ 69169689Skan tree lhs; 70169689Skan tree rhs; 71169689Skan 72169689Skan /* Traversing an edge may also indicate one or more particular conditions 73169689Skan are true or false. The number of recorded conditions can vary, but 74169689Skan can be determined by the condition's code. So we have an array 75169689Skan and its maximum index rather than use a varray. */ 76169689Skan tree *cond_equivalences; 77169689Skan unsigned int max_cond_equivalences; 78169689Skan}; 79169689Skan 80169689Skan 81169689Skan/* Hash table with expressions made available during the renaming process. 82169689Skan When an assignment of the form X_i = EXPR is found, the statement is 83169689Skan stored in this table. If the same expression EXPR is later found on the 84169689Skan RHS of another statement, it is replaced with X_i (thus performing 85169689Skan global redundancy elimination). Similarly as we pass through conditionals 86169689Skan we record the conditional itself as having either a true or false value 87169689Skan in this table. */ 88169689Skanstatic htab_t avail_exprs; 89169689Skan 90169689Skan/* Stack of available expressions in AVAIL_EXPRs. Each block pushes any 91169689Skan expressions it enters into the hash table along with a marker entry 92169689Skan (null). When we finish processing the block, we pop off entries and 93169689Skan remove the expressions from the global hash table until we hit the 94169689Skan marker. */ 95169689Skanstatic VEC(tree,heap) *avail_exprs_stack; 96169689Skan 97169689Skan/* Stack of statements we need to rescan during finalization for newly 98169689Skan exposed variables. 99169689Skan 100169689Skan Statement rescanning must occur after the current block's available 101169689Skan expressions are removed from AVAIL_EXPRS. Else we may change the 102169689Skan hash code for an expression and be unable to find/remove it from 103169689Skan AVAIL_EXPRS. */ 104169689Skanstatic VEC(tree,heap) *stmts_to_rescan; 105169689Skan 106169689Skan/* Structure for entries in the expression hash table. 107169689Skan 108169689Skan This requires more memory for the hash table entries, but allows us 109169689Skan to avoid creating silly tree nodes and annotations for conditionals, 110169689Skan eliminates 2 global hash tables and two block local varrays. 111169689Skan 112169689Skan It also allows us to reduce the number of hash table lookups we 113169689Skan have to perform in lookup_avail_expr and finally it allows us to 114169689Skan significantly reduce the number of calls into the hashing routine 115169689Skan itself. */ 116169689Skan 117169689Skanstruct expr_hash_elt 118169689Skan{ 119169689Skan /* The value (lhs) of this expression. */ 120169689Skan tree lhs; 121169689Skan 122169689Skan /* The expression (rhs) we want to record. */ 123169689Skan tree rhs; 124169689Skan 125169689Skan /* The stmt pointer if this element corresponds to a statement. */ 126169689Skan tree stmt; 127169689Skan 128169689Skan /* The hash value for RHS/ann. */ 129169689Skan hashval_t hash; 130169689Skan}; 131169689Skan 132169689Skan/* Stack of dest,src pairs that need to be restored during finalization. 133169689Skan 134169689Skan A NULL entry is used to mark the end of pairs which need to be 135169689Skan restored during finalization of this block. */ 136169689Skanstatic VEC(tree,heap) *const_and_copies_stack; 137169689Skan 138169689Skan/* Track whether or not we have changed the control flow graph. */ 139169689Skanstatic bool cfg_altered; 140169689Skan 141169689Skan/* Bitmap of blocks that have had EH statements cleaned. We should 142169689Skan remove their dead edges eventually. */ 143169689Skanstatic bitmap need_eh_cleanup; 144169689Skan 145169689Skan/* Statistics for dominator optimizations. */ 146169689Skanstruct opt_stats_d 147169689Skan{ 148169689Skan long num_stmts; 149169689Skan long num_exprs_considered; 150169689Skan long num_re; 151169689Skan long num_const_prop; 152169689Skan long num_copy_prop; 153169689Skan}; 154169689Skan 155169689Skanstatic struct opt_stats_d opt_stats; 156169689Skan 157169689Skanstruct eq_expr_value 158169689Skan{ 159169689Skan tree src; 160169689Skan tree dst; 161169689Skan}; 162169689Skan 163169689Skan/* Local functions. */ 164169689Skanstatic void optimize_stmt (struct dom_walk_data *, 165169689Skan basic_block bb, 166169689Skan block_stmt_iterator); 167169689Skanstatic tree lookup_avail_expr (tree, bool); 168169689Skanstatic hashval_t avail_expr_hash (const void *); 169169689Skanstatic hashval_t real_avail_expr_hash (const void *); 170169689Skanstatic int avail_expr_eq (const void *, const void *); 171169689Skanstatic void htab_statistics (FILE *, htab_t); 172169689Skanstatic void record_cond (tree, tree); 173169689Skanstatic void record_const_or_copy (tree, tree); 174169689Skanstatic void record_equality (tree, tree); 175169689Skanstatic void record_equivalences_from_phis (basic_block); 176169689Skanstatic void record_equivalences_from_incoming_edge (basic_block); 177169689Skanstatic bool eliminate_redundant_computations (tree); 178169689Skanstatic void record_equivalences_from_stmt (tree, int, stmt_ann_t); 179169689Skanstatic void dom_thread_across_edge (struct dom_walk_data *, edge); 180169689Skanstatic void dom_opt_finalize_block (struct dom_walk_data *, basic_block); 181169689Skanstatic void dom_opt_initialize_block (struct dom_walk_data *, basic_block); 182169689Skanstatic void propagate_to_outgoing_edges (struct dom_walk_data *, basic_block); 183169689Skanstatic void remove_local_expressions_from_table (void); 184169689Skanstatic void restore_vars_to_original_value (void); 185169689Skanstatic edge single_incoming_edge_ignoring_loop_edges (basic_block); 186169689Skan 187169689Skan 188169689Skan/* Allocate an EDGE_INFO for edge E and attach it to E. 189169689Skan Return the new EDGE_INFO structure. */ 190169689Skan 191169689Skanstatic struct edge_info * 192169689Skanallocate_edge_info (edge e) 193169689Skan{ 194169689Skan struct edge_info *edge_info; 195169689Skan 196169689Skan edge_info = XCNEW (struct edge_info); 197169689Skan 198169689Skan e->aux = edge_info; 199169689Skan return edge_info; 200169689Skan} 201169689Skan 202169689Skan/* Free all EDGE_INFO structures associated with edges in the CFG. 203169689Skan If a particular edge can be threaded, copy the redirection 204169689Skan target from the EDGE_INFO structure into the edge's AUX field 205169689Skan as required by code to update the CFG and SSA graph for 206169689Skan jump threading. */ 207169689Skan 208169689Skanstatic void 209169689Skanfree_all_edge_infos (void) 210169689Skan{ 211169689Skan basic_block bb; 212169689Skan edge_iterator ei; 213169689Skan edge e; 214169689Skan 215169689Skan FOR_EACH_BB (bb) 216169689Skan { 217169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 218169689Skan { 219169689Skan struct edge_info *edge_info = (struct edge_info *) e->aux; 220169689Skan 221169689Skan if (edge_info) 222169689Skan { 223169689Skan if (edge_info->cond_equivalences) 224169689Skan free (edge_info->cond_equivalences); 225169689Skan free (edge_info); 226169689Skan e->aux = NULL; 227169689Skan } 228169689Skan } 229169689Skan } 230169689Skan} 231169689Skan 232169689Skan/* Jump threading, redundancy elimination and const/copy propagation. 233169689Skan 234169689Skan This pass may expose new symbols that need to be renamed into SSA. For 235169689Skan every new symbol exposed, its corresponding bit will be set in 236169689Skan VARS_TO_RENAME. */ 237169689Skan 238169689Skanstatic unsigned int 239169689Skantree_ssa_dominator_optimize (void) 240169689Skan{ 241169689Skan struct dom_walk_data walk_data; 242169689Skan unsigned int i; 243169689Skan struct loops loops_info; 244169689Skan 245169689Skan memset (&opt_stats, 0, sizeof (opt_stats)); 246169689Skan 247169689Skan /* Create our hash tables. */ 248169689Skan avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free); 249169689Skan avail_exprs_stack = VEC_alloc (tree, heap, 20); 250169689Skan const_and_copies_stack = VEC_alloc (tree, heap, 20); 251169689Skan stmts_to_rescan = VEC_alloc (tree, heap, 20); 252169689Skan need_eh_cleanup = BITMAP_ALLOC (NULL); 253169689Skan 254169689Skan /* Setup callbacks for the generic dominator tree walker. */ 255169689Skan walk_data.walk_stmts_backward = false; 256169689Skan walk_data.dom_direction = CDI_DOMINATORS; 257169689Skan walk_data.initialize_block_local_data = NULL; 258169689Skan walk_data.before_dom_children_before_stmts = dom_opt_initialize_block; 259169689Skan walk_data.before_dom_children_walk_stmts = optimize_stmt; 260169689Skan walk_data.before_dom_children_after_stmts = propagate_to_outgoing_edges; 261169689Skan walk_data.after_dom_children_before_stmts = NULL; 262169689Skan walk_data.after_dom_children_walk_stmts = NULL; 263169689Skan walk_data.after_dom_children_after_stmts = dom_opt_finalize_block; 264169689Skan /* Right now we only attach a dummy COND_EXPR to the global data pointer. 265169689Skan When we attach more stuff we'll need to fill this out with a real 266169689Skan structure. */ 267169689Skan walk_data.global_data = NULL; 268169689Skan walk_data.block_local_data_size = 0; 269169689Skan walk_data.interesting_blocks = NULL; 270169689Skan 271169689Skan /* Now initialize the dominator walker. */ 272169689Skan init_walk_dominator_tree (&walk_data); 273169689Skan 274169689Skan calculate_dominance_info (CDI_DOMINATORS); 275169689Skan 276169689Skan /* We need to know which edges exit loops so that we can 277169689Skan aggressively thread through loop headers to an exit 278169689Skan edge. */ 279169689Skan flow_loops_find (&loops_info); 280169689Skan mark_loop_exit_edges (&loops_info); 281169689Skan flow_loops_free (&loops_info); 282169689Skan 283169689Skan /* Clean up the CFG so that any forwarder blocks created by loop 284169689Skan canonicalization are removed. */ 285169689Skan cleanup_tree_cfg (); 286169689Skan calculate_dominance_info (CDI_DOMINATORS); 287169689Skan 288169689Skan /* We need accurate information regarding back edges in the CFG 289169689Skan for jump threading. */ 290169689Skan mark_dfs_back_edges (); 291169689Skan 292169689Skan /* Recursively walk the dominator tree optimizing statements. */ 293169689Skan walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); 294169689Skan 295169689Skan { 296169689Skan block_stmt_iterator bsi; 297169689Skan basic_block bb; 298169689Skan FOR_EACH_BB (bb) 299169689Skan { 300169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 301169689Skan update_stmt_if_modified (bsi_stmt (bsi)); 302169689Skan } 303169689Skan } 304169689Skan 305169689Skan /* If we exposed any new variables, go ahead and put them into 306169689Skan SSA form now, before we handle jump threading. This simplifies 307169689Skan interactions between rewriting of _DECL nodes into SSA form 308169689Skan and rewriting SSA_NAME nodes into SSA form after block 309169689Skan duplication and CFG manipulation. */ 310169689Skan update_ssa (TODO_update_ssa); 311169689Skan 312169689Skan free_all_edge_infos (); 313169689Skan 314169689Skan /* Thread jumps, creating duplicate blocks as needed. */ 315169689Skan cfg_altered |= thread_through_all_blocks (); 316169689Skan 317169689Skan /* Removal of statements may make some EH edges dead. Purge 318169689Skan such edges from the CFG as needed. */ 319169689Skan if (!bitmap_empty_p (need_eh_cleanup)) 320169689Skan { 321169689Skan cfg_altered |= tree_purge_all_dead_eh_edges (need_eh_cleanup); 322169689Skan bitmap_zero (need_eh_cleanup); 323169689Skan } 324169689Skan 325169689Skan if (cfg_altered) 326169689Skan free_dominance_info (CDI_DOMINATORS); 327169689Skan 328169689Skan /* Finally, remove everything except invariants in SSA_NAME_VALUE. 329169689Skan 330169689Skan Long term we will be able to let everything in SSA_NAME_VALUE 331169689Skan persist. However, for now, we know this is the safe thing to do. */ 332169689Skan for (i = 0; i < num_ssa_names; i++) 333169689Skan { 334169689Skan tree name = ssa_name (i); 335169689Skan tree value; 336169689Skan 337169689Skan if (!name) 338169689Skan continue; 339169689Skan 340169689Skan value = SSA_NAME_VALUE (name); 341169689Skan if (value && !is_gimple_min_invariant (value)) 342169689Skan SSA_NAME_VALUE (name) = NULL; 343169689Skan } 344169689Skan 345169689Skan /* Debugging dumps. */ 346169689Skan if (dump_file && (dump_flags & TDF_STATS)) 347169689Skan dump_dominator_optimization_stats (dump_file); 348169689Skan 349169689Skan /* Delete our main hashtable. */ 350169689Skan htab_delete (avail_exprs); 351169689Skan 352169689Skan /* And finalize the dominator walker. */ 353169689Skan fini_walk_dominator_tree (&walk_data); 354169689Skan 355169689Skan /* Free asserted bitmaps and stacks. */ 356169689Skan BITMAP_FREE (need_eh_cleanup); 357169689Skan 358169689Skan VEC_free (tree, heap, avail_exprs_stack); 359169689Skan VEC_free (tree, heap, const_and_copies_stack); 360169689Skan VEC_free (tree, heap, stmts_to_rescan); 361169689Skan return 0; 362169689Skan} 363169689Skan 364169689Skanstatic bool 365169689Skangate_dominator (void) 366169689Skan{ 367169689Skan return flag_tree_dom != 0; 368169689Skan} 369169689Skan 370169689Skanstruct tree_opt_pass pass_dominator = 371169689Skan{ 372169689Skan "dom", /* name */ 373169689Skan gate_dominator, /* gate */ 374169689Skan tree_ssa_dominator_optimize, /* execute */ 375169689Skan NULL, /* sub */ 376169689Skan NULL, /* next */ 377169689Skan 0, /* static_pass_number */ 378169689Skan TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */ 379169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 380169689Skan 0, /* properties_provided */ 381169689Skan PROP_smt_usage, /* properties_destroyed */ 382169689Skan 0, /* todo_flags_start */ 383169689Skan TODO_dump_func 384169689Skan | TODO_update_ssa 385169689Skan | TODO_cleanup_cfg 386169689Skan | TODO_verify_ssa 387169689Skan | TODO_update_smt_usage, /* todo_flags_finish */ 388169689Skan 0 /* letter */ 389169689Skan}; 390169689Skan 391169689Skan 392169689Skan/* Given a stmt CONDSTMT containing a COND_EXPR, canonicalize the 393169689Skan COND_EXPR into a canonical form. */ 394169689Skan 395169689Skanstatic void 396169689Skancanonicalize_comparison (tree condstmt) 397169689Skan{ 398169689Skan tree cond = COND_EXPR_COND (condstmt); 399169689Skan tree op0; 400169689Skan tree op1; 401169689Skan enum tree_code code = TREE_CODE (cond); 402169689Skan 403169689Skan if (!COMPARISON_CLASS_P (cond)) 404169689Skan return; 405169689Skan 406169689Skan op0 = TREE_OPERAND (cond, 0); 407169689Skan op1 = TREE_OPERAND (cond, 1); 408169689Skan 409169689Skan /* If it would be profitable to swap the operands, then do so to 410169689Skan canonicalize the statement, enabling better optimization. 411169689Skan 412169689Skan By placing canonicalization of such expressions here we 413169689Skan transparently keep statements in canonical form, even 414169689Skan when the statement is modified. */ 415169689Skan if (tree_swap_operands_p (op0, op1, false)) 416169689Skan { 417169689Skan /* For relationals we need to swap the operands 418169689Skan and change the code. */ 419169689Skan if (code == LT_EXPR 420169689Skan || code == GT_EXPR 421169689Skan || code == LE_EXPR 422169689Skan || code == GE_EXPR) 423169689Skan { 424169689Skan TREE_SET_CODE (cond, swap_tree_comparison (code)); 425169689Skan swap_tree_operands (condstmt, 426169689Skan &TREE_OPERAND (cond, 0), 427169689Skan &TREE_OPERAND (cond, 1)); 428169689Skan /* If one operand was in the operand cache, but the other is 429169689Skan not, because it is a constant, this is a case that the 430169689Skan internal updating code of swap_tree_operands can't handle 431169689Skan properly. */ 432169689Skan if (TREE_CODE_CLASS (TREE_CODE (op0)) 433169689Skan != TREE_CODE_CLASS (TREE_CODE (op1))) 434169689Skan update_stmt (condstmt); 435169689Skan } 436169689Skan } 437169689Skan} 438169689Skan 439169689Skan/* Initialize local stacks for this optimizer and record equivalences 440169689Skan upon entry to BB. Equivalences can come from the edge traversed to 441169689Skan reach BB or they may come from PHI nodes at the start of BB. */ 442169689Skan 443169689Skanstatic void 444169689Skandom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 445169689Skan basic_block bb) 446169689Skan{ 447169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 448169689Skan fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index); 449169689Skan 450169689Skan /* Push a marker on the stacks of local information so that we know how 451169689Skan far to unwind when we finalize this block. */ 452169689Skan VEC_safe_push (tree, heap, avail_exprs_stack, NULL_TREE); 453169689Skan VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); 454169689Skan 455169689Skan record_equivalences_from_incoming_edge (bb); 456169689Skan 457169689Skan /* PHI nodes can create equivalences too. */ 458169689Skan record_equivalences_from_phis (bb); 459169689Skan} 460169689Skan 461169689Skan/* Given an expression EXPR (a relational expression or a statement), 462169689Skan initialize the hash table element pointed to by ELEMENT. */ 463169689Skan 464169689Skanstatic void 465169689Skaninitialize_hash_element (tree expr, tree lhs, struct expr_hash_elt *element) 466169689Skan{ 467169689Skan /* Hash table elements may be based on conditional expressions or statements. 468169689Skan 469169689Skan For the former case, we have no annotation and we want to hash the 470169689Skan conditional expression. In the latter case we have an annotation and 471169689Skan we want to record the expression the statement evaluates. */ 472169689Skan if (COMPARISON_CLASS_P (expr) || TREE_CODE (expr) == TRUTH_NOT_EXPR) 473169689Skan { 474169689Skan element->stmt = NULL; 475169689Skan element->rhs = expr; 476169689Skan } 477169689Skan else if (TREE_CODE (expr) == COND_EXPR) 478169689Skan { 479169689Skan element->stmt = expr; 480169689Skan element->rhs = COND_EXPR_COND (expr); 481169689Skan } 482169689Skan else if (TREE_CODE (expr) == SWITCH_EXPR) 483169689Skan { 484169689Skan element->stmt = expr; 485169689Skan element->rhs = SWITCH_COND (expr); 486169689Skan } 487169689Skan else if (TREE_CODE (expr) == RETURN_EXPR && TREE_OPERAND (expr, 0)) 488169689Skan { 489169689Skan element->stmt = expr; 490169689Skan element->rhs = TREE_OPERAND (TREE_OPERAND (expr, 0), 1); 491169689Skan } 492169689Skan else if (TREE_CODE (expr) == GOTO_EXPR) 493169689Skan { 494169689Skan element->stmt = expr; 495169689Skan element->rhs = GOTO_DESTINATION (expr); 496169689Skan } 497169689Skan else 498169689Skan { 499169689Skan element->stmt = expr; 500169689Skan element->rhs = TREE_OPERAND (expr, 1); 501169689Skan } 502169689Skan 503169689Skan element->lhs = lhs; 504169689Skan element->hash = avail_expr_hash (element); 505169689Skan} 506169689Skan 507169689Skan/* Remove all the expressions in LOCALS from TABLE, stopping when there are 508169689Skan LIMIT entries left in LOCALs. */ 509169689Skan 510169689Skanstatic void 511169689Skanremove_local_expressions_from_table (void) 512169689Skan{ 513169689Skan /* Remove all the expressions made available in this block. */ 514169689Skan while (VEC_length (tree, avail_exprs_stack) > 0) 515169689Skan { 516169689Skan struct expr_hash_elt element; 517169689Skan tree expr = VEC_pop (tree, avail_exprs_stack); 518169689Skan 519169689Skan if (expr == NULL_TREE) 520169689Skan break; 521169689Skan 522169689Skan initialize_hash_element (expr, NULL, &element); 523169689Skan htab_remove_elt_with_hash (avail_exprs, &element, element.hash); 524169689Skan } 525169689Skan} 526169689Skan 527169689Skan/* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore 528169689Skan CONST_AND_COPIES to its original state, stopping when we hit a 529169689Skan NULL marker. */ 530169689Skan 531169689Skanstatic void 532169689Skanrestore_vars_to_original_value (void) 533169689Skan{ 534169689Skan while (VEC_length (tree, const_and_copies_stack) > 0) 535169689Skan { 536169689Skan tree prev_value, dest; 537169689Skan 538169689Skan dest = VEC_pop (tree, const_and_copies_stack); 539169689Skan 540169689Skan if (dest == NULL) 541169689Skan break; 542169689Skan 543169689Skan prev_value = VEC_pop (tree, const_and_copies_stack); 544169689Skan SSA_NAME_VALUE (dest) = prev_value; 545169689Skan } 546169689Skan} 547169689Skan 548169689Skan/* A trivial wrapper so that we can present the generic jump 549169689Skan threading code with a simple API for simplifying statements. */ 550169689Skanstatic tree 551169689Skansimplify_stmt_for_jump_threading (tree stmt, tree within_stmt ATTRIBUTE_UNUSED) 552169689Skan{ 553169689Skan return lookup_avail_expr (stmt, false); 554169689Skan} 555169689Skan 556169689Skan/* Wrapper for common code to attempt to thread an edge. For example, 557169689Skan it handles lazily building the dummy condition and the bookkeeping 558169689Skan when jump threading is successful. */ 559169689Skan 560169689Skanstatic void 561169689Skandom_thread_across_edge (struct dom_walk_data *walk_data, edge e) 562169689Skan{ 563169689Skan /* If we don't already have a dummy condition, build it now. */ 564169689Skan if (! walk_data->global_data) 565169689Skan { 566169689Skan tree dummy_cond = build2 (NE_EXPR, boolean_type_node, 567169689Skan integer_zero_node, integer_zero_node); 568169689Skan dummy_cond = build3 (COND_EXPR, void_type_node, dummy_cond, NULL, NULL); 569169689Skan walk_data->global_data = dummy_cond; 570169689Skan } 571169689Skan 572169689Skan thread_across_edge (walk_data->global_data, e, false, 573169689Skan &const_and_copies_stack, 574169689Skan simplify_stmt_for_jump_threading); 575169689Skan} 576169689Skan 577169689Skan/* We have finished processing the dominator children of BB, perform 578169689Skan any finalization actions in preparation for leaving this node in 579169689Skan the dominator tree. */ 580169689Skan 581169689Skanstatic void 582169689Skandom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb) 583169689Skan{ 584169689Skan tree last; 585169689Skan 586169689Skan 587169689Skan /* If we have an outgoing edge to a block with multiple incoming and 588169689Skan outgoing edges, then we may be able to thread the edge. ie, we 589169689Skan may be able to statically determine which of the outgoing edges 590169689Skan will be traversed when the incoming edge from BB is traversed. */ 591169689Skan if (single_succ_p (bb) 592169689Skan && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0 593169689Skan && potentially_threadable_block (single_succ (bb))) 594169689Skan { 595169689Skan dom_thread_across_edge (walk_data, single_succ_edge (bb)); 596169689Skan } 597169689Skan else if ((last = last_stmt (bb)) 598169689Skan && TREE_CODE (last) == COND_EXPR 599169689Skan && (COMPARISON_CLASS_P (COND_EXPR_COND (last)) 600169689Skan || TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME) 601169689Skan && EDGE_COUNT (bb->succs) == 2 602169689Skan && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0 603169689Skan && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0) 604169689Skan { 605169689Skan edge true_edge, false_edge; 606169689Skan 607169689Skan extract_true_false_edges_from_block (bb, &true_edge, &false_edge); 608169689Skan 609169689Skan /* Only try to thread the edge if it reaches a target block with 610169689Skan more than one predecessor and more than one successor. */ 611169689Skan if (potentially_threadable_block (true_edge->dest)) 612169689Skan { 613169689Skan struct edge_info *edge_info; 614169689Skan unsigned int i; 615169689Skan 616169689Skan /* Push a marker onto the available expression stack so that we 617169689Skan unwind any expressions related to the TRUE arm before processing 618169689Skan the false arm below. */ 619169689Skan VEC_safe_push (tree, heap, avail_exprs_stack, NULL_TREE); 620169689Skan VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); 621169689Skan 622169689Skan edge_info = (struct edge_info *) true_edge->aux; 623169689Skan 624169689Skan /* If we have info associated with this edge, record it into 625169689Skan our equivalency tables. */ 626169689Skan if (edge_info) 627169689Skan { 628169689Skan tree *cond_equivalences = edge_info->cond_equivalences; 629169689Skan tree lhs = edge_info->lhs; 630169689Skan tree rhs = edge_info->rhs; 631169689Skan 632169689Skan /* If we have a simple NAME = VALUE equivalency record it. */ 633169689Skan if (lhs && TREE_CODE (lhs) == SSA_NAME) 634169689Skan record_const_or_copy (lhs, rhs); 635169689Skan 636169689Skan /* If we have 0 = COND or 1 = COND equivalences, record them 637169689Skan into our expression hash tables. */ 638169689Skan if (cond_equivalences) 639169689Skan for (i = 0; i < edge_info->max_cond_equivalences; i += 2) 640169689Skan { 641169689Skan tree expr = cond_equivalences[i]; 642169689Skan tree value = cond_equivalences[i + 1]; 643169689Skan 644169689Skan record_cond (expr, value); 645169689Skan } 646169689Skan } 647169689Skan 648169689Skan dom_thread_across_edge (walk_data, true_edge); 649169689Skan 650169689Skan /* And restore the various tables to their state before 651169689Skan we threaded this edge. */ 652169689Skan remove_local_expressions_from_table (); 653169689Skan } 654169689Skan 655169689Skan /* Similarly for the ELSE arm. */ 656169689Skan if (potentially_threadable_block (false_edge->dest)) 657169689Skan { 658169689Skan struct edge_info *edge_info; 659169689Skan unsigned int i; 660169689Skan 661169689Skan VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); 662169689Skan edge_info = (struct edge_info *) false_edge->aux; 663169689Skan 664169689Skan /* If we have info associated with this edge, record it into 665169689Skan our equivalency tables. */ 666169689Skan if (edge_info) 667169689Skan { 668169689Skan tree *cond_equivalences = edge_info->cond_equivalences; 669169689Skan tree lhs = edge_info->lhs; 670169689Skan tree rhs = edge_info->rhs; 671169689Skan 672169689Skan /* If we have a simple NAME = VALUE equivalency record it. */ 673169689Skan if (lhs && TREE_CODE (lhs) == SSA_NAME) 674169689Skan record_const_or_copy (lhs, rhs); 675169689Skan 676169689Skan /* If we have 0 = COND or 1 = COND equivalences, record them 677169689Skan into our expression hash tables. */ 678169689Skan if (cond_equivalences) 679169689Skan for (i = 0; i < edge_info->max_cond_equivalences; i += 2) 680169689Skan { 681169689Skan tree expr = cond_equivalences[i]; 682169689Skan tree value = cond_equivalences[i + 1]; 683169689Skan 684169689Skan record_cond (expr, value); 685169689Skan } 686169689Skan } 687169689Skan 688169689Skan /* Now thread the edge. */ 689169689Skan dom_thread_across_edge (walk_data, false_edge); 690169689Skan 691169689Skan /* No need to remove local expressions from our tables 692169689Skan or restore vars to their original value as that will 693169689Skan be done immediately below. */ 694169689Skan } 695169689Skan } 696169689Skan 697169689Skan remove_local_expressions_from_table (); 698169689Skan restore_vars_to_original_value (); 699169689Skan 700169689Skan /* If we queued any statements to rescan in this block, then 701169689Skan go ahead and rescan them now. */ 702169689Skan while (VEC_length (tree, stmts_to_rescan) > 0) 703169689Skan { 704169689Skan tree stmt = VEC_last (tree, stmts_to_rescan); 705169689Skan basic_block stmt_bb = bb_for_stmt (stmt); 706169689Skan 707169689Skan if (stmt_bb != bb) 708169689Skan break; 709169689Skan 710169689Skan VEC_pop (tree, stmts_to_rescan); 711169689Skan mark_new_vars_to_rename (stmt); 712169689Skan } 713169689Skan} 714169689Skan 715169689Skan/* PHI nodes can create equivalences too. 716169689Skan 717169689Skan Ignoring any alternatives which are the same as the result, if 718169689Skan all the alternatives are equal, then the PHI node creates an 719169689Skan equivalence. */ 720169689Skan 721169689Skanstatic void 722169689Skanrecord_equivalences_from_phis (basic_block bb) 723169689Skan{ 724169689Skan tree phi; 725169689Skan 726169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 727169689Skan { 728169689Skan tree lhs = PHI_RESULT (phi); 729169689Skan tree rhs = NULL; 730169689Skan int i; 731169689Skan 732169689Skan for (i = 0; i < PHI_NUM_ARGS (phi); i++) 733169689Skan { 734169689Skan tree t = PHI_ARG_DEF (phi, i); 735169689Skan 736169689Skan /* Ignore alternatives which are the same as our LHS. Since 737169689Skan LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we 738169689Skan can simply compare pointers. */ 739169689Skan if (lhs == t) 740169689Skan continue; 741169689Skan 742169689Skan /* If we have not processed an alternative yet, then set 743169689Skan RHS to this alternative. */ 744169689Skan if (rhs == NULL) 745169689Skan rhs = t; 746169689Skan /* If we have processed an alternative (stored in RHS), then 747169689Skan see if it is equal to this one. If it isn't, then stop 748169689Skan the search. */ 749169689Skan else if (! operand_equal_for_phi_arg_p (rhs, t)) 750169689Skan break; 751169689Skan } 752169689Skan 753169689Skan /* If we had no interesting alternatives, then all the RHS alternatives 754169689Skan must have been the same as LHS. */ 755169689Skan if (!rhs) 756169689Skan rhs = lhs; 757169689Skan 758169689Skan /* If we managed to iterate through each PHI alternative without 759169689Skan breaking out of the loop, then we have a PHI which may create 760169689Skan a useful equivalence. We do not need to record unwind data for 761169689Skan this, since this is a true assignment and not an equivalence 762169689Skan inferred from a comparison. All uses of this ssa name are dominated 763169689Skan by this assignment, so unwinding just costs time and space. */ 764169689Skan if (i == PHI_NUM_ARGS (phi) 765169689Skan && may_propagate_copy (lhs, rhs)) 766169689Skan SSA_NAME_VALUE (lhs) = rhs; 767169689Skan } 768169689Skan} 769169689Skan 770169689Skan/* Ignoring loop backedges, if BB has precisely one incoming edge then 771169689Skan return that edge. Otherwise return NULL. */ 772169689Skanstatic edge 773169689Skansingle_incoming_edge_ignoring_loop_edges (basic_block bb) 774169689Skan{ 775169689Skan edge retval = NULL; 776169689Skan edge e; 777169689Skan edge_iterator ei; 778169689Skan 779169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 780169689Skan { 781169689Skan /* A loop back edge can be identified by the destination of 782169689Skan the edge dominating the source of the edge. */ 783169689Skan if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest)) 784169689Skan continue; 785169689Skan 786169689Skan /* If we have already seen a non-loop edge, then we must have 787169689Skan multiple incoming non-loop edges and thus we return NULL. */ 788169689Skan if (retval) 789169689Skan return NULL; 790169689Skan 791169689Skan /* This is the first non-loop incoming edge we have found. Record 792169689Skan it. */ 793169689Skan retval = e; 794169689Skan } 795169689Skan 796169689Skan return retval; 797169689Skan} 798169689Skan 799169689Skan/* Record any equivalences created by the incoming edge to BB. If BB 800169689Skan has more than one incoming edge, then no equivalence is created. */ 801169689Skan 802169689Skanstatic void 803169689Skanrecord_equivalences_from_incoming_edge (basic_block bb) 804169689Skan{ 805169689Skan edge e; 806169689Skan basic_block parent; 807169689Skan struct edge_info *edge_info; 808169689Skan 809169689Skan /* If our parent block ended with a control statement, then we may be 810169689Skan able to record some equivalences based on which outgoing edge from 811169689Skan the parent was followed. */ 812169689Skan parent = get_immediate_dominator (CDI_DOMINATORS, bb); 813169689Skan 814169689Skan e = single_incoming_edge_ignoring_loop_edges (bb); 815169689Skan 816169689Skan /* If we had a single incoming edge from our parent block, then enter 817169689Skan any data associated with the edge into our tables. */ 818169689Skan if (e && e->src == parent) 819169689Skan { 820169689Skan unsigned int i; 821169689Skan 822169689Skan edge_info = (struct edge_info *) e->aux; 823169689Skan 824169689Skan if (edge_info) 825169689Skan { 826169689Skan tree lhs = edge_info->lhs; 827169689Skan tree rhs = edge_info->rhs; 828169689Skan tree *cond_equivalences = edge_info->cond_equivalences; 829169689Skan 830169689Skan if (lhs) 831169689Skan record_equality (lhs, rhs); 832169689Skan 833169689Skan if (cond_equivalences) 834169689Skan { 835169689Skan for (i = 0; i < edge_info->max_cond_equivalences; i += 2) 836169689Skan { 837169689Skan tree expr = cond_equivalences[i]; 838169689Skan tree value = cond_equivalences[i + 1]; 839169689Skan 840169689Skan record_cond (expr, value); 841169689Skan } 842169689Skan } 843169689Skan } 844169689Skan } 845169689Skan} 846169689Skan 847169689Skan/* Dump SSA statistics on FILE. */ 848169689Skan 849169689Skanvoid 850169689Skandump_dominator_optimization_stats (FILE *file) 851169689Skan{ 852169689Skan long n_exprs; 853169689Skan 854169689Skan fprintf (file, "Total number of statements: %6ld\n\n", 855169689Skan opt_stats.num_stmts); 856169689Skan fprintf (file, "Exprs considered for dominator optimizations: %6ld\n", 857169689Skan opt_stats.num_exprs_considered); 858169689Skan 859169689Skan n_exprs = opt_stats.num_exprs_considered; 860169689Skan if (n_exprs == 0) 861169689Skan n_exprs = 1; 862169689Skan 863169689Skan fprintf (file, " Redundant expressions eliminated: %6ld (%.0f%%)\n", 864169689Skan opt_stats.num_re, PERCENT (opt_stats.num_re, 865169689Skan n_exprs)); 866169689Skan fprintf (file, " Constants propagated: %6ld\n", 867169689Skan opt_stats.num_const_prop); 868169689Skan fprintf (file, " Copies propagated: %6ld\n", 869169689Skan opt_stats.num_copy_prop); 870169689Skan 871169689Skan fprintf (file, "\nHash table statistics:\n"); 872169689Skan 873169689Skan fprintf (file, " avail_exprs: "); 874169689Skan htab_statistics (file, avail_exprs); 875169689Skan} 876169689Skan 877169689Skan 878169689Skan/* Dump SSA statistics on stderr. */ 879169689Skan 880169689Skanvoid 881169689Skandebug_dominator_optimization_stats (void) 882169689Skan{ 883169689Skan dump_dominator_optimization_stats (stderr); 884169689Skan} 885169689Skan 886169689Skan 887169689Skan/* Dump statistics for the hash table HTAB. */ 888169689Skan 889169689Skanstatic void 890169689Skanhtab_statistics (FILE *file, htab_t htab) 891169689Skan{ 892169689Skan fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n", 893169689Skan (long) htab_size (htab), 894169689Skan (long) htab_elements (htab), 895169689Skan htab_collisions (htab)); 896169689Skan} 897169689Skan 898169689Skan/* Enter a statement into the true/false expression hash table indicating 899169689Skan that the condition COND has the value VALUE. */ 900169689Skan 901169689Skanstatic void 902169689Skanrecord_cond (tree cond, tree value) 903169689Skan{ 904169689Skan struct expr_hash_elt *element = XCNEW (struct expr_hash_elt); 905169689Skan void **slot; 906169689Skan 907169689Skan initialize_hash_element (cond, value, element); 908169689Skan 909169689Skan slot = htab_find_slot_with_hash (avail_exprs, (void *)element, 910169689Skan element->hash, INSERT); 911169689Skan if (*slot == NULL) 912169689Skan { 913169689Skan *slot = (void *) element; 914169689Skan VEC_safe_push (tree, heap, avail_exprs_stack, cond); 915169689Skan } 916169689Skan else 917169689Skan free (element); 918169689Skan} 919169689Skan 920169689Skan/* Build a new conditional using NEW_CODE, OP0 and OP1 and store 921169689Skan the new conditional into *p, then store a boolean_true_node 922169689Skan into *(p + 1). */ 923169689Skan 924169689Skanstatic void 925169689Skanbuild_and_record_new_cond (enum tree_code new_code, tree op0, tree op1, tree *p) 926169689Skan{ 927169689Skan *p = build2 (new_code, boolean_type_node, op0, op1); 928169689Skan p++; 929169689Skan *p = boolean_true_node; 930169689Skan} 931169689Skan 932169689Skan/* Record that COND is true and INVERTED is false into the edge information 933169689Skan structure. Also record that any conditions dominated by COND are true 934169689Skan as well. 935169689Skan 936169689Skan For example, if a < b is true, then a <= b must also be true. */ 937169689Skan 938169689Skanstatic void 939169689Skanrecord_conditions (struct edge_info *edge_info, tree cond, tree inverted) 940169689Skan{ 941169689Skan tree op0, op1; 942169689Skan 943169689Skan if (!COMPARISON_CLASS_P (cond)) 944169689Skan return; 945169689Skan 946169689Skan op0 = TREE_OPERAND (cond, 0); 947169689Skan op1 = TREE_OPERAND (cond, 1); 948169689Skan 949169689Skan switch (TREE_CODE (cond)) 950169689Skan { 951169689Skan case LT_EXPR: 952169689Skan case GT_EXPR: 953169689Skan if (FLOAT_TYPE_P (TREE_TYPE (op0))) 954169689Skan { 955169689Skan edge_info->max_cond_equivalences = 12; 956169689Skan edge_info->cond_equivalences = XNEWVEC (tree, 12); 957169689Skan build_and_record_new_cond (ORDERED_EXPR, op0, op1, 958169689Skan &edge_info->cond_equivalences[8]); 959169689Skan build_and_record_new_cond (LTGT_EXPR, op0, op1, 960169689Skan &edge_info->cond_equivalences[10]); 961169689Skan } 962169689Skan else 963169689Skan { 964169689Skan edge_info->max_cond_equivalences = 8; 965169689Skan edge_info->cond_equivalences = XNEWVEC (tree, 8); 966169689Skan } 967169689Skan 968169689Skan build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR 969169689Skan ? LE_EXPR : GE_EXPR), 970169689Skan op0, op1, &edge_info->cond_equivalences[4]); 971169689Skan build_and_record_new_cond (NE_EXPR, op0, op1, 972169689Skan &edge_info->cond_equivalences[6]); 973169689Skan break; 974169689Skan 975169689Skan case GE_EXPR: 976169689Skan case LE_EXPR: 977169689Skan if (FLOAT_TYPE_P (TREE_TYPE (op0))) 978169689Skan { 979169689Skan edge_info->max_cond_equivalences = 6; 980169689Skan edge_info->cond_equivalences = XNEWVEC (tree, 6); 981169689Skan build_and_record_new_cond (ORDERED_EXPR, op0, op1, 982169689Skan &edge_info->cond_equivalences[4]); 983169689Skan } 984169689Skan else 985169689Skan { 986169689Skan edge_info->max_cond_equivalences = 4; 987169689Skan edge_info->cond_equivalences = XNEWVEC (tree, 4); 988169689Skan } 989169689Skan break; 990169689Skan 991169689Skan case EQ_EXPR: 992169689Skan if (FLOAT_TYPE_P (TREE_TYPE (op0))) 993169689Skan { 994169689Skan edge_info->max_cond_equivalences = 10; 995169689Skan edge_info->cond_equivalences = XNEWVEC (tree, 10); 996169689Skan build_and_record_new_cond (ORDERED_EXPR, op0, op1, 997169689Skan &edge_info->cond_equivalences[8]); 998169689Skan } 999169689Skan else 1000169689Skan { 1001169689Skan edge_info->max_cond_equivalences = 8; 1002169689Skan edge_info->cond_equivalences = XNEWVEC (tree, 8); 1003169689Skan } 1004169689Skan build_and_record_new_cond (LE_EXPR, op0, op1, 1005169689Skan &edge_info->cond_equivalences[4]); 1006169689Skan build_and_record_new_cond (GE_EXPR, op0, op1, 1007169689Skan &edge_info->cond_equivalences[6]); 1008169689Skan break; 1009169689Skan 1010169689Skan case UNORDERED_EXPR: 1011169689Skan edge_info->max_cond_equivalences = 16; 1012169689Skan edge_info->cond_equivalences = XNEWVEC (tree, 16); 1013169689Skan build_and_record_new_cond (NE_EXPR, op0, op1, 1014169689Skan &edge_info->cond_equivalences[4]); 1015169689Skan build_and_record_new_cond (UNLE_EXPR, op0, op1, 1016169689Skan &edge_info->cond_equivalences[6]); 1017169689Skan build_and_record_new_cond (UNGE_EXPR, op0, op1, 1018169689Skan &edge_info->cond_equivalences[8]); 1019169689Skan build_and_record_new_cond (UNEQ_EXPR, op0, op1, 1020169689Skan &edge_info->cond_equivalences[10]); 1021169689Skan build_and_record_new_cond (UNLT_EXPR, op0, op1, 1022169689Skan &edge_info->cond_equivalences[12]); 1023169689Skan build_and_record_new_cond (UNGT_EXPR, op0, op1, 1024169689Skan &edge_info->cond_equivalences[14]); 1025169689Skan break; 1026169689Skan 1027169689Skan case UNLT_EXPR: 1028169689Skan case UNGT_EXPR: 1029169689Skan edge_info->max_cond_equivalences = 8; 1030169689Skan edge_info->cond_equivalences = XNEWVEC (tree, 8); 1031169689Skan build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR 1032169689Skan ? UNLE_EXPR : UNGE_EXPR), 1033169689Skan op0, op1, &edge_info->cond_equivalences[4]); 1034169689Skan build_and_record_new_cond (NE_EXPR, op0, op1, 1035169689Skan &edge_info->cond_equivalences[6]); 1036169689Skan break; 1037169689Skan 1038169689Skan case UNEQ_EXPR: 1039169689Skan edge_info->max_cond_equivalences = 8; 1040169689Skan edge_info->cond_equivalences = XNEWVEC (tree, 8); 1041169689Skan build_and_record_new_cond (UNLE_EXPR, op0, op1, 1042169689Skan &edge_info->cond_equivalences[4]); 1043169689Skan build_and_record_new_cond (UNGE_EXPR, op0, op1, 1044169689Skan &edge_info->cond_equivalences[6]); 1045169689Skan break; 1046169689Skan 1047169689Skan case LTGT_EXPR: 1048169689Skan edge_info->max_cond_equivalences = 8; 1049169689Skan edge_info->cond_equivalences = XNEWVEC (tree, 8); 1050169689Skan build_and_record_new_cond (NE_EXPR, op0, op1, 1051169689Skan &edge_info->cond_equivalences[4]); 1052169689Skan build_and_record_new_cond (ORDERED_EXPR, op0, op1, 1053169689Skan &edge_info->cond_equivalences[6]); 1054169689Skan break; 1055169689Skan 1056169689Skan default: 1057169689Skan edge_info->max_cond_equivalences = 4; 1058169689Skan edge_info->cond_equivalences = XNEWVEC (tree, 4); 1059169689Skan break; 1060169689Skan } 1061169689Skan 1062169689Skan /* Now store the original true and false conditions into the first 1063169689Skan two slots. */ 1064169689Skan edge_info->cond_equivalences[0] = cond; 1065169689Skan edge_info->cond_equivalences[1] = boolean_true_node; 1066169689Skan edge_info->cond_equivalences[2] = inverted; 1067169689Skan edge_info->cond_equivalences[3] = boolean_false_node; 1068169689Skan} 1069169689Skan 1070169689Skan/* A helper function for record_const_or_copy and record_equality. 1071169689Skan Do the work of recording the value and undo info. */ 1072169689Skan 1073169689Skanstatic void 1074169689Skanrecord_const_or_copy_1 (tree x, tree y, tree prev_x) 1075169689Skan{ 1076169689Skan SSA_NAME_VALUE (x) = y; 1077169689Skan 1078169689Skan VEC_reserve (tree, heap, const_and_copies_stack, 2); 1079169689Skan VEC_quick_push (tree, const_and_copies_stack, prev_x); 1080169689Skan VEC_quick_push (tree, const_and_copies_stack, x); 1081169689Skan} 1082169689Skan 1083169689Skan 1084169689Skan/* Return the loop depth of the basic block of the defining statement of X. 1085169689Skan This number should not be treated as absolutely correct because the loop 1086169689Skan information may not be completely up-to-date when dom runs. However, it 1087169689Skan will be relatively correct, and as more passes are taught to keep loop info 1088169689Skan up to date, the result will become more and more accurate. */ 1089169689Skan 1090169689Skanint 1091169689Skanloop_depth_of_name (tree x) 1092169689Skan{ 1093169689Skan tree defstmt; 1094169689Skan basic_block defbb; 1095169689Skan 1096169689Skan /* If it's not an SSA_NAME, we have no clue where the definition is. */ 1097169689Skan if (TREE_CODE (x) != SSA_NAME) 1098169689Skan return 0; 1099169689Skan 1100169689Skan /* Otherwise return the loop depth of the defining statement's bb. 1101169689Skan Note that there may not actually be a bb for this statement, if the 1102169689Skan ssa_name is live on entry. */ 1103169689Skan defstmt = SSA_NAME_DEF_STMT (x); 1104169689Skan defbb = bb_for_stmt (defstmt); 1105169689Skan if (!defbb) 1106169689Skan return 0; 1107169689Skan 1108169689Skan return defbb->loop_depth; 1109169689Skan} 1110169689Skan 1111169689Skan 1112169689Skan/* Record that X is equal to Y in const_and_copies. Record undo 1113169689Skan information in the block-local vector. */ 1114169689Skan 1115169689Skanstatic void 1116169689Skanrecord_const_or_copy (tree x, tree y) 1117169689Skan{ 1118169689Skan tree prev_x = SSA_NAME_VALUE (x); 1119169689Skan 1120169689Skan if (TREE_CODE (y) == SSA_NAME) 1121169689Skan { 1122169689Skan tree tmp = SSA_NAME_VALUE (y); 1123169689Skan if (tmp) 1124169689Skan y = tmp; 1125169689Skan } 1126169689Skan 1127169689Skan record_const_or_copy_1 (x, y, prev_x); 1128169689Skan} 1129169689Skan 1130169689Skan/* Similarly, but assume that X and Y are the two operands of an EQ_EXPR. 1131169689Skan This constrains the cases in which we may treat this as assignment. */ 1132169689Skan 1133169689Skanstatic void 1134169689Skanrecord_equality (tree x, tree y) 1135169689Skan{ 1136169689Skan tree prev_x = NULL, prev_y = NULL; 1137169689Skan 1138169689Skan if (TREE_CODE (x) == SSA_NAME) 1139169689Skan prev_x = SSA_NAME_VALUE (x); 1140169689Skan if (TREE_CODE (y) == SSA_NAME) 1141169689Skan prev_y = SSA_NAME_VALUE (y); 1142169689Skan 1143169689Skan /* If one of the previous values is invariant, or invariant in more loops 1144169689Skan (by depth), then use that. 1145169689Skan Otherwise it doesn't matter which value we choose, just so 1146169689Skan long as we canonicalize on one value. */ 1147169689Skan if (TREE_INVARIANT (y)) 1148169689Skan ; 1149169689Skan else if (TREE_INVARIANT (x) || (loop_depth_of_name (x) <= loop_depth_of_name (y))) 1150169689Skan prev_x = x, x = y, y = prev_x, prev_x = prev_y; 1151169689Skan else if (prev_x && TREE_INVARIANT (prev_x)) 1152169689Skan x = y, y = prev_x, prev_x = prev_y; 1153169689Skan else if (prev_y && TREE_CODE (prev_y) != VALUE_HANDLE) 1154169689Skan y = prev_y; 1155169689Skan 1156169689Skan /* After the swapping, we must have one SSA_NAME. */ 1157169689Skan if (TREE_CODE (x) != SSA_NAME) 1158169689Skan return; 1159169689Skan 1160169689Skan /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a 1161169689Skan variable compared against zero. If we're honoring signed zeros, 1162169689Skan then we cannot record this value unless we know that the value is 1163169689Skan nonzero. */ 1164169689Skan if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x))) 1165169689Skan && (TREE_CODE (y) != REAL_CST 1166169689Skan || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y)))) 1167169689Skan return; 1168169689Skan 1169169689Skan record_const_or_copy_1 (x, y, prev_x); 1170169689Skan} 1171169689Skan 1172169689Skan/* Returns true when STMT is a simple iv increment. It detects the 1173169689Skan following situation: 1174169689Skan 1175169689Skan i_1 = phi (..., i_2) 1176169689Skan i_2 = i_1 +/- ... */ 1177169689Skan 1178169689Skanstatic bool 1179169689Skansimple_iv_increment_p (tree stmt) 1180169689Skan{ 1181169689Skan tree lhs, rhs, preinc, phi; 1182169689Skan unsigned i; 1183169689Skan 1184169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR) 1185169689Skan return false; 1186169689Skan 1187169689Skan lhs = TREE_OPERAND (stmt, 0); 1188169689Skan if (TREE_CODE (lhs) != SSA_NAME) 1189169689Skan return false; 1190169689Skan 1191169689Skan rhs = TREE_OPERAND (stmt, 1); 1192169689Skan 1193169689Skan if (TREE_CODE (rhs) != PLUS_EXPR 1194169689Skan && TREE_CODE (rhs) != MINUS_EXPR) 1195169689Skan return false; 1196169689Skan 1197169689Skan preinc = TREE_OPERAND (rhs, 0); 1198169689Skan if (TREE_CODE (preinc) != SSA_NAME) 1199169689Skan return false; 1200169689Skan 1201169689Skan phi = SSA_NAME_DEF_STMT (preinc); 1202169689Skan if (TREE_CODE (phi) != PHI_NODE) 1203169689Skan return false; 1204169689Skan 1205169689Skan for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++) 1206169689Skan if (PHI_ARG_DEF (phi, i) == lhs) 1207169689Skan return true; 1208169689Skan 1209169689Skan return false; 1210169689Skan} 1211169689Skan 1212169689Skan/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current 1213169689Skan known value for that SSA_NAME (or NULL if no value is known). 1214169689Skan 1215169689Skan Propagate values from CONST_AND_COPIES into the PHI nodes of the 1216169689Skan successors of BB. */ 1217169689Skan 1218169689Skanstatic void 1219169689Skancprop_into_successor_phis (basic_block bb) 1220169689Skan{ 1221169689Skan edge e; 1222169689Skan edge_iterator ei; 1223169689Skan 1224169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1225169689Skan { 1226169689Skan tree phi; 1227169689Skan int indx; 1228169689Skan 1229169689Skan /* If this is an abnormal edge, then we do not want to copy propagate 1230169689Skan into the PHI alternative associated with this edge. */ 1231169689Skan if (e->flags & EDGE_ABNORMAL) 1232169689Skan continue; 1233169689Skan 1234169689Skan phi = phi_nodes (e->dest); 1235169689Skan if (! phi) 1236169689Skan continue; 1237169689Skan 1238169689Skan indx = e->dest_idx; 1239169689Skan for ( ; phi; phi = PHI_CHAIN (phi)) 1240169689Skan { 1241169689Skan tree new; 1242169689Skan use_operand_p orig_p; 1243169689Skan tree orig; 1244169689Skan 1245169689Skan /* The alternative may be associated with a constant, so verify 1246169689Skan it is an SSA_NAME before doing anything with it. */ 1247169689Skan orig_p = PHI_ARG_DEF_PTR (phi, indx); 1248169689Skan orig = USE_FROM_PTR (orig_p); 1249169689Skan if (TREE_CODE (orig) != SSA_NAME) 1250169689Skan continue; 1251169689Skan 1252169689Skan /* If we have *ORIG_P in our constant/copy table, then replace 1253169689Skan ORIG_P with its value in our constant/copy table. */ 1254169689Skan new = SSA_NAME_VALUE (orig); 1255169689Skan if (new 1256169689Skan && new != orig 1257169689Skan && (TREE_CODE (new) == SSA_NAME 1258169689Skan || is_gimple_min_invariant (new)) 1259169689Skan && may_propagate_copy (orig, new)) 1260169689Skan propagate_value (orig_p, new); 1261169689Skan } 1262169689Skan } 1263169689Skan} 1264169689Skan 1265169689Skan/* We have finished optimizing BB, record any information implied by 1266169689Skan taking a specific outgoing edge from BB. */ 1267169689Skan 1268169689Skanstatic void 1269169689Skanrecord_edge_info (basic_block bb) 1270169689Skan{ 1271169689Skan block_stmt_iterator bsi = bsi_last (bb); 1272169689Skan struct edge_info *edge_info; 1273169689Skan 1274169689Skan if (! bsi_end_p (bsi)) 1275169689Skan { 1276169689Skan tree stmt = bsi_stmt (bsi); 1277169689Skan 1278169689Skan if (stmt && TREE_CODE (stmt) == SWITCH_EXPR) 1279169689Skan { 1280169689Skan tree cond = SWITCH_COND (stmt); 1281169689Skan 1282169689Skan if (TREE_CODE (cond) == SSA_NAME) 1283169689Skan { 1284169689Skan tree labels = SWITCH_LABELS (stmt); 1285169689Skan int i, n_labels = TREE_VEC_LENGTH (labels); 1286169689Skan tree *info = XCNEWVEC (tree, last_basic_block); 1287169689Skan edge e; 1288169689Skan edge_iterator ei; 1289169689Skan 1290169689Skan for (i = 0; i < n_labels; i++) 1291169689Skan { 1292169689Skan tree label = TREE_VEC_ELT (labels, i); 1293169689Skan basic_block target_bb = label_to_block (CASE_LABEL (label)); 1294169689Skan 1295169689Skan if (CASE_HIGH (label) 1296169689Skan || !CASE_LOW (label) 1297169689Skan || info[target_bb->index]) 1298169689Skan info[target_bb->index] = error_mark_node; 1299169689Skan else 1300169689Skan info[target_bb->index] = label; 1301169689Skan } 1302169689Skan 1303169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1304169689Skan { 1305169689Skan basic_block target_bb = e->dest; 1306169689Skan tree node = info[target_bb->index]; 1307169689Skan 1308169689Skan if (node != NULL && node != error_mark_node) 1309169689Skan { 1310169689Skan tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node)); 1311169689Skan edge_info = allocate_edge_info (e); 1312169689Skan edge_info->lhs = cond; 1313169689Skan edge_info->rhs = x; 1314169689Skan } 1315169689Skan } 1316169689Skan free (info); 1317169689Skan } 1318169689Skan } 1319169689Skan 1320169689Skan /* A COND_EXPR may create equivalences too. */ 1321169689Skan if (stmt && TREE_CODE (stmt) == COND_EXPR) 1322169689Skan { 1323169689Skan tree cond = COND_EXPR_COND (stmt); 1324169689Skan edge true_edge; 1325169689Skan edge false_edge; 1326169689Skan 1327169689Skan extract_true_false_edges_from_block (bb, &true_edge, &false_edge); 1328169689Skan 1329169689Skan /* If the conditional is a single variable 'X', record 'X = 1' 1330169689Skan for the true edge and 'X = 0' on the false edge. */ 1331169689Skan if (SSA_VAR_P (cond)) 1332169689Skan { 1333169689Skan struct edge_info *edge_info; 1334169689Skan 1335169689Skan edge_info = allocate_edge_info (true_edge); 1336169689Skan edge_info->lhs = cond; 1337169689Skan edge_info->rhs = constant_boolean_node (1, TREE_TYPE (cond)); 1338169689Skan 1339169689Skan edge_info = allocate_edge_info (false_edge); 1340169689Skan edge_info->lhs = cond; 1341169689Skan edge_info->rhs = constant_boolean_node (0, TREE_TYPE (cond)); 1342169689Skan } 1343169689Skan /* Equality tests may create one or two equivalences. */ 1344169689Skan else if (COMPARISON_CLASS_P (cond)) 1345169689Skan { 1346169689Skan tree op0 = TREE_OPERAND (cond, 0); 1347169689Skan tree op1 = TREE_OPERAND (cond, 1); 1348169689Skan 1349169689Skan /* Special case comparing booleans against a constant as we 1350169689Skan know the value of OP0 on both arms of the branch. i.e., we 1351169689Skan can record an equivalence for OP0 rather than COND. */ 1352169689Skan if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR) 1353169689Skan && TREE_CODE (op0) == SSA_NAME 1354169689Skan && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE 1355169689Skan && is_gimple_min_invariant (op1)) 1356169689Skan { 1357169689Skan if (TREE_CODE (cond) == EQ_EXPR) 1358169689Skan { 1359169689Skan edge_info = allocate_edge_info (true_edge); 1360169689Skan edge_info->lhs = op0; 1361169689Skan edge_info->rhs = (integer_zerop (op1) 1362169689Skan ? boolean_false_node 1363169689Skan : boolean_true_node); 1364169689Skan 1365169689Skan edge_info = allocate_edge_info (false_edge); 1366169689Skan edge_info->lhs = op0; 1367169689Skan edge_info->rhs = (integer_zerop (op1) 1368169689Skan ? boolean_true_node 1369169689Skan : boolean_false_node); 1370169689Skan } 1371169689Skan else 1372169689Skan { 1373169689Skan edge_info = allocate_edge_info (true_edge); 1374169689Skan edge_info->lhs = op0; 1375169689Skan edge_info->rhs = (integer_zerop (op1) 1376169689Skan ? boolean_true_node 1377169689Skan : boolean_false_node); 1378169689Skan 1379169689Skan edge_info = allocate_edge_info (false_edge); 1380169689Skan edge_info->lhs = op0; 1381169689Skan edge_info->rhs = (integer_zerop (op1) 1382169689Skan ? boolean_false_node 1383169689Skan : boolean_true_node); 1384169689Skan } 1385169689Skan } 1386169689Skan 1387169689Skan else if (is_gimple_min_invariant (op0) 1388169689Skan && (TREE_CODE (op1) == SSA_NAME 1389169689Skan || is_gimple_min_invariant (op1))) 1390169689Skan { 1391169689Skan tree inverted = invert_truthvalue (cond); 1392169689Skan struct edge_info *edge_info; 1393169689Skan 1394169689Skan edge_info = allocate_edge_info (true_edge); 1395169689Skan record_conditions (edge_info, cond, inverted); 1396169689Skan 1397169689Skan if (TREE_CODE (cond) == EQ_EXPR) 1398169689Skan { 1399169689Skan edge_info->lhs = op1; 1400169689Skan edge_info->rhs = op0; 1401169689Skan } 1402169689Skan 1403169689Skan edge_info = allocate_edge_info (false_edge); 1404169689Skan record_conditions (edge_info, inverted, cond); 1405169689Skan 1406169689Skan if (TREE_CODE (cond) == NE_EXPR) 1407169689Skan { 1408169689Skan edge_info->lhs = op1; 1409169689Skan edge_info->rhs = op0; 1410169689Skan } 1411169689Skan } 1412169689Skan 1413169689Skan else if (TREE_CODE (op0) == SSA_NAME 1414169689Skan && (is_gimple_min_invariant (op1) 1415169689Skan || TREE_CODE (op1) == SSA_NAME)) 1416169689Skan { 1417169689Skan tree inverted = invert_truthvalue (cond); 1418169689Skan struct edge_info *edge_info; 1419169689Skan 1420169689Skan edge_info = allocate_edge_info (true_edge); 1421169689Skan record_conditions (edge_info, cond, inverted); 1422169689Skan 1423169689Skan if (TREE_CODE (cond) == EQ_EXPR) 1424169689Skan { 1425169689Skan edge_info->lhs = op0; 1426169689Skan edge_info->rhs = op1; 1427169689Skan } 1428169689Skan 1429169689Skan edge_info = allocate_edge_info (false_edge); 1430169689Skan record_conditions (edge_info, inverted, cond); 1431169689Skan 1432169689Skan if (TREE_CODE (cond) == NE_EXPR) 1433169689Skan { 1434169689Skan edge_info->lhs = op0; 1435169689Skan edge_info->rhs = op1; 1436169689Skan } 1437169689Skan } 1438169689Skan } 1439169689Skan 1440169689Skan /* ??? TRUTH_NOT_EXPR can create an equivalence too. */ 1441169689Skan } 1442169689Skan } 1443169689Skan} 1444169689Skan 1445169689Skan/* Propagate information from BB to its outgoing edges. 1446169689Skan 1447169689Skan This can include equivalency information implied by control statements 1448169689Skan at the end of BB and const/copy propagation into PHIs in BB's 1449169689Skan successor blocks. */ 1450169689Skan 1451169689Skanstatic void 1452169689Skanpropagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1453169689Skan basic_block bb) 1454169689Skan{ 1455169689Skan record_edge_info (bb); 1456169689Skan cprop_into_successor_phis (bb); 1457169689Skan} 1458169689Skan 1459169689Skan/* Search for redundant computations in STMT. If any are found, then 1460169689Skan replace them with the variable holding the result of the computation. 1461169689Skan 1462169689Skan If safe, record this expression into the available expression hash 1463169689Skan table. */ 1464169689Skan 1465169689Skanstatic bool 1466169689Skaneliminate_redundant_computations (tree stmt) 1467169689Skan{ 1468169689Skan tree *expr_p, def = NULL_TREE; 1469169689Skan bool insert = true; 1470169689Skan tree cached_lhs; 1471169689Skan bool retval = false; 1472169689Skan bool modify_expr_p = false; 1473169689Skan 1474169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR) 1475169689Skan def = TREE_OPERAND (stmt, 0); 1476169689Skan 1477169689Skan /* Certain expressions on the RHS can be optimized away, but can not 1478169689Skan themselves be entered into the hash tables. */ 1479169689Skan if (! def 1480169689Skan || TREE_CODE (def) != SSA_NAME 1481169689Skan || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) 1482169689Skan || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF) 1483169689Skan /* Do not record equivalences for increments of ivs. This would create 1484169689Skan overlapping live ranges for a very questionable gain. */ 1485169689Skan || simple_iv_increment_p (stmt)) 1486169689Skan insert = false; 1487169689Skan 1488169689Skan /* Check if the expression has been computed before. */ 1489169689Skan cached_lhs = lookup_avail_expr (stmt, insert); 1490169689Skan 1491169689Skan opt_stats.num_exprs_considered++; 1492169689Skan 1493169689Skan /* Get a pointer to the expression we are trying to optimize. */ 1494169689Skan if (TREE_CODE (stmt) == COND_EXPR) 1495169689Skan expr_p = &COND_EXPR_COND (stmt); 1496169689Skan else if (TREE_CODE (stmt) == SWITCH_EXPR) 1497169689Skan expr_p = &SWITCH_COND (stmt); 1498169689Skan else if (TREE_CODE (stmt) == RETURN_EXPR && TREE_OPERAND (stmt, 0)) 1499169689Skan { 1500169689Skan expr_p = &TREE_OPERAND (TREE_OPERAND (stmt, 0), 1); 1501169689Skan modify_expr_p = true; 1502169689Skan } 1503169689Skan else 1504169689Skan { 1505169689Skan expr_p = &TREE_OPERAND (stmt, 1); 1506169689Skan modify_expr_p = true; 1507169689Skan } 1508169689Skan 1509169689Skan /* It is safe to ignore types here since we have already done 1510169689Skan type checking in the hashing and equality routines. In fact 1511169689Skan type checking here merely gets in the way of constant 1512169689Skan propagation. Also, make sure that it is safe to propagate 1513169689Skan CACHED_LHS into *EXPR_P. */ 1514169689Skan if (cached_lhs 1515169689Skan && ((TREE_CODE (cached_lhs) != SSA_NAME 1516169689Skan && (modify_expr_p 1517169689Skan || tree_ssa_useless_type_conversion_1 (TREE_TYPE (*expr_p), 1518169689Skan TREE_TYPE (cached_lhs)))) 1519169689Skan || may_propagate_copy (*expr_p, cached_lhs))) 1520169689Skan { 1521169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1522169689Skan { 1523169689Skan fprintf (dump_file, " Replaced redundant expr '"); 1524169689Skan print_generic_expr (dump_file, *expr_p, dump_flags); 1525169689Skan fprintf (dump_file, "' with '"); 1526169689Skan print_generic_expr (dump_file, cached_lhs, dump_flags); 1527169689Skan fprintf (dump_file, "'\n"); 1528169689Skan } 1529169689Skan 1530169689Skan opt_stats.num_re++; 1531169689Skan 1532169689Skan#if defined ENABLE_CHECKING 1533169689Skan gcc_assert (TREE_CODE (cached_lhs) == SSA_NAME 1534169689Skan || is_gimple_min_invariant (cached_lhs)); 1535169689Skan#endif 1536169689Skan 1537169689Skan if (TREE_CODE (cached_lhs) == ADDR_EXPR 1538169689Skan || (POINTER_TYPE_P (TREE_TYPE (*expr_p)) 1539169689Skan && is_gimple_min_invariant (cached_lhs))) 1540169689Skan retval = true; 1541169689Skan 1542169689Skan if (modify_expr_p 1543169689Skan && !tree_ssa_useless_type_conversion_1 (TREE_TYPE (*expr_p), 1544169689Skan TREE_TYPE (cached_lhs))) 1545169689Skan cached_lhs = fold_convert (TREE_TYPE (*expr_p), cached_lhs); 1546169689Skan 1547169689Skan propagate_tree_value (expr_p, cached_lhs); 1548169689Skan mark_stmt_modified (stmt); 1549169689Skan } 1550169689Skan return retval; 1551169689Skan} 1552169689Skan 1553169689Skan/* STMT, a MODIFY_EXPR, may create certain equivalences, in either 1554169689Skan the available expressions table or the const_and_copies table. 1555169689Skan Detect and record those equivalences. */ 1556169689Skan 1557169689Skanstatic void 1558169689Skanrecord_equivalences_from_stmt (tree stmt, 1559169689Skan int may_optimize_p, 1560169689Skan stmt_ann_t ann) 1561169689Skan{ 1562169689Skan tree lhs = TREE_OPERAND (stmt, 0); 1563169689Skan enum tree_code lhs_code = TREE_CODE (lhs); 1564169689Skan 1565169689Skan if (lhs_code == SSA_NAME) 1566169689Skan { 1567169689Skan tree rhs = TREE_OPERAND (stmt, 1); 1568169689Skan 1569169689Skan /* Strip away any useless type conversions. */ 1570169689Skan STRIP_USELESS_TYPE_CONVERSION (rhs); 1571169689Skan 1572169689Skan /* If the RHS of the assignment is a constant or another variable that 1573169689Skan may be propagated, register it in the CONST_AND_COPIES table. We 1574169689Skan do not need to record unwind data for this, since this is a true 1575169689Skan assignment and not an equivalence inferred from a comparison. All 1576169689Skan uses of this ssa name are dominated by this assignment, so unwinding 1577169689Skan just costs time and space. */ 1578169689Skan if (may_optimize_p 1579169689Skan && (TREE_CODE (rhs) == SSA_NAME 1580169689Skan || is_gimple_min_invariant (rhs))) 1581169689Skan SSA_NAME_VALUE (lhs) = rhs; 1582169689Skan } 1583169689Skan 1584169689Skan /* A memory store, even an aliased store, creates a useful 1585169689Skan equivalence. By exchanging the LHS and RHS, creating suitable 1586169689Skan vops and recording the result in the available expression table, 1587169689Skan we may be able to expose more redundant loads. */ 1588169689Skan if (!ann->has_volatile_ops 1589169689Skan && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME 1590169689Skan || is_gimple_min_invariant (TREE_OPERAND (stmt, 1))) 1591169689Skan && !is_gimple_reg (lhs)) 1592169689Skan { 1593169689Skan tree rhs = TREE_OPERAND (stmt, 1); 1594169689Skan tree new; 1595169689Skan 1596169689Skan /* FIXME: If the LHS of the assignment is a bitfield and the RHS 1597169689Skan is a constant, we need to adjust the constant to fit into the 1598169689Skan type of the LHS. If the LHS is a bitfield and the RHS is not 1599169689Skan a constant, then we can not record any equivalences for this 1600169689Skan statement since we would need to represent the widening or 1601169689Skan narrowing of RHS. This fixes gcc.c-torture/execute/921016-1.c 1602169689Skan and should not be necessary if GCC represented bitfields 1603169689Skan properly. */ 1604169689Skan if (lhs_code == COMPONENT_REF 1605169689Skan && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1))) 1606169689Skan { 1607169689Skan if (TREE_CONSTANT (rhs)) 1608169689Skan rhs = widen_bitfield (rhs, TREE_OPERAND (lhs, 1), lhs); 1609169689Skan else 1610169689Skan rhs = NULL; 1611169689Skan 1612169689Skan /* If the value overflowed, then we can not use this equivalence. */ 1613169689Skan if (rhs && ! is_gimple_min_invariant (rhs)) 1614169689Skan rhs = NULL; 1615169689Skan } 1616169689Skan 1617169689Skan if (rhs) 1618169689Skan { 1619169689Skan /* Build a new statement with the RHS and LHS exchanged. */ 1620169689Skan new = build2 (MODIFY_EXPR, TREE_TYPE (stmt), rhs, lhs); 1621169689Skan 1622169689Skan create_ssa_artficial_load_stmt (new, stmt); 1623169689Skan 1624169689Skan /* Finally enter the statement into the available expression 1625169689Skan table. */ 1626169689Skan lookup_avail_expr (new, true); 1627169689Skan } 1628169689Skan } 1629169689Skan} 1630169689Skan 1631169689Skan/* Replace *OP_P in STMT with any known equivalent value for *OP_P from 1632169689Skan CONST_AND_COPIES. */ 1633169689Skan 1634169689Skanstatic bool 1635169689Skancprop_operand (tree stmt, use_operand_p op_p) 1636169689Skan{ 1637169689Skan bool may_have_exposed_new_symbols = false; 1638169689Skan tree val; 1639169689Skan tree op = USE_FROM_PTR (op_p); 1640169689Skan 1641169689Skan /* If the operand has a known constant value or it is known to be a 1642169689Skan copy of some other variable, use the value or copy stored in 1643169689Skan CONST_AND_COPIES. */ 1644169689Skan val = SSA_NAME_VALUE (op); 1645169689Skan if (val && val != op && TREE_CODE (val) != VALUE_HANDLE) 1646169689Skan { 1647169689Skan tree op_type, val_type; 1648169689Skan 1649169689Skan /* Do not change the base variable in the virtual operand 1650169689Skan tables. That would make it impossible to reconstruct 1651169689Skan the renamed virtual operand if we later modify this 1652169689Skan statement. Also only allow the new value to be an SSA_NAME 1653169689Skan for propagation into virtual operands. */ 1654169689Skan if (!is_gimple_reg (op) 1655169689Skan && (TREE_CODE (val) != SSA_NAME 1656169689Skan || is_gimple_reg (val) 1657169689Skan || get_virtual_var (val) != get_virtual_var (op))) 1658169689Skan return false; 1659169689Skan 1660169689Skan /* Do not replace hard register operands in asm statements. */ 1661169689Skan if (TREE_CODE (stmt) == ASM_EXPR 1662169689Skan && !may_propagate_copy_into_asm (op)) 1663169689Skan return false; 1664169689Skan 1665169689Skan /* Get the toplevel type of each operand. */ 1666169689Skan op_type = TREE_TYPE (op); 1667169689Skan val_type = TREE_TYPE (val); 1668169689Skan 1669169689Skan /* While both types are pointers, get the type of the object 1670169689Skan pointed to. */ 1671169689Skan while (POINTER_TYPE_P (op_type) && POINTER_TYPE_P (val_type)) 1672169689Skan { 1673169689Skan op_type = TREE_TYPE (op_type); 1674169689Skan val_type = TREE_TYPE (val_type); 1675169689Skan } 1676169689Skan 1677169689Skan /* Make sure underlying types match before propagating a constant by 1678169689Skan converting the constant to the proper type. Note that convert may 1679169689Skan return a non-gimple expression, in which case we ignore this 1680169689Skan propagation opportunity. */ 1681169689Skan if (TREE_CODE (val) != SSA_NAME) 1682169689Skan { 1683169689Skan if (!lang_hooks.types_compatible_p (op_type, val_type)) 1684169689Skan { 1685169689Skan val = fold_convert (TREE_TYPE (op), val); 1686169689Skan if (!is_gimple_min_invariant (val)) 1687169689Skan return false; 1688169689Skan } 1689169689Skan } 1690169689Skan 1691169689Skan /* Certain operands are not allowed to be copy propagated due 1692169689Skan to their interaction with exception handling and some GCC 1693169689Skan extensions. */ 1694169689Skan else if (!may_propagate_copy (op, val)) 1695169689Skan return false; 1696169689Skan 1697169689Skan /* Do not propagate copies if the propagated value is at a deeper loop 1698169689Skan depth than the propagatee. Otherwise, this may move loop variant 1699169689Skan variables outside of their loops and prevent coalescing 1700169689Skan opportunities. If the value was loop invariant, it will be hoisted 1701169689Skan by LICM and exposed for copy propagation. */ 1702169689Skan if (loop_depth_of_name (val) > loop_depth_of_name (op)) 1703169689Skan return false; 1704169689Skan 1705169689Skan /* Dump details. */ 1706169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1707169689Skan { 1708169689Skan fprintf (dump_file, " Replaced '"); 1709169689Skan print_generic_expr (dump_file, op, dump_flags); 1710169689Skan fprintf (dump_file, "' with %s '", 1711169689Skan (TREE_CODE (val) != SSA_NAME ? "constant" : "variable")); 1712169689Skan print_generic_expr (dump_file, val, dump_flags); 1713169689Skan fprintf (dump_file, "'\n"); 1714169689Skan } 1715169689Skan 1716169689Skan /* If VAL is an ADDR_EXPR or a constant of pointer type, note 1717169689Skan that we may have exposed a new symbol for SSA renaming. */ 1718169689Skan if (TREE_CODE (val) == ADDR_EXPR 1719169689Skan || (POINTER_TYPE_P (TREE_TYPE (op)) 1720169689Skan && is_gimple_min_invariant (val))) 1721169689Skan may_have_exposed_new_symbols = true; 1722169689Skan 1723169689Skan if (TREE_CODE (val) != SSA_NAME) 1724169689Skan opt_stats.num_const_prop++; 1725169689Skan else 1726169689Skan opt_stats.num_copy_prop++; 1727169689Skan 1728169689Skan propagate_value (op_p, val); 1729169689Skan 1730169689Skan /* And note that we modified this statement. This is now 1731169689Skan safe, even if we changed virtual operands since we will 1732169689Skan rescan the statement and rewrite its operands again. */ 1733169689Skan mark_stmt_modified (stmt); 1734169689Skan } 1735169689Skan return may_have_exposed_new_symbols; 1736169689Skan} 1737169689Skan 1738169689Skan/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current 1739169689Skan known value for that SSA_NAME (or NULL if no value is known). 1740169689Skan 1741169689Skan Propagate values from CONST_AND_COPIES into the uses, vuses and 1742169689Skan v_may_def_ops of STMT. */ 1743169689Skan 1744169689Skanstatic bool 1745169689Skancprop_into_stmt (tree stmt) 1746169689Skan{ 1747169689Skan bool may_have_exposed_new_symbols = false; 1748169689Skan use_operand_p op_p; 1749169689Skan ssa_op_iter iter; 1750169689Skan 1751169689Skan FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES) 1752169689Skan { 1753169689Skan if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME) 1754169689Skan may_have_exposed_new_symbols |= cprop_operand (stmt, op_p); 1755169689Skan } 1756169689Skan 1757169689Skan return may_have_exposed_new_symbols; 1758169689Skan} 1759169689Skan 1760169689Skan 1761169689Skan/* Optimize the statement pointed to by iterator SI. 1762169689Skan 1763169689Skan We try to perform some simplistic global redundancy elimination and 1764169689Skan constant propagation: 1765169689Skan 1766169689Skan 1- To detect global redundancy, we keep track of expressions that have 1767169689Skan been computed in this block and its dominators. If we find that the 1768169689Skan same expression is computed more than once, we eliminate repeated 1769169689Skan computations by using the target of the first one. 1770169689Skan 1771169689Skan 2- Constant values and copy assignments. This is used to do very 1772169689Skan simplistic constant and copy propagation. When a constant or copy 1773169689Skan assignment is found, we map the value on the RHS of the assignment to 1774169689Skan the variable in the LHS in the CONST_AND_COPIES table. */ 1775169689Skan 1776169689Skanstatic void 1777169689Skanoptimize_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1778169689Skan basic_block bb, block_stmt_iterator si) 1779169689Skan{ 1780169689Skan stmt_ann_t ann; 1781169689Skan tree stmt, old_stmt; 1782169689Skan bool may_optimize_p; 1783169689Skan bool may_have_exposed_new_symbols = false; 1784169689Skan 1785169689Skan old_stmt = stmt = bsi_stmt (si); 1786169689Skan 1787169689Skan if (TREE_CODE (stmt) == COND_EXPR) 1788169689Skan canonicalize_comparison (stmt); 1789169689Skan 1790169689Skan update_stmt_if_modified (stmt); 1791169689Skan ann = stmt_ann (stmt); 1792169689Skan opt_stats.num_stmts++; 1793169689Skan may_have_exposed_new_symbols = false; 1794169689Skan 1795169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1796169689Skan { 1797169689Skan fprintf (dump_file, "Optimizing statement "); 1798169689Skan print_generic_stmt (dump_file, stmt, TDF_SLIM); 1799169689Skan } 1800169689Skan 1801169689Skan /* Const/copy propagate into USES, VUSES and the RHS of V_MAY_DEFs. */ 1802169689Skan may_have_exposed_new_symbols = cprop_into_stmt (stmt); 1803169689Skan 1804169689Skan /* If the statement has been modified with constant replacements, 1805169689Skan fold its RHS before checking for redundant computations. */ 1806169689Skan if (ann->modified) 1807169689Skan { 1808169689Skan tree rhs; 1809169689Skan 1810169689Skan /* Try to fold the statement making sure that STMT is kept 1811169689Skan up to date. */ 1812169689Skan if (fold_stmt (bsi_stmt_ptr (si))) 1813169689Skan { 1814169689Skan stmt = bsi_stmt (si); 1815169689Skan ann = stmt_ann (stmt); 1816169689Skan 1817169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1818169689Skan { 1819169689Skan fprintf (dump_file, " Folded to: "); 1820169689Skan print_generic_stmt (dump_file, stmt, TDF_SLIM); 1821169689Skan } 1822169689Skan } 1823169689Skan 1824169689Skan rhs = get_rhs (stmt); 1825169689Skan if (rhs && TREE_CODE (rhs) == ADDR_EXPR) 1826169689Skan recompute_tree_invariant_for_addr_expr (rhs); 1827169689Skan 1828169689Skan /* Constant/copy propagation above may change the set of 1829169689Skan virtual operands associated with this statement. Folding 1830169689Skan may remove the need for some virtual operands. 1831169689Skan 1832169689Skan Indicate we will need to rescan and rewrite the statement. */ 1833169689Skan may_have_exposed_new_symbols = true; 1834169689Skan } 1835169689Skan 1836169689Skan /* Check for redundant computations. Do this optimization only 1837169689Skan for assignments that have no volatile ops and conditionals. */ 1838169689Skan may_optimize_p = (!ann->has_volatile_ops 1839169689Skan && ((TREE_CODE (stmt) == RETURN_EXPR 1840169689Skan && TREE_OPERAND (stmt, 0) 1841169689Skan && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR 1842169689Skan && ! (TREE_SIDE_EFFECTS 1843169689Skan (TREE_OPERAND (TREE_OPERAND (stmt, 0), 1)))) 1844169689Skan || (TREE_CODE (stmt) == MODIFY_EXPR 1845169689Skan && ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt, 1))) 1846169689Skan || TREE_CODE (stmt) == COND_EXPR 1847169689Skan || TREE_CODE (stmt) == SWITCH_EXPR)); 1848169689Skan 1849169689Skan if (may_optimize_p) 1850169689Skan may_have_exposed_new_symbols |= eliminate_redundant_computations (stmt); 1851169689Skan 1852169689Skan /* Record any additional equivalences created by this statement. */ 1853169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR) 1854169689Skan record_equivalences_from_stmt (stmt, 1855169689Skan may_optimize_p, 1856169689Skan ann); 1857169689Skan 1858169689Skan /* If STMT is a COND_EXPR and it was modified, then we may know 1859169689Skan where it goes. If that is the case, then mark the CFG as altered. 1860169689Skan 1861169689Skan This will cause us to later call remove_unreachable_blocks and 1862169689Skan cleanup_tree_cfg when it is safe to do so. It is not safe to 1863169689Skan clean things up here since removal of edges and such can trigger 1864169689Skan the removal of PHI nodes, which in turn can release SSA_NAMEs to 1865169689Skan the manager. 1866169689Skan 1867169689Skan That's all fine and good, except that once SSA_NAMEs are released 1868169689Skan to the manager, we must not call create_ssa_name until all references 1869169689Skan to released SSA_NAMEs have been eliminated. 1870169689Skan 1871169689Skan All references to the deleted SSA_NAMEs can not be eliminated until 1872169689Skan we remove unreachable blocks. 1873169689Skan 1874169689Skan We can not remove unreachable blocks until after we have completed 1875169689Skan any queued jump threading. 1876169689Skan 1877169689Skan We can not complete any queued jump threads until we have taken 1878169689Skan appropriate variables out of SSA form. Taking variables out of 1879169689Skan SSA form can call create_ssa_name and thus we lose. 1880169689Skan 1881169689Skan Ultimately I suspect we're going to need to change the interface 1882169689Skan into the SSA_NAME manager. */ 1883169689Skan 1884169689Skan if (ann->modified) 1885169689Skan { 1886169689Skan tree val = NULL; 1887169689Skan 1888169689Skan if (TREE_CODE (stmt) == COND_EXPR) 1889169689Skan val = COND_EXPR_COND (stmt); 1890169689Skan else if (TREE_CODE (stmt) == SWITCH_EXPR) 1891169689Skan val = SWITCH_COND (stmt); 1892169689Skan 1893169689Skan if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val)) 1894169689Skan cfg_altered = true; 1895169689Skan 1896169689Skan /* If we simplified a statement in such a way as to be shown that it 1897169689Skan cannot trap, update the eh information and the cfg to match. */ 1898169689Skan if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) 1899169689Skan { 1900169689Skan bitmap_set_bit (need_eh_cleanup, bb->index); 1901169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1902169689Skan fprintf (dump_file, " Flagged to clear EH edges.\n"); 1903169689Skan } 1904169689Skan } 1905169689Skan 1906169689Skan if (may_have_exposed_new_symbols) 1907169689Skan VEC_safe_push (tree, heap, stmts_to_rescan, bsi_stmt (si)); 1908169689Skan} 1909169689Skan 1910169689Skan/* Search for an existing instance of STMT in the AVAIL_EXPRS table. If 1911169689Skan found, return its LHS. Otherwise insert STMT in the table and return 1912169689Skan NULL_TREE. 1913169689Skan 1914169689Skan Also, when an expression is first inserted in the AVAIL_EXPRS table, it 1915169689Skan is also added to the stack pointed to by BLOCK_AVAIL_EXPRS_P, so that they 1916169689Skan can be removed when we finish processing this block and its children. 1917169689Skan 1918169689Skan NOTE: This function assumes that STMT is a MODIFY_EXPR node that 1919169689Skan contains no CALL_EXPR on its RHS and makes no volatile nor 1920169689Skan aliased references. */ 1921169689Skan 1922169689Skanstatic tree 1923169689Skanlookup_avail_expr (tree stmt, bool insert) 1924169689Skan{ 1925169689Skan void **slot; 1926169689Skan tree lhs; 1927169689Skan tree temp; 1928169689Skan struct expr_hash_elt *element = XNEW (struct expr_hash_elt); 1929169689Skan 1930169689Skan lhs = TREE_CODE (stmt) == MODIFY_EXPR ? TREE_OPERAND (stmt, 0) : NULL; 1931169689Skan 1932169689Skan initialize_hash_element (stmt, lhs, element); 1933169689Skan 1934169689Skan /* Don't bother remembering constant assignments and copy operations. 1935169689Skan Constants and copy operations are handled by the constant/copy propagator 1936169689Skan in optimize_stmt. */ 1937169689Skan if (TREE_CODE (element->rhs) == SSA_NAME 1938169689Skan || is_gimple_min_invariant (element->rhs)) 1939169689Skan { 1940169689Skan free (element); 1941169689Skan return NULL_TREE; 1942169689Skan } 1943169689Skan 1944169689Skan /* Finally try to find the expression in the main expression hash table. */ 1945169689Skan slot = htab_find_slot_with_hash (avail_exprs, element, element->hash, 1946169689Skan (insert ? INSERT : NO_INSERT)); 1947169689Skan if (slot == NULL) 1948169689Skan { 1949169689Skan free (element); 1950169689Skan return NULL_TREE; 1951169689Skan } 1952169689Skan 1953169689Skan if (*slot == NULL) 1954169689Skan { 1955169689Skan *slot = (void *) element; 1956169689Skan VEC_safe_push (tree, heap, avail_exprs_stack, 1957169689Skan stmt ? stmt : element->rhs); 1958169689Skan return NULL_TREE; 1959169689Skan } 1960169689Skan 1961169689Skan /* Extract the LHS of the assignment so that it can be used as the current 1962169689Skan definition of another variable. */ 1963169689Skan lhs = ((struct expr_hash_elt *)*slot)->lhs; 1964169689Skan 1965169689Skan /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then 1966169689Skan use the value from the const_and_copies table. */ 1967169689Skan if (TREE_CODE (lhs) == SSA_NAME) 1968169689Skan { 1969169689Skan temp = SSA_NAME_VALUE (lhs); 1970169689Skan if (temp && TREE_CODE (temp) != VALUE_HANDLE) 1971169689Skan lhs = temp; 1972169689Skan } 1973169689Skan 1974169689Skan free (element); 1975169689Skan return lhs; 1976169689Skan} 1977169689Skan 1978169689Skan/* Hashing and equality functions for AVAIL_EXPRS. The table stores 1979169689Skan MODIFY_EXPR statements. We compute a value number for expressions using 1980169689Skan the code of the expression and the SSA numbers of its operands. */ 1981169689Skan 1982169689Skanstatic hashval_t 1983169689Skanavail_expr_hash (const void *p) 1984169689Skan{ 1985169689Skan tree stmt = ((struct expr_hash_elt *)p)->stmt; 1986169689Skan tree rhs = ((struct expr_hash_elt *)p)->rhs; 1987169689Skan tree vuse; 1988169689Skan ssa_op_iter iter; 1989169689Skan hashval_t val = 0; 1990169689Skan 1991169689Skan /* iterative_hash_expr knows how to deal with any expression and 1992169689Skan deals with commutative operators as well, so just use it instead 1993169689Skan of duplicating such complexities here. */ 1994169689Skan val = iterative_hash_expr (rhs, val); 1995169689Skan 1996169689Skan /* If the hash table entry is not associated with a statement, then we 1997169689Skan can just hash the expression and not worry about virtual operands 1998169689Skan and such. */ 1999169689Skan if (!stmt || !stmt_ann (stmt)) 2000169689Skan return val; 2001169689Skan 2002169689Skan /* Add the SSA version numbers of every vuse operand. This is important 2003169689Skan because compound variables like arrays are not renamed in the 2004169689Skan operands. Rather, the rename is done on the virtual variable 2005169689Skan representing all the elements of the array. */ 2006169689Skan FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE) 2007169689Skan val = iterative_hash_expr (vuse, val); 2008169689Skan 2009169689Skan return val; 2010169689Skan} 2011169689Skan 2012169689Skanstatic hashval_t 2013169689Skanreal_avail_expr_hash (const void *p) 2014169689Skan{ 2015169689Skan return ((const struct expr_hash_elt *)p)->hash; 2016169689Skan} 2017169689Skan 2018169689Skanstatic int 2019169689Skanavail_expr_eq (const void *p1, const void *p2) 2020169689Skan{ 2021169689Skan tree stmt1 = ((struct expr_hash_elt *)p1)->stmt; 2022169689Skan tree rhs1 = ((struct expr_hash_elt *)p1)->rhs; 2023169689Skan tree stmt2 = ((struct expr_hash_elt *)p2)->stmt; 2024169689Skan tree rhs2 = ((struct expr_hash_elt *)p2)->rhs; 2025169689Skan 2026169689Skan /* If they are the same physical expression, return true. */ 2027169689Skan if (rhs1 == rhs2 && stmt1 == stmt2) 2028169689Skan return true; 2029169689Skan 2030169689Skan /* If their codes are not equal, then quit now. */ 2031169689Skan if (TREE_CODE (rhs1) != TREE_CODE (rhs2)) 2032169689Skan return false; 2033169689Skan 2034169689Skan /* In case of a collision, both RHS have to be identical and have the 2035169689Skan same VUSE operands. */ 2036169689Skan if ((TREE_TYPE (rhs1) == TREE_TYPE (rhs2) 2037169689Skan || lang_hooks.types_compatible_p (TREE_TYPE (rhs1), TREE_TYPE (rhs2))) 2038169689Skan && operand_equal_p (rhs1, rhs2, OEP_PURE_SAME)) 2039169689Skan { 2040169689Skan bool ret = compare_ssa_operands_equal (stmt1, stmt2, SSA_OP_VUSE); 2041169689Skan gcc_assert (!ret || ((struct expr_hash_elt *)p1)->hash 2042169689Skan == ((struct expr_hash_elt *)p2)->hash); 2043169689Skan return ret; 2044169689Skan } 2045169689Skan 2046169689Skan return false; 2047169689Skan} 2048169689Skan 2049169689Skan/* PHI-ONLY copy and constant propagation. This pass is meant to clean 2050169689Skan up degenerate PHIs created by or exposed by jump threading. */ 2051169689Skan 2052169689Skan/* Given PHI, return its RHS if the PHI is a degenerate, otherwise return 2053169689Skan NULL. */ 2054169689Skan 2055169689Skanstatic tree 2056169689Skandegenerate_phi_result (tree phi) 2057169689Skan{ 2058169689Skan tree lhs = PHI_RESULT (phi); 2059169689Skan tree val = NULL; 2060169689Skan int i; 2061169689Skan 2062169689Skan /* Ignoring arguments which are the same as LHS, if all the remaining 2063169689Skan arguments are the same, then the PHI is a degenerate and has the 2064169689Skan value of that common argument. */ 2065169689Skan for (i = 0; i < PHI_NUM_ARGS (phi); i++) 2066169689Skan { 2067169689Skan tree arg = PHI_ARG_DEF (phi, i); 2068169689Skan 2069169689Skan if (arg == lhs) 2070169689Skan continue; 2071169689Skan else if (!val) 2072169689Skan val = arg; 2073169689Skan else if (!operand_equal_p (arg, val, 0)) 2074169689Skan break; 2075169689Skan } 2076169689Skan return (i == PHI_NUM_ARGS (phi) ? val : NULL); 2077169689Skan} 2078169689Skan 2079169689Skan/* Given a tree node T, which is either a PHI_NODE or MODIFY_EXPR, 2080169689Skan remove it from the IL. */ 2081169689Skan 2082169689Skanstatic void 2083169689Skanremove_stmt_or_phi (tree t) 2084169689Skan{ 2085169689Skan if (TREE_CODE (t) == PHI_NODE) 2086169689Skan remove_phi_node (t, NULL); 2087169689Skan else 2088169689Skan { 2089169689Skan block_stmt_iterator bsi = bsi_for_stmt (t); 2090169689Skan bsi_remove (&bsi, true); 2091169689Skan } 2092169689Skan} 2093169689Skan 2094169689Skan/* Given a tree node T, which is either a PHI_NODE or MODIFY_EXPR, 2095169689Skan return the "rhs" of the node, in the case of a non-degenerate 2096169689Skan PHI, NULL is returned. */ 2097169689Skan 2098169689Skanstatic tree 2099169689Skanget_rhs_or_phi_arg (tree t) 2100169689Skan{ 2101169689Skan if (TREE_CODE (t) == PHI_NODE) 2102169689Skan return degenerate_phi_result (t); 2103169689Skan else if (TREE_CODE (t) == MODIFY_EXPR) 2104169689Skan return TREE_OPERAND (t, 1); 2105169689Skan gcc_unreachable (); 2106169689Skan} 2107169689Skan 2108169689Skan 2109169689Skan/* Given a tree node T, which is either a PHI_NODE or a MODIFY_EXPR, 2110169689Skan return the "lhs" of the node. */ 2111169689Skan 2112169689Skanstatic tree 2113169689Skanget_lhs_or_phi_result (tree t) 2114169689Skan{ 2115169689Skan if (TREE_CODE (t) == PHI_NODE) 2116169689Skan return PHI_RESULT (t); 2117169689Skan else if (TREE_CODE (t) == MODIFY_EXPR) 2118169689Skan return TREE_OPERAND (t, 0); 2119169689Skan gcc_unreachable (); 2120169689Skan} 2121169689Skan 2122169689Skan/* Propagate RHS into all uses of LHS (when possible). 2123169689Skan 2124169689Skan RHS and LHS are derived from STMT, which is passed in solely so 2125169689Skan that we can remove it if propagation is successful. 2126169689Skan 2127169689Skan When propagating into a PHI node or into a statement which turns 2128169689Skan into a trivial copy or constant initialization, set the 2129169689Skan appropriate bit in INTERESTING_NAMEs so that we will visit those 2130169689Skan nodes as well in an effort to pick up secondary optimization 2131169689Skan opportunities. */ 2132169689Skan 2133169689Skanstatic void 2134169689Skanpropagate_rhs_into_lhs (tree stmt, tree lhs, tree rhs, bitmap interesting_names) 2135169689Skan{ 2136169689Skan /* First verify that propagation is valid and isn't going to move a 2137169689Skan loop variant variable outside its loop. */ 2138169689Skan if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) 2139169689Skan && (TREE_CODE (rhs) != SSA_NAME 2140169689Skan || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs)) 2141169689Skan && may_propagate_copy (lhs, rhs) 2142169689Skan && loop_depth_of_name (lhs) >= loop_depth_of_name (rhs)) 2143169689Skan { 2144169689Skan use_operand_p use_p; 2145169689Skan imm_use_iterator iter; 2146169689Skan tree use_stmt; 2147169689Skan bool all = true; 2148169689Skan 2149169689Skan /* Dump details. */ 2150169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2151169689Skan { 2152169689Skan fprintf (dump_file, " Replacing '"); 2153169689Skan print_generic_expr (dump_file, lhs, dump_flags); 2154169689Skan fprintf (dump_file, "' with %s '", 2155169689Skan (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable")); 2156169689Skan print_generic_expr (dump_file, rhs, dump_flags); 2157169689Skan fprintf (dump_file, "'\n"); 2158169689Skan } 2159169689Skan 2160169689Skan /* Walk over every use of LHS and try to replace the use with RHS. 2161169689Skan At this point the only reason why such a propagation would not 2162169689Skan be successful would be if the use occurs in an ASM_EXPR. */ 2163169689Skan FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) 2164169689Skan { 2165169689Skan 2166169689Skan /* It's not always safe to propagate into an ASM_EXPR. */ 2167169689Skan if (TREE_CODE (use_stmt) == ASM_EXPR 2168169689Skan && ! may_propagate_copy_into_asm (lhs)) 2169169689Skan { 2170169689Skan all = false; 2171169689Skan continue; 2172169689Skan } 2173169689Skan 2174169689Skan /* Dump details. */ 2175169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2176169689Skan { 2177169689Skan fprintf (dump_file, " Original statement:"); 2178169689Skan print_generic_expr (dump_file, use_stmt, dump_flags); 2179169689Skan fprintf (dump_file, "\n"); 2180169689Skan } 2181169689Skan 2182169689Skan /* Propagate the RHS into this use of the LHS. */ 2183169689Skan FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 2184169689Skan propagate_value (use_p, rhs); 2185169689Skan 2186169689Skan /* Special cases to avoid useless calls into the folding 2187169689Skan routines, operand scanning, etc. 2188169689Skan 2189169689Skan First, propagation into a PHI may cause the PHI to become 2190169689Skan a degenerate, so mark the PHI as interesting. No other 2191169689Skan actions are necessary. 2192169689Skan 2193169689Skan Second, if we're propagating a virtual operand and the 2194169689Skan propagation does not change the underlying _DECL node for 2195169689Skan the virtual operand, then no further actions are necessary. */ 2196169689Skan if (TREE_CODE (use_stmt) == PHI_NODE 2197169689Skan || (! is_gimple_reg (lhs) 2198169689Skan && TREE_CODE (rhs) == SSA_NAME 2199169689Skan && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs))) 2200169689Skan { 2201169689Skan /* Dump details. */ 2202169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2203169689Skan { 2204169689Skan fprintf (dump_file, " Updated statement:"); 2205169689Skan print_generic_expr (dump_file, use_stmt, dump_flags); 2206169689Skan fprintf (dump_file, "\n"); 2207169689Skan } 2208169689Skan 2209169689Skan /* Propagation into a PHI may expose new degenerate PHIs, 2210169689Skan so mark the result of the PHI as interesting. */ 2211169689Skan if (TREE_CODE (use_stmt) == PHI_NODE) 2212169689Skan { 2213169689Skan tree result = get_lhs_or_phi_result (use_stmt); 2214169689Skan bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result)); 2215169689Skan } 2216169689Skan continue; 2217169689Skan } 2218169689Skan 2219169689Skan /* From this point onward we are propagating into a 2220169689Skan real statement. Folding may (or may not) be possible, 2221169689Skan we may expose new operands, expose dead EH edges, 2222169689Skan etc. */ 2223169689Skan fold_stmt_inplace (use_stmt); 2224169689Skan 2225169689Skan /* Sometimes propagation can expose new operands to the 2226169689Skan renamer. Note this will call update_stmt at the 2227169689Skan appropriate time. */ 2228169689Skan mark_new_vars_to_rename (use_stmt); 2229169689Skan 2230169689Skan /* Dump details. */ 2231169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2232169689Skan { 2233169689Skan fprintf (dump_file, " Updated statement:"); 2234169689Skan print_generic_expr (dump_file, use_stmt, dump_flags); 2235169689Skan fprintf (dump_file, "\n"); 2236169689Skan } 2237169689Skan 2238169689Skan /* If we replaced a variable index with a constant, then 2239169689Skan we would need to update the invariant flag for ADDR_EXPRs. */ 2240169689Skan if (TREE_CODE (use_stmt) == MODIFY_EXPR 2241169689Skan && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == ADDR_EXPR) 2242169689Skan recompute_tree_invariant_for_addr_expr (TREE_OPERAND (use_stmt, 1)); 2243169689Skan 2244169689Skan /* If we cleaned up EH information from the statement, 2245169689Skan mark its containing block as needing EH cleanups. */ 2246169689Skan if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt)) 2247169689Skan { 2248169689Skan bitmap_set_bit (need_eh_cleanup, bb_for_stmt (use_stmt)->index); 2249169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2250169689Skan fprintf (dump_file, " Flagged to clear EH edges.\n"); 2251169689Skan } 2252169689Skan 2253169689Skan /* Propagation may expose new trivial copy/constant propagation 2254169689Skan opportunities. */ 2255169689Skan if (TREE_CODE (use_stmt) == MODIFY_EXPR 2256169689Skan && TREE_CODE (TREE_OPERAND (use_stmt, 0)) == SSA_NAME 2257169689Skan && (TREE_CODE (TREE_OPERAND (use_stmt, 1)) == SSA_NAME 2258169689Skan || is_gimple_min_invariant (TREE_OPERAND (use_stmt, 1)))) 2259169689Skan { 2260169689Skan tree result = get_lhs_or_phi_result (use_stmt); 2261169689Skan bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result)); 2262169689Skan } 2263169689Skan 2264169689Skan /* Propagation into these nodes may make certain edges in 2265169689Skan the CFG unexecutable. We want to identify them as PHI nodes 2266169689Skan at the destination of those unexecutable edges may become 2267169689Skan degenerates. */ 2268169689Skan else if (TREE_CODE (use_stmt) == COND_EXPR 2269169689Skan || TREE_CODE (use_stmt) == SWITCH_EXPR 2270169689Skan || TREE_CODE (use_stmt) == GOTO_EXPR) 2271169689Skan { 2272169689Skan tree val; 2273169689Skan 2274169689Skan if (TREE_CODE (use_stmt) == COND_EXPR) 2275169689Skan val = COND_EXPR_COND (use_stmt); 2276169689Skan else if (TREE_CODE (use_stmt) == SWITCH_EXPR) 2277169689Skan val = SWITCH_COND (use_stmt); 2278169689Skan else 2279169689Skan val = GOTO_DESTINATION (use_stmt); 2280169689Skan 2281169689Skan if (is_gimple_min_invariant (val)) 2282169689Skan { 2283169689Skan basic_block bb = bb_for_stmt (use_stmt); 2284169689Skan edge te = find_taken_edge (bb, val); 2285169689Skan edge_iterator ei; 2286169689Skan edge e; 2287169689Skan block_stmt_iterator bsi; 2288169689Skan 2289169689Skan /* Remove all outgoing edges except TE. */ 2290169689Skan for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));) 2291169689Skan { 2292169689Skan if (e != te) 2293169689Skan { 2294169689Skan tree phi; 2295169689Skan 2296169689Skan /* Mark all the PHI nodes at the destination of 2297169689Skan the unexecutable edge as interesting. */ 2298169689Skan for (phi = phi_nodes (e->dest); 2299169689Skan phi; 2300169689Skan phi = PHI_CHAIN (phi)) 2301169689Skan { 2302169689Skan tree result = PHI_RESULT (phi); 2303169689Skan int version = SSA_NAME_VERSION (result); 2304169689Skan 2305169689Skan bitmap_set_bit (interesting_names, version); 2306169689Skan } 2307169689Skan 2308169689Skan te->probability += e->probability; 2309169689Skan 2310169689Skan te->count += e->count; 2311169689Skan remove_edge (e); 2312169689Skan cfg_altered = 1; 2313169689Skan } 2314169689Skan else 2315169689Skan ei_next (&ei); 2316169689Skan } 2317169689Skan 2318169689Skan bsi = bsi_last (bb_for_stmt (use_stmt)); 2319169689Skan bsi_remove (&bsi, true); 2320169689Skan 2321169689Skan /* And fixup the flags on the single remaining edge. */ 2322169689Skan te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); 2323169689Skan te->flags &= ~EDGE_ABNORMAL; 2324169689Skan te->flags |= EDGE_FALLTHRU; 2325169689Skan if (te->probability > REG_BR_PROB_BASE) 2326169689Skan te->probability = REG_BR_PROB_BASE; 2327169689Skan } 2328169689Skan } 2329169689Skan } 2330169689Skan 2331169689Skan /* Ensure there is nothing else to do. */ 2332169689Skan gcc_assert (!all || has_zero_uses (lhs)); 2333169689Skan 2334169689Skan /* If we were able to propagate away all uses of LHS, then 2335169689Skan we can remove STMT. */ 2336169689Skan if (all) 2337169689Skan remove_stmt_or_phi (stmt); 2338169689Skan } 2339169689Skan} 2340169689Skan 2341169689Skan/* T is either a PHI node (potentially a degenerate PHI node) or 2342169689Skan a statement that is a trivial copy or constant initialization. 2343169689Skan 2344169689Skan Attempt to eliminate T by propagating its RHS into all uses of 2345169689Skan its LHS. This may in turn set new bits in INTERESTING_NAMES 2346169689Skan for nodes we want to revisit later. 2347169689Skan 2348169689Skan All exit paths should clear INTERESTING_NAMES for the result 2349169689Skan of T. */ 2350169689Skan 2351169689Skanstatic void 2352169689Skaneliminate_const_or_copy (tree t, bitmap interesting_names) 2353169689Skan{ 2354169689Skan tree lhs = get_lhs_or_phi_result (t); 2355169689Skan tree rhs; 2356169689Skan int version = SSA_NAME_VERSION (lhs); 2357169689Skan 2358169689Skan /* If the LHS of this statement or PHI has no uses, then we can 2359169689Skan just eliminate it. This can occur if, for example, the PHI 2360169689Skan was created by block duplication due to threading and its only 2361169689Skan use was in the conditional at the end of the block which was 2362169689Skan deleted. */ 2363169689Skan if (has_zero_uses (lhs)) 2364169689Skan { 2365169689Skan bitmap_clear_bit (interesting_names, version); 2366169689Skan remove_stmt_or_phi (t); 2367169689Skan return; 2368169689Skan } 2369169689Skan 2370169689Skan /* Get the RHS of the assignment or PHI node if the PHI is a 2371169689Skan degenerate. */ 2372169689Skan rhs = get_rhs_or_phi_arg (t); 2373169689Skan if (!rhs) 2374169689Skan { 2375169689Skan bitmap_clear_bit (interesting_names, version); 2376169689Skan return; 2377169689Skan } 2378169689Skan 2379169689Skan propagate_rhs_into_lhs (t, lhs, rhs, interesting_names); 2380169689Skan 2381169689Skan /* Note that T may well have been deleted by now, so do 2382169689Skan not access it, instead use the saved version # to clear 2383169689Skan T's entry in the worklist. */ 2384169689Skan bitmap_clear_bit (interesting_names, version); 2385169689Skan} 2386169689Skan 2387169689Skan/* The first phase in degenerate PHI elimination. 2388169689Skan 2389169689Skan Eliminate the degenerate PHIs in BB, then recurse on the 2390169689Skan dominator children of BB. */ 2391169689Skan 2392169689Skanstatic void 2393169689Skaneliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names) 2394169689Skan{ 2395169689Skan tree phi, next; 2396169689Skan basic_block son; 2397169689Skan 2398169689Skan for (phi = phi_nodes (bb); phi; phi = next) 2399169689Skan { 2400169689Skan next = PHI_CHAIN (phi); 2401169689Skan eliminate_const_or_copy (phi, interesting_names); 2402169689Skan } 2403169689Skan 2404169689Skan /* Recurse into the dominator children of BB. */ 2405169689Skan for (son = first_dom_son (CDI_DOMINATORS, bb); 2406169689Skan son; 2407169689Skan son = next_dom_son (CDI_DOMINATORS, son)) 2408169689Skan eliminate_degenerate_phis_1 (son, interesting_names); 2409169689Skan} 2410169689Skan 2411169689Skan 2412169689Skan/* A very simple pass to eliminate degenerate PHI nodes from the 2413169689Skan IL. This is meant to be fast enough to be able to be run several 2414169689Skan times in the optimization pipeline. 2415169689Skan 2416169689Skan Certain optimizations, particularly those which duplicate blocks 2417169689Skan or remove edges from the CFG can create or expose PHIs which are 2418169689Skan trivial copies or constant initializations. 2419169689Skan 2420169689Skan While we could pick up these optimizations in DOM or with the 2421169689Skan combination of copy-prop and CCP, those solutions are far too 2422169689Skan heavy-weight for our needs. 2423169689Skan 2424169689Skan This implementation has two phases so that we can efficiently 2425169689Skan eliminate the first order degenerate PHIs and second order 2426169689Skan degenerate PHIs. 2427169689Skan 2428169689Skan The first phase performs a dominator walk to identify and eliminate 2429169689Skan the vast majority of the degenerate PHIs. When a degenerate PHI 2430169689Skan is identified and eliminated any affected statements or PHIs 2431169689Skan are put on a worklist. 2432169689Skan 2433169689Skan The second phase eliminates degenerate PHIs and trivial copies 2434169689Skan or constant initializations using the worklist. This is how we 2435169689Skan pick up the secondary optimization opportunities with minimal 2436169689Skan cost. */ 2437169689Skan 2438169689Skanstatic unsigned int 2439169689Skaneliminate_degenerate_phis (void) 2440169689Skan{ 2441169689Skan bitmap interesting_names; 2442169689Skan bitmap interesting_names1; 2443169689Skan 2444169689Skan /* Bitmap of blocks which need EH information updated. We can not 2445169689Skan update it on-the-fly as doing so invalidates the dominator tree. */ 2446169689Skan need_eh_cleanup = BITMAP_ALLOC (NULL); 2447169689Skan 2448169689Skan /* INTERESTING_NAMES is effectively our worklist, indexed by 2449169689Skan SSA_NAME_VERSION. 2450169689Skan 2451169689Skan A set bit indicates that the statement or PHI node which 2452169689Skan defines the SSA_NAME should be (re)examined to determine if 2453169689Skan it has become a degenerate PHI or trivial const/copy propagation 2454169689Skan opportunity. 2455169689Skan 2456169689Skan Experiments have show we generally get better compilation 2457169689Skan time behavior with bitmaps rather than sbitmaps. */ 2458169689Skan interesting_names = BITMAP_ALLOC (NULL); 2459169689Skan interesting_names1 = BITMAP_ALLOC (NULL); 2460169689Skan 2461169689Skan /* First phase. Eliminate degenerate PHIs via a dominator 2462169689Skan walk of the CFG. 2463169689Skan 2464169689Skan Experiments have indicated that we generally get better 2465169689Skan compile-time behavior by visiting blocks in the first 2466169689Skan phase in dominator order. Presumably this is because walking 2467169689Skan in dominator order leaves fewer PHIs for later examination 2468169689Skan by the worklist phase. */ 2469169689Skan calculate_dominance_info (CDI_DOMINATORS); 2470169689Skan eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR, interesting_names); 2471169689Skan 2472169689Skan /* Second phase. Eliminate second order degenerate PHIs as well 2473169689Skan as trivial copies or constant initializations identified by 2474169689Skan the first phase or this phase. Basically we keep iterating 2475169689Skan until our set of INTERESTING_NAMEs is empty. */ 2476169689Skan while (!bitmap_empty_p (interesting_names)) 2477169689Skan { 2478169689Skan unsigned int i; 2479169689Skan bitmap_iterator bi; 2480169689Skan 2481169689Skan /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap 2482169689Skan changed during the loop. Copy it to another bitmap and 2483169689Skan use that. */ 2484169689Skan bitmap_copy (interesting_names1, interesting_names); 2485169689Skan 2486169689Skan EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi) 2487169689Skan { 2488169689Skan tree name = ssa_name (i); 2489169689Skan 2490169689Skan /* Ignore SSA_NAMEs that have been released because 2491169689Skan their defining statement was deleted (unreachable). */ 2492169689Skan if (name) 2493169689Skan eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)), 2494169689Skan interesting_names); 2495169689Skan } 2496169689Skan } 2497169689Skan 2498169689Skan /* Propagation of const and copies may make some EH edges dead. Purge 2499169689Skan such edges from the CFG as needed. */ 2500169689Skan if (!bitmap_empty_p (need_eh_cleanup)) 2501169689Skan { 2502169689Skan cfg_altered |= tree_purge_all_dead_eh_edges (need_eh_cleanup); 2503169689Skan BITMAP_FREE (need_eh_cleanup); 2504169689Skan } 2505169689Skan 2506169689Skan BITMAP_FREE (interesting_names); 2507169689Skan BITMAP_FREE (interesting_names1); 2508169689Skan if (cfg_altered) 2509169689Skan free_dominance_info (CDI_DOMINATORS); 2510169689Skan return 0; 2511169689Skan} 2512169689Skan 2513169689Skanstruct tree_opt_pass pass_phi_only_cprop = 2514169689Skan{ 2515169689Skan "phicprop", /* name */ 2516169689Skan gate_dominator, /* gate */ 2517169689Skan eliminate_degenerate_phis, /* execute */ 2518169689Skan NULL, /* sub */ 2519169689Skan NULL, /* next */ 2520169689Skan 0, /* static_pass_number */ 2521169689Skan TV_TREE_PHI_CPROP, /* tv_id */ 2522169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 2523169689Skan 0, /* properties_provided */ 2524169689Skan PROP_smt_usage, /* properties_destroyed */ 2525169689Skan 0, /* todo_flags_start */ 2526169689Skan TODO_cleanup_cfg | TODO_dump_func 2527169689Skan | TODO_ggc_collect | TODO_verify_ssa 2528169689Skan | TODO_verify_stmts | TODO_update_smt_usage 2529169689Skan | TODO_update_ssa, /* todo_flags_finish */ 2530169689Skan 0 /* letter */ 2531169689Skan}; 2532