On 10/19/22 13:41, Jakub Jelinek wrote:
On Wed, Oct 19, 2022 at 07:39:05PM +0200, Jakub Jelinek via Gcc-patches wrote:
On Wed, Oct 19, 2022 at 12:55:12PM -0400, Andrew MacLeod via Gcc-patches wrote:
Not sure I understand this part. op is whatever we pass as the ith
argument to IFN_ASSUME. I'd expect that at this point one needs to
remap that to the (i-1)th PARM_DECL of assume_id (so e.g. when you
have the above loop you could as well start with DECL_ARGUMENTS and move
that to DECL_CHAIN at the end of every iteration. And then
query ssa_default_def (DECL_STRUCT_FUNCTION (assume_id), parm)
in each case and get global range of what that returns.
OK, this is the bit of code I dont know how to write :-)
yes, op is the name of the value within this current function, and yes, that
needs to be mapped to the argument decl in the assume function. Then we
need to query what range was given to that name during the assume pass.
when that is returned, the add_range (op, range) will inject it as a side
effect.
Can you write that loop?
I meant something like (untested code):
&& gimple_call_internal_fn (s) == IFN_ASSUME)
{
tree assume_id = gimple_call_arg (s, 0);
- for (unsigned i = 1; i < gimple_call_num_args (s); i++)
+ tree parm = DECL_ARGUMENTS (assume_id);
+ struct function *fun = DECL_STRUCT_FUNCTION (assume_id);
+ for (unsigned i = 1;
+ i < gimple_call_num_args (s) && parm;
+ i++, parm = DECL_CHAIN (parm))
{
tree op = gimple_call_arg (s, i);
tree type = TREE_TYPE (op);
+ tree arg = ssa_default_def (fun, parm);
+ if (arg == NULL_TREE)
+ continue;
if (gimple_range_ssa_p (op) && Value_Range::supports_type_p (type))
{
Value_Range assume_range (type);
and querying SSA_NAME_RANGE_INFO of arg rather than op.
Thanks, I had actually come to most of those conclusions already, except
for the DECL_STRUCT_FUNCTION bit.. I was stuck on that :-)
So the SSA_NAMEs for default_defs are never disposed of? so I can query
them even though they are not in the current function decl? huh. I did
not know that.
OK, attached is the latest set of patches. not bootstrapped or
anything, but very interesting.
from.assumption pass:
;; Function _Z3bari._assume.0 (_Z3bari._assume.0, funcdef_no=5,
decl_uid=2184, cgraph_uid=7, symbol_order=7)
Assumptions :
--------------
x_1(D) -> [irange] int [42, 42] NONZERO 0x2a
__attribute__((no_icf, noclone, noinline, noipa))
bool _Z3bari._assume.0 (int x)
{
bool _2;
;; basic block 2, loop depth 0
;; pred: ENTRY
_2 = x_1(D) == 42;
return _2;
;; succ: EXIT
}
and in the VRP2 pass, I see:
_Z3bari._assume.0 assume inferred range of x_1(D) (param x) = [irange]
int [42, 42] NONZERO 0x2a
int bar (int x)
{
<bb 2> [local count: 1073741824]:
.ASSUME (_Z3bari._assume.0, x_1(D));
return 42;
}
Huh. lookit that.....
Anyway, let me clean this up a bit more, but so far so good.
I'll try bootstrapping and such
Andrew
From 62cc63ca8d5cce3593cdb4b35e5fe96b0ecc77a8 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacl...@redhat.com>
Date: Tue, 18 Oct 2022 16:29:49 -0400
Subject: [PATCH 1/3] Infer support
---
gcc/gimple-range-infer.cc | 40 +++++++++++++++++++++++++++++++++++++++
1 file changed, 40 insertions(+)
diff --git a/gcc/gimple-range-infer.cc b/gcc/gimple-range-infer.cc
index f0d66d047a6..3e376740796 100644
--- a/gcc/gimple-range-infer.cc
+++ b/gcc/gimple-range-infer.cc
@@ -35,6 +35,7 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-iterator.h"
#include "gimple-walk.h"
#include "cfganal.h"
+#include "tree-dfa.h"
// Adapted from infer_nonnull_range_by_dereference and check_loadstore
// to process nonnull ssa_name OP in S. DATA contains a pointer to a
@@ -111,6 +112,45 @@ gimple_infer_range::gimple_infer_range (gimple *s)
// Fallthru and walk load/store ops now.
}
+ // Look for ASSUME calls, and call query_assume_call for each argument
+ // to determine if there is any inferred range to be had.
+ if (is_a<gcall *> (s) && gimple_call_internal_p (s)
+ && gimple_call_internal_fn (s) == IFN_ASSUME)
+ {
+ tree arg;
+ unsigned i;
+ tree assume_id = TREE_OPERAND (gimple_call_arg (s, 0), 0);
+ struct function *fun = DECL_STRUCT_FUNCTION (assume_id);
+ for (arg = DECL_ARGUMENTS (assume_id), i = 1;
+ arg && i < gimple_call_num_args (s);
+ i++, arg = DECL_CHAIN (arg))
+ {
+ tree op = gimple_call_arg (s, i);
+ tree type = TREE_TYPE (op);
+ tree def = ssa_default_def (fun, arg);
+ if (type != TREE_TYPE (arg) || !def)
+ continue;
+ if (gimple_range_ssa_p (op) && Value_Range::supports_type_p (type))
+ {
+ Value_Range assume_range (type);
+ global_ranges.range_of_expr (assume_range, def);
+ {
+ add_range (op, assume_range);
+ if (dump_file)
+ {
+ print_generic_expr (dump_file, assume_id, TDF_SLIM);
+ fprintf (dump_file, " assume inferred range of ");
+ print_generic_expr (dump_file, op, TDF_SLIM);
+ fprintf (dump_file, " (param ");
+ print_generic_expr (dump_file, arg, TDF_SLIM);
+ fprintf (dump_file, ") = ");
+ assume_range.dump (dump_file);
+ fputc ('\n', dump_file);
+ }
+ }
+ }
+ }
+ }
// Look for possible non-null values.
if (flag_delete_null_pointer_checks && gimple_code (s) != GIMPLE_ASM
&& !gimple_clobber_p (s))
--
2.37.3
From f163826f0e2b266c668e1500b3feb9a210569a0d Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacl...@redhat.com>
Date: Tue, 18 Oct 2022 16:30:04 -0400
Subject: [PATCH 2/3] assume_query support
---
gcc/gimple-range-gori.h | 6 +-
gcc/gimple-range.cc | 161 ++++++++++++++++++++++++++++++++++++++++
gcc/gimple-range.h | 17 +++++
3 files changed, 181 insertions(+), 3 deletions(-)
diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h
index c7a32162a1b..6cc533b58b2 100644
--- a/gcc/gimple-range-gori.h
+++ b/gcc/gimple-range-gori.h
@@ -165,15 +165,15 @@ public:
bool has_edge_range_p (tree name, basic_block bb = NULL);
bool has_edge_range_p (tree name, edge e);
void dump (FILE *f);
+ bool compute_operand_range (vrange &r, gimple *stmt, const vrange &lhs,
+ tree name, class fur_source &src,
+ value_relation *rel = NULL);
private:
bool refine_using_relation (tree op1, vrange &op1_range,
tree op2, vrange &op2_range,
fur_source &src, relation_kind k);
bool may_recompute_p (tree name, edge e);
bool may_recompute_p (tree name, basic_block bb = NULL);
- bool compute_operand_range (vrange &r, gimple *stmt, const vrange &lhs,
- tree name, class fur_source &src,
- value_relation *rel = NULL);
bool compute_operand_range_switch (vrange &r, gswitch *s, const vrange &lhs,
tree name, fur_source &src);
bool compute_operand1_range (vrange &r, gimple_range_op_handler &handler,
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index d67d6499c78..0990c1ca01e 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -645,3 +645,164 @@ disable_ranger (struct function *fun)
delete fun->x_range_query;
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 is can determine ranges forr
+// 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 (!global.get_global_range (op_range, op)
+ && m_gori.compute_operand_range (op_range, s, lhs, op, src)
+ && !op_range.varying_p ())
+ {
+ 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 argmeuents, 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);
+}
diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h
index 8b2ff5685e5..4dc7bc33c5f 100644
--- a/gcc/gimple-range.h
+++ b/gcc/gimple-range.h
@@ -80,4 +80,21 @@ 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);
+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
--
2.37.3
From 41a98cf507b96d9c64eed7c0f3b4daec5357e5a3 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacl...@redhat.com>
Date: Mon, 17 Oct 2022 12:28:21 -0400
Subject: [PATCH 3/3] Show output in assume pass
---
gcc/tree-vrp.cc | 31 +++++++++++++++++++++++++++++++
1 file changed, 31 insertions(+)
diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc
index 1adb15c9934..b7c59cfa057 100644
--- a/gcc/tree-vrp.cc
+++ b/gcc/tree-vrp.cc
@@ -50,6 +50,7 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-range-path.h"
#include "value-pointer-equiv.h"
#include "gimple-fold.h"
+#include "tree-dfa.h"
/* Set of SSA names found live during the RPO traversal of the function
for still active basic-blocks. */
@@ -4465,6 +4466,36 @@ public:
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_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);
+ }
return TODO_discard_function;
}
--
2.37.3
