2002-02-19 Philip Blundell <philb@gnu.org>

[official-gcc.git] / gcc / ssa-ccp.c

/* Conditional constant propagation pass for the GNU compiler.
   Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc.
   Original framework by Daniel Berlin <dan@cgsoftware.com>
   Fleshed out and major cleanups by Jeff Law <law@redhat.com>
   
This file is part of GCC.
   
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2, or (at your option) any later
version.
   
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.
   
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING.  If not, write to the Free
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.  */

/* Conditional constant propagation.

   References:

     Constant propagation with conditional branches,
     Wegman and Zadeck, ACM TOPLAS 13(2):181-210.

     Building an Optimizing Compiler,
     Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.

     Advanced Compiler Design and Implementation,
     Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6

   The overall structure is as follows:

        1. Run a simple SSA based DCE pass to remove any dead code.
        2. Run CCP to compute what registers are known constants
           and what edges are not executable.  Remove unexecutable
           edges from the CFG and simplify PHI nodes.
        3. Replace registers with constants where possible.
        4. Remove unreachable blocks computed in step #2.
        5. Another simple SSA DCE pass to remove dead code exposed
           by CCP.

   When we exit, we are still in SSA form. 


   Potential further enhancements:

    1. Handle SUBREGs, STRICT_LOW_PART, etc in destinations more
       gracefully.

    2. Handle insns with multiple outputs more gracefully.

    3. Handle CONST_DOUBLE and symbolic constants.

    4. Fold expressions after performing constant substitutions.  */


#include "config.h"
#include "system.h"

#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "ssa.h"
#include "insn-config.h"
#include "recog.h"
#include "output.h"
#include "errors.h"
#include "ggc.h"
#include "df.h"
#include "function.h"
\f
/* Possible lattice values.  */

typedef enum
{
  UNDEFINED,
  CONSTANT,
  VARYING
} latticevalue;

/* Main structure for CCP. 

   Contains the lattice value and, if it's a constant, the constant
   value.  */
typedef struct
{
  latticevalue lattice_val;
  rtx const_value;
} value;

/* Array of values indexed by register number.  */
static value *values;

/* A bitmap to keep track of executable blocks in the CFG.  */
static sbitmap executable_blocks;

/* A bitmap for all executable edges in the CFG.  */
static sbitmap executable_edges;

/* Array of edges on the work list.  */
static edge *edge_info;

/* We need an edge list to be able to get indexes easily.  */
static struct edge_list *edges;

/* For building/following use-def and def-use chains.  */
static struct df *df_analyzer;

/* Current edge we are operating on, from the worklist */
static edge flow_edges;

/* Bitmap of SSA edges which will need reexamination as their definition
   has changed.  */
static sbitmap ssa_edges;

/* Simple macros to simplify code */
#define SSA_NAME(x) REGNO (SET_DEST (x))
#define PHI_PARMS(x) XVEC (SET_SRC (x), 0)
#define EIE(x,y) EDGE_INDEX (edges, x, y)

static void visit_phi_node             PARAMS ((rtx, basic_block));
static void visit_expression           PARAMS ((rtx, basic_block));
static void defs_to_undefined          PARAMS ((rtx));
static void defs_to_varying            PARAMS ((rtx));
static void examine_flow_edges         PARAMS ((void));
static int mark_references             PARAMS ((rtx *, void *));
static void follow_def_use_chains      PARAMS ((void));
static void optimize_unexecutable_edges PARAMS ((struct edge_list *, sbitmap));
static void ssa_ccp_substitute_constants PARAMS ((void));
static void ssa_ccp_df_delete_unreachable_insns PARAMS ((void));
static void ssa_fast_dce PARAMS ((struct df *));

/* Loop through the PHI_NODE's parameters for BLOCK and compare their
   lattice values to determine PHI_NODE's lattice value.  */
static void
visit_phi_node (phi_node, block)
     rtx phi_node;
     basic_block block;
{
  unsigned int i;
  rtx phi_node_expr = NULL;
  unsigned int phi_node_name = SSA_NAME (PATTERN (phi_node));
  latticevalue phi_node_lattice_val = UNDEFINED;
  rtx pat = PATTERN (phi_node);
  rtvec phi_vec = XVEC (SET_SRC (pat), 0);
  unsigned int num_elem = GET_NUM_ELEM (phi_vec);

  for (i = 0; i < num_elem; i += 2)
    {
      if (TEST_BIT (executable_edges,
                    EIE (BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec, i + 1))),
                         block)))
        {
          unsigned int current_parm
            = REGNO (RTVEC_ELT (phi_vec, i));

          latticevalue current_parm_lattice_val
            = values[current_parm].lattice_val;

          /* If any node is VARYING, then new value of PHI_NODE
             is VARYING.  */
          if (current_parm_lattice_val == VARYING)
            {
              phi_node_lattice_val = VARYING;
              phi_node_expr = NULL;
              break;
            }

          /* If we have more than one distinct constant, then the new
             value of PHI_NODE is VARYING.  */
          if (current_parm_lattice_val == CONSTANT
              && phi_node_lattice_val == CONSTANT
              && values[current_parm].const_value != phi_node_expr)
            {
              phi_node_lattice_val = VARYING;
              phi_node_expr = NULL;
              break;
            }

          /* If the current value of PHI_NODE is UNDEFINED and one
             node in PHI_NODE is CONSTANT, then the new value of the
             PHI is that CONSTANT.  Note this can turn into VARYING
             if we find another distinct constant later.  */ 
          if (phi_node_lattice_val == UNDEFINED
              && phi_node_expr == NULL
              && current_parm_lattice_val == CONSTANT)
            {
              phi_node_expr = values[current_parm].const_value;
              phi_node_lattice_val = CONSTANT;
              continue;
            }
        }
    }

  /* If the value of PHI_NODE changed, then we will need to
     re-execute uses of the output of PHI_NODE.  */
  if (phi_node_lattice_val != values[phi_node_name].lattice_val)
    {
      values[phi_node_name].lattice_val = phi_node_lattice_val;
      values[phi_node_name].const_value = phi_node_expr;
      SET_BIT (ssa_edges, phi_node_name);
    }
}

/* Sets all defs in an insn to UNDEFINED.  */
static void
defs_to_undefined (insn)
     rtx insn;
{
  struct df_link *currdef;
  for (currdef = DF_INSN_DEFS (df_analyzer, insn); currdef;
       currdef = currdef->next)
    {
      if (values[DF_REF_REGNO (currdef->ref)].lattice_val != UNDEFINED)
        SET_BIT (ssa_edges, DF_REF_REGNO (currdef->ref));
      values[DF_REF_REGNO (currdef->ref)].lattice_val = UNDEFINED;
    }
}

/* Sets all defs in an insn to VARYING.  */
static void
defs_to_varying (insn)
     rtx insn;
{
  struct df_link *currdef;
  for (currdef = DF_INSN_DEFS (df_analyzer, insn); currdef;
       currdef = currdef->next)
    {
      if (values[DF_REF_REGNO (currdef->ref)].lattice_val != VARYING)
        SET_BIT (ssa_edges, DF_REF_REGNO (currdef->ref));
      values[DF_REF_REGNO (currdef->ref)].lattice_val = VARYING;
    }
}

/* Go through the expression, call the appropriate evaluation routines
   to attempt cprop */
static void
visit_expression (insn, block)
     rtx insn;
     basic_block block;
{
  rtx src, dest, set;


  /* Ugh.  CALL_INSNs may end a basic block and have multiple edges
     leading out from them.

     Mark all the outgoing edges as executable, then fall into the
     normal processing below.  */
  if (GET_CODE (insn) == CALL_INSN && block->end == insn)
    {
      edge curredge;

      for (curredge = block->succ; curredge;
           curredge = curredge->succ_next)
        {
          int index = EIE (curredge->src, curredge->dest);

          if (TEST_BIT (executable_edges, index))
            continue;

          SET_BIT (executable_edges, index);
          edge_info[index] = flow_edges;
          flow_edges = curredge;
        }
    }

  set = single_set (insn);
  if (! set)
    {
      defs_to_varying (insn);
      return;
    }

  src = SET_SRC (set);
  dest = SET_DEST (set);

  /* We may want to refine this some day.  */
  if (GET_CODE (dest) != REG && dest != pc_rtx)
    {
      defs_to_varying (insn);
      return;
    }

  /* Hard registers are not put in SSA form and thus we must consider
     them varying.  All the more reason to avoid hard registers in 
     RTL until as late as possible in the compilation.  */
  if (GET_CODE (dest) == REG && REGNO (dest) < FIRST_PSEUDO_REGISTER)
    {
      defs_to_varying (insn);
      return;
    }

  /* If this is assigning DEST to a constant, record that fact.  */
  if (GET_CODE (src) == CONST_INT && GET_CODE (insn) == INSN)
    {
      unsigned int resultreg = REGNO (dest);

      values[resultreg].lattice_val = CONSTANT;
      values[resultreg].const_value = SET_SRC (PATTERN (insn));
      SET_BIT (ssa_edges, resultreg);
    }

  /* If this is a copy operation, then we can copy the lattice values.  */
  else if (GET_CODE (src) == REG && GET_CODE (dest) == REG)
    {
      unsigned int old_value = REGNO (src);
      latticevalue old_lattice_value = values[old_value].lattice_val;
      unsigned int new_value = REGNO (dest);

      /* Unless the lattice value is going to change, don't bother
         adding the "new value" into the worklist.  */
      if (values[new_value].lattice_val != old_lattice_value
          || values[new_value].const_value != values[old_value].const_value)
        SET_BIT (ssa_edges, new_value);

      /* Copy the old lattice node info into the new value lattice node.  */
      values[new_value].lattice_val = old_lattice_value;
      values[new_value].const_value = values[old_value].const_value;
    }

  /* Handle jumps.  */
  else if (GET_CODE (insn) == JUMP_INSN)
    {
      rtx x = pc_set (insn);
      if (GET_CODE (src) != IF_THEN_ELSE)
        {
          edge curredge;

          /* This is a computed jump, table jump, or an unconditional
             jump.  For all these cases we want to mark all successor
             blocks as executable if they have not already been
             marked.

             One day we may try do better with swtich tables and
             other computed jumps.  */
          for (curredge = block->succ; curredge;
               curredge = curredge->succ_next)
            {
              int index = EIE (curredge->src, curredge->dest);

              if (TEST_BIT (executable_edges, index))
                continue;

              SET_BIT (executable_edges, index);
              edge_info[index] = flow_edges;
              flow_edges = curredge;
            }
        }
      else
        {
          edge curredge;
          enum rtx_code comparison_code;
          rtx comparison_src0;
          rtx comparison_src1;

          comparison_code = GET_CODE (XEXP (src, 0));
          comparison_src0 = XEXP (XEXP (src, 0), 0);
          comparison_src1 = XEXP (XEXP (src, 0), 1);

          /* If either operand is undefined, then there is nothing to
             do right now.  If/when operands are later defined we will
             revaluate the condition and take the appropriate action.  */
          if ((GET_CODE (comparison_src0) == REG
               && values[REGNO (comparison_src0)].lattice_val == UNDEFINED)
              || (GET_CODE (comparison_src1) == REG
                  && values[REGNO (comparison_src1)].lattice_val == UNDEFINED))
            return;

          /* If either operand is varying, then we must consider all
             paths as executable.  */
          if ((GET_CODE (comparison_src0) == REG
               && values[REGNO (comparison_src0)].lattice_val == VARYING)
              || (GET_CODE (comparison_src1) == REG
                  && values[REGNO (comparison_src1)].lattice_val == VARYING))
            {
              for (curredge = block->succ; curredge;
                   curredge = curredge->succ_next)
                {
                  int index = EIE (curredge->src, curredge->dest);

                  if (TEST_BIT (executable_edges, index))
                    continue;

                  SET_BIT (executable_edges, index);
                  edge_info[index] = flow_edges;
                  flow_edges = curredge;
                }
              return;
            }

          /* Try to simplify the comparison.  */
          if (GET_CODE (comparison_src0) == REG
              && values[REGNO (comparison_src0)].lattice_val == CONSTANT)
            comparison_src0 = values[REGNO (comparison_src0)].const_value;

          if (GET_CODE (comparison_src1) == REG
              && values[REGNO (comparison_src1)].lattice_val == CONSTANT)
            comparison_src1 = values[REGNO (comparison_src1)].const_value;

          x = simplify_ternary_operation (IF_THEN_ELSE,
                                          VOIDmode,
                                          GET_MODE (XEXP (src, 0)),
                                          gen_rtx (comparison_code,
                                                   GET_MODE (XEXP (src, 0)),
                                                   comparison_src0,
                                                   comparison_src1),
                                          XEXP (src, 1),
                                          XEXP (src, 2));

          /* Walk through all the outgoing edges from this block and see
             which (if any) we should mark as executable.  */
          for (curredge = block->succ; curredge;
               curredge = curredge->succ_next)
            {
              int index = EIE (curredge->src, curredge->dest);

              if (TEST_BIT (executable_edges, index))
                continue;

              /* If we were unable to simplify the expression at this
                 point, it's highly unlikely we'll be able to simplify
                 it later.  So consider all edges as executable if the
                 expression did not simplify.

                 If the expression simplified to (pc), then we know we
                 will take the fall-thru edge, so mark it.  Similarly,
                 if the expression simplified to (label_ref ...), then
                 we know the branch will be taken and we mark that
                 edge as taken.  */
              if (!x
                  || (x == pc_rtx
                      && (curredge->flags & EDGE_FALLTHRU))
                  || (GET_CODE (x) == LABEL_REF
                      && ! (curredge->flags & EDGE_FALLTHRU)))
                {
                  SET_BIT (executable_edges, index);
                  edge_info[index] = flow_edges;
                  flow_edges = curredge;
                }
            }
        }
    }
  else if (!PHI_NODE_P (insn))
    {
      rtx simplified = NULL;

      /* We've got some kind of INSN.  If it's simple, try to evaluate
         it and record the results. 

         We already know this insn is a single_set and that it sets
         a pseudo register.   So we just need to extract the source
         arguments, simplify them to constants if possible, then
         simplify the expression as a whole if possible.  */
      switch (GET_RTX_CLASS (GET_CODE (src)))
        {
          case '<':
            {
              rtx src0 = XEXP (src, 0);
              rtx src1 = XEXP (src, 1);
              enum machine_mode mode;

              /* If either is undefined, then the result is undefined.  */
              if ((GET_CODE (src0) == REG
                   && values[REGNO (src0)].lattice_val == UNDEFINED)
                  || (GET_CODE (src1) == REG
                      && values[REGNO (src1)].lattice_val == UNDEFINED))
                {
                  defs_to_undefined (insn);
                  break;
                }

              /* Determine the mode for the operation before we simplify
                 our arguments to constants.  */
              mode = GET_MODE (src0);
              if (mode == VOIDmode)
                mode = GET_MODE (src1);

              /* Simplify source operands to whatever known values they
                 may have.  */
              if (GET_CODE (src0) == REG
                  && values[REGNO (src0)].lattice_val == CONSTANT)
                src0 = values[REGNO (src0)].const_value;

              if (GET_CODE (src1) == REG
                  && values[REGNO (src1)].lattice_val == CONSTANT)
                src1 = values[REGNO (src1)].const_value;

              /* See if the simplifier can determine if this operation
                 computes a constant value.  */
              simplified = simplify_relational_operation (GET_CODE (src),
                                                          mode, src0, src1);
              break;

            }

          case '1':
            {
              rtx src0 = XEXP (src, 0);
              enum machine_mode mode0 = GET_MODE (src0);

              /* If the operand is undefined, then the result is undefined.  */
              if (GET_CODE (src0) == REG
                   && values[REGNO (src0)].lattice_val == UNDEFINED)
                {
                  defs_to_undefined (insn);
                  break;
                }
                
              /* Simplify source operands to whatever known values they
                 may have.  */
              if (GET_CODE (src0) == REG
                  && values[REGNO (src0)].lattice_val == CONSTANT)
                src0 = values[REGNO (src0)].const_value;

              /* See if the simplifier can determine if this operation
                 computes a constant value.  */
              simplified = simplify_unary_operation (GET_CODE (src),
                                                     GET_MODE (src),
                                                     src0,
                                                     mode0);
              break;
            }

          case '2':
          case 'c':
            {
              rtx src0 = XEXP (src, 0);
              rtx src1 = XEXP (src, 1);

              /* If either is undefined, then the result is undefined.  */
              if ((GET_CODE (src0) == REG
                   && values[REGNO (src0)].lattice_val == UNDEFINED)
                  || (GET_CODE (src1) == REG
                      && values[REGNO (src1)].lattice_val == UNDEFINED))
                {
                  defs_to_undefined (insn);
                  break;
                }
                
              /* Simplify source operands to whatever known values they
                 may have.  */
              if (GET_CODE (src0) == REG
                  && values[REGNO (src0)].lattice_val == CONSTANT)
                src0 = values[REGNO (src0)].const_value;

              if (GET_CODE (src1) == REG
                  && values[REGNO (src1)].lattice_val == CONSTANT)
                src1 = values[REGNO (src1)].const_value;

              /* See if the simplifier can determine if this operation
                 computes a constant value.  */
              simplified = simplify_binary_operation (GET_CODE (src),
                                                      GET_MODE (src),
                                                      src0, src1);
              break;
            }

          case '3':
          case 'b':
            {
              rtx src0 = XEXP (src, 0);
              rtx src1 = XEXP (src, 1);
              rtx src2 = XEXP (src, 2);

              /* If either is undefined, then the result is undefined.  */
              if ((GET_CODE (src0) == REG
                   && values[REGNO (src0)].lattice_val == UNDEFINED)
                  || (GET_CODE (src1) == REG
                      && values[REGNO (src1)].lattice_val == UNDEFINED)
                  || (GET_CODE (src2) == REG
                      && values[REGNO (src2)].lattice_val == UNDEFINED))
                {
                  defs_to_undefined (insn);
                  break;
                }
                
              /* Simplify source operands to whatever known values they
                 may have.  */
              if (GET_CODE (src0) == REG
                  && values[REGNO (src0)].lattice_val == CONSTANT)
                src0 = values[REGNO (src0)].const_value;

              if (GET_CODE (src1) == REG
                  && values[REGNO (src1)].lattice_val == CONSTANT)
                src1 = values[REGNO (src1)].const_value;

              if (GET_CODE (src2) == REG
                  && values[REGNO (src2)].lattice_val == CONSTANT)
                src2 = values[REGNO (src2)].const_value;

              /* See if the simplifier can determine if this operation
                 computes a constant value.  */
              simplified = simplify_ternary_operation (GET_CODE (src),
                                                       GET_MODE (src),
                                                       GET_MODE (src),
                                                       src0, src1, src2);
              break;
            }
        
          default:
            defs_to_varying (insn);
        }

      if (simplified && GET_CODE (simplified) == CONST_INT)
        {
          if (values[REGNO (dest)].lattice_val != CONSTANT
              || values[REGNO (dest)].const_value != simplified)
            SET_BIT (ssa_edges, REGNO (dest));

          values[REGNO (dest)].lattice_val = CONSTANT;
          values[REGNO (dest)].const_value = simplified;
        }
      else
        defs_to_varying (insn);
    }
}

/* Iterate over the FLOW_EDGES work list.  Simulate the target block
   for each edge.  */
static void
examine_flow_edges ()
{
  while (flow_edges != NULL)
    {
      basic_block succ_block;
      rtx curr_phi_node;

      /* Pull the next block to simulate off the worklist.  */
      succ_block = flow_edges->dest;
      flow_edges = edge_info[EIE (flow_edges->src, flow_edges->dest)];

      /* There is nothing to do for the exit block.  */
      if (succ_block == EXIT_BLOCK_PTR)
        continue;

      /* Always simulate PHI nodes, even if we have simulated this block
         before.  Note that all PHI nodes are consecutive within a block.  */
      for (curr_phi_node = first_insn_after_basic_block_note (succ_block);
           PHI_NODE_P (curr_phi_node);
           curr_phi_node = NEXT_INSN (curr_phi_node))
        visit_phi_node (curr_phi_node, succ_block);

      /* If this is the first time we've simulated this block, then we
         must simulate each of its insns.  */
      if (!TEST_BIT (executable_blocks, succ_block->index))
        {
          rtx currinsn;
          edge succ_edge = succ_block->succ;

          /* Note that we have simulated this block.  */
          SET_BIT (executable_blocks, succ_block->index);

          /* Simulate each insn within the block.  */
          currinsn = succ_block->head;
          while (currinsn != succ_block->end)
            {
              if (INSN_P (currinsn))
                visit_expression (currinsn, succ_block);

              currinsn = NEXT_INSN (currinsn);
            }
          
          /* Don't forget the last insn in the block.  */
          if (INSN_P (currinsn))
            visit_expression (currinsn, succ_block);
          
          /* If we haven't looked at the next block, and it has a
             single successor, add it onto the worklist.  This is because
             if we only have one successor, we know it gets executed,
             so we don't have to wait for cprop to tell us.  */
          if (succ_edge != NULL
              && succ_edge->succ_next == NULL
              && !TEST_BIT (executable_edges,
                            EIE (succ_edge->src, succ_edge->dest)))
            {
              SET_BIT (executable_edges,
                       EIE (succ_edge->src, succ_edge->dest));
              edge_info[EIE (succ_edge->src, succ_edge->dest)] = flow_edges;
              flow_edges = succ_edge;
            }
        }
    }
}

/* Follow the def-use chains for each definition on the worklist and
   simulate the uses of the definition.  */

static void
follow_def_use_chains ()
{
  /* Iterate over all the entries on the SSA_EDGES worklist.  */
  while (sbitmap_first_set_bit (ssa_edges) >= 0)
    {
      int member;
      struct df_link *curruse;

      /* Pick an entry off the worklist (it does not matter which
         entry we pick).  */
      member = sbitmap_first_set_bit (ssa_edges); 
      RESET_BIT (ssa_edges, member);

      /* Iterate through all the uses of this entry.  */
      for (curruse = df_analyzer->regs[member].uses; curruse;
           curruse = curruse->next)
        {
          rtx useinsn;

          useinsn = DF_REF_INSN (curruse->ref);
          if (PHI_NODE_P (useinsn))
            {
              if (TEST_BIT (executable_blocks, BLOCK_NUM (useinsn)))
                visit_phi_node (useinsn, BLOCK_FOR_INSN (useinsn));
            }     
          else
            {
              if (TEST_BIT (executable_blocks, BLOCK_NUM (useinsn)))
                visit_expression (useinsn, BLOCK_FOR_INSN (useinsn));
            }
        }
    }
}

/* Examine each edge to see if we were able to prove any were
   not executable. 

   If an edge is not executable, then we can remove its alternative
   in PHI nodes as the destination of the edge, we can simplify the
   conditional branch at the source of the edge, and we can remove
   the edge from the CFG.  Note we do not delete unreachable blocks
   yet as the DF analyzer can not deal with that yet.  */
static void
optimize_unexecutable_edges (edges, executable_edges)
     struct edge_list *edges;
     sbitmap executable_edges;
{
  int i;

  for (i = 0; i < NUM_EDGES (edges); i++)
    {
      if (!TEST_BIT (executable_edges, i))
        {
          edge edge = INDEX_EDGE (edges, i);

          if (edge->flags & EDGE_ABNORMAL)
            continue;

          /* We found an edge that is not executable.  First simplify
             the PHI nodes in the target block.  */
          if (edge->dest != EXIT_BLOCK_PTR)
            {
              rtx insn = first_insn_after_basic_block_note (edge->dest);

              while (PHI_NODE_P (insn))
                {
                  remove_phi_alternative (PATTERN (insn), edge->src);
                  if (rtl_dump_file)
                    fprintf (rtl_dump_file,
                             "Removing alternative for bb %d of phi %d\n", 
                             edge->src->index, SSA_NAME (PATTERN (insn)));
                  insn = NEXT_INSN (insn);
                }
            }
          if (rtl_dump_file)
            fprintf (rtl_dump_file,
                     "Removing unexecutable edge from %d to %d\n",
                     edge->src->index, edge->dest->index);
          /* Since the edge was not executable, remove it from the CFG.  */
          remove_edge (edge);
        }
    }

  /* We have removed all the unexecutable edges from the CFG.  Fix up
     the conditional jumps at the end of any affected block.

     We have three cases to deal with:

       a. Both outgoing edges are not executable.  This happens if the
          source block is not reachable.  We will deal with this by
          deleting all the insns in the block later.

       b. The fall-thru edge is not executable.  In this case we
          change the conditional jump into an unconditional jump and
          add a BARRIER after the unconditional jump.  Note that since
          we are working on generic RTL we can change the jump in-place
          instead of dealing with the headache of reemitting the jump.

       c. The branch taken edge is not executable.  In this case
          we turn the jump into (set (pc) (pc)) which is a nop-jump
          and we will remove the unrecognizable insn later.

     In cases B & C we are removing uses of registers, so make sure
     to note those changes for the DF analyzer.  */

  for (i = 0; i < n_basic_blocks; i++)
    {
      basic_block bb = BASIC_BLOCK (i);
      rtx insn = bb->end;
      edge edge = bb->succ;

      /* If we have no predecessors, then this block is unreachable and
         will be cleaned up when we remove unreachable blocks.  */
      if (bb->pred == NULL || GET_CODE (insn) != JUMP_INSN)
        continue;

      /* If this block ends in a conditional jump, but only has one
         successor, then the jump needs adjustment.  */
      if (condjump_p (insn) && ! simplejump_p (insn)
          && bb->succ && bb->succ->succ_next == NULL)
        {
          /* If the fallthru edge is the executable edge, then turn
             this jump into a nop jump, otherwise make it an unconditinoal
             jump to its target.  */
          if (edge->flags & EDGE_FALLTHRU)
            {
              PUT_CODE (insn, NOTE);
              NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
            }
          else
            {
              SET_SRC (PATTERN (insn)) = gen_rtx_LABEL_REF (Pmode,
                                                            JUMP_LABEL (insn));
              emit_barrier_after (insn);
              INSN_CODE (insn) = -1;
            }

          /* Inform the DF analyzer that this insn changed.  */
          df_insn_modify (df_analyzer, BLOCK_FOR_INSN (insn), insn);
        }
    }
}
 
/* Perform substitution of known values for pseudo registers.

   ??? Note we do not do simplifications or constant folding here, it
   is unlikely that any significant simplifications can be done here
   anyway.  Consider that if the simplification would result in an
   expression that produces a constant value that the value would
   have been discovered and recorded already.
   
   We perform two transformations.  First, we initialize pseudos to their
   known constant values at their definition point.  Second, we try to
   replace uses with the known constant value.  */

static void
ssa_ccp_substitute_constants ()
{
  unsigned int i;

  for (i = FIRST_PSEUDO_REGISTER; i < VARRAY_SIZE (ssa_definition); i++)
    {
      if (values[i].lattice_val == CONSTANT)
        {
          rtx def = VARRAY_RTX (ssa_definition, i);
          rtx set = single_set (def);
          struct df_link *curruse;

          if (! set)
            continue;

          /* Do not try to simplify PHI nodes down to a constant load.
             That will be done later as we translate out of SSA.  Also,
             doing that here could violate the rule that all PHI nodes
             are consecutive at the start of the basic block.

             Don't do anything to nodes that were already sets to
             constants.  */
          if (! PHI_NODE_P (def)
              && ! ((GET_CODE (def) == INSN
                     && GET_CODE (SET_SRC (set)) == CONST_INT)))
            {
              if (rtl_dump_file)
                fprintf (rtl_dump_file,
                         "Register %d is now set to a constant\n",
                         SSA_NAME (PATTERN (def)));
              SET_SRC (set) = values[i].const_value;
              INSN_CODE (def) = -1;
              df_insn_modify (df_analyzer, BLOCK_FOR_INSN (def), def);
            }

          /* Iterate through all the uses of this entry and try replacements
             there too.  Note it is not particularly profitable to try
             and fold/simplify expressions here as most of the common
             cases were handled above.  */
          for (curruse = df_analyzer->regs[i].uses;
               curruse;
               curruse = curruse->next)
            {
              rtx useinsn;

              useinsn = DF_REF_INSN (curruse->ref);

              if (!INSN_DELETED_P (useinsn)
                  && ! (GET_CODE (useinsn) == NOTE
                        && NOTE_LINE_NUMBER (useinsn) == NOTE_INSN_DELETED)
                  && (GET_CODE (useinsn) == INSN
                      || GET_CODE (useinsn) == JUMP_INSN))
                {
                  
                  if (validate_replace_src (regno_reg_rtx [i],
                                        values[i].const_value,
                                            useinsn))
                    {
                      if (rtl_dump_file)
                        fprintf (rtl_dump_file, 
                                 "Register %d in insn %d replaced with constant\n",
                                 i, INSN_UID (useinsn));
                      INSN_CODE (useinsn) = -1;
                      df_insn_modify (df_analyzer,
                                      BLOCK_FOR_INSN (useinsn),
                                      useinsn);
                    }
                  
                }
            }
        }
    }
}

/* Now find all unreachable basic blocks.  All the insns in those
   blocks are unreachable, so delete them and mark any necessary
   updates for the DF analyzer.  */

static void
ssa_ccp_df_delete_unreachable_insns ()
{
  int i;

  /* Use the CFG to find all the reachable blocks.  */
  find_unreachable_blocks ();

  /* Now we know what blocks are not reachable.  Mark all the insns
     in those blocks as deleted for the DF analyzer.   We'll let the
     normal flow code actually remove the unreachable blocks.  */
  for (i = n_basic_blocks - 1; i >= 0; --i)
    {
      basic_block b = BASIC_BLOCK (i);

      if (!(b->flags & BB_REACHABLE))
        {
          rtx start = b->head;
          rtx end = b->end;
          rtx tmp;

          /* Include any jump table following the basic block.  */
          end = b->end;
          if (GET_CODE (end) == JUMP_INSN
              && (tmp = JUMP_LABEL (end)) != NULL_RTX
              && (tmp = NEXT_INSN (tmp)) != NULL_RTX
              && GET_CODE (tmp) == JUMP_INSN
              && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
                  || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
            end = tmp;

          while (1)
            {
              rtx next = NEXT_INSN (start);

              if (GET_CODE (start) == INSN
                  || GET_CODE (start) == CALL_INSN
                  || GET_CODE (start) == JUMP_INSN)
                df_insn_delete (df_analyzer, BLOCK_FOR_INSN (start), start);

              if (start == end)
                break;
              start = next;
            }
        }
    }
}


/* Main entry point for SSA Conditional Constant Propagation.

   Long term it should accept as input the specific flow graph to
   operate on so that it can be called for sub-graphs.  */

void
ssa_const_prop ()
{
  unsigned int i;
  edge curredge;

  /* We need alias analysis (for what?) */
  init_alias_analysis ();

  df_analyzer = df_init ();
  df_analyse (df_analyzer, 0,
              DF_RD_CHAIN | DF_RU_CHAIN | DF_REG_INFO | DF_HARD_REGS);

  /* We need mappings from insn to its containing block.  */
  compute_bb_for_insn (get_max_uid ());

  /* Perform a quick and dirty dead code elimination pass.  This is not
     as aggressive as it could be, but it's good enough to clean up a
     lot of unwanted junk and it is fast.  */
  ssa_fast_dce (df_analyzer);

  /* Build an edge list from the CFG.  */
  edges = create_edge_list ();

  /* Initialize the values array with everything as undefined.  */
  values = (value *) xmalloc (VARRAY_SIZE (ssa_definition) * sizeof (value));
  for (i = 0; i < VARRAY_SIZE (ssa_definition); i++)
    {
      if (i < FIRST_PSEUDO_REGISTER)
        values[i].lattice_val = VARYING;
      else
        values[i].lattice_val = UNDEFINED;
      values[i].const_value = NULL;
    }

  ssa_edges = sbitmap_alloc (VARRAY_SIZE (ssa_definition));
  sbitmap_zero (ssa_edges);

  executable_blocks = sbitmap_alloc (n_basic_blocks);
  sbitmap_zero (executable_blocks);

  executable_edges = sbitmap_alloc (NUM_EDGES (edges));
  sbitmap_zero (executable_edges);

  edge_info = (edge *) xmalloc (NUM_EDGES (edges) * sizeof (edge));
  flow_edges = ENTRY_BLOCK_PTR->succ;

  /* Add the successors of the entry block to the edge worklist.  That
     is enough of a seed to get SSA-CCP started.  */
  for (curredge = ENTRY_BLOCK_PTR->succ; curredge;
       curredge = curredge->succ_next)
    {
      int index = EIE (curredge->src, curredge->dest);
      SET_BIT (executable_edges, index);
      edge_info[index] = curredge->succ_next;
    }

  /* Iterate until until the worklists are empty.  */
  do
    {
      examine_flow_edges ();
      follow_def_use_chains ();
    }
  while (flow_edges != NULL);

  /* Now perform substitutions based on the known constant values.  */
  ssa_ccp_substitute_constants ();

  /* Remove unexecutable edges from the CFG and make appropriate
     adjustments to PHI nodes.  */
  optimize_unexecutable_edges (edges, executable_edges);

  /* Now remove all unreachable insns and update the DF information.
     as appropriate.  */
  ssa_ccp_df_delete_unreachable_insns ();

#if 0
  /* The DF analyzer expects the number of blocks to remain constant,
     so we can't remove unreachable blocks.

     Code the DF analyzer calls expects there to be no unreachable
     blocks in the CFG.  So we can't leave unreachable blocks in the
     CFG.

     So, there is no way to do an incremental update of the DF data
     at this point.  */
  df_analyse (df_analyzer, 0,
              DF_RD_CHAIN | DF_RU_CHAIN | DF_REG_INFO | DF_HARD_REGS);
#endif

  /* Clean up any dead code exposed by SSA-CCP, do this after updating
     the dataflow information!  */
  ssa_fast_dce (df_analyzer);

  free (values);
  values = NULL;

  free (edge_info);
  edge_info = NULL;

  sbitmap_free (executable_blocks);
  executable_blocks = NULL;

  sbitmap_free (ssa_edges);
  ssa_edges = NULL;
  
  free_edge_list (edges);
  edges = NULL;

  sbitmap_free (executable_edges);
  executable_edges = NULL;

  df_finish (df_analyzer);
  end_alias_analysis ();
}

static int
mark_references (current_rtx, data)
     rtx *current_rtx;
     void *data;
{
  rtx x = *current_rtx;
  sbitmap worklist = (sbitmap) data;

  if (x == NULL_RTX)
    return 0;

  if (GET_CODE (x) == SET)
    {
      rtx dest = SET_DEST (x);

      if (GET_CODE (dest) == STRICT_LOW_PART
          || GET_CODE (dest) == SUBREG
          || GET_CODE (dest) == SIGN_EXTRACT
          || GET_CODE (dest) == ZERO_EXTRACT)
        {
          rtx reg;

          reg = dest;

          while (GET_CODE (reg) == STRICT_LOW_PART
                 || GET_CODE (reg) == SUBREG
                 || GET_CODE (reg) == SIGN_EXTRACT
                 || GET_CODE (reg) == ZERO_EXTRACT)
            reg = XEXP (reg, 0);

          if (GET_CODE (reg) == REG)
            SET_BIT (worklist, REGNO (reg));
        }

      if (GET_CODE (dest) == REG)
        {
          for_each_rtx (&SET_SRC (x), mark_references, data);
          return -1;
        }

      return 0;
    }
  else if (GET_CODE (x) == REG)
    {
      SET_BIT (worklist, REGNO (x));
      return -1;
    }
  else if (GET_CODE (x) == CLOBBER)
    return -1;
  else
    return 0;
}

static void
ssa_fast_dce (df)
     struct df *df;
{
  sbitmap worklist = sbitmap_alloc (VARRAY_SIZE (ssa_definition));
  sbitmap_ones (worklist);

  /* Iterate on the worklist until there's no definitions left to
     examine.  */
  while (sbitmap_first_set_bit (worklist) >= 0)
    {
      struct df_link *curruse;
      int reg, found_use;

      /* Remove an item from the worklist.  */
      reg = sbitmap_first_set_bit (worklist);
      RESET_BIT (worklist, reg);

      /* We never consider deleting assignments to hard regs or things
         which do not have SSA definitions, or things we have already
         deleted, or things with unusual side effects.  */
      if (reg < FIRST_PSEUDO_REGISTER
          || ! VARRAY_RTX (ssa_definition, reg)
          || INSN_DELETED_P (VARRAY_RTX (ssa_definition, reg))
          || (GET_CODE (VARRAY_RTX (ssa_definition, reg)) == NOTE
              && (NOTE_LINE_NUMBER (VARRAY_RTX (ssa_definition, reg))
                  == NOTE_INSN_DELETED))
          || side_effects_p (PATTERN (VARRAY_RTX (ssa_definition, reg))))
        continue;
      
      /* Iterate over the uses of this register.  If we can not find
         any uses that have not been deleted, then the definition of
         this register is dead.  */
      found_use = 0;
      for (curruse = df->regs[reg].uses; curruse; curruse = curruse->next)
        {
          if (curruse->ref
              && DF_REF_INSN (curruse->ref)
              && ! INSN_DELETED_P (DF_REF_INSN (curruse->ref))
              && ! (GET_CODE (DF_REF_INSN (curruse->ref)) == NOTE
                    && (NOTE_LINE_NUMBER (DF_REF_INSN (curruse->ref))
                        == NOTE_INSN_DELETED))
              && DF_REF_INSN (curruse->ref) != VARRAY_RTX (ssa_definition, reg))
            {
              found_use = 1;
              break;
            }
        }

      /* If we did not find a use of this register, then the definition
         of this register is dead.  */
             
      if (! found_use)
        {
          rtx def = VARRAY_RTX (ssa_definition, reg);

          /* Add all registers referenced by INSN to the work
             list.  */
          for_each_rtx (&PATTERN (def), mark_references, worklist);

          /* Inform the analyzer that this insn is going to be
             deleted.  */
          df_insn_delete (df, BLOCK_FOR_INSN (def), def);

          VARRAY_RTX (ssa_definition, reg) = NULL;
        }
    }

  sbitmap_free (worklist);
}