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,8 @@ #ifndef LLVM_TRANSFORMS_UTILS_CODEMOVERUTILS_H #define LLVM_TRANSFORMS_UTILS_CODEMOVERUTILS_H +#include + namespace llvm { class BasicBlock; @@ -21,6 +23,59 @@ class DominatorTree; class Instruction; class PostDominatorTree; +class Value; + +struct ControlCondition { + ControlCondition(const Value *V, bool IsTrueCondition) + : V(V), IsTrueCondition(IsTrueCondition) {} + + ControlCondition &operator=(const ControlCondition &C) { + V = C.V; + IsTrueCondition = C.IsTrueCondition; + return *this; + } + + const Value *V; + bool IsTrueCondition; +}; + +struct ControlConditionsHasher { + bool operator()(const ControlCondition &C) const { + return ((std::hash()(C.V) ^ + (std::hash()(C.IsTrueCondition) << 1)) >> + 1); + } +}; + +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); +}; + +class ControlConditions { + using SelfTy = std::unordered_set; + SelfTy Conditions; + +public: + bool empty() const { return Conditions.empty(); } + + const SelfTy &getControlConditions() const { return Conditions; } + + bool addControlCondition(const Value &V, const bool True); + + bool isEquivalent(const ControlConditions &Other); +}; + +/// Collect all conditions required to execute \p BB from \p Dominator, +/// and store the results in \p Conditions. Return true if all conditions are +/// collected successfully. +bool collectControlConditions(const BasicBlock &BB, const BasicBlock &Dominator, + const DominatorTree &DT, + const PostDominatorTree &PDT, + ControlConditions &Conditions); /// Return true if \p I0 and \p I1 are control flow equivalent. /// Two instructions are control flow equivalent if when one executes, 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,132 @@ STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported"); STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported"); +bool llvm::ControlConditionsComparator::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; +} + +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; +} + +bool llvm::ControlConditions::addControlCondition(const Value &V, + const bool True) { + bool Inserted = Conditions.insert(ControlCondition(&V, True)).second; + LLVM_DEBUG(dbgs() << (Inserted ? "Inserted " : "Not inserted ") << V << "\n"); + return Inserted; +} + +bool llvm::ControlConditions::isEquivalent(const ControlConditions &Other) { + if (empty() && Other.empty()) + return true; + + if (Conditions.size() != Other.getControlConditions().size()) + return false; + + for (const ControlCondition &C : Conditions) + if (!Other.getControlConditions().count(C)) + return false; + + return true; +} + +bool llvm::collectControlConditions(const BasicBlock &BB, + const BasicBlock &Dominator, + const DominatorTree &DT, + const PostDominatorTree &PDT, + ControlConditions &Conditions) { + assert(DT.dominates(&Dominator, &BB) && "Expecting Dominator to dominate BB"); + assert(Conditions.empty() && "Expecting an empty Conditions"); + + // BB is executed unconditional from itself. + if (&Dominator == &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 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 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.addControlCondition(*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.addControlCondition(*BI->getCondition(), false); + } + + CurBlock = IDom; + } while (CurBlock != &Dominator); + + return true; +} + bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1, const DominatorTree &DT, const PostDominatorTree &PDT) { @@ -42,8 +168,26 @@ 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"); + + ControlConditions BB0Conditions; + if (!collectControlConditions(BB0, *CommonDominator, DT, PDT, BB0Conditions)) + return false; + + ControlConditions BB1Conditions; + if (!collectControlConditions(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;