This patch adds 2 routine that can be called to generate GORI information.
The primar API is:
bool gori_on_edge (class ssa_cache &r, edge e, range_query *query =
NULL, gimple_outgoing_range *ogr = NULL);
This will populate an ssa-cache R with any ranges that are generated by
edge E. It will use QUERY, if provided, to satisfy any incoming
values. if OGR is provided, it is used to pick up hard edge values..
like TRUE, FALSE, or switch edges.
It currently only works for TRUE/FALSE conditionals, and doesn't try to
solve complex logical combinations. ie (a <6 && b > 6) || (a>10 || b <
3) as those can get exponential and require multiple evaluations of the
IL to satisfy. It will fully utilize range-ops however and so comes up
with many ranges ranger does.
It also provides the "raw" ranges on the edge.. ie. it doesn't try to
figure out anything outside the current basic block, but rather reflects
exactly what the edge indicates.
ie:
<bb 2> :
x.0_1 = (unsigned int) x_20(D);
_2 = x.0_1 + 4294967292;
if (_2 > 4)
goto <bb 3>; [INV]
else
goto <bb 4>; [INV]
produces
Edge ranges BB 2->3
x.0_1 : [irange] unsigned int [0, 3][9, +INF]
_2 : [irange] unsigned int [5, +INF]
x_20(D) : [irange] int [-INF, 3][9, +INF]
Edge ranges BB 2->4
x.0_1 : [irange] unsigned int [4, 8] MASK 0xf VALUE 0x0
_2 : [irange] unsigned int [0, 4]
x_20(D) : [irange] int [4, 8] MASK 0xf VALUE 0x0
It performs a linear walk through juts the required statements, so each
of the the above vectors are generated by visiting each of the 3
statements exactly once, so its pretty quick.
The other entry point is:
bool gori_name_on_edge (vrange &r, tree name, edge e, range_query *q);
This does basically the same thing, except it only looks at whether NAME
has a range, and returns it if it does. not other overhead.
Pushed.
From 52c1e2c805bc2fd7a30583dce3608b738f3a5ce4 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Tue, 15 Aug 2023 17:29:58 -0400
Subject: [PATCH 1/3] Add outgoing range vector calcualtion API
Provide a GORI API which can produce a range vector for all outgoing
ranges on an edge without any of the other infratructure.
* gimple-range-gori.cc (gori_stmt_info::gori_stmt_info): New.
(gori_calc_operands): New.
(gori_on_edge): New.
(gori_name_helper): New.
(gori_name_on_edge): New.
* gimple-range-gori.h (gori_on_edge): New prototype.
(gori_name_on_edge): New prototype.
---
gcc/gimple-range-gori.cc | 213 +++++++++++++++++++++++++++++++++++++++
gcc/gimple-range-gori.h | 15 +++
2 files changed, 228 insertions(+)
@@ -1605,3 +1605,216 @@ gori_export_iterator::get_name ()
}
return NULL_TREE;
}
+
+// This is a helper class to set up STMT with a known LHS for further GORI
+// processing.
+
+class gori_stmt_info : public gimple_range_op_handler
+{
+public:
+ gori_stmt_info (vrange &lhs, gimple *stmt, range_query *q);
+ Value_Range op1_range;
+ Value_Range op2_range;
+ tree ssa1;
+ tree ssa2;
+};
+
+
+// Uses query Q to get the known ranges on STMT with a LHS range
+// for op1_range and op2_range and set ssa1 and ssa2 if either or both of
+// those operands are SSA_NAMES.
+
+gori_stmt_info::gori_stmt_info (vrange &lhs, gimple *stmt, range_query *q)
+ : gimple_range_op_handler (stmt)
+{
+ ssa1 = NULL;
+ ssa2 = NULL;
+ // Don't handle switches as yet for vector processing.
+ if (is_a<gswitch *> (stmt))
+ return;
+
+ // No frther processing for VARYING or undefined.
+ if (lhs.undefined_p () || lhs.varying_p ())
+ return;
+
+ // If there is no range-op handler, we are also done.
+ if (!*this)
+ return;
+
+ // Only evaluate logical cases if both operands must be the same as the LHS.
+ // Otherwise its becomes exponential in time, as well as more complicated.
+ if (is_gimple_logical_p (stmt))
+ {
+ gcc_checking_assert (range_compatible_p (lhs.type (), boolean_type_node));
+ enum tree_code code = gimple_expr_code (stmt);
+ if (code == TRUTH_OR_EXPR || code == BIT_IOR_EXPR)
+ {
+ // [0, 0] = x || y means both x and y must be zero.
+ if (!lhs.singleton_p () || !lhs.zero_p ())
+ return;
+ }
+ else if (code == TRUTH_AND_EXPR || code == BIT_AND_EXPR)
+ {
+ // [1, 1] = x && y means both x and y must be one.
+ if (!lhs.singleton_p () || lhs.zero_p ())
+ return;
+ }
+ }
+
+ tree op1 = operand1 ();
+ tree op2 = operand2 ();
+ ssa1 = gimple_range_ssa_p (op1);
+ ssa2 = gimple_range_ssa_p (op2);
+ // If both operands are the same, only process one of them.
+ if (ssa1 && ssa1 == ssa2)
+ ssa2 = NULL_TREE;
+
+ // Extract current ranges for the operands.
+ fur_stmt src (stmt, q);
+ if (op1)
+ {
+ op1_range.set_type (TREE_TYPE (op1));
+ src.get_operand (op1_range, op1);
+ }
+
+ // And satisfy the second operand for single op satements.
+ if (op2)
+ {
+ op2_range.set_type (TREE_TYPE (op2));
+ src.get_operand (op2_range, op2);
+ }
+ else if (op1)
+ op2_range = op1_range;
+ return;
+}
+
+
+// Process STMT using LHS as the range of the LHS. Invoke GORI processing
+// to resolve ranges for all SSA_NAMES feeding STMT which may be altered
+// based on LHS. Fill R with the results, and resolve all incoming
+// ranges using range-query Q.
+
+static void
+gori_calc_operands (vrange &lhs, gimple *stmt, ssa_cache &r, range_query *q)
+{
+ struct gori_stmt_info si(lhs, stmt, q);
+ if (!si)
+ return;
+
+ Value_Range tmp;
+ // Now evaluate operand ranges, and set them in the edge cache.
+ // If there was already a range, leave it and do no further evaluation.
+ if (si.ssa1 && !r.has_range (si.ssa1))
+ {
+ tmp.set_type (TREE_TYPE (si.ssa1));
+ if (si.calc_op1 (tmp, lhs, si.op2_range))
+ si.op1_range.intersect (tmp);
+ r.set_range (si.ssa1, si.op1_range);
+ gimple *src = SSA_NAME_DEF_STMT (si.ssa1);
+ // If defintion is in the same basic lock, evaluate it.
+ if (src && gimple_bb (src) == gimple_bb (stmt))
+ gori_calc_operands (si.op1_range, src, r, q);
+ }
+
+ if (si.ssa2 && !r.has_range (si.ssa2))
+ {
+ tmp.set_type (TREE_TYPE (si.ssa2));
+ if (si.calc_op2 (tmp, lhs, si.op1_range))
+ si.op2_range.intersect (tmp);
+ r.set_range (si.ssa2, si.op2_range);
+ gimple *src = SSA_NAME_DEF_STMT (si.ssa2);
+ if (src && gimple_bb (src) == gimple_bb (stmt))
+ gori_calc_operands (si.op2_range, src, r, q);
+ }
+}
+
+// Use ssa_cache R as a repository for all outgoing ranges on edge E that
+// can be calculated. Use OGR if present to establish starting edge ranges,
+// and Q to resolve operand values. If Q is NULL use the current range
+// query available to the system.
+
+bool
+gori_on_edge (ssa_cache &r, edge e, range_query *q, gimple_outgoing_range *ogr)
+{
+ // Start with an empty vector
+ r.clear ();
+ int_range_max lhs;
+ // Determine if there is an outgoing edge.
+ gimple *stmt;
+ if (ogr)
+ stmt = ogr->edge_range_p (lhs, e);
+ else
+ {
+ stmt = gimple_outgoing_range_stmt_p (e->src);
+ if (stmt && is_a<gcond *> (stmt))
+ gcond_edge_range (lhs, e);
+ else
+ stmt = NULL;
+ }
+ if (!stmt)
+ return false;
+ gori_calc_operands (lhs, stmt, r, q);
+ return true;
+}
+
+// Helper for GORI_NAME_ON_EDGE which uses query Q to determine if STMT
+// provides a range for NAME, and returns it in R if so. If it does not,
+// continue processing feeding statments until we run out of statements
+// or fine a range for NAME.
+
+bool
+gori_name_helper (vrange &r, tree name, vrange &lhs, gimple *stmt,
+ range_query *q)
+{
+ struct gori_stmt_info si(lhs, stmt, q);
+ if (!si)
+ return false;
+
+ if (si.ssa1 == name)
+ return si.calc_op1 (r, lhs, si.op2_range);
+ if (si.ssa2 == name)
+ return si.calc_op2 (r, lhs, si.op1_range);
+
+ Value_Range tmp;
+ // Now evaluate operand ranges, and set them in the edge cache.
+ // If there was already a range, leave it and do no further evaluation.
+ if (si.ssa1)
+ {
+ tmp.set_type (TREE_TYPE (si.ssa1));
+ if (si.calc_op1 (tmp, lhs, si.op2_range))
+ si.op1_range.intersect (tmp);
+ gimple *src = SSA_NAME_DEF_STMT (si.ssa1);
+ // If defintion is in the same basic lock, evaluate it.
+ if (src && gimple_bb (src) == gimple_bb (stmt))
+ if (gori_name_helper (r, name, si.op1_range, src, q))
+ return true;
+ }
+
+ if (si.ssa2)
+ {
+ tmp.set_type (TREE_TYPE (si.ssa2));
+ if (si.calc_op2 (tmp, lhs, si.op1_range))
+ si.op2_range.intersect (tmp);
+ gimple *src = SSA_NAME_DEF_STMT (si.ssa2);
+ if (src && gimple_bb (src) == gimple_bb (stmt))
+ if (gori_name_helper (r, name, si.op2_range, src, q))
+ return true;
+ }
+ return false;
+}
+
+// Check if NAME has an outgoing range on edge E. Use query Q to evaluate
+// the operands. Return TRUE and the range in R if there is an outgoing range.
+// This is like gori_on_edge except it only looks for the single name and
+// does not require an ssa_cache.
+
+bool
+gori_name_on_edge (vrange &r, tree name, edge e, range_query *q)
+{
+ int_range_max lhs;
+ gimple *stmt = gimple_outgoing_range_stmt_p (e->src);
+ if (!stmt || !is_a<gcond *> (stmt))
+ return false;
+ gcond_edge_range (lhs, e);
+ return gori_name_helper (r, name, lhs, stmt, q);
+}
@@ -208,6 +208,21 @@ private:
int m_not_executable_flag;
};
+// These APIs are used to query GORI if there are ranges generated on an edge.
+// GORI_ON_EDGE is used to get all the ranges at once (returned in an
+// ssa_cache structure).
+// GORI_NAME_ON_EDGE is used to simply ask if NAME has a range on edge E
+
+// Fill ssa-cache R with any outgoing ranges on edge E, using OGR and QUERY.
+bool gori_on_edge (class ssa_cache &r, edge e,
+ range_query *query = NULL,
+ gimple_outgoing_range *ogr = NULL);
+
+// Query if NAME has an outgoing range on edge E, and return it in R if so.
+// Note this doesnt use ranger, its a static GORI analysis of the range in
+// block e->src and is based on any branch at the exit of that block.
+bool gori_name_on_edge (vrange &r, tree name, edge e, range_query *q = NULL);
+
// For each name that is an import into BB's exports..
#define FOR_EACH_GORI_IMPORT_NAME(gori, bb, name) \
for (gori_export_iterator iter ((gori).imports ((bb))); \
--
2.41.0