1169689Skan/* Generic SSA value propagation engine. 2169689Skan Copyright (C) 2004, 2005, 2006 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{ 179169689Skan gcc_assert (bb != ENTRY_BLOCK_PTR && bb != EXIT_BLOCK_PTR); 180169689Skan gcc_assert (!TEST_BIT (bb_in_list, bb->index)); 181169689Skan 182169689Skan if (cfg_blocks_empty_p ()) 183169689Skan { 184169689Skan cfg_blocks_tail = cfg_blocks_head = 0; 185169689Skan cfg_blocks_num = 1; 186169689Skan } 187169689Skan else 188169689Skan { 189169689Skan cfg_blocks_num++; 190169689Skan if (cfg_blocks_num > VEC_length (basic_block, cfg_blocks)) 191169689Skan { 192169689Skan /* We have to grow the array now. Adjust to queue to occupy 193169689Skan the full space of the original array. We do not need to 194169689Skan initialize the newly allocated portion of the array 195169689Skan because we keep track of CFG_BLOCKS_HEAD and 196169689Skan CFG_BLOCKS_HEAD. */ 197169689Skan cfg_blocks_tail = VEC_length (basic_block, cfg_blocks); 198169689Skan cfg_blocks_head = 0; 199169689Skan VEC_safe_grow (basic_block, heap, cfg_blocks, 2 * cfg_blocks_tail); 200169689Skan } 201169689Skan else 202169689Skan cfg_blocks_tail = ((cfg_blocks_tail + 1) 203169689Skan % VEC_length (basic_block, cfg_blocks)); 204169689Skan } 205169689Skan 206169689Skan VEC_replace (basic_block, cfg_blocks, cfg_blocks_tail, bb); 207169689Skan SET_BIT (bb_in_list, bb->index); 208169689Skan} 209169689Skan 210169689Skan 211169689Skan/* Remove a block from the worklist. */ 212169689Skan 213169689Skanstatic basic_block 214169689Skancfg_blocks_get (void) 215169689Skan{ 216169689Skan basic_block bb; 217169689Skan 218169689Skan bb = VEC_index (basic_block, cfg_blocks, cfg_blocks_head); 219169689Skan 220169689Skan gcc_assert (!cfg_blocks_empty_p ()); 221169689Skan gcc_assert (bb); 222169689Skan 223169689Skan cfg_blocks_head = ((cfg_blocks_head + 1) 224169689Skan % VEC_length (basic_block, cfg_blocks)); 225169689Skan --cfg_blocks_num; 226169689Skan RESET_BIT (bb_in_list, bb->index); 227169689Skan 228169689Skan return bb; 229169689Skan} 230169689Skan 231169689Skan 232169689Skan/* We have just defined a new value for VAR. If IS_VARYING is true, 233169689Skan add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add 234169689Skan them to INTERESTING_SSA_EDGES. */ 235169689Skan 236169689Skanstatic void 237169689Skanadd_ssa_edge (tree var, bool is_varying) 238169689Skan{ 239169689Skan imm_use_iterator iter; 240169689Skan use_operand_p use_p; 241169689Skan 242169689Skan FOR_EACH_IMM_USE_FAST (use_p, iter, var) 243169689Skan { 244169689Skan tree use_stmt = USE_STMT (use_p); 245169689Skan 246169689Skan if (!DONT_SIMULATE_AGAIN (use_stmt) 247169689Skan && !STMT_IN_SSA_EDGE_WORKLIST (use_stmt)) 248169689Skan { 249169689Skan STMT_IN_SSA_EDGE_WORKLIST (use_stmt) = 1; 250169689Skan if (is_varying) 251169689Skan VEC_safe_push (tree, gc, varying_ssa_edges, use_stmt); 252169689Skan else 253169689Skan VEC_safe_push (tree, gc, interesting_ssa_edges, use_stmt); 254169689Skan } 255169689Skan } 256169689Skan} 257169689Skan 258169689Skan 259169689Skan/* Add edge E to the control flow worklist. */ 260169689Skan 261169689Skanstatic void 262169689Skanadd_control_edge (edge e) 263169689Skan{ 264169689Skan basic_block bb = e->dest; 265169689Skan if (bb == EXIT_BLOCK_PTR) 266169689Skan return; 267169689Skan 268169689Skan /* If the edge had already been executed, skip it. */ 269169689Skan if (e->flags & EDGE_EXECUTABLE) 270169689Skan return; 271169689Skan 272169689Skan e->flags |= EDGE_EXECUTABLE; 273169689Skan 274169689Skan /* If the block is already in the list, we're done. */ 275169689Skan if (TEST_BIT (bb_in_list, bb->index)) 276169689Skan return; 277169689Skan 278169689Skan cfg_blocks_add (bb); 279169689Skan 280169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 281169689Skan fprintf (dump_file, "Adding Destination of edge (%d -> %d) to worklist\n\n", 282169689Skan e->src->index, e->dest->index); 283169689Skan} 284169689Skan 285169689Skan 286169689Skan/* Simulate the execution of STMT and update the work lists accordingly. */ 287169689Skan 288169689Skanstatic void 289169689Skansimulate_stmt (tree stmt) 290169689Skan{ 291169689Skan enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING; 292169689Skan edge taken_edge = NULL; 293169689Skan tree output_name = NULL_TREE; 294169689Skan 295169689Skan /* Don't bother visiting statements that are already 296169689Skan considered varying by the propagator. */ 297169689Skan if (DONT_SIMULATE_AGAIN (stmt)) 298169689Skan return; 299169689Skan 300169689Skan if (TREE_CODE (stmt) == PHI_NODE) 301169689Skan { 302169689Skan val = ssa_prop_visit_phi (stmt); 303169689Skan output_name = PHI_RESULT (stmt); 304169689Skan } 305169689Skan else 306169689Skan val = ssa_prop_visit_stmt (stmt, &taken_edge, &output_name); 307169689Skan 308169689Skan if (val == SSA_PROP_VARYING) 309169689Skan { 310169689Skan DONT_SIMULATE_AGAIN (stmt) = 1; 311169689Skan 312169689Skan /* If the statement produced a new varying value, add the SSA 313169689Skan edges coming out of OUTPUT_NAME. */ 314169689Skan if (output_name) 315169689Skan add_ssa_edge (output_name, true); 316169689Skan 317169689Skan /* If STMT transfers control out of its basic block, add 318169689Skan all outgoing edges to the work list. */ 319169689Skan if (stmt_ends_bb_p (stmt)) 320169689Skan { 321169689Skan edge e; 322169689Skan edge_iterator ei; 323169689Skan basic_block bb = bb_for_stmt (stmt); 324169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 325169689Skan add_control_edge (e); 326169689Skan } 327169689Skan } 328169689Skan else if (val == SSA_PROP_INTERESTING) 329169689Skan { 330169689Skan /* If the statement produced new value, add the SSA edges coming 331169689Skan out of OUTPUT_NAME. */ 332169689Skan if (output_name) 333169689Skan add_ssa_edge (output_name, false); 334169689Skan 335169689Skan /* If we know which edge is going to be taken out of this block, 336169689Skan add it to the CFG work list. */ 337169689Skan if (taken_edge) 338169689Skan add_control_edge (taken_edge); 339169689Skan } 340169689Skan} 341169689Skan 342169689Skan/* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to 343169689Skan drain. This pops statements off the given WORKLIST and processes 344169689Skan them until there are no more statements on WORKLIST. 345169689Skan We take a pointer to WORKLIST because it may be reallocated when an 346169689Skan SSA edge is added to it in simulate_stmt. */ 347169689Skan 348169689Skanstatic void 349169689Skanprocess_ssa_edge_worklist (VEC(tree,gc) **worklist) 350169689Skan{ 351169689Skan /* Drain the entire worklist. */ 352169689Skan while (VEC_length (tree, *worklist) > 0) 353169689Skan { 354169689Skan basic_block bb; 355169689Skan 356169689Skan /* Pull the statement to simulate off the worklist. */ 357169689Skan tree stmt = VEC_pop (tree, *worklist); 358169689Skan 359169689Skan /* If this statement was already visited by simulate_block, then 360169689Skan we don't need to visit it again here. */ 361169689Skan if (!STMT_IN_SSA_EDGE_WORKLIST (stmt)) 362169689Skan continue; 363169689Skan 364169689Skan /* STMT is no longer in a worklist. */ 365169689Skan STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0; 366169689Skan 367169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 368169689Skan { 369169689Skan fprintf (dump_file, "\nSimulating statement (from ssa_edges): "); 370169689Skan print_generic_stmt (dump_file, stmt, dump_flags); 371169689Skan } 372169689Skan 373169689Skan bb = bb_for_stmt (stmt); 374169689Skan 375169689Skan /* PHI nodes are always visited, regardless of whether or not 376169689Skan the destination block is executable. Otherwise, visit the 377169689Skan statement only if its block is marked executable. */ 378169689Skan if (TREE_CODE (stmt) == PHI_NODE 379169689Skan || TEST_BIT (executable_blocks, bb->index)) 380169689Skan simulate_stmt (stmt); 381169689Skan } 382169689Skan} 383169689Skan 384169689Skan 385169689Skan/* Simulate the execution of BLOCK. Evaluate the statement associated 386169689Skan with each variable reference inside the block. */ 387169689Skan 388169689Skanstatic void 389169689Skansimulate_block (basic_block block) 390169689Skan{ 391169689Skan tree phi; 392169689Skan 393169689Skan /* There is nothing to do for the exit block. */ 394169689Skan if (block == EXIT_BLOCK_PTR) 395169689Skan return; 396169689Skan 397169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 398169689Skan fprintf (dump_file, "\nSimulating block %d\n", block->index); 399169689Skan 400169689Skan /* Always simulate PHI nodes, even if we have simulated this block 401169689Skan before. */ 402169689Skan for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi)) 403169689Skan simulate_stmt (phi); 404169689Skan 405169689Skan /* If this is the first time we've simulated this block, then we 406169689Skan must simulate each of its statements. */ 407169689Skan if (!TEST_BIT (executable_blocks, block->index)) 408169689Skan { 409169689Skan block_stmt_iterator j; 410169689Skan unsigned int normal_edge_count; 411169689Skan edge e, normal_edge; 412169689Skan edge_iterator ei; 413169689Skan 414169689Skan /* Note that we have simulated this block. */ 415169689Skan SET_BIT (executable_blocks, block->index); 416169689Skan 417169689Skan for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j)) 418169689Skan { 419169689Skan tree stmt = bsi_stmt (j); 420169689Skan 421169689Skan /* If this statement is already in the worklist then 422169689Skan "cancel" it. The reevaluation implied by the worklist 423169689Skan entry will produce the same value we generate here and 424169689Skan thus reevaluating it again from the worklist is 425169689Skan pointless. */ 426169689Skan if (STMT_IN_SSA_EDGE_WORKLIST (stmt)) 427169689Skan STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0; 428169689Skan 429169689Skan simulate_stmt (stmt); 430169689Skan } 431169689Skan 432169689Skan /* We can not predict when abnormal edges will be executed, so 433169689Skan once a block is considered executable, we consider any 434169689Skan outgoing abnormal edges as executable. 435169689Skan 436169689Skan At the same time, if this block has only one successor that is 437169689Skan reached by non-abnormal edges, then add that successor to the 438169689Skan worklist. */ 439169689Skan normal_edge_count = 0; 440169689Skan normal_edge = NULL; 441169689Skan FOR_EACH_EDGE (e, ei, block->succs) 442169689Skan { 443169689Skan if (e->flags & EDGE_ABNORMAL) 444169689Skan add_control_edge (e); 445169689Skan else 446169689Skan { 447169689Skan normal_edge_count++; 448169689Skan normal_edge = e; 449169689Skan } 450169689Skan } 451169689Skan 452169689Skan if (normal_edge_count == 1) 453169689Skan add_control_edge (normal_edge); 454169689Skan } 455169689Skan} 456169689Skan 457169689Skan 458169689Skan/* Initialize local data structures and work lists. */ 459169689Skan 460169689Skanstatic void 461169689Skanssa_prop_init (void) 462169689Skan{ 463169689Skan edge e; 464169689Skan edge_iterator ei; 465169689Skan basic_block bb; 466169689Skan size_t i; 467169689Skan 468169689Skan /* Worklists of SSA edges. */ 469169689Skan interesting_ssa_edges = VEC_alloc (tree, gc, 20); 470169689Skan varying_ssa_edges = VEC_alloc (tree, gc, 20); 471169689Skan 472169689Skan executable_blocks = sbitmap_alloc (last_basic_block); 473169689Skan sbitmap_zero (executable_blocks); 474169689Skan 475169689Skan bb_in_list = sbitmap_alloc (last_basic_block); 476169689Skan sbitmap_zero (bb_in_list); 477169689Skan 478169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 479169689Skan dump_immediate_uses (dump_file); 480169689Skan 481169689Skan cfg_blocks = VEC_alloc (basic_block, heap, 20); 482169689Skan VEC_safe_grow (basic_block, heap, cfg_blocks, 20); 483169689Skan 484169689Skan /* Initialize the values for every SSA_NAME. */ 485169689Skan for (i = 1; i < num_ssa_names; i++) 486169689Skan if (ssa_name (i)) 487169689Skan SSA_NAME_VALUE (ssa_name (i)) = NULL_TREE; 488169689Skan 489169689Skan /* Initially assume that every edge in the CFG is not executable. 490169689Skan (including the edges coming out of ENTRY_BLOCK_PTR). */ 491169689Skan FOR_ALL_BB (bb) 492169689Skan { 493169689Skan block_stmt_iterator si; 494169689Skan 495169689Skan for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 496169689Skan STMT_IN_SSA_EDGE_WORKLIST (bsi_stmt (si)) = 0; 497169689Skan 498169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 499169689Skan e->flags &= ~EDGE_EXECUTABLE; 500169689Skan } 501169689Skan 502169689Skan /* Seed the algorithm by adding the successors of the entry block to the 503169689Skan edge worklist. */ 504169689Skan FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 505169689Skan add_control_edge (e); 506169689Skan} 507169689Skan 508169689Skan 509169689Skan/* Free allocated storage. */ 510169689Skan 511169689Skanstatic void 512169689Skanssa_prop_fini (void) 513169689Skan{ 514169689Skan VEC_free (tree, gc, interesting_ssa_edges); 515169689Skan VEC_free (tree, gc, varying_ssa_edges); 516169689Skan VEC_free (basic_block, heap, cfg_blocks); 517169689Skan cfg_blocks = NULL; 518169689Skan sbitmap_free (bb_in_list); 519169689Skan sbitmap_free (executable_blocks); 520169689Skan} 521169689Skan 522169689Skan 523169689Skan/* Get the main expression from statement STMT. */ 524169689Skan 525169689Skantree 526169689Skanget_rhs (tree stmt) 527169689Skan{ 528169689Skan enum tree_code code = TREE_CODE (stmt); 529169689Skan 530169689Skan switch (code) 531169689Skan { 532169689Skan case RETURN_EXPR: 533169689Skan stmt = TREE_OPERAND (stmt, 0); 534169689Skan if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR) 535169689Skan return stmt; 536169689Skan /* FALLTHRU */ 537169689Skan 538169689Skan case MODIFY_EXPR: 539169689Skan stmt = TREE_OPERAND (stmt, 1); 540169689Skan if (TREE_CODE (stmt) == WITH_SIZE_EXPR) 541169689Skan return TREE_OPERAND (stmt, 0); 542169689Skan else 543169689Skan return stmt; 544169689Skan 545169689Skan case COND_EXPR: 546169689Skan return COND_EXPR_COND (stmt); 547169689Skan case SWITCH_EXPR: 548169689Skan return SWITCH_COND (stmt); 549169689Skan case GOTO_EXPR: 550169689Skan return GOTO_DESTINATION (stmt); 551169689Skan case LABEL_EXPR: 552169689Skan return LABEL_EXPR_LABEL (stmt); 553169689Skan 554169689Skan default: 555169689Skan return stmt; 556169689Skan } 557169689Skan} 558169689Skan 559169689Skan 560169689Skan/* Set the main expression of *STMT_P to EXPR. If EXPR is not a valid 561169689Skan GIMPLE expression no changes are done and the function returns 562169689Skan false. */ 563169689Skan 564169689Skanbool 565169689Skanset_rhs (tree *stmt_p, tree expr) 566169689Skan{ 567169689Skan tree stmt = *stmt_p, op; 568169689Skan enum tree_code code = TREE_CODE (expr); 569169689Skan stmt_ann_t ann; 570169689Skan tree var; 571169689Skan ssa_op_iter iter; 572169689Skan 573169689Skan /* Verify the constant folded result is valid gimple. */ 574169689Skan if (TREE_CODE_CLASS (code) == tcc_binary) 575169689Skan { 576169689Skan if (!is_gimple_val (TREE_OPERAND (expr, 0)) 577169689Skan || !is_gimple_val (TREE_OPERAND (expr, 1))) 578169689Skan return false; 579169689Skan } 580169689Skan else if (TREE_CODE_CLASS (code) == tcc_unary) 581169689Skan { 582169689Skan if (!is_gimple_val (TREE_OPERAND (expr, 0))) 583169689Skan return false; 584169689Skan } 585169689Skan else if (code == ADDR_EXPR) 586169689Skan { 587169689Skan if (TREE_CODE (TREE_OPERAND (expr, 0)) == ARRAY_REF 588169689Skan && !is_gimple_val (TREE_OPERAND (TREE_OPERAND (expr, 0), 1))) 589169689Skan return false; 590169689Skan } 591169689Skan else if (code == COMPOUND_EXPR 592169689Skan || code == MODIFY_EXPR) 593169689Skan return false; 594169689Skan 595169689Skan if (EXPR_HAS_LOCATION (stmt) 596169689Skan && EXPR_P (expr) 597169689Skan && ! EXPR_HAS_LOCATION (expr) 598169689Skan && TREE_SIDE_EFFECTS (expr) 599169689Skan && TREE_CODE (expr) != LABEL_EXPR) 600169689Skan SET_EXPR_LOCATION (expr, EXPR_LOCATION (stmt)); 601169689Skan 602169689Skan switch (TREE_CODE (stmt)) 603169689Skan { 604169689Skan case RETURN_EXPR: 605169689Skan op = TREE_OPERAND (stmt, 0); 606169689Skan if (TREE_CODE (op) != MODIFY_EXPR) 607169689Skan { 608169689Skan TREE_OPERAND (stmt, 0) = expr; 609169689Skan break; 610169689Skan } 611169689Skan stmt = op; 612169689Skan /* FALLTHRU */ 613169689Skan 614169689Skan case MODIFY_EXPR: 615169689Skan op = TREE_OPERAND (stmt, 1); 616169689Skan if (TREE_CODE (op) == WITH_SIZE_EXPR) 617169689Skan stmt = op; 618169689Skan TREE_OPERAND (stmt, 1) = expr; 619169689Skan break; 620169689Skan 621169689Skan case COND_EXPR: 622169689Skan if (!is_gimple_condexpr (expr)) 623169689Skan return false; 624169689Skan COND_EXPR_COND (stmt) = expr; 625169689Skan break; 626169689Skan case SWITCH_EXPR: 627169689Skan SWITCH_COND (stmt) = expr; 628169689Skan break; 629169689Skan case GOTO_EXPR: 630169689Skan GOTO_DESTINATION (stmt) = expr; 631169689Skan break; 632169689Skan case LABEL_EXPR: 633169689Skan LABEL_EXPR_LABEL (stmt) = expr; 634169689Skan break; 635169689Skan 636169689Skan default: 637169689Skan /* Replace the whole statement with EXPR. If EXPR has no side 638169689Skan effects, then replace *STMT_P with an empty statement. */ 639169689Skan ann = stmt_ann (stmt); 640169689Skan *stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt (); 641169689Skan (*stmt_p)->common.ann = (tree_ann_t) ann; 642169689Skan 643169689Skan if (in_ssa_p 644169689Skan && TREE_SIDE_EFFECTS (expr)) 645169689Skan { 646169689Skan /* Fix all the SSA_NAMEs created by *STMT_P to point to its new 647169689Skan replacement. */ 648169689Skan FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_DEFS) 649169689Skan { 650169689Skan if (TREE_CODE (var) == SSA_NAME) 651169689Skan SSA_NAME_DEF_STMT (var) = *stmt_p; 652169689Skan } 653169689Skan } 654169689Skan break; 655169689Skan } 656169689Skan 657169689Skan return true; 658169689Skan} 659169689Skan 660169689Skan 661169689Skan/* Entry point to the propagation engine. 662169689Skan 663169689Skan VISIT_STMT is called for every statement visited. 664169689Skan VISIT_PHI is called for every PHI node visited. */ 665169689Skan 666169689Skanvoid 667169689Skanssa_propagate (ssa_prop_visit_stmt_fn visit_stmt, 668169689Skan ssa_prop_visit_phi_fn visit_phi) 669169689Skan{ 670169689Skan ssa_prop_visit_stmt = visit_stmt; 671169689Skan ssa_prop_visit_phi = visit_phi; 672169689Skan 673169689Skan ssa_prop_init (); 674169689Skan 675169689Skan /* Iterate until the worklists are empty. */ 676169689Skan while (!cfg_blocks_empty_p () 677169689Skan || VEC_length (tree, interesting_ssa_edges) > 0 678169689Skan || VEC_length (tree, varying_ssa_edges) > 0) 679169689Skan { 680169689Skan if (!cfg_blocks_empty_p ()) 681169689Skan { 682169689Skan /* Pull the next block to simulate off the worklist. */ 683169689Skan basic_block dest_block = cfg_blocks_get (); 684169689Skan simulate_block (dest_block); 685169689Skan } 686169689Skan 687169689Skan /* In order to move things to varying as quickly as 688169689Skan possible,process the VARYING_SSA_EDGES worklist first. */ 689169689Skan process_ssa_edge_worklist (&varying_ssa_edges); 690169689Skan 691169689Skan /* Now process the INTERESTING_SSA_EDGES worklist. */ 692169689Skan process_ssa_edge_worklist (&interesting_ssa_edges); 693169689Skan } 694169689Skan 695169689Skan ssa_prop_fini (); 696169689Skan} 697169689Skan 698169689Skan 699169689Skan/* Return the first V_MAY_DEF or V_MUST_DEF operand for STMT. */ 700169689Skan 701169689Skantree 702169689Skanfirst_vdef (tree stmt) 703169689Skan{ 704169689Skan ssa_op_iter iter; 705169689Skan tree op; 706169689Skan 707169689Skan /* Simply return the first operand we arrive at. */ 708169689Skan FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS) 709169689Skan return (op); 710169689Skan 711169689Skan gcc_unreachable (); 712169689Skan} 713169689Skan 714169689Skan 715169689Skan/* Return true if STMT is of the form 'LHS = mem_ref', where 'mem_ref' 716169689Skan is a non-volatile pointer dereference, a structure reference or a 717169689Skan reference to a single _DECL. Ignore volatile memory references 718169689Skan because they are not interesting for the optimizers. */ 719169689Skan 720169689Skanbool 721169689Skanstmt_makes_single_load (tree stmt) 722169689Skan{ 723169689Skan tree rhs; 724169689Skan 725169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR) 726169689Skan return false; 727169689Skan 728169689Skan if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VUSE)) 729169689Skan return false; 730169689Skan 731169689Skan rhs = TREE_OPERAND (stmt, 1); 732169689Skan STRIP_NOPS (rhs); 733169689Skan 734169689Skan return (!TREE_THIS_VOLATILE (rhs) 735169689Skan && (DECL_P (rhs) 736169689Skan || REFERENCE_CLASS_P (rhs))); 737169689Skan} 738169689Skan 739169689Skan 740169689Skan/* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref' 741169689Skan is a non-volatile pointer dereference, a structure reference or a 742169689Skan reference to a single _DECL. Ignore volatile memory references 743169689Skan because they are not interesting for the optimizers. */ 744169689Skan 745169689Skanbool 746169689Skanstmt_makes_single_store (tree stmt) 747169689Skan{ 748169689Skan tree lhs; 749169689Skan 750169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR) 751169689Skan return false; 752169689Skan 753169689Skan if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF)) 754169689Skan return false; 755169689Skan 756169689Skan lhs = TREE_OPERAND (stmt, 0); 757169689Skan STRIP_NOPS (lhs); 758169689Skan 759169689Skan return (!TREE_THIS_VOLATILE (lhs) 760169689Skan && (DECL_P (lhs) 761169689Skan || REFERENCE_CLASS_P (lhs))); 762169689Skan} 763169689Skan 764169689Skan 765169689Skan/* If STMT makes a single memory load and all the virtual use operands 766169689Skan have the same value in array VALUES, return it. Otherwise, return 767169689Skan NULL. */ 768169689Skan 769169689Skanprop_value_t * 770169689Skanget_value_loaded_by (tree stmt, prop_value_t *values) 771169689Skan{ 772169689Skan ssa_op_iter i; 773169689Skan tree vuse; 774169689Skan prop_value_t *prev_val = NULL; 775169689Skan prop_value_t *val = NULL; 776169689Skan 777169689Skan FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES) 778169689Skan { 779169689Skan val = &values[SSA_NAME_VERSION (vuse)]; 780169689Skan if (prev_val && prev_val->value != val->value) 781169689Skan return NULL; 782169689Skan prev_val = val; 783169689Skan } 784169689Skan 785169689Skan return val; 786169689Skan} 787169689Skan 788169689Skan 789169689Skan/* Propagation statistics. */ 790169689Skanstruct prop_stats_d 791169689Skan{ 792169689Skan long num_const_prop; 793169689Skan long num_copy_prop; 794169689Skan long num_pred_folded; 795169689Skan}; 796169689Skan 797169689Skanstatic struct prop_stats_d prop_stats; 798169689Skan 799169689Skan/* Replace USE references in statement STMT with the values stored in 800169689Skan PROP_VALUE. Return true if at least one reference was replaced. If 801169689Skan REPLACED_ADDRESSES_P is given, it will be set to true if an address 802169689Skan constant was replaced. */ 803169689Skan 804169689Skanbool 805169689Skanreplace_uses_in (tree stmt, bool *replaced_addresses_p, 806169689Skan prop_value_t *prop_value) 807169689Skan{ 808169689Skan bool replaced = false; 809169689Skan use_operand_p use; 810169689Skan ssa_op_iter iter; 811169689Skan 812169689Skan FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE) 813169689Skan { 814169689Skan tree tuse = USE_FROM_PTR (use); 815169689Skan tree val = prop_value[SSA_NAME_VERSION (tuse)].value; 816169689Skan 817169689Skan if (val == tuse || val == NULL_TREE) 818169689Skan continue; 819169689Skan 820169689Skan if (TREE_CODE (stmt) == ASM_EXPR 821169689Skan && !may_propagate_copy_into_asm (tuse)) 822169689Skan continue; 823169689Skan 824169689Skan if (!may_propagate_copy (tuse, val)) 825169689Skan continue; 826169689Skan 827169689Skan if (TREE_CODE (val) != SSA_NAME) 828169689Skan prop_stats.num_const_prop++; 829169689Skan else 830169689Skan prop_stats.num_copy_prop++; 831169689Skan 832169689Skan propagate_value (use, val); 833169689Skan 834169689Skan replaced = true; 835169689Skan if (POINTER_TYPE_P (TREE_TYPE (tuse)) && replaced_addresses_p) 836169689Skan *replaced_addresses_p = true; 837169689Skan } 838169689Skan 839169689Skan return replaced; 840169689Skan} 841169689Skan 842169689Skan 843169689Skan/* Replace the VUSE references in statement STMT with the values 844169689Skan stored in PROP_VALUE. Return true if a reference was replaced. If 845169689Skan REPLACED_ADDRESSES_P is given, it will be set to true if an address 846169689Skan constant was replaced. 847169689Skan 848169689Skan Replacing VUSE operands is slightly more complex than replacing 849169689Skan regular USEs. We are only interested in two types of replacements 850169689Skan here: 851169689Skan 852169689Skan 1- If the value to be replaced is a constant or an SSA name for a 853169689Skan GIMPLE register, then we are making a copy/constant propagation 854169689Skan from a memory store. For instance, 855169689Skan 856169689Skan # a_3 = V_MAY_DEF <a_2> 857169689Skan a.b = x_1; 858169689Skan ... 859169689Skan # VUSE <a_3> 860169689Skan y_4 = a.b; 861169689Skan 862169689Skan This replacement is only possible iff STMT is an assignment 863169689Skan whose RHS is identical to the LHS of the statement that created 864169689Skan the VUSE(s) that we are replacing. Otherwise, we may do the 865169689Skan wrong replacement: 866169689Skan 867169689Skan # a_3 = V_MAY_DEF <a_2> 868169689Skan # b_5 = V_MAY_DEF <b_4> 869169689Skan *p = 10; 870169689Skan ... 871169689Skan # VUSE <b_5> 872169689Skan x_8 = b; 873169689Skan 874169689Skan Even though 'b_5' acquires the value '10' during propagation, 875169689Skan there is no way for the propagator to tell whether the 876169689Skan replacement is correct in every reached use, because values are 877169689Skan computed at definition sites. Therefore, when doing final 878169689Skan substitution of propagated values, we have to check each use 879169689Skan site. Since the RHS of STMT ('b') is different from the LHS of 880169689Skan the originating statement ('*p'), we cannot replace 'b' with 881169689Skan '10'. 882169689Skan 883169689Skan Similarly, when merging values from PHI node arguments, 884169689Skan propagators need to take care not to merge the same values 885169689Skan stored in different locations: 886169689Skan 887169689Skan if (...) 888169689Skan # a_3 = V_MAY_DEF <a_2> 889169689Skan a.b = 3; 890169689Skan else 891169689Skan # a_4 = V_MAY_DEF <a_2> 892169689Skan a.c = 3; 893169689Skan # a_5 = PHI <a_3, a_4> 894169689Skan 895169689Skan It would be wrong to propagate '3' into 'a_5' because that 896169689Skan operation merges two stores to different memory locations. 897169689Skan 898169689Skan 899169689Skan 2- If the value to be replaced is an SSA name for a virtual 900169689Skan register, then we simply replace each VUSE operand with its 901169689Skan value from PROP_VALUE. This is the same replacement done by 902169689Skan replace_uses_in. */ 903169689Skan 904169689Skanstatic bool 905169689Skanreplace_vuses_in (tree stmt, bool *replaced_addresses_p, 906169689Skan prop_value_t *prop_value) 907169689Skan{ 908169689Skan bool replaced = false; 909169689Skan ssa_op_iter iter; 910169689Skan use_operand_p vuse; 911169689Skan 912169689Skan if (stmt_makes_single_load (stmt)) 913169689Skan { 914169689Skan /* If STMT is an assignment whose RHS is a single memory load, 915169689Skan see if we are trying to propagate a constant or a GIMPLE 916169689Skan register (case #1 above). */ 917169689Skan prop_value_t *val = get_value_loaded_by (stmt, prop_value); 918169689Skan tree rhs = TREE_OPERAND (stmt, 1); 919169689Skan 920169689Skan if (val 921169689Skan && val->value 922169689Skan && (is_gimple_reg (val->value) 923169689Skan || is_gimple_min_invariant (val->value)) 924169689Skan && simple_cst_equal (rhs, val->mem_ref) == 1) 925169689Skan 926169689Skan { 927169689Skan /* If we are replacing a constant address, inform our 928169689Skan caller. */ 929169689Skan if (TREE_CODE (val->value) != SSA_NAME 930169689Skan && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))) 931169689Skan && replaced_addresses_p) 932169689Skan *replaced_addresses_p = true; 933169689Skan 934169689Skan /* We can only perform the substitution if the load is done 935169689Skan from the same memory location as the original store. 936169689Skan Since we already know that there are no intervening 937169689Skan stores between DEF_STMT and STMT, we only need to check 938169689Skan that the RHS of STMT is the same as the memory reference 939169689Skan propagated together with the value. */ 940169689Skan TREE_OPERAND (stmt, 1) = val->value; 941169689Skan 942169689Skan if (TREE_CODE (val->value) != SSA_NAME) 943169689Skan prop_stats.num_const_prop++; 944169689Skan else 945169689Skan prop_stats.num_copy_prop++; 946169689Skan 947169689Skan /* Since we have replaced the whole RHS of STMT, there 948169689Skan is no point in checking the other VUSEs, as they will 949169689Skan all have the same value. */ 950169689Skan return true; 951169689Skan } 952169689Skan } 953169689Skan 954169689Skan /* Otherwise, the values for every VUSE operand must be other 955169689Skan SSA_NAMEs that can be propagated into STMT. */ 956169689Skan FOR_EACH_SSA_USE_OPERAND (vuse, stmt, iter, SSA_OP_VIRTUAL_USES) 957169689Skan { 958169689Skan tree var = USE_FROM_PTR (vuse); 959169689Skan tree val = prop_value[SSA_NAME_VERSION (var)].value; 960169689Skan 961169689Skan if (val == NULL_TREE || var == val) 962169689Skan continue; 963169689Skan 964169689Skan /* Constants and copies propagated between real and virtual 965169689Skan operands are only possible in the cases handled above. They 966169689Skan should be ignored in any other context. */ 967169689Skan if (is_gimple_min_invariant (val) || is_gimple_reg (val)) 968169689Skan continue; 969169689Skan 970169689Skan propagate_value (vuse, val); 971169689Skan prop_stats.num_copy_prop++; 972169689Skan replaced = true; 973169689Skan } 974169689Skan 975169689Skan return replaced; 976169689Skan} 977169689Skan 978169689Skan 979169689Skan/* Replace propagated values into all the arguments for PHI using the 980169689Skan values from PROP_VALUE. */ 981169689Skan 982169689Skanstatic void 983169689Skanreplace_phi_args_in (tree phi, prop_value_t *prop_value) 984169689Skan{ 985169689Skan int i; 986169689Skan bool replaced = false; 987169689Skan tree prev_phi = NULL; 988169689Skan 989169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 990169689Skan prev_phi = unshare_expr (phi); 991169689Skan 992169689Skan for (i = 0; i < PHI_NUM_ARGS (phi); i++) 993169689Skan { 994169689Skan tree arg = PHI_ARG_DEF (phi, i); 995169689Skan 996169689Skan if (TREE_CODE (arg) == SSA_NAME) 997169689Skan { 998169689Skan tree val = prop_value[SSA_NAME_VERSION (arg)].value; 999169689Skan 1000169689Skan if (val && val != arg && may_propagate_copy (arg, val)) 1001169689Skan { 1002169689Skan if (TREE_CODE (val) != SSA_NAME) 1003169689Skan prop_stats.num_const_prop++; 1004169689Skan else 1005169689Skan prop_stats.num_copy_prop++; 1006169689Skan 1007169689Skan propagate_value (PHI_ARG_DEF_PTR (phi, i), val); 1008169689Skan replaced = true; 1009169689Skan 1010169689Skan /* If we propagated a copy and this argument flows 1011169689Skan through an abnormal edge, update the replacement 1012169689Skan accordingly. */ 1013169689Skan if (TREE_CODE (val) == SSA_NAME 1014169689Skan && PHI_ARG_EDGE (phi, i)->flags & EDGE_ABNORMAL) 1015169689Skan SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1; 1016169689Skan } 1017169689Skan } 1018169689Skan } 1019169689Skan 1020169689Skan if (replaced && dump_file && (dump_flags & TDF_DETAILS)) 1021169689Skan { 1022169689Skan fprintf (dump_file, "Folded PHI node: "); 1023169689Skan print_generic_stmt (dump_file, prev_phi, TDF_SLIM); 1024169689Skan fprintf (dump_file, " into: "); 1025169689Skan print_generic_stmt (dump_file, phi, TDF_SLIM); 1026169689Skan fprintf (dump_file, "\n"); 1027169689Skan } 1028169689Skan} 1029169689Skan 1030169689Skan 1031169689Skan/* If STMT has a predicate whose value can be computed using the value 1032169689Skan range information computed by VRP, compute its value and return true. 1033169689Skan Otherwise, return false. */ 1034169689Skan 1035169689Skanstatic bool 1036169689Skanfold_predicate_in (tree stmt) 1037169689Skan{ 1038169689Skan tree *pred_p = NULL; 1039169689Skan bool modify_expr_p = false; 1040169689Skan tree val; 1041169689Skan 1042169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR 1043169689Skan && COMPARISON_CLASS_P (TREE_OPERAND (stmt, 1))) 1044169689Skan { 1045169689Skan modify_expr_p = true; 1046169689Skan pred_p = &TREE_OPERAND (stmt, 1); 1047169689Skan } 1048169689Skan else if (TREE_CODE (stmt) == COND_EXPR) 1049169689Skan pred_p = &COND_EXPR_COND (stmt); 1050169689Skan else 1051169689Skan return false; 1052169689Skan 1053169689Skan val = vrp_evaluate_conditional (*pred_p, stmt); 1054169689Skan if (val) 1055169689Skan { 1056169689Skan if (modify_expr_p) 1057169689Skan val = fold_convert (TREE_TYPE (*pred_p), val); 1058169689Skan 1059169689Skan if (dump_file) 1060169689Skan { 1061169689Skan fprintf (dump_file, "Folding predicate "); 1062169689Skan print_generic_expr (dump_file, *pred_p, 0); 1063169689Skan fprintf (dump_file, " to "); 1064169689Skan print_generic_expr (dump_file, val, 0); 1065169689Skan fprintf (dump_file, "\n"); 1066169689Skan } 1067169689Skan 1068169689Skan prop_stats.num_pred_folded++; 1069169689Skan *pred_p = val; 1070169689Skan return true; 1071169689Skan } 1072169689Skan 1073169689Skan return false; 1074169689Skan} 1075169689Skan 1076169689Skan 1077169689Skan/* Perform final substitution and folding of propagated values. 1078169689Skan 1079169689Skan PROP_VALUE[I] contains the single value that should be substituted 1080169689Skan at every use of SSA name N_I. If PROP_VALUE is NULL, no values are 1081169689Skan substituted. 1082169689Skan 1083169689Skan If USE_RANGES_P is true, statements that contain predicate 1084169689Skan expressions are evaluated with a call to vrp_evaluate_conditional. 1085169689Skan This will only give meaningful results when called from tree-vrp.c 1086169689Skan (the information used by vrp_evaluate_conditional is built by the 1087169689Skan VRP pass). */ 1088169689Skan 1089169689Skanvoid 1090169689Skansubstitute_and_fold (prop_value_t *prop_value, bool use_ranges_p) 1091169689Skan{ 1092169689Skan basic_block bb; 1093169689Skan 1094169689Skan if (prop_value == NULL && !use_ranges_p) 1095169689Skan return; 1096169689Skan 1097169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1098169689Skan fprintf (dump_file, "\nSubstituing values and folding statements\n\n"); 1099169689Skan 1100169689Skan memset (&prop_stats, 0, sizeof (prop_stats)); 1101169689Skan 1102169689Skan /* Substitute values in every statement of every basic block. */ 1103169689Skan FOR_EACH_BB (bb) 1104169689Skan { 1105169689Skan block_stmt_iterator i; 1106169689Skan tree phi; 1107169689Skan 1108169689Skan /* Propagate known values into PHI nodes. */ 1109169689Skan if (prop_value) 1110169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1111169689Skan replace_phi_args_in (phi, prop_value); 1112169689Skan 1113169689Skan for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i)) 1114169689Skan { 1115169689Skan bool replaced_address, did_replace; 1116169689Skan tree prev_stmt = NULL; 1117169689Skan tree stmt = bsi_stmt (i); 1118169689Skan 1119169689Skan /* Ignore ASSERT_EXPRs. They are used by VRP to generate 1120169689Skan range information for names and they are discarded 1121169689Skan afterwards. */ 1122169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR 1123169689Skan && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR) 1124169689Skan continue; 1125169689Skan 1126169689Skan /* Replace the statement with its folded version and mark it 1127169689Skan folded. */ 1128169689Skan did_replace = false; 1129169689Skan replaced_address = false; 1130169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1131169689Skan prev_stmt = unshare_expr (stmt); 1132169689Skan 1133169689Skan /* If we have range information, see if we can fold 1134169689Skan predicate expressions. */ 1135169689Skan if (use_ranges_p) 1136169689Skan did_replace = fold_predicate_in (stmt); 1137169689Skan 1138169689Skan if (prop_value) 1139169689Skan { 1140169689Skan /* Only replace real uses if we couldn't fold the 1141169689Skan statement using value range information (value range 1142169689Skan information is not collected on virtuals, so we only 1143169689Skan need to check this for real uses). */ 1144169689Skan if (!did_replace) 1145169689Skan did_replace |= replace_uses_in (stmt, &replaced_address, 1146169689Skan prop_value); 1147169689Skan 1148169689Skan did_replace |= replace_vuses_in (stmt, &replaced_address, 1149169689Skan prop_value); 1150169689Skan } 1151169689Skan 1152169689Skan /* If we made a replacement, fold and cleanup the statement. */ 1153169689Skan if (did_replace) 1154169689Skan { 1155169689Skan tree old_stmt = stmt; 1156169689Skan tree rhs; 1157169689Skan 1158169689Skan fold_stmt (bsi_stmt_ptr (i)); 1159169689Skan stmt = bsi_stmt (i); 1160169689Skan 1161169689Skan /* If we folded a builtin function, we'll likely 1162169689Skan need to rename VDEFs. */ 1163169689Skan mark_new_vars_to_rename (stmt); 1164169689Skan 1165169689Skan /* If we cleaned up EH information from the statement, 1166169689Skan remove EH edges. */ 1167169689Skan if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) 1168169689Skan tree_purge_dead_eh_edges (bb); 1169169689Skan 1170169689Skan rhs = get_rhs (stmt); 1171169689Skan if (TREE_CODE (rhs) == ADDR_EXPR) 1172169689Skan recompute_tree_invariant_for_addr_expr (rhs); 1173169689Skan 1174169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1175169689Skan { 1176169689Skan fprintf (dump_file, "Folded statement: "); 1177169689Skan print_generic_stmt (dump_file, prev_stmt, TDF_SLIM); 1178169689Skan fprintf (dump_file, " into: "); 1179169689Skan print_generic_stmt (dump_file, stmt, TDF_SLIM); 1180169689Skan fprintf (dump_file, "\n"); 1181169689Skan } 1182169689Skan } 1183169689Skan 1184169689Skan /* Some statements may be simplified using ranges. For 1185169689Skan example, division may be replaced by shifts, modulo 1186169689Skan replaced with bitwise and, etc. Do this after 1187169689Skan substituting constants, folding, etc so that we're 1188169689Skan presented with a fully propagated, canonicalized 1189169689Skan statement. */ 1190169689Skan if (use_ranges_p) 1191169689Skan simplify_stmt_using_ranges (stmt); 1192169689Skan 1193169689Skan } 1194169689Skan } 1195169689Skan 1196169689Skan if (dump_file && (dump_flags & TDF_STATS)) 1197169689Skan { 1198169689Skan fprintf (dump_file, "Constants propagated: %6ld\n", 1199169689Skan prop_stats.num_const_prop); 1200169689Skan fprintf (dump_file, "Copies propagated: %6ld\n", 1201169689Skan prop_stats.num_copy_prop); 1202169689Skan fprintf (dump_file, "Predicates folded: %6ld\n", 1203169689Skan prop_stats.num_pred_folded); 1204169689Skan } 1205169689Skan} 1206169689Skan 1207169689Skan#include "gt-tree-ssa-propagate.h" 1208