[llvm-dev] Finding Reduction Variables in a Loop

[Malhar Thakkar 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


ᐧ
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180621/b97f11f4/attachment-0001.html>