[llvm-dev] Finding Reduction Variables in a Loop

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

[llvm-dev] Finding Reduction Variables in a Loop

Bruce Hoult via llvm-dev
Hello everyone,

I'm trying to find reduction variables in a loop and I have a couple of questions about it.

Is it necessary that a reduction variable should be associated with a Phi node?

For my purpose, I tried using isReductionPHI() from LoopUtils.cpp (that is used by LoopVectorizer) for a toy C program (find below) that has a clear reduction variable but it still returns false.

// Toy program where "sum" is the reduction variable.
#include <stdio.h>
int main(int argc, char const *argv[])
{
	int sum = 0, a[100], i;

	for(i = 0; i < 100; i++)
		sum += a[i];

	printf("sum: %d\n", sum);
	return 0;
}
I generated LLVM IR (toy_reduction.ll) for the above program and then applied mem2reg on top of it (toy_reduction_mem2reg.ll). I have implemented a toy analysis pass which prints the phi nodes that are associated with reduction variables which is as under.

void checkRedux(Loop *L) {
	for (BasicBlock *BB : L->getBlocks()) {
		for (Instruction &I : *BB) {
			if (auto *Phi = dyn_cast<PHINode>(&I)) {
				errs() << *Phi << "\n";
				RecurrenceDescriptor RedDes;
		        if (RecurrenceDescriptor::isReductionPHI(Phi, L, RedDes)) {
		        	errs() << "Found reduction object\n";
		        	errs() << *Phi << "\n";
		        }
			}
		}
	}
} 
bool runOnFunction(Function &F) override {
	auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
	for(Loop *L : *LI){
			checkRedux(L);
	}
	return false;
}

However, for the input file toy_reduction_mem2reg.ll, isReductionPHI() returns false every time the control reaches there thereby declaring that there are no reduction variables when clearly there is one (sum).

Find below a snippet of the LLVM IR after applying mem2reg.

define i32 @main(i32 %argc, i8** %argv) #0 {
entry:
  %a = alloca [100 x i32], align 16
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %sum.0 = phi i32 [ 0, %entry ], [ %add, %for.inc ]
  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
  %cmp = icmp slt i32 %i.0, 100
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %idxprom = sext i32 %i.0 to i64
  %arrayidx = getelementptr inbounds [100 x i32], [100 x i32]* %a, i64 0, i64 %idxprom
  %0 = load i32, i32* %arrayidx, align 4
  %add = add nsw i32 %sum.0, %0
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %inc = add nsw i32 %i.0, 1
  br label %for.cond

for.end:                                          ; preds = %for.cond
  %call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([9 x i8], [9 x i8]* @.str, i32 0, i32 0), i32 %sum.0)
  ret i32 0
}

declare i32 @printf(i8*, ...) #
Do I need to run some passes other than mem2reg to obtain the desired result?

Is there a better way of finding reduction variables in LLVM?


Thank you.



Regards,
Malhar



_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev