On 3/28/25 05:25, Jakub Jelinek wrote:
On Fri, Mar 28, 2025 at 08:12:35AM +0100, Richard Biener wrote:
On Thu, Mar 27, 2025 at 8:14 PM Andrew MacLeod <amacl...@redhat.com> wrote:
This patch backports the ASSUME support that was rewritten in GCC 15.
Its slightly more complicated than the port to GCC 14 was in that a few
classes have been rewritten. I've isolated them all to tree-assume.cc
which contains the pass.
It has to also bring in the ssa_cache and lazy_ssa_cache from gcc14,
along with some tweaks to those classes to deal with changes in the way
range_allocators worked started in GCC14. Those changes are are all the
top of the tree-assume.cc file. The rest of the file is a carbon copy of
the GCC14 version. (well, what should be... there is an outstanding
debug output support that was never submitted I discovered)
I'm not sure if its worth putting this in GCC13 or not, but I will
submit it and leave it to the release managers :-) It should be low
risk, especially since assume was experimental support?
I have no strong opinion here besides questioning whether it's
necessary (as you say, assume is experimental) and the fact that
by splicing out the VRP changes to a special place further maintenance
is made more difficult.
IMO, up to you (expecting you'll fix issues if they come up), but would
like to hear a 2nd opinion from Jakub.
I'd probably apply it, it was a wrong-code issue and I'm not sure
users understand assume as experimental.
While the [[assume (...)]]; form is a C++23 feature which is experimental,
we accept that attribute even since C++11 and in C23 and in the
__attribute__((assume (...))); form everywhere and as a documented
extension.
If the ranger changes are done only when users actually use assume rather
than all the time (and only when using non-trivial assumptions, trivial
ones with no side-effects are turned into if (!x) __builtin_unreachable ()),
I think this decreases the risks.
Jakub
I've reattached the patch for gcc13.
Bootstrapped with no regressions on x86_64-pc-linux-gnu.
OK for gcc13 branch, or do we consider that "too old" now? :-)
Andrew
From 892a92002f94e2856fdee164b4d620edc69184b5 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacl...@redhat.com>
Date: Thu, 27 Mar 2025 10:51:16 -0400
Subject: [PATCH 1/3] backport new assume implementation and cache.
---
gcc/Makefile.in | 1 +
gcc/gimple-range-fold.cc | 13 -
gcc/gimple-range-fold.h | 12 +
gcc/gimple-range.cc | 189 ------
gcc/gimple-range.h | 19 -
gcc/testsuite/g++.dg/cpp23/pr117287-attr.C | 38 ++
gcc/tree-assume.cc | 650 +++++++++++++++++++++
gcc/tree-vrp.cc | 68 ---
8 files changed, 701 insertions(+), 289 deletions(-)
create mode 100644 gcc/testsuite/g++.dg/cpp23/pr117287-attr.C
create mode 100644 gcc/tree-assume.cc
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 775aaa1b3c4..1d9e10127ca 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1633,6 +1633,7 @@ OBJS = \
ubsan.o \
sanopt.o \
sancov.o \
+ tree-assume.o \
tree-call-cdce.o \
tree-cfg.o \
tree-cfgcleanup.o \
diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index 180f349eda9..e2bb294624f 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -103,21 +103,8 @@ fur_source::register_relation (edge e ATTRIBUTE_UNUSED,
{
}
-// This version of fur_source will pick a range up off an edge.
-
-class fur_edge : public fur_source
-{
-public:
- fur_edge (edge e, range_query *q = NULL);
- virtual bool get_operand (vrange &r, tree expr) override;
- virtual bool get_phi_operand (vrange &r, tree expr, edge e) override;
-private:
- edge m_edge;
-};
-
// Instantiate an edge based fur_source.
-inline
fur_edge::fur_edge (edge e, range_query *q) : fur_source (q)
{
m_edge = e;
diff --git a/gcc/gimple-range-fold.h b/gcc/gimple-range-fold.h
index 68c6d7743e9..0a028e31be0 100644
--- a/gcc/gimple-range-fold.h
+++ b/gcc/gimple-range-fold.h
@@ -149,6 +149,18 @@ protected:
relation_oracle *m_oracle;
};
+// This version of fur_source will pick a range up off an edge.
+
+class fur_edge : public fur_source
+{
+public:
+ fur_edge (edge e, range_query *q = NULL);
+ virtual bool get_operand (vrange &r, tree expr) override;
+ virtual bool get_phi_operand (vrange &r, tree expr, edge e) override;
+private:
+ edge m_edge;
+};
+
// This class uses ranges to fold a gimple statement producing a range for
// the LHS. The source of all operands is supplied via the fur_source class
// which provides a range_query as well as a source location and any other
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index b4de8dd4ef9..e1f283c774c 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -729,192 +729,3 @@ disable_ranger (struct function *fun)
fun->x_range_query = NULL;
}
-// ------------------------------------------------------------------------
-
-// If there is a non-varying value associated with NAME, return true and the
-// range in R.
-
-bool
-assume_query::assume_range_p (vrange &r, tree name)
-{
- if (global.get_global_range (r, name))
- return !r.varying_p ();
- return false;
-}
-
-// Query used by GORI to pick up any known value on entry to a block.
-
-bool
-assume_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
-{
- if (!gimple_range_ssa_p (expr))
- return get_tree_range (r, expr, stmt);
-
- if (!global.get_global_range (r, expr))
- r.set_varying (TREE_TYPE (expr));
- return true;
-}
-
-// If the current function returns an integral value, and has a single return
-// statement, it will calculate any SSA_NAMES it can determine ranges for
-// assuming the function returns 1.
-
-assume_query::assume_query ()
-{
- basic_block exit_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
- if (single_pred_p (exit_bb))
- {
- basic_block bb = single_pred (exit_bb);
- gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
- if (gsi_end_p (gsi))
- return;
- gimple *s = gsi_stmt (gsi);
- if (!is_a<greturn *> (s))
- return;
- greturn *gret = as_a<greturn *> (s);
- tree op = gimple_return_retval (gret);
- if (!gimple_range_ssa_p (op))
- return;
- tree lhs_type = TREE_TYPE (op);
- if (!irange::supports_p (lhs_type))
- return;
-
- unsigned prec = TYPE_PRECISION (lhs_type);
- int_range<2> lhs_range (lhs_type, wi::one (prec), wi::one (prec));
- global.set_global_range (op, lhs_range);
-
- gimple *def = SSA_NAME_DEF_STMT (op);
- if (!def || gimple_get_lhs (def) != op)
- return;
- fur_stmt src (gret, this);
- calculate_stmt (def, lhs_range, src);
- }
-}
-
-// Evaluate operand OP on statement S, using the provided LHS range.
-// If successful, set the range in the global table, then visit OP's def stmt.
-
-void
-assume_query::calculate_op (tree op, gimple *s, vrange &lhs, fur_source &src)
-{
- Value_Range op_range (TREE_TYPE (op));
- if (m_gori.compute_operand_range (op_range, s, lhs, op, src)
- && !op_range.varying_p ())
- {
- Value_Range range (TREE_TYPE (op));
- if (global.get_global_range (range, op))
- op_range.intersect (range);
- global.set_global_range (op, op_range);
- gimple *def_stmt = SSA_NAME_DEF_STMT (op);
- if (def_stmt && gimple_get_lhs (def_stmt) == op)
- calculate_stmt (def_stmt, op_range, src);
- }
-}
-
-// Evaluate PHI statement, using the provided LHS range.
-// Check each constant argument predecessor if it can be taken
-// provide LHS to any symbolic arguments, and process their def statements.
-
-void
-assume_query::calculate_phi (gphi *phi, vrange &lhs_range, fur_source &src)
-{
- for (unsigned x= 0; x < gimple_phi_num_args (phi); x++)
- {
- tree arg = gimple_phi_arg_def (phi, x);
- Value_Range arg_range (TREE_TYPE (arg));
- if (gimple_range_ssa_p (arg))
- {
- // A symbol arg will be the LHS value.
- arg_range = lhs_range;
- range_cast (arg_range, TREE_TYPE (arg));
- if (!global.get_global_range (arg_range, arg))
- {
- global.set_global_range (arg, arg_range);
- gimple *def_stmt = SSA_NAME_DEF_STMT (arg);
- if (def_stmt && gimple_get_lhs (def_stmt) == arg)
- calculate_stmt (def_stmt, arg_range, src);
- }
- }
- else if (get_tree_range (arg_range, arg, NULL))
- {
- // If this is a constant value that differs from LHS, this
- // edge cannot be taken.
- arg_range.intersect (lhs_range);
- if (arg_range.undefined_p ())
- continue;
- // Otherwise check the condition feeding this edge.
- edge e = gimple_phi_arg_edge (phi, x);
- check_taken_edge (e, src);
- }
- }
-}
-
-// If an edge is known to be taken, examine the outgoing edge to see
-// if it carries any range information that can also be evaluated.
-
-void
-assume_query::check_taken_edge (edge e, fur_source &src)
-{
- gimple *stmt = gimple_outgoing_range_stmt_p (e->src);
- if (stmt && is_a<gcond *> (stmt))
- {
- int_range<2> cond;
- gcond_edge_range (cond, e);
- calculate_stmt (stmt, cond, src);
- }
-}
-
-// Evaluate statement S which produces range LHS_RANGE.
-
-void
-assume_query::calculate_stmt (gimple *s, vrange &lhs_range, fur_source &src)
-{
- gimple_range_op_handler handler (s);
- if (handler)
- {
- tree op = gimple_range_ssa_p (handler.operand1 ());
- if (op)
- calculate_op (op, s, lhs_range, src);
- op = gimple_range_ssa_p (handler.operand2 ());
- if (op)
- calculate_op (op, s, lhs_range, src);
- }
- else if (is_a<gphi *> (s))
- {
- calculate_phi (as_a<gphi *> (s), lhs_range, src);
- // Don't further check predecessors of blocks with PHIs.
- return;
- }
-
- // Even if the walk back terminates before the top, if this is a single
- // predecessor block, see if the predecessor provided any ranges to get here.
- if (single_pred_p (gimple_bb (s)))
- check_taken_edge (single_pred_edge (gimple_bb (s)), src);
-}
-
-// Show everything that was calculated.
-
-void
-assume_query::dump (FILE *f)
-{
- fprintf (f, "Assumption details calculated:\n");
- for (unsigned i = 0; i < num_ssa_names; i++)
- {
- tree name = ssa_name (i);
- if (!name || !gimple_range_ssa_p (name))
- continue;
- tree type = TREE_TYPE (name);
- if (!Value_Range::supports_type_p (type))
- continue;
-
- Value_Range assume_range (type);
- if (assume_range_p (assume_range, name))
- {
- print_generic_expr (f, name, TDF_SLIM);
- fprintf (f, " -> ");
- assume_range.dump (f);
- fputc ('\n', f);
- }
- }
- fprintf (f, "------------------------------\n");
-}
diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h
index 7ed4d3870b8..690fc0fa703 100644
--- a/gcc/gimple-range.h
+++ b/gcc/gimple-range.h
@@ -81,23 +81,4 @@ protected:
extern gimple_ranger *enable_ranger (struct function *m,
bool use_imm_uses = true);
extern void disable_ranger (struct function *);
-
-class assume_query : public range_query
-{
-public:
- assume_query ();
- bool assume_range_p (vrange &r, tree name);
- virtual bool range_of_expr (vrange &r, tree expr, gimple * = NULL);
- void dump (FILE *f);
-protected:
- void calculate_stmt (gimple *s, vrange &lhs_range, fur_source &src);
- void calculate_op (tree op, gimple *s, vrange &lhs, fur_source &src);
- void calculate_phi (gphi *phi, vrange &lhs_range, fur_source &src);
- void check_taken_edge (edge e, fur_source &src);
-
- ssa_global_cache global;
- gori_compute m_gori;
-};
-
-
#endif // GCC_GIMPLE_RANGE_H
diff --git a/gcc/testsuite/g++.dg/cpp23/pr117287-attr.C b/gcc/testsuite/g++.dg/cpp23/pr117287-attr.C
new file mode 100644
index 00000000000..759c21dc283
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp23/pr117287-attr.C
@@ -0,0 +1,38 @@
+// P1774R8 - Portable assumptions
+// { dg-do run { target c++23 } }
+// { dg-options "-O2 --param=logical-op-non-short-circuit=0" }
+// Test the we can optimize based on conditions in assume.
+
+static inline bool
+foo (unsigned x)
+{
+ return x == 4 || x == 5 || x == 9 || x == 10;
+}
+
+int v;
+
+[[gnu::noipa]] void
+bar (const char *p)
+{
+ if (p[0] != (v ? 'a' : 'b') || p[1])
+ __builtin_abort ();
+}
+
+[[gnu::noipa]] void
+baz (unsigned x)
+{
+ bool a = x == 5;
+ [[assume (foo (x))]];
+ bar (a ? "a" : "b");
+}
+
+int
+main ()
+{
+ baz (4);
+ v = 1;
+ baz (5);
+ v = 0;
+ baz (9);
+ baz (10);
+}
diff --git a/gcc/tree-assume.cc b/gcc/tree-assume.cc
new file mode 100644
index 00000000000..77d260aa833
--- /dev/null
+++ b/gcc/tree-assume.cc
@@ -0,0 +1,650 @@
+/* Support for C++23 ASSUME keyword functionailty.
+ Copyright (C) 2023-2024 Free Software Foundation, Inc.
+ Contributed by Andrew MacLeod <amacl...@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 3, 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 COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "basic-block.h"
+#include "bitmap.h"
+#include "options.h"
+#include "function.h"
+#include "cfg.h"
+#include "tree.h"
+#include "gimple.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "gimple-iterator.h"
+#include "gimple-range.h"
+#include "tree-dfa.h"
+#include "gimple-pretty-print.h"
+#include "tree-cfg.h"
+#include "value-range-storage.h"
+
+// This global cache is used with the range engine as markers for what
+// has been visited during this incarnation. Once the ranger evaluates
+// a name, it is typically not re-evaluated again.
+
+class ssa_cache : public range_query
+{
+public:
+ ssa_cache ();
+ ~ssa_cache ();
+ virtual bool has_range (tree name) const;
+ virtual bool get_range (vrange &r, tree name) const;
+ virtual bool set_range (tree name, const vrange &r);
+ virtual bool merge_range (tree name, const vrange &r);
+ virtual void clear_range (tree name);
+ virtual void clear ();
+ void dump (FILE *f = stderr);
+ virtual bool range_of_expr (vrange &r, tree expr, gimple *stmt = NULL);
+protected:
+ vec<vrange *> m_tab;
+ vrange_allocator *m_range_allocator;
+};
+
+// This is the same as global cache, except it maintains an active bitmap
+// rather than depending on a zero'd out vector of pointers. This is better
+// for sparsely/lightly used caches.
+
+class ssa_lazy_cache : public ssa_cache
+{
+public:
+ inline ssa_lazy_cache () { active_p = BITMAP_ALLOC (NULL); }
+ inline ~ssa_lazy_cache () { BITMAP_FREE (active_p); }
+ inline bool empty_p () const { return bitmap_empty_p (active_p); }
+ virtual bool has_range (tree name) const;
+ virtual bool set_range (tree name, const vrange &r);
+ virtual bool merge_range (tree name, const vrange &r);
+ virtual bool get_range (vrange &r, tree name) const;
+ virtual void clear_range (tree name);
+ virtual void clear ();
+protected:
+ bitmap active_p;
+};
+
+
+// --------------------------------------------------------------------------
+
+// Initialize an ssa cache.
+
+ssa_cache::ssa_cache ()
+{
+ m_tab.create (0);
+ m_range_allocator = new obstack_vrange_allocator;
+}
+
+// Deconstruct an ssa cache.
+
+ssa_cache::~ssa_cache ()
+{
+ m_tab.release ();
+ delete m_range_allocator;
+}
+
+// Enable a query to evaluate staements/ramnges based on picking up ranges
+// from just an ssa-cache.
+
+bool
+ssa_cache::range_of_expr (vrange &r, tree expr, gimple *stmt)
+{
+ if (!gimple_range_ssa_p (expr))
+ return get_tree_range (r, expr, stmt);
+
+ if (!get_range (r, expr))
+ gimple_range_global (r, expr, cfun);
+ return true;
+}
+
+// Return TRUE if the global range of NAME has a cache entry.
+
+bool
+ssa_cache::has_range (tree name) const
+{
+ unsigned v = SSA_NAME_VERSION (name);
+ if (v >= m_tab.length ())
+ return false;
+ return m_tab[v] != NULL;
+}
+
+// Retrieve the global range of NAME from cache memory if it exists.
+// Return the value in R.
+
+bool
+ssa_cache::get_range (vrange &r, tree name) const
+{
+ unsigned v = SSA_NAME_VERSION (name);
+ if (v >= m_tab.length ())
+ return false;
+
+ vrange *stow = m_tab[v];
+ if (!stow)
+ return false;
+ r = *stow;
+ return true;
+}
+
+// Set the range for NAME to R in the ssa cache.
+// Return TRUE if there was already a range set, otherwise false.
+
+bool
+ssa_cache::set_range (tree name, const vrange &r)
+{
+ unsigned v = SSA_NAME_VERSION (name);
+ if (v >= m_tab.length ())
+ m_tab.safe_grow_cleared (num_ssa_names + 1);
+
+ vrange *m = m_tab[v];
+ if (m && m->fits_p (r))
+ *m = r;
+ else
+ m_tab[v] = m_range_allocator->clone (r);
+ return m != NULL;
+}
+
+// If NAME has a range, intersect it with R, otherwise set it to R.
+// Return TRUE if the range is new or changes.
+
+bool
+ssa_cache::merge_range (tree name, const vrange &r)
+{
+ unsigned v = SSA_NAME_VERSION (name);
+ if (v >= m_tab.length ())
+ m_tab.safe_grow_cleared (num_ssa_names + 1);
+
+ vrange *m = m_tab[v];
+ // Check if this is a new value.
+ if (!m)
+ m_tab[v] = m_range_allocator->clone (r);
+ else
+ {
+ Value_Range curr (TREE_TYPE (name));
+ curr = *m;
+ // If there is no change, return false.
+ if (!curr.intersect (r))
+ return false;
+
+ if (m->fits_p (curr))
+ *m = curr;
+ else
+ m_tab[v] = m_range_allocator->clone ((const vrange &)curr);
+ }
+ return true;
+}
+
+// Set the range for NAME to R in the ssa cache.
+
+void
+ssa_cache::clear_range (tree name)
+{
+ unsigned v = SSA_NAME_VERSION (name);
+ if (v >= m_tab.length ())
+ return;
+ m_tab[v] = NULL;
+}
+
+// Clear the ssa cache.
+
+void
+ssa_cache::clear ()
+{
+ if (m_tab.address ())
+ memset (m_tab.address(), 0, m_tab.length () * sizeof (vrange *));
+}
+
+// Dump the contents of the ssa cache to F.
+
+void
+ssa_cache::dump (FILE *f)
+{
+ for (unsigned x = 1; x < num_ssa_names; x++)
+ {
+ if (!gimple_range_ssa_p (ssa_name (x)))
+ continue;
+ Value_Range r (TREE_TYPE (ssa_name (x)));
+ // Dump all non-varying ranges.
+ if (get_range (r, ssa_name (x)) && !r.varying_p ())
+ {
+ print_generic_expr (f, ssa_name (x), TDF_NONE);
+ fprintf (f, " : ");
+ r.dump (f);
+ fprintf (f, "\n");
+ }
+ }
+
+}
+
+// Return true if NAME has an active range in the cache.
+
+bool
+ssa_lazy_cache::has_range (tree name) const
+{
+ return bitmap_bit_p (active_p, SSA_NAME_VERSION (name));
+}
+
+// Set range of NAME to R in a lazy cache. Return FALSE if it did not already
+// have a range.
+
+bool
+ssa_lazy_cache::set_range (tree name, const vrange &r)
+{
+ unsigned v = SSA_NAME_VERSION (name);
+ if (!bitmap_set_bit (active_p, v))
+ {
+ // There is already an entry, simply set it.
+ gcc_checking_assert (v < m_tab.length ());
+ return ssa_cache::set_range (name, r);
+ }
+ if (v >= m_tab.length ())
+ m_tab.safe_grow (num_ssa_names + 1);
+ m_tab[v] = m_range_allocator->clone (r);
+ return false;
+}
+
+// If NAME has a range, intersect it with R, otherwise set it to R.
+// Return TRUE if the range is new or changes.
+
+bool
+ssa_lazy_cache::merge_range (tree name, const vrange &r)
+{
+ unsigned v = SSA_NAME_VERSION (name);
+ if (!bitmap_set_bit (active_p, v))
+ {
+ // There is already an entry, simply merge it.
+ gcc_checking_assert (v < m_tab.length ());
+ return ssa_cache::merge_range (name, r);
+ }
+ if (v >= m_tab.length ())
+ m_tab.safe_grow (num_ssa_names + 1);
+ m_tab[v] = m_range_allocator->clone (r);
+ return true;
+}
+
+// Return TRUE if NAME has a range, and return it in R.
+
+bool
+ssa_lazy_cache::get_range (vrange &r, tree name) const
+{
+ if (!bitmap_bit_p (active_p, SSA_NAME_VERSION (name)))
+ return false;
+ return ssa_cache::get_range (r, name);
+}
+
+// Remove NAME from the active range list.
+
+void
+ssa_lazy_cache::clear_range (tree name)
+{
+ bitmap_clear_bit (active_p, SSA_NAME_VERSION (name));
+}
+
+// Remove all ranges from the active range list.
+
+void
+ssa_lazy_cache::clear ()
+{
+ bitmap_clear (active_p);
+}
+
+// An assume query utilizes the current range query to implement the assume
+// keyword.
+// For any return value of 1 from the function, it attempts to determine
+// which paths lead to a 1 value being returned. On those paths, it determines
+// the ranges of any ssa_names listed in bitmap P (usually the parm list for
+// the function), and combines them all.
+// These ranges are then set as the global ranges for those parms in this
+// function.
+// Other functions which refer to this function in an assume builtin
+// will then pick up these ranges for the parameters via the inferred range
+// mechanism.
+// See gimple-range-infer.cc::gimple_infer_range::check_assume_func ()
+//
+// my_func (int x)
+// {
+// <...>
+// assume [[(x == 1 || x ==4))]]
+// if (x ==3)
+//
+// a small temporary assume function consisting of
+// assume_f1 (int x) { return x == 1 || x == 4; }
+// is constructed by the front end, and optimized, at the very end of
+// optimization, instead of generating code, we instead invoke the assume pass
+// which uses this query to set the the global value of parm x to [1,1][4,4]
+//
+// Meanwhile., my_func has been rewritten to be:
+//
+// my_func (int x_2)
+// {
+// <...>
+// assume_builtin_call assume_f1 (x_2);
+// if (x_2 == 3)
+//
+// When ranger is processing the assume_builtin_call, it looks up the global
+// value of the parameter in assume_f1, which is [1,1][4,4]. It then registers
+// and inferred range at this statement setting the value x_2 to [1,1][4,4]
+//
+// Any uses of x_2 after this statement will now utilize this inferred range.
+//
+// When VRP processes if (x_2 == 3), it picks up the inferred range, and
+// determines that x_2 can never be 3, and will rewrite the branch to
+// if (0 != 0)
+
+class assume_query
+{
+public:
+ assume_query (gimple_ranger *ranger, function *f, bitmap p);
+protected:
+ inline void process_stmts (gimple *s, vrange &lhs_range)
+ {
+ fur_depend src (s, &(m_ranger->gori ()), m_ranger);
+ calculate_stmt (s, lhs_range, src);
+ update_parms (src);
+ }
+ void update_parms (fur_source &src);
+ void calculate_stmt (gimple *s, vrange &lhs_range, fur_source &src);
+ void calculate_op (tree op, gimple *s, vrange &lhs, fur_source &src);
+ void calculate_phi (gphi *phi, vrange &lhs_range);
+
+ ssa_lazy_cache m_path; // Values found on path
+ ssa_lazy_cache m_parms; // Cumulative parameter value calculated
+ gimple_ranger *m_ranger;
+ bitmap m_parm_list; // Parameter ssa-names list.
+ function *m_func;
+};
+
+// If function F returns a integral value, and has a single return
+// statement, try to calculate the range of each value in P that leads
+// to the return statement returning TRUE.
+
+assume_query::assume_query (gimple_ranger *ranger, function *f, bitmap p)
+ : m_ranger (ranger), m_parm_list (p), m_func (f)
+{
+ basic_block exit_bb = EXIT_BLOCK_PTR_FOR_FN (f);
+ // If there is more than one predecessor to the exit block, bail.
+ if (!single_pred_p (exit_bb))
+ return;
+
+ basic_block bb = single_pred (exit_bb);
+ gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
+ if (gsi_end_p (gsi))
+ return;
+ gimple *s = gsi_stmt (gsi);
+ if (!is_a<greturn *> (s))
+ return;
+
+ // Check if the single return value is a symbolic and supported type.
+ greturn *gret = as_a<greturn *> (s);
+ tree op = gimple_return_retval (gret);
+ if (!gimple_range_ssa_p (op))
+ return;
+ tree lhs_type = TREE_TYPE (op);
+ if (!irange::supports_p (lhs_type))
+ return;
+
+ // Only values of interest are when the return value is 1. The definition
+ // of the return value must be in the same block, or we have
+ // complicated flow control we don't understand, and just return.
+ unsigned prec = TYPE_PRECISION (lhs_type);
+ int_range<2> lhs_range (lhs_type, wi::one (prec), wi::one (prec));
+
+ gimple *def = SSA_NAME_DEF_STMT (op);
+ if (!def || gimple_get_lhs (def) != op || gimple_bb (def) != bb)
+ return;
+
+ // Determine if this is a PHI or a linear sequence to deal with.
+ if (is_a<gphi *> (def))
+ calculate_phi (as_a<gphi *> (def), lhs_range);
+ else
+ process_stmts (def, lhs_range);
+
+ if (dump_file)
+ fprintf (dump_file, "Assumptions :\n--------------\n");
+
+ // Now export any interesting values that were found.
+ bitmap_iterator bi;
+ unsigned x;
+ EXECUTE_IF_SET_IN_BITMAP (m_parm_list, 0, x, bi)
+ {
+ tree name = ssa_name (x);
+ tree type = TREE_TYPE (name);
+ Value_Range assume_range (type);
+ // Set the global range of NAME to anything calculated.
+ if (m_parms.get_range (assume_range, name) && !assume_range.varying_p ())
+ {
+ set_range_info (name, assume_range);
+ if (dump_file)
+ {
+ print_generic_expr (dump_file, name, TDF_SLIM);
+ fprintf (dump_file, " -> ");
+ assume_range.dump (dump_file);
+ fputc ('\n', dump_file);
+ }
+ }
+ }
+}
+
+// This function will update all the current values of interesting parameters.
+// It tries, in order:
+// a) a range found via path calculations.
+// b) range of the parm at SRC point in the IL. (either edge or stmt)
+// c) VARYING if those options fail.
+// The value is then unioned with any existing value, allowing for the
+// cumulation of all ranges leading to the return that return 1.
+
+void
+assume_query::update_parms (fur_source &src)
+{
+ // Merge any parameter values.
+ bitmap_iterator bi;
+ unsigned x;
+ EXECUTE_IF_SET_IN_BITMAP (m_parm_list, 0, x, bi)
+ {
+ tree name = ssa_name (x);
+ tree type = TREE_TYPE (name);
+
+ // Find a valu efrom calculations.
+ Value_Range glob_range (type);
+ if (!m_path.get_range (glob_range, name)
+ && !src.get_operand (glob_range, name))
+ glob_range.set_varying (type);
+
+ // Find any current value of parm, and combine them.
+ Value_Range parm_range (type);
+ if (m_parms.get_range (parm_range, name))
+ glob_range.union_ (parm_range);
+
+ // Set this new value.
+ m_parms.set_range (name, glob_range);
+ }
+ // Now reset the path values for the next path.
+ m_path.clear ();
+}
+
+
+// Evaluate PHI statement, using the provided LHS range.
+// Only process edge that are both taken and returns the LHS of the PHI.
+
+void
+assume_query::calculate_phi (gphi *phi, vrange &lhs_range)
+{
+ for (unsigned x= 0; x < gimple_phi_num_args (phi); x++)
+ {
+ tree arg = gimple_phi_arg_def (phi, x);
+ Value_Range arg_range (TREE_TYPE (arg));
+ edge e = gimple_phi_arg_edge (phi, x);
+ Value_Range edge_range (TREE_TYPE (arg));
+ // If we can't get an edge range, be conservative and assume the
+ // edge can be taken.
+ // NOte this can be either an ssa_name or a constant.
+ if (m_ranger->range_on_edge (edge_range, e, arg))
+ {
+ if (gimple_range_ssa_p (arg))
+ {
+ arg_range = lhs_range;
+ range_cast (arg_range, TREE_TYPE (arg));
+
+ // An SSA_NAME arg will start with the LHS value.
+ // Check the range of ARG on the edge leading here. If that range
+ // cannot be any value from the LHS of the PHI, then this branch
+ // will not be taken to return the LHS value and can be ignored.
+ arg_range.intersect (edge_range);
+ if (arg_range.undefined_p ())
+ continue;
+
+ // If the def is in the immediate preceeding block, process it
+ // with GORI to determine what values can produce this
+ // argument value. Otherwise there is more flow, so just query
+ // the edge for parm ranges and be conservative.
+ gimple *def_stmt = SSA_NAME_DEF_STMT (arg);
+ if (def_stmt && gimple_get_lhs (def_stmt) == arg
+ && gimple_bb (def_stmt) == e->src)
+ {
+ process_stmts (def_stmt, arg_range);
+ continue;
+ }
+ // Fall through to process the edge.
+ }
+ else
+ {
+ // If this is a constant value that differs from LHS, this
+ // edge cannot be taken and we can ignore it. Otherwise fall
+ // thorugh and process the edge.
+ edge_range.intersect (lhs_range);
+ if (edge_range.undefined_p ())
+ continue;
+ }
+ }
+ // If this point is reached the edge needs processing.
+ fur_edge src (e, m_ranger);
+ update_parms (src);
+ }
+}
+
+// Evaluate operand OP on statement S, using the provided LHS range.
+// If successful, set the range in path table, then visit OP's def stmt
+// if it is in the same BB.
+
+void
+assume_query::calculate_op (tree op, gimple *s, vrange &lhs, fur_source &src)
+{
+ basic_block bb = gimple_bb (s);
+ Value_Range op_range (TREE_TYPE (op));
+ if (src.gori () &&
+ src.gori ()->compute_operand_range (op_range, s, lhs, op, src)
+ && !op_range.varying_p ())
+ {
+ // Set the global range, merging if there is already a range.
+ m_path.merge_range (op, op_range);
+ gimple *def_stmt = SSA_NAME_DEF_STMT (op);
+ // Terminate if the patway leads to a different block as we
+ // are not analyzing flow.
+ if (def_stmt && gimple_get_lhs (def_stmt) == op
+ && gimple_bb (def_stmt) == bb)
+ calculate_stmt (def_stmt, op_range, src);
+ }
+}
+
+
+// Evaluate statement S which produces range LHS_RANGE. Use GORI to
+// determine what values the operands can have to produce the LHS,
+// and set these in the M_PATH table.
+
+void
+assume_query::calculate_stmt (gimple *s, vrange &lhs_range, fur_source &src)
+{
+ gimple_range_op_handler handler (s);
+ if (handler)
+ {
+ tree op = gimple_range_ssa_p (handler.operand1 ());
+ if (op)
+ calculate_op (op, s, lhs_range, src);
+ op = gimple_range_ssa_p (handler.operand2 ());
+ if (op)
+ calculate_op (op, s, lhs_range, src);
+ }
+}
+
+namespace {
+
+const pass_data pass_data_assumptions =
+{
+ GIMPLE_PASS, /* type */
+ "assumptions", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_ASSUMPTIONS, /* tv_id */
+ PROP_ssa, /* properties_required */
+ PROP_assumptions_done, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_end */
+};
+
+
+class pass_assumptions : public gimple_opt_pass
+{
+public:
+ pass_assumptions (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_assumptions, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ bool gate (function *fun) final override { return fun->assume_function; }
+ unsigned int execute (function *fun) final override
+ {
+ // Create a bitmap of all the parameters in this function.
+ // Invoke the assume_query to determine what values these parameters
+ // have when the function returns TRUE, and set the global values of
+ // those parameters in this function based on that. This will later be
+ // utilized by ranger when prcessing the builtin_assumer function.
+ auto_bitmap decls;
+ for (tree arg = DECL_ARGUMENTS (fun->decl); arg; arg = DECL_CHAIN (arg))
+ {
+ tree name = ssa_default_def (fun, arg);
+ if (!name || !gimple_range_ssa_p (name))
+ continue;
+ tree type = TREE_TYPE (name);
+ if (!Value_Range::supports_type_p (type))
+ continue;
+ bitmap_set_bit (decls, SSA_NAME_VERSION (name));
+ }
+ // If there are no parameters to map, simply return;
+ if (bitmap_empty_p (decls))
+ return TODO_discard_function;
+
+ gimple_ranger *ranger = enable_ranger (fun);
+
+ // This assume query will set any global values required.
+ assume_query query (ranger, fun, decls);
+
+ disable_ranger (fun);
+ if (dump_file)
+ gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
+
+ return TODO_discard_function;
+ }
+
+}; // class pass_assumptions
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_assumptions (gcc::context *ctx)
+{
+ return new pass_assumptions (ctx);
+}
diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc
index f4d484526c7..ff2403d00e5 100644
--- a/gcc/tree-vrp.cc
+++ b/gcc/tree-vrp.cc
@@ -1196,68 +1196,6 @@ public:
int my_pass;
}; // class pass_vrp
-const pass_data pass_data_assumptions =
-{
- GIMPLE_PASS, /* type */
- "assumptions", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- TV_TREE_ASSUMPTIONS, /* tv_id */
- PROP_ssa, /* properties_required */
- PROP_assumptions_done, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- 0, /* todo_flags_end */
-};
-
-class pass_assumptions : public gimple_opt_pass
-{
-public:
- pass_assumptions (gcc::context *ctxt)
- : gimple_opt_pass (pass_data_assumptions, ctxt)
- {}
-
- /* opt_pass methods: */
- bool gate (function *fun) final override { return fun->assume_function; }
- unsigned int execute (function *) final override
- {
- assume_query query;
- if (dump_file)
- fprintf (dump_file, "Assumptions :\n--------------\n");
-
- for (tree arg = DECL_ARGUMENTS (cfun->decl); arg; arg = DECL_CHAIN (arg))
- {
- tree name = ssa_default_def (cfun, arg);
- if (!name || !gimple_range_ssa_p (name))
- continue;
- tree type = TREE_TYPE (name);
- if (!Value_Range::supports_type_p (type))
- continue;
- Value_Range assume_range (type);
- if (query.assume_range_p (assume_range, name))
- {
- // Set the global range of NAME to anything calculated.
- set_range_info (name, assume_range);
- if (dump_file)
- {
- print_generic_expr (dump_file, name, TDF_SLIM);
- fprintf (dump_file, " -> ");
- assume_range.dump (dump_file);
- fputc ('\n', dump_file);
- }
- }
- }
- if (dump_file)
- {
- fputc ('\n', dump_file);
- gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
- if (dump_flags & TDF_DETAILS)
- query.dump (dump_file);
- }
- return TODO_discard_function;
- }
-
-}; // class pass_assumptions
-
} // anon namespace
gimple_opt_pass *
@@ -1271,9 +1209,3 @@ make_pass_early_vrp (gcc::context *ctxt)
{
return new pass_vrp (ctxt, pass_data_early_vrp);
}
-
-gimple_opt_pass *
-make_pass_assumptions (gcc::context *ctx)
-{
- return new pass_assumptions (ctx);
-}
--
2.45.0
