diff --git a/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h b/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h --- a/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h +++ b/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h @@ -23,33 +23,30 @@ 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. +/// Two instructions are control flow equivalent if their basic blocks are +/// control flow equivalent. bool isControlFlowEquivalent(const Instruction &I0, const Instruction &I1, const DominatorTree &DT, const PostDominatorTree &PDT); /// Return true if \p BB0 and \p BB1 are control flow equivalent. /// Two basic blocks 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. +/// is guaranteed to execute. bool isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1, 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, + DominatorTree &DT, const PostDominatorTree &PDT, DependenceInfo &DI); -/// Move instructions from \p FromBB bottom up to the beginning of \p ToBB -/// when proven safe. -void moveInstsBottomUp(BasicBlock &FromBB, BasicBlock &ToBB, - const DominatorTree &DT, const PostDominatorTree &PDT, - DependenceInfo &DI); +/// Move instructions, in an order-preserving manner, from \p FromBB to the +/// beginning of \p ToBB when proven safe. +void moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB, + DominatorTree &DT, + const PostDominatorTree &PDT, + DependenceInfo &DI); } // end namespace llvm diff --git a/llvm/lib/Transforms/Scalar/LoopFuse.cpp b/llvm/lib/Transforms/Scalar/LoopFuse.cpp --- a/llvm/lib/Transforms/Scalar/LoopFuse.cpp +++ b/llvm/lib/Transforms/Scalar/LoopFuse.cpp @@ -1123,7 +1123,7 @@ /// Move instructions from FC0.Latch to FC1.Latch. If FC0.Latch has an unique /// successor, then merge FC0.Latch with its unique successor. void mergeLatch(const FusionCandidate &FC0, const FusionCandidate &FC1) { - moveInstsBottomUp(*FC0.Latch, *FC1.Latch, DT, PDT, DI); + moveInstructionsToTheBeginning(*FC0.Latch, *FC1.Latch, DT, PDT, DI); if (BasicBlock *Succ = FC0.Latch->getUniqueSuccessor()) { MergeBlockIntoPredecessor(Succ, &DTU, &LI); DTU.flush(); diff --git a/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp b/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp --- a/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp +++ b/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp @@ -12,8 +12,10 @@ //===----------------------------------------------------------------------===// #include "llvm/Transforms/Utils/CodeMoverUtils.h" +#include "llvm/ADT/Optional.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/DependenceAnalysis.h" +#include "llvm/Analysis/OrderedInstructions.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Dominators.h" @@ -30,6 +32,189 @@ STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported"); STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported"); +namespace { +/// Represent a control condition. A control condition is a condition of a +/// terminator to decide which successors to execute. The pointer field +/// represents the address of the condition of the terminator. The integer field +/// is a bool, it is true when the basic block is executed when V is true. For +/// example, `br %cond, bb0, bb1` %cond is a control condition of bb0 with the +/// integer field equals to true, while %cond is a control condition of bb1 with +/// the integer field equals to false. +using ControlCondition = PointerIntPair; +#ifndef NDEBUG +raw_ostream &operator<<(raw_ostream &OS, const ControlCondition &C) { + OS << "[" << *C.getPointer() << ", " << (C.getInt() ? "true" : "false") + << "]"; + return OS; +} +#endif + +/// Represent a set of control conditions required to execute ToBB from FromBB. +class ControlConditions { + using ConditionVectorTy = SmallVector; + + /// A SmallVector of control conditions. + ConditionVectorTy Conditions; + +public: + /// Return a ControlConditions which stores all conditions required to execute + /// \p BB from \p Dominator. If \p MaxLookup is non-zero, it limits the + /// number of conditions to collect. Return None if not all conditions are + /// collected successfully, or we hit the limit. + static Optional + collectControlConditions(const BasicBlock &BB, const BasicBlock &Dominator, + const DominatorTree &DT, + const PostDominatorTree &PDT, + unsigned MaxLookup = 6); + + /// Return true if there exists no control conditions required to execute ToBB + /// from FromBB. + bool isUnconditional() const { return Conditions.empty(); } + + /// Return a constant reference of Conditions. + const ConditionVectorTy &getControlConditions() const { return Conditions; } + + /// Add \p V as one of the ControlCondition in Condition with IsTrueCondition + /// equals to \p True. Return true if inserted successfully. + bool addControlCondition(ControlCondition C); + + /// Return true if for all control conditions in Conditions, there exists an + /// equivalent control condition in \p Other.Conditions. + bool isEquivalent(const ControlConditions &Other) const; + + /// Return true if \p C1 and \p C2 are equivalent. + static bool isEquivalent(const ControlCondition &C1, + const ControlCondition &C2); + +private: + ControlConditions() = default; + + static bool isEquivalent(const Value &V1, const Value &V2); + static bool isInverse(const Value &V1, const Value &V2); +}; +} // namespace + +Optional ControlConditions::collectControlConditions( + const BasicBlock &BB, const BasicBlock &Dominator, const DominatorTree &DT, + const PostDominatorTree &PDT, unsigned MaxLookup) { + assert(DT.dominates(&Dominator, &BB) && "Expecting Dominator to dominate BB"); + + ControlConditions Conditions; + unsigned NumConditions = 0; + + // BB is executed unconditional from itself. + if (&Dominator == &BB) + return Conditions; + + const BasicBlock *CurBlock = &BB; + // Walk up the dominator tree from the associated DT node for BB to the + // associated DT node for Dominator. + do { + assert(DT.getNode(CurBlock) && "Expecting a valid DT node for CurBlock"); + BasicBlock *IDom = DT.getNode(CurBlock)->getIDom()->getBlock(); + assert(DT.dominates(&Dominator, IDom) && + "Expecting Dominator to dominate IDom"); + + // Limitation: can only handle branch instruction currently. + const BranchInst *BI = dyn_cast(IDom->getTerminator()); + if (!BI) + return None; + + bool Inserted = false; + if (PDT.dominates(CurBlock, IDom)) { + LLVM_DEBUG(dbgs() << CurBlock->getName() + << " is executed unconditionally from " + << IDom->getName() << "\n"); + } else if (PDT.dominates(CurBlock, BI->getSuccessor(0))) { + LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \"" + << *BI->getCondition() << "\" is true from " + << IDom->getName() << "\n"); + Inserted = Conditions.addControlCondition( + ControlCondition(BI->getCondition(), true)); + } else if (PDT.dominates(CurBlock, BI->getSuccessor(1))) { + LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \"" + << *BI->getCondition() << "\" is false from " + << IDom->getName() << "\n"); + Inserted = Conditions.addControlCondition( + ControlCondition(BI->getCondition(), false)); + } else + return None; + + if (Inserted) + ++NumConditions; + + if (MaxLookup != 0 && NumConditions > MaxLookup) + return None; + + CurBlock = IDom; + } while (CurBlock != &Dominator); + + return Conditions; +} + +bool ControlConditions::addControlCondition(ControlCondition C) { + bool Inserted = false; + if (none_of(Conditions, [&C](ControlCondition &Exists) { + return ControlConditions::isEquivalent(C, Exists); + })) { + Conditions.push_back(C); + Inserted = true; + } + + LLVM_DEBUG(dbgs() << (Inserted ? "Inserted " : "Not inserted ") << C << "\n"); + return Inserted; +} + +bool ControlConditions::isEquivalent(const ControlConditions &Other) const { + if (Conditions.empty() && Other.Conditions.empty()) + return true; + + if (Conditions.size() != Other.Conditions.size()) + return false; + + return all_of(Conditions, [&Other](const ControlCondition &C) { + return any_of(Other.Conditions, [&C](const ControlCondition &OtherC) { + return ControlConditions::isEquivalent(C, OtherC); + }); + }); +} + +bool ControlConditions::isEquivalent(const ControlCondition &C1, + const ControlCondition &C2) { + if (C1.getInt() == C2.getInt()) { + if (isEquivalent(*C1.getPointer(), *C2.getPointer())) + return true; + } else if (isInverse(*C1.getPointer(), *C2.getPointer())) + return true; + + return false; +} + +// FIXME: Use SCEV and reuse GVN/CSE logic to check for equivalence between +// Values. +// Currently, isEquivalent rely on other passes to ensure equivalent conditions +// have the same value, e.g. GVN. +bool ControlConditions::isEquivalent(const Value &V1, const Value &V2) { + return &V1 == &V2; +} + +bool ControlConditions::isInverse(const Value &V1, const Value &V2) { + if (const CmpInst *Cmp1 = dyn_cast(&V1)) + if (const CmpInst *Cmp2 = dyn_cast(&V2)) { + if (Cmp1->getPredicate() == Cmp2->getInversePredicate() && + Cmp1->getOperand(0) == Cmp2->getOperand(0) && + Cmp1->getOperand(1) == Cmp2->getOperand(1)) + return true; + + if (Cmp1->getPredicate() == + CmpInst::getSwappedPredicate(Cmp2->getInversePredicate()) && + Cmp1->getOperand(0) == Cmp2->getOperand(1) && + Cmp1->getOperand(1) == Cmp2->getOperand(0)) + return true; + } + return false; +} + bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1, const DominatorTree &DT, const PostDominatorTree &PDT) { @@ -42,8 +227,30 @@ if (&BB0 == &BB1) return true; - return ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) || - (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0))); + if ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) || + (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0))) + return true; + + // If the set of conditions required to execute BB0 and BB1 from their common + // dominator are the same, then BB0 and BB1 are control flow equivalent. + const BasicBlock *CommonDominator = DT.findNearestCommonDominator(&BB0, &BB1); + LLVM_DEBUG(dbgs() << "The nearest common dominator of " << BB0.getName() + << " and " << BB1.getName() << " is " + << CommonDominator->getName() << "\n"); + + Optional BB0Conditions = + ControlConditions::collectControlConditions(BB0, *CommonDominator, DT, + PDT); + if (BB0Conditions == None) + return false; + + Optional BB1Conditions = + ControlConditions::collectControlConditions(BB1, *CommonDominator, DT, + PDT); + if (BB1Conditions == None) + return false; + + return BB0Conditions->isEquivalent(*BB1Conditions); } static bool reportInvalidCandidate(const Instruction &I, @@ -90,8 +297,7 @@ } bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint, - const DominatorTree &DT, - const PostDominatorTree &PDT, + DominatorTree &DT, const PostDominatorTree &PDT, DependenceInfo &DI) { // Cannot move itself before itself. if (&I == &InsertPoint) @@ -111,9 +317,9 @@ 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); + OrderedInstructions OI(&DT); + DT.updateDFSNumbers(); + const bool MoveForward = OI.dfsBefore(&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. @@ -126,7 +332,7 @@ // dominates the InsertPoint. Or else, an operand may be undefined for I. for (const Value *Op : I.operands()) if (auto *OpInst = dyn_cast(Op)) - if (&InsertPoint == OpInst || !DT.dominates(OpInst, &InsertPoint)) + if (&InsertPoint == OpInst || !OI.dominates(OpInst, &InsertPoint)) return false; } @@ -174,9 +380,10 @@ return true; } -void llvm::moveInstsBottomUp(BasicBlock &FromBB, BasicBlock &ToBB, - const DominatorTree &DT, - const PostDominatorTree &PDT, DependenceInfo &DI) { +void llvm::moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB, + DominatorTree &DT, + const PostDominatorTree &PDT, + DependenceInfo &DI) { for (auto It = ++FromBB.rbegin(); It != FromBB.rend();) { Instruction *MovePos = ToBB.getFirstNonPHIOrDbg(); Instruction &I = *It; diff --git a/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp b/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp --- a/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp +++ b/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp @@ -45,7 +45,389 @@ Test(*F, DT, PDT, DI); } -TEST(CodeMoverUtils, BasicTest) { +static BasicBlock *getBasicBlockByName(Function &F, StringRef Name) { + for (BasicBlock &BB : F) + if (BB.getName() == Name) + return &BB; + llvm_unreachable("Expected to find basic block!"); +} + +static Instruction *getInstructionByName(Function &F, StringRef Name) { + for (BasicBlock &BB : F) + for (Instruction &I : BB) + if (I.getName() == Name) + return &I; + llvm_unreachable("Expected to find instruction!"); +} + +TEST(CodeMoverUtils, IsControlFlowEquivalentSimpleTest) { + LLVMContext C; + + // void foo(int &i, bool cond1, bool cond2) { + // if (cond1) + // i = 1; + // if (cond1) + // i = 2; + // if (cond2) + // i = 3; + // } + std::unique_ptr M = + parseIR(C, R"(define void @foo(i32* %i, i1 %cond1, i1 %cond2) { + entry: + br i1 %cond1, label %if.first, label %if.first.end + if.first: + store i32 1, i32* %i, align 4 + br label %if.first.end + if.first.end: + br i1 %cond1, label %if.second, label %if.second.end + if.second: + store i32 2, i32* %i, align 4 + br label %if.second.end + if.second.end: + br i1 %cond2, label %if.third, label %if.third.end + if.third: + store i32 3, i32* %i, align 4 + br label %if.third.end + if.third.end: + ret void + })"); + run(*M, "foo", + [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, + DependenceInfo &DI) { + BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); + EXPECT_TRUE( + isControlFlowEquivalent(*FirstIfBody, *FirstIfBody, DT, PDT)); + BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second"); + EXPECT_TRUE( + isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT)); + + BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third"); + EXPECT_FALSE( + isControlFlowEquivalent(*FirstIfBody, *ThirdIfBody, DT, PDT)); + EXPECT_FALSE( + isControlFlowEquivalent(*SecondIfBody, *ThirdIfBody, DT, PDT)); + }); +} + +TEST(CodeMoverUtils, IsControlFlowEquivalentOppositeCondTest) { + LLVMContext C; + + // void foo(int &i, unsigned X, unsigned Y) { + // if (X < Y) + // i = 1; + // if (Y > X) + // i = 2; + // if (X >= Y) + // i = 3; + // else + // i = 4; + // if (X == Y) + // i = 5; + // if (Y == X) + // i = 6; + // else + // i = 7; + // if (X != Y) + // i = 8; + // else + // i = 9; + // } + std::unique_ptr M = + parseIR(C, R"(define void @foo(i32* %i, i32 %X, i32 %Y) { + entry: + %cmp1 = icmp ult i32 %X, %Y + br i1 %cmp1, label %if.first, label %if.first.end + if.first: + store i32 1, i32* %i, align 4 + br label %if.first.end + if.first.end: + %cmp2 = icmp ugt i32 %Y, %X + br i1 %cmp2, label %if.second, label %if.second.end + if.second: + store i32 2, i32* %i, align 4 + br label %if.second.end + if.second.end: + %cmp3 = icmp uge i32 %X, %Y + br i1 %cmp3, label %if.third, label %if.third.else + if.third: + store i32 3, i32* %i, align 4 + br label %if.third.end + if.third.else: + store i32 4, i32* %i, align 4 + br label %if.third.end + if.third.end: + %cmp4 = icmp eq i32 %X, %Y + br i1 %cmp4, label %if.fourth, label %if.fourth.end + if.fourth: + store i32 5, i32* %i, align 4 + br label %if.fourth.end + if.fourth.end: + %cmp5 = icmp eq i32 %Y, %X + br i1 %cmp5, label %if.fifth, label %if.fifth.else + if.fifth: + store i32 6, i32* %i, align 4 + br label %if.fifth.end + if.fifth.else: + store i32 7, i32* %i, align 4 + br label %if.fifth.end + if.fifth.end: + %cmp6 = icmp ne i32 %X, %Y + br i1 %cmp6, label %if.sixth, label %if.sixth.else + if.sixth: + store i32 8, i32* %i, align 4 + br label %if.sixth.end + if.sixth.else: + store i32 9, i32* %i, align 4 + br label %if.sixth.end + if.sixth.end: + ret void + })"); + run(*M, "foo", + [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, + DependenceInfo &DI) { + BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); + BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second"); + BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third"); + BasicBlock *ThirdElseBody = getBasicBlockByName(F, "if.third.else"); + EXPECT_TRUE( + isControlFlowEquivalent(*FirstIfBody, *ThirdElseBody, DT, PDT)); + EXPECT_TRUE( + isControlFlowEquivalent(*SecondIfBody, *ThirdElseBody, DT, PDT)); + EXPECT_FALSE( + isControlFlowEquivalent(*ThirdIfBody, *ThirdElseBody, DT, PDT)); + + BasicBlock *FourthIfBody = getBasicBlockByName(F, "if.fourth"); + BasicBlock *FifthIfBody = getBasicBlockByName(F, "if.fifth"); + BasicBlock *FifthElseBody = getBasicBlockByName(F, "if.fifth.else"); + EXPECT_FALSE( + isControlFlowEquivalent(*FifthIfBody, *FifthElseBody, DT, PDT)); + BasicBlock *SixthIfBody = getBasicBlockByName(F, "if.sixth"); + EXPECT_TRUE( + isControlFlowEquivalent(*FifthElseBody, *SixthIfBody, DT, PDT)); + BasicBlock *SixthElseBody = getBasicBlockByName(F, "if.sixth.else"); + EXPECT_TRUE( + isControlFlowEquivalent(*FourthIfBody, *SixthElseBody, DT, PDT)); + EXPECT_TRUE( + isControlFlowEquivalent(*FifthIfBody, *SixthElseBody, DT, PDT)); + }); +} + +TEST(CodeMoverUtils, IsControlFlowEquivalentCondNestTest) { + LLVMContext C; + + // void foo(int &i, bool cond1, bool cond2) { + // if (cond1) + // if (cond2) + // i = 1; + // if (cond2) + // if (cond1) + // i = 2; + // } + std::unique_ptr M = + parseIR(C, R"(define void @foo(i32* %i, i1 %cond1, i1 %cond2) { + entry: + br i1 %cond1, label %if.outer.first, label %if.first.end + if.outer.first: + br i1 %cond2, label %if.inner.first, label %if.first.end + if.inner.first: + store i32 1, i32* %i, align 4 + br label %if.first.end + if.first.end: + br i1 %cond2, label %if.outer.second, label %if.second.end + if.outer.second: + br i1 %cond1, label %if.inner.second, label %if.second.end + if.inner.second: + store i32 2, i32* %i, align 4 + br label %if.second.end + if.second.end: + ret void + })"); + run(*M, "foo", + [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, + DependenceInfo &DI) { + BasicBlock *FirstOuterIfBody = getBasicBlockByName(F, "if.outer.first"); + BasicBlock *FirstInnerIfBody = getBasicBlockByName(F, "if.inner.first"); + BasicBlock *SecondOuterIfBody = + getBasicBlockByName(F, "if.outer.second"); + BasicBlock *SecondInnerIfBody = + getBasicBlockByName(F, "if.inner.second"); + EXPECT_TRUE(isControlFlowEquivalent(*FirstInnerIfBody, + *SecondInnerIfBody, DT, PDT)); + EXPECT_FALSE(isControlFlowEquivalent(*FirstOuterIfBody, + *SecondOuterIfBody, DT, PDT)); + EXPECT_FALSE(isControlFlowEquivalent(*FirstOuterIfBody, + *SecondInnerIfBody, DT, PDT)); + EXPECT_FALSE(isControlFlowEquivalent(*FirstInnerIfBody, + *SecondOuterIfBody, DT, PDT)); + }); +} + +TEST(CodeMoverUtils, IsControlFlowEquivalentImbalanceTest) { + LLVMContext C; + + // void foo(int &i, bool cond1, bool cond2) { + // if (cond1) + // if (cond2) + // if (cond3) + // i = 1; + // if (cond2) + // if (cond3) + // i = 2; + // if (cond1) + // if (cond1) + // i = 3; + // if (cond1) + // i = 4; + // } + std::unique_ptr M = parseIR( + C, R"(define void @foo(i32* %i, i1 %cond1, i1 %cond2, i1 %cond3) { + entry: + br i1 %cond1, label %if.outer.first, label %if.first.end + if.outer.first: + br i1 %cond2, label %if.middle.first, label %if.first.end + if.middle.first: + br i1 %cond3, label %if.inner.first, label %if.first.end + if.inner.first: + store i32 1, i32* %i, align 4 + br label %if.first.end + if.first.end: + br i1 %cond2, label %if.outer.second, label %if.second.end + if.outer.second: + br i1 %cond3, label %if.inner.second, label %if.second.end + if.inner.second: + store i32 2, i32* %i, align 4 + br label %if.second.end + if.second.end: + br i1 %cond1, label %if.outer.third, label %if.third.end + if.outer.third: + br i1 %cond1, label %if.inner.third, label %if.third.end + if.inner.third: + store i32 3, i32* %i, align 4 + br label %if.third.end + if.third.end: + br i1 %cond1, label %if.fourth, label %if.fourth.end + if.fourth: + store i32 4, i32* %i, align 4 + br label %if.fourth.end + if.fourth.end: + ret void + })"); + run(*M, "foo", + [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, + DependenceInfo &DI) { + BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.inner.first"); + BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.inner.second"); + EXPECT_FALSE( + isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT)); + + BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.inner.third"); + BasicBlock *FourthIfBody = getBasicBlockByName(F, "if.fourth"); + EXPECT_TRUE( + isControlFlowEquivalent(*ThirdIfBody, *FourthIfBody, DT, PDT)); + }); +} + +TEST(CodeMoverUtils, IsControlFlowEquivalentPointerTest) { + LLVMContext C; + + // void foo(int &i, int *cond) { + // if (*cond) + // i = 1; + // if (*cond) + // i = 2; + // *cond = 1; + // if (*cond) + // i = 3; + // } + std::unique_ptr M = + parseIR(C, R"(define void @foo(i32* %i, i32* %cond) { + entry: + %0 = load i32, i32* %cond, align 4 + %tobool1 = icmp ne i32 %0, 0 + br i1 %tobool1, label %if.first, label %if.first.end + if.first: + store i32 1, i32* %i, align 4 + br label %if.first.end + if.first.end: + %1 = load i32, i32* %cond, align 4 + %tobool2 = icmp ne i32 %1, 0 + br i1 %tobool2, label %if.second, label %if.second.end + if.second: + store i32 2, i32* %i, align 4 + br label %if.second.end + if.second.end: + store i32 1, i32* %cond, align 4 + %2 = load i32, i32* %cond, align 4 + %tobool3 = icmp ne i32 %2, 0 + br i1 %tobool3, label %if.third, label %if.third.end + if.third: + store i32 3, i32* %i, align 4 + br label %if.third.end + if.third.end: + ret void + })"); + run(*M, "foo", + [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, + DependenceInfo &DI) { + BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); + BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second"); + // Limitation: if we can prove cond haven't been modify between %0 and + // %1, then we can prove FirstIfBody and SecondIfBody are control flow + // equivalent. + EXPECT_FALSE( + isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT)); + + BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third"); + EXPECT_FALSE( + isControlFlowEquivalent(*FirstIfBody, *ThirdIfBody, DT, PDT)); + EXPECT_FALSE( + isControlFlowEquivalent(*SecondIfBody, *ThirdIfBody, DT, PDT)); + }); +} + +TEST(CodeMoverUtils, IsControlFlowEquivalentNotPostdomTest) { + LLVMContext C; + + // void foo(bool cond1, bool cond2) { + // if (cond1) { + // if (cond2) + // return; + // } else + // if (cond2) + // return; + // return; + // } + std::unique_ptr M = + parseIR(C, R"(define void @foo(i1 %cond1, i1 %cond2) { + idom: + br i1 %cond1, label %succ0, label %succ1 + succ0: + br i1 %cond2, label %succ0ret, label %succ0succ1 + succ0ret: + ret void + succ0succ1: + br label %bb + succ1: + br i1 %cond2, label %succ1ret, label %succ1succ1 + succ1ret: + ret void + succ1succ1: + br label %bb + bb: + ret void + })"); + run(*M, "foo", + [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, + DependenceInfo &DI) { + BasicBlock &Idom = F.front(); + assert(Idom.getName() == "idom" && "Expecting BasicBlock idom"); + BasicBlock &BB = F.back(); + assert(BB.getName() == "bb" && "Expecting BasicBlock bb"); + EXPECT_FALSE(isControlFlowEquivalent(Idom, BB, DT, PDT)); + }); +} + +TEST(CodeMoverUtils, IsSafeToMoveTest1) { LLVMContext C; // void safecall() noexcept willreturn nosync; @@ -65,73 +447,59 @@ // } // } std::unique_ptr 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"); + C, R"(define void @foo(i32* noalias %A, i32* noalias %B, i32* noalias %C + , i64 %N) { + entry: + %X = sdiv i64 1, %N + call void @safecall() + %cmp1 = icmp slt i64 0, %N + call void @unsafecall1() + call void @unsafecall2() + br i1 %cmp1, label %for.body, label %for.end + for.body: + %i = phi i64 [ 0, %entry ], [ %inc, %for.body ] + %arrayidx_A5 = getelementptr inbounds i32, i32* %A, i64 5 + store i32 5, i32* %arrayidx_A5, align 4 + %arrayidx_A = getelementptr inbounds i32, i32* %A, i64 %i + store i32 0, i32* %arrayidx_A, align 4 + %load1 = load i32, i32* %arrayidx_A, align 4 + %arrayidx_B = getelementptr inbounds i32, i32* %B, i64 %i + store i32 %load1, i32* %arrayidx_B, align 4 + %load2 = load i32, i32* %arrayidx_A, align 4 + %arrayidx_C = getelementptr inbounds i32, i32* %C, i64 %i + store i32 %load2, i32* %arrayidx_C, align 4 + %arrayidx_A6 = getelementptr inbounds i32, i32* %A, i64 6 + store i32 6, i32* %arrayidx_A6, align 4 + %inc = add nsw i64 %i, 1 + %cmp = icmp slt i64 %inc, %N + br i1 %cmp, label %for.body, label %for.end + for.end: + ret void + } + declare void @safecall() nounwind nosync willreturn + declare void @unsafecall1() + declare void @unsafecall2())"); 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"); + BasicBlock *Entry = getBasicBlockByName(F, "entry"); Instruction *CI_safecall = Entry->front().getNextNode(); assert(isa(CI_safecall) && "Expecting CI_safecall to be a CallInst"); Instruction *CI_unsafecall = CI_safecall->getNextNode()->getNextNode(); assert(isa(CI_unsafecall) && "Expecting CI_unsafecall to be a CallInst"); - BasicBlock *ForBody = &*(FI++); - assert(ForBody->getName() == "for.body" && - "Expecting BasicBlock for.body"); + BasicBlock *ForBody = getBasicBlockByName(F, "for.body"); Instruction &PN = ForBody->front(); assert(isa(PN) && "Expecting PN to be a PHINode"); - Instruction *SI_A5 = PN.getNextNode()->getNextNode(); - assert(isa(SI_A5) && - SI_A5->getOperand(1)->getName() == "arrayidx_A5" && - "Expecting store to arrayidx_A5"); - Instruction *SI = SI_A5->getNextNode()->getNextNode(); - assert(isa(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_A5 = + getInstructionByName(F, "arrayidx_A5")->getNextNode(); + Instruction *SI = getInstructionByName(F, "arrayidx_A")->getNextNode(); + Instruction *LI1 = getInstructionByName(F, "load1"); + Instruction *LI2 = getInstructionByName(F, "load2"); Instruction *SI_A6 = - LI2->getNextNode()->getNextNode()->getNextNode()->getNextNode(); - assert(isa(SI_A6) && - SI_A6->getOperand(1)->getName() == "arrayidx_A6" && - "Expecting store to arrayidx_A6"); + getInstructionByName(F, "arrayidx_A6")->getNextNode(); // Can move after CI_safecall, as it does not throw, not synchronize, or // must return. @@ -180,3 +548,68 @@ EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, PDT, DI)); }); } + +TEST(CodeMoverUtils, IsSafeToMoveTest2) { + LLVMContext C; + + std::unique_ptr M = + parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) { + entry: + br i1 %cond, label %if.then.first, label %if.end.first + if.then.first: + %add = add i32 %op0, %op1 + %user = add i32 %add, 1 + br label %if.end.first + if.end.first: + br i1 %cond, label %if.then.second, label %if.end.second + if.then.second: + %sub_op0 = add i32 %op0, 1 + %sub = sub i32 %sub_op0, %op1 + br label %if.end.second + if.end.second: + ret void + })"); + + run(*M, "foo", + [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, + DependenceInfo &DI) { + Instruction *AddInst = getInstructionByName(F, "add"); + Instruction *SubInst = getInstructionByName(F, "sub"); + + // Cannot move as %user uses %add and %sub doesn't dominates %user. + EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, PDT, DI)); + + // Cannot move as %sub_op0 is an operand of %sub and %add doesn't + // dominates %sub_op0. + EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, PDT, DI)); + }); +} + +TEST(CodeMoverUtils, IsSafeToMoveTest3) { + LLVMContext C; + + std::unique_ptr M = parseIR(C, R"(define void @foo(i64 %N) { + entry: + br label %for.body + for.body: + %i = phi i64 [ 0, %entry ], [ %inc, %for.latch ] + %inc = add nsw i64 %i, 1 + br label %for.latch + for.latch: + %cmp = icmp slt i64 %inc, %N + br i1 %cmp, label %for.body, label %for.end + for.end: + ret void + })"); + + run(*M, "foo", + [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, + DependenceInfo &DI) { + Instruction *IncInst = getInstructionByName(F, "inc"); + Instruction *CmpInst = getInstructionByName(F, "cmp"); + + // Can move as the incoming block of %inc for %i (%for.latch) dominated + // by %cmp. + EXPECT_TRUE(isSafeToMoveBefore(*IncInst, *CmpInst, DT, PDT, DI)); + }); +}