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 @@ -20,36 +20,35 @@ class DependenceInfo; class DominatorTree; class Instruction; +class OrderedInstructions; 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, - 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); + DominatorTree &DT, const PostDominatorTree &PDT, + DependenceInfo &DI, const OrderedInstructions &OI); + +/// 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, + const OrderedInstructions &OI); } // 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 @@ -50,6 +50,7 @@ #include "llvm/Analysis/DomTreeUpdater.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" +#include "llvm/Analysis/OrderedInstructions.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" @@ -1118,7 +1119,8 @@ /// 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); + OrderedInstructions OI(&DT); + moveInstructionsToTheBeginning(*FC0.Latch, *FC1.Latch, DT, PDT, DI, OI); 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,187 @@ 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; +raw_ostream &operator<<(raw_ostream &OS, const ControlCondition &C) { + OS << "[" << *C.getPointer() << ", " << (C.getInt() ? "true" : "false") + << "]"; + return OS; +} + +/// Represent a set of control conditions required to execute ToBB from FromBB. +class ControlConditions { + using SelfTy = SmallVector; + + /// A SmallVector of control conditions. + SelfTy 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 SelfTy &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 +225,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,9 +295,9 @@ } bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint, - const DominatorTree &DT, - const PostDominatorTree &PDT, - DependenceInfo &DI) { + DominatorTree &DT, const PostDominatorTree &PDT, + DependenceInfo &DI, + const OrderedInstructions &OI) { // Cannot move itself before itself. if (&I == &InsertPoint) return false; @@ -111,9 +316,7 @@ 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); + const bool MoveForward = OI.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. @@ -174,16 +377,18 @@ 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, + const OrderedInstructions &OI) { for (auto It = ++FromBB.rbegin(); It != FromBB.rend();) { Instruction *MovePos = ToBB.getFirstNonPHIOrDbg(); Instruction &I = *It; // Increment the iterator before modifying FromBB. ++It; - if (isSafeToMoveBefore(I, *MovePos, DT, PDT, DI)) + if (isSafeToMoveBefore(I, *MovePos, DT, PDT, DI, OI)) I.moveBefore(MovePos); } } 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 @@ -10,6 +10,7 @@ #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/DependenceAnalysis.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/OrderedInstructions.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/AsmParser/Parser.h" @@ -45,7 +46,465 @@ Test(*F, DT, PDT, DI); } -TEST(CodeMoverUtils, BasicTest) { +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, "define void @foo(i32* dereferenceable(4) %i, i1 zeroext " + "%cond1, i1 zeroext %cond2) {\n" + "entry:\n" + " %frombool1 = zext i1 %cond1 to i8\n" + " %frombool2 = zext i1 %cond2 to i8\n" + " %tobool1 = trunc i8 %frombool1 to i1\n" + " br i1 %tobool1, label %if.first, label %if.first.end\n" + "if.first:\n" + " store i32 1, i32* %i, align 4\n" + " br label %if.first.end\n" + "if.first.end:\n" + " br i1 %tobool1, label %if.second, label %if.second.end\n" + "if.second:\n" + " store i32 2, i32* %i, align 4\n" + " br label %if.second.end\n" + "if.second.end:\n" + " %tobool2 = trunc i8 %frombool2 to i1\n" + " br i1 %tobool2, label %if.third, label %if.third.end\n" + "if.third:\n" + " store i32 3, i32* %i, align 4\n" + " br label %if.third.end\n" + "if.third.end:\n" + " ret void\n" + "}\n"); + run(*M, "foo", + [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, + DependenceInfo &DI) { + Function::iterator FI = F.begin(); + FI++; + BasicBlock *FirstIfBody = &*(FI++); + assert(FirstIfBody->getName() == "if.first" && + "Expecting BasicBlock if.first"); + EXPECT_TRUE( + isControlFlowEquivalent(*FirstIfBody, *FirstIfBody, DT, PDT)); + FI++; + BasicBlock *SecondIfBody = &*(FI++); + assert(SecondIfBody->getName() == "if.second" && + "Expecting BasicBlock if.second"); + EXPECT_TRUE( + isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT)); + + FI++; + BasicBlock *ThirdIfBody = &*(FI++); + assert(ThirdIfBody->getName() == "if.third" && + "Expecting BasicBlock 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, "define void @foo(i32* dereferenceable(4) %i, i32 zeroext %X, " + "i32 zeroext %Y) {\n" + "entry:\n" + " %cmp1 = icmp ult i32 %X, %Y\n" + " br i1 %cmp1, label %if.first, label %if.first.end\n" + "if.first:\n" + " store i32 1, i32* %i, align 4\n" + " br label %if.first.end\n" + "if.first.end:\n" + " %cmp2 = icmp ugt i32 %Y, %X\n" + " br i1 %cmp2, label %if.second, label %if.second.end\n" + "if.second:\n" + " store i32 2, i32* %i, align 4\n" + " br label %if.second.end\n" + "if.second.end:\n" + " %cmp3 = icmp uge i32 %X, %Y\n" + " br i1 %cmp3, label %if.third, label %if.third.else\n" + "if.third:\n" + " store i32 3, i32* %i, align 4\n" + " br label %if.third.end\n" + "if.third.else:\n" + " store i32 4, i32* %i, align 4\n" + " br label %if.third.end\n" + "if.third.end:\n" + " %cmp4 = icmp eq i32 %X, %Y\n" + " br i1 %cmp4, label %if.fourth, label %if.fourth.end\n" + "if.fourth:\n" + " store i32 5, i32* %i, align 4\n" + " br label %if.fourth.end\n" + "if.fourth.end:\n" + " %cmp5 = icmp eq i32 %Y, %X\n" + " br i1 %cmp5, label %if.fifth, label %if.fifth.else\n" + "if.fifth:\n" + " store i32 6, i32* %i, align 4\n" + " br label %if.fifth.end\n" + "if.fifth.else:\n" + " store i32 7, i32* %i, align 4\n" + " br label %if.fifth.end\n" + "if.fifth.end:\n" + " %cmp6 = icmp ne i32 %X, %Y\n" + " br i1 %cmp6, label %if.sixth, label %if.sixth.else\n" + "if.sixth:\n" + " store i32 8, i32* %i, align 4\n" + " br label %if.sixth.end\n" + "if.sixth.else:\n" + " store i32 9, i32* %i, align 4\n" + " br label %if.sixth.end\n" + "if.sixth.end:\n" + " ret void\n" + "}\n"); + run(*M, "foo", + [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, + DependenceInfo &DI) { + Function::iterator FI = F.begin(); + FI++; + BasicBlock *FirstIfBody = &*(FI++); + assert(FirstIfBody->getName() == "if.first" && + "Expecting BasicBlock if.first"); + FI++; + BasicBlock *SecondIfBody = &*(FI++); + assert(SecondIfBody->getName() == "if.second" && + "Expecting BasicBlock if.second"); + FI++; + BasicBlock *ThirdIfBody = &*(FI++); + assert(ThirdIfBody->getName() == "if.third" && + "Expecting BasicBlock if.third"); + BasicBlock *ThirdElseBody = &*(FI++); + assert(ThirdElseBody->getName() == "if.third.else" && + "Expecting BasicBlock if.third.else"); + EXPECT_TRUE( + isControlFlowEquivalent(*FirstIfBody, *ThirdElseBody, DT, PDT)); + EXPECT_TRUE( + isControlFlowEquivalent(*SecondIfBody, *ThirdElseBody, DT, PDT)); + EXPECT_FALSE( + isControlFlowEquivalent(*ThirdIfBody, *ThirdElseBody, DT, PDT)); + + FI++; + BasicBlock *FourthIfBody = &*(FI++); + assert(FourthIfBody->getName() == "if.fourth" && + "Expecting BasicBlock if.fourth"); + FI++; + BasicBlock *FifthIfBody = &*(FI++); + assert(FifthIfBody->getName() == "if.fifth" && + "Expecting BasicBlock if.fifth"); + BasicBlock *FifthElseBody = &*(FI++); + assert(FifthElseBody->getName() == "if.fifth.else" && + "Expecting BasicBlock if.fifth.else"); + EXPECT_FALSE( + isControlFlowEquivalent(*FifthIfBody, *FifthElseBody, DT, PDT)); + FI++; + BasicBlock *SixthIfBody = &*(FI++); + assert(SixthIfBody->getName() == "if.sixth" && + "Expecting BasicBlock if.sixth"); + EXPECT_TRUE( + isControlFlowEquivalent(*FifthElseBody, *SixthIfBody, DT, PDT)); + BasicBlock *SixthElseBody = &*(FI++); + assert(SixthElseBody->getName() == "if.sixth.else" && + "Expecting BasicBlock 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, "define void @foo(i32* dereferenceable(4) %i, i1 zeroext %cond1, i1 " + "zeroext %cond2) {\n" + "entry:\n" + " %frombool1 = zext i1 %cond1 to i8\n" + " %frombool2 = zext i1 %cond2 to i8\n" + " %tobool1 = trunc i8 %frombool1 to i1\n" + " %tobool2 = trunc i8 %frombool2 to i1\n" + " br i1 %tobool1, label %if.outer.first, label %if.first.end\n" + "if.outer.first:\n" + " br i1 %tobool2, label %if.inner.first, label %if.first.end\n" + "if.inner.first:\n" + " store i32 1, i32* %i, align 4\n" + " br label %if.first.end\n" + "if.first.end:\n" + " br i1 %tobool2, label %if.outer.second, label %if.second.end\n" + "if.outer.second:\n" + " br i1 %tobool1, label %if.inner.second, label %if.second.end\n" + "if.inner.second:\n" + " store i32 2, i32* %i, align 4\n" + " br label %if.second.end\n" + "if.second.end:\n" + " ret void\n" + "}\n"); + run(*M, "foo", + [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, + DependenceInfo &DI) { + Function::iterator FI = F.begin(); + FI++; + BasicBlock *FirstOuterIfBody = &*(FI++); + assert(FirstOuterIfBody->getName() == "if.outer.first" && + "Expecting BasicBlock if.outer.first"); + BasicBlock *FirstInnerIfBody = &*(FI++); + assert(FirstInnerIfBody->getName() == "if.inner.first" && + "Expecting BasicBlock if.inner.first"); + FI++; + BasicBlock *SecondOuterIfBody = &*(FI++); + assert(SecondOuterIfBody->getName() == "if.outer.second" && + "Expecting BasicBlock if.outer.second"); + BasicBlock *SecondInnerIfBody = &*(FI++); + assert(SecondInnerIfBody->getName() == "if.inner.second" && + "Expecting BasicBlock 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, "define void @foo(i32* dereferenceable(4) %i, i1 zeroext " + "%cond1, i1 zeroext %cond2, i1 zeroext %cond3) {\n" + "entry:\n" + " %frombool1 = zext i1 %cond1 to i8\n" + " %frombool2 = zext i1 %cond2 to i8\n" + " %frombool3 = zext i1 %cond3 to i8\n" + " %tobool1 = trunc i8 %frombool1 to i1\n" + " br i1 %tobool1, label %if.outer.first, label %if.first.end\n" + "if.outer.first:\n" + " %tobool21 = trunc i8 %frombool2 to i1\n" + " br i1 %tobool21, label %if.middle.first, label %if.first.end\n" + "if.middle.first:\n" + " %tobool31 = trunc i8 %frombool3 to i1\n" + " br i1 %tobool31, label %if.inner.first, label %if.first.end\n" + "if.inner.first:\n" + " store i32 1, i32* %i, align 4\n" + " br label %if.first.end\n" + "if.first.end:\n" + " %tobool22 = trunc i8 %frombool2 to i1\n" + " br i1 %tobool22, label %if.outer.second, label %if.second.end\n" + "if.outer.second:\n" + " %tobool32 = trunc i8 %frombool3 to i1\n" + " br i1 %tobool32, label %if.inner.second, label %if.second.end\n" + "if.inner.second:\n" + " store i32 2, i32* %i, align 4\n" + " br label %if.second.end\n" + "if.second.end:\n" + " br i1 %tobool1, label %if.outer.third, label %if.third.end\n" + "if.outer.third:\n" + " br i1 %tobool1, label %if.inner.third, label %if.third.end\n" + "if.inner.third:\n" + " store i32 3, i32* %i, align 4\n" + " br label %if.third.end\n" + "if.third.end:\n" + " br i1 %tobool1, label %if.fourth, label %if.fourth.end\n" + "if.fourth:\n" + " store i32 4, i32* %i, align 4\n" + " br label %if.fourth.end\n" + "if.fourth.end:\n" + " ret void\n" + "}\n"); + run(*M, "foo", + [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, + DependenceInfo &DI) { + Function::iterator FI = F.begin(); + FI++; // entry + FI++; // if.outer.first + FI++; // if.middle.first + BasicBlock *FirstIfBody = &*(FI++); + assert(FirstIfBody->getName() == "if.inner.first" && + "Expecting BasicBlock if.inner.first"); + FI++; // if.first.end + FI++; // if.outer.second + BasicBlock *SecondIfBody = &*(FI++); + assert(SecondIfBody->getName() == "if.inner.second" && + "Expecting BasicBlock if.inner.second"); + EXPECT_FALSE( + isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT)); + + FI++; // if.second.end + FI++; // if.outer.third + BasicBlock *ThirdIfBody = &*(FI++); + assert(ThirdIfBody->getName() == "if.inner.third" && + "Expecting BasicBlock if.inner.third"); + FI++; // if.third.end + BasicBlock *FourthIfBody = &*(FI++); + assert(FourthIfBody->getName() == "if.fourth" && + "Expecting BasicBlock 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, "define void @foo(i32* dereferenceable(4) %i, i32* %cond) {\n" + "entry:\n" + " %0 = load i32, i32* %cond, align 4\n" + " %tobool1 = icmp ne i32 %0, 0\n" + " br i1 %tobool1, label %if.first, label %if.first.end\n" + "if.first:\n" + " store i32 1, i32* %i, align 4\n" + " br label %if.first.end\n" + "if.first.end:\n" + " %1 = load i32, i32* %cond, align 4\n" + " %tobool2 = icmp ne i32 %1, 0\n" + " br i1 %tobool2, label %if.second, label %if.second.end\n" + "if.second:\n" + " store i32 2, i32* %i, align 4\n" + " br label %if.second.end\n" + "if.second.end:\n" + " store i32 1, i32* %cond, align 4\n" + " %2 = load i32, i32* %cond, align 4\n" + " %tobool3 = icmp ne i32 %2, 0\n" + " br i1 %tobool3, label %if.third, label %if.third.end\n" + "if.third:\n" + " store i32 3, i32* %i, align 4\n" + " br label %if.third.end\n" + "if.third.end:\n" + " ret void\n" + "}\n"); + run(*M, "foo", + [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, + DependenceInfo &DI) { + Function::iterator FI = F.begin(); + FI++; + BasicBlock *FirstIfBody = &*(FI++); + assert(FirstIfBody->getName() == "if.first" && + "Expecting BasicBlock if.first"); + FI++; + BasicBlock *SecondIfBody = &*(FI++); + assert(SecondIfBody->getName() == "if.second" && + "Expecting BasicBlock 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)); + + FI++; + BasicBlock *ThirdIfBody = &*(FI++); + assert(ThirdIfBody->getName() == "if.third" && + "Expecting BasicBlock 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, "define void @foo(i1 %cond1, i1 %cond2) {\n" + "idom:\n" + " br i1 %cond1, label %succ0, label %succ1\n" + "succ0:\n" + " br i1 %cond2, label %succ0ret, label %succ0succ1\n" + "succ0ret:\n" + " ret void\n" + "succ0succ1:\n" + " br label %bb\n" + "succ1:\n" + " br i1 %cond2, label %succ1ret, label %succ1succ1\n" + "succ1ret:\n" + " ret void\n" + "succ1succ1:\n" + " br label %bb\n" + "bb:\n" + " ret void\n" + "}\n"); + 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, IsSafeToMoveTest) { LLVMContext C; // void safecall() noexcept willreturn nosync; @@ -133,50 +592,55 @@ SI_A6->getOperand(1)->getName() == "arrayidx_A6" && "Expecting store to arrayidx_A6"); + OrderedInstructions OI(&DT); + // 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)); + *CI_safecall->getNextNode(), DT, PDT, DI, + OI)); // Cannot move CI_unsafecall, as it may throw. EXPECT_FALSE(isSafeToMoveBefore(*CI_unsafecall->getNextNode(), - *CI_unsafecall, DT, PDT, DI)); + *CI_unsafecall, DT, PDT, DI, OI)); // Moving instruction to non control flow equivalent places are not // supported. - EXPECT_FALSE( - isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, PDT, DI)); + EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, + PDT, DI, OI)); // Moving PHINode is not supported. EXPECT_FALSE(isSafeToMoveBefore(PN, *PN.getNextNode()->getNextNode(), - DT, PDT, DI)); + DT, PDT, DI, OI)); // Cannot move non-PHINode before PHINode. - EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, DT, PDT, DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*PN.getNextNode(), PN, DT, PDT, DI, OI)); // Moving Terminator is not supported. EXPECT_FALSE(isSafeToMoveBefore(*Entry->getTerminator(), - *PN.getNextNode(), DT, PDT, DI)); + *PN.getNextNode(), DT, PDT, DI, OI)); // Cannot move %arrayidx_A after SI, as SI is its user. EXPECT_FALSE(isSafeToMoveBefore(*SI->getPrevNode(), *SI->getNextNode(), - DT, PDT, DI)); + DT, PDT, DI, OI)); // Cannot move SI before %arrayidx_A, as %arrayidx_A is its operand. - EXPECT_FALSE(isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, PDT, DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, PDT, DI, OI)); // Cannot move LI2 after SI_A6, as there is a flow dependence. EXPECT_FALSE( - isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, PDT, DI)); + isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, PDT, DI, OI)); // Cannot move SI after LI1, as there is a anti dependence. - EXPECT_FALSE(isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, PDT, DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, PDT, DI, OI)); // Cannot move SI_A5 after SI, as there is a output dependence. - EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, DT, PDT, DI)); + EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, DT, PDT, DI, OI)); // Can move LI2 before LI1, as there is only an input dependence. - EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, PDT, DI)); + EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, PDT, DI, OI)); }); }