/* 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
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:
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
VARYING
} latticevalue;
-/* Main structure for CCP.
+/* Main structure for CCP.
Contains the lattice value and, if it's a constant, the constant
value. */
/* 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;
/* 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)
/* 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;
/* 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;
/* 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;
}
/* 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)
{
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)
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
defs_to_undefined (insn);
break;
}
-
+
/* Simplify source operands to whatever known values they
may have. */
if (GET_CODE (src0) == REG
defs_to_undefined (insn);
break;
}
-
+
/* Simplify source operands to whatever known values they
may have. */
if (GET_CODE (src0) == REG
defs_to_undefined (insn);
break;
}
-
+
/* Simplify source operands to whatever known values they
may have. */
if (GET_CODE (src0) == REG
src0, src1, src2);
break;
}
-
+
default:
defs_to_varying (insn);
}
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)
{
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,
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)
/* 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. */
{
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)))
}
/* 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
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++)
{
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);
}
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;
&& 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)
{
}
}
}
-
+
/* Perform substitution of known values for pseudo registers.
??? Note we do not do simplifications or constant folding here, it
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;
{
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;
&& (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;
BLOCK_FOR_INSN (useinsn),
useinsn);
}
-
+
}
}
}
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 ();
/* 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;
/* 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)
operate on so that it can be called for sub-graphs. */
void
-ssa_const_prop ()
+ssa_const_prop (void)
{
unsigned int i;
edge curredge;
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. */
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;
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
sbitmap_free (ssa_edges);
ssa_edges = NULL;
-
+
free_edge_list (edges);
edges = NULL;
}
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;
}
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);
== 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. */
/* 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);
}
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);
}