+2004-06-28 Diego Novillo <dnovillo@redhat.com>
+
+ * common.opt (ftree-fre): New flag.
+ * flags.h (flag_tree_fre): Declare.
+ * opts.c (decode_options): Set.
+ * timevar.def (TV_TREE_FRE): Define.
+ * tree-flow-inline.h (may_propagate_copy): Re-arrange for
+ readability. Handle destinations that are not SSA_NAMEs.
+ * tree-flow.h (struct ptr_info_def): Move from tree.h
+ (cprop_into_stmt, cprop_into_successor_phis): Remove.
+ (vn_compute, vn_lookup_or_add, vn_add, vn_lookup): Add
+ vuse_optype parameter.
+ * tree-pass.h (pass_fre): Declare.
+ * tree-ssa-copy.c (cprop_operand): Move to tree-ssa-dom.c
+ (cprop_into_stmt): Likewise.
+ (cprop_into_successor_phis): Likewise.
+ * tree-ssa-dom.c (eliminate_redundant_computations): Fix
+ argument ordering in call to may_propagate_copy.
+ * tree-ssa-pre.c (is_undefined_value): Assume hard registers
+ to be always defined.
+ (add_to_sets): New local function.
+ (create_value_expr_from): New local function.
+ (compute_avail): Call them.
+ (eliminate): Don't ignore statements with virtual operands.
+ (init_pre): New local function.
+ (fini_pre): New local function.
+ (execute_pre): Call them.
+ Add argument DO_FRE. Don't do insertion if DO_FRE is true.
+ (do_pre): New function.
+ (do_fre): New function.
+ (gate_fre): New function.
+ (pass_fre): Declare.
+ * tree-ssa.c (init_tree_ssa): Don't call vn_init.
+ (delete_tree_ssa): Don't call vn_delete.
+ * tree-vn.c (val_expr_pair_d): Add documentation.
+ (vn_compute): Add VUSES argument to incorporate in computing
+ hash values. Update all callers.
+ (expressions_equal_p): Call operand_equal_p with
+ OEP_PURE_SAME.
+ (vn_add): Add VUSES argument. Update all callers.
+ (vn_lookup): Likewise.
+ (vn_lookup_or_add): Likewise.
+ * doc/invoke.texi: Document -ftree-fre and -fdump-tree-fre.
+
2004-06-28 Steven Bosscher <stevenb@suse.de>
* config/m32r/m32r.c (m32r_sched_odd_word_p, m32r_adjust_cost,
Common Report Var(flag_tree_dse)
Enable dead store elimination
+ftree-fre
+Common Report Var(flag_tree_fre)
+Enable Full Redundancy Elimination (FRE) on trees
+
ftree-points-to=
Common Joined RejectNegative
-fdump-tree-copyrename@r{[}-@var{n}@r{]} @gol
-fdump-tree-nrv @gol
-fdump-tree-sra@r{[}-@var{n}@r{]} @gol
+-fdump-tree-fre@r{[}-@var{n}@r{]} @gol
-feliminate-dwarf2-dups -feliminate-unused-debug-types @gol
-feliminate-unused-debug-symbols -fmem-report -fprofile-arcs -ftree-based-profiling @gol
-frandom-seed=@var{string} -fsched-verbose=@var{n} @gol
-funswitch-loops -fold-unroll-loops -fold-unroll-all-loops @gol
-ftree-pre -ftree-ccp -ftree-dce @gol
-ftree-dominator-opts -ftree-dse -ftree-copyrename @gol
--ftree-ch -ftree-sra -ftree-ter -ftree-lrs @gol
+-ftree-ch -ftree-sra -ftree-ter -ftree-lrs -ftree-fre @gol
--param @var{name}=@var{value}
-O -O0 -O1 -O2 -O3 -Os}
Dump trees after partial redundancy elimination. The file name is made
by appending @file{.pre} to the source file name.
+@item fre
+@opindex fdump-tree-fre
+Dump trees after full redundancy elimination. The file name is made
+by appending @file{.fre} to the source file name.
+
@item dce
@opindex fdump-tree-dce
Dump each function after dead code elimination. The file name is made by
Perform Partial Redundancy Elimination (PRE) on trees. This flag is
enabled by default at -O and higher.
+@item -ftree-fre
+Perform Full Redundancy Elimination (FRE) on trees. The difference
+between FRE and PRE is that FRE only considers expressions
+that are computed on all paths leading to the redundant computation.
+This analysis faster than PRE, though it exposes fewer redundancies.
+This flag is enabled by default at -O and higher.
+
@item -ftree-ccp
Perform sparse conditional constant propagation (CCP) on trees. This flag
is enabled by default at -O and higher.
};
extern enum pta_type flag_tree_points_to;
+/* Enable FRE (Full Redundancy Elimination) on trees. */
+extern int flag_tree_fre;
+
/* Nonzero means put zero initialized data in the bss section. */
extern int flag_zero_initialized_in_bss;
flag_tree_live_range_split = 1;
flag_tree_sra = 1;
flag_tree_copyrename = 1;
+ flag_tree_fre = 1;
if (!optimize_size)
{
DEFTIMEVAR (TV_TREE_CCP , "tree CCP")
DEFTIMEVAR (TV_TREE_SPLIT_EDGES , "tree split crit edges")
DEFTIMEVAR (TV_TREE_PRE , "tree PRE")
+DEFTIMEVAR (TV_TREE_FRE , "tree FRE")
DEFTIMEVAR (TV_TREE_PHIOPT , "tree linearize phis")
DEFTIMEVAR (TV_TREE_FORWPROP , "tree forward propagate")
DEFTIMEVAR (TV_TREE_DCE , "tree conservative DCE")
return false;
}
- return (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest)
- && (TREE_CODE (orig) != SSA_NAME
- || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
- && !DECL_HARD_REGISTER (SSA_NAME_VAR (dest)));
+ /* If ORIG flows in from an abnormal edge, it cannot be propagated. */
+ if (TREE_CODE (orig) == SSA_NAME
+ && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
+ return false;
+
+ /* If DEST is an SSA_NAME that flows from an abnormal edge or if it
+ represents a hard register, then it cannot be replaced. */
+ if (TREE_CODE (dest) == SSA_NAME
+ && (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest)
+ || DECL_HARD_REGISTER (SSA_NAME_VAR (dest))))
+ return false;
+
+ /* Anything else is OK. */
+ return true;
}
/* Set the default definition for VAR to DEF. */
#endif
/*---------------------------------------------------------------------------
+ Attributes for SSA_NAMEs.
+
+ NOTE: These structures are stored in struct tree_ssa_name
+ but are only used by the tree optimizers, so it makes better sense
+ to declare them here to avoid recompiling unrelated files when
+ making changes.
+---------------------------------------------------------------------------*/
+
+/* Aliasing information for SSA_NAMEs representing pointer variables. */
+struct ptr_info_def GTY(())
+{
+ /* Nonzero if points-to analysis couldn't determine where this pointer
+ is pointing to. */
+ unsigned int pt_anything : 1;
+
+ /* Nonzero if this pointer is the result of a call to malloc. */
+ unsigned int pt_malloc : 1;
+
+ /* Nonzero if the value of this pointer escapes the current function. */
+ unsigned int value_escapes_p : 1;
+
+ /* Set of variables that this pointer may point to. */
+ bitmap pt_vars;
+
+ /* If this pointer has been dereferenced, and points-to information is
+ more precise than type-based aliasing, indirect references to this
+ pointer will be represented by this memory tag, instead of the type
+ tag computed by TBAA. */
+ tree name_mem_tag;
+};
+
+
+/*---------------------------------------------------------------------------
Tree annotations stored in tree_common.ann
---------------------------------------------------------------------------*/
enum tree_ann_type { TREE_ANN_COMMON, VAR_ANN, STMT_ANN };
extern void propagate_value (use_operand_p, tree);
extern void propagate_tree_value (tree *, tree);
extern void replace_exp (use_operand_p, tree);
-extern bool cprop_into_stmt (tree, varray_type);
-extern void cprop_into_successor_phis (basic_block, varray_type, bitmap);
/* In tree-flow-inline.h */
static inline int phi_arg_from_edge (tree, edge);
/* In tree-vn.c */
-bool expressions_equal_p (tree e1, tree e2);
+bool expressions_equal_p (tree, tree);
tree get_value_handle (tree);
-hashval_t vn_compute (tree, hashval_t);
-tree vn_lookup_or_add (tree);
-void vn_add (tree, tree);
-tree vn_lookup (tree);
+hashval_t vn_compute (tree, hashval_t, vuse_optype);
+tree vn_lookup_or_add (tree, vuse_optype);
+void vn_add (tree, tree, vuse_optype);
+tree vn_lookup (tree, vuse_optype);
void vn_init (void);
void vn_delete (void);
extern struct tree_opt_pass pass_rename_ssa_copies;
extern struct tree_opt_pass pass_expand;
extern struct tree_opt_pass pass_rest_of_compilation;
+extern struct tree_opt_pass pass_fre;
#endif /* GCC_TREE_PASS_H */
SET_USE (op_p, lhd_unsave_expr_now (val));
}
+
/* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
into the operand pointed by OP_P.
replace_exp_1 (op_p, val, true);
}
+
/* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
into the tree pointed by OP_P.
*op_p = lhd_unsave_expr_now (val);
}
+
/* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
Use this version when not const/copy propagating values. For example,
{
replace_exp_1 (op_p, val, false);
}
-
-/* Replace *OP_P in STMT with any known equivalent value for *OP_P from
- CONST_AND_COPIES. */
-
-static bool
-cprop_operand (stmt_ann_t ann, use_operand_p op_p, varray_type const_and_copies)
-{
- bool may_have_exposed_new_symbols = false;
- tree val;
- tree op = USE_FROM_PTR (op_p);
-
- /* If the operand has a known constant value or it is known to be a
- copy of some other variable, use the value or copy stored in
- CONST_AND_COPIES. */
- val = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (op));
- if (val)
- {
- tree op_type, val_type;
-
- /* Do not change the base variable in the virtual operand
- tables. That would make it impossible to reconstruct
- the renamed virtual operand if we later modify this
- statement. Also only allow the new value to be an SSA_NAME
- for propagation into virtual operands. */
- if (!is_gimple_reg (op)
- && (get_virtual_var (val) != get_virtual_var (op)
- || TREE_CODE (val) != SSA_NAME))
- return false;
-
- /* Get the toplevel type of each operand. */
- op_type = TREE_TYPE (op);
- val_type = TREE_TYPE (val);
-
- /* While both types are pointers, get the type of the object
- pointed to. */
- while (POINTER_TYPE_P (op_type) && POINTER_TYPE_P (val_type))
- {
- op_type = TREE_TYPE (op_type);
- val_type = TREE_TYPE (val_type);
- }
-
- /* Make sure underlying types match before propagating a
- constant by converting the constant to the proper type. Note
- that convert may return a non-gimple expression, in which case
- we ignore this propagation opportunity. */
- if (!lang_hooks.types_compatible_p (op_type, val_type)
- && TREE_CODE (val) != SSA_NAME)
- {
- val = fold_convert (TREE_TYPE (op), val);
- if (!is_gimple_min_invariant (val)
- && TREE_CODE (val) != SSA_NAME)
- return false;
- }
-
- /* Certain operands are not allowed to be copy propagated due
- to their interaction with exception handling and some GCC
- extensions. */
- if (TREE_CODE (val) == SSA_NAME
- && !may_propagate_copy (op, val))
- return false;
-
- /* Dump details. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " Replaced '");
- print_generic_expr (dump_file, op, dump_flags);
- fprintf (dump_file, "' with %s '",
- (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
- print_generic_expr (dump_file, val, dump_flags);
- fprintf (dump_file, "'\n");
- }
-
- /* If VAL is an ADDR_EXPR or a constant of pointer type, note
- that we may have exposed a new symbol for SSA renaming. */
- if (TREE_CODE (val) == ADDR_EXPR
- || (POINTER_TYPE_P (TREE_TYPE (op))
- && is_gimple_min_invariant (val)))
- may_have_exposed_new_symbols = true;
-
- propagate_value (op_p, val);
-
- /* And note that we modified this statement. This is now
- safe, even if we changed virtual operands since we will
- rescan the statement and rewrite its operands again. */
- ann->modified = 1;
- }
- return may_have_exposed_new_symbols;
-}
-
-/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
- known value for that SSA_NAME (or NULL if no value is known).
-
- Propagate values from CONST_AND_COPIES into the uses, vuses and
- v_may_def_ops of STMT. */
-
-bool
-cprop_into_stmt (tree stmt, varray_type const_and_copies)
-{
- bool may_have_exposed_new_symbols = false;
- stmt_ann_t ann = stmt_ann (stmt);
- size_t i, num_uses, num_vuses, num_v_may_defs;
- vuse_optype vuses;
- v_may_def_optype v_may_defs;
- use_optype uses;
-
- uses = USE_OPS (ann);
- num_uses = NUM_USES (uses);
- for (i = 0; i < num_uses; i++)
- {
- use_operand_p op_p = USE_OP_PTR (uses, i);
- if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
- may_have_exposed_new_symbols
- |= cprop_operand (ann, op_p, const_and_copies);
- }
-
- vuses = VUSE_OPS (ann);
- num_vuses = NUM_VUSES (vuses);
- for (i = 0; i < num_vuses; i++)
- {
- use_operand_p op_p = VUSE_OP_PTR (vuses, i);
- if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
- may_have_exposed_new_symbols
- |= cprop_operand (ann, op_p, const_and_copies);
- }
-
- v_may_defs = V_MAY_DEF_OPS (ann);
- num_v_may_defs = NUM_V_MAY_DEFS (v_may_defs);
- for (i = 0; i < num_v_may_defs; i++)
- {
- use_operand_p op_p = V_MAY_DEF_OP_PTR (v_may_defs, i);
- if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
- may_have_exposed_new_symbols
- |= cprop_operand (ann, op_p, const_and_copies);
- }
- return may_have_exposed_new_symbols;
-}
-
-/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
- known value for that SSA_NAME (or NULL if no value is known).
-
- NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
- even if we don't know their precise value.
-
- Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
- nodes of the successors of BB. */
-
-void
-cprop_into_successor_phis (basic_block bb,
- varray_type const_and_copies,
- bitmap nonzero_vars)
-{
- edge e;
-
- /* This can get rather expensive if the implementation is naive in
- how it finds the phi alternative associated with a particular edge. */
- for (e = bb->succ; e; e = e->succ_next)
- {
- tree phi;
- int phi_num_args;
- int hint;
-
- /* If this is an abnormal edge, then we do not want to copy propagate
- into the PHI alternative associated with this edge. */
- if (e->flags & EDGE_ABNORMAL)
- continue;
-
- phi = phi_nodes (e->dest);
- if (! phi)
- continue;
-
- /* There is no guarantee that for any two PHI nodes in a block that
- the phi alternative associated with a particular edge will be
- at the same index in the phi alternative array.
-
- However, it is very likely they will be the same. So we keep
- track of the index of the alternative where we found the edge in
- the previous phi node and check that index first in the next
- phi node. If that hint fails, then we actually search all
- the entries. */
- phi_num_args = PHI_NUM_ARGS (phi);
- hint = phi_num_args;
- for ( ; phi; phi = PHI_CHAIN (phi))
- {
- int i;
- tree new;
- use_operand_p orig_p;
- tree orig;
-
- /* If the hint is valid (!= phi_num_args), see if it points
- us to the desired phi alternative. */
- if (hint != phi_num_args && PHI_ARG_EDGE (phi, hint) == e)
- ;
- else
- {
- /* The hint was either invalid or did not point to the
- correct phi alternative. Search all the alternatives
- for the correct one. Update the hint. */
- for (i = 0; i < phi_num_args; i++)
- if (PHI_ARG_EDGE (phi, i) == e)
- break;
- hint = i;
- }
-
-#ifdef ENABLE_CHECKING
- /* If we did not find the proper alternative, then something is
- horribly wrong. */
- if (hint == phi_num_args)
- abort ();
-#endif
-
- /* The alternative may be associated with a constant, so verify
- it is an SSA_NAME before doing anything with it. */
- orig_p = PHI_ARG_DEF_PTR (phi, hint);
- orig = USE_FROM_PTR (orig_p);
- if (TREE_CODE (orig) != SSA_NAME)
- continue;
-
- /* If the alternative is known to have a nonzero value, record
- that fact in the PHI node itself for future use. */
- if (bitmap_bit_p (nonzero_vars, SSA_NAME_VERSION (orig)))
- PHI_ARG_NONZERO (phi, hint) = true;
-
- /* If we have *ORIG_P in our constant/copy table, then replace
- ORIG_P with its value in our constant/copy table. */
- new = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (orig));
- if (new
- && (TREE_CODE (new) == SSA_NAME
- || is_gimple_min_invariant (new))
- && may_propagate_copy (orig, new))
- propagate_value (orig_p, new);
- }
- }
-}
/* Jump threading, redundancy elimination and const/copy propagation.
- Optimize function FNDECL based on a walk through the dominator tree.
-
This pass may expose new symbols that need to be renamed into SSA. For
every new symbol exposed, its corresponding bit will be set in
- VARS_TO_RENAME.
-
- PHASE indicates which dump file from the DUMP_FILES array to use when
- dumping debugging information. */
+ VARS_TO_RENAME. */
static void
tree_ssa_dominator_optimize (void)
return 0;
}
+
+/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
+ known value for that SSA_NAME (or NULL if no value is known).
+
+ NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
+ even if we don't know their precise value.
+
+ Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
+ nodes of the successors of BB. */
+
+static void
+cprop_into_successor_phis (basic_block bb,
+ varray_type const_and_copies,
+ bitmap nonzero_vars)
+{
+ edge e;
+
+ /* This can get rather expensive if the implementation is naive in
+ how it finds the phi alternative associated with a particular edge. */
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ tree phi;
+ int phi_num_args;
+ int hint;
+
+ /* If this is an abnormal edge, then we do not want to copy propagate
+ into the PHI alternative associated with this edge. */
+ if (e->flags & EDGE_ABNORMAL)
+ continue;
+
+ phi = phi_nodes (e->dest);
+ if (! phi)
+ continue;
+
+ /* There is no guarantee that for any two PHI nodes in a block that
+ the phi alternative associated with a particular edge will be
+ at the same index in the phi alternative array.
+
+ However, it is very likely they will be the same. So we keep
+ track of the index of the alternative where we found the edge in
+ the previous phi node and check that index first in the next
+ phi node. If that hint fails, then we actually search all
+ the entries. */
+ phi_num_args = PHI_NUM_ARGS (phi);
+ hint = phi_num_args;
+ for ( ; phi; phi = PHI_CHAIN (phi))
+ {
+ int i;
+ tree new;
+ use_operand_p orig_p;
+ tree orig;
+
+ /* If the hint is valid (!= phi_num_args), see if it points
+ us to the desired phi alternative. */
+ if (hint != phi_num_args && PHI_ARG_EDGE (phi, hint) == e)
+ ;
+ else
+ {
+ /* The hint was either invalid or did not point to the
+ correct phi alternative. Search all the alternatives
+ for the correct one. Update the hint. */
+ for (i = 0; i < phi_num_args; i++)
+ if (PHI_ARG_EDGE (phi, i) == e)
+ break;
+ hint = i;
+ }
+
+#ifdef ENABLE_CHECKING
+ /* If we did not find the proper alternative, then something is
+ horribly wrong. */
+ if (hint == phi_num_args)
+ abort ();
+#endif
+
+ /* The alternative may be associated with a constant, so verify
+ it is an SSA_NAME before doing anything with it. */
+ orig_p = PHI_ARG_DEF_PTR (phi, hint);
+ orig = USE_FROM_PTR (orig_p);
+ if (TREE_CODE (orig) != SSA_NAME)
+ continue;
+
+ /* If the alternative is known to have a nonzero value, record
+ that fact in the PHI node itself for future use. */
+ if (bitmap_bit_p (nonzero_vars, SSA_NAME_VERSION (orig)))
+ PHI_ARG_NONZERO (phi, hint) = true;
+
+ /* If we have *ORIG_P in our constant/copy table, then replace
+ ORIG_P with its value in our constant/copy table. */
+ new = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (orig));
+ if (new
+ && (TREE_CODE (new) == SSA_NAME
+ || is_gimple_min_invariant (new))
+ && may_propagate_copy (orig, new))
+ {
+ propagate_value (orig_p, new);
+ }
+ }
+ }
+}
+
+
/* Propagate known constants/copies into PHI nodes of BB's successor
blocks. */
CACHED_LHS into *EXPR_P. */
if (cached_lhs
&& (TREE_CODE (cached_lhs) != SSA_NAME
- || may_propagate_copy (cached_lhs, *expr_p)))
+ || may_propagate_copy (*expr_p, cached_lhs)))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
}
}
+/* Replace *OP_P in STMT with any known equivalent value for *OP_P from
+ CONST_AND_COPIES. */
+
+static bool
+cprop_operand (stmt_ann_t ann, use_operand_p op_p, varray_type const_and_copies)
+{
+ bool may_have_exposed_new_symbols = false;
+ tree val;
+ tree op = USE_FROM_PTR (op_p);
+
+ /* If the operand has a known constant value or it is known to be a
+ copy of some other variable, use the value or copy stored in
+ CONST_AND_COPIES. */
+ val = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (op));
+ if (val)
+ {
+ tree op_type, val_type;
+
+ /* Do not change the base variable in the virtual operand
+ tables. That would make it impossible to reconstruct
+ the renamed virtual operand if we later modify this
+ statement. Also only allow the new value to be an SSA_NAME
+ for propagation into virtual operands. */
+ if (!is_gimple_reg (op)
+ && (get_virtual_var (val) != get_virtual_var (op)
+ || TREE_CODE (val) != SSA_NAME))
+ return false;
+
+ /* Get the toplevel type of each operand. */
+ op_type = TREE_TYPE (op);
+ val_type = TREE_TYPE (val);
+
+ /* While both types are pointers, get the type of the object
+ pointed to. */
+ while (POINTER_TYPE_P (op_type) && POINTER_TYPE_P (val_type))
+ {
+ op_type = TREE_TYPE (op_type);
+ val_type = TREE_TYPE (val_type);
+ }
+
+ /* Make sure underlying types match before propagating a
+ constant by converting the constant to the proper type. Note
+ that convert may return a non-gimple expression, in which case
+ we ignore this propagation opportunity. */
+ if (!lang_hooks.types_compatible_p (op_type, val_type)
+ && TREE_CODE (val) != SSA_NAME)
+ {
+ val = fold_convert (TREE_TYPE (op), val);
+ if (!is_gimple_min_invariant (val)
+ && TREE_CODE (val) != SSA_NAME)
+ return false;
+ }
+
+ /* Certain operands are not allowed to be copy propagated due
+ to their interaction with exception handling and some GCC
+ extensions. */
+ if (TREE_CODE (val) == SSA_NAME
+ && !may_propagate_copy (op, val))
+ return false;
+
+ /* Dump details. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " Replaced '");
+ print_generic_expr (dump_file, op, dump_flags);
+ fprintf (dump_file, "' with %s '",
+ (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
+ print_generic_expr (dump_file, val, dump_flags);
+ fprintf (dump_file, "'\n");
+ }
+
+ /* If VAL is an ADDR_EXPR or a constant of pointer type, note
+ that we may have exposed a new symbol for SSA renaming. */
+ if (TREE_CODE (val) == ADDR_EXPR
+ || (POINTER_TYPE_P (TREE_TYPE (op))
+ && is_gimple_min_invariant (val)))
+ may_have_exposed_new_symbols = true;
+
+ propagate_value (op_p, val);
+
+ /* And note that we modified this statement. This is now
+ safe, even if we changed virtual operands since we will
+ rescan the statement and rewrite its operands again. */
+ ann->modified = 1;
+ }
+ return may_have_exposed_new_symbols;
+}
+
+/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
+ known value for that SSA_NAME (or NULL if no value is known).
+
+ Propagate values from CONST_AND_COPIES into the uses, vuses and
+ v_may_def_ops of STMT. */
+
+static bool
+cprop_into_stmt (tree stmt, varray_type const_and_copies)
+{
+ bool may_have_exposed_new_symbols = false;
+ stmt_ann_t ann = stmt_ann (stmt);
+ size_t i, num_uses, num_vuses, num_v_may_defs;
+ vuse_optype vuses;
+ v_may_def_optype v_may_defs;
+ use_optype uses;
+
+ uses = USE_OPS (ann);
+ num_uses = NUM_USES (uses);
+ for (i = 0; i < num_uses; i++)
+ {
+ use_operand_p op_p = USE_OP_PTR (uses, i);
+ if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
+ may_have_exposed_new_symbols
+ |= cprop_operand (ann, op_p, const_and_copies);
+ }
+
+ vuses = VUSE_OPS (ann);
+ num_vuses = NUM_VUSES (vuses);
+ for (i = 0; i < num_vuses; i++)
+ {
+ use_operand_p op_p = VUSE_OP_PTR (vuses, i);
+ if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
+ may_have_exposed_new_symbols
+ |= cprop_operand (ann, op_p, const_and_copies);
+ }
+
+ v_may_defs = V_MAY_DEF_OPS (ann);
+ num_v_may_defs = NUM_V_MAY_DEFS (v_may_defs);
+ for (i = 0; i < num_v_may_defs; i++)
+ {
+ use_operand_p op_p = V_MAY_DEF_OP_PTR (v_may_defs, i);
+ if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
+ may_have_exposed_new_symbols
+ |= cprop_operand (ann, op_p, const_and_copies);
+ }
+ return may_have_exposed_new_symbols;
+}
+
+
/* Optimize the statement pointed by iterator SI.
We try to perform some simplistic global redundancy elimination and
struct expr_pred_trans_d ept;
ept.e = e;
ept.pred = pred;
- ept.hashcode = vn_compute (e, (unsigned long) pred);
+ ept.hashcode = vn_compute (e, (unsigned long) pred, NULL);
slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
NO_INSERT);
if (!slot)
new_pair->e = e;
new_pair->pred = pred;
new_pair->v = v;
- new_pair->hashcode = vn_compute (e, (unsigned long) pred);
+ new_pair->hashcode = vn_compute (e, (unsigned long) pred, NULL);
slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
new_pair->hashcode, INSERT);
if (*slot)
*slot = (void *) new_pair;
}
+
/* Add expression E to the expression set of value V. */
void
part of the translated expression. */
static tree
-phi_translate (tree expr, value_set_t set, basic_block pred,
+phi_translate (tree expr, value_set_t set, basic_block pred,
basic_block phiblock)
{
tree phitrans = NULL;
create_tree_ann (newexpr);
TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
- vn_lookup_or_add (newexpr);
+ vn_lookup_or_add (newexpr, NULL);
expr = newexpr;
phi_trans_add (oldexpr, newexpr, pred);
}
memcpy (newexpr, expr, tree_size (expr));
create_tree_ann (newexpr);
TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
- vn_lookup_or_add (newexpr);
+ vn_lookup_or_add (newexpr, NULL);
expr = newexpr;
phi_trans_add (oldexpr, newexpr, pred);
}
tree val;
if (is_undefined_value (PHI_ARG_DEF (phi, i)))
return NULL;
- val = vn_lookup_or_add (PHI_ARG_DEF (phi, i));
+ val = vn_lookup_or_add (PHI_ARG_DEF (phi, i), NULL);
return PHI_ARG_DEF (phi, i);
}
}
}
}
-/* Find the leader for a value (IE the name representing that
+/* Find the leader for a value (i.e., the name representing that
value) in a given set, and return it. Return NULL if no leader is
found. */
if (val == NULL)
return NULL;
+
/* True constants represent themselves. */
if (TREE_CODE_CLASS (TREE_CODE (val)) == 'c')
return val;
+
/* Invariants are still represented by values, since they may be
more than a single _CST node. */
if (TREE_CONSTANT (val))
return node->expr;
}
}
+
return NULL;
}
}
v = get_value_handle (expr);
- vn_add (name, v);
+ vn_add (name, v, NULL);
insert_into_set (NEW_SETS (block), name);
value_insert_into_set (AVAIL_OUT (block), name);
if (dump_file && (dump_flags & TDF_DETAILS))
temp = create_tmp_var (type, "prephitmp");
add_referenced_tmp_var (temp);
temp = create_phi_node (temp, block);
- vn_add (PHI_RESULT (temp), val);
+ vn_add (PHI_RESULT (temp), val, NULL);
#if 0
if (!set_contains_value (AVAIL_OUT (block), val))
}
-/* Return true if EXPR has no defining statement in this procedure,
- *AND* isn't a live-on-entry parameter. */
+/* Return true if VAR is an SSA variable with no defining statement in
+ this procedure, *AND* isn't a live-on-entry parameter. */
static bool
is_undefined_value (tree expr)
-{
-#ifdef ENABLE_CHECKING
- /* We should never be handed DECL's */
- if (DECL_P (expr))
+{
+ return (TREE_CODE (expr) == SSA_NAME
+ && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
+ /* PARM_DECLs and hard registers are always defined. */
+ && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL
+ && !DECL_HARD_REGISTER (SSA_NAME_VAR (expr)));
+}
+
+
+/* Given an SSA variable VAR and an expression EXPR, compute the value
+ number for EXPR and create a value handle (VAL) for it. If VAR and
+ EXPR are not the same, associate VAL with VAR. Finally, add VAR to
+ S1 and its value handle to S2.
+
+ VUSES represent the virtual use operands associated with EXPR (if
+ any). They are used when computing the hash value for EXPR. */
+
+static inline void
+add_to_sets (tree var, tree expr, vuse_optype vuses, value_set_t s1,
+ value_set_t s2)
+{
+ tree val = vn_lookup_or_add (expr, vuses);
+
+ /* VAR and EXPR may be the same when processing statements for which
+ we are not computing value numbers (e.g., non-assignments, or
+ statements that make aliased stores). In those cases, we are
+ only interested in making VAR available as its own value. */
+ if (var != expr)
+ vn_add (var, val, vuses);
+
+ insert_into_set (s1, var);
+ value_insert_into_set (s2, var);
+}
+
+
+/* Given a unary or binary expression EXPR, create and return a new
+ expresion with the same structure as EXPR but with its operands
+ replaced with the value handles of each of the operands of EXPR.
+ Insert EXPR's operands into the EXP_GEN set for BLOCK.
+
+ VUSES represent the virtual use operands associated with EXPR (if
+ any). They are used when computing the hash value for EXPR. */
+
+static inline tree
+create_value_expr_from (tree expr, basic_block block, vuse_optype vuses)
+{
+ int i;
+ enum tree_code code = TREE_CODE (expr);
+ tree vexpr;
+
+#if defined ENABLE_CHECKING
+ if (TREE_CODE_CLASS (code) != '1'
+ && TREE_CODE_CLASS (code) != '2')
abort ();
#endif
- if (TREE_CODE (expr) == SSA_NAME)
+ if (TREE_CODE_CLASS (code) == '1')
+ vexpr = pool_alloc (unary_node_pool);
+ else
+ vexpr = pool_alloc (binary_node_pool);
+
+ memcpy (vexpr, expr, tree_size (expr));
+
+ for (i = 0; i < TREE_CODE_LENGTH (code); i++)
{
- /* XXX: Is this the correct test? */
- if (TREE_CODE (SSA_NAME_VAR (expr)) == PARM_DECL)
- return false;
- if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr)))
- return true;
+ tree op = TREE_OPERAND (expr, i);
+ tree val = vn_lookup_or_add (op, vuses);
+ if (!is_undefined_value (op))
+ value_insert_into_set (EXP_GEN (block), op);
+ TREE_OPERAND (vexpr, i) = val;
}
- return false;
+ return vexpr;
}
+
/* Compute the AVAIL set for BLOCK.
This function performs value numbering of the statements in BLOCK.
The AVAIL sets are built from information we glean while doing this
- value numbering, since the AVAIL sets contain only entry per
+ value numbering, since the AVAIL sets contain only one entry per
value.
-
AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
- AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U
- TMP_GEN[BLOCK].
-*/
+ AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
static void
compute_avail (basic_block block)
{
tree val;
tree def = default_def (param);
- val = vn_lookup_or_add (def);
+ val = vn_lookup_or_add (def, NULL);
insert_into_set (TMP_GEN (block), def);
value_insert_into_set (AVAIL_OUT (block), def);
}
tree stmt, phi;
basic_block dom;
+ /* Initially, the set of available values in BLOCK is that of
+ its immediate dominator. */
dom = get_immediate_dominator (CDI_DOMINATORS, block);
if (dom)
set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
+ /* Generate values for PHI nodes. */
for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
- {
- /* Ignore virtual PHIs until we can do PRE on expressions
- with virtual operands. */
- if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
- continue;
-
- vn_lookup_or_add (PHI_RESULT (phi));
- value_insert_into_set (AVAIL_OUT (block), PHI_RESULT (phi));
- insert_into_set (PHI_GEN (block), PHI_RESULT (phi));
- }
+ add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL,
+ PHI_GEN (block), AVAIL_OUT (block));
+ /* Now compute value numbers and populate value sets with all
+ the expressions computed in BLOCK. */
for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
{
- tree op0, op1;
+ stmt_ann_t ann;
+ size_t j;
+
stmt = bsi_stmt (bsi);
+ ann = stmt_ann (stmt);
get_stmt_operands (stmt);
-
- if (NUM_VUSES (STMT_VUSE_OPS (stmt))
- || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt))
- || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt))
- || stmt_ann (stmt)->has_volatile_ops)
+
+ /* We are only interested in assignments of the form
+ X_i = EXPR, where EXPR represents an "interesting"
+ computation, it has no volatile operands and X_i
+ doesn't flow through an abnormal edge. */
+ if (TREE_CODE (stmt) == MODIFY_EXPR
+ && !ann->has_volatile_ops
+ && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
+ && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt, 0)))
{
- size_t j;
- for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
+ tree lhs = TREE_OPERAND (stmt, 0);
+ tree rhs = TREE_OPERAND (stmt, 1);
+ vuse_optype vuses = STMT_VUSE_OPS (stmt);
+
+ STRIP_USELESS_TYPE_CONVERSION (rhs);
+
+ if (TREE_CODE_CLASS (TREE_CODE (rhs)) == '1'
+ || TREE_CODE_CLASS (TREE_CODE (rhs)) == '2')
{
- tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
- vn_lookup_or_add (def);
- insert_into_set (TMP_GEN (block), def);
- value_insert_into_set (AVAIL_OUT (block), def);
+ /* For binary and unary expressions, create a duplicate
+ expression with the operands replaced with the value
+ handles of the original RHS. */
+ tree newt = create_value_expr_from (rhs, block, vuses);
+ add_to_sets (lhs, newt, vuses, TMP_GEN (block),
+ AVAIL_OUT (block));
+ value_insert_into_set (EXP_GEN (block), newt);
+ continue;
}
- for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
+ else if (TREE_CODE (rhs) == SSA_NAME
+ || is_gimple_min_invariant (rhs))
{
- tree use = USE_OP (STMT_USE_OPS (stmt), j);
- if (TREE_CODE (use) == SSA_NAME)
- {
- vn_lookup_or_add (use);
- insert_into_set (TMP_GEN (block), use);
- value_insert_into_set (AVAIL_OUT (block), use);
- }
+ /* Compute a value number for the RHS of the statement
+ and add its value to the AVAIL_OUT set for the block.
+ Add the LHS to TMP_GEN. */
+ add_to_sets (lhs, rhs, vuses, TMP_GEN (block),
+ AVAIL_OUT (block));
+
+ if (TREE_CODE (rhs) == SSA_NAME
+ && !is_undefined_value (rhs))
+ value_insert_into_set (EXP_GEN (block), rhs);
+ continue;
}
- continue;
}
- if (TREE_CODE (stmt) == MODIFY_EXPR)
+ /* For any other statement that we don't recognize, simply
+ make the names generated by the statement available in
+ AVAIL_OUT and TMP_GEN. */
+ for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
{
- op0 = TREE_OPERAND (stmt, 0);
- if (TREE_CODE (op0) != SSA_NAME)
- continue;
- if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
- continue;
- op1 = TREE_OPERAND (stmt, 1);
- STRIP_USELESS_TYPE_CONVERSION (op1);
- if (is_gimple_min_invariant (op1))
- {
- vn_add (op0, vn_lookup_or_add (op1));
- insert_into_set (TMP_GEN (block), op0);
- value_insert_into_set (AVAIL_OUT (block), op0);
- }
- else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '2')
- {
- tree bop1, bop2;
- tree val, val1, val2;
- tree newt;
- bop1 = TREE_OPERAND (op1, 0);
- bop2 = TREE_OPERAND (op1, 1);
- val1 = vn_lookup_or_add (bop1);
- val2 = vn_lookup_or_add (bop2);
-
- newt = pool_alloc (binary_node_pool);
- memcpy (newt, op1, tree_size (op1));
- TREE_OPERAND (newt, 0) = val1;
- TREE_OPERAND (newt, 1) = val2;
- val = vn_lookup_or_add (newt);
- vn_add (op0, val);
- if (!is_undefined_value (bop1))
- value_insert_into_set (EXP_GEN (block), bop1);
- if (!is_undefined_value (bop2))
- value_insert_into_set (EXP_GEN (block), bop2);
- value_insert_into_set (EXP_GEN (block), newt);
- insert_into_set (TMP_GEN (block), op0);
- value_insert_into_set (AVAIL_OUT (block), op0);
- }
- else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '1'
- && !is_gimple_cast (op1))
- {
- tree uop;
- tree val, val1;
- tree newt;
- uop = TREE_OPERAND (op1, 0);
- val1 = vn_lookup_or_add (uop);
- newt = pool_alloc (unary_node_pool);
- memcpy (newt, op1, tree_size (op1));
- TREE_OPERAND (newt, 0) = val1;
- val = vn_lookup_or_add (newt);
- vn_add (op0, val);
- if (!is_undefined_value (uop))
- value_insert_into_set (EXP_GEN (block), uop);
- value_insert_into_set (EXP_GEN (block), newt);
- insert_into_set (TMP_GEN (block), op0);
- value_insert_into_set (AVAIL_OUT (block), op0);
- }
- else if (TREE_CODE (op1) == SSA_NAME)
- {
- tree val = vn_lookup_or_add (op1);
- vn_add (op0, val);
- if (!is_undefined_value (op1))
- value_insert_into_set (EXP_GEN (block), op1);
- insert_into_set (TMP_GEN (block), op0);
- value_insert_into_set (AVAIL_OUT (block), op0);
- }
- else
- {
- size_t j;
- for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
- {
- tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
- vn_lookup_or_add (def);
- insert_into_set (TMP_GEN (block), def);
- value_insert_into_set (AVAIL_OUT (block), def);
- if (def != op0)
- abort ();
- }
- for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
- {
- tree use = USE_OP (STMT_USE_OPS (stmt), j);
- if (TREE_CODE (use) == SSA_NAME)
- {
- vn_lookup_or_add (use);
- insert_into_set (TMP_GEN (block), use);
- value_insert_into_set (AVAIL_OUT (block), use);
- }
- }
- }
+ tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
+ add_to_sets (def, def, NULL, TMP_GEN (block),
+ AVAIL_OUT (block));
}
- else
+
+ for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
{
- size_t j;
- for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
- {
- tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
- vn_lookup_or_add (def);
- insert_into_set (TMP_GEN (block), def);
- value_insert_into_set (AVAIL_OUT (block), def);
- }
- for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
- {
- tree use = USE_OP (STMT_USE_OPS (stmt), j);
- if (TREE_CODE (use) == SSA_NAME)
- {
- vn_lookup_or_add (use);
- insert_into_set (TMP_GEN (block), use);
- value_insert_into_set (AVAIL_OUT (block), use);
- }
- }
+ tree use = USE_OP (STMT_USE_OPS (stmt), j);
+ add_to_sets (use, use, NULL, TMP_GEN (block),
+ AVAIL_OUT (block));
}
}
}
+ /* Compute available sets for the dominator children of BLOCK. */
for (son = first_dom_son (CDI_DOMINATORS, block);
son;
son = next_dom_son (CDI_DOMINATORS, son))
{
tree stmt = bsi_stmt (i);
- if (NUM_VUSES (STMT_VUSE_OPS (stmt))
- || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt))
- || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt))
- || stmt_ann (stmt)->has_volatile_ops)
- continue;
-
- /* Lookup the RHS of the expression, see if we have an
- available computation for it. If so, replace the RHS with
+ /* Lookup the RHS of the expression, see if we have an
+ available computation for it. If so, replace the RHS with
the available computation. */
- if (TREE_CODE (stmt) == MODIFY_EXPR)
- {
- tree t = TREE_OPERAND (stmt, 0);
- tree expr = TREE_OPERAND (stmt, 1);
- tree sprime;
- /* There is no point in eliminating NOP_EXPR, it isn't
- supposed to generate any code. */
- if (TREE_CODE (expr) == NOP_EXPR
- || (TREE_CODE_CLASS (TREE_CODE (expr)) != '2'
- && TREE_CODE_CLASS (TREE_CODE (expr)) != '1'))
- continue;
-
- sprime = find_leader (AVAIL_OUT (b), vn_lookup (t));
- if (sprime
- && sprime != t
- && may_propagate_copy (sprime, TREE_OPERAND (stmt, 1)))
- {
+ if (TREE_CODE (stmt) == MODIFY_EXPR
+ && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
+ && TREE_CODE (TREE_OPERAND (stmt ,1)) != SSA_NAME
+ && !is_gimple_min_invariant (TREE_OPERAND (stmt, 1))
+ && !stmt_ann (stmt)->has_volatile_ops)
+ {
+ tree lhs = TREE_OPERAND (stmt, 0);
+ tree *rhs_p = &TREE_OPERAND (stmt, 1);
+ tree sprime;
+ vuse_optype vuses = STMT_VUSE_OPS (stmt);
+
+ sprime = find_leader (AVAIL_OUT (b), vn_lookup (lhs, vuses));
+ if (sprime
+ && sprime != lhs
+ && (TREE_CODE (*rhs_p) != SSA_NAME
+ || may_propagate_copy (*rhs_p, sprime)))
+ {
+ if (sprime == *rhs_p)
+ abort ();
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Replaced ");
- print_generic_expr (dump_file, expr, 0);
+ print_generic_expr (dump_file, *rhs_p, 0);
fprintf (dump_file, " with ");
print_generic_expr (dump_file, sprime, 0);
fprintf (dump_file, " in ");
print_generic_stmt (dump_file, stmt, 0);
}
pre_stats.eliminations++;
- propagate_tree_value (&TREE_OPERAND (stmt, 1), sprime);
- modify_stmt (stmt);
- }
- }
+ propagate_tree_value (rhs_p, sprime);
+ modify_stmt (stmt);
+ }
+ }
}
}
}
-/* Main entry point to the SSA-PRE pass.
-
- PHASE indicates which dump file from the DUMP_FILES array to use when
- dumping debugging information. */
+/* Initialize data structures used by PRE. */
static void
-execute_pre (void)
+init_pre (void)
{
size_t tsize;
basic_block bb;
+
+ vn_init ();
memset (&pre_stats, 0, sizeof (pre_stats));
FOR_ALL_BB (bb)
- {
- bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
- }
+ bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
+
phi_translate_table = htab_create (511, expr_pred_trans_hash,
- expr_pred_trans_eq,
- free);
+ expr_pred_trans_eq, free);
value_set_pool = create_alloc_pool ("Value sets",
sizeof (struct value_set), 30);
value_set_node_pool = create_alloc_pool ("Value set nodes",
- sizeof (struct value_set_node), 30);
+ sizeof (struct value_set_node), 30);
calculate_dominance_info (CDI_POST_DOMINATORS);
calculate_dominance_info (CDI_DOMINATORS);
- tsize = tree_size (build (PLUS_EXPR, void_type_node, NULL_TREE,
- NULL_TREE));
+ tsize = tree_size (build (PLUS_EXPR, void_type_node, NULL_TREE, NULL_TREE));
binary_node_pool = create_alloc_pool ("Binary tree nodes", tsize, 30);
tsize = tree_size (build1 (NEGATE_EXPR, void_type_node, NULL_TREE));
unary_node_pool = create_alloc_pool ("Unary tree nodes", tsize, 30);
TMP_GEN (bb) = set_new (false);
AVAIL_OUT (bb) = set_new (true);
}
+}
+
+
+/* Deallocate data structures used by PRE. */
+static void
+fini_pre (void)
+{
+ basic_block bb;
+
+ free_alloc_pool (value_set_pool);
+ free_alloc_pool (value_set_node_pool);
+ free_alloc_pool (binary_node_pool);
+ free_alloc_pool (unary_node_pool);
+ htab_delete (phi_translate_table);
+
+ FOR_ALL_BB (bb)
+ {
+ free (bb->aux);
+ bb->aux = NULL;
+ }
+ free_dominance_info (CDI_POST_DOMINATORS);
+ vn_delete ();
+}
+
+
+/* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
+ only wants to do full redundancy elimination. */
+
+static void
+execute_pre (bool do_fre)
+{
+ init_pre ();
+
+ /* Collect and value number expressions computed in each basic
+ block. */
compute_avail (ENTRY_BLOCK_PTR);
if (dump_file && (dump_flags & TDF_DETAILS))
{
+ basic_block bb;
+
FOR_ALL_BB (bb)
{
print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
fixed, don't run it when he have an incredibly large number of
bb's. If we aren't going to run insert, there is no point in
computing ANTIC, either, even though it's plenty fast. */
-
- if (n_basic_blocks < 4000)
+ if (!do_fre && n_basic_blocks < 4000)
{
compute_antic ();
-
insert ();
}
+
+ /* Remove all the redundant expressions. */
eliminate ();
if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations);
}
- free_alloc_pool (value_set_pool);
- free_alloc_pool (value_set_node_pool);
- free_alloc_pool (binary_node_pool);
- free_alloc_pool (unary_node_pool);
- htab_delete (phi_translate_table);
-
- FOR_ALL_BB (bb)
- {
- free (bb->aux);
- bb->aux = NULL;
- }
- free_dominance_info (CDI_POST_DOMINATORS);
+ fini_pre ();
+}
+
+
+/* Gate and execute functions for PRE. */
+
+static void
+do_pre (void)
+{
+ execute_pre (false);
}
static bool
{
"pre", /* name */
gate_pre, /* gate */
- execute_pre, /* execute */
+ do_pre, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
0, /* todo_flags_start */
TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
};
+
+
+/* Gate and execute functions for FRE. */
+
+static void
+do_fre (void)
+{
+ execute_pre (true);
+}
+
+static bool
+gate_fre (void)
+{
+ return flag_tree_fre != 0;
+}
+
+struct tree_opt_pass pass_fre =
+{
+ "fre", /* name */
+ gate_fre, /* gate */
+ do_fre, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_TREE_FRE, /* tv_id */
+ PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
+};
init_ssa_operands ();
init_ssanames ();
init_phinodes ();
- vn_init ();
global_var = NULL_TREE;
aliases_computed_p = false;
}
fini_ssanames ();
fini_phinodes ();
fini_ssa_operands ();
- vn_delete ();
global_var = NULL_TREE;
BITMAP_XFREE (call_clobbered_vars);
pairs, and the expression is the key. */
typedef struct val_expr_pair_d
{
- tree v, e;
+ /* Value handle. */
+ tree v;
+
+ /* Associated expression. */
+ tree e;
+
+ /* Virtual uses in E. */
+ vuse_optype vuses;
+
+ /* E's hash value. */
hashval_t hashcode;
} *val_expr_pair_t;
}
-/* Given an expression or statement P, compute a hash value number using the
- code of the expression and its real operands. */
+/* Given an expression EXPR, compute a hash value number using the
+ code of the expression, its real operands and virtual operands (if
+ any).
+
+ VAL can be used to iterate by passing previous value numbers (it is
+ used by iterative_hash_expr).
+
+ VUSES is the set of virtual use operands associated with EXPR. It
+ may be NULL if EXPR has no virtual operands. */
hashval_t
-vn_compute (tree expr, hashval_t val)
+vn_compute (tree expr, hashval_t val, vuse_optype vuses)
{
+ size_t i;
+
+#if defined ENABLE_CHECKING
+ /* EXPR must not be a statement. We are only interested in value
+ numbering expressions on the RHS of assignments. */
+ if (expr == NULL_TREE
+ || (expr->common.ann
+ && expr->common.ann->common.type == STMT_ANN))
+ abort ();
+#endif
+
val = iterative_hash_expr (expr, val);
+
+ /* If the expression has virtual uses, incorporate them into the
+ hash value computed for EXPR. */
+ for (i = 0; i < NUM_VUSES (vuses); i++)
+ val = iterative_hash_expr (VUSE_OP (vuses, i), val);
+
return val;
}
if (TREE_CODE (e1) == TREE_CODE (e2)
&& (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
- && operand_equal_p (e1, e2, 0))
+ && operand_equal_p (e1, e2, OEP_PURE_SAME))
return true;
return false;
}
-/* Insert E into VALUE_TABLE with value V, and add expression E to the
- value set for value V. */
+/* Insert EXPR into VALUE_TABLE with value VAL, and add expression
+ EXPR to the value set for value VAL. VUSES represent the virtual
+ use operands associated with EXPR (if any). They are used when
+ computing the hash value for EXPR. */
void
-vn_add (tree e, tree v)
+vn_add (tree expr, tree val, vuse_optype vuses)
{
void **slot;
- val_expr_pair_t new_pair = xmalloc (sizeof (struct val_expr_pair_d));
- new_pair->e = e;
- new_pair->v = v;
- new_pair->hashcode = vn_compute (e, 0);
+ val_expr_pair_t new_pair;
+
+ new_pair = xmalloc (sizeof (struct val_expr_pair_d));
+ new_pair->e = expr;
+ new_pair->v = val;
+ new_pair->vuses = vuses;
+ new_pair->hashcode = vn_compute (expr, 0, vuses);
slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
INSERT);
if (*slot)
free (*slot);
*slot = (void *) new_pair;
- set_value_handle (e, v);
- add_to_value (v, e);
+ set_value_handle (expr, val);
+ add_to_value (val, expr);
}
-/* Search in VALUE_TABLE for an existing instance of expression E, and
- return its value, or NULL if none has been set. */
+/* Search in VALUE_TABLE for an existing instance of expression EXPR,
+ and return its value, or NULL if none has been set. VUSES
+ represent the virtual use operands associated with EXPR (if any).
+ They are used when computing the hash value for EXPR. */
tree
-vn_lookup (tree e)
+vn_lookup (tree expr, vuse_optype vuses)
{
void **slot;
- struct val_expr_pair_d vep = {NULL, NULL, 0};
+ struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
- if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c')
- return e;
- vep.e = e;
- vep.hashcode = vn_compute (e, 0);
+ if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c')
+ return expr;
+ vep.e = expr;
+ vep.vuses = vuses;
+ vep.hashcode = vn_compute (expr, 0, vuses);
slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
if (!slot)
return NULL_TREE;
}
-/* Like vn_lookup, but creates a new value for expression E if E doesn't
- already have a value. Return the existing/created value for E. */
+/* Like vn_lookup, but creates a new value for expression EXPR, if
+ EXPR doesn't already have a value. Return the existing/created
+ value for EXPR. VUSES represent the virtual use operands
+ associated with EXPR (if any). They are used when computing the
+ hash value for EXPR. */
tree
-vn_lookup_or_add (tree e)
+vn_lookup_or_add (tree expr, vuse_optype vuses)
{
- tree x = vn_lookup (e);
- if (x == NULL_TREE)
+ tree v = vn_lookup (expr, vuses);
+ if (v == NULL_TREE)
{
- tree v = make_value_handle (TREE_TYPE (e));
+ v = make_value_handle (TREE_TYPE (expr));
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Created value ");
print_generic_expr (dump_file, v, dump_flags);
fprintf (dump_file, " for ");
- print_generic_expr (dump_file, e, dump_flags);
+ print_generic_expr (dump_file, expr, dump_flags);
fprintf (dump_file, "\n");
}
- vn_add (e, v);
- x = v;
+ vn_add (expr, v, vuses);
}
- set_value_handle (e, x);
+ set_value_handle (expr, v);
- return x;
+ return v;
}
#define SSA_NAME_VALUE(N) \
SSA_NAME_CHECK (N)->ssa_name.value_handle
-#ifndef GCC_BITMAP_H
-struct bitmap_head_def;
+#ifndef _TREE_FLOW_H
+struct ptr_info_def;
#endif
-/* Aliasing information for SSA_NAMEs representing pointer variables. */
-struct ptr_info_def GTY(())
-{
- /* Nonzero if points-to analysis couldn't determine where this pointer
- is pointing to. */
- unsigned int pt_anything : 1;
-
- /* Nonzero if this pointer is the result of a call to malloc. */
- unsigned int pt_malloc : 1;
-
- /* Nonzero if the value of this pointer escapes the current function. */
- unsigned int value_escapes_p : 1;
-
- /* Set of variables that this pointer may point to. */
- struct bitmap_head_def *pt_vars;
-
- /* If this pointer has been dereferenced, and points-to information is
- more precise than type-based aliasing, indirect references to this
- pointer will be represented by this memory tag, instead of the type
- tag computed by TBAA. */
- tree name_mem_tag;
-};
-
struct tree_ssa_name GTY(())
{
struct tree_common common;
OSDN Git Service
