summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/include/llvm/Analysis/PostDominators.h7
-rw-r--r--llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h40
-rw-r--r--llvm/lib/Analysis/PostDominators.cpp23
-rw-r--r--llvm/lib/Transforms/Utils/CMakeLists.txt1
-rw-r--r--llvm/lib/Transforms/Utils/CodeMoverUtils.cpp168
-rw-r--r--llvm/unittests/Transforms/Utils/CMakeLists.txt1
-rw-r--r--llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp172
7 files changed, 412 insertions, 0 deletions
diff --git a/llvm/include/llvm/Analysis/PostDominators.h b/llvm/include/llvm/Analysis/PostDominators.h
index e4582599a5a..801eb3d5967 100644
--- a/llvm/include/llvm/Analysis/PostDominators.h
+++ b/llvm/include/llvm/Analysis/PostDominators.h
@@ -34,6 +34,13 @@ public:
/// Handle invalidation explicitly.
bool invalidate(Function &F, const PreservedAnalyses &PA,
FunctionAnalysisManager::Invalidator &);
+
+ // Ensure base-class overloads are visible.
+ using Base::dominates;
+
+ /// Return true if \p I1 dominates \p I2. This checks if \p I2 comes before
+ /// \p I1 if they belongs to the same basic block.
+ bool dominates(const Instruction *I1, const Instruction *I2) const;
};
/// Analysis pass which computes a \c PostDominatorTree.
diff --git a/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h b/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h
new file mode 100644
index 00000000000..4cf30e3899a
--- /dev/null
+++ b/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h
@@ -0,0 +1,40 @@
+//===- Transform/Utils/CodeMoverUtils.h - CodeMover Utils -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This family of functions determine movements are safe on basic blocks, and
+// instructions contained within a function.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_CODEMOVERUTILS_H
+#define LLVM_TRANSFORMS_UTILS_CODEMOVERUTILS_H
+
+namespace llvm {
+
+class DependenceInfo;
+class DominatorTree;
+class Instruction;
+class PostDominatorTree;
+
+/// Return true if \p I0 and \p I1 are control flow equivalent.
+/// Two instructions are control flow equivalent if when one executes,
+/// the other is guaranteed to execute. This is determined using dominators
+/// and post-dominators: if A dominates B and B post-dominates A then A and B
+/// are control-flow equivalent.
+bool isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
+ const DominatorTree &DT,
+ const PostDominatorTree &PDT);
+
+/// Return true if \p I can be safely moved before \p InsertPoint.
+bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
+ const DominatorTree &DT, const PostDominatorTree &PDT,
+ DependenceInfo &DI);
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_CODEMOVERUTILS_H
diff --git a/llvm/lib/Analysis/PostDominators.cpp b/llvm/lib/Analysis/PostDominators.cpp
index 918c3edafa9..f01d51504d7 100644
--- a/llvm/lib/Analysis/PostDominators.cpp
+++ b/llvm/lib/Analysis/PostDominators.cpp
@@ -12,6 +12,7 @@
#include "llvm/Analysis/PostDominators.h"
#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
#include "llvm/IR/PassManager.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
@@ -50,6 +51,28 @@ bool PostDominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
PAC.preservedSet<CFGAnalyses>());
}
+bool PostDominatorTree::dominates(const Instruction *I1,
+ const Instruction *I2) const {
+ assert(I1 && I2 && "Expecting valid I1 and I2");
+
+ const BasicBlock *BB1 = I1->getParent();
+ const BasicBlock *BB2 = I2->getParent();
+
+ if (BB1 != BB2)
+ return Base::dominates(BB1, BB2);
+
+ // PHINodes in a block are unordered.
+ if (isa<PHINode>(I1) && isa<PHINode>(I2))
+ return false;
+
+ // Loop through the basic block until we find I1 or I2.
+ BasicBlock::const_iterator I = BB1->begin();
+ for (; &*I != I1 && &*I != I2; ++I)
+ /*empty*/;
+
+ return &*I == I2;
+}
+
bool PostDominatorTreeWrapperPass::runOnFunction(Function &F) {
DT.recalculate(F);
return false;
diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt
index 254662afdcf..67bc6fbd180 100644
--- a/llvm/lib/Transforms/Utils/CMakeLists.txt
+++ b/llvm/lib/Transforms/Utils/CMakeLists.txt
@@ -10,6 +10,7 @@ add_llvm_component_library(LLVMTransformUtils
CloneFunction.cpp
CloneModule.cpp
CodeExtractor.cpp
+ CodeMoverUtils.cpp
CtorUtils.cpp
Debugify.cpp
DemoteRegToStack.cpp
diff --git a/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp b/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
new file mode 100644
index 00000000000..5aab27fa094
--- /dev/null
+++ b/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
@@ -0,0 +1,168 @@
+//===- CodeMoverUtils.cpp - CodeMover Utilities ----------------------------==//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This family of functions perform movements on basic blocks, and instructions
+// contained within a function.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/CodeMoverUtils.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/DependenceAnalysis.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/Dominators.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "codemover-utils"
+
+STATISTIC(HasDependences,
+ "Cannot move across instructions that has memory dependences");
+STATISTIC(MayThrowException, "Cannot move across instructions that may throw");
+STATISTIC(NotControlFlowEquivalent,
+ "Instructions are not control flow equivalent");
+STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported");
+STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported");
+
+bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
+ const DominatorTree &DT,
+ const PostDominatorTree &PDT) {
+ const BasicBlock *BB0 = I0.getParent();
+ const BasicBlock *BB1 = I1.getParent();
+ return ((DT.dominates(BB0, BB1) && PDT.dominates(BB1, BB0)) ||
+ (PDT.dominates(BB0, BB1) && DT.dominates(BB1, BB0)));
+}
+
+static bool reportInvalidCandidate(const Instruction &I,
+ llvm::Statistic &Stat) {
+ ++Stat;
+ LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". "
+ << Stat.getDesc());
+ return false;
+}
+
+/// Collect all instructions in between \p StartInst and \p EndInst, and store
+/// them in \p InBetweenInsts.
+static void
+collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst,
+ SmallPtrSetImpl<Instruction *> &InBetweenInsts) {
+ assert(InBetweenInsts.empty() && "Expecting InBetweenInsts to be empty");
+
+ /// Get the next instructions of \p I, and push them to \p WorkList.
+ auto getNextInsts = [](Instruction &I,
+ SmallPtrSetImpl<Instruction *> &WorkList) {
+ if (Instruction *NextInst = I.getNextNode())
+ WorkList.insert(NextInst);
+ else {
+ assert(I.isTerminator() && "Expecting a terminator instruction");
+ for (BasicBlock *Succ : successors(&I))
+ WorkList.insert(&Succ->front());
+ }
+ };
+
+ SmallPtrSet<Instruction *, 10> WorkList;
+ getNextInsts(StartInst, WorkList);
+ while (!WorkList.empty()) {
+ Instruction *CurInst = *WorkList.begin();
+ WorkList.erase(CurInst);
+
+ if (CurInst == &EndInst)
+ continue;
+
+ if (!InBetweenInsts.insert(CurInst).second)
+ continue;
+
+ getNextInsts(*CurInst, WorkList);
+ }
+}
+
+bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
+ const DominatorTree &DT,
+ const PostDominatorTree &PDT,
+ DependenceInfo &DI) {
+ // Cannot move itself before itself.
+ if (&I == &InsertPoint)
+ return false;
+
+ // Not moved.
+ if (I.getNextNode() == &InsertPoint)
+ return true;
+
+ if (isa<PHINode>(I) || isa<PHINode>(InsertPoint))
+ return reportInvalidCandidate(I, NotMovedPHINode);
+
+ if (I.isTerminator())
+ return reportInvalidCandidate(I, NotMovedTerminator);
+
+ // TODO remove this limitation.
+ if (!isControlFlowEquivalent(I, InsertPoint, DT, PDT))
+ return reportInvalidCandidate(I, NotControlFlowEquivalent);
+
+ // As I and InsertPoint are control flow equivalent, if I dominates
+ // InsertPoint, then I comes before InsertPoint.
+ const bool MoveForward = DT.dominates(&I, &InsertPoint);
+ if (MoveForward) {
+ // When I is being moved forward, we need to make sure the InsertPoint
+ // dominates every users. Or else, a user may be using an undefined I.
+ for (const Value *User : I.users())
+ if (auto *UserInst = dyn_cast<Instruction>(User))
+ if (!DT.dominates(&InsertPoint, UserInst))
+ return false;
+ } else {
+ // When I is being moved backward, we need to make sure all its opernads
+ // dominates the InsertPoint. Or else, an operand may be undefined for I.
+ for (const Value *Op : I.operands())
+ if (auto *OpInst = dyn_cast<Instruction>(Op))
+ if (&InsertPoint == OpInst || !DT.dominates(OpInst, &InsertPoint))
+ return false;
+ }
+
+ Instruction &StartInst = (MoveForward ? I : InsertPoint);
+ Instruction &EndInst = (MoveForward ? InsertPoint : I);
+ SmallPtrSet<Instruction *, 10> InstsToCheck;
+ collectInstructionsInBetween(StartInst, EndInst, InstsToCheck);
+ if (!MoveForward)
+ InstsToCheck.insert(&InsertPoint);
+
+ // Check if there exists instructions which may throw, may synchonize, or may
+ // never return, from I to InsertPoint.
+ if (!isSafeToSpeculativelyExecute(&I))
+ if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
+ [](Instruction *I) {
+ if (I->mayThrow())
+ return true;
+
+ const CallBase *CB = dyn_cast<CallBase>(I);
+ if (!CB)
+ return false;
+ if (!CB->hasFnAttr(Attribute::WillReturn))
+ return true;
+ if (!CB->hasFnAttr(Attribute::NoSync))
+ return true;
+
+ return false;
+ })) {
+ return reportInvalidCandidate(I, MayThrowException);
+ }
+
+ // Check if I has any output/flow/anti dependences with instructions from \p
+ // StartInst to \p EndInst.
+ if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
+ [&DI, &I](Instruction *CurInst) {
+ auto DepResult = DI.depends(&I, CurInst, true);
+ if (DepResult &&
+ (DepResult->isOutput() || DepResult->isFlow() ||
+ DepResult->isAnti()))
+ return true;
+ return false;
+ }))
+ return reportInvalidCandidate(I, HasDependences);
+
+ return true;
+}
diff --git a/llvm/unittests/Transforms/Utils/CMakeLists.txt b/llvm/unittests/Transforms/Utils/CMakeLists.txt
index 8d9d7df4f40..5a8204cb86a 100644
--- a/llvm/unittests/Transforms/Utils/CMakeLists.txt
+++ b/llvm/unittests/Transforms/Utils/CMakeLists.txt
@@ -11,6 +11,7 @@ add_llvm_unittest(UtilsTests
BasicBlockUtilsTest.cpp
CloningTest.cpp
CodeExtractorTest.cpp
+ CodeMoverUtilsTest.cpp
FunctionComparatorTest.cpp
IntegerDivisionTest.cpp
LocalTest.cpp
diff --git a/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp b/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
new file mode 100644
index 00000000000..64c4f796cb8
--- /dev/null
+++ b/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
@@ -0,0 +1,172 @@
+//===- CodeMoverUtils.cpp - Unit tests for CodeMoverUtils ---------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/CodeMoverUtils.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/DependenceAnalysis.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/Support/SourceMgr.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
+ SMDiagnostic Err;
+ std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
+ if (!Mod)
+ Err.print("CodeMoverUtilsTests", errs());
+ return Mod;
+}
+
+static void run(Module &M, StringRef FuncName,
+ function_ref<void(Function &F, DominatorTree &DT,
+ PostDominatorTree &PDT, DependenceInfo &DI)>
+ Test) {
+ auto *F = M.getFunction(FuncName);
+ DominatorTree DT(*F);
+ PostDominatorTree PDT(*F);
+ TargetLibraryInfoImpl TLII;
+ TargetLibraryInfo TLI(TLII);
+ AssumptionCache AC(*F);
+ AliasAnalysis AA(TLI);
+ LoopInfo LI(DT);
+ ScalarEvolution SE(*F, TLI, AC, DT, LI);
+ DependenceInfo DI(F, &AA, &SE, &LI);
+ Test(*F, DT, PDT, DI);
+}
+
+TEST(CodeMoverUtils, BasicTest) {
+ LLVMContext C;
+
+ // void safecall() noexcept willreturn nosync;
+ // void unsafecall();
+ // void foo(int * __restrict__ A, int * __restrict__ B, int * __restrict__ C,
+ // long N) {
+ // X = N / 1;
+ // safecall();
+ // unsafecall1();
+ // unsafecall2();
+ // for (long i = 0; i < N; ++i) {
+ // A[5] = 5;
+ // A[i] = 0;
+ // B[i] = A[i];
+ // C[i] = A[i];
+ // A[6] = 6;
+ // }
+ // }
+ std::unique_ptr<Module> M = parseIR(
+ C,
+ "define void @foo(i32* noalias %A, i32* noalias %B, i32* noalias %C\n"
+ " , i64 %N) {\n"
+ "entry:\n"
+ " %X = sdiv i64 1, %N\n"
+ " call void @safecall()\n"
+ " %cmp1 = icmp slt i64 0, %N\n"
+ " call void @unsafecall1()\n"
+ " call void @unsafecall2()\n"
+ " br i1 %cmp1, label %for.body, label %for.end\n"
+ "for.body:\n"
+ " %i = phi i64 [ 0, %entry ], [ %inc, %for.body ]\n"
+ " %arrayidx_A5 = getelementptr inbounds i32, i32* %A, i64 5\n"
+ " store i32 5, i32* %arrayidx_A5, align 4\n"
+ " %arrayidx_A = getelementptr inbounds i32, i32* %A, i64 %i\n"
+ " store i32 0, i32* %arrayidx_A, align 4\n"
+ " %load1 = load i32, i32* %arrayidx_A, align 4\n"
+ " %arrayidx_B = getelementptr inbounds i32, i32* %B, i64 %i\n"
+ " store i32 %load1, i32* %arrayidx_B, align 4\n"
+ " %load2 = load i32, i32* %arrayidx_A, align 4\n"
+ " %arrayidx_C = getelementptr inbounds i32, i32* %C, i64 %i\n"
+ " store i32 %load2, i32* %arrayidx_C, align 4\n"
+ " %arrayidx_A6 = getelementptr inbounds i32, i32* %A, i64 6\n"
+ " store i32 6, i32* %arrayidx_A6, align 4\n"
+ " %inc = add nsw i64 %i, 1\n"
+ " %cmp = icmp slt i64 %inc, %N\n"
+ " br i1 %cmp, label %for.body, label %for.end\n"
+ "for.end:\n"
+ " ret void\n"
+ "}\n"
+ "declare void @safecall() nounwind nosync willreturn\n"
+ "declare void @unsafecall1()\n"
+ "declare void @unsafecall2()\n");
+
+ run(*M, "foo",
+ [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
+ DependenceInfo &DI) {
+ Function::iterator FI = F.begin();
+ BasicBlock *Entry = &*(FI++);
+ assert(Entry->getName() == "entry" && "Expecting BasicBlock entry");
+ Instruction *CI_safecall = Entry->front().getNextNode();
+ assert(isa<CallInst>(CI_safecall) && "Expecting CI_safecall to be a CallInst");
+ Instruction *CI_unsafecall = CI_safecall->getNextNode()->getNextNode();
+ assert(isa<CallInst>(CI_unsafecall) && "Expecting CI_unsafecall to be a CallInst");
+ BasicBlock *ForBody = &*(FI++);
+ assert(ForBody->getName() == "for.body" &&
+ "Expecting BasicBlock for.body");
+ Instruction &PN = ForBody->front();
+ assert(isa<PHINode>(PN) && "Expecting PN to be a PHINode");
+ Instruction *SI_A5 = PN.getNextNode()->getNextNode();
+ assert(isa<StoreInst>(SI_A5) &&
+ SI_A5->getOperand(1)->getName() == "arrayidx_A5" &&
+ "Expecting store to arrayidx_A5");
+ Instruction *SI = SI_A5->getNextNode()->getNextNode();
+ assert(isa<StoreInst>(SI) &&
+ SI->getOperand(1)->getName() == "arrayidx_A" &&
+ "Expecting store to arrayidx_A");
+ Instruction *LI1 = SI->getNextNode();
+ assert(LI1->getName() == "load1" && "Expecting LI1 to be load1");
+ Instruction *LI2 = LI1->getNextNode()->getNextNode()->getNextNode();
+ assert(LI2->getName() == "load2" && "Expecting LI2 to be load2");
+ Instruction *SI_A6 = LI2->getNextNode()->getNextNode()->getNextNode()->getNextNode();
+ assert(isa<StoreInst>(SI_A6) &&
+ SI_A6->getOperand(1)->getName() == "arrayidx_A6" &&
+ "Expecting store to arrayidx_A6");
+
+ // Can move after CI_safecall, as it does not throw, not synchronize, or must return.
+ EXPECT_TRUE(isSafeToMoveBefore(*CI_safecall->getPrevNode(), *CI_safecall->getNextNode(), DT, PDT, DI));
+
+ // Cannot move CI_unsafecall, as it may throw.
+ EXPECT_FALSE(isSafeToMoveBefore(*CI_unsafecall->getNextNode(), *CI_unsafecall, DT, PDT, DI));
+
+ // Moving instruction to non control flow equivalent places are not
+ // supported.
+ EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, PDT, DI));
+
+ // Moving PHINode is not supported.
+ EXPECT_FALSE(isSafeToMoveBefore(PN, *PN.getPrevNode(), DT, PDT, DI));
+
+ // Cannot move non-PHINode before PHINode.
+ EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, DT, PDT, DI));
+
+ // Moving Terminator is not supported.
+ EXPECT_FALSE(isSafeToMoveBefore(*Entry->getTerminator(), *PN.getNextNode(), DT,
+ PDT, DI));
+
+ // Cannot move %arrayidx_A after SI, as SI is its user.
+ EXPECT_FALSE(isSafeToMoveBefore(*SI->getPrevNode(), *SI->getNextNode(), DT, PDT, DI));
+
+ // Cannot move SI before %arrayidx_A, as %arrayidx_A is its operand.
+ EXPECT_FALSE(isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, PDT, DI));
+
+ // Cannot move LI2 after SI_A6, as there is a flow dependence.
+ EXPECT_FALSE(isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, PDT, DI));
+
+ // Cannot move SI after LI1, as there is a anti dependence.
+ EXPECT_FALSE(isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, PDT, DI));
+
+ // Cannot move SI_A5 after SI, as there is a output dependence.
+ EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, DT, PDT, DI));
+
+ // Can move LI2 before LI1, as there is only an input dependence.
+ EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, PDT, DI));
+ });
+}
OpenPOWER on IntegriCloud