vrp

Project Infrastructure LLVM Dev List Archives
1

Hello,

I am trying to figure out, what vrp propagation does in llvm. I tried this program:
#include <stdio.h>

int main() {
int s = 0;
int j = 0;
for (int i = 0; i < 100; i++) {
j = j+i+1;
s+=j;
}
return (s+j);
}

And got this under optimized version ( I don’t want everything to be eliminated)
define i32 @main() #0 {
entry:
br label %for.body

for.body: ; preds = %for.body, %entry
%i.03 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
%s.02 = phi i32 [ 0, %entry ], [ %add2, %for.body ]
%j.01 = phi i32 [ 0, %entry ], [ %add1, %for.body ]
%add = add nsw i32 %j.01, %i.03
%add1 = add nsw i32 %add, 1
%add2 = add nsw i32 %s.02, %add1
%inc = add nsw i32 %i.03, 1
%cmp = icmp slt i32 %i.03, 99
br i1 %cmp, label %for.body, label %for.end

for.end: ; preds = %for.body
%add3 = add nsw i32 %add2, %add1
ret i32 %add3
}

the value range pass was not able to determine any size, even of the induction variable, is it a correct behavior?

2

I am trying to print it like this (maybe here is smth wrong?)

LazyValueInfo &LV = getAnalysis().getLVI();
DominatorTree &DT = getAnalysis().getDomTree();
LV.printLVI(F, DT, llvm::outs());
for (BasicBlock &BB : F) {
for (Instruction &I : BB) {
if (Value* v = dyn_cast(&I))
if (v->getType()->isIntegerTy()) {
ConstantRange r = LV.getConstantRange(v, &BB, &I);
I.dump();
printf(“LOWER VALUE : %llu\n”,r.getLower().getRawData());
printf(“UPPER VALUE : %llu\n”,r.getUpper().getRawData());
}
}
}

3

I am trying to print it like this (maybe here is smth wrong?)

    LazyValueInfo &LV = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
    DominatorTree &DT =
getAnalysis<DominatorTreeWrapperPass>().getDomTree();
    LV.printLVI(F, DT, llvm::outs());

The value analysis in llvm is lazy (hence, LVI), so you're trying to
print an empty cache, I guess.

    for (BasicBlock &BB : F) {
      for (Instruction &I : BB) {
    if (Value* v = dyn_cast<Value>(&I))
      if (v->getType()->isIntegerTy()) {
        ConstantRange r = LV.getConstantRange(v, &BB, &I);
        I.dump();
        printf("LOWER VALUE : %llu\n",r.getLower().getRawData());
        printf("UPPER VALUE : %llu\n",r.getUpper().getRawData());
      }
      }

About your other question, "the value range pass was not able to
determine any size, even of the induction variable, is it a correct
behavior?". Yes, returning a conservative answer is always correct,
but not optimal.

As reference, a more sophisticated range analysis finds the following
ranges for your IR:

[0, +inf] %i.03 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
[0, +inf] %s.02 = phi i32 [ 0, %entry ], [ %add2, %for.body ]
[0, +inf] %j.01 = phi i32 [ 0, %entry ], [ %add1, %for.body ]
[0, +inf] %add = add nsw i32 %j.01, %i.03
[1, +inf] %add1 = add nsw i32 %add, 1
[1, +inf] %add2 = add nsw i32 %s.02, %add1
[1, +inf] %inc = add nsw i32 %i.03, 1
[2, +inf] %add3 = add nsw i32 %add2, %add1

4

So, it is not supported to determine by this instruction : %cmp = icmp slt i32 %i.03, 99,

that %i.03 = phi i32 [ 0, %entry ], [ %inc, %for.body ] has
a range [0, 99]?

And what is then a correct way to get such an info, that you sent ( with more specified ranges)? …seems that appropriate method for it is not in LazyValueInfo class.

5

I am primarily interested in phi nodes and their induction variables, in ValueTracking file there is an analysis of them, but if the upper bound is inf, it is not working?

6

When I am printing, I call getConstantRange and this method internally calls : gerValueInBlock()

LVILatticeVal LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,

Instruction *CxtI) {

DEBUG(dbgs() << “LVI Getting block end value " << *V << " at '”

<< BB->getName() << “'\n”);

assert(BlockValueStack.empty() && BlockValueSet.empty());

if (!hasBlockValue(V, BB)) {

pushBlockValue(std::make_pair(BB, V));

solve();

}

<…>

}

which internally inserts the pair, so it seems that the informations, that I am printing , is in cache.

7

Maybe there is a concrete document or paper about VRP in llvm (what it exactly has)? After studying the code, seems that the answer is : llvm can’t detect borders with help of cmp statements but I still want to be sure.

8

To the best of my knowledge, LVI in llvm tries to emulate a standard
fixpoint algorithm on a meet semilattice ( see, e.g.

for details, on a bit-by-bit basis).
I haven't debugged your testcase but if you have something that should
be caught by VRP (but it's not), you may consider reporting a bug at
bugs.llvm.org

Thanks,