The patch switches to a hybrid EVRP pass which utilizes both the Ranger
and the classic EVRP pass.
it introduces a new undocumented option:
-fevrp-mode= which can be one of the following options
evrp-only : This is classic EVRP mode, identical to whats in trunk now.
rvrp-only : This runs EVRP using *only* the ranger for ranges.
*evrp-first * : This is a hybrid mode, which uses EVRP to satisfy
simplifications first, and if that fails, then tries with the ranger
rvrp-first : Another hybrid mode, this time it tries to simplify
with the ranger first, then with EVRP.
rvrp-trace : same as rvrp-only, except a lot of tracing information
is also dumped to the listing file
rvrp-debug : This is similar to rvrp-trace, except it also include a
lot of debug information fo the on-entry caches.
trace :This runs in EVRP-first mode, but turns on tracing in
the ranger
The default option currently enabled is *evrp_first*
This gives us similar functionality to what trunk current has, except
its enhanced by trying to use the ranger to find additional cases.
We see numerous places where the ranger provides enhanced result, the
primary cases are
a) When switches are involved.. we provide very precise ranges to
each switch case, including default, and we see cases where we can
eliminate branches due to that
b) We track ranges on edges quite accurately, and are not limited to
single entry blocks. In particular we are seeing a number of places
where ranges are being propagated into PHIs that were not before:
ie, from PR 81192:
if (j_8(D) != 2147483647)
goto <bb 4>; [50.00%]
else
goto <bb 5>; [50.00%]
<bb 4> :
iftmp.2_11 = j_8(D) + 1;
<bb 5> :
# iftmp.2_12 = PHI <j_8(D)(3), iftmp.2_11(4)>
hybrid mode now recognizes a constant can be propagated into the 3->5
edge and
produces
# iftmp.2_12 = PHI <2147483647(3), iftmp.2_11(4)>
As a result, we're finding a lot of jump threading opportunities are
being exposed earlier.
The patch provides 3 EVRP passes, and uses the option to choose which of
the 3 are invoked. You can see from the patch how interchangeable we
have managed to make the range engines.
The goal here is to continue exercising both engines regularly, which
making it easy to detect when one engine is better. when a dump_file is
requested for the pass, any time there is a variance in results between
the 2 engines will be highlighted by lines such as
EVRP:hybrid: RVRP found singleton 3
EVRP:hybrid: EVRP found singleton -1B
EVRP:hybrid: Second query simplifed stmt
We'll be using these to work on identifying differences/issues as we
move towards replacing EVRP/VRP fully.
Andrew
* flag-types.h (enum evrp_mode): New enumerated type EVRP_MODE_*.
* common.opt (fevrp-mode): New undocumented flag.
* vr-values.c (simplify_using_ranges::fold_cond): Try range_of_stmt
first to see if it returns a value.
(simplify_using_ranges::simplify_switch_using_ranges): Return true if
any changes were made to the switch.
* gimple-ssa-evrp.c: Include gimple-range.h
(class rvrp_folder): EVRP folding using ranger exclusively.
(rvrp_folder::rvrp_folder): New.
(rvrp_folder::~rvrp_folder): New.
(rvrp_folder::value_of_expr): New. Use rangers value_of_expr.
(rvrp_folder::value_on_edge): New. Use rangers value_on_edge.
(rvrp_folder::value_of_Stmt): New. Use rangers value_of_stmt.
(rvrp_folder::fold_stmt): New. Call the simplifier.
(class hybrid_folder): EVRP folding using both engines.
(hybrid_folder::hybrid_folder): New.
(hybrid_folder::~hybrid_folder): New.
(hybrid_folder::fold_stmt): New. Simplify with one engne, then the
other.
(hybrid_folder::value_of_expr): New. Use both value routines.
(hybrid_folder::value_on_edge): New. Use both value routines.
(hybrid_folder::value_of_stmt): New. Use both value routines.
(hybrid_folder::choose_value): New. Choose between range_analzyer and
rangers values.
(execute_early_vrp): Choose a folder based on flag_evrp_mode.
diff --git a/gcc/flag-types.h b/gcc/flag-types.h
index 852ea76eaa2..0ca2a1cff46 100644
--- a/gcc/flag-types.h
+++ b/gcc/flag-types.h
@@ -382,4 +382,16 @@ enum parloops_schedule_type
PARLOOPS_SCHEDULE_RUNTIME
};
+/* EVRP mode. */
+enum evrp_mode
+{
+ EVRP_MODE_EVRP_ONLY,
+ EVRP_MODE_RVRP_ONLY,
+ EVRP_MODE_EVRP_FIRST,
+ EVRP_MODE_RVRP_FIRST,
+ EVRP_MODE_RVRP_TRACE,
+ EVRP_MODE_RVRP_DEBUG,
+ EVRP_MODE_TRACE
+};
+
#endif /* ! GCC_FLAG_TYPES_H */
diff --git a/gcc/common.opt b/gcc/common.opt
index 292c2de694e..71b9292a22e 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -2870,6 +2870,34 @@ ftree-vrp
Common Report Var(flag_tree_vrp) Init(0) Optimization
Perform Value Range Propagation on trees.
+fevrp-mode=
+Common Undocumented Joined RejectNegative Enum(evrp_mode) Var(flag_evrp_mode) Init(EVRP_MODE_EVRP_FIRST) Optimization
+-fevrp-mode=[evrp-only|rvrp-only|evrp-first|rvrp-first|rvrp-trace|rvrp-debug|trace] Specifies the mode Early VRP should operate in.
+
+Enum
+Name(evrp_mode) Type(enum evrp_mode) UnknownError(unknown evrp mode %qs)
+
+EnumValue
+Enum(evrp_mode) String(evrp-only) Value(EVRP_MODE_EVRP_ONLY)
+
+EnumValue
+Enum(evrp_mode) String(rvrp-only) Value(EVRP_MODE_RVRP_ONLY)
+
+EnumValue
+Enum(evrp_mode) String(evrp-first) Value(EVRP_MODE_EVRP_FIRST)
+
+EnumValue
+Enum(evrp_mode) String(rvrp-first) Value(EVRP_MODE_RVRP_FIRST)
+
+EnumValue
+Enum(evrp_mode) String(rvrp-trace) Value(EVRP_MODE_RVRP_TRACE)
+
+EnumValue
+Enum(evrp_mode) String(rvrp-debug) Value(EVRP_MODE_RVRP_DEBUG)
+
+EnumValue
+Enum(evrp_mode) String(hybrid-trace) Value(EVRP_MODE_TRACE)
+
fsplit-paths
Common Report Var(flag_split_paths) Init(0) Optimization
Split paths leading to loop backedges.
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index 4d7dfd0b4bf..88aa672466c 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -3606,6 +3606,35 @@ simplify_using_ranges::fold_cond (gcond *cond)
some point we should merge all variants of this code. */
edge taken_edge;
vrp_visit_cond_stmt (cond, &taken_edge);
+
+ int_range_max r;
+ if (query->range_of_stmt (r, cond) && r.singleton_p ())
+ {
+ // COND has already been folded if arguments are constant.
+ if (TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
+ && TREE_CODE (gimple_cond_rhs (cond)) != SSA_NAME)
+ return false;
+
+ if (r.zero_p ())
+ {
+ gcc_checking_assert (!taken_edge
+ || taken_edge->flags & EDGE_FALSE_VALUE);
+ if (dump_file && (dump_flags & TDF_DETAILS) && !taken_edge)
+ fprintf (dump_file, "\nPredicate evaluates to: 0\n");
+ gimple_cond_make_false (cond);
+ }
+ else
+ {
+ gcc_checking_assert (!taken_edge
+ || taken_edge->flags & EDGE_TRUE_VALUE);
+ if (dump_file && (dump_flags & TDF_DETAILS) && !taken_edge)
+ fprintf (dump_file, "\nPredicate evaluates to: 1\n");
+ gimple_cond_make_true (cond);
+ }
+ update_stmt (cond);
+ return true;
+ }
+
if (taken_edge)
{
if (taken_edge->flags & EDGE_TRUE_VALUE)
@@ -3947,7 +3976,7 @@ simplify_using_ranges::simplify_switch_using_ranges (gswitch *stmt)
su.stmt = stmt;
su.vec = vec2;
to_update_switch_stmts.safe_push (su);
- return false;
+ return true;
}
void
diff --git a/gcc/gimple-ssa-evrp.c b/gcc/gimple-ssa-evrp.c
index 60bf82a6805..29680b05855 100644
--- a/gcc/gimple-ssa-evrp.c
+++ b/gcc/gimple-ssa-evrp.c
@@ -41,6 +41,10 @@ along with GCC; see the file COPYING3. If not see
#include "tree-cfgcleanup.h"
#include "vr-values.h"
#include "gimple-ssa-evrp-analyze.h"
+#include "gimple-range.h"
+
+// This is the classic EVRP folder which uses a dominator walk and pushes
+// ranges into the next block if it is a single predecessor block.
class evrp_folder : public substitute_and_fold_engine
{
@@ -98,12 +102,196 @@ public:
m_range_analyzer.set_defs_to_varying (stmt);
}
-private:
+protected:
DISABLE_COPY_AND_ASSIGN (evrp_folder);
evrp_range_analyzer m_range_analyzer;
simplify_using_ranges simplifier;
};
+// This is a ranger based folder which continues to use the dominator
+// walk to access the substitute and fold machinery. Ranges are calculated
+// on demand.
+
+class rvrp_folder : public substitute_and_fold_engine
+{
+public:
+
+ rvrp_folder () : substitute_and_fold_engine (), m_simplifier ()
+ {
+ if (flag_evrp_mode == EVRP_MODE_RVRP_TRACE
+ || flag_evrp_mode == EVRP_MODE_RVRP_DEBUG)
+ m_ranger = new trace_ranger ();
+ else
+ m_ranger = new gimple_ranger ();
+ m_simplifier.set_range_query (m_ranger);
+ }
+
+ ~rvrp_folder ()
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ m_ranger->dump (dump_file);
+ delete m_ranger;
+ }
+
+ tree value_of_expr (tree name, gimple *s = NULL) OVERRIDE
+ {
+ return m_ranger->value_of_expr (name, s);
+ }
+
+ tree value_on_edge (edge e, tree name) OVERRIDE
+ {
+ return m_ranger->value_on_edge (e, name);
+ }
+
+ tree value_of_stmt (gimple *s, tree name = NULL) OVERRIDE
+ {
+ return m_ranger->value_of_stmt (s, name);
+ }
+
+ bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE
+ {
+ return m_simplifier.simplify (gsi);
+ }
+
+private:
+ DISABLE_COPY_AND_ASSIGN (rvrp_folder);
+ gimple_ranger *m_ranger;
+ simplify_using_ranges m_simplifier;
+};
+
+// In a hybrid folder, start with an EVRP folder, and add the required
+// fold_stmt bits to either try the ranger first or second.
+//
+// The 3 value_* routines will always query both EVRP and the ranger for
+// a result, and ensure they return the same value. If either returns a value
+// when the other doesn't, it is flagged in the listing, and the discoverd
+// value is returned.
+//
+// The simplifier is unable to process 2 different sources, thus we try to
+// use one engine, and if it fails to simplify, try using the other engine.
+// It is reported when the first attempt fails and the second succeeds.
+
+class hybrid_folder : public evrp_folder
+{
+public:
+ hybrid_folder (bool evrp_first)
+ {
+ if (flag_evrp_mode == EVRP_MODE_TRACE)
+ m_ranger = new trace_ranger ();
+ else
+ m_ranger = new gimple_ranger ();
+
+ if (evrp_first)
+ {
+ first = &m_range_analyzer;
+ second = m_ranger;
+ }
+ else
+ {
+ first = m_ranger;
+ second = &m_range_analyzer;
+ }
+ }
+
+ ~hybrid_folder ()
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ m_ranger->dump (dump_file);
+ delete m_ranger;
+ }
+
+ bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE
+ {
+ simplifier.set_range_query (first);
+ if (simplifier.simplify (gsi))
+ return true;
+
+ simplifier.set_range_query (second);
+ if (simplifier.simplify (gsi))
+ {
+ if (dump_file)
+ fprintf (dump_file, "EVRP:hybrid: Second query simplifed stmt\n");
+ return true;
+ }
+ return false;
+ }
+
+ tree value_of_expr (tree name, gimple *) OVERRIDE;
+ tree value_on_edge (edge, tree name) OVERRIDE;
+ tree value_of_stmt (gimple *, tree name) OVERRIDE;
+
+private:
+ DISABLE_COPY_AND_ASSIGN (hybrid_folder);
+ gimple_ranger *m_ranger;
+ range_query *first;
+ range_query *second;
+ tree choose_value (tree evrp_val, tree ranger_val);
+};
+
+
+tree
+hybrid_folder::value_of_expr (tree op, gimple *stmt)
+{
+ tree evrp_ret = evrp_folder::value_of_expr (op, stmt);
+ tree ranger_ret = m_ranger->value_of_expr (op, stmt);
+ return choose_value (evrp_ret, ranger_ret);
+}
+
+tree
+hybrid_folder::value_on_edge (edge e, tree op)
+{
+ tree evrp_ret = evrp_folder::value_on_edge (e, op);
+ tree ranger_ret = m_ranger->value_on_edge (e, op);
+ return choose_value (evrp_ret, ranger_ret);
+}
+
+tree
+hybrid_folder::value_of_stmt (gimple *stmt, tree op)
+{
+ tree evrp_ret = evrp_folder::value_of_stmt (stmt, op);
+ tree ranger_ret = m_ranger->value_of_stmt (stmt, op);
+ return choose_value (evrp_ret, ranger_ret);
+}
+
+// Given trees returned by EVRP and Ranger, choose/report the value to use
+// by the folder.
+
+tree
+hybrid_folder::choose_value (tree evrp_val, tree ranger_val)
+{
+ if (!ranger_val)
+ {
+ // If neither returned a value, return NULL_TREE.
+ if (!evrp_val)
+ return NULL_TREE;
+
+ // Otherwise EVRP found something.
+ if (dump_file)
+ {
+ fprintf (dump_file, "EVRP:hybrid: EVRP found singleton ");
+ print_generic_expr (dump_file, evrp_val);
+ fprintf (dump_file, "\n");
+ }
+ return evrp_val;
+ }
+
+ // Otherwise ranger found a value, if they match we're good.
+ if (evrp_val && !compare_values (evrp_val, ranger_val))
+ return evrp_val;
+
+ // We should never get different singletons.
+ gcc_checking_assert (!evrp_val);
+
+ // Now ranger has found a value, but EVRP did not.
+ if (dump_file)
+ {
+ fprintf (dump_file, "EVRP:hybrid: RVRP found singleton ");
+ print_generic_expr (dump_file, ranger_val);
+ fprintf (dump_file, "\n");
+ }
+ return ranger_val;
+}
+
/* Main entry point for the early vrp pass which is a simplified non-iterative
version of vrp where basic blocks are visited in dominance order. Value
ranges discovered in early vrp will also be used by ipa-vrp. */
@@ -120,8 +308,33 @@ execute_early_vrp ()
scev_initialize ();
calculate_dominance_info (CDI_DOMINATORS);
- evrp_folder folder;
- folder.substitute_and_fold ();
+ switch (flag_evrp_mode)
+ {
+ case EVRP_MODE_EVRP_ONLY:
+ {
+ evrp_folder folder;
+ folder.substitute_and_fold ();
+ break;
+ }
+ case EVRP_MODE_RVRP_ONLY:
+ case EVRP_MODE_RVRP_TRACE:
+ case EVRP_MODE_RVRP_DEBUG:
+ {
+ rvrp_folder folder;
+ folder.substitute_and_fold ();
+ break;
+ }
+ case EVRP_MODE_EVRP_FIRST:
+ case EVRP_MODE_RVRP_FIRST:
+ case EVRP_MODE_TRACE:
+ {
+ hybrid_folder folder (flag_evrp_mode != EVRP_MODE_RVRP_FIRST);
+ folder.substitute_and_fold ();
+ break;
+ }
+ default:
+ gcc_unreachable ();
+ }
scev_finalize ();
loop_optimizer_finalize ();
