[COMMITTED 1/7] Initial value-relation code.
Tue Jun 22 13:17:41 GMT 2021
This file introduces a relation oracle to GCC.
Rather than introducing a new enum for relations, I chose to reuse a
range of enum tree_code, leaving us with mostly familiar names:
EQ_EXPR, NE_EXPR, GT_EXPR, GE_EXPR, LT_EXPR and LE_EXPR. In addition to
these relations, are 2 other codes:
#define VREL_NONE TRUTH_NOT_EXPR
#define VREL_EMPTY LTGT_EXPR
VREL_NONE represents a lack of a relation (ie a = b + c there is no
relation between b and c, so thats VREL_NONE)
VREL_EMPTY represents an EMPTY , or impossible relation. This is
usually the result of combining relations that apply (ie, a > b && a <
b provides a VREL_EMPTY representing the relation between a and b on
the true side. Its impossible.)
The additional relations have tree codes chosen carefully to form a
contiguous series from VREL_NONE to NE_EXPR enabling some internal
calculation tables to be used indexing from 0..last_relation . This is
easily changed, but seems convenient.
The oracle is pretty basic to start, but will be enhanced as we move
along. It requires a dominance tree and stores/looks up things based on
dominance. It hasn't been extensively analyzed in an iterative/on-demand
environment yet, so there may be some warts that show up. It should
never give a wrong result, but its possible it may miss something in
some instances. We'll work those out as we find them. It exists in
- an equivalence oracle which manages all the EQ_EXPR relations, and
groups equivalences as sets, and
- a relation oracle which derives from that which handles all the other
The API is straightforward. Relations are registered via one of 2 routines:
void register_relation (gimple *stmt, relation_kind k, tree op1, tree op2);
void register_relation (edge e, relation_kind k, tree op1, tree op2);
and there is a single query routine:
relation_kind query_relation (basic_block bb, tree ssa1, tree ssa2);
Our friend the range_query object now contains a relation pointer, and
this is set and used by ranger. range_query has also had 2 query
routines added so if a pass is using a ranger, it can also invoke the
range queries that same way range_of_expr is invokes. ie:
get_range_query (cfun)->query_relation (stmt, ssa1, ssa2) THis
mechanism has the advantage that you dont need to check if an oracle is
present, it'll simple return VREL_NONE (no relation) between 2 ssa-names
if there is no oracle.
More advanced users can access the oracle directly via the
get_range_query (cfun)->oracle () call. It would be possible to create
an oracle for a pass without a ranger, and manage the relations in the
pass. That is not being done yet, but would be easy enough to add the
enable/disable() oracle routines much like the enable/disable_ranger
When using ranger, this information is set and propagated automatically,
and the results are transparently applied to the ranges that are
generated. For instance,
if (a_2 < b_3) // register relation a_2 < b_3 on the true edge
c_3 = a_2 > b_3 // applies a_2 < b_3, and the range of c_3 is set
to [0, 0] or false.
Currently only direct 1st order relations are tracked. I will get to
transitive relations soon, but that is not in this first round.
Relations on edges are also currently limited to single predecessor
blocks .. They are simply dropped/ignored if the destination of the
edge has multiple preds.
I will be writing up a relation guide in the not too distant future,
alone with a few of the other components.
This patch provides the oracle, as well as the range_query interface,
but does not actually do anything.
Bootstraps on x86_64-pc-linux-gnu with no regressions. Pushed.
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 40051 bytes
Desc: not available
More information about the Gcc-patches