getting branch conditions using ranger

getting branch conditions using ranger

[Martin Sebor]

Andrew, to improve the context of the late warnings I'm trying
to see how to get the execution path(s) leading from function
entry up to a statement.  For example, for the code below I'd
like to "collect" and show the three conditionals in the context
of the warning:

extern char a[9];

void f (int m, int n, void *s)
{
   if (m < 3) m = 3;
   if (n < 4) n = 4;
   if (s != 0)
     {
       char *d = a + 3;
       __builtin_memcpy (d, s, m + n);
     }
}

At a minimum, I'd like to print a note after the warning:

   warning: ‘__builtin_memcpy’ writing between 7 and 2147483647 bytes 
into a region of size 6 overflows the destination [-Wstringop-overflow=]

   note: when 'm >= 3 && n >= 4 && s != 0'

(The final version would point to each conditional in the source
like the static analyzer does.)

For conditions that involve ranges used in the statements (i.e.,
the first two conditions in the source above), I wonder if rather
than traversing the CFG in a separate step, I might be able to
use Ranger to collect the conditions at the time it populates its
cache (i.e., when I call it to get range info for each statement).
I imagine I would need to derive a new class from gimple_ranger
and override some virtual member functions.  (And maybe also do
the same for ranger_cache?)

Does this sound like something I should be able to do within
the framework?  If yes, do you have any tips or suggestions for
where/how to start?

Thanks
Martin

PS I'm assuming -O0 for the above test case where the m + n
expression is a sum of two PHIs.  With -O1 and higher some of
the integer conditionals end up transformed into MAX_EXPRs so
it will likely need to be handled differently or I may not be
able to capture all the conditions reliably.  I don't know how
much that might compromise the result.

Re: getting branch conditions using ranger

[Andrew MacLeod]

On 12/14/21 18:55, Martin Sebor wrote:
> Andrew, to improve the context of the late warnings I'm trying
> to see how to get the execution path(s) leading from function
> entry up to a statement.  For example, for the code below I'd
> like to "collect" and show the three conditionals in the context
> of the warning:
>
> extern char a[9];
>
> void f (int m, int n, void *s)
> {
>   if (m < 3) m = 3;
>   if (n < 4) n = 4;
>   if (s != 0)
>     {
>       char *d = a + 3;
>       __builtin_memcpy (d, s, m + n);
>     }
> }
>
> At a minimum, I'd like to print a note after the warning:
>
>   warning: ‘__builtin_memcpy’ writing between 7 and 2147483647 bytes 
> into a region of size 6 overflows the destination [-Wstringop-overflow=]
>
>   note: when 'm >= 3 && n >= 4 && s != 0'
>
> (The final version would point to each conditional in the source
> like the static analyzer does.)


Finding the exact location of the conditional may not be possible.. the 
condition could be the aggregation of multiple statements.  The ranges 
of m and n are set via 2 statements, the condition and the assignment, 
and then collected by a 3rd, the PHI node.

The "note:" itself could simply be created from the ranges..  the range 
at the memcpy of m,  n and s are:

m_3  : int [3, +INF]
n_4  : int [4, +INF]
s_10(D) :     void * [1B, +INF]

which could be easily translated to 'm >= 3 && n >= 4 && s != 0', 
assuming you can figure out the original source name.. In this case 
happens to be the VAR on the ssa-name, but you can't always count on 
that.  I'd also point out there is no statement which has m >=3 or n>= 
4, but rather a series of statements that produce that result.


>
> For conditions that involve ranges used in the statements (i.e.,
> the first two conditions in the source above), I wonder if rather
> than traversing the CFG in a separate step, I might be able to
> use Ranger to collect the conditions at the time it populates its
> cache (i.e., when I call it to get range info for each statement).
> I imagine I would need to derive a new class from gimple_ranger
> and override some virtual member functions.  (And maybe also do
> the same for ranger_cache?)
>
> Does this sound like something I should be able to do within
> the framework?  If yes, do you have any tips or suggestions for
> where/how to start?
>
That is not really going to work. The cache is agnostic as to why there 
are ranges or what caused them.  It is primarily a propagation engine 
which utilizes the edge ranges provided by GORI and range-ops.  Ranger 
itself is the controller for this property propagation.

GORI does not treat any statement as special.  It is an equation solver 
which uses range-ops to algebraically solve for an unknown value when 
the other values are known.  The "if" condition at the exit of a basic 
block is considered no different than an assignment statement where the 
LHS is either [0,0] or [1,1] depending on the edge you are looking at. 
    So to use your example above for just m:

     <bb 2> :
     if (m_6(D) <= 2)
       goto <bb 3>; [INV]       //  [1,1] = m_6 <= 2
     else
       goto <bb 4>; [INV]      //    [0,0] = m_6 <= 2

2->3  (T) m_6(D) :      int [-INF, 2]
2->4  (F) m_6(D) :      int [3, +INF]

=========== BB 3 ============
     <bb 3> :

=========== BB 4 ============
Imports: n_8(D)
Exports: n_8(D)
n_8(D)  int VARYING
     <bb 4> :
     # m_3 = PHI <m_6(D)(2), 3(3)>    //  m_3 = union (m_6 (2->4), 
[3,3]) = union ([3, +INF],[3,3]) = [3, +INF]

m_3 : int [3, +INF]


We generate 3 ranges for m..  m_6 on the 1)edge 2->3, 2)edge 2->4 and 
3)combine them with the constant 3 to produce m_3 at the PHI.

This all happens at a fairly low level, and you wont be able to overload 
anything to be able to log it in a sensible fashion. And I'm not sure 
how you would go about logging the arbitrarily long series of actions 
that result in the range you are looking at, and then utilize it.  GORI 
could tell you that m_6 and m_3 are used in the range calculation, but 
then the IL tells you that too.


> Thanks
> Martin
>
> PS I'm assuming -O0 for the above test case where the m + n
> expression is a sum of two PHIs.  With -O1 and higher some of
> the integer conditionals end up transformed into MAX_EXPRs so
> it will likely need to be handled differently or I may not be
> able to capture all the conditions reliably.  I don't know how
> much that might compromise the result.
>
Within ranger is is irrelevant whether its from a MAX or a condition.

   <bb 3> [local count: 574129753]:
   _5 = MAX_EXPR <n_6(D), 4>;
   _7 = MAX_EXPR <m_4(D), 3>;
   _1 = _5 + _7;

_7 generates a range of [3, +INF] based on range-ops knowledge of how 
MAX works.

In both cases, for m_3 above and _7, the range of [3, +INF] is generated 
at the definition point... One is a PHI which includes some CFG 
propagation to retrieve the argument values and perform the calculation, 
and  _7 which is much simpler.. its just the global characteristic of 
the statement calculated by range-ops where the LHS is the unknown in 
the equation.  Ultimately, both ranges are created at the definition 
point of the ssa_name  _7 or m_3.

The question is what precisely do you want to do with the IL  and what 
do you want to point at?  Optimization makes mapping things back to the 
original IL problematic to be sure, and as you can see with the _7, even 
the symbolic name can become lost or changed.

GORI can be utilized to tell you whether a range is generated on an edge 
for any specific name, but it depends on what you want to do with it.  
There is currently no facility to ask which particular statement caused 
the range to be created, mostly because there hasn't been a need, and 
also because it is usually the result of a string of operations.   Given:

a = m + 10
if (m > 10 && m < 100)
     foo (a)

we see:

     <bb 2> :
     a_5 = m_4(D) + 10;
     m.0_1 = (unsigned int) m_4(D);
     _2 = m.0_1 + 4294967285;
     if (_2 <= 88)
       goto <bb 3>; [INV]
     else
       goto <bb 4>; [INV]

a_5 : int [-2147483638, +INF]
2->3  (T) m.0_1 :       unsigned int [11, 99]
2->3  (T) m_4(D) :      int [11, 99]
2->3  (T) a_5 :         int [21, 109]
2->4  (F) m.0_1 :       unsigned int [0, 10][100, +INF]
2->4  (F) m_4(D) :      int [-INF, 10][100, +INF]
2->4  (F) a_5 :         int [-2147483638, 20][110, +INF]

=========== BB 3 ============
a_5     int [21, 109]

We produce a range of [21, 109] for a_5,  but which statement would we 
point to as the "defining" statement for that range?  (_2 <= 88) isn't 
very useful.  a_5 is never used in a condition, but based on the reduced 
range of m_4 we can recalculate a_5 on that path to produce that 
value... but there is no good single thing to point to.

The condition can be arbitrarily complex as well:

if we change the condition to:

   if ((m > 10 && m < 100) || m == 200)
     foo (a);

     a_8 = m_7(D) + 10;
     m.0_1 = (unsigned int) m_7(D);
     _2 = m.0_1 + 4294967285;
     _3 = _2 <= 88;
     _4 = m_7(D) == 200;
     _5 = _3 | _4;
     if (_5 != 0)
       goto <bb 3>; [INV]
     else
       goto <bb 4>; [INV]

a_8 : int [-2147483638, +INF]
2->3  (T) m.0_1 :       unsigned int [11, 99][200, 200]
2->3  (T) m_7(D) :      int [11, 99][200, 200]
2->3  (T) a_8 :         int [21, 109][210, 210]
2->4  (F) m.0_1 :       unsigned int [0, 10][100, 199][201, +INF]
2->4  (F) m_7(D) :      int [-INF, 10][100, 199][201, +INF]
2->4  (F) a_8 :         int [-2147483638, 20][110, 209][211, +INF]

=========== BB 3 ============
a_8     int [21, 109][210, 210]

Now the condition that causes this range is a string of expressions that 
all combine to produce the range, again, none of which actually utilize 
a_8.   GORI uses range-ops to solve the equation from the bottom of the 
block upwards until it has a result for m_7,  and then recalculates a_8 
based on that.

We could produce a list of the ssa_names which are evaluated on each 
edge to produce a range.  In the latter case, the range of a_8 is 
produced by evaluating _5, _3, _4, m_7, _2, m.0_1, m_7, and finally a_8.


So I think the long answer to your question is no, ranger probably isn't 
going to provide a quick pointer to the information you are looking for. 
    However, its not clear to me precisely what you are looking for.   
GORI can provide lots of information about whether ranges are created or 
not from each basic block, and there is a fair amount of dependency 
information available about which names go into a calucaltion.  Its also 
good at seeing thru different combinations of expressions. The engine 
could also be repurposed, but to delve into the details of each 
low-level range operation in such a way to produce useful high-level 
information isn't clear to me how that would work.

You could reverse engineer an expression from the resulting range, and 
then point to the source statements from the aggregate of the line 
number info over all ssa_names definitions used in the calculation by 
GORI across the various blocks in the dominators, but I can see how that 
could quickly become verbose. Probably not that useful unless is was 
limited and some mechanism for combining source lines from different 
blocks in a meaningful way.

I'm not familiar with how much useful info the line-info has, nor how 
much "noise" this would produce.  I would expect this to rapidly 
degenerate and become confusing with missing information as the control 
flow or optimizations increase.  Perhaps it could be limited to just 
simple cases, if they could be easily identified.

Andrew

Re: getting branch conditions using ranger

[Martin Sebor]

On 12/15/21 12:23 PM, Andrew MacLeod wrote:
> On 12/14/21 18:55, Martin Sebor wrote:

Thanks a lot for the feedback!  I'll need some time to fully
digest it.  Just a few clarifying comments to explain what
I'm after.

>> Andrew, to improve the context of the late warnings I'm trying
>> to see how to get the execution path(s) leading from function
>> entry up to a statement.  For example, for the code below I'd
>> like to "collect" and show the three conditionals in the context
>> of the warning:
>>
>> extern char a[9];
>>
>> void f (int m, int n, void *s)
>> {
>>   if (m < 3) m = 3;
>>   if (n < 4) n = 4;
>>   if (s != 0)
>>     {
>>       char *d = a + 3;
>>       __builtin_memcpy (d, s, m + n);
>>     }
>> }
>>
>> At a minimum, I'd like to print a note after the warning:
>>
>>   warning: ‘__builtin_memcpy’ writing between 7 and 2147483647 bytes 
>> into a region of size 6 overflows the destination [-Wstringop-overflow=]
>>
>>   note: when 'm >= 3 && n >= 4 && s != 0'
>>
>> (The final version would point to each conditional in the source
>> like the static analyzer does.)
> 
> 
> Finding the exact location of the conditional may not be possible.. the 
> condition could be the aggregation of multiple statements.  The ranges 
> of m and n are set via 2 statements, the condition and the assignment, 
> and then collected by a 3rd, the PHI node.
> 
> The "note:" itself could simply be created from the ranges..  the range 
> at the memcpy of m,  n and s are:
> 
> m_3  : int [3, +INF]
> n_4  : int [4, +INF]
> s_10(D) :     void * [1B, +INF]
> 
> which could be easily translated to 'm >= 3 && n >= 4 && s != 0', 
> assuming you can figure out the original source name.. In this case 
> happens to be the VAR on the ssa-name, but you can't always count on 
> that.  I'd also point out there is no statement which has m >=3 or n>= 
> 4, but rather a series of statements that produce that result.

Understood.

> 
> 
>>
>> For conditions that involve ranges used in the statements (i.e.,
>> the first two conditions in the source above), I wonder if rather
>> than traversing the CFG in a separate step, I might be able to
>> use Ranger to collect the conditions at the time it populates its
>> cache (i.e., when I call it to get range info for each statement).
>> I imagine I would need to derive a new class from gimple_ranger
>> and override some virtual member functions.  (And maybe also do
>> the same for ranger_cache?)
>>
>> Does this sound like something I should be able to do within
>> the framework?  If yes, do you have any tips or suggestions for
>> where/how to start?
>>
> That is not really going to work. The cache is agnostic as to why there 
> are ranges or what caused them.  It is primarily a propagation engine 
> which utilizes the edge ranges provided by GORI and range-ops.  Ranger 
> itself is the controller for this property propagation.
> 
> GORI does not treat any statement as special.  It is an equation solver 
> which uses range-ops to algebraically solve for an unknown value when 
> the other values are known.  The "if" condition at the exit of a basic 
> block is considered no different than an assignment statement where the 
> LHS is either [0,0] or [1,1] depending on the edge you are looking at. 
>     So to use your example above for just m:
> 
>      <bb 2> :
>      if (m_6(D) <= 2)
>        goto <bb 3>; [INV]       //  [1,1] = m_6 <= 2
>      else
>        goto <bb 4>; [INV]      //    [0,0] = m_6 <= 2
> 
> 2->3  (T) m_6(D) :      int [-INF, 2]
> 2->4  (F) m_6(D) :      int [3, +INF]
> 
> =========== BB 3 ============
>      <bb 3> :
> 
> =========== BB 4 ============
> Imports: n_8(D)
> Exports: n_8(D)
> n_8(D)  int VARYING
>      <bb 4> :
>      # m_3 = PHI <m_6(D)(2), 3(3)>    //  m_3 = union (m_6 (2->4), 
> [3,3]) = union ([3, +INF],[3,3]) = [3, +INF]
> 
> m_3 : int [3, +INF]
> 
> 
> We generate 3 ranges for m..  m_6 on the 1)edge 2->3, 2)edge 2->4 and 
> 3)combine them with the constant 3 to produce m_3 at the PHI.
> 
> This all happens at a fairly low level, and you wont be able to overload 
> anything to be able to log it in a sensible fashion. And I'm not sure 
> how you would go about logging the arbitrarily long series of actions 
> that result in the range you are looking at, and then utilize it.  GORI 
> could tell you that m_6 and m_3 are used in the range calculation, but 
> then the IL tells you that too.

Yes, it is in the IL, and I need to get it from there.  Ranger
traverses the IL to build up the cache and I thought if I could
hook into it I could, in addition, collect the GIMPLE_CONDs that
Ranger relies on to determine the bounds.  (For each SSA_NAME
I'm thinking I'd collect an array of either the GIMPLE_CONDs,
or perhaps more usefully the edges between the CONDs and
the branches that contribute to the lower (and maybe also upper)
bounds.

The only other way to do it that I can think of is to recreate
the same process Ranger uses, except outside of it (including
all the computation and range propagation).

>> Thanks
>> Martin
>>
>> PS I'm assuming -O0 for the above test case where the m + n
>> expression is a sum of two PHIs.  With -O1 and higher some of
>> the integer conditionals end up transformed into MAX_EXPRs so
>> it will likely need to be handled differently or I may not be
>> able to capture all the conditions reliably.  I don't know how
>> much that might compromise the result.
>>
> Within ranger is is irrelevant whether its from a MAX or a condition.
> 
>    <bb 3> [local count: 574129753]:
>    _5 = MAX_EXPR <n_6(D), 4>;
>    _7 = MAX_EXPR <m_4(D), 3>;
>    _1 = _5 + _7;
> 
> _7 generates a range of [3, +INF] based on range-ops knowledge of how 
> MAX works.
> 
> In both cases, for m_3 above and _7, the range of [3, +INF] is generated 
> at the definition point... One is a PHI which includes some CFG 
> propagation to retrieve the argument values and perform the calculation, 
> and  _7 which is much simpler.. its just the global characteristic of 
> the statement calculated by range-ops where the LHS is the unknown in 
> the equation.  Ultimately, both ranges are created at the definition 
> point of the ssa_name  _7 or m_3.

Understood.

> 
> The question is what precisely do you want to do with the IL  and what 
> do you want to point at?  Optimization makes mapping things back to the 
> original IL problematic to be sure, and as you can see with the _7, even 
> the symbolic name can become lost or changed.

Right.  To print the conditional expression I expand each SSA_NAME
to its definition (variable, function call, or expressions like *p).
There's some loss of accuracy in the process so the result is not
a perfect reflection of the original source code.  Some things are
uglier than others.  But printing the expanded expressions is just
one possibility and it may not be best.  Just pointing to
the GIMPLE_CONDs and indicating which branch, when taken, leads
to the offending statement might be a simpler alternative.

> 
> GORI can be utilized to tell you whether a range is generated on an edge 
> for any specific name, but it depends on what you want to do with it. 
> There is currently no facility to ask which particular statement caused 
> the range to be created, mostly because there hasn't been a need, and 
> also because it is usually the result of a string of operations.   Given:
> 
> a = m + 10
> if (m > 10 && m < 100)
>      foo (a)
> 
> we see:
> 
>      <bb 2> :
>      a_5 = m_4(D) + 10;
>      m.0_1 = (unsigned int) m_4(D);
>      _2 = m.0_1 + 4294967285;
>      if (_2 <= 88)
>        goto <bb 3>; [INV]
>      else
>        goto <bb 4>; [INV]
> 
> a_5 : int [-2147483638, +INF]
> 2->3  (T) m.0_1 :       unsigned int [11, 99]
> 2->3  (T) m_4(D) :      int [11, 99]
> 2->3  (T) a_5 :         int [21, 109]
> 2->4  (F) m.0_1 :       unsigned int [0, 10][100, +INF]
> 2->4  (F) m_4(D) :      int [-INF, 10][100, +INF]
> 2->4  (F) a_5 :         int [-2147483638, 20][110, +INF]
> 
> =========== BB 3 ============
> a_5     int [21, 109]
> 
> We produce a range of [21, 109] for a_5,  but which statement would we 
> point to as the "defining" statement for that range?  (_2 <= 88) isn't 
> very useful.  a_5 is never used in a condition, but based on the reduced 
> range of m_4 we can recalculate a_5 on that path to produce that 
> value... but there is no good single thing to point to.

Hmm, yes, this could make the result even more detached from
the source.

> 
> The condition can be arbitrarily complex as well:
> 
> if we change the condition to:
> 
>    if ((m > 10 && m < 100) || m == 200)
>      foo (a);
> 
>      a_8 = m_7(D) + 10;
>      m.0_1 = (unsigned int) m_7(D);
>      _2 = m.0_1 + 4294967285;
>      _3 = _2 <= 88;
>      _4 = m_7(D) == 200;
>      _5 = _3 | _4;
>      if (_5 != 0)
>        goto <bb 3>; [INV]
>      else
>        goto <bb 4>; [INV]
> 
> a_8 : int [-2147483638, +INF]
> 2->3  (T) m.0_1 :       unsigned int [11, 99][200, 200]
> 2->3  (T) m_7(D) :      int [11, 99][200, 200]
> 2->3  (T) a_8 :         int [21, 109][210, 210]
> 2->4  (F) m.0_1 :       unsigned int [0, 10][100, 199][201, +INF]
> 2->4  (F) m_7(D) :      int [-INF, 10][100, 199][201, +INF]
> 2->4  (F) a_8 :         int [-2147483638, 20][110, 209][211, +INF]
> 
> =========== BB 3 ============
> a_8     int [21, 109][210, 210]
> 
> Now the condition that causes this range is a string of expressions that 
> all combine to produce the range, again, none of which actually utilize 
> a_8.   GORI uses range-ops to solve the equation from the bottom of the 
> block upwards until it has a result for m_7,  and then recalculates a_8 
> based on that.
> 
> We could produce a list of the ssa_names which are evaluated on each 
> edge to produce a range.  In the latter case, the range of a_8 is 
> produced by evaluating _5, _3, _4, m_7, _2, m.0_1, m_7, and finally a_8.
> 
> 
> So I think the long answer to your question is no, ranger probably isn't 
> going to provide a quick pointer to the information you are looking for. 
>     However, its not clear to me precisely what you are looking for. 
> GORI can provide lots of information about whether ranges are created or 
> not from each basic block, and there is a fair amount of dependency 
> information available about which names go into a calucaltion.  Its also 
> good at seeing thru different combinations of expressions. The engine 
> could also be repurposed, but to delve into the details of each 
> low-level range operation in such a way to produce useful high-level 
> information isn't clear to me how that would work.
> 
> You could reverse engineer an expression from the resulting range, and 
> then point to the source statements from the aggregate of the line 
> number info over all ssa_names definitions used in the calculation by 
> GORI across the various blocks in the dominators, but I can see how that 
> could quickly become verbose. Probably not that useful unless is was 
> limited and some mechanism for combining source lines from different 
> blocks in a meaningful way.
> 
> I'm not familiar with how much useful info the line-info has, nor how 
> much "noise" this would produce.  I would expect this to rapidly 
> degenerate and become confusing with missing information as the control 
> flow or optimizations increase.  Perhaps it could be limited to just 
> simple cases, if they could be easily identified.
> 

These are valid concerns that might in the end spell doom for
the whole idea.  I'm at a very early stage to have a sense of
the extent of some of these problems.

I do have a couple of proof-of-concept implementations of
the general idea (sans ranges) so I have some sense of what
to expect.  Both are far from ideal but in light of the issues
we have discussed recently having something seems better than
nothing at all.

The ideal goal I think is to produce output similar to what our
static analyzer puts out.  For instance, instead of printing just:

warning: ‘v’ may be used uninitialized in this function 
[-Wmaybe-uninitialized]

I'd like to print this for the test:

/src/gcc/master/gcc/testsuite/gcc.dg/uninit-pred-2_b.c:26:5: warning: 
use of uninitialized value ‘v’ [CWE-457] 
[-Wanalyzer-use-of-uninitialized-value]
    26 |     blah(v); /* { dg-warning "uninitialized" "real 
uninitialized var warning" } */
       |     ^~~~~~~
   ‘foo’: events 1-5
     |
     |   13 |   if (n)
     |      |      ^
     |      |      |
     |      |      (1) following ‘false’ branch (when ‘n == 0’)...
     |......
     |   19 |   if (m)
     |      |      ~
     |      |      |
     |      |      (2) ...to here
     |......
     |   25 |   if (!flag)
     |      |      ~
     |      |      |
     |      |      (3) following ‘true’ branch (when ‘flag == 0’)...
     |   26 |     blah(v); /* { dg-warning "uninitialized" "real 
uninitialized var warning" } */
     |      |     ~~~~~~~
     |      |     |
     |      |     (4) ...to here
     |      |     (5) use of uninitialized value ‘v’ here
     |

I can come close to this for simple code that doesn't involve
ranges (like the offsets or the size in a memcpy() call).  My
biggest challenge at the moment is getting the conditions that
ranges are derived from in code with nontrivial logic.  To get
at those it seems like I would have to redo all the same work
that Ranger does.

Thanks again!

Martin