OSDN Git Service

* longlong.h (umul_ppmm): Add ColdFire support.
[pf3gnuchains/gcc-fork.git] / gcc / ssa-ccp.c
index d1b597c..7ff305a 100644 (file)
@@ -1,20 +1,20 @@
 /* Conditional constant propagation pass for the GNU compiler.
-   Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc.
+   Copyright (C) 2000, 2001, 2002, 2003 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
@@ -44,7 +44,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
        5. Another simple SSA DCE pass to remove dead code exposed
           by CCP.
 
-   When we exit, we are still in SSA form. 
+   When we exit, we are still in SSA form.
 
 
    Potential further enhancements:
@@ -61,6 +61,8 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 
 #include "config.h"
 #include "system.h"
+#include "coretypes.h"
+#include "tm.h"
 
 #include "rtl.h"
 #include "hard-reg-set.h"
@@ -83,7 +85,7 @@ typedef enum
   VARYING
 } latticevalue;
 
-/* Main structure for CCP. 
+/* Main structure for CCP.
 
    Contains the lattice value and, if it's a constant, the constant
    value.  */
@@ -120,27 +122,24 @@ 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 *));
+static void visit_phi_node (rtx, basic_block);
+static void visit_expression (rtx, basic_block);
+static void defs_to_undefined (rtx);
+static void defs_to_varying (rtx);
+static void examine_flow_edges (void);
+static int mark_references (rtx *, void *);
+static void follow_def_use_chains (void);
+static void optimize_unexecutable_edges (struct edge_list *, sbitmap);
+static void ssa_ccp_substitute_constants (void);
+static void ssa_ccp_df_delete_unreachable_insns (void);
+static void ssa_fast_dce (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;
+visit_phi_node (rtx phi_node, basic_block block)
 {
   unsigned int i;
   rtx phi_node_expr = NULL;
@@ -185,7 +184,7 @@ visit_phi_node (phi_node, block)
          /* 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 we find another distinct constant later.  */
          if (phi_node_lattice_val == UNDEFINED
              && phi_node_expr == NULL
              && current_parm_lattice_val == CONSTANT)
@@ -209,8 +208,7 @@ visit_phi_node (phi_node, block)
 
 /* Sets all defs in an insn to UNDEFINED.  */
 static void
-defs_to_undefined (insn)
-     rtx insn;
+defs_to_undefined (rtx insn)
 {
   struct df_link *currdef;
   for (currdef = DF_INSN_DEFS (df_analyzer, insn); currdef;
@@ -224,8 +222,7 @@ defs_to_undefined (insn)
 
 /* Sets all defs in an insn to VARYING.  */
 static void
-defs_to_varying (insn)
-     rtx insn;
+defs_to_varying (rtx insn)
 {
   struct df_link *currdef;
   for (currdef = DF_INSN_DEFS (df_analyzer, insn); currdef;
@@ -240,9 +237,7 @@ defs_to_varying (insn)
 /* Go through the expression, call the appropriate evaluation routines
    to attempt cprop */
 static void
-visit_expression (insn, block)
-     rtx insn;
-     basic_block block;
+visit_expression (rtx insn, basic_block block)
 {
   rtx src, dest, set;
 
@@ -288,7 +283,7 @@ visit_expression (insn, block)
     }
 
   /* Hard registers are not put in SSA form and thus we must consider
-     them varying.  All the more reason to avoid hard registers in 
+     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)
     {
@@ -337,7 +332,7 @@ visit_expression (insn, block)
             blocks as executable if they have not already been
             marked.
 
-            One day we may try do better with swtich tables and
+            One day we may try do better with switch tables and
             other computed jumps.  */
          for (curredge = block->succ; curredge;
               curredge = curredge->succ_next)
@@ -451,7 +446,7 @@ visit_expression (insn, block)
       rtx simplified = NULL;
 
       /* We've got some kind of INSN.  If it's simple, try to evaluate
-        it and record the results. 
+        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
@@ -511,7 +506,7 @@ visit_expression (insn, block)
                  defs_to_undefined (insn);
                  break;
                }
-               
+
              /* Simplify source operands to whatever known values they
                 may have.  */
              if (GET_CODE (src0) == REG
@@ -542,7 +537,7 @@ visit_expression (insn, block)
                  defs_to_undefined (insn);
                  break;
                }
-               
+
              /* Simplify source operands to whatever known values they
                 may have.  */
              if (GET_CODE (src0) == REG
@@ -579,7 +574,7 @@ visit_expression (insn, block)
                  defs_to_undefined (insn);
                  break;
                }
-               
+
              /* Simplify source operands to whatever known values they
                 may have.  */
              if (GET_CODE (src0) == REG
@@ -602,7 +597,7 @@ visit_expression (insn, block)
                                                       src0, src1, src2);
              break;
            }
-       
+
          default:
            defs_to_varying (insn);
        }
@@ -617,14 +612,14 @@ visit_expression (insn, block)
          values[REGNO (dest)].const_value = simplified;
        }
       else
-        defs_to_varying (insn);
+       defs_to_varying (insn);
     }
 }
 
 /* Iterate over the FLOW_EDGES work list.  Simulate the target block
    for each edge.  */
 static void
-examine_flow_edges ()
+examine_flow_edges (void)
 {
   while (flow_edges != NULL)
     {
@@ -665,11 +660,11 @@ examine_flow_edges ()
 
              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,
@@ -692,7 +687,7 @@ examine_flow_edges ()
    simulate the uses of the definition.  */
 
 static void
-follow_def_use_chains ()
+follow_def_use_chains (void)
 {
   /* Iterate over all the entries on the SSA_EDGES worklist.  */
   while (sbitmap_first_set_bit (ssa_edges) >= 0)
@@ -702,7 +697,7 @@ follow_def_use_chains ()
 
       /* Pick an entry off the worklist (it does not matter which
         entry we pick).  */
-      member = sbitmap_first_set_bit (ssa_edges); 
+      member = sbitmap_first_set_bit (ssa_edges);
       RESET_BIT (ssa_edges, member);
 
       /* Iterate through all the uses of this entry.  */
@@ -716,7 +711,7 @@ follow_def_use_chains ()
            {
              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)))
@@ -727,7 +722,7 @@ follow_def_use_chains ()
 }
 
 /* Examine each edge to see if we were able to prove any were
-   not executable. 
+   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
@@ -735,11 +730,11 @@ follow_def_use_chains ()
    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;
+optimize_unexecutable_edges (struct edge_list *edges,
+                            sbitmap executable_edges)
 {
   int i;
+  basic_block bb;
 
   for (i = 0; i < NUM_EDGES (edges); i++)
     {
@@ -761,7 +756,7 @@ optimize_unexecutable_edges (edges, executable_edges)
                  remove_phi_alternative (PATTERN (insn), edge->src);
                  if (rtl_dump_file)
                    fprintf (rtl_dump_file,
-                            "Removing alternative for bb %d of phi %d\n", 
+                            "Removing alternative for bb %d of phi %d\n",
                             edge->src->index, SSA_NAME (PATTERN (insn)));
                  insn = NEXT_INSN (insn);
                }
@@ -797,9 +792,8 @@ optimize_unexecutable_edges (edges, executable_edges)
      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++)
+  FOR_EACH_BB (bb)
     {
-      basic_block bb = BASIC_BLOCK (i);
       rtx insn = bb->end;
       edge edge = bb->succ;
 
@@ -814,7 +808,7 @@ optimize_unexecutable_edges (edges, executable_edges)
          && 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
+            this jump into a nop jump, otherwise make it an unconditional
             jump to its target.  */
          if (edge->flags & EDGE_FALLTHRU)
            {
@@ -834,7 +828,7 @@ optimize_unexecutable_edges (edges, executable_edges)
        }
     }
 }
+
 /* Perform substitution of known values for pseudo registers.
 
    ??? Note we do not do simplifications or constant folding here, it
@@ -842,13 +836,13 @@ optimize_unexecutable_edges (edges, executable_edges)
    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 ()
+ssa_ccp_substitute_constants (void)
 {
   unsigned int i;
 
@@ -856,14 +850,10 @@ ssa_ccp_substitute_constants ()
     {
       if (values[i].lattice_val == CONSTANT)
        {
-         rtx def = VARRAY_RTX (ssa_definition, i), set;
+         rtx def = VARRAY_RTX (ssa_definition, i);
+         rtx set = single_set (def);
          struct df_link *curruse;
 
-         /* Definition might have been deleted already.  */
-         if (! def)
-           continue;
-
-         set = single_set (def);
          if (! set)
            continue;
 
@@ -905,13 +895,13 @@ ssa_ccp_substitute_constants ()
                  && (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, 
+                       fprintf (rtl_dump_file,
                                 "Register %d in insn %d replaced with constant\n",
                                 i, INSN_UID (useinsn));
                      INSN_CODE (useinsn) = -1;
@@ -919,7 +909,7 @@ ssa_ccp_substitute_constants ()
                                      BLOCK_FOR_INSN (useinsn),
                                      useinsn);
                    }
-                 
+
                }
            }
        }
@@ -931,9 +921,9 @@ ssa_ccp_substitute_constants ()
    updates for the DF analyzer.  */
 
 static void
-ssa_ccp_df_delete_unreachable_insns ()
+ssa_ccp_df_delete_unreachable_insns (void)
 {
-  int i;
+  basic_block b;
 
   /* Use the CFG to find all the reachable blocks.  */
   find_unreachable_blocks ();
@@ -941,10 +931,8 @@ ssa_ccp_df_delete_unreachable_insns ()
   /* 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)
+  FOR_EACH_BB_REVERSE (b)
     {
-      basic_block b = BASIC_BLOCK (i);
-
       if (!(b->flags & BB_REACHABLE))
        {
          rtx start = b->head;
@@ -953,12 +941,7 @@ ssa_ccp_df_delete_unreachable_insns ()
 
          /* 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))
+         if (tablejump_p (end, NULL, &tmp))
            end = tmp;
 
          while (1)
@@ -985,7 +968,7 @@ ssa_ccp_df_delete_unreachable_insns ()
    operate on so that it can be called for sub-graphs.  */
 
 void
-ssa_const_prop ()
+ssa_const_prop (void)
 {
   unsigned int i;
   edge curredge;
@@ -997,9 +980,6 @@ ssa_const_prop ()
   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.  */
@@ -1009,11 +989,11 @@ ssa_const_prop ()
   edges = create_edge_list ();
 
   /* Initialize the values array with everything as undefined.  */
-  values = (value *) xmalloc (VARRAY_SIZE (ssa_definition) * sizeof (value));
+  values = 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;
+       values[i].lattice_val = VARYING;
       else
        values[i].lattice_val = UNDEFINED;
       values[i].const_value = NULL;
@@ -1022,13 +1002,13 @@ ssa_const_prop ()
   ssa_edges = sbitmap_alloc (VARRAY_SIZE (ssa_definition));
   sbitmap_zero (ssa_edges);
 
-  executable_blocks = sbitmap_alloc (n_basic_blocks);
+  executable_blocks = sbitmap_alloc (last_basic_block);
   sbitmap_zero (executable_blocks);
 
   executable_edges = sbitmap_alloc (NUM_EDGES (edges));
   sbitmap_zero (executable_edges);
 
-  edge_info = (edge *) xmalloc (NUM_EDGES (edges) * sizeof (edge));
+  edge_info = xmalloc (NUM_EDGES (edges) * sizeof (edge));
   flow_edges = ENTRY_BLOCK_PTR->succ;
 
   /* Add the successors of the entry block to the edge worklist.  That
@@ -1089,7 +1069,7 @@ ssa_const_prop ()
 
   sbitmap_free (ssa_edges);
   ssa_edges = NULL;
-  
+
   free_edge_list (edges);
   edges = NULL;
 
@@ -1101,9 +1081,7 @@ ssa_const_prop ()
 }
 
 static int
-mark_references (current_rtx, data)
-     rtx *current_rtx;
-     void *data;
+mark_references (rtx *current_rtx, void *data)
 {
   rtx x = *current_rtx;
   sbitmap worklist = (sbitmap) data;
@@ -1154,8 +1132,7 @@ mark_references (current_rtx, data)
 }
 
 static void
-ssa_fast_dce (df)
-     struct df *df;
+ssa_fast_dce (struct df *df)
 {
   sbitmap worklist = sbitmap_alloc (VARRAY_SIZE (ssa_definition));
   sbitmap_ones (worklist);
@@ -1182,7 +1159,7 @@ ssa_fast_dce (df)
                  == 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.  */
@@ -1204,7 +1181,7 @@ ssa_fast_dce (df)
 
       /* 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);
@@ -1222,4 +1199,8 @@ ssa_fast_dce (df)
     }
 
   sbitmap_free (worklist);
+
+  /* Update the use-def chains in the df_analyzer as needed.  */
+  df_analyse (df_analyzer, 0,
+             DF_RD_CHAIN | DF_RU_CHAIN | DF_REG_INFO | DF_HARD_REGS);
 }