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