[LLVMdev] GSoC - Range Analysis

[Duncan Sands]

Hi Victor,

>  > one of the big problems with Douglas's original range analysis was that
>  > it couldn't handle modulo arithmetic.
>
> We still have this problem. Jorge Navas, who is using our analysis, is
> working on an implementation that deals with wrapping arithmetics, but
> we did not have access to his code yet.

can you please clarify whether the pass only looks at operations with the
nsw flag (and bails out on others), or just assumes that there is no wrapping
behaviour anywhere.  It used to just assume that nothing wrapped, which made
all stated results about bit shrinking, dead variables found etc pointless
since they were based on an incorrect analysis.

>  > An analysis that is not sound with respect to the original C/C++ semantics
>  > would be of little use to anyone.
>
> You can use our analysis to remove overflows. If we output that a variable
> is bound to the range [c1, c2], where c1 > -inf, and c2 < +inf, then you
> are guaranteed to be inside these bounds.

Is this really true?  For example, suppose you know that X is in the range
[1, +inf], and now you calculate Y = 1 / X, then you get that Y is in the
range [0, 1].  But there is no guarantee that Y is really in that range:
since X might have overflowed it might for example be equal to -1, in which
case Y would be equal to -1 too, outside the range [0, 1].  In short, I doubt
you can conclude that a variable Y is really in a range [c1, c2] just from the
information that c1 > -inf and c2 < +inf.  I think you also need to look at the
history of how you got there.

Ciao, Duncan.