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