Querying loop invariance on a per-level basis

IR & Optimizations Loop Optimizations
1

I want to be able to determine when an outer loop in a nest doesn’t have any operations that mutate an address computed in an inner loop. For example:

for (int n=0; n < N; n++)
    for (int i=0; i < i; i++)
        a[i] += 1;

a[i] is variant with respect to the inner loop, but not the outer loop. However, if I use SCEV to query if the computed address a[i] is invariant to the loop object of the outer loop, it will return false, because it considers the entire loop nest, to which it’s obviously not invariant.

Is there any easy way I can do this, or am I looking at traversing use-def chains manually?

2

ScalarEvolution::isLoopInvariant takes the loop for which to check invariance as argument (LLVM: llvm::ScalarEvolution Class Reference).

You can just pass in the inner loop to check for invariance wrt to the inner loop. If you want to check for all loops individually in a loop nest, the Loop object provides functions to get all child loops or walk upwards to the parent loop.

4

This is what I’ve been trying but I still find that the address is marked as variant wrt to the outer loop.

My code currently is simply:

const SCEV *Scev = SE.getSCEV(Ptr);
for (auto L: LI.getLoopsInPreorder()){
    if (SE.isLoopInvariant(Scev, L))
        return true;
    return false;
}

And this always returns false when run on the example code.

5

I don’t think there’s an existing helper for the exact property you’re looking for, no. You should be able to write code to analyze the SCEV expression yourself, though. Start with something like auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Ptr));, and then check that the base of the AddRec is invariant.

6

Thanks for the advice. I’m not really too familiar with how SCEV works though, could you elaborate on your idea a little more? I was just going to follow the use-def chain and see if any (non-cast or comparison) instructions fall inside basic blocks that belong to the outer loop.

Edit: Nevermind, just realised my idea here would fail for the trivial case of

for (int i=0; i < n; i++)
   for(int j=0; j < n; j++)
      a[i][j]+=1;
7

When you call SE.getSCEV(Ptr), that returns a SCEV expression. If you call it on the pointer a[i] in your example, it will be a SCEVAddRecExpr. If you examine that SCEVAddRecExpr (e.g. calling dump() on it), you’ll find the loop will be the inner loop, the first operand (the base) will be “a”, and the second operand (the increment) will be 1.

You can then query SCEV to see that “a” is invariant. So that’s completely specifies the relevant properties of the pointer.

The block comment at the top of LLVM: lib/Analysis/ScalarEvolution.cpp Source File has some generally useful information.

1 Like
8

Ah, ok I see now! So by testing the invariance of the underlying address the inner loop accesses that tells us the same thing.

Thanks!

9

Implemented this function now and basic test cases indicate it works. Posting here for anyone who might stumble across this thread looking for the same thing!

Small problem with my implementation here is that the helper getUnderlyingObject which I’m relying on will just return its argument if it finds an instruction that isn’t a GEP, phi or call, which isn’t ideal. I handled loads of pointers manually but if its say an inttoptr or something else I haven’t considered I’m just giving up for now, which works well enough for me. Modify to your own needs!

bool isVariantAtAllLevels(Value *Ptr, Loop *ParentLoop, LoopInfo &LI, ScalarEvolution &SE){
    Loop *L = ParentLoop;
    Value *NextValue = Ptr;
    Value *PreviousValue = nullptr;
    while ((L = L->getParentLoop())) {
        bool nest_level_is_variant = false;
        for (; !nest_level_is_variant ; NextValue = getUnderlyingObject(NextValue, 1)){
            //getUnderlyingObject is giving up on something that isn't a load so we're giving up too
            if (NextValue == PreviousValue) return false;
            PreviousValue = NextValue;

            //we haven't worked through the whole nest yet but the underlying
            //value is already a function argument or global variable, must be invariant
            if (!isa<Instruction>(NextValue)) return false;

            Instruction *NextInstruction = reinterpret_cast<Instruction *>(NextValue);

            //found instruction on the ptr at this specific loop, check if its invariant
            //if it is, keep stripping back instructions
            if (L->contains(NextInstruction) && L == LI.getLoopFor(NextInstruction->getParent())){
                const SCEV *Scev = SE.getSCEV(NextInstruction);
                if (!SE.isLoopInvariant(Scev, L)) nest_level_is_variant = true;
            }
            //found instruction outside this level before we found any instructions within it,
            //pointer is invariant w.r.t this level
            else if (!L->contains(NextInstruction)) return false;

            if (auto *Load = dyn_cast<LoadInst>(NextValue)) NextValue = Load->getPointerOperand();
        }
    }
    return true;
}