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