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.
> 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.Duncan these problems can definitely be solved. In your example, we would need to have avoided giving X the wrong interval value in the first place. The problem with overflow isn't that it makes sound analysis impossible, it's that it can kill precision. Here's GCC's value range propagation module, which is definitely intended to be sound since it feeds the optimizer: http://gcc.gnu.org/svn/gcc/trunk/gcc/tree-vrp.c John
Hi John,>> 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. > > Duncan these problems can definitely be solved.I didn't say it couldn't be solved, I was just pointing out that Victor probably made a wrong statement. Ciao, Duncan.