gcc/ssa-ccp.c

   1 /* Conditional constant propagation pass for the GNU compiler.
   2    Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc.
   3    Original framework by Daniel Berlin <dan@cgsoftware.com>
   4    Fleshed out and major cleanups by Jeff Law <law@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  21 02111-1307, USA.  */
  22
  23 /* Conditional constant propagation.
  24
  25    References:
  26
  27      Constant propagation with conditional branches,
  28      Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
  29
  30      Building an Optimizing Compiler,
  31      Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
  32
  33      Advanced Compiler Design and Implementation,
  34      Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6
  35
  36    The overall structure is as follows:
  37
  38         1. Run a simple SSA based DCE pass to remove any dead code.
  39         2. Run CCP to compute what registers are known constants
  40            and what edges are not executable.  Remove unexecutable
  41            edges from the CFG and simplify PHI nodes.
  42         3. Replace registers with constants where possible.
  43         4. Remove unreachable blocks computed in step #2.
  44         5. Another simple SSA DCE pass to remove dead code exposed
  45            by CCP.
  46
  47    When we exit, we are still in SSA form.
  48
  49
  50    Potential further enhancements:
  51
  52     1. Handle SUBREGs, STRICT_LOW_PART, etc in destinations more
  53        gracefully.
  54
  55     2. Handle insns with multiple outputs more gracefully.
  56
  57     3. Handle CONST_DOUBLE and symbolic constants.
  58
  59     4. Fold expressions after performing constant substitutions.  */
  60
  61
  62 #include "config.h"
  63 #include "system.h"
  64 #include "coretypes.h"
  65 #include "tm.h"
  66
  67 #include "rtl.h"
  68 #include "hard-reg-set.h"
  69 #include "basic-block.h"
  70 #include "ssa.h"
  71 #include "insn-config.h"
  72 #include "recog.h"
  73 #include "output.h"
  74 #include "errors.h"
  75 #include "ggc.h"
  76 #include "df.h"
  77 #include "function.h"
  78 \f
  79 /* Possible lattice values.  */
  80
  81 typedef enum
  82 {
  83   UNDEFINED,
  84   CONSTANT,
  85   VARYING
  86 } latticevalue;
  87
  88 /* Main structure for CCP.
  89
  90    Contains the lattice value and, if it's a constant, the constant
  91    value.  */
  92 typedef struct
  93 {
  94   latticevalue lattice_val;
  95   rtx const_value;
  96 } value;
  97
  98 /* Array of values indexed by register number.  */
  99 static value *values;
 100
 101 /* A bitmap to keep track of executable blocks in the CFG.  */
 102 static sbitmap executable_blocks;
 103
 104 /* A bitmap for all executable edges in the CFG.  */
 105 static sbitmap executable_edges;
 106
 107 /* Array of edges on the work list.  */
 108 static edge *edge_info;
 109
 110 /* We need an edge list to be able to get indexes easily.  */
 111 static struct edge_list *edges;
 112
 113 /* For building/following use-def and def-use chains.  */
 114 static struct df *df_analyzer;
 115
 116 /* Current edge we are operating on, from the worklist */
 117 static edge flow_edges;
 118
 119 /* Bitmap of SSA edges which will need reexamination as their definition
 120    has changed.  */
 121 static sbitmap ssa_edges;
 122
 123 /* Simple macros to simplify code */
 124 #define SSA_NAME(x) REGNO (SET_DEST (x))
 125 #define EIE(x,y) EDGE_INDEX (edges, x, y)
 126
 127 static void visit_phi_node             PARAMS ((rtx, basic_block));
 128 static void visit_expression           PARAMS ((rtx, basic_block));
 129 static void defs_to_undefined          PARAMS ((rtx));
 130 static void defs_to_varying            PARAMS ((rtx));
 131 static void examine_flow_edges         PARAMS ((void));
 132 static int mark_references             PARAMS ((rtx *, void *));
 133 static void follow_def_use_chains      PARAMS ((void));
 134 static void optimize_unexecutable_edges PARAMS ((struct edge_list *, sbitmap));
 135 static void ssa_ccp_substitute_constants PARAMS ((void));
 136 static void ssa_ccp_df_delete_unreachable_insns PARAMS ((void));
 137 static void ssa_fast_dce PARAMS ((struct df *));
 138
 139 /* Loop through the PHI_NODE's parameters for BLOCK and compare their
 140    lattice values to determine PHI_NODE's lattice value.  */
 141 static void
 142 visit_phi_node (phi_node, block)
 143      rtx phi_node;
 144      basic_block block;
 145 {
 146   unsigned int i;
 147   rtx phi_node_expr = NULL;
 148   unsigned int phi_node_name = SSA_NAME (PATTERN (phi_node));
 149   latticevalue phi_node_lattice_val = UNDEFINED;
 150   rtx pat = PATTERN (phi_node);
 151   rtvec phi_vec = XVEC (SET_SRC (pat), 0);
 152   unsigned int num_elem = GET_NUM_ELEM (phi_vec);
 153
 154   for (i = 0; i < num_elem; i += 2)
 155     {
 156       if (TEST_BIT (executable_edges,
 157                     EIE (BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec, i + 1))),
 158                          block)))
 159         {
 160           unsigned int current_parm
 161             = REGNO (RTVEC_ELT (phi_vec, i));
 162
 163           latticevalue current_parm_lattice_val
 164             = values[current_parm].lattice_val;
 165
 166           /* If any node is VARYING, then new value of PHI_NODE
 167              is VARYING.  */
 168           if (current_parm_lattice_val == VARYING)
 169             {
 170               phi_node_lattice_val = VARYING;
 171               phi_node_expr = NULL;
 172               break;
 173             }
 174
 175           /* If we have more than one distinct constant, then the new
 176              value of PHI_NODE is VARYING.  */
 177           if (current_parm_lattice_val == CONSTANT
 178               && phi_node_lattice_val == CONSTANT
 179               && values[current_parm].const_value != phi_node_expr)
 180             {
 181               phi_node_lattice_val = VARYING;
 182               phi_node_expr = NULL;
 183               break;
 184             }
 185
 186           /* If the current value of PHI_NODE is UNDEFINED and one
 187              node in PHI_NODE is CONSTANT, then the new value of the
 188              PHI is that CONSTANT.  Note this can turn into VARYING
 189              if we find another distinct constant later.  */
 190           if (phi_node_lattice_val == UNDEFINED
 191               && phi_node_expr == NULL
 192               && current_parm_lattice_val == CONSTANT)
 193             {
 194               phi_node_expr = values[current_parm].const_value;
 195               phi_node_lattice_val = CONSTANT;
 196               continue;
 197             }
 198         }
 199     }
 200
 201   /* If the value of PHI_NODE changed, then we will need to
 202      re-execute uses of the output of PHI_NODE.  */
 203   if (phi_node_lattice_val != values[phi_node_name].lattice_val)
 204     {
 205       values[phi_node_name].lattice_val = phi_node_lattice_val;
 206       values[phi_node_name].const_value = phi_node_expr;
 207       SET_BIT (ssa_edges, phi_node_name);
 208     }
 209 }
 210
 211 /* Sets all defs in an insn to UNDEFINED.  */
 212 static void
 213 defs_to_undefined (insn)
 214      rtx insn;
 215 {
 216   struct df_link *currdef;
 217   for (currdef = DF_INSN_DEFS (df_analyzer, insn); currdef;
 218        currdef = currdef->next)
 219     {
 220       if (values[DF_REF_REGNO (currdef->ref)].lattice_val != UNDEFINED)
 221         SET_BIT (ssa_edges, DF_REF_REGNO (currdef->ref));
 222       values[DF_REF_REGNO (currdef->ref)].lattice_val = UNDEFINED;
 223     }
 224 }
 225
 226 /* Sets all defs in an insn to VARYING.  */
 227 static void
 228 defs_to_varying (insn)
 229      rtx insn;
 230 {
 231   struct df_link *currdef;
 232   for (currdef = DF_INSN_DEFS (df_analyzer, insn); currdef;
 233        currdef = currdef->next)
 234     {
 235       if (values[DF_REF_REGNO (currdef->ref)].lattice_val != VARYING)
 236         SET_BIT (ssa_edges, DF_REF_REGNO (currdef->ref));
 237       values[DF_REF_REGNO (currdef->ref)].lattice_val = VARYING;
 238     }
 239 }
 240
 241 /* Go through the expression, call the appropriate evaluation routines
 242    to attempt cprop */
 243 static void
 244 visit_expression (insn, block)
 245      rtx insn;
 246      basic_block block;
 247 {
 248   rtx src, dest, set;
 249
 250
 251   /* Ugh.  CALL_INSNs may end a basic block and have multiple edges
 252      leading out from them.
 253
 254      Mark all the outgoing edges as executable, then fall into the
 255      normal processing below.  */
 256   if (GET_CODE (insn) == CALL_INSN && block->end == insn)
 257     {
 258       edge curredge;
 259
 260       for (curredge = block->succ; curredge;
 261            curredge = curredge->succ_next)
 262         {
 263           int index = EIE (curredge->src, curredge->dest);
 264
 265           if (TEST_BIT (executable_edges, index))
 266             continue;
 267
 268           SET_BIT (executable_edges, index);
 269           edge_info[index] = flow_edges;
 270           flow_edges = curredge;
 271         }
 272     }
 273
 274   set = single_set (insn);
 275   if (! set)
 276     {
 277       defs_to_varying (insn);
 278       return;
 279     }
 280
 281   src = SET_SRC (set);
 282   dest = SET_DEST (set);
 283
 284   /* We may want to refine this some day.  */
 285   if (GET_CODE (dest) != REG && dest != pc_rtx)
 286     {
 287       defs_to_varying (insn);
 288       return;
 289     }
 290
 291   /* Hard registers are not put in SSA form and thus we must consider
 292      them varying.  All the more reason to avoid hard registers in
 293      RTL until as late as possible in the compilation.  */
 294   if (GET_CODE (dest) == REG && REGNO (dest) < FIRST_PSEUDO_REGISTER)
 295     {
 296       defs_to_varying (insn);
 297       return;
 298     }
 299
 300   /* If this is assigning DEST to a constant, record that fact.  */
 301   if (GET_CODE (src) == CONST_INT && GET_CODE (insn) == INSN)
 302     {
 303       unsigned int resultreg = REGNO (dest);
 304
 305       values[resultreg].lattice_val = CONSTANT;
 306       values[resultreg].const_value = SET_SRC (PATTERN (insn));
 307       SET_BIT (ssa_edges, resultreg);
 308     }
 309
 310   /* If this is a copy operation, then we can copy the lattice values.  */
 311   else if (GET_CODE (src) == REG && GET_CODE (dest) == REG)
 312     {
 313       unsigned int old_value = REGNO (src);
 314       latticevalue old_lattice_value = values[old_value].lattice_val;
 315       unsigned int new_value = REGNO (dest);
 316
 317       /* Unless the lattice value is going to change, don't bother
 318          adding the "new value" into the worklist.  */
 319       if (values[new_value].lattice_val != old_lattice_value
 320           || values[new_value].const_value != values[old_value].const_value)
 321         SET_BIT (ssa_edges, new_value);
 322
 323       /* Copy the old lattice node info into the new value lattice node.  */
 324       values[new_value].lattice_val = old_lattice_value;
 325       values[new_value].const_value = values[old_value].const_value;
 326     }
 327
 328   /* Handle jumps.  */
 329   else if (GET_CODE (insn) == JUMP_INSN)
 330     {
 331       rtx x = pc_set (insn);
 332       if (GET_CODE (src) != IF_THEN_ELSE)
 333         {
 334           edge curredge;
 335
 336           /* This is a computed jump, table jump, or an unconditional
 337              jump.  For all these cases we want to mark all successor
 338              blocks as executable if they have not already been
 339              marked.
 340
 341              One day we may try do better with swtich tables and
 342              other computed jumps.  */
 343           for (curredge = block->succ; curredge;
 344                curredge = curredge->succ_next)
 345             {
 346               int index = EIE (curredge->src, curredge->dest);
 347
 348               if (TEST_BIT (executable_edges, index))
 349                 continue;
 350
 351               SET_BIT (executable_edges, index);
 352               edge_info[index] = flow_edges;
 353               flow_edges = curredge;
 354             }
 355         }
 356       else
 357         {
 358           edge curredge;
 359           enum rtx_code comparison_code;
 360           rtx comparison_src0;
 361           rtx comparison_src1;
 362
 363           comparison_code = GET_CODE (XEXP (src, 0));
 364           comparison_src0 = XEXP (XEXP (src, 0), 0);
 365           comparison_src1 = XEXP (XEXP (src, 0), 1);
 366
 367           /* If either operand is undefined, then there is nothing to
 368              do right now.  If/when operands are later defined we will
 369              revaluate the condition and take the appropriate action.  */
 370           if ((GET_CODE (comparison_src0) == REG
 371                && values[REGNO (comparison_src0)].lattice_val == UNDEFINED)
 372               || (GET_CODE (comparison_src1) == REG
 373                   && values[REGNO (comparison_src1)].lattice_val == UNDEFINED))
 374             return;
 375
 376           /* If either operand is varying, then we must consider all
 377              paths as executable.  */
 378           if ((GET_CODE (comparison_src0) == REG
 379                && values[REGNO (comparison_src0)].lattice_val == VARYING)
 380               || (GET_CODE (comparison_src1) == REG
 381                   && values[REGNO (comparison_src1)].lattice_val == VARYING))
 382             {
 383               for (curredge = block->succ; curredge;
 384                    curredge = curredge->succ_next)
 385                 {
 386                   int index = EIE (curredge->src, curredge->dest);
 387
 388                   if (TEST_BIT (executable_edges, index))
 389                     continue;
 390
 391                   SET_BIT (executable_edges, index);
 392                   edge_info[index] = flow_edges;
 393                   flow_edges = curredge;
 394                 }
 395               return;
 396             }
 397
 398           /* Try to simplify the comparison.  */
 399           if (GET_CODE (comparison_src0) == REG
 400               && values[REGNO (comparison_src0)].lattice_val == CONSTANT)
 401             comparison_src0 = values[REGNO (comparison_src0)].const_value;
 402
 403           if (GET_CODE (comparison_src1) == REG
 404               && values[REGNO (comparison_src1)].lattice_val == CONSTANT)
 405             comparison_src1 = values[REGNO (comparison_src1)].const_value;
 406
 407           x = simplify_ternary_operation (IF_THEN_ELSE,
 408                                           VOIDmode,
 409                                           GET_MODE (XEXP (src, 0)),
 410                                           gen_rtx (comparison_code,
 411                                                    GET_MODE (XEXP (src, 0)),
 412                                                    comparison_src0,
 413                                                    comparison_src1),
 414                                           XEXP (src, 1),
 415                                           XEXP (src, 2));
 416
 417           /* Walk through all the outgoing edges from this block and see
 418              which (if any) we should mark as executable.  */
 419           for (curredge = block->succ; curredge;
 420                curredge = curredge->succ_next)
 421             {
 422               int index = EIE (curredge->src, curredge->dest);
 423
 424               if (TEST_BIT (executable_edges, index))
 425                 continue;
 426
 427               /* If we were unable to simplify the expression at this
 428                  point, it's highly unlikely we'll be able to simplify
 429                  it later.  So consider all edges as executable if the
 430                  expression did not simplify.
 431
 432                  If the expression simplified to (pc), then we know we
 433                  will take the fall-thru edge, so mark it.  Similarly,
 434                  if the expression simplified to (label_ref ...), then
 435                  we know the branch will be taken and we mark that
 436                  edge as taken.  */
 437               if (!x
 438                   || (x == pc_rtx
 439                       && (curredge->flags & EDGE_FALLTHRU))
 440                   || (GET_CODE (x) == LABEL_REF
 441                       && ! (curredge->flags & EDGE_FALLTHRU)))
 442                 {
 443                   SET_BIT (executable_edges, index);
 444                   edge_info[index] = flow_edges;
 445                   flow_edges = curredge;
 446                 }
 447             }
 448         }
 449     }
 450   else if (!PHI_NODE_P (insn))
 451     {
 452       rtx simplified = NULL;
 453
 454       /* We've got some kind of INSN.  If it's simple, try to evaluate
 455          it and record the results.
 456
 457          We already know this insn is a single_set and that it sets
 458          a pseudo register.   So we just need to extract the source
 459          arguments, simplify them to constants if possible, then
 460          simplify the expression as a whole if possible.  */
 461       switch (GET_RTX_CLASS (GET_CODE (src)))
 462         {
 463           case '<':
 464             {
 465               rtx src0 = XEXP (src, 0);
 466               rtx src1 = XEXP (src, 1);
 467               enum machine_mode mode;
 468
 469               /* If either is undefined, then the result is undefined.  */
 470               if ((GET_CODE (src0) == REG
 471                    && values[REGNO (src0)].lattice_val == UNDEFINED)
 472                   || (GET_CODE (src1) == REG
 473                       && values[REGNO (src1)].lattice_val == UNDEFINED))
 474                 {
 475                   defs_to_undefined (insn);
 476                   break;
 477                 }
 478
 479               /* Determine the mode for the operation before we simplify
 480                  our arguments to constants.  */
 481               mode = GET_MODE (src0);
 482               if (mode == VOIDmode)
 483                 mode = GET_MODE (src1);
 484
 485               /* Simplify source operands to whatever known values they
 486                  may have.  */
 487               if (GET_CODE (src0) == REG
 488                   && values[REGNO (src0)].lattice_val == CONSTANT)
 489                 src0 = values[REGNO (src0)].const_value;
 490
 491               if (GET_CODE (src1) == REG
 492                   && values[REGNO (src1)].lattice_val == CONSTANT)
 493                 src1 = values[REGNO (src1)].const_value;
 494
 495               /* See if the simplifier can determine if this operation
 496                  computes a constant value.  */
 497               simplified = simplify_relational_operation (GET_CODE (src),
 498                                                           mode, src0, src1);
 499               break;
 500
 501             }
 502
 503           case '1':
 504             {
 505               rtx src0 = XEXP (src, 0);
 506               enum machine_mode mode0 = GET_MODE (src0);
 507
 508               /* If the operand is undefined, then the result is undefined.  */
 509               if (GET_CODE (src0) == REG
 510                    && values[REGNO (src0)].lattice_val == UNDEFINED)
 511                 {
 512                   defs_to_undefined (insn);
 513                   break;
 514                 }
 515
 516               /* Simplify source operands to whatever known values they
 517                  may have.  */
 518               if (GET_CODE (src0) == REG
 519                   && values[REGNO (src0)].lattice_val == CONSTANT)
 520                 src0 = values[REGNO (src0)].const_value;
 521
 522               /* See if the simplifier can determine if this operation
 523                  computes a constant value.  */
 524               simplified = simplify_unary_operation (GET_CODE (src),
 525                                                      GET_MODE (src),
 526                                                      src0,
 527                                                      mode0);
 528               break;
 529             }
 530
 531           case '2':
 532           case 'c':
 533             {
 534               rtx src0 = XEXP (src, 0);
 535               rtx src1 = XEXP (src, 1);
 536
 537               /* If either is undefined, then the result is undefined.  */
 538               if ((GET_CODE (src0) == REG
 539                    && values[REGNO (src0)].lattice_val == UNDEFINED)
 540                   || (GET_CODE (src1) == REG
 541                       && values[REGNO (src1)].lattice_val == UNDEFINED))
 542                 {
 543                   defs_to_undefined (insn);
 544                   break;
 545                 }
 546
 547               /* Simplify source operands to whatever known values they
 548                  may have.  */
 549               if (GET_CODE (src0) == REG
 550                   && values[REGNO (src0)].lattice_val == CONSTANT)
 551                 src0 = values[REGNO (src0)].const_value;
 552
 553               if (GET_CODE (src1) == REG
 554                   && values[REGNO (src1)].lattice_val == CONSTANT)
 555                 src1 = values[REGNO (src1)].const_value;
 556
 557               /* See if the simplifier can determine if this operation
 558                  computes a constant value.  */
 559               simplified = simplify_binary_operation (GET_CODE (src),
 560                                                       GET_MODE (src),
 561                                                       src0, src1);
 562               break;
 563             }
 564
 565           case '3':
 566           case 'b':
 567             {
 568               rtx src0 = XEXP (src, 0);
 569               rtx src1 = XEXP (src, 1);
 570               rtx src2 = XEXP (src, 2);
 571
 572               /* If either is undefined, then the result is undefined.  */
 573               if ((GET_CODE (src0) == REG
 574                    && values[REGNO (src0)].lattice_val == UNDEFINED)
 575                   || (GET_CODE (src1) == REG
 576                       && values[REGNO (src1)].lattice_val == UNDEFINED)
 577                   || (GET_CODE (src2) == REG
 578                       && values[REGNO (src2)].lattice_val == UNDEFINED))
 579                 {
 580                   defs_to_undefined (insn);
 581                   break;
 582                 }
 583
 584               /* Simplify source operands to whatever known values they
 585                  may have.  */
 586               if (GET_CODE (src0) == REG
 587                   && values[REGNO (src0)].lattice_val == CONSTANT)
 588                 src0 = values[REGNO (src0)].const_value;
 589
 590               if (GET_CODE (src1) == REG
 591                   && values[REGNO (src1)].lattice_val == CONSTANT)
 592                 src1 = values[REGNO (src1)].const_value;
 593
 594               if (GET_CODE (src2) == REG
 595                   && values[REGNO (src2)].lattice_val == CONSTANT)
 596                 src2 = values[REGNO (src2)].const_value;
 597
 598               /* See if the simplifier can determine if this operation
 599                  computes a constant value.  */
 600               simplified = simplify_ternary_operation (GET_CODE (src),
 601                                                        GET_MODE (src),
 602                                                        GET_MODE (src),
 603                                                        src0, src1, src2);
 604               break;
 605             }
 606
 607           default:
 608             defs_to_varying (insn);
 609         }
 610
 611       if (simplified && GET_CODE (simplified) == CONST_INT)
 612         {
 613           if (values[REGNO (dest)].lattice_val != CONSTANT
 614               || values[REGNO (dest)].const_value != simplified)
 615             SET_BIT (ssa_edges, REGNO (dest));
 616
 617           values[REGNO (dest)].lattice_val = CONSTANT;
 618           values[REGNO (dest)].const_value = simplified;
 619         }
 620       else
 621         defs_to_varying (insn);
 622     }
 623 }
 624
 625 /* Iterate over the FLOW_EDGES work list.  Simulate the target block
 626    for each edge.  */
 627 static void
 628 examine_flow_edges ()
 629 {
 630   while (flow_edges != NULL)
 631     {
 632       basic_block succ_block;
 633       rtx curr_phi_node;
 634
 635       /* Pull the next block to simulate off the worklist.  */
 636       succ_block = flow_edges->dest;
 637       flow_edges = edge_info[EIE (flow_edges->src, flow_edges->dest)];
 638
 639       /* There is nothing to do for the exit block.  */
 640       if (succ_block == EXIT_BLOCK_PTR)
 641         continue;
 642
 643       /* Always simulate PHI nodes, even if we have simulated this block
 644          before.  Note that all PHI nodes are consecutive within a block.  */
 645       for (curr_phi_node = first_insn_after_basic_block_note (succ_block);
 646            PHI_NODE_P (curr_phi_node);
 647            curr_phi_node = NEXT_INSN (curr_phi_node))
 648         visit_phi_node (curr_phi_node, succ_block);
 649
 650       /* If this is the first time we've simulated this block, then we
 651          must simulate each of its insns.  */
 652       if (!TEST_BIT (executable_blocks, succ_block->index))
 653         {
 654           rtx currinsn;
 655           edge succ_edge = succ_block->succ;
 656
 657           /* Note that we have simulated this block.  */
 658           SET_BIT (executable_blocks, succ_block->index);
 659
 660           /* Simulate each insn within the block.  */
 661           currinsn = succ_block->head;
 662           while (currinsn != succ_block->end)
 663             {
 664               if (INSN_P (currinsn))
 665                 visit_expression (currinsn, succ_block);
 666
 667               currinsn = NEXT_INSN (currinsn);
 668             }
 669
 670           /* Don't forget the last insn in the block.  */
 671           if (INSN_P (currinsn))
 672             visit_expression (currinsn, succ_block);
 673
 674           /* If we haven't looked at the next block, and it has a
 675              single successor, add it onto the worklist.  This is because
 676              if we only have one successor, we know it gets executed,
 677              so we don't have to wait for cprop to tell us.  */
 678           if (succ_edge != NULL
 679               && succ_edge->succ_next == NULL
 680               && !TEST_BIT (executable_edges,
 681                             EIE (succ_edge->src, succ_edge->dest)))
 682             {
 683               SET_BIT (executable_edges,
 684                        EIE (succ_edge->src, succ_edge->dest));
 685               edge_info[EIE (succ_edge->src, succ_edge->dest)] = flow_edges;
 686               flow_edges = succ_edge;
 687             }
 688         }
 689     }
 690 }
 691
 692 /* Follow the def-use chains for each definition on the worklist and
 693    simulate the uses of the definition.  */
 694
 695 static void
 696 follow_def_use_chains ()
 697 {
 698   /* Iterate over all the entries on the SSA_EDGES worklist.  */
 699   while (sbitmap_first_set_bit (ssa_edges) >= 0)
 700     {
 701       int member;
 702       struct df_link *curruse;
 703
 704       /* Pick an entry off the worklist (it does not matter which
 705          entry we pick).  */
 706       member = sbitmap_first_set_bit (ssa_edges);
 707       RESET_BIT (ssa_edges, member);
 708
 709       /* Iterate through all the uses of this entry.  */
 710       for (curruse = df_analyzer->regs[member].uses; curruse;
 711            curruse = curruse->next)
 712         {
 713           rtx useinsn;
 714
 715           useinsn = DF_REF_INSN (curruse->ref);
 716           if (PHI_NODE_P (useinsn))
 717             {
 718               if (TEST_BIT (executable_blocks, BLOCK_NUM (useinsn)))
 719                 visit_phi_node (useinsn, BLOCK_FOR_INSN (useinsn));
 720             }
 721           else
 722             {
 723               if (TEST_BIT (executable_blocks, BLOCK_NUM (useinsn)))
 724                 visit_expression (useinsn, BLOCK_FOR_INSN (useinsn));
 725             }
 726         }
 727     }
 728 }
 729
 730 /* Examine each edge to see if we were able to prove any were
 731    not executable.
 732
 733    If an edge is not executable, then we can remove its alternative
 734    in PHI nodes as the destination of the edge, we can simplify the
 735    conditional branch at the source of the edge, and we can remove
 736    the edge from the CFG.  Note we do not delete unreachable blocks
 737    yet as the DF analyzer can not deal with that yet.  */
 738 static void
 739 optimize_unexecutable_edges (edges, executable_edges)
 740      struct edge_list *edges;
 741      sbitmap executable_edges;
 742 {
 743   int i;
 744   basic_block bb;
 745
 746   for (i = 0; i < NUM_EDGES (edges); i++)
 747     {
 748       if (!TEST_BIT (executable_edges, i))
 749         {
 750           edge edge = INDEX_EDGE (edges, i);
 751
 752           if (edge->flags & EDGE_ABNORMAL)
 753             continue;
 754
 755           /* We found an edge that is not executable.  First simplify
 756              the PHI nodes in the target block.  */
 757           if (edge->dest != EXIT_BLOCK_PTR)
 758             {
 759               rtx insn = first_insn_after_basic_block_note (edge->dest);
 760
 761               while (PHI_NODE_P (insn))
 762                 {
 763                   remove_phi_alternative (PATTERN (insn), edge->src);
 764                   if (rtl_dump_file)
 765                     fprintf (rtl_dump_file,
 766                              "Removing alternative for bb %d of phi %d\n",
 767                              edge->src->index, SSA_NAME (PATTERN (insn)));
 768                   insn = NEXT_INSN (insn);
 769                 }
 770             }
 771           if (rtl_dump_file)
 772             fprintf (rtl_dump_file,
 773                      "Removing unexecutable edge from %d to %d\n",
 774                      edge->src->index, edge->dest->index);
 775           /* Since the edge was not executable, remove it from the CFG.  */
 776           remove_edge (edge);
 777         }
 778     }
 779
 780   /* We have removed all the unexecutable edges from the CFG.  Fix up
 781      the conditional jumps at the end of any affected block.
 782
 783      We have three cases to deal with:
 784
 785        a. Both outgoing edges are not executable.  This happens if the
 786           source block is not reachable.  We will deal with this by
 787           deleting all the insns in the block later.
 788
 789        b. The fall-thru edge is not executable.  In this case we
 790           change the conditional jump into an unconditional jump and
 791           add a BARRIER after the unconditional jump.  Note that since
 792           we are working on generic RTL we can change the jump in-place
 793           instead of dealing with the headache of reemitting the jump.
 794
 795        c. The branch taken edge is not executable.  In this case
 796           we turn the jump into (set (pc) (pc)) which is a nop-jump
 797           and we will remove the unrecognizable insn later.
 798
 799      In cases B & C we are removing uses of registers, so make sure
 800      to note those changes for the DF analyzer.  */
 801
 802   FOR_EACH_BB (bb)
 803     {
 804       rtx insn = bb->end;
 805       edge edge = bb->succ;
 806
 807       /* If we have no predecessors, then this block is unreachable and
 808          will be cleaned up when we remove unreachable blocks.  */
 809       if (bb->pred == NULL || GET_CODE (insn) != JUMP_INSN)
 810         continue;
 811
 812       /* If this block ends in a conditional jump, but only has one
 813          successor, then the jump needs adjustment.  */
 814       if (condjump_p (insn) && ! simplejump_p (insn)
 815           && bb->succ && bb->succ->succ_next == NULL)
 816         {
 817           /* If the fallthru edge is the executable edge, then turn
 818              this jump into a nop jump, otherwise make it an unconditional
 819              jump to its target.  */
 820           if (edge->flags & EDGE_FALLTHRU)
 821             {
 822               PUT_CODE (insn, NOTE);
 823               NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
 824             }
 825           else
 826             {
 827               SET_SRC (PATTERN (insn)) = gen_rtx_LABEL_REF (Pmode,
 828                                                             JUMP_LABEL (insn));
 829               emit_barrier_after (insn);
 830               INSN_CODE (insn) = -1;
 831             }
 832
 833           /* Inform the DF analyzer that this insn changed.  */
 834           df_insn_modify (df_analyzer, BLOCK_FOR_INSN (insn), insn);
 835         }
 836     }
 837 }
 838
 839 /* Perform substitution of known values for pseudo registers.
 840
 841    ??? Note we do not do simplifications or constant folding here, it
 842    is unlikely that any significant simplifications can be done here
 843    anyway.  Consider that if the simplification would result in an
 844    expression that produces a constant value that the value would
 845    have been discovered and recorded already.
 846
 847    We perform two transformations.  First, we initialize pseudos to their
 848    known constant values at their definition point.  Second, we try to
 849    replace uses with the known constant value.  */
 850
 851 static void
 852 ssa_ccp_substitute_constants ()
 853 {
 854   unsigned int i;
 855
 856   for (i = FIRST_PSEUDO_REGISTER; i < VARRAY_SIZE (ssa_definition); i++)
 857     {
 858       if (values[i].lattice_val == CONSTANT)
 859         {
 860           rtx def = VARRAY_RTX (ssa_definition, i);
 861           rtx set = single_set (def);
 862           struct df_link *curruse;
 863
 864           if (! set)
 865             continue;
 866
 867           /* Do not try to simplify PHI nodes down to a constant load.
 868              That will be done later as we translate out of SSA.  Also,
 869              doing that here could violate the rule that all PHI nodes
 870              are consecutive at the start of the basic block.
 871
 872              Don't do anything to nodes that were already sets to
 873              constants.  */
 874           if (! PHI_NODE_P (def)
 875               && ! ((GET_CODE (def) == INSN
 876                      && GET_CODE (SET_SRC (set)) == CONST_INT)))
 877             {
 878               if (rtl_dump_file)
 879                 fprintf (rtl_dump_file,
 880                          "Register %d is now set to a constant\n",
 881                          SSA_NAME (PATTERN (def)));
 882               SET_SRC (set) = values[i].const_value;
 883               INSN_CODE (def) = -1;
 884               df_insn_modify (df_analyzer, BLOCK_FOR_INSN (def), def);
 885             }
 886
 887           /* Iterate through all the uses of this entry and try replacements
 888              there too.  Note it is not particularly profitable to try
 889              and fold/simplify expressions here as most of the common
 890              cases were handled above.  */
 891           for (curruse = df_analyzer->regs[i].uses;
 892                curruse;
 893                curruse = curruse->next)
 894             {
 895               rtx useinsn;
 896
 897               useinsn = DF_REF_INSN (curruse->ref);
 898
 899               if (!INSN_DELETED_P (useinsn)
 900                   && ! (GET_CODE (useinsn) == NOTE
 901                         && NOTE_LINE_NUMBER (useinsn) == NOTE_INSN_DELETED)
 902                   && (GET_CODE (useinsn) == INSN
 903                       || GET_CODE (useinsn) == JUMP_INSN))
 904                 {
 905
 906                   if (validate_replace_src (regno_reg_rtx [i],
 907                                         values[i].const_value,
 908                                             useinsn))
 909                     {
 910                       if (rtl_dump_file)
 911                         fprintf (rtl_dump_file,
 912                                  "Register %d in insn %d replaced with constant\n",
 913                                  i, INSN_UID (useinsn));
 914                       INSN_CODE (useinsn) = -1;
 915                       df_insn_modify (df_analyzer,
 916                                       BLOCK_FOR_INSN (useinsn),
 917                                       useinsn);
 918                     }
 919
 920                 }
 921             }
 922         }
 923     }
 924 }
 925
 926 /* Now find all unreachable basic blocks.  All the insns in those
 927    blocks are unreachable, so delete them and mark any necessary
 928    updates for the DF analyzer.  */
 929
 930 static void
 931 ssa_ccp_df_delete_unreachable_insns ()
 932 {
 933   basic_block b;
 934
 935   /* Use the CFG to find all the reachable blocks.  */
 936   find_unreachable_blocks ();
 937
 938   /* Now we know what blocks are not reachable.  Mark all the insns
 939      in those blocks as deleted for the DF analyzer.   We'll let the
 940      normal flow code actually remove the unreachable blocks.  */
 941   FOR_EACH_BB_REVERSE (b)
 942     {
 943       if (!(b->flags & BB_REACHABLE))
 944         {
 945           rtx start = b->head;
 946           rtx end = b->end;
 947           rtx tmp;
 948
 949           /* Include any jump table following the basic block.  */
 950           end = b->end;
 951           if (tablejump_p (end, NULL, &tmp))
 952             end = tmp;
 953
 954           while (1)
 955             {
 956               rtx next = NEXT_INSN (start);
 957
 958               if (GET_CODE (start) == INSN
 959                   || GET_CODE (start) == CALL_INSN
 960                   || GET_CODE (start) == JUMP_INSN)
 961                 df_insn_delete (df_analyzer, BLOCK_FOR_INSN (start), start);
 962
 963               if (start == end)
 964                 break;
 965               start = next;
 966             }
 967         }
 968     }
 969 }
 970
 971
 972 /* Main entry point for SSA Conditional Constant Propagation.
 973
 974    Long term it should accept as input the specific flow graph to
 975    operate on so that it can be called for sub-graphs.  */
 976
 977 void
 978 ssa_const_prop ()
 979 {
 980   unsigned int i;
 981   edge curredge;
 982
 983   /* We need alias analysis (for what?) */
 984   init_alias_analysis ();
 985
 986   df_analyzer = df_init ();
 987   df_analyse (df_analyzer, 0,
 988               DF_RD_CHAIN | DF_RU_CHAIN | DF_REG_INFO | DF_HARD_REGS);
 989
 990   /* Perform a quick and dirty dead code elimination pass.  This is not
 991      as aggressive as it could be, but it's good enough to clean up a
 992      lot of unwanted junk and it is fast.  */
 993   ssa_fast_dce (df_analyzer);
 994
 995   /* Build an edge list from the CFG.  */
 996   edges = create_edge_list ();
 997
 998   /* Initialize the values array with everything as undefined.  */
 999   values = (value *) xmalloc (VARRAY_SIZE (ssa_definition) * sizeof (value));
1000   for (i = 0; i < VARRAY_SIZE (ssa_definition); i++)
1001     {
1002       if (i < FIRST_PSEUDO_REGISTER)
1003         values[i].lattice_val = VARYING;
1004       else
1005         values[i].lattice_val = UNDEFINED;
1006       values[i].const_value = NULL;
1007     }
1008
1009   ssa_edges = sbitmap_alloc (VARRAY_SIZE (ssa_definition));
1010   sbitmap_zero (ssa_edges);
1011
1012   executable_blocks = sbitmap_alloc (last_basic_block);
1013   sbitmap_zero (executable_blocks);
1014
1015   executable_edges = sbitmap_alloc (NUM_EDGES (edges));
1016   sbitmap_zero (executable_edges);
1017
1018   edge_info = (edge *) xmalloc (NUM_EDGES (edges) * sizeof (edge));
1019   flow_edges = ENTRY_BLOCK_PTR->succ;
1020
1021   /* Add the successors of the entry block to the edge worklist.  That
1022      is enough of a seed to get SSA-CCP started.  */
1023   for (curredge = ENTRY_BLOCK_PTR->succ; curredge;
1024        curredge = curredge->succ_next)
1025     {
1026       int index = EIE (curredge->src, curredge->dest);
1027       SET_BIT (executable_edges, index);
1028       edge_info[index] = curredge->succ_next;
1029     }
1030
1031   /* Iterate until until the worklists are empty.  */
1032   do
1033     {
1034       examine_flow_edges ();
1035       follow_def_use_chains ();
1036     }
1037   while (flow_edges != NULL);
1038
1039   /* Now perform substitutions based on the known constant values.  */
1040   ssa_ccp_substitute_constants ();
1041
1042   /* Remove unexecutable edges from the CFG and make appropriate
1043      adjustments to PHI nodes.  */
1044   optimize_unexecutable_edges (edges, executable_edges);
1045
1046   /* Now remove all unreachable insns and update the DF information.
1047      as appropriate.  */
1048   ssa_ccp_df_delete_unreachable_insns ();
1049
1050 #if 0
1051   /* The DF analyzer expects the number of blocks to remain constant,
1052      so we can't remove unreachable blocks.
1053
1054      Code the DF analyzer calls expects there to be no unreachable
1055      blocks in the CFG.  So we can't leave unreachable blocks in the
1056      CFG.
1057
1058      So, there is no way to do an incremental update of the DF data
1059      at this point.  */
1060   df_analyse (df_analyzer, 0,
1061               DF_RD_CHAIN | DF_RU_CHAIN | DF_REG_INFO | DF_HARD_REGS);
1062 #endif
1063
1064   /* Clean up any dead code exposed by SSA-CCP, do this after updating
1065      the dataflow information!  */
1066   ssa_fast_dce (df_analyzer);
1067
1068   free (values);
1069   values = NULL;
1070
1071   free (edge_info);
1072   edge_info = NULL;
1073
1074   sbitmap_free (executable_blocks);
1075   executable_blocks = NULL;
1076
1077   sbitmap_free (ssa_edges);
1078   ssa_edges = NULL;
1079
1080   free_edge_list (edges);
1081   edges = NULL;
1082
1083   sbitmap_free (executable_edges);
1084   executable_edges = NULL;
1085
1086   df_finish (df_analyzer);
1087   end_alias_analysis ();
1088 }
1089
1090 static int
1091 mark_references (current_rtx, data)
1092      rtx *current_rtx;
1093      void *data;
1094 {
1095   rtx x = *current_rtx;
1096   sbitmap worklist = (sbitmap) data;
1097
1098   if (x == NULL_RTX)
1099     return 0;
1100
1101   if (GET_CODE (x) == SET)
1102     {
1103       rtx dest = SET_DEST (x);
1104
1105       if (GET_CODE (dest) == STRICT_LOW_PART
1106           || GET_CODE (dest) == SUBREG
1107           || GET_CODE (dest) == SIGN_EXTRACT
1108           || GET_CODE (dest) == ZERO_EXTRACT)
1109         {
1110           rtx reg;
1111
1112           reg = dest;
1113
1114           while (GET_CODE (reg) == STRICT_LOW_PART
1115                  || GET_CODE (reg) == SUBREG
1116                  || GET_CODE (reg) == SIGN_EXTRACT
1117                  || GET_CODE (reg) == ZERO_EXTRACT)
1118             reg = XEXP (reg, 0);
1119
1120           if (GET_CODE (reg) == REG)
1121             SET_BIT (worklist, REGNO (reg));
1122         }
1123
1124       if (GET_CODE (dest) == REG)
1125         {
1126           for_each_rtx (&SET_SRC (x), mark_references, data);
1127           return -1;
1128         }
1129
1130       return 0;
1131     }
1132   else if (GET_CODE (x) == REG)
1133     {
1134       SET_BIT (worklist, REGNO (x));
1135       return -1;
1136     }
1137   else if (GET_CODE (x) == CLOBBER)
1138     return -1;
1139   else
1140     return 0;
1141 }
1142
1143 static void
1144 ssa_fast_dce (df)
1145      struct df *df;
1146 {
1147   sbitmap worklist = sbitmap_alloc (VARRAY_SIZE (ssa_definition));
1148   sbitmap_ones (worklist);
1149
1150   /* Iterate on the worklist until there's no definitions left to
1151      examine.  */
1152   while (sbitmap_first_set_bit (worklist) >= 0)
1153     {
1154       struct df_link *curruse;
1155       int reg, found_use;
1156
1157       /* Remove an item from the worklist.  */
1158       reg = sbitmap_first_set_bit (worklist);
1159       RESET_BIT (worklist, reg);
1160
1161       /* We never consider deleting assignments to hard regs or things
1162          which do not have SSA definitions, or things we have already
1163          deleted, or things with unusual side effects.  */
1164       if (reg < FIRST_PSEUDO_REGISTER
1165           || ! VARRAY_RTX (ssa_definition, reg)
1166           || INSN_DELETED_P (VARRAY_RTX (ssa_definition, reg))
1167           || (GET_CODE (VARRAY_RTX (ssa_definition, reg)) == NOTE
1168               && (NOTE_LINE_NUMBER (VARRAY_RTX (ssa_definition, reg))
1169                   == NOTE_INSN_DELETED))
1170           || side_effects_p (PATTERN (VARRAY_RTX (ssa_definition, reg))))
1171         continue;
1172
1173       /* Iterate over the uses of this register.  If we can not find
1174          any uses that have not been deleted, then the definition of
1175          this register is dead.  */
1176       found_use = 0;
1177       for (curruse = df->regs[reg].uses; curruse; curruse = curruse->next)
1178         {
1179           if (curruse->ref
1180               && DF_REF_INSN (curruse->ref)
1181               && ! INSN_DELETED_P (DF_REF_INSN (curruse->ref))
1182               && ! (GET_CODE (DF_REF_INSN (curruse->ref)) == NOTE
1183                     && (NOTE_LINE_NUMBER (DF_REF_INSN (curruse->ref))
1184                         == NOTE_INSN_DELETED))
1185               && DF_REF_INSN (curruse->ref) != VARRAY_RTX (ssa_definition, reg))
1186             {
1187               found_use = 1;
1188               break;
1189             }
1190         }
1191
1192       /* If we did not find a use of this register, then the definition
1193          of this register is dead.  */
1194
1195       if (! found_use)
1196         {
1197           rtx def = VARRAY_RTX (ssa_definition, reg);
1198
1199           /* Add all registers referenced by INSN to the work
1200              list.  */
1201           for_each_rtx (&PATTERN (def), mark_references, worklist);
1202
1203           /* Inform the analyzer that this insn is going to be
1204              deleted.  */
1205           df_insn_delete (df, BLOCK_FOR_INSN (def), def);
1206
1207           VARRAY_RTX (ssa_definition, reg) = NULL;
1208         }
1209     }
1210
1211   sbitmap_free (worklist);
1212
1213   /* Update the use-def chains in the df_analyzer as needed.  */
1214   df_analyse (df_analyzer, 0,
1215               DF_RD_CHAIN | DF_RU_CHAIN | DF_REG_INFO | DF_HARD_REGS);
1216 }