gcc/tree-ssa-propagate.c

   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, 59 Temple Place - Suite 330, Boston, MA
  20    02111-1307, 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.  */
 118 static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt;
 119 static 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.  */
 130 static sbitmap executable_blocks;
 131
 132 /* Array of control flow edges on the worklist.  */
 133 static GTY(()) varray_type cfg_blocks = NULL;
 134
 135 static unsigned int cfg_blocks_num = 0;
 136 static int cfg_blocks_tail;
 137 static int cfg_blocks_head;
 138
 139 static 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.  */
 145 static 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.  */
 161 static GTY(()) VEC(tree,gc) *varying_ssa_edges;
 162
 163
 164 /* Return true if the block worklist empty.  */
 165
 166 static inline bool
 167 cfg_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
 176 static void
 177 cfg_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
 209 static basic_block
 210 cfg_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
 231 static void
 232 add_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
 256 static void
 257 add_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
 283 static void
 284 simulate_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
 343 static void
 344 process_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
 383 static void
 384 simulate_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
 455 static void
 456 ssa_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
 505 static void
 506 ssa_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
 518 tree
 519 get_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
 557 bool
 558 set_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       COND_EXPR_COND (stmt) = expr;
 608       break;
 609     case SWITCH_EXPR:
 610       SWITCH_COND (stmt) = expr;
 611       break;
 612     case GOTO_EXPR:
 613       GOTO_DESTINATION (stmt) = expr;
 614       break;
 615     case LABEL_EXPR:
 616       LABEL_EXPR_LABEL (stmt) = expr;
 617       break;
 618
 619     default:
 620       /* Replace the whole statement with EXPR.  If EXPR has no side
 621          effects, then replace *STMT_P with an empty statement.  */
 622       ann = stmt_ann (stmt);
 623       *stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt ();
 624       (*stmt_p)->common.ann = (tree_ann_t) ann;
 625
 626       if (TREE_SIDE_EFFECTS (expr))
 627         {
 628           /* Fix all the SSA_NAMEs created by *STMT_P to point to its new
 629              replacement.  */
 630           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_DEFS)
 631             {
 632               if (TREE_CODE (var) == SSA_NAME)
 633                 SSA_NAME_DEF_STMT (var) = *stmt_p;
 634             }
 635         }
 636       break;
 637     }
 638
 639   return true;
 640 }
 641
 642
 643 /* Entry point to the propagation engine.
 644
 645    VISIT_STMT is called for every statement visited.
 646    VISIT_PHI is called for every PHI node visited.  */
 647
 648 void
 649 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt,
 650                ssa_prop_visit_phi_fn visit_phi)
 651 {
 652   ssa_prop_visit_stmt = visit_stmt;
 653   ssa_prop_visit_phi = visit_phi;
 654
 655   ssa_prop_init ();
 656
 657   /* Iterate until the worklists are empty.  */
 658   while (!cfg_blocks_empty_p ()
 659          || VEC_length (tree, interesting_ssa_edges) > 0
 660          || VEC_length (tree, varying_ssa_edges) > 0)
 661     {
 662       if (!cfg_blocks_empty_p ())
 663         {
 664           /* Pull the next block to simulate off the worklist.  */
 665           basic_block dest_block = cfg_blocks_get ();
 666           simulate_block (dest_block);
 667         }
 668
 669       /* In order to move things to varying as quickly as
 670          possible,process the VARYING_SSA_EDGES worklist first.  */
 671       process_ssa_edge_worklist (&varying_ssa_edges);
 672
 673       /* Now process the INTERESTING_SSA_EDGES worklist.  */
 674       process_ssa_edge_worklist (&interesting_ssa_edges);
 675     }
 676
 677   ssa_prop_fini ();
 678 }
 679
 680
 681 /* Return the first V_MAY_DEF or V_MUST_DEF operand for STMT.  */
 682
 683 tree
 684 first_vdef (tree stmt)
 685 {
 686   ssa_op_iter iter;
 687   tree op;
 688
 689   /* Simply return the first operand we arrive at.  */
 690   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
 691     return (op);
 692
 693   gcc_unreachable ();
 694 }
 695
 696
 697 /* Return true if STMT is of the form 'LHS = mem_ref', where 'mem_ref'
 698    is a non-volatile pointer dereference, a structure reference or a
 699    reference to a single _DECL.  Ignore volatile memory references
 700    because they are not interesting for the optimizers.  */
 701
 702 bool
 703 stmt_makes_single_load (tree stmt)
 704 {
 705   tree rhs;
 706
 707   if (TREE_CODE (stmt) != MODIFY_EXPR)
 708     return false;
 709
 710   if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VUSE))
 711     return false;
 712
 713   rhs = TREE_OPERAND (stmt, 1);
 714   STRIP_NOPS (rhs);
 715
 716   return (!TREE_THIS_VOLATILE (rhs)
 717           && (DECL_P (rhs)
 718               || REFERENCE_CLASS_P (rhs)));
 719 }
 720
 721
 722 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
 723    is a non-volatile pointer dereference, a structure reference or a
 724    reference to a single _DECL.  Ignore volatile memory references
 725    because they are not interesting for the optimizers.  */
 726
 727 bool
 728 stmt_makes_single_store (tree stmt)
 729 {
 730   tree lhs;
 731
 732   if (TREE_CODE (stmt) != MODIFY_EXPR)
 733     return false;
 734
 735   if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF))
 736     return false;
 737
 738   lhs = TREE_OPERAND (stmt, 0);
 739   STRIP_NOPS (lhs);
 740
 741   return (!TREE_THIS_VOLATILE (lhs)
 742           && (DECL_P (lhs)
 743               || REFERENCE_CLASS_P (lhs)));
 744 }
 745
 746
 747 /* If STMT makes a single memory load and all the virtual use operands
 748    have the same value in array VALUES, return it.  Otherwise, return
 749    NULL.  */
 750
 751 prop_value_t *
 752 get_value_loaded_by (tree stmt, prop_value_t *values)
 753 {
 754   ssa_op_iter i;
 755   tree vuse;
 756   prop_value_t *prev_val = NULL;
 757   prop_value_t *val = NULL;
 758
 759   FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES)
 760     {
 761       val = &values[SSA_NAME_VERSION (vuse)];
 762       if (prev_val && prev_val->value != val->value)
 763         return NULL;
 764       prev_val = val;
 765     }
 766
 767   return val;
 768 }
 769
 770
 771 /* Propagation statistics.  */
 772 struct prop_stats_d
 773 {
 774   long num_const_prop;
 775   long num_copy_prop;
 776 };
 777
 778 static struct prop_stats_d prop_stats;
 779
 780 /* Replace USE references in statement STMT with the values stored in
 781    PROP_VALUE. Return true if at least one reference was replaced.  If
 782    REPLACED_ADDRESSES_P is given, it will be set to true if an address
 783    constant was replaced.  */
 784
 785 bool
 786 replace_uses_in (tree stmt, bool *replaced_addresses_p,
 787                  prop_value_t *prop_value)
 788 {
 789   bool replaced = false;
 790   use_operand_p use;
 791   ssa_op_iter iter;
 792
 793   FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
 794     {
 795       tree tuse = USE_FROM_PTR (use);
 796       tree val = prop_value[SSA_NAME_VERSION (tuse)].value;
 797
 798       if (val == tuse || val == NULL_TREE)
 799         continue;
 800
 801       if (TREE_CODE (stmt) == ASM_EXPR
 802           && !may_propagate_copy_into_asm (tuse))
 803         continue;
 804
 805       if (!may_propagate_copy (tuse, val))
 806         continue;
 807
 808       if (TREE_CODE (val) != SSA_NAME)
 809         prop_stats.num_const_prop++;
 810       else
 811         prop_stats.num_copy_prop++;
 812
 813       propagate_value (use, val);
 814
 815       replaced = true;
 816       if (POINTER_TYPE_P (TREE_TYPE (tuse)) && replaced_addresses_p)
 817         *replaced_addresses_p = true;
 818     }
 819
 820   return replaced;
 821 }
 822
 823
 824 /* Replace the VUSE references in statement STMT with the values
 825    stored in PROP_VALUE.  Return true if a reference was replaced.  If
 826    REPLACED_ADDRESSES_P is given, it will be set to true if an address
 827    constant was replaced.
 828
 829    Replacing VUSE operands is slightly more complex than replacing
 830    regular USEs.  We are only interested in two types of replacements
 831    here:
 832
 833    1- If the value to be replaced is a constant or an SSA name for a
 834       GIMPLE register, then we are making a copy/constant propagation
 835       from a memory store.  For instance,
 836
 837         # a_3 = V_MAY_DEF <a_2>
 838         a.b = x_1;
 839         ...
 840         # VUSE <a_3>
 841         y_4 = a.b;
 842
 843       This replacement is only possible iff STMT is an assignment
 844       whose RHS is identical to the LHS of the statement that created
 845       the VUSE(s) that we are replacing.  Otherwise, we may do the
 846       wrong replacement:
 847
 848         # a_3 = V_MAY_DEF <a_2>
 849         # b_5 = V_MAY_DEF <b_4>
 850         *p = 10;
 851         ...
 852         # VUSE <b_5>
 853         x_8 = b;
 854
 855       Even though 'b_5' acquires the value '10' during propagation,
 856       there is no way for the propagator to tell whether the
 857       replacement is correct in every reached use, because values are
 858       computed at definition sites.  Therefore, when doing final
 859       substitution of propagated values, we have to check each use
 860       site.  Since the RHS of STMT ('b') is different from the LHS of
 861       the originating statement ('*p'), we cannot replace 'b' with
 862       '10'.
 863
 864       Similarly, when merging values from PHI node arguments,
 865       propagators need to take care not to merge the same values
 866       stored in different locations:
 867
 868                 if (...)
 869                   # a_3 = V_MAY_DEF <a_2>
 870                   a.b = 3;
 871                 else
 872                   # a_4 = V_MAY_DEF <a_2>
 873                   a.c = 3;
 874                 # a_5 = PHI <a_3, a_4>
 875
 876       It would be wrong to propagate '3' into 'a_5' because that
 877       operation merges two stores to different memory locations.
 878
 879
 880    2- If the value to be replaced is an SSA name for a virtual
 881       register, then we simply replace each VUSE operand with its
 882       value from PROP_VALUE.  This is the same replacement done by
 883       replace_uses_in.  */
 884
 885 static bool
 886 replace_vuses_in (tree stmt, bool *replaced_addresses_p,
 887                   prop_value_t *prop_value)
 888 {
 889   bool replaced = false;
 890   ssa_op_iter iter;
 891   use_operand_p vuse;
 892
 893   if (stmt_makes_single_load (stmt))
 894     {
 895       /* If STMT is an assignment whose RHS is a single memory load,
 896          see if we are trying to propagate a constant or a GIMPLE
 897          register (case #1 above).  */
 898       prop_value_t *val = get_value_loaded_by (stmt, prop_value);
 899       tree rhs = TREE_OPERAND (stmt, 1);
 900
 901       if (val
 902           && val->value
 903           && (is_gimple_reg (val->value)
 904               || is_gimple_min_invariant (val->value))
 905           && simple_cst_equal (rhs, val->mem_ref) == 1)
 906
 907         {
 908           /* If we are replacing a constant address, inform our
 909              caller.  */
 910           if (TREE_CODE (val->value) != SSA_NAME
 911               && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1)))
 912               && replaced_addresses_p)
 913             *replaced_addresses_p = true;
 914
 915           /* We can only perform the substitution if the load is done
 916              from the same memory location as the original store.
 917              Since we already know that there are no intervening
 918              stores between DEF_STMT and STMT, we only need to check
 919              that the RHS of STMT is the same as the memory reference
 920              propagated together with the value.  */
 921           TREE_OPERAND (stmt, 1) = val->value;
 922
 923           if (TREE_CODE (val->value) != SSA_NAME)
 924             prop_stats.num_const_prop++;
 925           else
 926             prop_stats.num_copy_prop++;
 927
 928           /* Since we have replaced the whole RHS of STMT, there
 929              is no point in checking the other VUSEs, as they will
 930              all have the same value.  */
 931           return true;
 932         }
 933     }
 934
 935   /* Otherwise, the values for every VUSE operand must be other
 936      SSA_NAMEs that can be propagated into STMT.  */
 937   FOR_EACH_SSA_USE_OPERAND (vuse, stmt, iter, SSA_OP_VIRTUAL_USES)
 938     {
 939       tree var = USE_FROM_PTR (vuse);
 940       tree val = prop_value[SSA_NAME_VERSION (var)].value;
 941
 942       if (val == NULL_TREE || var == val)
 943         continue;
 944
 945       /* Constants and copies propagated between real and virtual
 946          operands are only possible in the cases handled above.  They
 947          should be ignored in any other context.  */
 948       if (is_gimple_min_invariant (val) || is_gimple_reg (val))
 949         continue;
 950
 951       propagate_value (vuse, val);
 952       prop_stats.num_copy_prop++;
 953       replaced = true;
 954     }
 955
 956   return replaced;
 957 }
 958
 959
 960 /* Replace propagated values into all the arguments for PHI using the
 961    values from PROP_VALUE.  */
 962
 963 static void
 964 replace_phi_args_in (tree phi, prop_value_t *prop_value)
 965 {
 966   int i;
 967
 968   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
 969     {
 970       tree arg = PHI_ARG_DEF (phi, i);
 971
 972       if (TREE_CODE (arg) == SSA_NAME)
 973         {
 974           tree val = prop_value[SSA_NAME_VERSION (arg)].value;
 975
 976           if (val && val != arg && may_propagate_copy (arg, val))
 977             {
 978               if (TREE_CODE (val) != SSA_NAME)
 979                 prop_stats.num_const_prop++;
 980               else
 981                 prop_stats.num_copy_prop++;
 982
 983               propagate_value (PHI_ARG_DEF_PTR (phi, i), val);
 984
 985               /* If we propagated a copy and this argument flows
 986                  through an abnormal edge, update the replacement
 987                  accordingly.  */
 988               if (TREE_CODE (val) == SSA_NAME
 989                   && PHI_ARG_EDGE (phi, i)->flags & EDGE_ABNORMAL)
 990                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
 991             }
 992         }
 993     }
 994 }
 995
 996
 997 /* Perform final substitution and folding of propagated values.  */
 998
 999 void
1000 substitute_and_fold (prop_value_t *prop_value)
1001 {
1002   basic_block bb;
1003
1004   if (dump_file && (dump_flags & TDF_DETAILS))
1005     fprintf (dump_file,
1006              "\nSubstituing values and folding statements\n\n");
1007
1008   memset (&prop_stats, 0, sizeof (prop_stats));
1009
1010   /* Substitute values in every statement of every basic block.  */
1011   FOR_EACH_BB (bb)
1012     {
1013       block_stmt_iterator i;
1014       tree phi;
1015
1016       /* Propagate our known values into PHI nodes.  */
1017       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1018         {
1019           if (dump_file && (dump_flags & TDF_DETAILS))
1020             {
1021               fprintf (dump_file, "Replaced ");
1022               print_generic_stmt (dump_file, phi, TDF_SLIM);
1023             }
1024
1025           replace_phi_args_in (phi, prop_value);
1026
1027           if (dump_file && (dump_flags & TDF_DETAILS))
1028             {
1029               fprintf (dump_file, " with ");
1030               print_generic_stmt (dump_file, phi, TDF_SLIM);
1031               fprintf (dump_file, "\n");
1032             }
1033         }
1034
1035       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
1036         {
1037           bool replaced_address, did_replace;
1038           tree stmt = bsi_stmt (i);
1039
1040           /* Replace the statement with its folded version and mark it
1041              folded.  */
1042           if (dump_file && (dump_flags & TDF_DETAILS))
1043             {
1044               fprintf (dump_file, "Replaced ");
1045               print_generic_stmt (dump_file, stmt, TDF_SLIM);
1046             }
1047
1048           replaced_address = false;
1049           did_replace = replace_uses_in (stmt, &replaced_address, prop_value);
1050           did_replace |= replace_vuses_in (stmt, &replaced_address, prop_value);
1051           if (did_replace)
1052             {
1053               tree old_stmt = stmt;
1054               tree rhs;
1055
1056               fold_stmt (bsi_stmt_ptr (i));
1057               stmt = bsi_stmt (i);
1058
1059               /* If we folded a builtin function, we'll likely
1060                  need to rename VDEFs.  */
1061               mark_new_vars_to_rename (stmt);
1062
1063               /* If we cleaned up EH information from the statement,
1064                  remove EH edges.  */
1065               if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
1066                 tree_purge_dead_eh_edges (bb);
1067
1068               rhs = get_rhs (stmt);
1069               if (TREE_CODE (rhs) == ADDR_EXPR)
1070                 recompute_tree_invarant_for_addr_expr (rhs);
1071             }
1072
1073           if (dump_file && (dump_flags & TDF_DETAILS))
1074             {
1075               fprintf (dump_file, " with ");
1076               print_generic_stmt (dump_file, stmt, TDF_SLIM);
1077               fprintf (dump_file, "\n");
1078             }
1079         }
1080     }
1081
1082   if (dump_file && (dump_flags & TDF_STATS))
1083     {
1084       fprintf (dump_file, "Constants propagated: %6ld\n",
1085                prop_stats.num_const_prop);
1086       fprintf (dump_file, "Copies propagated:    %6ld\n",
1087                prop_stats.num_copy_prop);
1088     }
1089 }
1090 #include "gt-tree-ssa-propagate.h"