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