From: Andrew MacLeod <amacleod@redhat.com>
To: Jakub Jelinek <jakub@redhat.com>, Jan Hubicka <jh@suse.cz>,
Richard Biener <rguenther@suse.de>,
gcc-patches@gcc.gnu.org
Subject: Re: [PATCH] middle-end, v4: IFN_ASSUME support [PR106654]
Date: Wed, 19 Oct 2022 14:25:59 -0400 [thread overview]
Message-ID: <332ba657-c7ac-72d4-b8dc-fccd321aa60e@redhat.com> (raw)
In-Reply-To: <Y1A20pnavpfU0Zde@tucnak>
[-- Attachment #1: Type: text/plain, Size: 3184 bytes --]
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
[-- Attachment #2: 0001-Infer-support.patch --]
[-- Type: text/x-patch, Size: 2456 bytes --]
From 62cc63ca8d5cce3593cdb4b35e5fe96b0ecc77a8 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@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
[-- Attachment #3: 0002-assume_query-support.patch --]
[-- Type: text/x-patch, Size: 7659 bytes --]
From f163826f0e2b266c668e1500b3feb9a210569a0d Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@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
[-- Attachment #4: 0003-Show-output-in-assume-pass.patch --]
[-- Type: text/x-patch, Size: 1785 bytes --]
From 41a98cf507b96d9c64eed7c0f3b4daec5357e5a3 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@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
next prev parent reply other threads:[~2022-10-19 18:26 UTC|newest]
Thread overview: 33+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-10-10 8:54 [PATCH] middle-end " Jakub Jelinek
2022-10-10 21:09 ` Jason Merrill
2022-10-10 21:19 ` Jakub Jelinek
2022-10-11 13:36 ` [PATCH] middle-end, v2: " Jakub Jelinek
2022-10-12 15:48 ` Jason Merrill
2022-10-13 6:50 ` [PATCH] middle-end, v3: " Jakub Jelinek
2022-10-14 11:27 ` Richard Biener
2022-10-14 18:33 ` Jakub Jelinek
2022-10-17 6:55 ` Richard Biener
2022-10-17 15:44 ` [PATCH] middle-end, v4: " Jakub Jelinek
2022-10-18 7:00 ` Richard Biener
2022-10-18 21:31 ` Andrew MacLeod
2022-10-19 16:06 ` Jakub Jelinek
2022-10-19 16:55 ` Andrew MacLeod
2022-10-19 17:39 ` Jakub Jelinek
2022-10-19 17:41 ` Jakub Jelinek
2022-10-19 18:25 ` Andrew MacLeod [this message]
2022-10-19 17:14 ` Andrew MacLeod
2022-10-11 18:05 ` [PATCH] middle-end " Andrew MacLeod
2022-10-12 10:15 ` Jakub Jelinek
2022-10-12 14:31 ` Andrew MacLeod
2022-10-12 14:39 ` Jakub Jelinek
2022-10-12 16:12 ` Andrew MacLeod
2022-10-13 8:11 ` Richard Biener
2022-10-13 9:53 ` Jakub Jelinek
2022-10-13 13:16 ` Andrew MacLeod
2022-10-13 9:57 ` Jakub Jelinek
2022-10-17 17:53 ` Andrew MacLeod
2022-10-14 20:43 ` Martin Uecker
2022-10-14 21:20 ` Jakub Jelinek
2022-10-15 8:07 ` Martin Uecker
2022-10-15 8:53 ` Jakub Jelinek
2022-10-17 5:52 ` Martin Uecker
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=332ba657-c7ac-72d4-b8dc-fccd321aa60e@redhat.com \
--to=amacleod@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=jakub@redhat.com \
--cc=jh@suse.cz \
--cc=rguenther@suse.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).