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