Hi, I have some questions on Loop Interchange and what I think maybe a missing case?
I was observing this benchmark comparing llvm/clang to gcc on the BPi-F3, an in-order cpu.
I surmised from the assembly that gcc was able to perform loop-interchange on this nested for loop, which causes a significant performance gain since it can avoid doing a load/store every iteration of the inner loop.
for (k=0; k<1000; k++) {
for (i = n-1; i >= 0; i--) {
y[i] += x[i];
}
}
Full code here: llvm-test-suite/SingleSource/Benchmarks/Shootout/ary3.c at main · llvm/llvm-test-suite · GitHub
I understand that loop-interchange isn’t enabled by default, but I wanted to try running it on the code for curiosity’s sake.
I executed this command to get the LLVM IR prior to the loop-vectorizer pass
../bin/clang --target=riscv64-linux-gnu \
-march=rva22u64_v -mcpu=spacemit-x60 -O3 \
--sysroot=/usr/riscv64-linux-gnu \
-mllvm -print-before=loop-vectorize \
-mllvm -print-module-scope \
-S -emit-llvm ary3.c -o ary3_prevec.ll
and then this command to get the debug output from loop-interchange and DependenceAnalysis
../bin/opt -passes='loop-interchange' \
-mtriple=riscv64 -mattr=+v \
-debug-only=loop-interchange,da \
-S ary3_prevec.ll -o ary3_interchange.ll 2> interchange_log.txt
I gleaned from the debug message was that the LoopInterchange pass made this dependency matrix: * =
Dependency matrix before interchange:
* =
...
Failed interchange InnerLoopId = 1 and OuterLoopId = 0 due to dependence
Cannot prove legality, not interchanging loops 'for.cond11.preheader.us' and 'for.body14.us'
I trace this to the code where the dependency matrix is populated populateDependencyMatrix. My takeaway is that the outter loop is categorized as DVEntry::LE, so the direction is treated as ’ * '?
for (unsigned II = 1; II <= Levels; ++II) {
// `DVEntry::LE` is converted to `*`. This is because `LE` means `<`
// or `=`, for which we don't have an equivalent representation, so
// that the conservative approximation is necessary. The same goes for
// `DVEntry::GE`.
// TODO: Use of fine-grained expressions allows for more accurate
// analysis.
unsigned Dir = D->getDirection(II);
if (Dir == Dependence::DVEntry::LT)
Direction = '<';
else if (Dir == Dependence::DVEntry::GT)
Direction = '>';
else if (Dir == Dependence::DVEntry::EQ)
Direction = '=';
else
Direction = '*';
Dep.push_back(Direction);
}
I also noticed that to check for legality, function isLexicographicallyPositive is called, which I believe would return false since the first Direction is an ’ * ’ instead of ‘<’. This would subsequently cause isLegalToInterChangeLoops to return false.
static std::optional<bool>
isLexicographicallyPositive(ArrayRef<char> DV, unsigned Begin, unsigned End) {
for (unsigned char Direction : DV.slice(Begin, End - Begin)) {
if (Direction == '<')
return true;
if (Direction == '>' || Direction == '*')
return false;
}
return std::nullopt;
}
Questions
- Is this case a known limitation of the current LoopInterchange pass?
- In the dependency matrix, I’m quite lost as to why the outer loop would be categorized as a
DVEntry::LE, instead ofDVEntry::LT. - How trivial of a fix would this be? My very naive assumption is that it wouldn’t be too difficult to tell this pass is legal in this case since the outer induction variable
kis not used in the inner loop.
Apologies if this was too verbose. If these questions are too broad, I’d appreciate any links to existing documentation or RFCs I should read. Thanks for your time!
