#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
using namespace llvm;
#define DEBUG_TYPE "flattencfg"
namespace {
class FlattenCFGOpt {
AliasAnalysis *AA;
bool FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder,
Pass *P = nullptr);
bool MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder, Pass *P = nullptr);
bool CompareIfRegionBlock(BasicBlock *Head1, BasicBlock *Head2,
BasicBlock *Block1, BasicBlock *Block2);
public:
FlattenCFGOpt(AliasAnalysis *AA) : AA(AA) {}
bool run(BasicBlock *BB);
};
}
bool FlattenCFGOpt::FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder,
Pass *P) {
PHINode *PHI = dyn_cast<PHINode>(BB->begin());
if (PHI)
return false;
BasicBlock *LastCondBlock = nullptr;
BasicBlock *FirstCondBlock = nullptr;
BasicBlock *UnCondBlock = nullptr;
int Idx = -1;
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());
if (!PBI)
return false;
BasicBlock *PP = Pred->getSinglePredecessor();
if (PBI->isUnconditional()) {
if (UnCondBlock || !PP || (Preds.count(PP) == 0) ||
Pred->hasAddressTaken())
return false;
UnCondBlock = Pred;
continue;
}
assert(PBI->isConditional());
Value *PC = PBI->getCondition();
if (!PC || !PC->hasOneUse())
return false;
if (PP && Preds.count(PP)) {
if (Pred->hasAddressTaken())
return false;
for (BasicBlock::iterator BI = Pred->begin(), BE = PBI; BI != BE;) {
Instruction *CI = BI++;
if (isa<PHINode>(CI) || !isSafeToSpeculativelyExecute(CI))
return false;
}
} else {
if (FirstCondBlock)
return false;
FirstCondBlock = Pred;
}
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;
if (Preds.count(PS) == 0) {
LastCondBlock = Pred;
} else {
BranchInst *BPS = dyn_cast<BranchInst>(PS->getTerminator());
if (BPS && BPS->isUnconditional()) {
LastCondBlock = Pred;
}
}
}
if (!FirstCondBlock || !LastCondBlock || (FirstCondBlock == LastCondBlock))
return false;
TerminatorInst *TBB = LastCondBlock->getTerminator();
BasicBlock *PS1 = TBB->getSuccessor(0);
BasicBlock *PS2 = TBB->getSuccessor(1);
BranchInst *PBI1 = dyn_cast<BranchInst>(PS1->getTerminator());
BranchInst *PBI2 = dyn_cast<BranchInst>(PS2->getTerminator());
if (!PBI1 || !PBI1->isUnconditional() ||
(PS1->getTerminator()->getSuccessor(0) != PS2)) {
if (!PBI2 || !PBI2->isUnconditional() ||
(PS2->getTerminator()->getSuccessor(0) != PS1))
return false;
BasicBlock *CurrBlock = LastCondBlock;
bool EverChanged = false;
for (;CurrBlock != FirstCondBlock;
CurrBlock = CurrBlock->getSinglePredecessor()) {
BranchInst *BI = dyn_cast<BranchInst>(CurrBlock->getTerminator());
CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
if (!CI)
continue;
CmpInst::Predicate Predicate = CI->getPredicate();
if ((Predicate == CmpInst::ICMP_NE) || (Predicate == CmpInst::FCMP_ONE)) {
CI->setPredicate(ICmpInst::getInversePredicate(Predicate));
BI->swapSuccessors();
EverChanged = true;
}
}
return EverChanged;
}
if (!PBI1 || !PBI1->isUnconditional())
return false;
PHI = dyn_cast<PHINode>(PS2->begin());
if (PHI)
return false;
BasicBlock *CB;
BranchInst *PBI = dyn_cast<BranchInst>(FirstCondBlock->getTerminator());
bool Iteration = true;
IRBuilder<>::InsertPointGuard Guard(Builder);
Value *PC = PBI->getCondition();
do {
CB = PBI->getSuccessor(1 - Idx);
FirstCondBlock->getInstList().pop_back();
FirstCondBlock->getInstList()
.splice(FirstCondBlock->end(), CB->getInstList());
PBI = cast<BranchInst>(FirstCondBlock->getTerminator());
Value *CC = PBI->getCondition();
Builder.SetInsertPoint(PBI);
Value *NC;
if (Idx == 0)
NC = Builder.CreateOr(PC, CC);
else
NC = Builder.CreateAnd(PC, CC);
PBI->replaceUsesOfWith(CC, NC);
PC = NC;
if (CB == LastCondBlock)
Iteration = false;
CB->dropAllReferences();
new UnreachableInst(CB->getContext(), CB);
} while (Iteration);
DEBUG(dbgs() << "Use parallel and/or in:\n" << *FirstCondBlock);
return true;
}
bool FlattenCFGOpt::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) {
return (eq1 == eq2);
}
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;
if (iter1->mayHaveSideEffects()) {
Instruction *CurI = &*iter1;
StoreInst *SI = dyn_cast<StoreInst>(CurI);
if (!SI || SI->isVolatile())
return false;
}
if (iter1->mayReadFromMemory())
return false;
if (iter1->mayWriteToMemory()) {
for (BasicBlock::iterator BI = PBI2, BE = PTI2; BI != BE; ++BI) {
if (BI->mayReadFromMemory() || BI->mayWriteToMemory()) {
if (!AA || AA->alias(iter1, BI))
return false;
}
}
}
++iter1;
++iter2;
}
return true;
}
bool FlattenCFGOpt::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();
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;
for (BasicBlock::iterator BI = PBI2, BE = PTI2; BI != BE; ++BI) {
Instruction *CI = BI;
if (isa<PHINode>(CI) || CI->mayHaveSideEffects() ||
!isSafeToSpeculativelyExecute(CI))
return false;
}
FirstEntryBlock->getInstList().pop_back();
FirstEntryBlock->getInstList()
.splice(FirstEntryBlock->end(), SecondEntryBlock->getInstList());
BranchInst *PBI = dyn_cast<BranchInst>(FirstEntryBlock->getTerminator());
Value *CC = PBI->getCondition();
BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
Builder.SetInsertPoint(PBI);
Value *NC = Builder.CreateOr(CInst1, CC);
PBI->replaceUsesOfWith(CC, NC);
Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt);
if (IfTrue1 != FirstEntryBlock) {
IfTrue1->dropAllReferences();
IfTrue1->eraseFromParent();
}
if (IfFalse1 != FirstEntryBlock) {
IfFalse1->dropAllReferences();
IfFalse1->eraseFromParent();
}
SecondEntryBlock->dropAllReferences();
SecondEntryBlock->eraseFromParent();
DEBUG(dbgs() << "If conditions merged into:\n" << *FirstEntryBlock);
return true;
}
bool FlattenCFGOpt::run(BasicBlock *BB) {
bool Changed = false;
assert(BB && BB->getParent() && "Block not embedded in function!");
assert(BB->getTerminator() && "Degenerate basic block encountered!");
IRBuilder<> Builder(BB);
if (FlattenParallelAndOr(BB, Builder))
return true;
if (MergeIfRegion(BB, Builder))
return true;
return Changed;
}
bool llvm::FlattenCFG(BasicBlock *BB, AliasAnalysis *AA) {
return FlattenCFGOpt(AA).run(BB);
}