-/// If \param [in] BB has more than one predecessor that is a conditional
-/// branch, attempt to use parallel and/or for the branch condition. \returns
-/// true on success.
-///
-/// Before:
-/// ......
-/// %cmp10 = fcmp une float %tmp1, %tmp2
-/// br i1 %cmp1, label %if.then, label %lor.rhs
-///
-/// lor.rhs:
-/// ......
-/// %cmp11 = fcmp une float %tmp3, %tmp4
-/// br i1 %cmp11, label %if.then, label %ifend
-///
-/// if.end: // the merge block
-/// ......
-///
-/// if.then: // has two predecessors, both of them contains conditional branch.
-/// ......
-/// br label %if.end;
-///
-/// After:
-/// ......
-/// %cmp10 = fcmp une float %tmp1, %tmp2
-/// ......
-/// %cmp11 = fcmp une float %tmp3, %tmp4
-/// %cmp12 = or i1 %cmp10, %cmp11 // parallel-or mode.
-/// br i1 %cmp12, label %if.then, label %ifend
-///
-/// if.end:
-/// ......
-///
-/// if.then:
-/// ......
-/// br label %if.end;
-///
-/// Current implementation handles two cases.
-/// Case 1: \param BB is on the else-path.
-///
-/// BB1
-/// / |
-/// BB2 |
-/// / \ |
-/// BB3 \ | where, BB1, BB2 contain conditional branches.
-/// \ | / BB3 contains unconditional branch.
-/// \ | / BB4 corresponds to \param BB which is also the merge.
-/// BB => BB4
-///
-///
-/// Corresponding source code:
-///
-/// if (a == b && c == d)
-/// statement; // BB3
-///
-/// Case 2: \param BB 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.
-/// BB4
-///
-/// Corresponding source code:
-///
-/// 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
-/// as its predecessors.
-///
-bool SimplifyCFGOpt::SimplifyParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder,
- Pass *P) {
- PHINode *PHI = dyn_cast<PHINode>(BB->begin());
- if (PHI)
- return false; // For simplicity, avoid cases containing PHI nodes.
-
- BasicBlock *LastCondBlock = NULL;
- BasicBlock *FirstCondBlock = NULL;
- BasicBlock *UnCondBlock = NULL;
- int Idx = -1;
-
- // Check predecessors of \param BB.
- SmallPtrSet<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB));
- for (SmallPtrSetIterator<BasicBlock*> PI = Preds.begin(), PE = Preds.end();
- PI != PE; ++PI) {
- BasicBlock *Pred = *PI;
- BranchInst *PBI = dyn_cast<BranchInst>(Pred->getTerminator());
-
- // All predecessors should terminate with a branch.
- if (!PBI)
- return false;
-
- BasicBlock *PP = Pred->getSinglePredecessor();
-
- if (PBI->isUnconditional()) {
- // Case 1: Pred (BB3) is an unconditional block, it should
- // have a single predecessor (BB2) that is also a predecessor
- // of \param BB (BB4) and should not have address-taken.
- // There should exist only one such unconditional
- // branch among the predecessors.
- if (UnCondBlock || !PP || (Preds.count(PP) == 0) ||
- Pred->hasAddressTaken())
- return false;
-
- UnCondBlock = Pred;
- continue;
- }
-
- // Only conditional branches are allowed beyond this point.
- assert(PBI->isConditional());
-
- // Condition's unique use should be the branch instruction.
- Value *PC = PBI->getCondition();
- if (!PC || !PC->hasOneUse())
- return false;
-
- if (PP && Preds.count(PP)) {
- // These are internal condition blocks to be merged from, e.g.,
- // BB2 in both cases.
- // Should not be address-taken.
- if (Pred->hasAddressTaken())
- return false;
-
- // Instructions in the internal condition blocks should be safe
- // to hoist up.
- for (BasicBlock::iterator BI = Pred->begin(), BE = PBI; BI != BE;) {
- Instruction *CI = BI++;
- if (isa<PHINode>(CI) ||
- !isSafeToSpeculativelyExecute(CI))
- return false;
- }
- } else {
- // This is the condition block to be merged into, e.g. BB1 in
- // both cases.
- if (FirstCondBlock)
- return false;
- FirstCondBlock = Pred;
- }
-
- // Find whether BB is uniformly on the true (or false) path
- // for all of its predecessors.
- BasicBlock *PS1 = PBI->getSuccessor(0);
- BasicBlock *PS2 = PBI->getSuccessor(1);
- BasicBlock *PS = (PS1 == BB) ? PS2 : PS1;
- int CIdx = (PS1 == BB) ? 0 : 1;
-
- if (Idx == -1)
- Idx = CIdx;
- else if (CIdx != Idx)
- return false;
-
- // PS is the successor which is not BB. Check successors to identify
- // the last conditional branch.
- if (Preds.count(PS) == 0) {
- // Case 2.
- // BB must have an unique successor.
- TerminatorInst *TBB = BB->getTerminator();
- if (TBB->getNumSuccessors() != 1)
- return false;
-
- BasicBlock *SBB = TBB->getSuccessor(0);
- PHI = dyn_cast<PHINode>(SBB->begin());
- if (PHI)
- return false;
-
- // PS (BB4) should be BB's successor.
- if (SBB != PS)
- return false;
- LastCondBlock = Pred;
- } else {
- BranchInst *BPS = dyn_cast<BranchInst>(PS->getTerminator());
- if (BPS && BPS->isUnconditional()) {
- // Case 1: PS(BB3) should be an unconditional branch.
- LastCondBlock = Pred;
- }
- }
- }
-
- if (!FirstCondBlock || !LastCondBlock || (FirstCondBlock == LastCondBlock))
- return false;
-
- // Do the transformation.
- BasicBlock *CB;
- bool Iteration = true;
- BasicBlock::iterator ItOld = Builder.GetInsertPoint();
- BranchInst *PBI = dyn_cast<BranchInst>(FirstCondBlock->getTerminator());
- Value *PC = PBI->getCondition();
- do {
- CB = PBI->getSuccessor(1 - Idx);
- // Delete the conditional branch.
- FirstCondBlock->getInstList().pop_back();
- FirstCondBlock->getInstList().splice(FirstCondBlock->end(), CB->getInstList());
- PBI = cast<BranchInst>(FirstCondBlock->getTerminator());
- Value *CC = PBI->getCondition();
- // Merge conditions.
- Builder.SetInsertPoint(PBI);
- Value *NC;
- if (Idx == 0)
- // Case 2, use parallel or.
- NC = Builder.CreateOr(PC, CC);
- else
- // Case 1, use parallel and.
- NC = Builder.CreateAnd(PC, CC);
-
- PBI->replaceUsesOfWith(CC, NC);
- PC = NC;
- if (CB == LastCondBlock)
- Iteration = false;
- // Remove internal conditional branches.
- CB->dropAllReferences();
- // make CB unreachable and let downstream to delete the block.
- new UnreachableInst(CB->getContext(), CB);
- } while (Iteration);
-
- Builder.SetInsertPoint(ItOld);
- DEBUG(dbgs() << "Use parallel and/or in:\n" << *FirstCondBlock);
- 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 SimplifyCFGOpt::CompareIfRegionBlock(BasicBlock *Head1, BasicBlock *Head2,
- BasicBlock *Block1, BasicBlock *Block2) {
- TerminatorInst *PTI2 = Head2->getTerminator();
- Instruction *PBI2 = Head2->begin();
-
- 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();
- BasicBlock::iterator end1 = Block1->getTerminator();
- BasicBlock::iterator iter2 = Block2->begin();
- BasicBlock::iterator end2 = Block2->getTerminator();
-
- while (1) {
- if (iter1 == end1) {
- if (iter2 != end2)
- return false;
- break;
- }
-
- if (!iter1->isIdenticalTo(iter2))
- return false;
-
- // Illegal to remove instructions with side effects except
- // non-volatile stores.
- if (iter1->mayHaveSideEffects()) {
- Instruction *CurI = &*iter1;
- StoreInst *SI = dyn_cast<StoreInst>(CurI);
- if (!SI || SI->isVolatile())
- return false;
- }
-
- // For simplicity and speed, data dependency check can be
- // avoided if read from memory doesn't exist.
- if (iter1->mayReadFromMemory())
- return false;
-
- if (iter1->mayWriteToMemory()) {
- for (BasicBlock::iterator BI = PBI2, BE = PTI2; BI != BE; ++BI) {
- if (BI->mayReadFromMemory() || BI->mayWriteToMemory()) {
- // Check alias with Head2.
- if (!AA || AA->alias(iter1, BI))
- return false;
- }
- }
- }
- ++iter1;
- ++iter2;
- }
-
- return true;
-}
-
-/// Check whether \param BB is the merge block of a if-region. If yes, check
-/// whether there exists an adjacent if-region upstream, the two if-regions
-/// contain identical instuctions and can be legally merged. \returns true if
-/// the two if-regions are merged.
-///
-/// From:
-/// if (a)
-/// statement;
-/// if (b)
-/// statement;
-///
-/// To:
-/// if (a || b)
-/// statement;
-///
-bool SimplifyCFGOpt::MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder,
- Pass *P) {
- BasicBlock *IfTrue2, *IfFalse2;
- Value *IfCond2 = GetIfCondition(BB, IfTrue2, IfFalse2);
- Instruction *CInst2 = dyn_cast_or_null<Instruction>(IfCond2);
- if (!CInst2)
- return false;
-
- BasicBlock *SecondEntryBlock = CInst2->getParent();
- if (SecondEntryBlock->hasAddressTaken())
- return false;
-
- BasicBlock *IfTrue1, *IfFalse1;
- Value *IfCond1 = GetIfCondition(SecondEntryBlock, IfTrue1, IfFalse1);
- Instruction *CInst1 = dyn_cast_or_null<Instruction>(IfCond1);
- if (!CInst1)
- return false;
-
- 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;
-
- TerminatorInst *PTI2 = SecondEntryBlock->getTerminator();
- Instruction *PBI2 = SecondEntryBlock->begin();
-
- if (!CompareIfRegionBlock(FirstEntryBlock, SecondEntryBlock, IfTrue1, IfTrue2))
- return false;
-
- if (!CompareIfRegionBlock(FirstEntryBlock, SecondEntryBlock, IfFalse1, IfFalse2))
- return false;
-
- // Check whether \param SecondEntryBlock has side-effect and is safe to speculate.
- for (BasicBlock::iterator BI = PBI2, BE = PTI2; BI != BE; ++BI) {
- Instruction *CI = BI;
- if (isa<PHINode>(CI) || CI->mayHaveSideEffects() ||
- !isSafeToSpeculativelyExecute(CI))
- return false;
- }
-
- // Merge \param SecondEntryBlock into \param FirstEntryBlock.
- FirstEntryBlock->getInstList().pop_back();
- FirstEntryBlock->getInstList().splice(FirstEntryBlock->end(), SecondEntryBlock->getInstList());
- BranchInst *PBI = dyn_cast<BranchInst>(FirstEntryBlock->getTerminator());
- Value *CC = PBI->getCondition();
- BasicBlock::iterator ItOld = Builder.GetInsertPoint();
- Builder.SetInsertPoint(PBI);
- Value *NC = Builder.CreateOr(CInst1, CC);
- PBI->replaceUsesOfWith(CC, NC);
- Builder.SetInsertPoint(ItOld);
-
- // Remove IfTrue1
- if (IfTrue1 != FirstEntryBlock) {
- IfTrue1->dropAllReferences();
- IfTrue1->eraseFromParent();
- }
-
- // Remove IfFalse1
- if (IfFalse1 != FirstEntryBlock) {
- IfFalse1->dropAllReferences();
- IfFalse1->eraseFromParent();
- }
-
- // Remove \param SecondEntryBlock
- SecondEntryBlock->dropAllReferences();
- SecondEntryBlock->eraseFromParent();
- DEBUG(dbgs() << "If conditions merged into:\n" << *FirstEntryBlock);
- return true;
-}
-