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 (GET_CODE (end) == JUMP_INSN
 952               && (tmp = JUMP_LABEL (end)) != NULL_RTX
 953               && (tmp = NEXT_INSN (tmp)) != NULL_RTX
 954               && GET_CODE (tmp) == JUMP_INSN
 955               && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
 956                   || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
 957             end = tmp;
 958
 959           while (1)
 960             {
 961               rtx next = NEXT_INSN (start);
 962
 963               if (GET_CODE (start) == INSN
 964                   || GET_CODE (start) == CALL_INSN
 965                   || GET_CODE (start) == JUMP_INSN)
 966                 df_insn_delete (df_analyzer, BLOCK_FOR_INSN (start), start);
 967
 968               if (start == end)
 969                 break;
 970               start = next;
 971             }
 972         }
 973     }
 974 }
 975
 976
 977 /* Main entry point for SSA Conditional Constant Propagation.
 978
 979    Long term it should accept as input the specific flow graph to
 980    operate on so that it can be called for sub-graphs.  */
 981
 982 void
 983 ssa_const_prop ()
 984 {
 985   unsigned int i;
 986   edge curredge;
 987
 988   /* We need alias analysis (for what?) */
 989   init_alias_analysis ();
 990
 991   df_analyzer = df_init ();
 992   df_analyse (df_analyzer, 0,
 993               DF_RD_CHAIN | DF_RU_CHAIN | DF_REG_INFO | DF_HARD_REGS);
 994
 995   /* Perform a quick and dirty dead code elimination pass.  This is not
 996      as aggressive as it could be, but it's good enough to clean up a
 997      lot of unwanted junk and it is fast.  */
 998   ssa_fast_dce (df_analyzer);
 999
1000   /* Build an edge list from the CFG.  */
1001   edges = create_edge_list ();
1002
1003   /* Initialize the values array with everything as undefined.  */
1004   values = (value *) xmalloc (VARRAY_SIZE (ssa_definition) * sizeof (value));
1005   for (i = 0; i < VARRAY_SIZE (ssa_definition); i++)
1006     {
1007       if (i < FIRST_PSEUDO_REGISTER)
1008         values[i].lattice_val = VARYING;
1009       else
1010         values[i].lattice_val = UNDEFINED;
1011       values[i].const_value = NULL;
1012     }
1013
1014   ssa_edges = sbitmap_alloc (VARRAY_SIZE (ssa_definition));
1015   sbitmap_zero (ssa_edges);
1016
1017   executable_blocks = sbitmap_alloc (last_basic_block);
1018   sbitmap_zero (executable_blocks);
1019
1020   executable_edges = sbitmap_alloc (NUM_EDGES (edges));
1021   sbitmap_zero (executable_edges);
1022
1023   edge_info = (edge *) xmalloc (NUM_EDGES (edges) * sizeof (edge));
1024   flow_edges = ENTRY_BLOCK_PTR->succ;
1025
1026   /* Add the successors of the entry block to the edge worklist.  That
1027      is enough of a seed to get SSA-CCP started.  */
1028   for (curredge = ENTRY_BLOCK_PTR->succ; curredge;
1029        curredge = curredge->succ_next)
1030     {
1031       int index = EIE (curredge->src, curredge->dest);
1032       SET_BIT (executable_edges, index);
1033       edge_info[index] = curredge->succ_next;
1034     }
1035
1036   /* Iterate until until the worklists are empty.  */
1037   do
1038     {
1039       examine_flow_edges ();
1040       follow_def_use_chains ();
1041     }
1042   while (flow_edges != NULL);
1043
1044   /* Now perform substitutions based on the known constant values.  */
1045   ssa_ccp_substitute_constants ();
1046
1047   /* Remove unexecutable edges from the CFG and make appropriate
1048      adjustments to PHI nodes.  */
1049   optimize_unexecutable_edges (edges, executable_edges);
1050
1051   /* Now remove all unreachable insns and update the DF information.
1052      as appropriate.  */
1053   ssa_ccp_df_delete_unreachable_insns ();
1054
1055 #if 0
1056   /* The DF analyzer expects the number of blocks to remain constant,
1057      so we can't remove unreachable blocks.
1058
1059      Code the DF analyzer calls expects there to be no unreachable
1060      blocks in the CFG.  So we can't leave unreachable blocks in the
1061      CFG.
1062
1063      So, there is no way to do an incremental update of the DF data
1064      at this point.  */
1065   df_analyse (df_analyzer, 0,
1066               DF_RD_CHAIN | DF_RU_CHAIN | DF_REG_INFO | DF_HARD_REGS);
1067 #endif
1068
1069   /* Clean up any dead code exposed by SSA-CCP, do this after updating
1070      the dataflow information!  */
1071   ssa_fast_dce (df_analyzer);
1072
1073   free (values);
1074   values = NULL;
1075
1076   free (edge_info);
1077   edge_info = NULL;
1078
1079   sbitmap_free (executable_blocks);
1080   executable_blocks = NULL;
1081
1082   sbitmap_free (ssa_edges);
1083   ssa_edges = NULL;
1084
1085   free_edge_list (edges);
1086   edges = NULL;
1087
1088   sbitmap_free (executable_edges);
1089   executable_edges = NULL;
1090
1091   df_finish (df_analyzer);
1092   end_alias_analysis ();
1093 }
1094
1095 static int
1096 mark_references (current_rtx, data)
1097      rtx *current_rtx;
1098      void *data;
1099 {
1100   rtx x = *current_rtx;
1101   sbitmap worklist = (sbitmap) data;
1102
1103   if (x == NULL_RTX)
1104     return 0;
1105
1106   if (GET_CODE (x) == SET)
1107     {
1108       rtx dest = SET_DEST (x);
1109
1110       if (GET_CODE (dest) == STRICT_LOW_PART
1111           || GET_CODE (dest) == SUBREG
1112           || GET_CODE (dest) == SIGN_EXTRACT
1113           || GET_CODE (dest) == ZERO_EXTRACT)
1114         {
1115           rtx reg;
1116
1117           reg = dest;
1118
1119           while (GET_CODE (reg) == STRICT_LOW_PART
1120                  || GET_CODE (reg) == SUBREG
1121                  || GET_CODE (reg) == SIGN_EXTRACT
1122                  || GET_CODE (reg) == ZERO_EXTRACT)
1123             reg = XEXP (reg, 0);
1124
1125           if (GET_CODE (reg) == REG)
1126             SET_BIT (worklist, REGNO (reg));
1127         }
1128
1129       if (GET_CODE (dest) == REG)
1130         {
1131           for_each_rtx (&SET_SRC (x), mark_references, data);
1132           return -1;
1133         }
1134
1135       return 0;
1136     }
1137   else if (GET_CODE (x) == REG)
1138     {
1139       SET_BIT (worklist, REGNO (x));
1140       return -1;
1141     }
1142   else if (GET_CODE (x) == CLOBBER)
1143     return -1;
1144   else
1145     return 0;
1146 }
1147
1148 static void
1149 ssa_fast_dce (df)
1150      struct df *df;
1151 {
1152   sbitmap worklist = sbitmap_alloc (VARRAY_SIZE (ssa_definition));
1153   sbitmap_ones (worklist);
1154
1155   /* Iterate on the worklist until there's no definitions left to
1156      examine.  */
1157   while (sbitmap_first_set_bit (worklist) >= 0)
1158     {
1159       struct df_link *curruse;
1160       int reg, found_use;
1161
1162       /* Remove an item from the worklist.  */
1163       reg = sbitmap_first_set_bit (worklist);
1164       RESET_BIT (worklist, reg);
1165
1166       /* We never consider deleting assignments to hard regs or things
1167          which do not have SSA definitions, or things we have already
1168          deleted, or things with unusual side effects.  */
1169       if (reg < FIRST_PSEUDO_REGISTER
1170           || ! VARRAY_RTX (ssa_definition, reg)
1171           || INSN_DELETED_P (VARRAY_RTX (ssa_definition, reg))
1172           || (GET_CODE (VARRAY_RTX (ssa_definition, reg)) == NOTE
1173               && (NOTE_LINE_NUMBER (VARRAY_RTX (ssa_definition, reg))
1174                   == NOTE_INSN_DELETED))
1175           || side_effects_p (PATTERN (VARRAY_RTX (ssa_definition, reg))))
1176         continue;
1177
1178       /* Iterate over the uses of this register.  If we can not find
1179          any uses that have not been deleted, then the definition of
1180          this register is dead.  */
1181       found_use = 0;
1182       for (curruse = df->regs[reg].uses; curruse; curruse = curruse->next)
1183         {
1184           if (curruse->ref
1185               && DF_REF_INSN (curruse->ref)
1186               && ! INSN_DELETED_P (DF_REF_INSN (curruse->ref))
1187               && ! (GET_CODE (DF_REF_INSN (curruse->ref)) == NOTE
1188                     && (NOTE_LINE_NUMBER (DF_REF_INSN (curruse->ref))
1189                         == NOTE_INSN_DELETED))
1190               && DF_REF_INSN (curruse->ref) != VARRAY_RTX (ssa_definition, reg))
1191             {
1192               found_use = 1;
1193               break;
1194             }
1195         }
1196
1197       /* If we did not find a use of this register, then the definition
1198          of this register is dead.  */
1199
1200       if (! found_use)
1201         {
1202           rtx def = VARRAY_RTX (ssa_definition, reg);
1203
1204           /* Add all registers referenced by INSN to the work
1205              list.  */
1206           for_each_rtx (&PATTERN (def), mark_references, worklist);
1207
1208           /* Inform the analyzer that this insn is going to be
1209              deleted.  */
1210           df_insn_delete (df, BLOCK_FOR_INSN (def), def);
1211
1212           VARRAY_RTX (ssa_definition, reg) = NULL;
1213         }
1214     }
1215
1216   sbitmap_free (worklist);
1217
1218   /* Update the use-def chains in the df_analyzer as needed.  */
1219   df_analyse (df_analyzer, 0,
1220               DF_RD_CHAIN | DF_RU_CHAIN | DF_REG_INFO | DF_HARD_REGS);
1221 }