This is an archive of the discontinued LLVM Phabricator instance.

Differential D101943

[LoopNest] Consider loop nest with inner loop guard using outer loop induction variable to be perfect
AbandonedPublic

Authored by Whitney on May 5 2021, 1:55 PM.

Details

Reviewers
bmahjour
Meinersbur
fhahn
sidbav
Summary

This patch allow more conditional branches to be considered as loop guard, and so more loop nests can be considered perfect.

Unable to select update an existing revision, but this is a continuation of https://reviews.llvm.org/D94717.
The original author sidbav has delegated this work to me.

Diff Detail

Unit TestsFailed

TimeTest
40 msx64 debian > LLVM.Analysis/LoopNestAnalysis::nests-with-lcssa.ll
80 msx64 windows > LLVM.Analysis/LoopNestAnalysis::nests-with-lcssa.ll

Event Timeline

Whitney created this revision.May 5 2021, 1:55 PM
Herald added a subscriber: hiraditya. · View Herald TranscriptMay 5 2021, 1:55 PM
Whitney requested review of this revision.May 5 2021, 1:55 PM
Herald added a subscriber: llvm-commits. · View Herald TranscriptMay 5 2021, 1:55 PM
Whitney abandoned this revision.May 5 2021, 1:58 PM

Found out how to update the original review.

Harbormaster completed remote builds in B102839: Diff 343174.May 5 2021, 3:15 PM

Revision Contents

PathSize
llvm/
include/
llvm/
Analysis/
8 lines
lib/
Analysis/
17 lines
8 lines
test/
Analysis/
LoopNestAnalysis/
67 lines
145 lines
unittests/
Analysis/
48 lines

Diff 343174

llvm/include/llvm/Analysis/LoopNestAnalysis.h

Show First 20 Lines • Show All 55 Lines • ▼ Show 20 Linespublic:
/// for(j) // loop at level 2 /// for(j) // loop at level 2
/// <code> /// <code>
/// for(k) // loop at level 3 /// for(k) // loop at level 3
/// \endcode /// \endcode
/// getMaxPerfectDepth(Loop_i) would return 2. /// getMaxPerfectDepth(Loop_i) would return 2.
static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE); static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE);
/// Recursivelly traverse all empty 'single successor' basic blocks of \p From /// Recursivelly traverse all empty 'single successor' basic blocks of \p From
/// (if there are any). Return the last basic block found or \p End if it was /// (if there are any). When \p CheckUniquePred is set to true, check if
/// reached during the search. /// each of the empty single successors has an unique predecessor. Return
/// the last basic block found or \p End if it was reached during the search.
static const BasicBlock &skipEmptyBlockUntil(const BasicBlock *From, static const BasicBlock &skipEmptyBlockUntil(const BasicBlock *From,
const BasicBlock *End); const BasicBlock *End,
bool CheckUniquePred = false);
/// Return the outermost loop in the loop nest. /// Return the outermost loop in the loop nest.
Loop &getOutermostLoop() const { return *Loops.front(); } Loop &getOutermostLoop() const { return *Loops.front(); }
/// Return the innermost loop in the loop nest if the nest has only one /// Return the innermost loop in the loop nest if the nest has only one
/// innermost loop, and a nullptr otherwise. /// innermost loop, and a nullptr otherwise.
/// Note: the innermost loop returned is not necessarily perfectly nested. /// Note: the innermost loop returned is not necessarily perfectly nested.
Loop *getInnermostLoop() const { Loop *getInnermostLoop() const {
▲ Show 20 Lines • Show All 105 Lines • Show Last 20 Lines

llvm/lib/Analysis/LoopInfo.cpp

Show All 14 Lines
#include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopInfo.h"
#include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/ScopeExit.h" #include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/IVDescriptors.h" #include "llvm/Analysis/IVDescriptors.h"
#include "llvm/Analysis/LoopInfoImpl.h" #include "llvm/Analysis/LoopInfoImpl.h"
#include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/LoopNestAnalysis.h"
#include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h" #include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h" #include "llvm/Analysis/ValueTracking.h"
#include "llvm/Config/llvm-config.h" #include "llvm/Config/llvm-config.h"
#include "llvm/IR/CFG.h" #include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h" #include "llvm/IR/Constants.h"
#include "llvm/IR/DebugLoc.h" #include "llvm/IR/DebugLoc.h"
▲ Show 20 Lines • Show All 344 Lines • ▼ Show 20 Lines if (!isRotatedForm())
return nullptr; return nullptr;
// Disallow loops with more than one unique exit block, as we do not verify // Disallow loops with more than one unique exit block, as we do not verify
// that GuardOtherSucc post dominates all exit blocks. // that GuardOtherSucc post dominates all exit blocks.
BasicBlock *ExitFromLatch = getUniqueExitBlock(); BasicBlock *ExitFromLatch = getUniqueExitBlock();
if (!ExitFromLatch) if (!ExitFromLatch)
return nullptr; return nullptr;
BasicBlock *ExitFromLatchSucc = ExitFromLatch->getUniqueSuccessor();
if (!ExitFromLatchSucc)
return nullptr;
BasicBlock *GuardBB = Preheader->getUniquePredecessor(); BasicBlock *GuardBB = Preheader->getUniquePredecessor();
if (!GuardBB) if (!GuardBB)
return nullptr; return nullptr;
assert(GuardBB->getTerminator() && "Expecting valid guard terminator"); assert(GuardBB->getTerminator() && "Expecting valid guard terminator");
BranchInst *GuardBI = dyn_cast<BranchInst>(GuardBB->getTerminator()); BranchInst *GuardBI = dyn_cast<BranchInst>(GuardBB->getTerminator());
if (!GuardBI || GuardBI->isUnconditional()) if (!GuardBI || GuardBI->isUnconditional())
return nullptr; return nullptr;
BasicBlock *GuardOtherSucc = (GuardBI->getSuccessor(0) == Preheader) BasicBlock *GuardOtherSucc = (GuardBI->getSuccessor(0) == Preheader)
? GuardBI->getSuccessor(1) ? GuardBI->getSuccessor(1)
: GuardBI->getSuccessor(0); : GuardBI->getSuccessor(0);
return (GuardOtherSucc == ExitFromLatchSucc) ? GuardBI : nullptr;
// Check if ExitFromLatch (or any BasicBlock which is an empty unique
// successor of ExitFromLatch) is equal to GuardOtherSucc. If
// skipEmptyBlockUntil returns GuardOtherSucc, then the guard branch for the
// loop is GuardBI (return GuardBI), otherwise return nullptr.
if (&LoopNest::skipEmptyBlockUntil(ExitFromLatch, GuardOtherSucc,
/*CheckUniquePred=*/true) ==
GuardOtherSucc)
return GuardBI;
else
return nullptr;
} }
bool Loop::isCanonical(ScalarEvolution &SE) const { bool Loop::isCanonical(ScalarEvolution &SE) const {
InductionDescriptor IndDesc; InductionDescriptor IndDesc;
if (!getInductionDescriptor(SE, IndDesc)) if (!getInductionDescriptor(SE, IndDesc))
return false; return false;
ConstantInt *Init = dyn_cast_or_null<ConstantInt>(IndDesc.getStartValue()); ConstantInt *Init = dyn_cast_or_null<ConstantInt>(IndDesc.getStartValue());
▲ Show 20 Lines • Show All 740 Lines • Show Last 20 Lines

llvm/lib/Analysis/LoopNestAnalysis.cpp

Show First 20 Lines • Show All 200 Lines • ▼ Show 20 Lines while (SubLoops->size() == 1) {
SubLoops = &CurrentLoop->getSubLoops(); SubLoops = &CurrentLoop->getSubLoops();
++CurrentDepth; ++CurrentDepth;
} }
return CurrentDepth; return CurrentDepth;
} }
const BasicBlock &LoopNest::skipEmptyBlockUntil(const BasicBlock *From, const BasicBlock &LoopNest::skipEmptyBlockUntil(const BasicBlock *From,
const BasicBlock *End) { const BasicBlock *End,
bool CheckUniquePred) {
assert(From && "Expecting valid From"); assert(From && "Expecting valid From");
assert(End && "Expecting valid End"); assert(End && "Expecting valid End");
if (From == End || !From->getUniqueSuccessor()) if (From == End || !From->getUniqueSuccessor())
return *From; return *From;
auto IsEmpty = [](const BasicBlock *BB) { auto IsEmpty = [](const BasicBlock *BB) {
return (BB->getInstList().size() == 1); return (BB->getInstList().size() == 1);
}; };
// Visited is used to avoid running into an infinite loop. // Visited is used to avoid running into an infinite loop.
SmallPtrSet<const BasicBlock *, 4> Visited; SmallPtrSet<const BasicBlock *, 4> Visited;
const BasicBlock *BB = From->getUniqueSuccessor(); const BasicBlock *BB = From->getUniqueSuccessor();
const BasicBlock *PredBB = BB; const BasicBlock *PredBB = From;
while (BB && BB != End && IsEmpty(BB) && !Visited.count(BB)) { while (BB && BB != End && IsEmpty(BB) && !Visited.count(BB) &&
(!CheckUniquePred || BB->getUniquePredecessor())) {
Visited.insert(BB); Visited.insert(BB);
PredBB = BB; PredBB = BB;
BB = BB->getUniqueSuccessor(); BB = BB->getUniqueSuccessor();
} }
return (BB == End) ? *End : *PredBB; return (BB == End) ? *End : *PredBB;
} }
▲ Show 20 Lines • Show All 148 Lines • Show Last 20 Lines

llvm/test/Analysis/LoopNestAnalysis/imperfectnest.ll

Show First 20 Lines • Show All 418 Lines • ▼ Show 20 Linesfor.inc11:
br i1 %cmp, label %imperf_nest_5_loop_i, label %for.cond.for.end13_crit_edge br i1 %cmp, label %imperf_nest_5_loop_i, label %for.cond.for.end13_crit_edge
for.cond.for.end13_crit_edge: for.cond.for.end13_crit_edge:
br label %for.end13 br label %for.end13
for.end13: for.end13:
ret void ret void
} }
; Test an imperfect loop nest of the form:
; for (int i = 0; i < nx; ++i)
; if (i > 5) { // user branch
; for (int j = 1; j <= 5; j+=2)
; y[j][i] = x[i][j] + j;
; }
define void @imperf_nest_6(i32** %y, i32** %x, i32 signext %nx, i32 signext %ny) {
; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_6_loop_i, Loops: ( imperf_nest_6_loop_i imperf_nest_6_loop_j )
entry:
%cmp2 = icmp slt i32 0, %nx
br i1 %cmp2, label %imperf_nest_6_loop_i.lr.ph, label %for.end13
imperf_nest_6_loop_i.lr.ph:
br label %imperf_nest_6_loop_i
imperf_nest_6_loop_i:
%i.0 = phi i32 [ 0, %imperf_nest_6_loop_i.lr.ph ], [ %inc12, %for.inc11 ]
%cmp1 = icmp sgt i32 %i.0, 5
br i1 %cmp1, label %imperf_nest_6_loop_j.lr.ph, label %if.end
imperf_nest_6_loop_j.lr.ph:
br label %imperf_nest_6_loop_j
imperf_nest_6_loop_j:
%j.0 = phi i32 [ 1, %imperf_nest_6_loop_j.lr.ph ], [ %inc, %for.inc ]
%idxprom = sext i32 %i.0 to i64
%arrayidx = getelementptr inbounds i32*, i32** %x, i64 %idxprom
%0 = load i32*, i32** %arrayidx, align 8
%idxprom5 = sext i32 %j.0 to i64
%arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %idxprom5
%1 = load i32, i32* %arrayidx6, align 4
%add = add nsw i32 %1, %j.0
%idxprom7 = sext i32 %j.0 to i64
%arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %idxprom7
%2 = load i32*, i32** %arrayidx8, align 8
%idxprom9 = sext i32 %i.0 to i64
%arrayidx10 = getelementptr inbounds i32, i32* %2, i64 %idxprom9
store i32 %add, i32* %arrayidx10, align 4
br label %for.inc
for.inc:
%inc = add nsw i32 %j.0, 2
%cmp3 = icmp sle i32 %inc, 5
br i1 %cmp3, label %imperf_nest_6_loop_j, label %for.cond2.for.end_crit_edge
for.cond2.for.end_crit_edge:
br label %for.end
for.end:
br label %if.end
if.end:
br label %for.inc11
for.inc11:
%inc12 = add nsw i32 %i.0, 1
%cmp = icmp slt i32 %inc12, %nx
br i1 %cmp, label %imperf_nest_6_loop_i, label %for.cond.for.end13_crit_edge
for.cond.for.end13_crit_edge:
br label %for.end13
for.end13:
ret void
}

llvm/test/Analysis/LoopNestAnalysis/perfectnest.ll

Show First 20 Lines • Show All 316 Lines • ▼ Show 20 Lines
for.cond.for.end7_crit_edge: for.cond.for.end7_crit_edge:
%split7 = phi i32 [ %x.addr.1.lcssa, %for.inc5 ] %split7 = phi i32 [ %x.addr.1.lcssa, %for.inc5 ]
br label %for.end7 br label %for.end7
for.end7: for.end7:
%x.addr.0.lcssa = phi i32 [ %split7, %for.cond.for.end7_crit_edge ], [ %x, %entry ] %x.addr.0.lcssa = phi i32 [ %split7, %for.cond.for.end7_crit_edge ], [ %x, %entry ]
ret i32 %x.addr.0.lcssa ret i32 %x.addr.0.lcssa
} }
; Test a perfect loop nest of the form:
; for (int i = 0; i < nx; ++i)
; if (i < ny) { // guard branch for the j-loop
; for (int j=i; j < ny; j+=1)
; y[j][i] = x[i][j] + j;
; }
define double @perf_nest_guard_branch(i32** %y, i32** %x, i32 signext %nx, i32 signext %ny) {
; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: test6Loop2, Loops: ( test6Loop2 )
; CHECK-LABEL: IsPerfect=true, Depth=2, OutermostLoop: test6Loop1, Loops: ( test6Loop1 test6Loop2 )
entry:
%cmp2 = icmp slt i32 0, %nx
br i1 %cmp2, label %test6Loop1.lr.ph, label %for.end13
test6Loop1.lr.ph: ; preds = %entry
br label %test6Loop1
test6Loop1: ; preds = %test6Loop1.lr.ph, %for.inc11
%i.0 = phi i32 [ 0, %test6Loop1.lr.ph ], [ %inc12, %for.inc11 ]
%cmp1 = icmp slt i32 %i.0, %ny
br i1 %cmp1, label %test6Loop2.lr.ph, label %if.end
test6Loop2.lr.ph: ; preds = %if.then
br label %test6Loop2
test6Loop2: ; preds = %test6Loop2.lr.ph, %for.inc
%j.0 = phi i32 [ %i.0, %test6Loop2.lr.ph ], [ %inc, %for.inc ]
%idxprom = sext i32 %i.0 to i64
%arrayidx = getelementptr inbounds i32*, i32** %x, i64 %idxprom
%0 = load i32*, i32** %arrayidx, align 8
%idxprom5 = sext i32 %j.0 to i64
%arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %idxprom5
%1 = load i32, i32* %arrayidx6, align 4
%add = add nsw i32 %1, %j.0
%idxprom7 = sext i32 %j.0 to i64
%arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %idxprom7
%2 = load i32*, i32** %arrayidx8, align 8
%idxprom9 = sext i32 %i.0 to i64
%arrayidx10 = getelementptr inbounds i32, i32* %2, i64 %idxprom9
store i32 %add, i32* %arrayidx10, align 4
br label %for.inc
for.inc: ; preds = %test6Loop2
%inc = add nsw i32 %j.0, 1
%cmp3 = icmp slt i32 %inc, %ny
br i1 %cmp3, label %test6Loop2, label %for.cond2.for.end_crit_edge
for.cond2.for.end_crit_edge: ; preds = %for.inc
br label %for.end
for.end: ; preds = %for.cond2.for.end_crit_edge, %if.then
br label %if.end
if.end: ; preds = %for.end, %test6Loop1
br label %for.inc11
for.inc11: ; preds = %if.end
%inc12 = add nsw i32 %i.0, 1
%cmp = icmp slt i32 %inc12, %nx
br i1 %cmp, label %test6Loop1, label %for.cond.for.end13_crit_edge
for.cond.for.end13_crit_edge: ; preds = %for.inc11
br label %for.end13
for.end13: ; preds = %for.cond.for.end13_crit_edge, %entry
%arrayidx14 = getelementptr inbounds i32*, i32** %y, i64 0
%3 = load i32*, i32** %arrayidx14, align 8
%arrayidx15 = getelementptr inbounds i32, i32* %3, i64 0
%4 = load i32, i32* %arrayidx15, align 4
%conv = sitofp i32 %4 to double
ret double %conv
}
; Test a perfect loop nest of the form:
; for (int i = 0; i < nx; ++i)
; if (i < ny) { // guard branch for the j-loop
; for (int j=i; j < ny; j+=1)
; y[j][i] = x[i][j] + j;
; }
define double @test6(i32** %y, i32** %x, i32 signext %nx, i32 signext %ny) {
; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: test6Loop2, Loops: ( test6Loop2 )
; CHECK-LABEL: IsPerfect=true, Depth=2, OutermostLoop: test6Loop1, Loops: ( test6Loop1 test6Loop2 )
entry:
%cmp2 = icmp slt i32 0, %nx
br i1 %cmp2, label %test6Loop1.lr.ph, label %for.end13
test6Loop1.lr.ph: ; preds = %entry
br label %test6Loop1
test6Loop1: ; preds = %test6Loop1.lr.ph, %for.inc11
%i.0 = phi i32 [ 0, %test6Loop1.lr.ph ], [ %inc12, %for.inc11 ]
%cmp1 = icmp slt i32 %i.0, %ny
br i1 %cmp1, label %test6Loop2.lr.ph, label %if.end
test6Loop2.lr.ph: ; preds = %if.then
br label %test6Loop2
test6Loop2: ; preds = %test6Loop2.lr.ph, %for.inc
%j.0 = phi i32 [ %i.0, %test6Loop2.lr.ph ], [ %inc, %for.inc ]
%idxprom = sext i32 %i.0 to i64
%arrayidx = getelementptr inbounds i32*, i32** %x, i64 %idxprom
%0 = load i32*, i32** %arrayidx, align 8
%idxprom5 = sext i32 %j.0 to i64
%arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %idxprom5
%1 = load i32, i32* %arrayidx6, align 4
%add = add nsw i32 %1, %j.0
%idxprom7 = sext i32 %j.0 to i64
%arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %idxprom7
%2 = load i32*, i32** %arrayidx8, align 8
%idxprom9 = sext i32 %i.0 to i64
%arrayidx10 = getelementptr inbounds i32, i32* %2, i64 %idxprom9
store i32 %add, i32* %arrayidx10, align 4
br label %for.inc
for.inc: ; preds = %test6Loop2
%inc = add nsw i32 %j.0, 1
%cmp3 = icmp slt i32 %inc, %ny
br i1 %cmp3, label %test6Loop2, label %for.cond2.for.end_crit_edge
for.cond2.for.end_crit_edge: ; preds = %for.inc
br label %for.end
for.end: ; preds = %for.cond2.for.end_crit_edge, %if.then
br label %if.end
if.end: ; preds = %for.end, %test6Loop1
br label %for.inc11
for.inc11: ; preds = %if.end
%inc12 = add nsw i32 %i.0, 1
%cmp = icmp slt i32 %inc12, %nx
br i1 %cmp, label %test6Loop1, label %for.cond.for.end13_crit_edge
for.cond.for.end13_crit_edge: ; preds = %for.inc11
br label %for.end13
for.end13: ; preds = %for.cond.for.end13_crit_edge, %entry
%arrayidx14 = getelementptr inbounds i32*, i32** %y, i64 0
%3 = load i32*, i32** %arrayidx14, align 8
%arrayidx15 = getelementptr inbounds i32, i32* %3, i64 0
%4 = load i32, i32* %arrayidx15, align 4
%conv = sitofp i32 %4 to double
ret double %conv
}

llvm/unittests/Analysis/LoopInfoTest.cpp

Show First 20 Lines • Show All 1,494 Lines • ▼ Show 20 Lines runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
// This loop is in simplified form. // This loop is in simplified form.
EXPECT_TRUE(L->isLoopSimplifyForm()); EXPECT_TRUE(L->isLoopSimplifyForm());
// This loop is not rotated. // This loop is not rotated.
EXPECT_FALSE(L->isRotatedForm()); EXPECT_FALSE(L->isRotatedForm());
}); });
} }
TEST(LoopInfoTest, LoopUserBranch) {
const char *ModuleStr =
"target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
"define void @foo(i32* %B, i64 signext %nx, i1 %cond) {\n"
"entry:\n"
" br i1 %cond, label %bb, label %guard\n"
"guard:\n"
" %cmp.guard = icmp slt i64 0, %nx\n"
" br i1 %cmp.guard, label %for.i.preheader, label %for.end\n"
"for.i.preheader:\n"
" br label %for.i\n"
"for.i:\n"
" %i = phi i64 [ 0, %for.i.preheader ], [ %inc13, %for.i ]\n"
" %Bi = getelementptr inbounds i32, i32* %B, i64 %i\n"
" store i32 0, i32* %Bi, align 4\n"
" %inc13 = add nsw i64 %i, 1\n"
" %cmp = icmp slt i64 %inc13, %nx\n"
" br i1 %cmp, label %for.i, label %for.i.exit\n"
"for.i.exit:\n"
" br label %bb\n"
"bb:\n"
" br label %for.end\n"
"for.end:\n"
" ret void\n"
"}\n";
// Parse the module.
LLVMContext Context;
std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
Function::iterator FI = F.begin();
FI = ++FI;
BasicBlock *Guard = &*FI;
assert(Guard->getName() == "guard");
FI = ++FI;
BasicBlock *Header = &*(++FI);
assert(Header->getName() == "for.i");
Loop *L = LI.getLoopFor(Header);
EXPECT_NE(L, nullptr);
// L should not have a guard branch
EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
});
}