1/* Generic SSA value propagation engine. 2 Copyright (C) 2004, 2005 Free Software Foundation, Inc. 3 Contributed by Diego Novillo <dnovillo@redhat.com> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it 8 under the terms of the GNU General Public License as published by the 9 Free Software Foundation; either version 2, or (at your option) any 10 later version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING. If not, write to the Free 19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20 02110-1301, USA. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "tm.h" 26#include "tree.h" 27#include "flags.h" 28#include "rtl.h" 29#include "tm_p.h" 30#include "ggc.h" 31#include "basic-block.h" 32#include "output.h" 33#include "expr.h" 34#include "function.h" 35#include "diagnostic.h" 36#include "timevar.h" 37#include "tree-dump.h" 38#include "tree-flow.h" 39#include "tree-pass.h" 40#include "tree-ssa-propagate.h" 41#include "langhooks.h" 42#include "varray.h" 43#include "vec.h" 44 45/* This file implements a generic value propagation engine based on 46 the same propagation used by the SSA-CCP algorithm [1]. 47 48 Propagation is performed by simulating the execution of every 49 statement that produces the value being propagated. Simulation 50 proceeds as follows: 51 52 1- Initially, all edges of the CFG are marked not executable and 53 the CFG worklist is seeded with all the statements in the entry 54 basic block (block 0). 55 56 2- Every statement S is simulated with a call to the call-back 57 function SSA_PROP_VISIT_STMT. This evaluation may produce 3 58 results: 59 60 SSA_PROP_NOT_INTERESTING: Statement S produces nothing of 61 interest and does not affect any of the work lists. 62 63 SSA_PROP_VARYING: The value produced by S cannot be determined 64 at compile time. Further simulation of S is not required. 65 If S is a conditional jump, all the outgoing edges for the 66 block are considered executable and added to the work 67 list. 68 69 SSA_PROP_INTERESTING: S produces a value that can be computed 70 at compile time. Its result can be propagated into the 71 statements that feed from S. Furthermore, if S is a 72 conditional jump, only the edge known to be taken is added 73 to the work list. Edges that are known not to execute are 74 never simulated. 75 76 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The 77 return value from SSA_PROP_VISIT_PHI has the same semantics as 78 described in #2. 79 80 4- Three work lists are kept. Statements are only added to these 81 lists if they produce one of SSA_PROP_INTERESTING or 82 SSA_PROP_VARYING. 83 84 CFG_BLOCKS contains the list of blocks to be simulated. 85 Blocks are added to this list if their incoming edges are 86 found executable. 87 88 VARYING_SSA_EDGES contains the list of statements that feed 89 from statements that produce an SSA_PROP_VARYING result. 90 These are simulated first to speed up processing. 91 92 INTERESTING_SSA_EDGES contains the list of statements that 93 feed from statements that produce an SSA_PROP_INTERESTING 94 result. 95 96 5- Simulation terminates when all three work lists are drained. 97 98 Before calling ssa_propagate, it is important to clear 99 DONT_SIMULATE_AGAIN for all the statements in the program that 100 should be simulated. This initialization allows an implementation 101 to specify which statements should never be simulated. 102 103 It is also important to compute def-use information before calling 104 ssa_propagate. 105 106 References: 107 108 [1] Constant propagation with conditional branches, 109 Wegman and Zadeck, ACM TOPLAS 13(2):181-210. 110 111 [2] Building an Optimizing Compiler, 112 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9. 113 114 [3] Advanced Compiler Design and Implementation, 115 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */ 116 117/* Function pointers used to parameterize the propagation engine. */ 118static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt; 119static ssa_prop_visit_phi_fn ssa_prop_visit_phi; 120 121/* Use the TREE_DEPRECATED bitflag to mark statements that have been 122 added to one of the SSA edges worklists. This flag is used to 123 avoid visiting statements unnecessarily when draining an SSA edge 124 worklist. If while simulating a basic block, we find a statement with 125 STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge 126 processing from visiting it again. */ 127#define STMT_IN_SSA_EDGE_WORKLIST(T) TREE_DEPRECATED (T) 128 129/* A bitmap to keep track of executable blocks in the CFG. */ 130static sbitmap executable_blocks; 131 132/* Array of control flow edges on the worklist. */ 133static GTY(()) varray_type cfg_blocks = NULL; 134 135static unsigned int cfg_blocks_num = 0; 136static int cfg_blocks_tail; 137static int cfg_blocks_head; 138 139static sbitmap bb_in_list; 140 141/* Worklist of SSA edges which will need reexamination as their 142 definition has changed. SSA edges are def-use edges in the SSA 143 web. For each D-U edge, we store the target statement or PHI node 144 U. */ 145static GTY(()) VEC(tree,gc) *interesting_ssa_edges; 146 147/* Identical to INTERESTING_SSA_EDGES. For performance reasons, the 148 list of SSA edges is split into two. One contains all SSA edges 149 who need to be reexamined because their lattice value changed to 150 varying (this worklist), and the other contains all other SSA edges 151 to be reexamined (INTERESTING_SSA_EDGES). 152 153 Since most values in the program are VARYING, the ideal situation 154 is to move them to that lattice value as quickly as possible. 155 Thus, it doesn't make sense to process any other type of lattice 156 value until all VARYING values are propagated fully, which is one 157 thing using the VARYING worklist achieves. In addition, if we 158 don't use a separate worklist for VARYING edges, we end up with 159 situations where lattice values move from 160 UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */ 161static GTY(()) VEC(tree,gc) *varying_ssa_edges; 162 163 164/* Return true if the block worklist empty. */ 165 166static inline bool 167cfg_blocks_empty_p (void) 168{ 169 return (cfg_blocks_num == 0); 170} 171 172 173/* Add a basic block to the worklist. The block must not be already 174 in the worklist, and it must not be the ENTRY or EXIT block. */ 175 176static void 177cfg_blocks_add (basic_block bb) 178{ 179 gcc_assert (bb != ENTRY_BLOCK_PTR && bb != EXIT_BLOCK_PTR); 180 gcc_assert (!TEST_BIT (bb_in_list, bb->index)); 181 182 if (cfg_blocks_empty_p ()) 183 { 184 cfg_blocks_tail = cfg_blocks_head = 0; 185 cfg_blocks_num = 1; 186 } 187 else 188 { 189 cfg_blocks_num++; 190 if (cfg_blocks_num > VARRAY_SIZE (cfg_blocks)) 191 { 192 /* We have to grow the array now. Adjust to queue to occupy the 193 full space of the original array. */ 194 cfg_blocks_tail = VARRAY_SIZE (cfg_blocks); 195 cfg_blocks_head = 0; 196 VARRAY_GROW (cfg_blocks, 2 * VARRAY_SIZE (cfg_blocks)); 197 } 198 else 199 cfg_blocks_tail = (cfg_blocks_tail + 1) % VARRAY_SIZE (cfg_blocks); 200 } 201 202 VARRAY_BB (cfg_blocks, cfg_blocks_tail) = bb; 203 SET_BIT (bb_in_list, bb->index); 204} 205 206 207/* Remove a block from the worklist. */ 208 209static basic_block 210cfg_blocks_get (void) 211{ 212 basic_block bb; 213 214 bb = VARRAY_BB (cfg_blocks, cfg_blocks_head); 215 216 gcc_assert (!cfg_blocks_empty_p ()); 217 gcc_assert (bb); 218 219 cfg_blocks_head = (cfg_blocks_head + 1) % VARRAY_SIZE (cfg_blocks); 220 --cfg_blocks_num; 221 RESET_BIT (bb_in_list, bb->index); 222 223 return bb; 224} 225 226 227/* We have just defined a new value for VAR. If IS_VARYING is true, 228 add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add 229 them to INTERESTING_SSA_EDGES. */ 230 231static void 232add_ssa_edge (tree var, bool is_varying) 233{ 234 imm_use_iterator iter; 235 use_operand_p use_p; 236 237 FOR_EACH_IMM_USE_FAST (use_p, iter, var) 238 { 239 tree use_stmt = USE_STMT (use_p); 240 241 if (!DONT_SIMULATE_AGAIN (use_stmt) 242 && !STMT_IN_SSA_EDGE_WORKLIST (use_stmt)) 243 { 244 STMT_IN_SSA_EDGE_WORKLIST (use_stmt) = 1; 245 if (is_varying) 246 VEC_safe_push (tree, gc, varying_ssa_edges, use_stmt); 247 else 248 VEC_safe_push (tree, gc, interesting_ssa_edges, use_stmt); 249 } 250 } 251} 252 253 254/* Add edge E to the control flow worklist. */ 255 256static void 257add_control_edge (edge e) 258{ 259 basic_block bb = e->dest; 260 if (bb == EXIT_BLOCK_PTR) 261 return; 262 263 /* If the edge had already been executed, skip it. */ 264 if (e->flags & EDGE_EXECUTABLE) 265 return; 266 267 e->flags |= EDGE_EXECUTABLE; 268 269 /* If the block is already in the list, we're done. */ 270 if (TEST_BIT (bb_in_list, bb->index)) 271 return; 272 273 cfg_blocks_add (bb); 274 275 if (dump_file && (dump_flags & TDF_DETAILS)) 276 fprintf (dump_file, "Adding Destination of edge (%d -> %d) to worklist\n\n", 277 e->src->index, e->dest->index); 278} 279 280 281/* Simulate the execution of STMT and update the work lists accordingly. */ 282 283static void 284simulate_stmt (tree stmt) 285{ 286 enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING; 287 edge taken_edge = NULL; 288 tree output_name = NULL_TREE; 289 290 /* Don't bother visiting statements that are already 291 considered varying by the propagator. */ 292 if (DONT_SIMULATE_AGAIN (stmt)) 293 return; 294 295 if (TREE_CODE (stmt) == PHI_NODE) 296 { 297 val = ssa_prop_visit_phi (stmt); 298 output_name = PHI_RESULT (stmt); 299 } 300 else 301 val = ssa_prop_visit_stmt (stmt, &taken_edge, &output_name); 302 303 if (val == SSA_PROP_VARYING) 304 { 305 DONT_SIMULATE_AGAIN (stmt) = 1; 306 307 /* If the statement produced a new varying value, add the SSA 308 edges coming out of OUTPUT_NAME. */ 309 if (output_name) 310 add_ssa_edge (output_name, true); 311 312 /* If STMT transfers control out of its basic block, add 313 all outgoing edges to the work list. */ 314 if (stmt_ends_bb_p (stmt)) 315 { 316 edge e; 317 edge_iterator ei; 318 basic_block bb = bb_for_stmt (stmt); 319 FOR_EACH_EDGE (e, ei, bb->succs) 320 add_control_edge (e); 321 } 322 } 323 else if (val == SSA_PROP_INTERESTING) 324 { 325 /* If the statement produced new value, add the SSA edges coming 326 out of OUTPUT_NAME. */ 327 if (output_name) 328 add_ssa_edge (output_name, false); 329 330 /* If we know which edge is going to be taken out of this block, 331 add it to the CFG work list. */ 332 if (taken_edge) 333 add_control_edge (taken_edge); 334 } 335} 336 337/* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to 338 drain. This pops statements off the given WORKLIST and processes 339 them until there are no more statements on WORKLIST. 340 We take a pointer to WORKLIST because it may be reallocated when an 341 SSA edge is added to it in simulate_stmt. */ 342 343static void 344process_ssa_edge_worklist (VEC(tree,gc) **worklist) 345{ 346 /* Drain the entire worklist. */ 347 while (VEC_length (tree, *worklist) > 0) 348 { 349 basic_block bb; 350 351 /* Pull the statement to simulate off the worklist. */ 352 tree stmt = VEC_pop (tree, *worklist); 353 354 /* If this statement was already visited by simulate_block, then 355 we don't need to visit it again here. */ 356 if (!STMT_IN_SSA_EDGE_WORKLIST (stmt)) 357 continue; 358 359 /* STMT is no longer in a worklist. */ 360 STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0; 361 362 if (dump_file && (dump_flags & TDF_DETAILS)) 363 { 364 fprintf (dump_file, "\nSimulating statement (from ssa_edges): "); 365 print_generic_stmt (dump_file, stmt, dump_flags); 366 } 367 368 bb = bb_for_stmt (stmt); 369 370 /* PHI nodes are always visited, regardless of whether or not 371 the destination block is executable. Otherwise, visit the 372 statement only if its block is marked executable. */ 373 if (TREE_CODE (stmt) == PHI_NODE 374 || TEST_BIT (executable_blocks, bb->index)) 375 simulate_stmt (stmt); 376 } 377} 378 379 380/* Simulate the execution of BLOCK. Evaluate the statement associated 381 with each variable reference inside the block. */ 382 383static void 384simulate_block (basic_block block) 385{ 386 tree phi; 387 388 /* There is nothing to do for the exit block. */ 389 if (block == EXIT_BLOCK_PTR) 390 return; 391 392 if (dump_file && (dump_flags & TDF_DETAILS)) 393 fprintf (dump_file, "\nSimulating block %d\n", block->index); 394 395 /* Always simulate PHI nodes, even if we have simulated this block 396 before. */ 397 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi)) 398 simulate_stmt (phi); 399 400 /* If this is the first time we've simulated this block, then we 401 must simulate each of its statements. */ 402 if (!TEST_BIT (executable_blocks, block->index)) 403 { 404 block_stmt_iterator j; 405 unsigned int normal_edge_count; 406 edge e, normal_edge; 407 edge_iterator ei; 408 409 /* Note that we have simulated this block. */ 410 SET_BIT (executable_blocks, block->index); 411 412 for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j)) 413 { 414 tree stmt = bsi_stmt (j); 415 416 /* If this statement is already in the worklist then 417 "cancel" it. The reevaluation implied by the worklist 418 entry will produce the same value we generate here and 419 thus reevaluating it again from the worklist is 420 pointless. */ 421 if (STMT_IN_SSA_EDGE_WORKLIST (stmt)) 422 STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0; 423 424 simulate_stmt (stmt); 425 } 426 427 /* We can not predict when abnormal edges will be executed, so 428 once a block is considered executable, we consider any 429 outgoing abnormal edges as executable. 430 431 At the same time, if this block has only one successor that is 432 reached by non-abnormal edges, then add that successor to the 433 worklist. */ 434 normal_edge_count = 0; 435 normal_edge = NULL; 436 FOR_EACH_EDGE (e, ei, block->succs) 437 { 438 if (e->flags & EDGE_ABNORMAL) 439 add_control_edge (e); 440 else 441 { 442 normal_edge_count++; 443 normal_edge = e; 444 } 445 } 446 447 if (normal_edge_count == 1) 448 add_control_edge (normal_edge); 449 } 450} 451 452 453/* Initialize local data structures and work lists. */ 454 455static void 456ssa_prop_init (void) 457{ 458 edge e; 459 edge_iterator ei; 460 basic_block bb; 461 size_t i; 462 463 /* Worklists of SSA edges. */ 464 interesting_ssa_edges = VEC_alloc (tree, gc, 20); 465 varying_ssa_edges = VEC_alloc (tree, gc, 20); 466 467 executable_blocks = sbitmap_alloc (last_basic_block); 468 sbitmap_zero (executable_blocks); 469 470 bb_in_list = sbitmap_alloc (last_basic_block); 471 sbitmap_zero (bb_in_list); 472 473 if (dump_file && (dump_flags & TDF_DETAILS)) 474 dump_immediate_uses (dump_file); 475 476 VARRAY_BB_INIT (cfg_blocks, 20, "cfg_blocks"); 477 478 /* Initialize the values for every SSA_NAME. */ 479 for (i = 1; i < num_ssa_names; i++) 480 if (ssa_name (i)) 481 SSA_NAME_VALUE (ssa_name (i)) = NULL_TREE; 482 483 /* Initially assume that every edge in the CFG is not executable. 484 (including the edges coming out of ENTRY_BLOCK_PTR). */ 485 FOR_ALL_BB (bb) 486 { 487 block_stmt_iterator si; 488 489 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 490 STMT_IN_SSA_EDGE_WORKLIST (bsi_stmt (si)) = 0; 491 492 FOR_EACH_EDGE (e, ei, bb->succs) 493 e->flags &= ~EDGE_EXECUTABLE; 494 } 495 496 /* Seed the algorithm by adding the successors of the entry block to the 497 edge worklist. */ 498 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 499 add_control_edge (e); 500} 501 502 503/* Free allocated storage. */ 504 505static void 506ssa_prop_fini (void) 507{ 508 VEC_free (tree, gc, interesting_ssa_edges); 509 VEC_free (tree, gc, varying_ssa_edges); 510 cfg_blocks = NULL; 511 sbitmap_free (bb_in_list); 512 sbitmap_free (executable_blocks); 513} 514 515 516/* Get the main expression from statement STMT. */ 517 518tree 519get_rhs (tree stmt) 520{ 521 enum tree_code code = TREE_CODE (stmt); 522 523 switch (code) 524 { 525 case RETURN_EXPR: 526 stmt = TREE_OPERAND (stmt, 0); 527 if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR) 528 return stmt; 529 /* FALLTHRU */ 530 531 case MODIFY_EXPR: 532 stmt = TREE_OPERAND (stmt, 1); 533 if (TREE_CODE (stmt) == WITH_SIZE_EXPR) 534 return TREE_OPERAND (stmt, 0); 535 else 536 return stmt; 537 538 case COND_EXPR: 539 return COND_EXPR_COND (stmt); 540 case SWITCH_EXPR: 541 return SWITCH_COND (stmt); 542 case GOTO_EXPR: 543 return GOTO_DESTINATION (stmt); 544 case LABEL_EXPR: 545 return LABEL_EXPR_LABEL (stmt); 546 547 default: 548 return stmt; 549 } 550} 551 552 553/* Set the main expression of *STMT_P to EXPR. If EXPR is not a valid 554 GIMPLE expression no changes are done and the function returns 555 false. */ 556 557bool 558set_rhs (tree *stmt_p, tree expr) 559{ 560 tree stmt = *stmt_p, op; 561 enum tree_code code = TREE_CODE (expr); 562 stmt_ann_t ann; 563 tree var; 564 ssa_op_iter iter; 565 566 /* Verify the constant folded result is valid gimple. */ 567 if (TREE_CODE_CLASS (code) == tcc_binary) 568 { 569 if (!is_gimple_val (TREE_OPERAND (expr, 0)) 570 || !is_gimple_val (TREE_OPERAND (expr, 1))) 571 return false; 572 } 573 else if (TREE_CODE_CLASS (code) == tcc_unary) 574 { 575 if (!is_gimple_val (TREE_OPERAND (expr, 0))) 576 return false; 577 } 578 else if (code == ADDR_EXPR) 579 { 580 if (TREE_CODE (TREE_OPERAND (expr, 0)) == ARRAY_REF 581 && !is_gimple_val (TREE_OPERAND (TREE_OPERAND (expr, 0), 1))) 582 return false; 583 } 584 else if (code == COMPOUND_EXPR) 585 return false; 586 587 switch (TREE_CODE (stmt)) 588 { 589 case RETURN_EXPR: 590 op = TREE_OPERAND (stmt, 0); 591 if (TREE_CODE (op) != MODIFY_EXPR) 592 { 593 TREE_OPERAND (stmt, 0) = expr; 594 break; 595 } 596 stmt = op; 597 /* FALLTHRU */ 598 599 case MODIFY_EXPR: 600 op = TREE_OPERAND (stmt, 1); 601 if (TREE_CODE (op) == WITH_SIZE_EXPR) 602 stmt = op; 603 TREE_OPERAND (stmt, 1) = expr; 604 break; 605 606 case COND_EXPR: 607 if (!is_gimple_condexpr (expr)) 608 return false; 609 COND_EXPR_COND (stmt) = expr; 610 break; 611 case SWITCH_EXPR: 612 SWITCH_COND (stmt) = expr; 613 break; 614 case GOTO_EXPR: 615 GOTO_DESTINATION (stmt) = expr; 616 break; 617 case LABEL_EXPR: 618 LABEL_EXPR_LABEL (stmt) = expr; 619 break; 620 621 default: 622 /* Replace the whole statement with EXPR. If EXPR has no side 623 effects, then replace *STMT_P with an empty statement. */ 624 ann = stmt_ann (stmt); 625 *stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt (); 626 (*stmt_p)->common.ann = (tree_ann_t) ann; 627 628 if (in_ssa_p 629 && TREE_SIDE_EFFECTS (expr)) 630 { 631 /* Fix all the SSA_NAMEs created by *STMT_P to point to its new 632 replacement. */ 633 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_DEFS) 634 { 635 if (TREE_CODE (var) == SSA_NAME) 636 SSA_NAME_DEF_STMT (var) = *stmt_p; 637 } 638 } 639 break; 640 } 641 642 return true; 643} 644 645 646/* Entry point to the propagation engine. 647 648 VISIT_STMT is called for every statement visited. 649 VISIT_PHI is called for every PHI node visited. */ 650 651void 652ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt, 653 ssa_prop_visit_phi_fn visit_phi) 654{ 655 ssa_prop_visit_stmt = visit_stmt; 656 ssa_prop_visit_phi = visit_phi; 657 658 ssa_prop_init (); 659 660 /* Iterate until the worklists are empty. */ 661 while (!cfg_blocks_empty_p () 662 || VEC_length (tree, interesting_ssa_edges) > 0 663 || VEC_length (tree, varying_ssa_edges) > 0) 664 { 665 if (!cfg_blocks_empty_p ()) 666 { 667 /* Pull the next block to simulate off the worklist. */ 668 basic_block dest_block = cfg_blocks_get (); 669 simulate_block (dest_block); 670 } 671 672 /* In order to move things to varying as quickly as 673 possible,process the VARYING_SSA_EDGES worklist first. */ 674 process_ssa_edge_worklist (&varying_ssa_edges); 675 676 /* Now process the INTERESTING_SSA_EDGES worklist. */ 677 process_ssa_edge_worklist (&interesting_ssa_edges); 678 } 679 680 ssa_prop_fini (); 681} 682 683 684/* Return the first V_MAY_DEF or V_MUST_DEF operand for STMT. */ 685 686tree 687first_vdef (tree stmt) 688{ 689 ssa_op_iter iter; 690 tree op; 691 692 /* Simply return the first operand we arrive at. */ 693 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS) 694 return (op); 695 696 gcc_unreachable (); 697} 698 699 700/* Return true if STMT is of the form 'LHS = mem_ref', where 'mem_ref' 701 is a non-volatile pointer dereference, a structure reference or a 702 reference to a single _DECL. Ignore volatile memory references 703 because they are not interesting for the optimizers. */ 704 705bool 706stmt_makes_single_load (tree stmt) 707{ 708 tree rhs; 709 710 if (TREE_CODE (stmt) != MODIFY_EXPR) 711 return false; 712 713 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VUSE)) 714 return false; 715 716 rhs = TREE_OPERAND (stmt, 1); 717 STRIP_NOPS (rhs); 718 719 return (!TREE_THIS_VOLATILE (rhs) 720 && (DECL_P (rhs) 721 || REFERENCE_CLASS_P (rhs))); 722} 723 724 725/* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref' 726 is a non-volatile pointer dereference, a structure reference or a 727 reference to a single _DECL. Ignore volatile memory references 728 because they are not interesting for the optimizers. */ 729 730bool 731stmt_makes_single_store (tree stmt) 732{ 733 tree lhs; 734 735 if (TREE_CODE (stmt) != MODIFY_EXPR) 736 return false; 737 738 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF)) 739 return false; 740 741 lhs = TREE_OPERAND (stmt, 0); 742 STRIP_NOPS (lhs); 743 744 return (!TREE_THIS_VOLATILE (lhs) 745 && (DECL_P (lhs) 746 || REFERENCE_CLASS_P (lhs))); 747} 748 749 750/* If STMT makes a single memory load and all the virtual use operands 751 have the same value in array VALUES, return it. Otherwise, return 752 NULL. */ 753 754prop_value_t * 755get_value_loaded_by (tree stmt, prop_value_t *values) 756{ 757 ssa_op_iter i; 758 tree vuse; 759 prop_value_t *prev_val = NULL; 760 prop_value_t *val = NULL; 761 762 FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES) 763 { 764 val = &values[SSA_NAME_VERSION (vuse)]; 765 if (prev_val && prev_val->value != val->value) 766 return NULL; 767 prev_val = val; 768 } 769 770 return val; 771} 772 773 774/* Propagation statistics. */ 775struct prop_stats_d 776{ 777 long num_const_prop; 778 long num_copy_prop; 779 long num_pred_folded; 780}; 781 782static struct prop_stats_d prop_stats; 783 784/* Replace USE references in statement STMT with the values stored in 785 PROP_VALUE. Return true if at least one reference was replaced. If 786 REPLACED_ADDRESSES_P is given, it will be set to true if an address 787 constant was replaced. */ 788 789bool 790replace_uses_in (tree stmt, bool *replaced_addresses_p, 791 prop_value_t *prop_value) 792{ 793 bool replaced = false; 794 use_operand_p use; 795 ssa_op_iter iter; 796 797 FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE) 798 { 799 tree tuse = USE_FROM_PTR (use); 800 tree val = prop_value[SSA_NAME_VERSION (tuse)].value; 801 802 if (val == tuse || val == NULL_TREE) 803 continue; 804 805 if (TREE_CODE (stmt) == ASM_EXPR 806 && !may_propagate_copy_into_asm (tuse)) 807 continue; 808 809 if (!may_propagate_copy (tuse, val)) 810 continue; 811 812 if (TREE_CODE (val) != SSA_NAME) 813 prop_stats.num_const_prop++; 814 else 815 prop_stats.num_copy_prop++; 816 817 propagate_value (use, val); 818 819 replaced = true; 820 if (POINTER_TYPE_P (TREE_TYPE (tuse)) && replaced_addresses_p) 821 *replaced_addresses_p = true; 822 } 823 824 return replaced; 825} 826 827 828/* Replace the VUSE references in statement STMT with the values 829 stored in PROP_VALUE. Return true if a reference was replaced. If 830 REPLACED_ADDRESSES_P is given, it will be set to true if an address 831 constant was replaced. 832 833 Replacing VUSE operands is slightly more complex than replacing 834 regular USEs. We are only interested in two types of replacements 835 here: 836 837 1- If the value to be replaced is a constant or an SSA name for a 838 GIMPLE register, then we are making a copy/constant propagation 839 from a memory store. For instance, 840 841 # a_3 = V_MAY_DEF <a_2> 842 a.b = x_1; 843 ... 844 # VUSE <a_3> 845 y_4 = a.b; 846 847 This replacement is only possible iff STMT is an assignment 848 whose RHS is identical to the LHS of the statement that created 849 the VUSE(s) that we are replacing. Otherwise, we may do the 850 wrong replacement: 851 852 # a_3 = V_MAY_DEF <a_2> 853 # b_5 = V_MAY_DEF <b_4> 854 *p = 10; 855 ... 856 # VUSE <b_5> 857 x_8 = b; 858 859 Even though 'b_5' acquires the value '10' during propagation, 860 there is no way for the propagator to tell whether the 861 replacement is correct in every reached use, because values are 862 computed at definition sites. Therefore, when doing final 863 substitution of propagated values, we have to check each use 864 site. Since the RHS of STMT ('b') is different from the LHS of 865 the originating statement ('*p'), we cannot replace 'b' with 866 '10'. 867 868 Similarly, when merging values from PHI node arguments, 869 propagators need to take care not to merge the same values 870 stored in different locations: 871 872 if (...) 873 # a_3 = V_MAY_DEF <a_2> 874 a.b = 3; 875 else 876 # a_4 = V_MAY_DEF <a_2> 877 a.c = 3; 878 # a_5 = PHI <a_3, a_4> 879 880 It would be wrong to propagate '3' into 'a_5' because that 881 operation merges two stores to different memory locations. 882 883 884 2- If the value to be replaced is an SSA name for a virtual 885 register, then we simply replace each VUSE operand with its 886 value from PROP_VALUE. This is the same replacement done by 887 replace_uses_in. */ 888 889static bool 890replace_vuses_in (tree stmt, bool *replaced_addresses_p, 891 prop_value_t *prop_value) 892{ 893 bool replaced = false; 894 ssa_op_iter iter; 895 use_operand_p vuse; 896 897 if (stmt_makes_single_load (stmt)) 898 { 899 /* If STMT is an assignment whose RHS is a single memory load, 900 see if we are trying to propagate a constant or a GIMPLE 901 register (case #1 above). */ 902 prop_value_t *val = get_value_loaded_by (stmt, prop_value); 903 tree rhs = TREE_OPERAND (stmt, 1); 904 905 if (val 906 && val->value 907 && (is_gimple_reg (val->value) 908 || is_gimple_min_invariant (val->value)) 909 && simple_cst_equal (rhs, val->mem_ref) == 1) 910 911 { 912 /* If we are replacing a constant address, inform our 913 caller. */ 914 if (TREE_CODE (val->value) != SSA_NAME 915 && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))) 916 && replaced_addresses_p) 917 *replaced_addresses_p = true; 918 919 /* We can only perform the substitution if the load is done 920 from the same memory location as the original store. 921 Since we already know that there are no intervening 922 stores between DEF_STMT and STMT, we only need to check 923 that the RHS of STMT is the same as the memory reference 924 propagated together with the value. */ 925 TREE_OPERAND (stmt, 1) = val->value; 926 927 if (TREE_CODE (val->value) != SSA_NAME) 928 prop_stats.num_const_prop++; 929 else 930 prop_stats.num_copy_prop++; 931 932 /* Since we have replaced the whole RHS of STMT, there 933 is no point in checking the other VUSEs, as they will 934 all have the same value. */ 935 return true; 936 } 937 } 938 939 /* Otherwise, the values for every VUSE operand must be other 940 SSA_NAMEs that can be propagated into STMT. */ 941 FOR_EACH_SSA_USE_OPERAND (vuse, stmt, iter, SSA_OP_VIRTUAL_USES) 942 { 943 tree var = USE_FROM_PTR (vuse); 944 tree val = prop_value[SSA_NAME_VERSION (var)].value; 945 946 if (val == NULL_TREE || var == val) 947 continue; 948 949 /* Constants and copies propagated between real and virtual 950 operands are only possible in the cases handled above. They 951 should be ignored in any other context. */ 952 if (is_gimple_min_invariant (val) || is_gimple_reg (val)) 953 continue; 954 955 propagate_value (vuse, val); 956 prop_stats.num_copy_prop++; 957 replaced = true; 958 } 959 960 return replaced; 961} 962 963 964/* Replace propagated values into all the arguments for PHI using the 965 values from PROP_VALUE. */ 966 967static void 968replace_phi_args_in (tree phi, prop_value_t *prop_value) 969{ 970 int i; 971 bool replaced = false; 972 tree prev_phi = NULL; 973 974 if (dump_file && (dump_flags & TDF_DETAILS)) 975 prev_phi = unshare_expr (phi); 976 977 for (i = 0; i < PHI_NUM_ARGS (phi); i++) 978 { 979 tree arg = PHI_ARG_DEF (phi, i); 980 981 if (TREE_CODE (arg) == SSA_NAME) 982 { 983 tree val = prop_value[SSA_NAME_VERSION (arg)].value; 984 985 if (val && val != arg && may_propagate_copy (arg, val)) 986 { 987 if (TREE_CODE (val) != SSA_NAME) 988 prop_stats.num_const_prop++; 989 else 990 prop_stats.num_copy_prop++; 991 992 propagate_value (PHI_ARG_DEF_PTR (phi, i), val); 993 replaced = true; 994 995 /* If we propagated a copy and this argument flows 996 through an abnormal edge, update the replacement 997 accordingly. */ 998 if (TREE_CODE (val) == SSA_NAME 999 && PHI_ARG_EDGE (phi, i)->flags & EDGE_ABNORMAL) 1000 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1; 1001 } 1002 } 1003 } 1004 1005 if (replaced && dump_file && (dump_flags & TDF_DETAILS)) 1006 { 1007 fprintf (dump_file, "Folded PHI node: "); 1008 print_generic_stmt (dump_file, prev_phi, TDF_SLIM); 1009 fprintf (dump_file, " into: "); 1010 print_generic_stmt (dump_file, phi, TDF_SLIM); 1011 fprintf (dump_file, "\n"); 1012 } 1013} 1014 1015 1016/* If STMT has a predicate whose value can be computed using the value 1017 range information computed by VRP, compute its value and return true. 1018 Otherwise, return false. */ 1019 1020static bool 1021fold_predicate_in (tree stmt) 1022{ 1023 tree *pred_p = NULL; 1024 bool modify_expr_p = false; 1025 tree val; 1026 1027 if (TREE_CODE (stmt) == MODIFY_EXPR 1028 && COMPARISON_CLASS_P (TREE_OPERAND (stmt, 1))) 1029 { 1030 modify_expr_p = true; 1031 pred_p = &TREE_OPERAND (stmt, 1); 1032 } 1033 else if (TREE_CODE (stmt) == COND_EXPR) 1034 pred_p = &COND_EXPR_COND (stmt); 1035 else 1036 return false; 1037 1038 val = vrp_evaluate_conditional (*pred_p, true); 1039 if (val) 1040 { 1041 if (modify_expr_p) 1042 val = fold_convert (TREE_TYPE (*pred_p), val); 1043 1044 if (dump_file) 1045 { 1046 fprintf (dump_file, "Folding predicate "); 1047 print_generic_expr (dump_file, *pred_p, 0); 1048 fprintf (dump_file, " to "); 1049 print_generic_expr (dump_file, val, 0); 1050 fprintf (dump_file, "\n"); 1051 } 1052 1053 prop_stats.num_pred_folded++; 1054 *pred_p = val; 1055 return true; 1056 } 1057 1058 return false; 1059} 1060 1061 1062/* Perform final substitution and folding of propagated values. 1063 1064 PROP_VALUE[I] contains the single value that should be substituted 1065 at every use of SSA name N_I. If PROP_VALUE is NULL, no values are 1066 substituted. 1067 1068 If USE_RANGES_P is true, statements that contain predicate 1069 expressions are evaluated with a call to vrp_evaluate_conditional. 1070 This will only give meaningful results when called from tree-vrp.c 1071 (the information used by vrp_evaluate_conditional is built by the 1072 VRP pass). */ 1073 1074void 1075substitute_and_fold (prop_value_t *prop_value, bool use_ranges_p) 1076{ 1077 basic_block bb; 1078 1079 if (prop_value == NULL && !use_ranges_p) 1080 return; 1081 1082 if (dump_file && (dump_flags & TDF_DETAILS)) 1083 fprintf (dump_file, "\nSubstituing values and folding statements\n\n"); 1084 1085 memset (&prop_stats, 0, sizeof (prop_stats)); 1086 1087 /* Substitute values in every statement of every basic block. */ 1088 FOR_EACH_BB (bb) 1089 { 1090 block_stmt_iterator i; 1091 tree phi; 1092 1093 /* Propagate known values into PHI nodes. */ 1094 if (prop_value) 1095 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1096 replace_phi_args_in (phi, prop_value); 1097 1098 for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i)) 1099 { 1100 bool replaced_address, did_replace; 1101 tree prev_stmt = NULL; 1102 tree stmt = bsi_stmt (i); 1103 1104 /* Ignore ASSERT_EXPRs. They are used by VRP to generate 1105 range information for names and they are discarded 1106 afterwards. */ 1107 if (TREE_CODE (stmt) == MODIFY_EXPR 1108 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR) 1109 continue; 1110 1111 /* Replace the statement with its folded version and mark it 1112 folded. */ 1113 did_replace = false; 1114 replaced_address = false; 1115 if (dump_file && (dump_flags & TDF_DETAILS)) 1116 prev_stmt = unshare_expr (stmt); 1117 1118 /* If we have range information, see if we can fold 1119 predicate expressions. */ 1120 if (use_ranges_p) 1121 { 1122 did_replace = fold_predicate_in (stmt); 1123 1124 /* Some statements may be simplified using ranges. For 1125 example, division may be replaced by shifts, modulo 1126 replaced with bitwise and, etc. */ 1127 simplify_stmt_using_ranges (stmt); 1128 } 1129 1130 if (prop_value) 1131 { 1132 /* Only replace real uses if we couldn't fold the 1133 statement using value range information (value range 1134 information is not collected on virtuals, so we only 1135 need to check this for real uses). */ 1136 if (!did_replace) 1137 did_replace |= replace_uses_in (stmt, &replaced_address, 1138 prop_value); 1139 1140 did_replace |= replace_vuses_in (stmt, &replaced_address, 1141 prop_value); 1142 } 1143 1144 /* If we made a replacement, fold and cleanup the statement. */ 1145 if (did_replace) 1146 { 1147 tree old_stmt = stmt; 1148 tree rhs; 1149 1150 fold_stmt (bsi_stmt_ptr (i)); 1151 stmt = bsi_stmt (i); 1152 1153 /* If we folded a builtin function, we'll likely 1154 need to rename VDEFs. */ 1155 mark_new_vars_to_rename (stmt); 1156 1157 /* If we cleaned up EH information from the statement, 1158 remove EH edges. */ 1159 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) 1160 tree_purge_dead_eh_edges (bb); 1161 1162 rhs = get_rhs (stmt); 1163 if (TREE_CODE (rhs) == ADDR_EXPR) 1164 recompute_tree_invarant_for_addr_expr (rhs); 1165 1166 if (dump_file && (dump_flags & TDF_DETAILS)) 1167 { 1168 fprintf (dump_file, "Folded statement: "); 1169 print_generic_stmt (dump_file, prev_stmt, TDF_SLIM); 1170 fprintf (dump_file, " into: "); 1171 print_generic_stmt (dump_file, stmt, TDF_SLIM); 1172 fprintf (dump_file, "\n"); 1173 } 1174 } 1175 } 1176 } 1177 1178 if (dump_file && (dump_flags & TDF_STATS)) 1179 { 1180 fprintf (dump_file, "Constants propagated: %6ld\n", 1181 prop_stats.num_const_prop); 1182 fprintf (dump_file, "Copies propagated: %6ld\n", 1183 prop_stats.num_copy_prop); 1184 fprintf (dump_file, "Predicates folded: %6ld\n", 1185 prop_stats.num_pred_folded); 1186 } 1187} 1188 1189#include "gt-tree-ssa-propagate.h" 1190