gcc/ssa-ccp.c

   1 /* Conditional constant propagation pass for the GNU compiler.
   2    Copyright (C) 2000,2001 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 GNU CC.
   7
   8 GNU CC is free software; you can redistribute it and/or modify it
   9 under the terms of the GNU General Public License as published by the
  10 Free Software Foundation; either version 2, or (at your option) any
  11 later version.
  12
  13 GNU CC is distributed in the hope that it will be useful, but WITHOUT
  14 ANY 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 GNU CC; 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 rtx first_phi_node              PARAMS ((basic_block));
 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 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
 137 /* Return the first PHI node in a basic block.  This routine knows
 138    what INSNs can start a basic block and what can validly follow
 139    them up to the first PHI node.
 140
 141    If the INSN chain or block structures are incorrect, then the behavior
 142    of this routine is undefined.  verify_flow_info will normally catch
 143    these problems in a more graceful manner.  */
 144 rtx
 145 first_phi_node (block)
 146      basic_block block;
 147 {
 148   rtx insn = block->head;
 149
 150   /* Eat the optional CODE_LABEL at the start of the block.  */
 151   if (GET_CODE (insn) == CODE_LABEL)
 152     insn = NEXT_INSN (insn);
 153
 154   /* Eat the mandatory NOTE_INSN_BASIC_BLOCK.  */
 155   if (!NOTE_INSN_BASIC_BLOCK_P (insn) || NOTE_BASIC_BLOCK (insn) != block)
 156     abort ();
 157
 158   /* If there is a PHI node in this block, then it will be the next insn.  */
 159   return NEXT_INSN (insn);
 160 }
 161
 162 /* Loop through the PHI_NODE's parameters for BLOCK and compare their
 163    lattice values to determine PHI_NODE's lattice value.  */
 164 static void
 165 visit_phi_node (phi_node, block)
 166      rtx phi_node;
 167      basic_block block;
 168 {
 169   unsigned int i;
 170   rtx phi_node_expr = NULL;
 171   unsigned int phi_node_name = SSA_NAME (PATTERN (phi_node));
 172   latticevalue phi_node_lattice_val = UNDEFINED;
 173   rtx pat = PATTERN (phi_node);
 174   rtvec phi_vec = XVEC (SET_SRC (pat), 0);
 175   unsigned int num_elem = GET_NUM_ELEM (phi_vec);
 176
 177   for (i = 0; i < num_elem; i += 2)
 178     {
 179       if (TEST_BIT (executable_edges,
 180                     EIE (BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec, i + 1))),
 181                          block)))
 182         {
 183           unsigned int current_parm
 184             = REGNO (RTVEC_ELT (phi_vec, i));
 185
 186           latticevalue current_parm_lattice_val
 187             = values[current_parm].lattice_val;
 188
 189           /* If any node is VARYING, then new value of PHI_NODE
 190              is VARYING.  */
 191           if (current_parm_lattice_val == VARYING)
 192             {
 193               phi_node_lattice_val = VARYING;
 194               phi_node_expr = NULL;
 195               break;
 196             }
 197
 198           /* If we have more than one distinct constant, then the new
 199              value of PHI_NODE is VARYING.  */
 200           if (current_parm_lattice_val == CONSTANT
 201               && phi_node_lattice_val == CONSTANT
 202               && values[current_parm].const_value != phi_node_expr)
 203             {
 204               phi_node_lattice_val = VARYING;
 205               phi_node_expr = NULL;
 206               break;
 207             }
 208
 209           /* If the current value of PHI_NODE is UNDEFINED and one
 210              node in PHI_NODE is CONSTANT, then the new value of the
 211              PHI is that CONSTANT.  Note this can turn into VARYING
 212              if we find another distinct constant later.  */
 213           if (phi_node_lattice_val == UNDEFINED
 214               && phi_node_expr == NULL
 215               && current_parm_lattice_val == CONSTANT)
 216             {
 217               phi_node_expr = values[current_parm].const_value;
 218               phi_node_lattice_val = CONSTANT;
 219               continue;
 220             }
 221         }
 222     }
 223
 224   /* If the value of PHI_NODE changed, then we will need to
 225      re-execute uses of the output of PHI_NODE.  */
 226   if (phi_node_lattice_val != values[phi_node_name].lattice_val)
 227     {
 228       values[phi_node_name].lattice_val = phi_node_lattice_val;
 229       values[phi_node_name].const_value = phi_node_expr;
 230       SET_BIT (ssa_edges, phi_node_name);
 231     }
 232 }
 233
 234 /* Sets all defs in an insn to UNDEFINED.  */
 235 static void
 236 defs_to_undefined (insn)
 237      rtx insn;
 238 {
 239   struct df_link *currdef;
 240   for (currdef = DF_INSN_DEFS (df_analyzer, insn); currdef;
 241        currdef = currdef->next)
 242     {
 243       if (values[DF_REF_REGNO (currdef->ref)].lattice_val != UNDEFINED)
 244         SET_BIT (ssa_edges, DF_REF_REGNO (currdef->ref));
 245       values[DF_REF_REGNO (currdef->ref)].lattice_val = UNDEFINED;
 246     }
 247 }
 248
 249 /* Sets all defs in an insn to VARYING.  */
 250 static void
 251 defs_to_varying (insn)
 252      rtx insn;
 253 {
 254   struct df_link *currdef;
 255   for (currdef = DF_INSN_DEFS (df_analyzer, insn); currdef;
 256        currdef = currdef->next)
 257     {
 258       if (values[DF_REF_REGNO (currdef->ref)].lattice_val != VARYING)
 259         SET_BIT (ssa_edges, DF_REF_REGNO (currdef->ref));
 260       values[DF_REF_REGNO (currdef->ref)].lattice_val = VARYING;
 261     }
 262 }
 263
 264 /* Go through the expression, call the approriate evaluation routines
 265    to attempt cprop */
 266 static void
 267 visit_expression (insn, block)
 268      rtx insn;
 269      basic_block block;
 270 {
 271   rtx src, dest, set;
 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               /* Simplify source operands to whatever known values they
 479                  may have.  */
 480               if (GET_CODE (src0) == REG
 481                   && values[REGNO (src0)].lattice_val == CONSTANT)
 482                 src0 = values[REGNO (src0)].const_value;
 483
 484               if (GET_CODE (src1) == REG
 485                   && values[REGNO (src1)].lattice_val == CONSTANT)
 486                 src1 = values[REGNO (src1)].const_value;
 487
 488               /* See if the simplifier can determine if this operation
 489                  computes a constant value.  */
 490               mode = GET_MODE (src0);
 491               if (mode == VOIDmode)
 492                 mode = GET_MODE (src1);
 493
 494               simplified = simplify_relational_operation (GET_CODE (src),
 495                                                           mode, src0, src1);
 496               break;
 497
 498             }
 499
 500           case '1':
 501             {
 502               rtx src0 = XEXP (src, 0);
 503
 504               /* If the operand is undefined, then the result is undefined.  */
 505               if (GET_CODE (src0) == REG
 506                    && values[REGNO (src0)].lattice_val == UNDEFINED)
 507                 {
 508                   defs_to_undefined (insn);
 509                   break;
 510                 }
 511
 512               /* Simplify source operands to whatever known values they
 513                  may have.  */
 514               if (GET_CODE (src0) == REG
 515                   && values[REGNO (src0)].lattice_val == CONSTANT)
 516                 src0 = values[REGNO (src0)].const_value;
 517
 518               /* See if the simplifier can determine if this operation
 519                  computes a constant value.  */
 520               simplified = simplify_unary_operation (GET_CODE (src),
 521                                                      GET_MODE (src),
 522                                                      src0,
 523                                                      GET_MODE (src0));
 524               break;
 525             }
 526
 527           case '2':
 528           case 'c':
 529             {
 530               rtx src0 = XEXP (src, 0);
 531               rtx src1 = XEXP (src, 1);
 532
 533               /* If either is undefined, then the result is undefined.  */
 534               if ((GET_CODE (src0) == REG
 535                    && values[REGNO (src0)].lattice_val == UNDEFINED)
 536                   || (GET_CODE (src1) == REG
 537                       && values[REGNO (src1)].lattice_val == UNDEFINED))
 538                 {
 539                   defs_to_undefined (insn);
 540                   break;
 541                 }
 542
 543               /* Simplify source operands to whatever known values they
 544                  may have.  */
 545               if (GET_CODE (src0) == REG
 546                   && values[REGNO (src0)].lattice_val == CONSTANT)
 547                 src0 = values[REGNO (src0)].const_value;
 548
 549               if (GET_CODE (src1) == REG
 550                   && values[REGNO (src1)].lattice_val == CONSTANT)
 551                 src1 = values[REGNO (src1)].const_value;
 552
 553               /* See if the simplifier can determine if this operation
 554                  computes a constant value.  */
 555               simplified = simplify_binary_operation (GET_CODE (src),
 556                                                       GET_MODE (src),
 557                                                       src0, src1);
 558               break;
 559             }
 560
 561           case '3':
 562           case 'b':
 563             {
 564               rtx src0 = XEXP (src, 0);
 565               rtx src1 = XEXP (src, 1);
 566               rtx src2 = XEXP (src, 2);
 567
 568               /* If either is undefined, then the result is undefined.  */
 569               if ((GET_CODE (src0) == REG
 570                    && values[REGNO (src0)].lattice_val == UNDEFINED)
 571                   || (GET_CODE (src1) == REG
 572                       && values[REGNO (src1)].lattice_val == UNDEFINED)
 573                   || (GET_CODE (src2) == REG
 574                       && values[REGNO (src2)].lattice_val == UNDEFINED))
 575                 {
 576                   defs_to_undefined (insn);
 577                   break;
 578                 }
 579
 580               /* Simplify source operands to whatever known values they
 581                  may have.  */
 582               if (GET_CODE (src0) == REG
 583                   && values[REGNO (src0)].lattice_val == CONSTANT)
 584                 src0 = values[REGNO (src0)].const_value;
 585
 586               if (GET_CODE (src1) == REG
 587                   && values[REGNO (src1)].lattice_val == CONSTANT)
 588                 src1 = values[REGNO (src1)].const_value;
 589
 590               if (GET_CODE (src2) == REG
 591                   && values[REGNO (src2)].lattice_val == CONSTANT)
 592                 src2 = values[REGNO (src2)].const_value;
 593
 594               /* See if the simplifier can determine if this operation
 595                  computes a constant value.  */
 596               simplified = simplify_ternary_operation (GET_CODE (src),
 597                                                        GET_MODE (src),
 598                                                        GET_MODE (src),
 599                                                        src0, src1, src2);
 600               break;
 601             }
 602
 603           default:
 604             defs_to_varying (insn);
 605         }
 606
 607       if (simplified && GET_CODE (simplified) == CONST_INT)
 608         {
 609           if (values[REGNO (dest)].lattice_val != CONSTANT
 610               || values[REGNO (dest)].const_value != simplified)
 611             SET_BIT (ssa_edges, REGNO (dest));
 612
 613           values[REGNO (dest)].lattice_val = CONSTANT;
 614           values[REGNO (dest)].const_value = simplified;
 615         }
 616       else
 617         defs_to_varying (insn);
 618     }
 619 }
 620
 621 /* Iterate over the FLOW_EDGES work list.  Simulate the target block
 622    for each edge.  */
 623 static void
 624 examine_flow_edges (void)
 625 {
 626   while (flow_edges != NULL)
 627     {
 628       basic_block succ_block;
 629       rtx curr_phi_node;
 630
 631       /* Pull the next block to simulate off the worklist.  */
 632       succ_block = flow_edges->dest;
 633       flow_edges = edge_info[EIE (flow_edges->src, flow_edges->dest)];
 634
 635       /* There is nothing to do for the exit block.  */
 636       if (succ_block == EXIT_BLOCK_PTR)
 637         continue;
 638
 639       /* Always simulate PHI nodes, even if we have simulated this block
 640          before.  Note that all PHI nodes are consecutive within a block.  */
 641       for (curr_phi_node = first_phi_node (succ_block);
 642            PHI_NODE_P (curr_phi_node);
 643            curr_phi_node = NEXT_INSN (curr_phi_node))
 644         visit_phi_node (curr_phi_node, succ_block);
 645
 646       /* If this is the first time we've simulated this block, then we
 647          must simulate each of its insns.  */
 648       if (!TEST_BIT (executable_blocks, succ_block->index))
 649         {
 650           rtx currinsn;
 651           edge succ_edge = succ_block->succ;
 652
 653           /* Note that we have simulated this block.  */
 654           SET_BIT (executable_blocks, succ_block->index);
 655
 656           /* Simulate each insn within the block.  */
 657           currinsn = succ_block->head;
 658           while (currinsn != succ_block->end)
 659             {
 660               if (INSN_P (currinsn))
 661                 visit_expression (currinsn, succ_block);
 662
 663               currinsn = NEXT_INSN (currinsn);
 664             }
 665
 666           /* Don't forget the last insn in the block.  */
 667           if (INSN_P (currinsn))
 668             visit_expression (currinsn, succ_block);
 669
 670           /* If we haven't looked at the next block, and it has a
 671              single successor, add it onto the worklist.  This is because
 672              if we only have one successor, we know it gets executed,
 673              so we don't have to wait for cprop to tell us. */
 674           if (succ_edge != NULL
 675               && succ_edge->succ_next == NULL
 676               && !TEST_BIT (executable_edges,
 677                             EIE (succ_edge->src, succ_edge->dest)))
 678             {
 679               SET_BIT (executable_edges,
 680                        EIE (succ_edge->src, succ_edge->dest));
 681               edge_info[EIE (succ_edge->src, succ_edge->dest)] = flow_edges;
 682               flow_edges = succ_edge;
 683             }
 684         }
 685     }
 686 }
 687
 688 /* Follow the def-use chains for each definition on the worklist and
 689    simulate the uses of the definition.  */
 690
 691 static void
 692 follow_def_use_chains ()
 693 {
 694   /* Iterate over all the entries on the SSA_EDGES worklist.  */
 695   while (sbitmap_first_set_bit (ssa_edges) >= 0)
 696     {
 697       int member;
 698       struct df_link *curruse;
 699
 700       /* Pick an entry off the worklist (it does not matter which
 701          entry we pick).  */
 702       member = sbitmap_first_set_bit (ssa_edges);
 703       RESET_BIT (ssa_edges, member);
 704
 705       /* Iterate through all the uses of this entry.  */
 706       for (curruse = df_analyzer->regs[member].uses; curruse;
 707            curruse = curruse->next)
 708         {
 709           rtx useinsn;
 710
 711           useinsn = DF_REF_INSN (curruse->ref);
 712           if (PHI_NODE_P (useinsn))
 713             {
 714               if (TEST_BIT (executable_blocks, BLOCK_NUM (useinsn)))
 715                 visit_phi_node (useinsn, BLOCK_FOR_INSN (useinsn));
 716             }
 717           else
 718             {
 719               if (TEST_BIT (executable_blocks, BLOCK_NUM (useinsn)))
 720                 visit_expression (useinsn, BLOCK_FOR_INSN (useinsn));
 721             }
 722         }
 723     }
 724 }
 725
 726 /* Examine each edge to see if we were able to prove any were
 727    not executable.
 728
 729    If an edge is not executable, then we can remove its alternative
 730    in PHI nodes as the destination of the edge, we can simplify the
 731    conditional branch at the source of the edge, and we can remove
 732    the edge from the CFG.  Note we do not delete unreachable blocks
 733    yet as the DF analyzer can not deal with that yet.  */
 734 static void
 735 optimize_unexecutable_edges (edges, executable_edges)
 736      struct edge_list *edges;
 737      sbitmap executable_edges;
 738 {
 739   int i;
 740
 741   for (i = 0; i < NUM_EDGES (edges); i++)
 742     {
 743       if (!TEST_BIT (executable_edges, i))
 744         {
 745           edge edge = INDEX_EDGE (edges, i);
 746
 747           if (edge->flags & EDGE_ABNORMAL)
 748             continue;
 749
 750           /* We found an edge that is not executable.  First simplify
 751              the PHI nodes in the target block.  */
 752           if (edge->dest != EXIT_BLOCK_PTR)
 753             {
 754               rtx insn = first_phi_node (edge->dest);
 755
 756               while (PHI_NODE_P (insn))
 757                 {
 758                   remove_phi_alternative (PATTERN (insn), edge->src);
 759                   insn = NEXT_INSN (insn);
 760                 }
 761             }
 762
 763           /* Since the edge was not executable, remove it from the CFG.  */
 764           remove_edge (edge);
 765         }
 766     }
 767
 768   /* We have removed all the unexecutable edges from the CFG.  Fix up
 769      the conditional jumps at the end of any affected block.
 770
 771      We have three cases to deal with:
 772
 773        a. Both outgoing edges are not executable.  This happens if the
 774           source block is not reachable.  We will deal with this by
 775           deleting all the insns in the block later.
 776
 777        b. The fall-thru edge is not executable.  In this case we
 778           change the conditional jump into an unconditional jump and
 779           add a BARRIER after the unconditional jump.  Note that since
 780           we are working on generic RTL we can change the jump in-place
 781           instead of dealing with the headache of reemitting the jump.
 782
 783        c. The branch taken edge is not executable.  In this case
 784           we turn the jump into (set (pc) (pc)) which is a nop-jump
 785           and we will remove the unrecognizable insn later.
 786
 787      In cases B & C we are removing uses of registers, so make sure
 788      to note those changes for the DF analyzer.  */
 789
 790   for (i = 0; i < n_basic_blocks; i++)
 791     {
 792       basic_block bb = BASIC_BLOCK (i);
 793       rtx insn = bb->end;
 794       edge edge = bb->succ;
 795
 796       /* If we have no predecessors, then this block is unreachable and
 797          will be cleaned up when we remove unreachable blocks.  */
 798       if (bb->pred == NULL || GET_CODE (insn) != JUMP_INSN)
 799         continue;
 800
 801       /* If this block ends in a conditional jump, but only has one
 802          successor, then the jump needs adjustment.  */
 803       if (condjump_p (insn) && ! simplejump_p (insn)
 804           && bb->succ && bb->succ->succ_next == NULL)
 805         {
 806           /* If the fallthru edge is the executable edge, then turn
 807              this jump into a nop jump, otherwise make it an unconditinoal
 808              jump to its target.  */
 809           if (edge->flags & EDGE_FALLTHRU)
 810             {
 811               PUT_CODE (insn, NOTE);
 812               NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
 813             }
 814           else
 815             {
 816               SET_SRC (PATTERN (insn)) = gen_rtx_LABEL_REF (Pmode,
 817                                                             JUMP_LABEL (insn));
 818               emit_barrier_after (insn);
 819               INSN_CODE (insn) = -1;
 820             }
 821
 822           /* Inform the DF analyzer that this insn changed.  */
 823           df_insn_modify (df_analyzer, BLOCK_FOR_INSN (insn), insn);
 824         }
 825     }
 826 }
 827
 828 /* Perform substitution of known values for pseudo registers.
 829
 830    ??? Note we do not do simplifications or constant folding here, it
 831    is unlikely that any significant simplifications can be done here
 832    anyway.  Consider that if the simplification would result in an
 833    expression that produces a constant value that the value would
 834    have been discovered and recorded already.
 835
 836    We perform two transformations.  First, we initialize pseudos to their
 837    known constant values at their definition point.  Second, we try to
 838    replace uses with the known constant value.  */
 839
 840 static void
 841 ssa_ccp_substitute_constants ()
 842 {
 843   int i;
 844
 845   for (i = FIRST_PSEUDO_REGISTER; i < VARRAY_SIZE (ssa_definition); i++)
 846     {
 847       if (values[i].lattice_val == CONSTANT)
 848         {
 849           rtx def = VARRAY_RTX (ssa_definition, i);
 850           rtx set = single_set (def);
 851           struct df_link *curruse;
 852
 853           if (! set)
 854             continue;
 855
 856           /* Do not try to simplify PHI nodes down to a constant load.
 857              That will be done later as we translate out of SSA.  Also,
 858              doing that here could violate the rule that all PHI nodes
 859              are consecutive at the start of the basic block.  */
 860           if (! PHI_NODE_P (def))
 861             {
 862               SET_SRC (set) = values[i].const_value;
 863               INSN_CODE (def) = -1;
 864               df_insn_modify (df_analyzer, BLOCK_FOR_INSN (def), def);
 865             }
 866
 867           /* Iterate through all the uses of this entry and try replacements
 868              there too.  Note it is not particularly profitable to try
 869              and fold/simplify expressions here as most of the common
 870              cases were handled above.  */
 871           for (curruse = df_analyzer->regs[i].uses;
 872                curruse;
 873                curruse = curruse->next)
 874             {
 875               rtx useinsn;
 876
 877               useinsn = DF_REF_INSN (curruse->ref);
 878
 879               if (!INSN_DELETED_P (useinsn)
 880                   && ! (GET_CODE (useinsn) == NOTE
 881                         && NOTE_LINE_NUMBER (useinsn) == NOTE_INSN_DELETED)
 882                   && (GET_CODE (useinsn) == INSN
 883                       || GET_CODE (useinsn) == JUMP_INSN))
 884                 {
 885                   validate_replace_src (regno_reg_rtx [i],
 886                                         values[i].const_value,
 887                                         useinsn);
 888                   INSN_CODE (useinsn) = -1;
 889                   df_insn_modify (df_analyzer,
 890                                   BLOCK_FOR_INSN (useinsn),
 891                                   useinsn);
 892                 }
 893
 894             }
 895         }
 896     }
 897 }
 898
 899 /* Now find all unreachable basic blocks.  All the insns in those
 900    blocks are unreachable, so delete them and mark any necessary
 901    updates for the DF analyzer.  */
 902
 903 static void
 904 ssa_ccp_df_delete_unreachable_insns ()
 905 {
 906   int i;
 907
 908   /* Use the CFG to find all the reachable blocks.  */
 909   find_unreachable_blocks ();
 910
 911   /* Now we know what blocks are not reachable.  Mark all the insns
 912      in those blocks as deleted for the DF analyzer.   We'll let the
 913      normal flow code actually remove the unreachable blocks.  */
 914   for (i = n_basic_blocks - 1; i >= 0; --i)
 915     {
 916       basic_block b = BASIC_BLOCK (i);
 917
 918       if (b->aux != NULL)
 919         /* This block was found.  Tidy up the mark.  */
 920         b->aux = NULL;
 921       else
 922         {
 923           rtx start = b->head;
 924           rtx end = b->end;
 925           rtx tmp;
 926
 927           /* Include any jump table following the basic block.  */
 928           end = b->end;
 929           if (GET_CODE (end) == JUMP_INSN
 930               && (tmp = JUMP_LABEL (end)) != NULL_RTX
 931               && (tmp = NEXT_INSN (tmp)) != NULL_RTX
 932               && GET_CODE (tmp) == JUMP_INSN
 933               && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
 934                   || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
 935             end = tmp;
 936
 937           while (1)
 938             {
 939               rtx next = NEXT_INSN (start);
 940
 941               if (GET_CODE (start) == INSN
 942                   || GET_CODE (start) == CALL_INSN
 943                   || GET_CODE (start) == JUMP_INSN)
 944                 df_insn_delete (df_analyzer, BLOCK_FOR_INSN (start), start);
 945
 946               if (start == end)
 947                 break;
 948               start = next;
 949             }
 950         }
 951     }
 952 }
 953
 954
 955 /* Main entry point for SSA Conditional Constant Propagation.
 956
 957    Long term it should accept as input the specific flow graph to
 958    operate on so that it can be called for sub-graphs.  */
 959
 960 void
 961 ssa_const_prop (void)
 962 {
 963   unsigned int i;
 964   edge curredge;
 965
 966   /* We need alias analysis (for what?) */
 967   init_alias_analysis ();
 968
 969   df_analyzer = df_init ();
 970   df_analyse (df_analyzer, 0,
 971               DF_RD_CHAIN | DF_RU_CHAIN | DF_REG_INFO | DF_HARD_REGS);
 972
 973   /* We need mappings from insn to its containing block.  */
 974   compute_bb_for_insn (get_max_uid ());
 975
 976   /* Perform a quick and dirty dead code elimination pass.  This is not
 977      as aggressive as it could be, but it's good enough to clean up a
 978      lot of unwanted junk and it is fast.  */
 979   ssa_fast_dce (df_analyzer);
 980
 981   /* Build an edge list from the CFG.  */
 982   edges = create_edge_list ();
 983
 984   /* Initialize the values array with everything as undefined.  */
 985   values = (value *) xmalloc (VARRAY_SIZE (ssa_definition) * sizeof (value));
 986   for (i = 0; i < VARRAY_SIZE (ssa_definition); i++)
 987     {
 988       if (i < FIRST_PSEUDO_REGISTER)
 989         values[i].lattice_val = VARYING;
 990       else
 991         values[i].lattice_val = UNDEFINED;
 992       values[i].const_value = NULL;
 993     }
 994
 995   ssa_edges = sbitmap_alloc (VARRAY_SIZE (ssa_definition));
 996   sbitmap_zero (ssa_edges);
 997
 998   executable_blocks = sbitmap_alloc (n_basic_blocks);
 999   sbitmap_zero (executable_blocks);
1000
1001   executable_edges = sbitmap_alloc (NUM_EDGES (edges));
1002   sbitmap_zero (executable_edges);
1003
1004   edge_info = (edge *) xmalloc (NUM_EDGES (edges) * sizeof (edge));
1005   flow_edges = ENTRY_BLOCK_PTR->succ;
1006
1007   /* Add the successors of the entry block to the edge worklist.  That
1008      is enough of a seed to get SSA-CCP started.  */
1009   for (curredge = ENTRY_BLOCK_PTR->succ; curredge;
1010        curredge = curredge->succ_next)
1011     {
1012       int index = EIE (curredge->src, curredge->dest);
1013       SET_BIT (executable_edges, index);
1014       edge_info[index] = curredge->succ_next;
1015     }
1016
1017   /* Iterate until until the worklists are empty.  */
1018   do
1019     {
1020       examine_flow_edges ();
1021       follow_def_use_chains ();
1022     }
1023   while (flow_edges != NULL);
1024
1025   /* Now perform substitutions based on the known constant values.  */
1026   ssa_ccp_substitute_constants ();
1027
1028   /* Remove unexecutable edges from the CFG and make appropriate
1029      adjustments to PHI nodes.  */
1030   optimize_unexecutable_edges (edges, executable_edges);
1031
1032   /* Now remove all unreachable insns and update the DF information.
1033      as appropriate.  */
1034   ssa_ccp_df_delete_unreachable_insns ();
1035
1036 #if 0
1037   /* The DF analyzer expects the number of blocks to remain constant,
1038      so we can't remove unreachable blocks.
1039
1040      Code the DF analyzer calls expects there to be no unreachable
1041      blocks in the CFG.  So we can't leave unreachable blocks in the
1042      CFG.
1043
1044      So, there is no way to do an incremental update of the DF data
1045      at this point.  */
1046   df_analyse (df_analyzer, 0,
1047               DF_RD_CHAIN | DF_RU_CHAIN | DF_REG_INFO | DF_HARD_REGS);
1048 #endif
1049
1050   /* Clean up any dead code exposed by SSA-CCP, do this after updating
1051      the dataflow information!  */
1052   ssa_fast_dce (df_analyzer);
1053
1054   free (values);
1055   values = NULL;
1056
1057   free (edge_info);
1058   edge_info = NULL;
1059
1060   sbitmap_free (executable_blocks);
1061   executable_blocks = NULL;
1062
1063   free_edge_list (edges);
1064   edges = NULL;
1065
1066   sbitmap_free (executable_edges);
1067   executable_edges = NULL;
1068
1069   df_finish (df_analyzer);
1070   end_alias_analysis ();
1071 }
1072
1073 static int
1074 mark_references (current_rtx, data)
1075      rtx *current_rtx;
1076      void *data;
1077 {
1078   rtx x = *current_rtx;
1079   sbitmap worklist = (sbitmap)data;
1080
1081   if (x == NULL_RTX)
1082     return 0;
1083
1084   if (GET_CODE (x) == SET)
1085     {
1086       rtx dest = SET_DEST (x);
1087
1088       if (GET_CODE (dest) == STRICT_LOW_PART
1089           || GET_CODE (dest) == SUBREG
1090           || GET_CODE (dest) == SIGN_EXTRACT
1091           || GET_CODE (dest) == ZERO_EXTRACT)
1092         {
1093           rtx reg;
1094
1095           reg = dest;
1096
1097           while (GET_CODE (reg) == STRICT_LOW_PART
1098                  || GET_CODE (reg) == SUBREG
1099                  || GET_CODE (reg) == SIGN_EXTRACT
1100                  || GET_CODE (reg) == ZERO_EXTRACT)
1101             reg = XEXP (reg, 0);
1102
1103           if (GET_CODE (reg) == REG)
1104             SET_BIT (worklist, REGNO (reg));
1105         }
1106
1107       if (GET_CODE (dest) == REG)
1108         {
1109           for_each_rtx (&SET_SRC (x), mark_references, data);
1110           return -1;
1111         }
1112
1113       return 0;
1114     }
1115   else if (GET_CODE (x) == REG)
1116     {
1117       SET_BIT (worklist, REGNO (x));
1118       return -1;
1119     }
1120   else if (GET_CODE (x) == CLOBBER)
1121     return -1;
1122   else
1123     return 0;
1124 }
1125
1126 static void
1127 ssa_fast_dce (df)
1128      struct df *df;
1129 {
1130   sbitmap worklist = sbitmap_alloc (VARRAY_SIZE (ssa_definition));
1131   sbitmap_ones (worklist);
1132
1133   /* Iterate on the worklist until there's no definitions left to
1134      examine.  */
1135   while (sbitmap_first_set_bit (worklist) >= 0)
1136     {
1137       struct df_link *curruse;
1138       int reg, found_use;
1139
1140       /* Remove an item from the worklist.  */
1141       reg = sbitmap_first_set_bit (worklist);
1142       RESET_BIT (worklist, reg);
1143
1144       /* We never consider deleting assignments to hard regs or things
1145          which do not have SSA definitions, or things we have already
1146          deleted, or things with unusual side effects.  */
1147       if (reg < FIRST_PSEUDO_REGISTER
1148           || ! VARRAY_RTX (ssa_definition, reg)
1149           || INSN_DELETED_P (VARRAY_RTX (ssa_definition, reg))
1150           || (GET_CODE (VARRAY_RTX (ssa_definition, reg)) == NOTE
1151               && (NOTE_LINE_NUMBER (VARRAY_RTX (ssa_definition, reg))
1152                   == NOTE_INSN_DELETED))
1153           || side_effects_p (PATTERN (VARRAY_RTX (ssa_definition, reg))))
1154         continue;
1155
1156       /* Iterate over the uses of this register.  If we can not find
1157          any uses that have not been deleted, then the definition of
1158          this register is dead.  */
1159       found_use = 0;
1160       for (curruse = df->regs[reg].uses; curruse; curruse = curruse->next)
1161         {
1162           rtx useinsn;
1163
1164           if (curruse->ref
1165               && DF_REF_INSN (curruse->ref)
1166               && ! INSN_DELETED_P (DF_REF_INSN (curruse->ref))
1167               && ! (GET_CODE (DF_REF_INSN (curruse->ref)) == NOTE
1168                     && (NOTE_LINE_NUMBER (DF_REF_INSN (curruse->ref))
1169                         == NOTE_INSN_DELETED))
1170               && DF_REF_INSN (curruse->ref) != VARRAY_RTX (ssa_definition, reg))
1171             {
1172               found_use = 1;
1173               break;
1174             }
1175         }
1176
1177       /* If we did not find a use of this register, then the definition
1178          of this register is dead.  */
1179
1180       if (! found_use)
1181         {
1182           rtx def = VARRAY_RTX (ssa_definition, reg);
1183
1184           /* Add all registers referenced by INSN to the work
1185              list.  */
1186           for_each_rtx (&PATTERN (def), mark_references, worklist);
1187
1188           /* Inform the analyzer that this insn is going to be
1189              deleted.  */
1190           df_insn_delete (df, BLOCK_FOR_INSN (def), def);
1191
1192           if (PHI_NODE_P (def))
1193             {
1194               if (def == BLOCK_FOR_INSN (def)->head
1195                   && def == BLOCK_FOR_INSN (def)->end)
1196                 {
1197                   /* Delete it.  */
1198                   PUT_CODE (def, NOTE);
1199                   NOTE_LINE_NUMBER (def) = NOTE_INSN_DELETED;
1200                 }
1201               else if (def == BLOCK_FOR_INSN (def)->head)
1202                 {
1203                   BLOCK_FOR_INSN (def)->head = NEXT_INSN (def);
1204                   flow_delete_insn (def);
1205                 }
1206               else if (def == BLOCK_FOR_INSN (def)->end)
1207                 {
1208                   BLOCK_FOR_INSN (def)->end = PREV_INSN (def);
1209                   flow_delete_insn (def);
1210                 }
1211               else
1212                 flow_delete_insn (def);
1213             }
1214           else
1215             {
1216               flow_delete_insn (def);
1217             }
1218           VARRAY_RTX (ssa_definition, reg) = NULL;
1219         }
1220     }
1221 }