mbox series

[COMMITTED,0/4] Add partial equivalences to the oracle.

Message ID 27aee40a-5cb5-d680-e6ca-369839d3580a@redhat.com
Headers show
Series Add partial equivalences to the oracle. | expand

Message

Andrew MacLeod Oct. 13, 2022, 3:30 p.m. UTC 
This patch implements partial equivalences in the relation oracle.

They are tracked much like normal equivalences, in that they all belong 
to a set.  I refer to them as "slices" of an ssa-name.  A little extra 
info is maintained for a partial set in class pe_slice.

A slice contains the bitmap of other members of the partial equivalence, 
the root ssa-name that every member is a slice of, along with the 
relation code indicating if its an 8, 16, 32, or 64 bit slice of that name.

4 new relation kinds are added for these:  VREL_PE8, VREL_PE16, 
VREL_PE32 and VREL_PE64.

The oracle maintains a vector of pe_slices representing one entry for 
each ssa-name globally. we determine at the def point what the LHS is a 
slice of. It is either the RHS, or becomes a member of the set the RHS 
is already in. ie:

long b_3 = foo()
a_4 = (short) b_3

a_4 is registered as a 16 bit slice of b_3.  and the slice set is {b_3, a_4}

c_5 = (char) a_4

a_4 is already in a slice set, so c_5 is registered into the set as a 8 
bit slice of b_3, and the set now contains {b_3, a_4, c_5}

If we query the relation between c_5 and a_4, it is trivial to check 
that that are in the same slice set, and therefore share bits.  The 
number of bits they share is the MIN of the slice size of each, so MIN 
(16, 8). The relation will be returned as VREL_PE8.   This means you can 
count on the lower 8 bits to be identical between the 2 ssa-names, and 
they will be defined as those bits in the root value in b_3.

That relation can then be used to determine if there is anything useful 
to be done with this relation by the caller.

In particular, this will fix 2 regressions from last year, PR 102540 and 
102872 where we lose the connection between a cast and a bitwise mask of 
the same size.  ie:

static long a;
static unsigned b;
int test1 () {
     long c, e;
     c = b = a;
     e = c ? 2 / (c + 1) : 0;
     if (e && !b)
         kill ();
     a = 0;

   <bb 2> :
Equivalence set : [_6, c_10]
Partial equiv (_2 pe32 a.0_1)
Partial equiv (_6 pe32 a.0_1)

   a.0_1 = a;
   _2 = (unsigned int) a.0_1;
   b = _2;
   _6 = a.0_1 & 4294967295;
   c_10 = _6;
   if (c_10 != 0)
     goto <bb 3>; [INV]
   else
     goto <bb 6>; [INV]

_6 : [irange] long int [0, 4294967295] NONZERO 0xffffffff
c_10 : [irange] long int [0, 4294967295] NONZERO 0xffffffff
2->3  (T) a.0_1 :       [irange] long int [-INF, -1][1, +INF]
2->3  (T) _6 :  [irange] long int [1, 4294967295] NONZERO 0xffffffff
2->3  (T) c_10 :        [irange] long int [1, 4294967295] NONZERO 0xffffffff
2->6  (F) a.0_1 :       [irange] long int [-INF, -4294967296][0, +INF] 
NONZERO 0xffffffff00000000
2->6  (F) _6 :  [irange] long int [0, 0] NONZERO 0x0
2->6  (F) c_10 :        [irange] long int [0, 0] NONZERO 0x0

   <bb 3> :
   _4 = c_10 + 1;
   iftmp.2_12 = 2 / _4;
   if (iftmp.2_12 != 0)
     goto <bb 4>; [INV]
   else
     goto <bb 6>; [INV]

   <bb 4> :
   if (_2 == 0)

When we get to _2 == 0, ranger looks for any equivalences (full or 
partial) of _2 coming into this block. It sees that _6 on the edges 
2->3->4 has the range

2->3  (T) _6 :  [irange] long int [1, 4294967295] NONZERO 0xffffffff
and shares 32 bits.   Both _6 and _2 are 32 bits, so it casts that range 
of _6 and determines _2 is

_2      [irange] unsigned int [1, +INF]

and folds away the condition.

Bootstrapped on x86_64-pc-linux-gnu with no regressions.