diff options
Diffstat (limited to 'llvm/lib/Transforms/Utils/FlattenCFG.cpp')
-rw-r--r-- | llvm/lib/Transforms/Utils/FlattenCFG.cpp | 128 |
1 files changed, 86 insertions, 42 deletions
diff --git a/llvm/lib/Transforms/Utils/FlattenCFG.cpp b/llvm/lib/Transforms/Utils/FlattenCFG.cpp index 893f23eb6048..0098dcaeb07a 100644 --- a/llvm/lib/Transforms/Utils/FlattenCFG.cpp +++ b/llvm/lib/Transforms/Utils/FlattenCFG.cpp @@ -45,12 +45,12 @@ class FlattenCFGOpt { bool MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder); /// Compare a pair of blocks: \p Block1 and \p Block2, which - /// are from two if-regions whose entry blocks are \p Head1 and \p - /// Head2. \returns true if \p Block1 and \p Block2 contain identical + /// are from two if-regions, where \p Head2 is the entry block of the 2nd + /// if-region. \returns true if \p Block1 and \p Block2 contain identical /// instructions, and have no memory reference alias with \p Head2. /// This is used as a legality check for merging if-regions. - bool CompareIfRegionBlock(BasicBlock *Head1, BasicBlock *Head2, - BasicBlock *Block1, BasicBlock *Block2); + bool CompareIfRegionBlock(BasicBlock *Block1, BasicBlock *Block2, + BasicBlock *Head2); public: FlattenCFGOpt(AliasAnalysis *AA) : AA(AA) {} @@ -97,7 +97,7 @@ public: /// br label %if.end; /// /// Current implementation handles two cases. -/// Case 1: \param BB is on the else-path. +/// Case 1: BB is on the else-path. /// /// BB1 /// / | @@ -105,7 +105,7 @@ public: /// / \ | /// BB3 \ | where, BB1, BB2 contain conditional branches. /// \ | / BB3 contains unconditional branch. -/// \ | / BB4 corresponds to \param BB which is also the merge. +/// \ | / BB4 corresponds to BB which is also the merge. /// BB => BB4 /// /// @@ -114,14 +114,14 @@ public: /// if (a == b && c == d) /// statement; // BB3 /// -/// Case 2: \param BB BB is on the then-path. +/// Case 2: BB is on the then-path. /// /// BB1 /// / | /// | BB2 /// \ / | where BB1, BB2 contain conditional branches. /// BB => BB3 | BB3 contains unconditiona branch and corresponds -/// \ / to \param BB. BB4 is the merge. +/// \ / to BB. BB4 is the merge. /// BB4 /// /// Corresponding source code: @@ -129,9 +129,9 @@ public: /// if (a == b || c == d) /// statement; // BB3 /// -/// In both cases, \param BB is the common successor of conditional branches. -/// In Case 1, \param BB (BB4) has an unconditional branch (BB3) as -/// its predecessor. In Case 2, \param BB (BB3) only has conditional branches +/// In both cases, BB is the common successor of conditional branches. +/// In Case 1, BB (BB4) has an unconditional branch (BB3) as +/// its predecessor. In Case 2, BB (BB3) only has conditional branches /// as its predecessors. bool FlattenCFGOpt::FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder) { PHINode *PHI = dyn_cast<PHINode>(BB->begin()); @@ -315,25 +315,16 @@ bool FlattenCFGOpt::FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder) { return true; } -/// Compare blocks from two if-regions, where \param Head1 is the entry of the -/// 1st if-region. \param Head2 is the entry of the 2nd if-region. \param -/// Block1 is a block in the 1st if-region to compare. \param Block2 is a block -// in the 2nd if-region to compare. \returns true if \param Block1 and \param -/// Block2 have identical instructions and do not have memory reference alias -/// with \param Head2. -bool FlattenCFGOpt::CompareIfRegionBlock(BasicBlock *Head1, BasicBlock *Head2, - BasicBlock *Block1, - BasicBlock *Block2) { +/// Compare blocks from two if-regions, where \param Head2 is the entry of the +/// 2nd if-region. \param Block1 is a block in the 1st if-region to compare. +/// \param Block2 is a block in the 2nd if-region to compare. \returns true if +/// Block1 and Block2 have identical instructions and do not have +/// memory reference alias with Head2. +bool FlattenCFGOpt::CompareIfRegionBlock(BasicBlock *Block1, BasicBlock *Block2, + BasicBlock *Head2) { Instruction *PTI2 = Head2->getTerminator(); Instruction *PBI2 = &Head2->front(); - bool eq1 = (Block1 == Head1); - bool eq2 = (Block2 == Head2); - if (eq1 || eq2) { - // An empty then-path or else-path. - return (eq1 == eq2); - } - // Check whether instructions in Block1 and Block2 are identical // and do not alias with instructions in Head2. BasicBlock::iterator iter1 = Block1->begin(); @@ -395,6 +386,29 @@ bool FlattenCFGOpt::CompareIfRegionBlock(BasicBlock *Head1, BasicBlock *Head2, /// To: /// if (a || b) /// statement; +/// +/// +/// And from: +/// if (a) +/// ; +/// else +/// statement; +/// if (b) +/// ; +/// else +/// statement; +/// +/// To: +/// if (a && b) +/// ; +/// else +/// statement; +/// +/// We always take the form of the first if-region. This means that if the +/// statement in the first if-region, is in the "then-path", while in the second +/// if-region it is in the "else-path", then we convert the second to the first +/// form, by inverting the condition and the branch successors. The same +/// approach goes for the opposite case. bool FlattenCFGOpt::MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder) { BasicBlock *IfTrue2, *IfFalse2; Value *IfCond2 = GetIfCondition(BB, IfTrue2, IfFalse2); @@ -415,22 +429,42 @@ bool FlattenCFGOpt::MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder) { BasicBlock *FirstEntryBlock = CInst1->getParent(); // Either then-path or else-path should be empty. - if ((IfTrue1 != FirstEntryBlock) && (IfFalse1 != FirstEntryBlock)) - return false; - if ((IfTrue2 != SecondEntryBlock) && (IfFalse2 != SecondEntryBlock)) - return false; + bool InvertCond2 = false; + BinaryOperator::BinaryOps CombineOp; + if (IfFalse1 == FirstEntryBlock) { + // The else-path is empty, so we must use "or" operation to combine the + // conditions. + CombineOp = BinaryOperator::Or; + if (IfFalse2 != SecondEntryBlock) { + if (IfTrue2 != SecondEntryBlock) + return false; - Instruction *PTI2 = SecondEntryBlock->getTerminator(); - Instruction *PBI2 = &SecondEntryBlock->front(); + InvertCond2 = true; + std::swap(IfTrue2, IfFalse2); + } - if (!CompareIfRegionBlock(FirstEntryBlock, SecondEntryBlock, IfTrue1, - IfTrue2)) - return false; + if (!CompareIfRegionBlock(IfTrue1, IfTrue2, SecondEntryBlock)) + return false; + } else if (IfTrue1 == FirstEntryBlock) { + // The then-path is empty, so we must use "and" operation to combine the + // conditions. + CombineOp = BinaryOperator::And; + if (IfTrue2 != SecondEntryBlock) { + if (IfFalse2 != SecondEntryBlock) + return false; + + InvertCond2 = true; + std::swap(IfTrue2, IfFalse2); + } - if (!CompareIfRegionBlock(FirstEntryBlock, SecondEntryBlock, IfFalse1, - IfFalse2)) + if (!CompareIfRegionBlock(IfFalse1, IfFalse2, SecondEntryBlock)) + return false; + } else return false; + Instruction *PTI2 = SecondEntryBlock->getTerminator(); + Instruction *PBI2 = &SecondEntryBlock->front(); + // Check whether \param SecondEntryBlock has side-effect and is safe to // speculate. for (BasicBlock::iterator BI(PBI2), BE(PTI2); BI != BE; ++BI) { @@ -445,12 +479,22 @@ bool FlattenCFGOpt::MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder) { FirstEntryBlock->getInstList() .splice(FirstEntryBlock->end(), SecondEntryBlock->getInstList()); BranchInst *PBI = cast<BranchInst>(FirstEntryBlock->getTerminator()); - Value *CC = PBI->getCondition(); + assert(PBI->getCondition() == IfCond2); BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); Builder.SetInsertPoint(PBI); - Value *NC = Builder.CreateOr(CInst1, CC); - PBI->replaceUsesOfWith(CC, NC); + if (InvertCond2) { + // If this is a "cmp" instruction, only used for branching (and nowhere + // else), then we can simply invert the predicate. + auto Cmp2 = dyn_cast<CmpInst>(CInst2); + if (Cmp2 && Cmp2->hasOneUse()) + Cmp2->setPredicate(Cmp2->getInversePredicate()); + else + CInst2 = cast<Instruction>(Builder.CreateNot(CInst2)); + PBI->swapSuccessors(); + } + Value *NC = Builder.CreateBinOp(CombineOp, CInst1, CInst2); + PBI->replaceUsesOfWith(IfCond2, NC); Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt); // Handle PHI node to replace its predecessors to FirstEntryBlock. @@ -496,6 +540,6 @@ bool FlattenCFGOpt::run(BasicBlock *BB) { /// FlattenCFG - This function is used to flatten a CFG. For /// example, it uses parallel-and and parallel-or mode to collapse /// if-conditions and merge if-regions with identical statements. -bool llvm::FlattenCFG(BasicBlock *BB, AliasAnalysis *AA) { +bool llvm::FlattenCFG(BasicBlock *BB, AAResults *AA) { return FlattenCFGOpt(AA).run(BB); } |