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 @@ -14,6 +14,9 @@ #ifndef LLVM_TRANSFORMS_UTILS_CODEMOVERUTILS_H #define LLVM_TRANSFORMS_UTILS_CODEMOVERUTILS_H +#include "llvm/ADT/Optional.h" +#include + namespace llvm { class BasicBlock; @@ -21,21 +24,98 @@ class DominatorTree; class Instruction; class PostDominatorTree; +class Value; + +/// Represent a control condition. A control condition is a condition of a +/// terminaotr to decide which successors to execute. +struct ControlCondition { + ControlCondition(const Value *V, bool IsTrueCondition) + : V(V), IsTrueCondition(IsTrueCondition) {} + + // The condition of the terminator. + const Value *V; + + // The control condition of a basic block has IsTrueCondition equals to 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 IsTrueCondition equals + // to true, while %cond is a control condition of bb1 with IsTrueCondition + // equals to false. + const bool IsTrueCondition; +}; +raw_ostream &operator<<(raw_ostream &OS, const ControlCondition &C); + +/// The hasher of ControlConditions. +struct ControlConditionsHasher { + bool operator()(const ControlCondition &C) const { + return ((std::hash()(C.V) ^ + (std::hash()(C.IsTrueCondition) << 1)) >> + 1); + } +}; + +/// The binary predicate to check if two ControlConditions are considered +/// equivalent. +struct ControlConditionsComparator { + bool operator()(const ControlCondition &C1, const ControlCondition &C2) const; + + static bool isEquivalent(const Value &V1, const Value &V2); + static bool isInverse(const Value &V1, const Value &V2); +}; + +/// Represent a set of control conditions required to execute ToBB from FromBB. +class ControlConditions { + using SelfTy = std::unordered_set; + /// A unordered_set of control conditions. + SelfTy Conditions; + + const BasicBlock &FromBB; + const BasicBlock &ToBB; + +public: + /// Return a ControlConditions which stores all conditions required to execute + /// \p BB from \p Dominator. Return None if not all conditions are collected + /// successfully. + static Optional + collectControlConditions(const BasicBlock &BB, const BasicBlock &Dominator, + const DominatorTree &DT, + const PostDominatorTree &PDT); + + /// 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; } + + /// Return the basic block range associated with this ControlConditions. + std::pair getRange() const { + return std::make_pair(&FromBB, &ToBB); + } + + /// 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; + +private: + ControlConditions(const BasicBlock &FromBB, const BasicBlock &ToBB) + : FromBB(FromBB), ToBB(ToBB) {} +}; /// 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); 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 @@ -30,6 +30,153 @@ STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported"); STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported"); +raw_ostream &llvm::operator<<(raw_ostream &OS, const ControlCondition &C) { + OS << "[" << *C.V << ", " << (C.IsTrueCondition ? "true" : "false") << "]"; + return OS; +} + +// FIXME: Reuse GVN/CSE logic to check for equivalence between Values. +bool llvm::ControlConditionsComparator::isEquivalent(const Value &V1, + const Value &V2) { + if (&V1 == &V2) + return true; + + const Instruction *I1 = dyn_cast(&V1); + const Instruction *I2 = dyn_cast(&V2); + if (!I1 || !I2) + return false; + + // The result of a LoadInst or CallBase can be different at different + // point in time. + // TODO: Add handle of invariant loads and readnone calls. + if (isa(I1) || isa(I1)) + return false; + + if (I1->getOpcode() != I2->getOpcode() || + I1->getNumOperands() != I2->getNumOperands() || + I1->getType() != I2->getType()) + return false; + + if (I1->isIdenticalTo(I2)) + return true; + + // Cmp1 and Cmp2 are the same, but the predicates have been swapped. + if (const CmpInst *Cmp1 = dyn_cast(&V1)) + if (const CmpInst *Cmp2 = dyn_cast(&V2)) + if (Cmp1->getPredicate() == Cmp2->getSwappedPredicate() && + Cmp1->getOperand(0) == Cmp2->getOperand(1) && + Cmp1->getOperand(1) == Cmp2->getOperand(0)) + return true; + + // TODO: Add handle of other kinds of Values, e.g. boolean binary operations. + + for (const Value *Op1 : I1->operands()) + for (const Value *Op2 : I2->operands()) + if (!isEquivalent(*Op1, *Op2)) + return false; + + return true; +} + +bool llvm::ControlConditionsComparator::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::ControlConditionsComparator::operator()( + const ControlCondition &C1, const ControlCondition &C2) const { + if (C1.IsTrueCondition == C2.IsTrueCondition) { + if (isEquivalent(*C1.V, *C2.V)) + return true; + } else if (isInverse(*C1.V, *C2.V)) + return true; + + return false; +} + +Optional +llvm::ControlConditions::collectControlConditions( + const BasicBlock &BB, const BasicBlock &Dominator, const DominatorTree &DT, + const PostDominatorTree &PDT) { + assert(DT.dominates(&Dominator, &BB) && "Expecting Dominator to dominate BB"); + + ControlConditions Conditions(Dominator, BB); + + // 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; + + 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"); + 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"); + Conditions.addControlCondition( + ControlCondition(BI->getCondition(), false)); + } else + return None; + + CurBlock = IDom; + } while (CurBlock != &Dominator); + + return Conditions; +} + +bool llvm::ControlConditions::addControlCondition(ControlCondition C) { + bool Inserted = Conditions.insert(C).second; + LLVM_DEBUG(dbgs() << (Inserted ? "Inserted " : "Not inserted ") << C << "\n"); + return Inserted; +} + +bool llvm::ControlConditions::isEquivalent( + const ControlConditions &Other) const { + if (Conditions.empty() && Other.getControlConditions().empty()) + return true; + + if (Conditions.size() != Other.getControlConditions().size()) + return false; + + return llvm::all_of(Conditions, [&Other](const ControlCondition &C) { + return Other.getControlConditions().count(C); + }); +} + bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1, const DominatorTree &DT, const PostDominatorTree &PDT) { @@ -42,8 +189,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, 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,481 @@ 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" + " %tobool11 = trunc i8 %frombool1 to i1\n" + " br i1 %tobool11, 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" + " %tobool12 = trunc i8 %frombool1 to i1\n" + " br i1 %tobool12, 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"); + 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)); + + 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"); + EXPECT_TRUE( + isControlFlowEquivalent(*FourthIfBody, *FifthIfBody, DT, PDT)); + 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" + " %tobool11 = trunc i8 %frombool1 to i1\n" + " br i1 %tobool11, 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.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" + " %tobool12 = trunc i8 %frombool1 to i1\n" + " br i1 %tobool12, 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" + " %tobool11 = trunc i8 %frombool1 to i1\n" + " br i1 %tobool11, 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" + " %tobool131 = trunc i8 %frombool1 to i1\n" + " br i1 %tobool131, label %if.outer.third, label %if.third.end\n" + "if.outer.third:\n" + " %tobool132 = trunc i8 %frombool1 to i1\n" + " br i1 %tobool132, 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" + " %tobool14 = trunc i8 %frombool1 to i1\n" + " br i1 %tobool14, 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;