LazyValueInfo vs ScalarEvolution

Project Infrastructure LLVM Dev List Archives
#1

Hi,

Both LazyValueInfo and ScalarEvolution can calculate a constant range for an LLVM Value.
I found that some times they do not agree, may be I interpreted them incorrectly

For example in the following IR:

bb85: ; preds = %bb85, %bb73
%tmp86 = phi i32 [ 1, %bb73 ], [ %tmp95, %bb85 ]
%tmp95 = add nsw i32 %tmp86, 1

%tmp96 = icmp slt i32 %tmp95, 20
br i1 %tmp96, label %bb85, label %bb97

LazyValueInfo give:

POP %tmp86 = phi i32 [ 1, %bb73 ], [ %tmp95, %bb85 ] in bb85 = constantrange<-2147483648, 20>

While ScalarEvolution give:

%tmp86 = phi i32 [ 1, %bb73 ], [ %tmp95, %bb85 ]
→ {1,+,1}<%bb85> U: [1,20) S: [1,20) Exits: 19 LoopDispositions: { %bb85: Computable, %bb73: Variant, %bb46: Variant }

In this example, the range of %tmp86 is <-2147483648, 20> from LazyValueInfo, but it is [1,20) from ScalarEvolution.

How can I interpret these results?
Is there a way to get [0, 20) for %tmp86 in LazyValueInfo?

Thanks
Hongbin

#2

Since they are different static analyses there's no reason to expect them to agree, but they should both be conservative. In other words, if you like you can compute the intersection of the two ConstantRanges and the result should still be an overapproximation of the values that will occur at run time.

John

#3

Thanks, maybe we could use ScalarEvolution in LazyValueInfo if it is available?

#4

This should be fairly easy to try, if you want to propose a patch and run some experiments. The question is whether the benefit in terms of improved optimization power is worth the compile-time cost. Also, the last time I looked, there seemed to be a fair amount of room for improvement in LVI and ConstantRange.

John

#5

Thanks, maybe we could use ScalarEvolution in LazyValueInfo if it is
available?

This should be fairly easy to try, if you want to propose a patch and run
some experiments. The question is whether the benefit in terms of improved
optimization power is worth the compile-time cost.

Ok

Also, the last time I looked, there seemed to be a fair amount of room for

improvement in LVI and ConstantRange.

Could you point some out?

Thanks
Hongbin

#6

Check out the TODO items in binaryAnd and BinaryOr in ConstantRange.cpp.

There are some missing cases in the switch in ConstantRange::binaryOp, such as xor and ashr.

Argh this is embarrassing, I have some unfinished work sitting in Phabricator that could use a helper if you have time to take a look:

https://reviews.llvm.org/D19859
https://reviews.llvm.org/D20669
https://reviews.llvm.org/D19867
https://reviews.llvm.org/D19559

John

#7

Also I should add that I strongly doubt that it will be acceptable to simply call ScalarEvolution's integer range analysis from LVI. The right answer is no doubt more nuanced and the actual experts in this stuff are here and hopefully they can chime in with opinions. Also, I am hoping to get together with a few people who care about LVI at the October dev meeting, you should join if you are going to attend.

John

#8

Also I should add that I strongly doubt that it will be acceptable to
simply call ScalarEvolution's integer range analysis from LVI. The right
answer is no doubt more nuanced and the actual experts in this stuff are
here and hopefully they can chime in with opinions.

It looks like in LazyValueInfoCache::solveBlockValuePHINode we only get the
upper bound of the PHINode in the above example in getEdgeValue.
Thus it generates range like constantrange<-2147483648 <(214)%20748-3648>,
20>.

In order to also get the lower bound, we need to prove the PN is is
monotonically increasing. And such code had been implemented in SCEV. Maybe
we could factor these code out and use them in both LVI and SCEV.

Also, I am hoping to get together with a few people who care about LVI at
the October dev meeting, you should join if you are going to attend.

Sure