From df9158c9a45a6902c2b0394f9bd6512e3e441f31 Mon Sep 17 00:00:00 2001 From: Ta-Wei Tu Date: Mon, 8 Mar 2021 11:35:35 +0800 Subject: [PATCH] [LoopInterchange] Replace tightly-nesting-ness check with the one from `LoopNest` The check `tightlyNested()` in `LoopInterchange` is similar to the one in `LoopNest`. In fact, the former misses some cases where loop-interchange is not feasible and results in incorrect behaviour. Replacing it with the much robust version provided by `LoopNest` reduces code duplications and fixes https://bugs.llvm.org/show_bug.cgi?id=48113. `LoopInterchange` has a weaker definition of tightly or perfectly nesting-ness than the one implemented in `LoopNest::arePerfectlyNested()`. Therefore, `tightlyNested()` is instead implemented with `LoopNest::checkLoopsStructure` and additional checks for unsafe instructions. Reviewed By: Whitney Differential Revision: https://reviews.llvm.org/D97290 --- llvm/include/llvm/Analysis/LoopNestAnalysis.h | 12 +++++ llvm/lib/Analysis/LoopNestAnalysis.cpp | 16 +----- llvm/lib/Transforms/Scalar/LoopInterchange.cpp | 20 ++----- llvm/test/Transforms/LoopInterchange/pr48113.ll | 72 +++++++++++++++++++++++++ 4 files changed, 90 insertions(+), 30 deletions(-) create mode 100644 llvm/test/Transforms/LoopInterchange/pr48113.ll diff --git a/llvm/include/llvm/Analysis/LoopNestAnalysis.h b/llvm/include/llvm/Analysis/LoopNestAnalysis.h index ace1754..b913284 100644 --- a/llvm/include/llvm/Analysis/LoopNestAnalysis.h +++ b/llvm/include/llvm/Analysis/LoopNestAnalysis.h @@ -66,6 +66,18 @@ public: static const BasicBlock &skipEmptyBlockUntil(const BasicBlock *From, const BasicBlock *End); + /// Determine whether the loops structure violates basic requirements for + /// perfect nesting: + /// - the inner loop should be the outer loop's only child + /// - the outer loop header should 'flow' into the inner loop preheader + /// or jump around the inner loop to the outer loop latch + /// - if the inner loop latch exits the inner loop, it should 'flow' into + /// the outer loop latch. + /// Returns true if the loop structure satisfies the basic requirements and + /// false otherwise. + static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, + ScalarEvolution &SE); + /// Return the outermost loop in the loop nest. Loop &getOutermostLoop() const { return *Loops.front(); } diff --git a/llvm/lib/Analysis/LoopNestAnalysis.cpp b/llvm/lib/Analysis/LoopNestAnalysis.cpp index ee74d4b..7f9bdb4 100644 --- a/llvm/lib/Analysis/LoopNestAnalysis.cpp +++ b/llvm/lib/Analysis/LoopNestAnalysis.cpp @@ -24,18 +24,6 @@ using namespace llvm; static const char *VerboseDebug = DEBUG_TYPE "-verbose"; #endif -/// Determine whether the loops structure violates basic requirements for -/// perfect nesting: -/// - the inner loop should be the outer loop's only child -/// - the outer loop header should 'flow' into the inner loop preheader -/// or jump around the inner loop to the outer loop latch -/// - if the inner loop latch exits the inner loop, it should 'flow' into -/// the outer loop latch. -/// Returns true if the loop structure satisfies the basic requirements and -/// false otherwise. -static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, - ScalarEvolution &SE); - //===----------------------------------------------------------------------===// // LoopNest implementation // @@ -230,8 +218,8 @@ const BasicBlock &LoopNest::skipEmptyBlockUntil(const BasicBlock *From, return (BB == End) ? *End : *PredBB; } -static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, - ScalarEvolution &SE) { +bool LoopNest::checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, + ScalarEvolution &SE) { // The inner loop must be the only outer loop's child. if ((OuterLoop.getSubLoops().size() != 1) || (InnerLoop.getParentLoop() != &OuterLoop)) diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index 0162bf13..723ba00 100644 --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -584,26 +584,14 @@ bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB) { } bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) { - BasicBlock *OuterLoopHeader = OuterLoop->getHeader(); - BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); - BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch(); - LLVM_DEBUG(dbgs() << "Checking if loops are tightly nested\n"); - // A perfectly nested loop will not have any branch in between the outer and - // inner block i.e. outer header will branch to either inner preheader and - // outerloop latch. - BranchInst *OuterLoopHeaderBI = - dyn_cast(OuterLoopHeader->getTerminator()); - if (!OuterLoopHeaderBI) + if (!LoopNest::checkLoopsStructure(*OuterLoop, *InnerLoop, *SE)) return false; + BasicBlock *OuterLoopHeader = OuterLoop->getHeader(); + BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); + BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch(); - for (BasicBlock *Succ : successors(OuterLoopHeaderBI)) - if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader() && - Succ != OuterLoopLatch) - return false; - - LLVM_DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n"); // We do not have any basic block in between now make sure the outer header // and outer loop latch doesn't contain any unsafe instructions. if (containsUnsafeInstructions(OuterLoopHeader) || diff --git a/llvm/test/Transforms/LoopInterchange/pr48113.ll b/llvm/test/Transforms/LoopInterchange/pr48113.ll new file mode 100644 index 0000000..cfb118c --- /dev/null +++ b/llvm/test/Transforms/LoopInterchange/pr48113.ll @@ -0,0 +1,72 @@ +; RUN: opt -S -passes='loop-interchange' -debug-only=loop-interchange < %s 2>&1 > /dev/null | FileCheck %s + +; Test case of PR48113. +; The loops should not be interchanged becuase they are not tightly nested. + +@a = dso_local local_unnamed_addr global i8 0, align 1 +@b = dso_local local_unnamed_addr global [1 x [2 x i32]] zeroinitializer, align 4 +@c = dso_local local_unnamed_addr global [1 x [9 x i8]] zeroinitializer, align 1 +@d = dso_local local_unnamed_addr global i8 0, align 1 +@e = dso_local local_unnamed_addr global i8* null, align 8 +@f = internal unnamed_addr global i32 0, align 4 +@g = dso_local local_unnamed_addr global i16 0, align 2 + +; CHECK: Processing InnerLoopId = 1 and OuterLoopId = 0 +; CHECK-NEXT: Checking if loops are tightly nested +; CHECK-NEXT: Loops not tightly nested +; CHECK-NEXT: Not interchanging loops. Cannot prove legality + +define dso_local i32 @main() local_unnamed_addr { +entry: + %.pr.i = load i32, i32* @f, align 4 + %cmp3.i = icmp ult i32 %.pr.i, 3 + br i1 %cmp3.i, label %for.cond1.preheader.lr.ph.i, label %h.exit + +for.cond1.preheader.lr.ph.i: ; preds = %entry + %0 = load i8, i8* @a, align 1 + %tobool.not.i = icmp eq i8 %0, 0 + %1 = load i8*, i8** @e, align 8 + %2 = zext i32 %.pr.i to i64 + br label %for.cond1.preheader.i + +for.cond1.preheader.i: ; preds = %if.end.i, %for.cond1.preheader.lr.ph.i + %indvars.iv4.i = phi i64 [ %2, %for.cond1.preheader.lr.ph.i ], [ %indvars.iv.next5.i, %if.end.i ] + br label %for.body3.i + +for.body3.i: ; preds = %for.body3.i, %for.cond1.preheader.i + %indvars.iv.i = phi i64 [ 0, %for.cond1.preheader.i ], [ %indvars.iv.next.i, %for.body3.i ] + %arrayidx5.i = getelementptr inbounds [1 x [9 x i8]], [1 x [9 x i8]]* @c, i64 0, i64 %indvars.iv.i, i64 %indvars.iv4.i + %3 = load i8, i8* %arrayidx5.i, align 1 + %conv.i = sext i8 %3 to i32 + %arrayidx8.i = getelementptr inbounds [1 x [2 x i32]], [1 x [2 x i32]]* @b, i64 0, i64 %indvars.iv.i, i64 1 + store i32 %conv.i, i32* %arrayidx8.i, align 4 + %indvars.iv.next.i = add nuw nsw i64 %indvars.iv.i, 1 + %exitcond.not.i = icmp eq i64 %indvars.iv.next.i, 3 + br i1 %exitcond.not.i, label %for.end.i, label %for.body3.i + +for.end.i: ; preds = %for.body3.i + %4 = load i8, i8* @d, align 1 + %inc9.i = add i8 %4, 1 + store i8 %inc9.i, i8* @d, align 1 + br i1 %tobool.not.i, label %if.end.i, label %if.then.i + +if.then.i: ; preds = %for.end.i + %5 = load i8, i8* %1, align 1 + %conv10.i = sext i8 %5 to i16 + store i16 %conv10.i, i16* @g, align 2 + br label %if.end.i + +if.end.i: ; preds = %if.then.i, %for.end.i + %indvars.iv.next5.i = add nuw nsw i64 %indvars.iv4.i, 1 + %exitcond6.not.i = icmp eq i64 %indvars.iv.next5.i, 3 + br i1 %exitcond6.not.i, label %for.cond.for.end13_crit_edge.i, label %for.cond1.preheader.i + +for.cond.for.end13_crit_edge.i: ; preds = %if.end.i + store i32 3, i32* @f, align 4 + br label %h.exit + +h.exit: ; preds = %entry, %for.cond.for.end13_crit_edge.i + %6 = load i8, i8* @d, align 1 + %conv = sext i8 %6 to i32 + ret i32 %conv +} -- 2.7.4