1169689Skan/* Generic SSA value propagation engine. 2259563Spfg Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc. 3169689Skan Contributed by Diego Novillo <dnovillo@redhat.com> 4169689Skan 5169689Skan This file is part of GCC. 6169689Skan 7169689Skan GCC is free software; you can redistribute it and/or modify it 8169689Skan under the terms of the GNU General Public License as published by the 9169689Skan Free Software Foundation; either version 2, or (at your option) any 10169689Skan later version. 11169689Skan 12169689Skan GCC is distributed in the hope that it will be useful, but WITHOUT 13169689Skan ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14169689Skan FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15169689Skan for more details. 16169689Skan 17169689Skan You should have received a copy of the GNU General Public License 18169689Skan along with GCC; see the file COPYING. If not, write to the Free 19169689Skan Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan 02110-1301, USA. */ 21169689Skan 22169689Skan#include "config.h" 23169689Skan#include "system.h" 24169689Skan#include "coretypes.h" 25169689Skan#include "tm.h" 26169689Skan#include "tree.h" 27169689Skan#include "flags.h" 28169689Skan#include "rtl.h" 29169689Skan#include "tm_p.h" 30169689Skan#include "ggc.h" 31169689Skan#include "basic-block.h" 32169689Skan#include "output.h" 33169689Skan#include "expr.h" 34169689Skan#include "function.h" 35169689Skan#include "diagnostic.h" 36169689Skan#include "timevar.h" 37169689Skan#include "tree-dump.h" 38169689Skan#include "tree-flow.h" 39169689Skan#include "tree-pass.h" 40169689Skan#include "tree-ssa-propagate.h" 41169689Skan#include "langhooks.h" 42169689Skan#include "varray.h" 43169689Skan#include "vec.h" 44169689Skan 45169689Skan/* This file implements a generic value propagation engine based on 46169689Skan the same propagation used by the SSA-CCP algorithm [1]. 47169689Skan 48169689Skan Propagation is performed by simulating the execution of every 49169689Skan statement that produces the value being propagated. Simulation 50169689Skan proceeds as follows: 51169689Skan 52169689Skan 1- Initially, all edges of the CFG are marked not executable and 53169689Skan the CFG worklist is seeded with all the statements in the entry 54169689Skan basic block (block 0). 55169689Skan 56169689Skan 2- Every statement S is simulated with a call to the call-back 57169689Skan function SSA_PROP_VISIT_STMT. This evaluation may produce 3 58169689Skan results: 59169689Skan 60169689Skan SSA_PROP_NOT_INTERESTING: Statement S produces nothing of 61169689Skan interest and does not affect any of the work lists. 62169689Skan 63169689Skan SSA_PROP_VARYING: The value produced by S cannot be determined 64169689Skan at compile time. Further simulation of S is not required. 65169689Skan If S is a conditional jump, all the outgoing edges for the 66169689Skan block are considered executable and added to the work 67169689Skan list. 68169689Skan 69169689Skan SSA_PROP_INTERESTING: S produces a value that can be computed 70169689Skan at compile time. Its result can be propagated into the 71169689Skan statements that feed from S. Furthermore, if S is a 72169689Skan conditional jump, only the edge known to be taken is added 73169689Skan to the work list. Edges that are known not to execute are 74169689Skan never simulated. 75169689Skan 76169689Skan 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The 77169689Skan return value from SSA_PROP_VISIT_PHI has the same semantics as 78169689Skan described in #2. 79169689Skan 80169689Skan 4- Three work lists are kept. Statements are only added to these 81169689Skan lists if they produce one of SSA_PROP_INTERESTING or 82169689Skan SSA_PROP_VARYING. 83169689Skan 84169689Skan CFG_BLOCKS contains the list of blocks to be simulated. 85169689Skan Blocks are added to this list if their incoming edges are 86169689Skan found executable. 87169689Skan 88169689Skan VARYING_SSA_EDGES contains the list of statements that feed 89169689Skan from statements that produce an SSA_PROP_VARYING result. 90169689Skan These are simulated first to speed up processing. 91169689Skan 92169689Skan INTERESTING_SSA_EDGES contains the list of statements that 93169689Skan feed from statements that produce an SSA_PROP_INTERESTING 94169689Skan result. 95169689Skan 96169689Skan 5- Simulation terminates when all three work lists are drained. 97169689Skan 98169689Skan Before calling ssa_propagate, it is important to clear 99169689Skan DONT_SIMULATE_AGAIN for all the statements in the program that 100169689Skan should be simulated. This initialization allows an implementation 101169689Skan to specify which statements should never be simulated. 102169689Skan 103169689Skan It is also important to compute def-use information before calling 104169689Skan ssa_propagate. 105169689Skan 106169689Skan References: 107169689Skan 108169689Skan [1] Constant propagation with conditional branches, 109169689Skan Wegman and Zadeck, ACM TOPLAS 13(2):181-210. 110169689Skan 111169689Skan [2] Building an Optimizing Compiler, 112169689Skan Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9. 113169689Skan 114169689Skan [3] Advanced Compiler Design and Implementation, 115169689Skan Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */ 116169689Skan 117169689Skan/* Function pointers used to parameterize the propagation engine. */ 118169689Skanstatic ssa_prop_visit_stmt_fn ssa_prop_visit_stmt; 119169689Skanstatic ssa_prop_visit_phi_fn ssa_prop_visit_phi; 120169689Skan 121169689Skan/* Use the TREE_DEPRECATED bitflag to mark statements that have been 122169689Skan added to one of the SSA edges worklists. This flag is used to 123169689Skan avoid visiting statements unnecessarily when draining an SSA edge 124169689Skan worklist. If while simulating a basic block, we find a statement with 125169689Skan STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge 126169689Skan processing from visiting it again. */ 127169689Skan#define STMT_IN_SSA_EDGE_WORKLIST(T) TREE_DEPRECATED (T) 128169689Skan 129169689Skan/* A bitmap to keep track of executable blocks in the CFG. */ 130169689Skanstatic sbitmap executable_blocks; 131169689Skan 132169689Skan/* Array of control flow edges on the worklist. */ 133169689Skanstatic VEC(basic_block,heap) *cfg_blocks; 134169689Skan 135169689Skanstatic unsigned int cfg_blocks_num = 0; 136169689Skanstatic int cfg_blocks_tail; 137169689Skanstatic int cfg_blocks_head; 138169689Skan 139169689Skanstatic sbitmap bb_in_list; 140169689Skan 141169689Skan/* Worklist of SSA edges which will need reexamination as their 142169689Skan definition has changed. SSA edges are def-use edges in the SSA 143169689Skan web. For each D-U edge, we store the target statement or PHI node 144169689Skan U. */ 145169689Skanstatic GTY(()) VEC(tree,gc) *interesting_ssa_edges; 146169689Skan 147169689Skan/* Identical to INTERESTING_SSA_EDGES. For performance reasons, the 148169689Skan list of SSA edges is split into two. One contains all SSA edges 149169689Skan who need to be reexamined because their lattice value changed to 150169689Skan varying (this worklist), and the other contains all other SSA edges 151169689Skan to be reexamined (INTERESTING_SSA_EDGES). 152169689Skan 153169689Skan Since most values in the program are VARYING, the ideal situation 154169689Skan is to move them to that lattice value as quickly as possible. 155169689Skan Thus, it doesn't make sense to process any other type of lattice 156169689Skan value until all VARYING values are propagated fully, which is one 157169689Skan thing using the VARYING worklist achieves. In addition, if we 158169689Skan don't use a separate worklist for VARYING edges, we end up with 159169689Skan situations where lattice values move from 160169689Skan UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */ 161169689Skanstatic GTY(()) VEC(tree,gc) *varying_ssa_edges; 162169689Skan 163169689Skan 164169689Skan/* Return true if the block worklist empty. */ 165169689Skan 166169689Skanstatic inline bool 167169689Skancfg_blocks_empty_p (void) 168169689Skan{ 169169689Skan return (cfg_blocks_num == 0); 170169689Skan} 171169689Skan 172169689Skan 173169689Skan/* Add a basic block to the worklist. The block must not be already 174169689Skan in the worklist, and it must not be the ENTRY or EXIT block. */ 175169689Skan 176169689Skanstatic void 177169689Skancfg_blocks_add (basic_block bb) 178169689Skan{ 179259563Spfg bool head = false; 180259563Spfg 181169689Skan gcc_assert (bb != ENTRY_BLOCK_PTR && bb != EXIT_BLOCK_PTR); 182169689Skan gcc_assert (!TEST_BIT (bb_in_list, bb->index)); 183169689Skan 184169689Skan if (cfg_blocks_empty_p ()) 185169689Skan { 186169689Skan cfg_blocks_tail = cfg_blocks_head = 0; 187169689Skan cfg_blocks_num = 1; 188169689Skan } 189169689Skan else 190169689Skan { 191169689Skan cfg_blocks_num++; 192169689Skan if (cfg_blocks_num > VEC_length (basic_block, cfg_blocks)) 193169689Skan { 194169689Skan /* We have to grow the array now. Adjust to queue to occupy 195169689Skan the full space of the original array. We do not need to 196169689Skan initialize the newly allocated portion of the array 197169689Skan because we keep track of CFG_BLOCKS_HEAD and 198169689Skan CFG_BLOCKS_HEAD. */ 199169689Skan cfg_blocks_tail = VEC_length (basic_block, cfg_blocks); 200169689Skan cfg_blocks_head = 0; 201169689Skan VEC_safe_grow (basic_block, heap, cfg_blocks, 2 * cfg_blocks_tail); 202169689Skan } 203259563Spfg /* Minor optimization: we prefer to see blocks with more 204259563Spfg predecessors later, because there is more of a chance that 205259563Spfg the incoming edges will be executable. */ 206259563Spfg else if (EDGE_COUNT (bb->preds) 207259563Spfg >= EDGE_COUNT (VEC_index (basic_block, cfg_blocks, 208259563Spfg cfg_blocks_head)->preds)) 209169689Skan cfg_blocks_tail = ((cfg_blocks_tail + 1) 210169689Skan % VEC_length (basic_block, cfg_blocks)); 211259563Spfg else 212259563Spfg { 213259563Spfg if (cfg_blocks_head == 0) 214259563Spfg cfg_blocks_head = VEC_length (basic_block, cfg_blocks); 215259563Spfg --cfg_blocks_head; 216259563Spfg head = true; 217259563Spfg } 218169689Skan } 219169689Skan 220259563Spfg VEC_replace (basic_block, cfg_blocks, 221259563Spfg head ? cfg_blocks_head : cfg_blocks_tail, 222259563Spfg bb); 223169689Skan SET_BIT (bb_in_list, bb->index); 224169689Skan} 225169689Skan 226169689Skan 227169689Skan/* Remove a block from the worklist. */ 228169689Skan 229169689Skanstatic basic_block 230169689Skancfg_blocks_get (void) 231169689Skan{ 232169689Skan basic_block bb; 233169689Skan 234169689Skan bb = VEC_index (basic_block, cfg_blocks, cfg_blocks_head); 235169689Skan 236169689Skan gcc_assert (!cfg_blocks_empty_p ()); 237169689Skan gcc_assert (bb); 238169689Skan 239169689Skan cfg_blocks_head = ((cfg_blocks_head + 1) 240169689Skan % VEC_length (basic_block, cfg_blocks)); 241169689Skan --cfg_blocks_num; 242169689Skan RESET_BIT (bb_in_list, bb->index); 243169689Skan 244169689Skan return bb; 245169689Skan} 246169689Skan 247169689Skan 248169689Skan/* We have just defined a new value for VAR. If IS_VARYING is true, 249169689Skan add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add 250169689Skan them to INTERESTING_SSA_EDGES. */ 251169689Skan 252169689Skanstatic void 253169689Skanadd_ssa_edge (tree var, bool is_varying) 254169689Skan{ 255169689Skan imm_use_iterator iter; 256169689Skan use_operand_p use_p; 257169689Skan 258169689Skan FOR_EACH_IMM_USE_FAST (use_p, iter, var) 259169689Skan { 260169689Skan tree use_stmt = USE_STMT (use_p); 261169689Skan 262169689Skan if (!DONT_SIMULATE_AGAIN (use_stmt) 263169689Skan && !STMT_IN_SSA_EDGE_WORKLIST (use_stmt)) 264169689Skan { 265169689Skan STMT_IN_SSA_EDGE_WORKLIST (use_stmt) = 1; 266169689Skan if (is_varying) 267169689Skan VEC_safe_push (tree, gc, varying_ssa_edges, use_stmt); 268169689Skan else 269169689Skan VEC_safe_push (tree, gc, interesting_ssa_edges, use_stmt); 270169689Skan } 271169689Skan } 272169689Skan} 273169689Skan 274169689Skan 275169689Skan/* Add edge E to the control flow worklist. */ 276169689Skan 277169689Skanstatic void 278169689Skanadd_control_edge (edge e) 279169689Skan{ 280169689Skan basic_block bb = e->dest; 281169689Skan if (bb == EXIT_BLOCK_PTR) 282169689Skan return; 283169689Skan 284169689Skan /* If the edge had already been executed, skip it. */ 285169689Skan if (e->flags & EDGE_EXECUTABLE) 286169689Skan return; 287169689Skan 288169689Skan e->flags |= EDGE_EXECUTABLE; 289169689Skan 290169689Skan /* If the block is already in the list, we're done. */ 291169689Skan if (TEST_BIT (bb_in_list, bb->index)) 292169689Skan return; 293169689Skan 294169689Skan cfg_blocks_add (bb); 295169689Skan 296169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 297169689Skan fprintf (dump_file, "Adding Destination of edge (%d -> %d) to worklist\n\n", 298169689Skan e->src->index, e->dest->index); 299169689Skan} 300169689Skan 301169689Skan 302169689Skan/* Simulate the execution of STMT and update the work lists accordingly. */ 303169689Skan 304169689Skanstatic void 305169689Skansimulate_stmt (tree stmt) 306169689Skan{ 307169689Skan enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING; 308169689Skan edge taken_edge = NULL; 309169689Skan tree output_name = NULL_TREE; 310169689Skan 311169689Skan /* Don't bother visiting statements that are already 312169689Skan considered varying by the propagator. */ 313169689Skan if (DONT_SIMULATE_AGAIN (stmt)) 314169689Skan return; 315169689Skan 316169689Skan if (TREE_CODE (stmt) == PHI_NODE) 317169689Skan { 318169689Skan val = ssa_prop_visit_phi (stmt); 319169689Skan output_name = PHI_RESULT (stmt); 320169689Skan } 321169689Skan else 322169689Skan val = ssa_prop_visit_stmt (stmt, &taken_edge, &output_name); 323169689Skan 324169689Skan if (val == SSA_PROP_VARYING) 325169689Skan { 326169689Skan DONT_SIMULATE_AGAIN (stmt) = 1; 327169689Skan 328169689Skan /* If the statement produced a new varying value, add the SSA 329169689Skan edges coming out of OUTPUT_NAME. */ 330169689Skan if (output_name) 331169689Skan add_ssa_edge (output_name, true); 332169689Skan 333169689Skan /* If STMT transfers control out of its basic block, add 334169689Skan all outgoing edges to the work list. */ 335169689Skan if (stmt_ends_bb_p (stmt)) 336169689Skan { 337169689Skan edge e; 338169689Skan edge_iterator ei; 339169689Skan basic_block bb = bb_for_stmt (stmt); 340169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 341169689Skan add_control_edge (e); 342169689Skan } 343169689Skan } 344169689Skan else if (val == SSA_PROP_INTERESTING) 345169689Skan { 346169689Skan /* If the statement produced new value, add the SSA edges coming 347169689Skan out of OUTPUT_NAME. */ 348169689Skan if (output_name) 349169689Skan add_ssa_edge (output_name, false); 350169689Skan 351169689Skan /* If we know which edge is going to be taken out of this block, 352169689Skan add it to the CFG work list. */ 353169689Skan if (taken_edge) 354169689Skan add_control_edge (taken_edge); 355169689Skan } 356169689Skan} 357169689Skan 358169689Skan/* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to 359169689Skan drain. This pops statements off the given WORKLIST and processes 360169689Skan them until there are no more statements on WORKLIST. 361169689Skan We take a pointer to WORKLIST because it may be reallocated when an 362169689Skan SSA edge is added to it in simulate_stmt. */ 363169689Skan 364169689Skanstatic void 365169689Skanprocess_ssa_edge_worklist (VEC(tree,gc) **worklist) 366169689Skan{ 367169689Skan /* Drain the entire worklist. */ 368169689Skan while (VEC_length (tree, *worklist) > 0) 369169689Skan { 370169689Skan basic_block bb; 371169689Skan 372169689Skan /* Pull the statement to simulate off the worklist. */ 373169689Skan tree stmt = VEC_pop (tree, *worklist); 374169689Skan 375169689Skan /* If this statement was already visited by simulate_block, then 376169689Skan we don't need to visit it again here. */ 377169689Skan if (!STMT_IN_SSA_EDGE_WORKLIST (stmt)) 378169689Skan continue; 379169689Skan 380169689Skan /* STMT is no longer in a worklist. */ 381169689Skan STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0; 382169689Skan 383169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 384169689Skan { 385169689Skan fprintf (dump_file, "\nSimulating statement (from ssa_edges): "); 386169689Skan print_generic_stmt (dump_file, stmt, dump_flags); 387169689Skan } 388169689Skan 389169689Skan bb = bb_for_stmt (stmt); 390169689Skan 391169689Skan /* PHI nodes are always visited, regardless of whether or not 392169689Skan the destination block is executable. Otherwise, visit the 393169689Skan statement only if its block is marked executable. */ 394169689Skan if (TREE_CODE (stmt) == PHI_NODE 395169689Skan || TEST_BIT (executable_blocks, bb->index)) 396169689Skan simulate_stmt (stmt); 397169689Skan } 398169689Skan} 399169689Skan 400169689Skan 401169689Skan/* Simulate the execution of BLOCK. Evaluate the statement associated 402169689Skan with each variable reference inside the block. */ 403169689Skan 404169689Skanstatic void 405169689Skansimulate_block (basic_block block) 406169689Skan{ 407169689Skan tree phi; 408169689Skan 409169689Skan /* There is nothing to do for the exit block. */ 410169689Skan if (block == EXIT_BLOCK_PTR) 411169689Skan return; 412169689Skan 413169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 414169689Skan fprintf (dump_file, "\nSimulating block %d\n", block->index); 415169689Skan 416169689Skan /* Always simulate PHI nodes, even if we have simulated this block 417169689Skan before. */ 418169689Skan for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi)) 419169689Skan simulate_stmt (phi); 420169689Skan 421169689Skan /* If this is the first time we've simulated this block, then we 422169689Skan must simulate each of its statements. */ 423169689Skan if (!TEST_BIT (executable_blocks, block->index)) 424169689Skan { 425169689Skan block_stmt_iterator j; 426169689Skan unsigned int normal_edge_count; 427169689Skan edge e, normal_edge; 428169689Skan edge_iterator ei; 429169689Skan 430169689Skan /* Note that we have simulated this block. */ 431169689Skan SET_BIT (executable_blocks, block->index); 432169689Skan 433169689Skan for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j)) 434169689Skan { 435169689Skan tree stmt = bsi_stmt (j); 436169689Skan 437169689Skan /* If this statement is already in the worklist then 438169689Skan "cancel" it. The reevaluation implied by the worklist 439169689Skan entry will produce the same value we generate here and 440169689Skan thus reevaluating it again from the worklist is 441169689Skan pointless. */ 442169689Skan if (STMT_IN_SSA_EDGE_WORKLIST (stmt)) 443169689Skan STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0; 444169689Skan 445169689Skan simulate_stmt (stmt); 446169689Skan } 447169689Skan 448169689Skan /* We can not predict when abnormal edges will be executed, so 449169689Skan once a block is considered executable, we consider any 450169689Skan outgoing abnormal edges as executable. 451169689Skan 452169689Skan At the same time, if this block has only one successor that is 453169689Skan reached by non-abnormal edges, then add that successor to the 454169689Skan worklist. */ 455169689Skan normal_edge_count = 0; 456169689Skan normal_edge = NULL; 457169689Skan FOR_EACH_EDGE (e, ei, block->succs) 458169689Skan { 459169689Skan if (e->flags & EDGE_ABNORMAL) 460169689Skan add_control_edge (e); 461169689Skan else 462169689Skan { 463169689Skan normal_edge_count++; 464169689Skan normal_edge = e; 465169689Skan } 466169689Skan } 467169689Skan 468169689Skan if (normal_edge_count == 1) 469169689Skan add_control_edge (normal_edge); 470169689Skan } 471169689Skan} 472169689Skan 473169689Skan 474169689Skan/* Initialize local data structures and work lists. */ 475169689Skan 476169689Skanstatic void 477169689Skanssa_prop_init (void) 478169689Skan{ 479169689Skan edge e; 480169689Skan edge_iterator ei; 481169689Skan basic_block bb; 482169689Skan size_t i; 483169689Skan 484169689Skan /* Worklists of SSA edges. */ 485169689Skan interesting_ssa_edges = VEC_alloc (tree, gc, 20); 486169689Skan varying_ssa_edges = VEC_alloc (tree, gc, 20); 487169689Skan 488169689Skan executable_blocks = sbitmap_alloc (last_basic_block); 489169689Skan sbitmap_zero (executable_blocks); 490169689Skan 491169689Skan bb_in_list = sbitmap_alloc (last_basic_block); 492169689Skan sbitmap_zero (bb_in_list); 493169689Skan 494169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 495169689Skan dump_immediate_uses (dump_file); 496169689Skan 497169689Skan cfg_blocks = VEC_alloc (basic_block, heap, 20); 498169689Skan VEC_safe_grow (basic_block, heap, cfg_blocks, 20); 499169689Skan 500169689Skan /* Initialize the values for every SSA_NAME. */ 501169689Skan for (i = 1; i < num_ssa_names; i++) 502169689Skan if (ssa_name (i)) 503169689Skan SSA_NAME_VALUE (ssa_name (i)) = NULL_TREE; 504169689Skan 505169689Skan /* Initially assume that every edge in the CFG is not executable. 506169689Skan (including the edges coming out of ENTRY_BLOCK_PTR). */ 507169689Skan FOR_ALL_BB (bb) 508169689Skan { 509169689Skan block_stmt_iterator si; 510169689Skan 511169689Skan for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 512169689Skan STMT_IN_SSA_EDGE_WORKLIST (bsi_stmt (si)) = 0; 513169689Skan 514169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 515169689Skan e->flags &= ~EDGE_EXECUTABLE; 516169689Skan } 517169689Skan 518169689Skan /* Seed the algorithm by adding the successors of the entry block to the 519169689Skan edge worklist. */ 520169689Skan FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 521169689Skan add_control_edge (e); 522169689Skan} 523169689Skan 524169689Skan 525169689Skan/* Free allocated storage. */ 526169689Skan 527169689Skanstatic void 528169689Skanssa_prop_fini (void) 529169689Skan{ 530169689Skan VEC_free (tree, gc, interesting_ssa_edges); 531169689Skan VEC_free (tree, gc, varying_ssa_edges); 532169689Skan VEC_free (basic_block, heap, cfg_blocks); 533169689Skan cfg_blocks = NULL; 534169689Skan sbitmap_free (bb_in_list); 535169689Skan sbitmap_free (executable_blocks); 536169689Skan} 537169689Skan 538169689Skan 539169689Skan/* Get the main expression from statement STMT. */ 540169689Skan 541169689Skantree 542169689Skanget_rhs (tree stmt) 543169689Skan{ 544169689Skan enum tree_code code = TREE_CODE (stmt); 545169689Skan 546169689Skan switch (code) 547169689Skan { 548169689Skan case RETURN_EXPR: 549169689Skan stmt = TREE_OPERAND (stmt, 0); 550169689Skan if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR) 551169689Skan return stmt; 552169689Skan /* FALLTHRU */ 553169689Skan 554169689Skan case MODIFY_EXPR: 555169689Skan stmt = TREE_OPERAND (stmt, 1); 556169689Skan if (TREE_CODE (stmt) == WITH_SIZE_EXPR) 557169689Skan return TREE_OPERAND (stmt, 0); 558169689Skan else 559169689Skan return stmt; 560169689Skan 561169689Skan case COND_EXPR: 562169689Skan return COND_EXPR_COND (stmt); 563169689Skan case SWITCH_EXPR: 564169689Skan return SWITCH_COND (stmt); 565169689Skan case GOTO_EXPR: 566169689Skan return GOTO_DESTINATION (stmt); 567169689Skan case LABEL_EXPR: 568169689Skan return LABEL_EXPR_LABEL (stmt); 569169689Skan 570169689Skan default: 571169689Skan return stmt; 572169689Skan } 573169689Skan} 574169689Skan 575169689Skan 576169689Skan/* Set the main expression of *STMT_P to EXPR. If EXPR is not a valid 577169689Skan GIMPLE expression no changes are done and the function returns 578169689Skan false. */ 579169689Skan 580169689Skanbool 581169689Skanset_rhs (tree *stmt_p, tree expr) 582169689Skan{ 583169689Skan tree stmt = *stmt_p, op; 584169689Skan enum tree_code code = TREE_CODE (expr); 585169689Skan stmt_ann_t ann; 586169689Skan tree var; 587169689Skan ssa_op_iter iter; 588169689Skan 589169689Skan /* Verify the constant folded result is valid gimple. */ 590169689Skan if (TREE_CODE_CLASS (code) == tcc_binary) 591169689Skan { 592169689Skan if (!is_gimple_val (TREE_OPERAND (expr, 0)) 593169689Skan || !is_gimple_val (TREE_OPERAND (expr, 1))) 594169689Skan return false; 595169689Skan } 596169689Skan else if (TREE_CODE_CLASS (code) == tcc_unary) 597169689Skan { 598169689Skan if (!is_gimple_val (TREE_OPERAND (expr, 0))) 599169689Skan return false; 600169689Skan } 601169689Skan else if (code == ADDR_EXPR) 602169689Skan { 603169689Skan if (TREE_CODE (TREE_OPERAND (expr, 0)) == ARRAY_REF 604169689Skan && !is_gimple_val (TREE_OPERAND (TREE_OPERAND (expr, 0), 1))) 605169689Skan return false; 606169689Skan } 607169689Skan else if (code == COMPOUND_EXPR 608169689Skan || code == MODIFY_EXPR) 609169689Skan return false; 610169689Skan 611169689Skan if (EXPR_HAS_LOCATION (stmt) 612169689Skan && EXPR_P (expr) 613169689Skan && ! EXPR_HAS_LOCATION (expr) 614169689Skan && TREE_SIDE_EFFECTS (expr) 615169689Skan && TREE_CODE (expr) != LABEL_EXPR) 616169689Skan SET_EXPR_LOCATION (expr, EXPR_LOCATION (stmt)); 617169689Skan 618169689Skan switch (TREE_CODE (stmt)) 619169689Skan { 620169689Skan case RETURN_EXPR: 621169689Skan op = TREE_OPERAND (stmt, 0); 622169689Skan if (TREE_CODE (op) != MODIFY_EXPR) 623169689Skan { 624169689Skan TREE_OPERAND (stmt, 0) = expr; 625169689Skan break; 626169689Skan } 627169689Skan stmt = op; 628169689Skan /* FALLTHRU */ 629169689Skan 630169689Skan case MODIFY_EXPR: 631169689Skan op = TREE_OPERAND (stmt, 1); 632169689Skan if (TREE_CODE (op) == WITH_SIZE_EXPR) 633169689Skan stmt = op; 634169689Skan TREE_OPERAND (stmt, 1) = expr; 635169689Skan break; 636169689Skan 637169689Skan case COND_EXPR: 638169689Skan if (!is_gimple_condexpr (expr)) 639169689Skan return false; 640169689Skan COND_EXPR_COND (stmt) = expr; 641169689Skan break; 642169689Skan case SWITCH_EXPR: 643169689Skan SWITCH_COND (stmt) = expr; 644169689Skan break; 645169689Skan case GOTO_EXPR: 646169689Skan GOTO_DESTINATION (stmt) = expr; 647169689Skan break; 648169689Skan case LABEL_EXPR: 649169689Skan LABEL_EXPR_LABEL (stmt) = expr; 650169689Skan break; 651169689Skan 652169689Skan default: 653169689Skan /* Replace the whole statement with EXPR. If EXPR has no side 654169689Skan effects, then replace *STMT_P with an empty statement. */ 655169689Skan ann = stmt_ann (stmt); 656169689Skan *stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt (); 657169689Skan (*stmt_p)->common.ann = (tree_ann_t) ann; 658169689Skan 659169689Skan if (in_ssa_p 660169689Skan && TREE_SIDE_EFFECTS (expr)) 661169689Skan { 662169689Skan /* Fix all the SSA_NAMEs created by *STMT_P to point to its new 663169689Skan replacement. */ 664169689Skan FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_DEFS) 665169689Skan { 666169689Skan if (TREE_CODE (var) == SSA_NAME) 667169689Skan SSA_NAME_DEF_STMT (var) = *stmt_p; 668169689Skan } 669169689Skan } 670169689Skan break; 671169689Skan } 672169689Skan 673169689Skan return true; 674169689Skan} 675169689Skan 676169689Skan 677169689Skan/* Entry point to the propagation engine. 678169689Skan 679169689Skan VISIT_STMT is called for every statement visited. 680169689Skan VISIT_PHI is called for every PHI node visited. */ 681169689Skan 682169689Skanvoid 683169689Skanssa_propagate (ssa_prop_visit_stmt_fn visit_stmt, 684169689Skan ssa_prop_visit_phi_fn visit_phi) 685169689Skan{ 686169689Skan ssa_prop_visit_stmt = visit_stmt; 687169689Skan ssa_prop_visit_phi = visit_phi; 688169689Skan 689169689Skan ssa_prop_init (); 690169689Skan 691169689Skan /* Iterate until the worklists are empty. */ 692169689Skan while (!cfg_blocks_empty_p () 693169689Skan || VEC_length (tree, interesting_ssa_edges) > 0 694169689Skan || VEC_length (tree, varying_ssa_edges) > 0) 695169689Skan { 696169689Skan if (!cfg_blocks_empty_p ()) 697169689Skan { 698169689Skan /* Pull the next block to simulate off the worklist. */ 699169689Skan basic_block dest_block = cfg_blocks_get (); 700169689Skan simulate_block (dest_block); 701169689Skan } 702169689Skan 703169689Skan /* In order to move things to varying as quickly as 704169689Skan possible,process the VARYING_SSA_EDGES worklist first. */ 705169689Skan process_ssa_edge_worklist (&varying_ssa_edges); 706169689Skan 707169689Skan /* Now process the INTERESTING_SSA_EDGES worklist. */ 708169689Skan process_ssa_edge_worklist (&interesting_ssa_edges); 709169689Skan } 710169689Skan 711169689Skan ssa_prop_fini (); 712169689Skan} 713169689Skan 714169689Skan 715169689Skan/* Return the first V_MAY_DEF or V_MUST_DEF operand for STMT. */ 716169689Skan 717169689Skantree 718169689Skanfirst_vdef (tree stmt) 719169689Skan{ 720169689Skan ssa_op_iter iter; 721169689Skan tree op; 722169689Skan 723169689Skan /* Simply return the first operand we arrive at. */ 724169689Skan FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS) 725169689Skan return (op); 726169689Skan 727169689Skan gcc_unreachable (); 728169689Skan} 729169689Skan 730169689Skan 731169689Skan/* Return true if STMT is of the form 'LHS = mem_ref', where 'mem_ref' 732169689Skan is a non-volatile pointer dereference, a structure reference or a 733169689Skan reference to a single _DECL. Ignore volatile memory references 734169689Skan because they are not interesting for the optimizers. */ 735169689Skan 736169689Skanbool 737169689Skanstmt_makes_single_load (tree stmt) 738169689Skan{ 739169689Skan tree rhs; 740169689Skan 741169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR) 742169689Skan return false; 743169689Skan 744169689Skan if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VUSE)) 745169689Skan return false; 746169689Skan 747169689Skan rhs = TREE_OPERAND (stmt, 1); 748169689Skan STRIP_NOPS (rhs); 749169689Skan 750169689Skan return (!TREE_THIS_VOLATILE (rhs) 751169689Skan && (DECL_P (rhs) 752169689Skan || REFERENCE_CLASS_P (rhs))); 753169689Skan} 754169689Skan 755169689Skan 756169689Skan/* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref' 757169689Skan is a non-volatile pointer dereference, a structure reference or a 758169689Skan reference to a single _DECL. Ignore volatile memory references 759169689Skan because they are not interesting for the optimizers. */ 760169689Skan 761169689Skanbool 762169689Skanstmt_makes_single_store (tree stmt) 763169689Skan{ 764169689Skan tree lhs; 765169689Skan 766169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR) 767169689Skan return false; 768169689Skan 769169689Skan if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF)) 770169689Skan return false; 771169689Skan 772169689Skan lhs = TREE_OPERAND (stmt, 0); 773169689Skan STRIP_NOPS (lhs); 774169689Skan 775169689Skan return (!TREE_THIS_VOLATILE (lhs) 776169689Skan && (DECL_P (lhs) 777169689Skan || REFERENCE_CLASS_P (lhs))); 778169689Skan} 779169689Skan 780169689Skan 781169689Skan/* If STMT makes a single memory load and all the virtual use operands 782169689Skan have the same value in array VALUES, return it. Otherwise, return 783169689Skan NULL. */ 784169689Skan 785169689Skanprop_value_t * 786169689Skanget_value_loaded_by (tree stmt, prop_value_t *values) 787169689Skan{ 788169689Skan ssa_op_iter i; 789169689Skan tree vuse; 790169689Skan prop_value_t *prev_val = NULL; 791169689Skan prop_value_t *val = NULL; 792169689Skan 793169689Skan FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES) 794169689Skan { 795169689Skan val = &values[SSA_NAME_VERSION (vuse)]; 796169689Skan if (prev_val && prev_val->value != val->value) 797169689Skan return NULL; 798169689Skan prev_val = val; 799169689Skan } 800169689Skan 801169689Skan return val; 802169689Skan} 803169689Skan 804169689Skan 805169689Skan/* Propagation statistics. */ 806169689Skanstruct prop_stats_d 807169689Skan{ 808169689Skan long num_const_prop; 809169689Skan long num_copy_prop; 810169689Skan long num_pred_folded; 811169689Skan}; 812169689Skan 813169689Skanstatic struct prop_stats_d prop_stats; 814169689Skan 815169689Skan/* Replace USE references in statement STMT with the values stored in 816169689Skan PROP_VALUE. Return true if at least one reference was replaced. If 817169689Skan REPLACED_ADDRESSES_P is given, it will be set to true if an address 818169689Skan constant was replaced. */ 819169689Skan 820169689Skanbool 821169689Skanreplace_uses_in (tree stmt, bool *replaced_addresses_p, 822169689Skan prop_value_t *prop_value) 823169689Skan{ 824169689Skan bool replaced = false; 825169689Skan use_operand_p use; 826169689Skan ssa_op_iter iter; 827169689Skan 828169689Skan FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE) 829169689Skan { 830169689Skan tree tuse = USE_FROM_PTR (use); 831169689Skan tree val = prop_value[SSA_NAME_VERSION (tuse)].value; 832169689Skan 833169689Skan if (val == tuse || val == NULL_TREE) 834169689Skan continue; 835169689Skan 836169689Skan if (TREE_CODE (stmt) == ASM_EXPR 837169689Skan && !may_propagate_copy_into_asm (tuse)) 838169689Skan continue; 839169689Skan 840169689Skan if (!may_propagate_copy (tuse, val)) 841169689Skan continue; 842169689Skan 843169689Skan if (TREE_CODE (val) != SSA_NAME) 844169689Skan prop_stats.num_const_prop++; 845169689Skan else 846169689Skan prop_stats.num_copy_prop++; 847169689Skan 848169689Skan propagate_value (use, val); 849169689Skan 850169689Skan replaced = true; 851169689Skan if (POINTER_TYPE_P (TREE_TYPE (tuse)) && replaced_addresses_p) 852169689Skan *replaced_addresses_p = true; 853169689Skan } 854169689Skan 855169689Skan return replaced; 856169689Skan} 857169689Skan 858169689Skan 859169689Skan/* Replace the VUSE references in statement STMT with the values 860169689Skan stored in PROP_VALUE. Return true if a reference was replaced. If 861169689Skan REPLACED_ADDRESSES_P is given, it will be set to true if an address 862169689Skan constant was replaced. 863169689Skan 864169689Skan Replacing VUSE operands is slightly more complex than replacing 865169689Skan regular USEs. We are only interested in two types of replacements 866169689Skan here: 867169689Skan 868169689Skan 1- If the value to be replaced is a constant or an SSA name for a 869169689Skan GIMPLE register, then we are making a copy/constant propagation 870169689Skan from a memory store. For instance, 871169689Skan 872169689Skan # a_3 = V_MAY_DEF <a_2> 873169689Skan a.b = x_1; 874169689Skan ... 875169689Skan # VUSE <a_3> 876169689Skan y_4 = a.b; 877169689Skan 878169689Skan This replacement is only possible iff STMT is an assignment 879169689Skan whose RHS is identical to the LHS of the statement that created 880169689Skan the VUSE(s) that we are replacing. Otherwise, we may do the 881169689Skan wrong replacement: 882169689Skan 883169689Skan # a_3 = V_MAY_DEF <a_2> 884169689Skan # b_5 = V_MAY_DEF <b_4> 885169689Skan *p = 10; 886169689Skan ... 887169689Skan # VUSE <b_5> 888169689Skan x_8 = b; 889169689Skan 890169689Skan Even though 'b_5' acquires the value '10' during propagation, 891169689Skan there is no way for the propagator to tell whether the 892169689Skan replacement is correct in every reached use, because values are 893169689Skan computed at definition sites. Therefore, when doing final 894169689Skan substitution of propagated values, we have to check each use 895169689Skan site. Since the RHS of STMT ('b') is different from the LHS of 896169689Skan the originating statement ('*p'), we cannot replace 'b' with 897169689Skan '10'. 898169689Skan 899169689Skan Similarly, when merging values from PHI node arguments, 900169689Skan propagators need to take care not to merge the same values 901169689Skan stored in different locations: 902169689Skan 903169689Skan if (...) 904169689Skan # a_3 = V_MAY_DEF <a_2> 905169689Skan a.b = 3; 906169689Skan else 907169689Skan # a_4 = V_MAY_DEF <a_2> 908169689Skan a.c = 3; 909169689Skan # a_5 = PHI <a_3, a_4> 910169689Skan 911169689Skan It would be wrong to propagate '3' into 'a_5' because that 912169689Skan operation merges two stores to different memory locations. 913169689Skan 914169689Skan 915169689Skan 2- If the value to be replaced is an SSA name for a virtual 916169689Skan register, then we simply replace each VUSE operand with its 917169689Skan value from PROP_VALUE. This is the same replacement done by 918169689Skan replace_uses_in. */ 919169689Skan 920169689Skanstatic bool 921169689Skanreplace_vuses_in (tree stmt, bool *replaced_addresses_p, 922169689Skan prop_value_t *prop_value) 923169689Skan{ 924169689Skan bool replaced = false; 925169689Skan ssa_op_iter iter; 926169689Skan use_operand_p vuse; 927169689Skan 928169689Skan if (stmt_makes_single_load (stmt)) 929169689Skan { 930169689Skan /* If STMT is an assignment whose RHS is a single memory load, 931169689Skan see if we are trying to propagate a constant or a GIMPLE 932169689Skan register (case #1 above). */ 933169689Skan prop_value_t *val = get_value_loaded_by (stmt, prop_value); 934169689Skan tree rhs = TREE_OPERAND (stmt, 1); 935169689Skan 936169689Skan if (val 937169689Skan && val->value 938169689Skan && (is_gimple_reg (val->value) 939169689Skan || is_gimple_min_invariant (val->value)) 940169689Skan && simple_cst_equal (rhs, val->mem_ref) == 1) 941169689Skan 942169689Skan { 943169689Skan /* If we are replacing a constant address, inform our 944169689Skan caller. */ 945169689Skan if (TREE_CODE (val->value) != SSA_NAME 946169689Skan && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))) 947169689Skan && replaced_addresses_p) 948169689Skan *replaced_addresses_p = true; 949169689Skan 950169689Skan /* We can only perform the substitution if the load is done 951169689Skan from the same memory location as the original store. 952169689Skan Since we already know that there are no intervening 953169689Skan stores between DEF_STMT and STMT, we only need to check 954169689Skan that the RHS of STMT is the same as the memory reference 955169689Skan propagated together with the value. */ 956169689Skan TREE_OPERAND (stmt, 1) = val->value; 957169689Skan 958169689Skan if (TREE_CODE (val->value) != SSA_NAME) 959169689Skan prop_stats.num_const_prop++; 960169689Skan else 961169689Skan prop_stats.num_copy_prop++; 962169689Skan 963169689Skan /* Since we have replaced the whole RHS of STMT, there 964169689Skan is no point in checking the other VUSEs, as they will 965169689Skan all have the same value. */ 966169689Skan return true; 967169689Skan } 968169689Skan } 969169689Skan 970169689Skan /* Otherwise, the values for every VUSE operand must be other 971169689Skan SSA_NAMEs that can be propagated into STMT. */ 972169689Skan FOR_EACH_SSA_USE_OPERAND (vuse, stmt, iter, SSA_OP_VIRTUAL_USES) 973169689Skan { 974169689Skan tree var = USE_FROM_PTR (vuse); 975169689Skan tree val = prop_value[SSA_NAME_VERSION (var)].value; 976169689Skan 977169689Skan if (val == NULL_TREE || var == val) 978169689Skan continue; 979169689Skan 980169689Skan /* Constants and copies propagated between real and virtual 981169689Skan operands are only possible in the cases handled above. They 982169689Skan should be ignored in any other context. */ 983169689Skan if (is_gimple_min_invariant (val) || is_gimple_reg (val)) 984169689Skan continue; 985169689Skan 986169689Skan propagate_value (vuse, val); 987169689Skan prop_stats.num_copy_prop++; 988169689Skan replaced = true; 989169689Skan } 990169689Skan 991169689Skan return replaced; 992169689Skan} 993169689Skan 994169689Skan 995169689Skan/* Replace propagated values into all the arguments for PHI using the 996169689Skan values from PROP_VALUE. */ 997169689Skan 998169689Skanstatic void 999169689Skanreplace_phi_args_in (tree phi, prop_value_t *prop_value) 1000169689Skan{ 1001169689Skan int i; 1002169689Skan bool replaced = false; 1003169689Skan tree prev_phi = NULL; 1004169689Skan 1005169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1006169689Skan prev_phi = unshare_expr (phi); 1007169689Skan 1008169689Skan for (i = 0; i < PHI_NUM_ARGS (phi); i++) 1009169689Skan { 1010169689Skan tree arg = PHI_ARG_DEF (phi, i); 1011169689Skan 1012169689Skan if (TREE_CODE (arg) == SSA_NAME) 1013169689Skan { 1014169689Skan tree val = prop_value[SSA_NAME_VERSION (arg)].value; 1015169689Skan 1016169689Skan if (val && val != arg && may_propagate_copy (arg, val)) 1017169689Skan { 1018169689Skan if (TREE_CODE (val) != SSA_NAME) 1019169689Skan prop_stats.num_const_prop++; 1020169689Skan else 1021169689Skan prop_stats.num_copy_prop++; 1022169689Skan 1023169689Skan propagate_value (PHI_ARG_DEF_PTR (phi, i), val); 1024169689Skan replaced = true; 1025169689Skan 1026169689Skan /* If we propagated a copy and this argument flows 1027169689Skan through an abnormal edge, update the replacement 1028169689Skan accordingly. */ 1029169689Skan if (TREE_CODE (val) == SSA_NAME 1030169689Skan && PHI_ARG_EDGE (phi, i)->flags & EDGE_ABNORMAL) 1031169689Skan SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1; 1032169689Skan } 1033169689Skan } 1034169689Skan } 1035169689Skan 1036169689Skan if (replaced && dump_file && (dump_flags & TDF_DETAILS)) 1037169689Skan { 1038169689Skan fprintf (dump_file, "Folded PHI node: "); 1039169689Skan print_generic_stmt (dump_file, prev_phi, TDF_SLIM); 1040169689Skan fprintf (dump_file, " into: "); 1041169689Skan print_generic_stmt (dump_file, phi, TDF_SLIM); 1042169689Skan fprintf (dump_file, "\n"); 1043169689Skan } 1044169689Skan} 1045169689Skan 1046169689Skan 1047169689Skan/* If STMT has a predicate whose value can be computed using the value 1048169689Skan range information computed by VRP, compute its value and return true. 1049169689Skan Otherwise, return false. */ 1050169689Skan 1051169689Skanstatic bool 1052169689Skanfold_predicate_in (tree stmt) 1053169689Skan{ 1054169689Skan tree *pred_p = NULL; 1055169689Skan bool modify_expr_p = false; 1056169689Skan tree val; 1057169689Skan 1058169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR 1059169689Skan && COMPARISON_CLASS_P (TREE_OPERAND (stmt, 1))) 1060169689Skan { 1061169689Skan modify_expr_p = true; 1062169689Skan pred_p = &TREE_OPERAND (stmt, 1); 1063169689Skan } 1064169689Skan else if (TREE_CODE (stmt) == COND_EXPR) 1065169689Skan pred_p = &COND_EXPR_COND (stmt); 1066169689Skan else 1067169689Skan return false; 1068169689Skan 1069169689Skan val = vrp_evaluate_conditional (*pred_p, stmt); 1070169689Skan if (val) 1071169689Skan { 1072169689Skan if (modify_expr_p) 1073169689Skan val = fold_convert (TREE_TYPE (*pred_p), val); 1074169689Skan 1075169689Skan if (dump_file) 1076169689Skan { 1077169689Skan fprintf (dump_file, "Folding predicate "); 1078169689Skan print_generic_expr (dump_file, *pred_p, 0); 1079169689Skan fprintf (dump_file, " to "); 1080169689Skan print_generic_expr (dump_file, val, 0); 1081169689Skan fprintf (dump_file, "\n"); 1082169689Skan } 1083169689Skan 1084169689Skan prop_stats.num_pred_folded++; 1085169689Skan *pred_p = val; 1086169689Skan return true; 1087169689Skan } 1088169689Skan 1089169689Skan return false; 1090169689Skan} 1091169689Skan 1092169689Skan 1093169689Skan/* Perform final substitution and folding of propagated values. 1094169689Skan 1095169689Skan PROP_VALUE[I] contains the single value that should be substituted 1096169689Skan at every use of SSA name N_I. If PROP_VALUE is NULL, no values are 1097169689Skan substituted. 1098169689Skan 1099169689Skan If USE_RANGES_P is true, statements that contain predicate 1100169689Skan expressions are evaluated with a call to vrp_evaluate_conditional. 1101169689Skan This will only give meaningful results when called from tree-vrp.c 1102169689Skan (the information used by vrp_evaluate_conditional is built by the 1103169689Skan VRP pass). */ 1104169689Skan 1105169689Skanvoid 1106169689Skansubstitute_and_fold (prop_value_t *prop_value, bool use_ranges_p) 1107169689Skan{ 1108169689Skan basic_block bb; 1109169689Skan 1110169689Skan if (prop_value == NULL && !use_ranges_p) 1111169689Skan return; 1112169689Skan 1113169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1114169689Skan fprintf (dump_file, "\nSubstituing values and folding statements\n\n"); 1115169689Skan 1116169689Skan memset (&prop_stats, 0, sizeof (prop_stats)); 1117169689Skan 1118169689Skan /* Substitute values in every statement of every basic block. */ 1119169689Skan FOR_EACH_BB (bb) 1120169689Skan { 1121169689Skan block_stmt_iterator i; 1122169689Skan tree phi; 1123169689Skan 1124169689Skan /* Propagate known values into PHI nodes. */ 1125169689Skan if (prop_value) 1126169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1127169689Skan replace_phi_args_in (phi, prop_value); 1128169689Skan 1129169689Skan for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i)) 1130169689Skan { 1131169689Skan bool replaced_address, did_replace; 1132169689Skan tree prev_stmt = NULL; 1133169689Skan tree stmt = bsi_stmt (i); 1134169689Skan 1135169689Skan /* Ignore ASSERT_EXPRs. They are used by VRP to generate 1136169689Skan range information for names and they are discarded 1137169689Skan afterwards. */ 1138169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR 1139169689Skan && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR) 1140169689Skan continue; 1141169689Skan 1142169689Skan /* Replace the statement with its folded version and mark it 1143169689Skan folded. */ 1144169689Skan did_replace = false; 1145169689Skan replaced_address = false; 1146169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1147169689Skan prev_stmt = unshare_expr (stmt); 1148169689Skan 1149169689Skan /* If we have range information, see if we can fold 1150169689Skan predicate expressions. */ 1151169689Skan if (use_ranges_p) 1152169689Skan did_replace = fold_predicate_in (stmt); 1153169689Skan 1154169689Skan if (prop_value) 1155169689Skan { 1156169689Skan /* Only replace real uses if we couldn't fold the 1157169689Skan statement using value range information (value range 1158169689Skan information is not collected on virtuals, so we only 1159169689Skan need to check this for real uses). */ 1160169689Skan if (!did_replace) 1161169689Skan did_replace |= replace_uses_in (stmt, &replaced_address, 1162169689Skan prop_value); 1163169689Skan 1164169689Skan did_replace |= replace_vuses_in (stmt, &replaced_address, 1165169689Skan prop_value); 1166169689Skan } 1167169689Skan 1168169689Skan /* If we made a replacement, fold and cleanup the statement. */ 1169169689Skan if (did_replace) 1170169689Skan { 1171169689Skan tree old_stmt = stmt; 1172169689Skan tree rhs; 1173169689Skan 1174169689Skan fold_stmt (bsi_stmt_ptr (i)); 1175169689Skan stmt = bsi_stmt (i); 1176169689Skan 1177169689Skan /* If we folded a builtin function, we'll likely 1178169689Skan need to rename VDEFs. */ 1179169689Skan mark_new_vars_to_rename (stmt); 1180169689Skan 1181169689Skan /* If we cleaned up EH information from the statement, 1182169689Skan remove EH edges. */ 1183169689Skan if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) 1184169689Skan tree_purge_dead_eh_edges (bb); 1185169689Skan 1186169689Skan rhs = get_rhs (stmt); 1187169689Skan if (TREE_CODE (rhs) == ADDR_EXPR) 1188169689Skan recompute_tree_invariant_for_addr_expr (rhs); 1189169689Skan 1190169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1191169689Skan { 1192169689Skan fprintf (dump_file, "Folded statement: "); 1193169689Skan print_generic_stmt (dump_file, prev_stmt, TDF_SLIM); 1194169689Skan fprintf (dump_file, " into: "); 1195169689Skan print_generic_stmt (dump_file, stmt, TDF_SLIM); 1196169689Skan fprintf (dump_file, "\n"); 1197169689Skan } 1198169689Skan } 1199169689Skan 1200169689Skan /* Some statements may be simplified using ranges. For 1201169689Skan example, division may be replaced by shifts, modulo 1202169689Skan replaced with bitwise and, etc. Do this after 1203169689Skan substituting constants, folding, etc so that we're 1204169689Skan presented with a fully propagated, canonicalized 1205169689Skan statement. */ 1206169689Skan if (use_ranges_p) 1207169689Skan simplify_stmt_using_ranges (stmt); 1208169689Skan 1209169689Skan } 1210169689Skan } 1211169689Skan 1212169689Skan if (dump_file && (dump_flags & TDF_STATS)) 1213169689Skan { 1214169689Skan fprintf (dump_file, "Constants propagated: %6ld\n", 1215169689Skan prop_stats.num_const_prop); 1216169689Skan fprintf (dump_file, "Copies propagated: %6ld\n", 1217169689Skan prop_stats.num_copy_prop); 1218169689Skan fprintf (dump_file, "Predicates folded: %6ld\n", 1219169689Skan prop_stats.num_pred_folded); 1220169689Skan } 1221169689Skan} 1222169689Skan 1223169689Skan#include "gt-tree-ssa-propagate.h" 1224