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 @@ -36,14 +36,197 @@ return isControlFlowEquivalent(*I0.getParent(), *I1.getParent(), DT, PDT); } +class Conditions { + SmallVector TrueConditions; + SmallVector FalseConditions; + +public: + bool empty() const { + return TrueConditions.empty() && FalseConditions.empty(); + } + + const SmallVector &getTrueConditions() const { + return TrueConditions; + } + + const SmallVector &getFalseConditions() const { + return FalseConditions; + } + + void addCondition(const Value &V, const bool True) { + if (True) + TrueConditions.push_back(&V); + else + FalseConditions.push_back(&V); + } + + bool isEquivalent(const Conditions &Other) { + if (empty() && Other.empty()) + return true; + + if (empty() || Other.empty()) + return false; + + // For each value in \p Conds1 check to see if a corresponding value can be + // found in \p Conds2 or \p OppositeConds2. When we examine the values in \p + // OppositeConds2, we consider the inverse predicate of the compare to + // identify compare instructions that evaluate to the same condition. + auto IsDifferent = + [](const SmallVectorImpl &Conds1, + const SmallVectorImpl &Conds2, + const SmallVectorImpl &OppositeConds2) { + // For each Value in Conds1, if there does not exist an equivalent in + // Conds2 or an inverse in OppositeConds2, then we found a Value in + // Conds1 that does not have a corresponding value in Cond2 or + // OppositeConds2. So we return true to indicate that there exists a + // difference. + for (const Value *V1 : Conds1) + if (llvm::none_of( + Conds2, + [&](const Value *V2) { return isEquivalent(*V1, *V2); }) && + llvm::none_of(OppositeConds2, [&](const Value *V2) { + return isInverse(*V1, *V2); + })) + return true; + return false; + }; + + return (!IsDifferent(TrueConditions, Other.getTrueConditions(), + Other.getFalseConditions()) && + !IsDifferent(FalseConditions, Other.getFalseConditions(), + Other.getTrueConditions()) && + !IsDifferent(Other.getTrueConditions(), TrueConditions, + FalseConditions) && + !IsDifferent(Other.getFalseConditions(), FalseConditions, + TrueConditions)); + } + +private: + static bool isEquivalent(const Value &V1, const Value &V2) { + if (&V1 == &V2) + return true; + + if (const Instruction *I1 = dyn_cast(&V1)) + if (const Instruction *I2 = dyn_cast(&V2)) { + // The result of a LoadInst or CallInst can be different at different + // point in time. + if (isa(I1) || isa(I1)) + 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; + + return false; + } + + static bool 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; + } +}; + +/// Collect all conditions required to execute \p BB from \p CommonDominator, +/// and store the results in \p Conditions. Return true if all conditions are +/// collected successfully. +static bool collectDependingConditions(const BasicBlock &BB, + const BasicBlock &CommonDominator, + const DominatorTree &DT, + const PostDominatorTree &PDT, + Conditions &Conditions) { + assert(DT.dominates(&CommonDominator, &BB) && + "Expecting CommonDominator to dominate BB"); + assert(Conditions.empty() && "Expecting an empty Conditions"); + + // BB is executed unconditional from itself. + if (&CommonDominator == &BB) + return true; + + const BasicBlock *CurBlock = &BB; + // Walk up the dominator tree from the associated DT node for BB to the + // associated DT node for CommonDominator. + do { + assert(DT.getNode(CurBlock) && "Expecting a valid DT node for CurBlock"); + BasicBlock *IDom = DT.getNode(CurBlock)->getIDom()->getBlock(); + assert(DT.dominates(&CommonDominator, IDom) && + "Expecting CommonDominator to dominate IDom"); + + // Limitation: can only handle branch instruction currently. + const BranchInst *BI = dyn_cast(IDom->getTerminator()); + if (!BI) + return false; + + if (PDT.dominates(CurBlock, IDom)) { + LLVM_DEBUG(dbgs() << CurBlock->getName() + << " is executed unconditionally from " + << IDom->getName() << "\n"); + } else if (DT.dominates(BI->getSuccessor(0), CurBlock)) { + LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \"" + << *BI->getCondition() << "\" is true from " + << IDom->getName() << "\n"); + Conditions.addCondition(*BI->getCondition(), true); + } else { + assert(DT.dominates(BI->getSuccessor(1), CurBlock) && + "Expecting the false block of BI to dominate IDom"); + LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \"" + << *BI->getCondition() << "\" is false from " + << IDom->getName() << "\n"); + Conditions.addCondition(*BI->getCondition(), false); + } + + CurBlock = IDom; + } while (CurBlock != &CommonDominator); + + return true; +} + bool llvm::isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1, const DominatorTree &DT, const PostDominatorTree &PDT) { 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"); + + Conditions BB0Conditions; + if (!collectDependingConditions(BB0, *CommonDominator, DT, PDT, + BB0Conditions)) + return false; + + Conditions BB1Conditions; + if (!collectDependingConditions(BB1, *CommonDominator, DT, PDT, + BB1Conditions)) + 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,439 @@ 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, IsSafeToMoveTest) { LLVMContext C; // void safecall() noexcept willreturn nosync;