[COMMITTED 1/7] Initial value-relation code.

[Andrew MacLeod]

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 
2 parts:
- 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 
relations.

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 
routines.

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.

Andrew



-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Initial-value-relation-code.patch
Type: text/x-patch
Size: 40051 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20210622/09c0a922/attachment-0001.bin>