aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Transforms/Utils/FlattenCFG.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Transforms/Utils/FlattenCFG.cpp')
-rw-r--r--llvm/lib/Transforms/Utils/FlattenCFG.cpp128
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);
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-10-28 04:34:10 +0000