[llvm-dev] ConstantRange modelling precision?

Roman Lebedev via llvm-dev llvm-dev at lists.llvm.org
Sun Dec 1 14:52:23 PST 2019


This question has come up in https://reviews.llvm.org/D70043
There, i'm teaching ConstantRange how no-wrap flags affect
the range of `mul` instruction, with end goal of exploiting
this in LVI/CVP.

There are certain combinations of ranges and no-wrap flags
that result in always-overflowing `mul`. For example,
`mul nuw nsw i4 [2,0), [4,0)` always overflows:
so for such ranges the ideal answer is `empty set`;
although it wouldn't be incorrect to return a more pessimistic
range (e.g. full-set) that contains more than the ideal result.

The problem is, unlike the case of `add`, where intersection
between plain `add` range and `saturating-[un?]signed-add`
range already returns empty set in similar cases, here we 'need'
to model it explicitly. (as it is seen in the patch, the modelling
is reasonably straight-forward)

As it was pointed out in the review, currently, LVI does not
make use of empty-sets, and maps them to `overdefined`:

So the question is: considering the fact that LVI would not
make use of such empty-set knowledge, does that mean we
shouldn't bother doing that extra analysis in ConstantRange,
thus avoiding the compile time cost of said modelling?

Right now i'm thinking we *should* be doing it, because:
* Wouldn't `overdefined` lattice result in LVI giving up
   on the users of said value, as opposed to keeping
   propagating "incorrect" range, and thus incurring maybe
   more compile time cost, than we would have spent
   proving that the result is empty-set?
* Likely LVI will make use of the knowledge later on?
* Are there other users of ConstantRange
  that may want this precision?


More information about the llvm-dev mailing list