LLVM Discussion Forums

How to get a bound of a loop

Hi experts,
I’m about to get a bound of a loop to get detail information like initial, final value and so on. And I found LoopBounds seems competent. However, it can’t be get through following code:

class myPass: public LoopPass
{
public:
    void getAnalysisUsage(AnalysisUsage &AU) const override 
    {
        AU.addRequired<ScalarEvolutionWrapperPass>();
    }

    bool runOnLoop(Loop *lp, LPPassManager &LPM) override
    {
        ScalarEvolution *se = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
        Optional< Loop::LoopBounds > bounds = lp->getBounds(*se);
        if(! bounds.hasValue())
                return;
          ...
    }

}
where bounds.hasValue() always return false. and I added "-scalar-evolution " option when running. Did I do anything wrong or forget anything?

Thanks in advance.

Maybe scalar evolution is not able to find the bound of the loop. Can you show the input IR?

(Btw. people might answer faster if you ask on llvm-dev@lists.llvm.org )

Hi, jdoerfert
Thanks for replying. The IR is as follow:
; ModuleID = ‘specialty.c’
source_filename = “specialty.c”
target datalayout = “e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128”
target triple = “x86_64-unknown-linux-gnu”

@a = dso_local global [6 x i32] [i32 1, i32 2, i32 3, i32 4, i32 5, i32 6], align 16
@b = dso_local global [6 x i32] [i32 7, i32 8, i32 9, i32 10, i32 11, i32 12], align 16

; Function Attrs: noinline nounwind optnone uwtable
define dso_local void @test3b(i32 %n) #0 {
entry:
  %n.addr = alloca i32, align 4
  %saved_stack = alloca i8*, align 8
  %__vla_expr0 = alloca i64, align 8
  %i = alloca i32, align 4
  %j = alloca i32, align 4
  store volatile i32 %n, i32* %n.addr, align 4
  %0 = load volatile i32, i32* %n.addr, align 4
  %1 = zext i32 %0 to i64
  %2 = call i8* @llvm.stacksave()
  store i8* %2, i8** %saved_stack, align 8
  %vla = alloca i32, i64 %1, align 16
  store i64 %1, i64* %__vla_expr0, align 8
  store volatile i32 0, i32* %i, align 4
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %3 = load volatile i32, i32* %i, align 4
  %4 = load volatile i32, i32* %n.addr, align 4
  %cmp = icmp slt i32 %3, %4
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %5 = load volatile i32, i32* %i, align 4
  %add = add nsw i32 %5, 1
  %6 = load volatile i32, i32* %i, align 4
  %idxprom = sext i32 %6 to i64
  %arrayidx = getelementptr inbounds i32, i32* %vla, i64 %idxprom
  store volatile i32 %add, i32* %arrayidx, align 4
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %7 = load volatile i32, i32* %i, align 4
  %inc = add nsw i32 %7, 1
  store volatile i32 %inc, i32* %i, align 4
  br label %for.cond

for.end:                                          ; preds = %for.cond
  store volatile i32 0, i32* %j, align 4
  br label %while.cond

while.cond:                                       ; preds = %while.body, %for.end
  %8 = load volatile i32, i32* %j, align 4
  %9 = load volatile i32, i32* %n.addr, align 4
  %cmp1 = icmp slt i32 %8, %9
  br i1 %cmp1, label %while.body, label %while.end

while.body:                                       ; preds = %while.cond
  %10 = load volatile i32, i32* %j, align 4
  %mul = mul nsw i32 %10, 2
  %11 = load volatile i32, i32* %j, align 4
  %idxprom2 = sext i32 %11 to i64
  %arrayidx3 = getelementptr inbounds i32, i32* %vla, i64 %idxprom2
  %12 = load volatile i32, i32* %arrayidx3, align 4
  %add4 = add nsw i32 %12, %mul
  store volatile i32 %add4, i32* %arrayidx3, align 4
  %13 = load volatile i32, i32* %j, align 4
  %inc5 = add nsw i32 %13, 1
  store volatile i32 %inc5, i32* %j, align 4
  br label %while.cond

while.end:                                        ; preds = %while.cond
  %14 = load volatile i32, i32* %n.addr, align 4
  %sub = sub nsw i32 %14, 1
  store volatile i32 %sub, i32* %j, align 4
  br label %while.cond6

while.cond6:                                      ; preds = %if.end, %while.end
  br label %while.body7

while.body7:                                      ; preds = %while.cond6
  %15 = load volatile i32, i32* %j, align 4
  %idxprom8 = sext i32 %15 to i64
  %arrayidx9 = getelementptr inbounds i32, i32* %vla, i64 %idxprom8
  %16 = load volatile i32, i32* %arrayidx9, align 4
  %mul10 = mul nsw i32 %16, 2
  store volatile i32 %mul10, i32* %arrayidx9, align 4
  %17 = load volatile i32, i32* %j, align 4
  %dec = add nsw i32 %17, -1
  store volatile i32 %dec, i32* %j, align 4
  %cmp11 = icmp slt i32 %dec, 0
  br i1 %cmp11, label %if.then, label %if.end

if.then:                                          ; preds = %while.body7
  br label %while.end12

if.end:                                           ; preds = %while.body7
  br label %while.cond6

while.end12:                                      ; preds = %if.then
  %18 = load i8*, i8** %saved_stack, align 8
  call void @llvm.stackrestore(i8* %18)
  ret void
}

; Function Attrs: nounwind
declare i8* @llvm.stacksave() #1

; Function Attrs: nounwind
declare void @llvm.stackrestore(i8*) #1

; Function Attrs: noinline nounwind optnone uwtable
define dso_local i32 @main(i32 %argc, i8** %argv) #0 {
entry:
  %retval = alloca i32, align 4
  %argc.addr = alloca i32, align 4
  %argv.addr = alloca i8**, align 8
  store i32 0, i32* %retval, align 4
  store i32 %argc, i32* %argc.addr, align 4
  store i8** %argv, i8*** %argv.addr, align 8
  call void @test3b(i32 10)
  ret i32 0
}

attributes #0 = { noinline nounwind optnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { nounwind }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{!"clang version 10.0.0 (trunk 375208)"}

Run -mem2reg before your pass.

Thanks, I tried to access the website, but unfortunatly, it either cannot be found or was transferred to http://lists.llvm.org/mailman/listinfo.

Do you get the loop bounds you are looking for now?


I don’t understand. What website?

You can register for the llvm-dev mailing list here:
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Once on it you can send emails to llvm-dev@lists.llvm.org.
You can probably send the email without registering for the mailing list but then a moderator needs to unblock your mail.

do you mean in the instruction? like
opt -load dfg.so -mem2reg -scalar-evolution -dfg …/specialty.bc ? where dfg is my pass.
it’s vain, I tried :disappointed:

you did create the IR without an -O{1,2,3} flag or with -O0, correct? Remove the optnone attribute from the IR so passes will actually do something and not skip the functions.

What should I do besizes adding a -O2 to the instruction? I mean how to remove the optnone attribute from the IR? Could you specify it?

Either you create the IR with O1 or higher (clang -O1 ...), or you strip the optnone manually (see below).
Another option is to use the script you find here: llvm-project/polly/test/create_ll.sh.
Run create_ll.sh ../speciality.c to get a ../speciality.ll which is already “pre-processed” and can be used directly: opt -load dfg.so -scalar-evolution -dfg …/specialty.ll

Manual stripping:
opt -S …/specialty.bc -o …/specialty.ll
sed -i".tmp" '/optnone/d'
opt -load dfg.so -mem2reg -scalar-evolution -dfg …/specialty.ll

Disclaimer: I haven’t tested the above.

both ways are tried, but neither works.
I think there are more errors to be solved. Anyway, thanks again. I’m going to leave for vacation for a week for lunar new year. See you~

I traced the program, the reason is associated to the bold line below

/// Get the latch condition instruction.
static ICmpInst *getLatchCmpInst(const Loop &L) {
if (BasicBlock *Latch = L.getLoopLatch())
if (BranchInst *BI = dyn_cast_or_null(Latch->getTerminator()))
if (BI->isConditional())
return dyn_cast(BI->getCondition());

return nullptr;
}

isn’t my loop conditional?

I think I’ve solved problem, at least to some extent.
Via debugging and tracing, I finally know what the ScalarEvolutionWrapperPass requires.
It demonds:
1 the code must be optimized so that the Loop latch which refers to the only node jumping to the head of the loop would integrated into for.body, rather than in the for.inc block and the last br instruction has only one arguement.
2 An instruction phi must exist in the latch block. To realize this, -mem2reg is needed in the opt command.
However, it seems in some cases, -mem2reg doesn’t work, I mean it may not help to generate phi node in IR codes. Besides, -O{1, 2, 3} may eliminate a whole loop. To solve it, I used -O0 -Xclang -disable-O0-optnone to prevent “optnone” being in IR codes which blocks other optimizes like -mem2reg.

Acturally, I rewrote bounds class to cope with the above issues.
The key junction is the function

/// Get the latch condition instruction.
static ICmpInst *getLatchCmpInst(const Loop &L) {
if (BasicBlock *Latch = L.getLoopLatch())
if (BranchInst *BI = dyn_cast_or_null(Latch->getTerminator()))
if (BI->isConditional())
return dyn_cast(BI->getCondition());

return nullptr;
}

it automately finds Latch, but the Latch may not conform to the demand. So I improved it as following:

static ICmpInst *myGetLatchCmpInst(BasicBlock *Latch)
{
ICmpInst *CmpInst = nullptr;
if (BranchInst *BI = dyn_cast_or_null(Latch->getTerminator()))
if (BI->isConditional())
CmpInst = dyn_cast(BI->getCondition());
return CmpInst;
}

Of course, anywhere calling it need to be modified. the block Latch I repaced with BasicBlock *Header = lp.getHeader(); //lp is a loop

BTW, who can tell me how to solve the problem of no phi node?

I think it was because I added “volatile” keywords in my codes :flushed: