#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/NoFolder.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <map>
#include <set>
using namespace llvm;
using namespace PatternMatch;
#define DEBUG_TYPE "simplifycfg"
static cl::opt<unsigned>
PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(1),
cl::desc("Control the amount of phi node folding to perform (default = 1)"));
static cl::opt<bool>
DupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false),
cl::desc("Duplicate return instructions into unconditional branches"));
static cl::opt<bool>
SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true),
cl::desc("Sink common instructions down to the end block"));
static cl::opt<bool> HoistCondStores(
"simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true),
cl::desc("Hoist conditional stores if an unconditional store precedes"));
STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps");
STATISTIC(NumLinearMaps, "Number of switch instructions turned into linear mapping");
STATISTIC(NumLookupTables, "Number of switch instructions turned into lookup tables");
STATISTIC(NumLookupTablesHoles, "Number of switch instructions turned into lookup tables (holes checked)");
STATISTIC(NumTableCmpReuses, "Number of reused switch table lookup compares");
STATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block");
STATISTIC(NumSpeculations, "Number of speculative executed instructions");
namespace {
typedef SmallVector<std::pair<Constant *, SmallVector<ConstantInt *, 4>>, 2>
SwitchCaseResultVectorTy;
typedef SmallVector<std::pair<PHINode *, Constant *>, 4> SwitchCaseResultsTy;
struct ValueEqualityComparisonCase {
ConstantInt *Value;
BasicBlock *Dest;
ValueEqualityComparisonCase(ConstantInt *Value, BasicBlock *Dest)
: Value(Value), Dest(Dest) {}
bool operator<(ValueEqualityComparisonCase RHS) const {
return Value < RHS.Value;
}
bool operator==(BasicBlock *RHSDest) const { return Dest == RHSDest; }
};
class SimplifyCFGOpt {
const TargetTransformInfo &TTI;
const DataLayout &DL;
unsigned BonusInstThreshold;
AssumptionCache *AC;
Value *isValueEqualityComparison(TerminatorInst *TI);
BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI,
std::vector<ValueEqualityComparisonCase> &Cases);
bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
BasicBlock *Pred,
IRBuilder<> &Builder);
bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
IRBuilder<> &Builder);
bool SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder);
bool SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder);
bool SimplifyUnreachable(UnreachableInst *UI);
bool SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder);
bool SimplifyIndirectBr(IndirectBrInst *IBI);
bool SimplifyUncondBranch(BranchInst *BI, IRBuilder <> &Builder);
bool SimplifyCondBranch(BranchInst *BI, IRBuilder <>&Builder);
public:
SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout &DL,
unsigned BonusInstThreshold, AssumptionCache *AC)
: TTI(TTI), DL(DL), BonusInstThreshold(BonusInstThreshold), AC(AC) {}
bool run(BasicBlock *BB);
};
}
static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) {
if (SI1 == SI2) return false;
BasicBlock *SI1BB = SI1->getParent();
BasicBlock *SI2BB = SI2->getParent();
SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB));
for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I)
if (SI1Succs.count(*I))
for (BasicBlock::iterator BBI = (*I)->begin();
isa<PHINode>(BBI); ++BBI) {
PHINode *PN = cast<PHINode>(BBI);
if (PN->getIncomingValueForBlock(SI1BB) !=
PN->getIncomingValueForBlock(SI2BB))
return false;
}
return true;
}
static bool isProfitableToFoldUnconditional(BranchInst *SI1,
BranchInst *SI2,
Instruction *Cond,
SmallVectorImpl<PHINode*> &PhiNodes) {
if (SI1 == SI2) return false; assert(SI1->isUnconditional() && SI2->isConditional());
CmpInst *Ci2 = dyn_cast<CmpInst>(SI2->getCondition());
if (!Ci2) return false;
if (!(Cond->getOperand(0) == Ci2->getOperand(0) &&
Cond->getOperand(1) == Ci2->getOperand(1)) &&
!(Cond->getOperand(0) == Ci2->getOperand(1) &&
Cond->getOperand(1) == Ci2->getOperand(0)))
return false;
BasicBlock *SI1BB = SI1->getParent();
BasicBlock *SI2BB = SI2->getParent();
SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB));
for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I)
if (SI1Succs.count(*I))
for (BasicBlock::iterator BBI = (*I)->begin();
isa<PHINode>(BBI); ++BBI) {
PHINode *PN = cast<PHINode>(BBI);
if (PN->getIncomingValueForBlock(SI1BB) != Cond ||
!isa<ConstantInt>(PN->getIncomingValueForBlock(SI2BB)))
return false;
PhiNodes.push_back(PN);
}
return true;
}
static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred,
BasicBlock *ExistPred) {
if (!isa<PHINode>(Succ->begin())) return;
PHINode *PN;
for (BasicBlock::iterator I = Succ->begin();
(PN = dyn_cast<PHINode>(I)); ++I)
PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred);
}
static unsigned ComputeSpeculationCost(const User *I) {
assert(isSafeToSpeculativelyExecute(I) &&
"Instruction is not safe to speculatively execute!");
switch (Operator::getOpcode(I)) {
default:
return UINT_MAX;
case Instruction::GetElementPtr:
if (!cast<GEPOperator>(I)->hasAllConstantIndices())
return UINT_MAX;
return 1;
case Instruction::ExtractValue:
case Instruction::Load:
case Instruction::Add:
case Instruction::Sub:
case Instruction::And:
case Instruction::Or:
case Instruction::Xor:
case Instruction::Shl:
case Instruction::LShr:
case Instruction::AShr:
case Instruction::ICmp:
case Instruction::Trunc:
case Instruction::ZExt:
case Instruction::SExt:
case Instruction::BitCast:
case Instruction::ExtractElement:
case Instruction::InsertElement:
return 1;
case Instruction::Call:
case Instruction::Select:
return 2;
}
}
static bool DominatesMergePoint(Value *V, BasicBlock *BB,
SmallPtrSetImpl<Instruction*> *AggressiveInsts,
unsigned &CostRemaining) {
Instruction *I = dyn_cast<Instruction>(V);
if (!I) {
if (ConstantExpr *C = dyn_cast<ConstantExpr>(V))
if (C->canTrap())
return false;
return true;
}
BasicBlock *PBB = I->getParent();
if (PBB == BB) return false;
BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator());
if (!BI || BI->isConditional() || BI->getSuccessor(0) != BB)
return true;
if (!AggressiveInsts) return false;
if (AggressiveInsts->count(I)) return true;
if (!isSafeToSpeculativelyExecute(I))
return false;
unsigned Cost = ComputeSpeculationCost(I);
if (Cost > CostRemaining)
return false;
CostRemaining -= Cost;
for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i)
if (!DominatesMergePoint(*i, BB, AggressiveInsts, CostRemaining))
return false;
AggressiveInsts->insert(I);
return true;
}
static ConstantInt *GetConstantInt(Value *V, const DataLayout &DL) {
ConstantInt *CI = dyn_cast<ConstantInt>(V);
if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy())
return CI;
IntegerType *PtrTy = cast<IntegerType>(DL.getIntPtrType(V->getType()));
if (isa<ConstantPointerNull>(V))
return ConstantInt::get(PtrTy, 0);
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
if (CE->getOpcode() == Instruction::IntToPtr)
if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
if (CI->getType() == PtrTy)
return CI;
else
return cast<ConstantInt>
(ConstantExpr::getIntegerCast(CI, PtrTy, false));
}
return nullptr;
}
namespace {
struct ConstantComparesGatherer {
const DataLayout &DL;
Value *CompValue; Value *Extra; SmallVector<ConstantInt *, 8> Vals; unsigned UsedICmps;
ConstantComparesGatherer(Instruction *Cond, const DataLayout &DL)
: DL(DL), CompValue(nullptr), Extra(nullptr), UsedICmps(0) {
gather(Cond);
}
ConstantComparesGatherer(const ConstantComparesGatherer &)
LLVM_DELETED_FUNCTION;
ConstantComparesGatherer &
operator=(const ConstantComparesGatherer &) LLVM_DELETED_FUNCTION;
private:
bool setValueOnce(Value *NewVal) {
if(CompValue && CompValue != NewVal) return false;
CompValue = NewVal;
return (CompValue != nullptr);
}
bool matchInstruction(Instruction *I, bool isEQ) {
ICmpInst *ICI;
ConstantInt *C;
if (!((ICI = dyn_cast<ICmpInst>(I)) &&
(C = GetConstantInt(I->getOperand(1), DL)))) {
return false;
}
Value *RHSVal;
ConstantInt *RHSC;
if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) {
if (match(ICI->getOperand(0),
m_And(m_Value(RHSVal), m_ConstantInt(RHSC)))) {
APInt Not = ~RHSC->getValue();
if (Not.isPowerOf2()) {
if(!setValueOnce(RHSVal))
return false;
Vals.push_back(C);
Vals.push_back(ConstantInt::get(C->getContext(),
C->getValue() | Not));
UsedICmps++;
return true;
}
}
if(!setValueOnce(ICI->getOperand(0)))
return false;
UsedICmps++;
Vals.push_back(C);
return ICI->getOperand(0);
}
ConstantRange Span = ConstantRange::makeICmpRegion(ICI->getPredicate(),
C->getValue());
Value *CandidateVal = I->getOperand(0);
if(match(I->getOperand(0), m_Add(m_Value(RHSVal), m_ConstantInt(RHSC)))) {
Span = Span.subtract(RHSC->getValue());
CandidateVal = RHSVal;
}
if (!isEQ)
Span = Span.inverse();
if (Span.getSetSize().ugt(8) || Span.isEmptySet()) {
return false;
}
if(!setValueOnce(CandidateVal))
return false;
for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp)
Vals.push_back(ConstantInt::get(I->getContext(), Tmp));
UsedICmps++;
return true;
}
void gather(Value *V) {
Instruction *I = dyn_cast<Instruction>(V);
bool isEQ = (I->getOpcode() == Instruction::Or);
SmallVector<Value *, 8> DFT;
DFT.push_back(V);
while(!DFT.empty()) {
V = DFT.pop_back_val();
if (Instruction *I = dyn_cast<Instruction>(V)) {
if (I->getOpcode() == (isEQ ? Instruction::Or : Instruction::And)) {
DFT.push_back(I->getOperand(1));
DFT.push_back(I->getOperand(0));
continue;
}
if (matchInstruction(I, isEQ))
continue;
}
if (!Extra) {
Extra = V;
continue;
}
CompValue = nullptr;
break;
}
}
};
}
static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) {
Instruction *Cond = nullptr;
if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
Cond = dyn_cast<Instruction>(SI->getCondition());
} else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
if (BI->isConditional())
Cond = dyn_cast<Instruction>(BI->getCondition());
} else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(TI)) {
Cond = dyn_cast<Instruction>(IBI->getAddress());
}
TI->eraseFromParent();
if (Cond) RecursivelyDeleteTriviallyDeadInstructions(Cond);
}
Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) {
Value *CV = nullptr;
if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
if (SI->getNumSuccessors()*std::distance(pred_begin(SI->getParent()),
pred_end(SI->getParent())) <= 128)
CV = SI->getCondition();
} else if (BranchInst *BI = dyn_cast<BranchInst>(TI))
if (BI->isConditional() && BI->getCondition()->hasOneUse())
if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
if (ICI->isEquality() && GetConstantInt(ICI->getOperand(1), DL))
CV = ICI->getOperand(0);
}
if (CV) {
if (PtrToIntInst *PTII = dyn_cast<PtrToIntInst>(CV)) {
Value *Ptr = PTII->getPointerOperand();
if (PTII->getType() == DL.getIntPtrType(Ptr->getType()))
CV = Ptr;
}
}
return CV;
}
BasicBlock *SimplifyCFGOpt::
GetValueEqualityComparisonCases(TerminatorInst *TI,
std::vector<ValueEqualityComparisonCase>
&Cases) {
if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
Cases.reserve(SI->getNumCases());
for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i)
Cases.push_back(ValueEqualityComparisonCase(i.getCaseValue(),
i.getCaseSuccessor()));
return SI->getDefaultDest();
}
BranchInst *BI = cast<BranchInst>(TI);
ICmpInst *ICI = cast<ICmpInst>(BI->getCondition());
BasicBlock *Succ = BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE);
Cases.push_back(ValueEqualityComparisonCase(GetConstantInt(ICI->getOperand(1),
DL),
Succ));
return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ);
}
static void EliminateBlockCases(BasicBlock *BB,
std::vector<ValueEqualityComparisonCase> &Cases) {
Cases.erase(std::remove(Cases.begin(), Cases.end(), BB), Cases.end());
}
static bool
ValuesOverlap(std::vector<ValueEqualityComparisonCase> &C1,
std::vector<ValueEqualityComparisonCase > &C2) {
std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
if (V1->size() > V2->size())
std::swap(V1, V2);
if (V1->size() == 0) return false;
if (V1->size() == 1) {
ConstantInt *TheVal = (*V1)[0].Value;
for (unsigned i = 0, e = V2->size(); i != e; ++i)
if (TheVal == (*V2)[i].Value)
return true;
}
array_pod_sort(V1->begin(), V1->end());
array_pod_sort(V2->begin(), V2->end());
unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
while (i1 != e1 && i2 != e2) {
if ((*V1)[i1].Value == (*V2)[i2].Value)
return true;
if ((*V1)[i1].Value < (*V2)[i2].Value)
++i1;
else
++i2;
}
return false;
}
bool SimplifyCFGOpt::
SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
BasicBlock *Pred,
IRBuilder<> &Builder) {
Value *PredVal = isValueEqualityComparison(Pred->getTerminator());
if (!PredVal) return false;
Value *ThisVal = isValueEqualityComparison(TI);
assert(ThisVal && "This isn't a value comparison!!");
if (ThisVal != PredVal) return false;
std::vector<ValueEqualityComparisonCase> PredCases;
BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(),
PredCases);
EliminateBlockCases(PredDef, PredCases);
std::vector<ValueEqualityComparisonCase> ThisCases;
BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
EliminateBlockCases(ThisDef, ThisCases);
if (PredDef == TI->getParent()) {
if (!ValuesOverlap(PredCases, ThisCases))
return false;
if (isa<BranchInst>(TI)) {
assert(ThisCases.size() == 1 && "Branch can only have one case!");
Instruction *NI = Builder.CreateBr(ThisDef);
(void) NI;
ThisCases[0].Dest->removePredecessor(TI->getParent());
DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
<< "Through successor TI: " << *TI << "Leaving: " << *NI << "\n");
EraseTerminatorInstAndDCECond(TI);
return true;
}
SwitchInst *SI = cast<SwitchInst>(TI);
SmallPtrSet<Constant*, 16> DeadCases;
for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
DeadCases.insert(PredCases[i].Value);
DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
<< "Through successor TI: " << *TI);
SmallVector<uint32_t, 8> Weights;
MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
bool HasWeight = MD && (MD->getNumOperands() == 2 + SI->getNumCases());
if (HasWeight)
for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e;
++MD_i) {
ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(MD_i));
Weights.push_back(CI->getValue().getZExtValue());
}
for (SwitchInst::CaseIt i = SI->case_end(), e = SI->case_begin(); i != e;) {
--i;
if (DeadCases.count(i.getCaseValue())) {
if (HasWeight) {
std::swap(Weights[i.getCaseIndex()+1], Weights.back());
Weights.pop_back();
}
i.getCaseSuccessor()->removePredecessor(TI->getParent());
SI->removeCase(i);
}
}
if (HasWeight && Weights.size() >= 2)
SI->setMetadata(LLVMContext::MD_prof,
MDBuilder(SI->getParent()->getContext()).
createBranchWeights(Weights));
DEBUG(dbgs() << "Leaving: " << *TI << "\n");
return true;
}
ConstantInt *TIV = nullptr;
BasicBlock *TIBB = TI->getParent();
for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
if (PredCases[i].Dest == TIBB) {
if (TIV)
return false; TIV = PredCases[i].Value;
}
assert(TIV && "No edge from pred to succ?");
BasicBlock *TheRealDest = nullptr;
for (unsigned i = 0, e = ThisCases.size(); i != e; ++i)
if (ThisCases[i].Value == TIV) {
TheRealDest = ThisCases[i].Dest;
break;
}
if (!TheRealDest) TheRealDest = ThisDef;
BasicBlock *CheckEdge = TheRealDest;
for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI)
if (*SI != CheckEdge)
(*SI)->removePredecessor(TIBB);
else
CheckEdge = nullptr;
Instruction *NI = Builder.CreateBr(TheRealDest);
(void) NI;
DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
<< "Through successor TI: " << *TI << "Leaving: " << *NI << "\n");
EraseTerminatorInstAndDCECond(TI);
return true;
}
namespace {
struct ConstantIntOrdering {
bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const {
return LHS->getValue().ult(RHS->getValue());
}
};
}
static int ConstantIntSortPredicate(ConstantInt *const *P1,
ConstantInt *const *P2) {
const ConstantInt *LHS = *P1;
const ConstantInt *RHS = *P2;
if (LHS->getValue().ult(RHS->getValue()))
return 1;
if (LHS->getValue() == RHS->getValue())
return 0;
return -1;
}
static inline bool HasBranchWeights(const Instruction* I) {
MDNode *ProfMD = I->getMetadata(LLVMContext::MD_prof);
if (ProfMD && ProfMD->getOperand(0))
if (MDString* MDS = dyn_cast<MDString>(ProfMD->getOperand(0)))
return MDS->getString().equals("branch_weights");
return false;
}
static void GetBranchWeights(TerminatorInst *TI,
SmallVectorImpl<uint64_t> &Weights) {
MDNode *MD = TI->getMetadata(LLVMContext::MD_prof);
assert(MD);
for (unsigned i = 1, e = MD->getNumOperands(); i < e; ++i) {
ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(i));
Weights.push_back(CI->getValue().getZExtValue());
}
if (BranchInst* BI = dyn_cast<BranchInst>(TI)) {
assert(Weights.size() == 2);
ICmpInst *ICI = cast<ICmpInst>(BI->getCondition());
if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
std::swap(Weights.front(), Weights.back());
}
}
static void FitWeights(MutableArrayRef<uint64_t> Weights) {
uint64_t Max = *std::max_element(Weights.begin(), Weights.end());
if (Max > UINT_MAX) {
unsigned Offset = 32 - countLeadingZeros(Max);
for (uint64_t &I : Weights)
I >>= Offset;
}
}
bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
IRBuilder<> &Builder) {
BasicBlock *BB = TI->getParent();
Value *CV = isValueEqualityComparison(TI); assert(CV && "Not a comparison?");
bool Changed = false;
SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB));
while (!Preds.empty()) {
BasicBlock *Pred = Preds.pop_back_val();
TerminatorInst *PTI = Pred->getTerminator();
Value *PCV = isValueEqualityComparison(PTI);
if (PCV == CV && SafeToMergeTerminators(TI, PTI)) {
std::vector<ValueEqualityComparisonCase> BBCases;
BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
std::vector<ValueEqualityComparisonCase> PredCases;
BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
SmallVector<BasicBlock*, 8> NewSuccessors;
SmallVector<uint64_t, 8> Weights;
bool PredHasWeights = HasBranchWeights(PTI);
bool SuccHasWeights = HasBranchWeights(TI);
if (PredHasWeights) {
GetBranchWeights(PTI, Weights);
if (Weights.size() != 1 + PredCases.size())
PredHasWeights = SuccHasWeights = false;
} else if (SuccHasWeights)
Weights.assign(1 + PredCases.size(), 1);
SmallVector<uint64_t, 8> SuccWeights;
if (SuccHasWeights) {
GetBranchWeights(TI, SuccWeights);
if (SuccWeights.size() != 1 + BBCases.size())
PredHasWeights = SuccHasWeights = false;
} else if (PredHasWeights)
SuccWeights.assign(1 + BBCases.size(), 1);
if (PredDefault == BB) {
std::set<ConstantInt*, ConstantIntOrdering> PTIHandled;
for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
if (PredCases[i].Dest != BB)
PTIHandled.insert(PredCases[i].Value);
else {
std::swap(PredCases[i], PredCases.back());
if (PredHasWeights || SuccHasWeights) {
Weights[0] += Weights[i+1];
std::swap(Weights[i+1], Weights.back());
Weights.pop_back();
}
PredCases.pop_back();
--i; --e;
}
if (PredDefault != BBDefault) {
PredDefault->removePredecessor(Pred);
PredDefault = BBDefault;
NewSuccessors.push_back(BBDefault);
}
unsigned CasesFromPred = Weights.size();
uint64_t ValidTotalSuccWeight = 0;
for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
if (!PTIHandled.count(BBCases[i].Value) &&
BBCases[i].Dest != BBDefault) {
PredCases.push_back(BBCases[i]);
NewSuccessors.push_back(BBCases[i].Dest);
if (SuccHasWeights || PredHasWeights) {
Weights.push_back(Weights[0] * SuccWeights[i+1]);
ValidTotalSuccWeight += SuccWeights[i+1];
}
}
if (SuccHasWeights || PredHasWeights) {
ValidTotalSuccWeight += SuccWeights[0];
for (unsigned i = 1; i < CasesFromPred; ++i)
Weights[i] *= ValidTotalSuccWeight;
Weights[0] *= SuccWeights[0];
}
} else {
std::set<ConstantInt*, ConstantIntOrdering> PTIHandled;
std::map<ConstantInt*, uint64_t> WeightsForHandled;
for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
if (PredCases[i].Dest == BB) {
PTIHandled.insert(PredCases[i].Value);
if (PredHasWeights || SuccHasWeights) {
WeightsForHandled[PredCases[i].Value] = Weights[i+1];
std::swap(Weights[i+1], Weights.back());
Weights.pop_back();
}
std::swap(PredCases[i], PredCases.back());
PredCases.pop_back();
--i; --e;
}
for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
if (PTIHandled.count(BBCases[i].Value)) {
if (PredHasWeights || SuccHasWeights)
Weights.push_back(WeightsForHandled[BBCases[i].Value]);
PredCases.push_back(BBCases[i]);
NewSuccessors.push_back(BBCases[i].Dest);
PTIHandled.erase(BBCases[i].Value); }
for (std::set<ConstantInt*, ConstantIntOrdering>::iterator I =
PTIHandled.begin(),
E = PTIHandled.end(); I != E; ++I) {
if (PredHasWeights || SuccHasWeights)
Weights.push_back(WeightsForHandled[*I]);
PredCases.push_back(ValueEqualityComparisonCase(*I, BBDefault));
NewSuccessors.push_back(BBDefault);
}
}
for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i)
AddPredecessorToBlock(NewSuccessors[i], Pred, BB);
Builder.SetInsertPoint(PTI);
if (CV->getType()->isPointerTy()) {
CV = Builder.CreatePtrToInt(CV, DL.getIntPtrType(CV->getType()),
"magicptr");
}
SwitchInst *NewSI = Builder.CreateSwitch(CV, PredDefault,
PredCases.size());
NewSI->setDebugLoc(PTI->getDebugLoc());
for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
NewSI->addCase(PredCases[i].Value, PredCases[i].Dest);
if (PredHasWeights || SuccHasWeights) {
FitWeights(Weights);
SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end());
NewSI->setMetadata(LLVMContext::MD_prof,
MDBuilder(BB->getContext()).
createBranchWeights(MDWeights));
}
EraseTerminatorInstAndDCECond(PTI);
BasicBlock *InfLoopBlock = nullptr;
for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i)
if (NewSI->getSuccessor(i) == BB) {
if (!InfLoopBlock) {
InfLoopBlock = BasicBlock::Create(BB->getContext(),
"infloop", BB->getParent());
BranchInst::Create(InfLoopBlock, InfLoopBlock);
}
NewSI->setSuccessor(i, InfLoopBlock);
}
Changed = true;
}
}
return Changed;
}
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2,
Instruction *I1, Instruction *I2) {
for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) {
PHINode *PN;
for (BasicBlock::iterator BBI = SI->begin();
(PN = dyn_cast<PHINode>(BBI)); ++BBI) {
Value *BB1V = PN->getIncomingValueForBlock(BB1);
Value *BB2V = PN->getIncomingValueForBlock(BB2);
if (BB1V != BB2V && (BB1V==I1 || BB2V==I2)) {
return false;
}
}
}
return true;
}
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I);
static bool HoistThenElseCodeToIf(BranchInst *BI) {
BasicBlock *BB1 = BI->getSuccessor(0); BasicBlock *BB2 = BI->getSuccessor(1);
BasicBlock::iterator BB1_Itr = BB1->begin();
BasicBlock::iterator BB2_Itr = BB2->begin();
Instruction *I1 = BB1_Itr++, *I2 = BB2_Itr++;
DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);
if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
while (isa<DbgInfoIntrinsic>(I1))
I1 = BB1_Itr++;
while (isa<DbgInfoIntrinsic>(I2))
I2 = BB2_Itr++;
}
if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2) ||
(isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)))
return false;
BasicBlock *BIParent = BI->getParent();
bool Changed = false;
do {
if (isa<TerminatorInst>(I1))
goto HoistTerminator;
BIParent->getInstList().splice(BI, BB1->getInstList(), I1);
if (!I2->use_empty())
I2->replaceAllUsesWith(I1);
I1->intersectOptionalDataWith(I2);
unsigned KnownIDs[] = {
LLVMContext::MD_tbaa,
LLVMContext::MD_range,
LLVMContext::MD_fpmath,
LLVMContext::MD_invariant_load,
LLVMContext::MD_nonnull
};
combineMetadata(I1, I2, KnownIDs);
I2->eraseFromParent();
Changed = true;
I1 = BB1_Itr++;
I2 = BB2_Itr++;
DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);
if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
while (isa<DbgInfoIntrinsic>(I1))
I1 = BB1_Itr++;
while (isa<DbgInfoIntrinsic>(I2))
I2 = BB2_Itr++;
}
} while (I1->isIdenticalToWhenDefined(I2));
return true;
HoistTerminator:
if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))
return Changed;
for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) {
PHINode *PN;
for (BasicBlock::iterator BBI = SI->begin();
(PN = dyn_cast<PHINode>(BBI)); ++BBI) {
Value *BB1V = PN->getIncomingValueForBlock(BB1);
Value *BB2V = PN->getIncomingValueForBlock(BB2);
if (BB1V == BB2V)
continue;
if (passingValueIsAlwaysUndefined(BB1V, PN) ||
passingValueIsAlwaysUndefined(BB2V, PN))
return Changed;
if (isa<ConstantExpr>(BB1V) && !isSafeToSpeculativelyExecute(BB1V))
return Changed;
if (isa<ConstantExpr>(BB2V) && !isSafeToSpeculativelyExecute(BB2V))
return Changed;
}
}
Instruction *NT = I1->clone();
BIParent->getInstList().insert(BI, NT);
if (!NT->getType()->isVoidTy()) {
I1->replaceAllUsesWith(NT);
I2->replaceAllUsesWith(NT);
NT->takeName(I1);
}
IRBuilder<true, NoFolder> Builder(NT);
std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects;
for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) {
PHINode *PN;
for (BasicBlock::iterator BBI = SI->begin();
(PN = dyn_cast<PHINode>(BBI)); ++BBI) {
Value *BB1V = PN->getIncomingValueForBlock(BB1);
Value *BB2V = PN->getIncomingValueForBlock(BB2);
if (BB1V == BB2V) continue;
SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
if (!SI)
SI = cast<SelectInst>
(Builder.CreateSelect(BI->getCondition(), BB1V, BB2V,
BB1V->getName()+"."+BB2V->getName()));
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2)
PN->setIncomingValue(i, SI);
}
}
for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI)
AddPredecessorToBlock(*SI, BIParent, BB1);
EraseTerminatorInstAndDCECond(BI);
return true;
}
static bool SinkThenElseCodeToEnd(BranchInst *BI1) {
assert(BI1->isUnconditional());
BasicBlock *BB1 = BI1->getParent();
BasicBlock *BBEnd = BI1->getSuccessor(0);
pred_iterator PI = pred_begin(BBEnd), PE = pred_end(BBEnd);
BasicBlock *Pred0 = *PI++;
if (PI == PE) return false;
BasicBlock *Pred1 = *PI++;
if (PI != PE) return false;
BasicBlock *BB2 = (Pred0 == BB1) ? Pred1 : Pred0;
BranchInst *BI2 = dyn_cast<BranchInst>(BB2->getTerminator());
if (!BI2 || !BI2->isUnconditional())
return false;
SmallDenseMap<std::pair<Value *, Value *>, PHINode *> JointValueMap;
Instruction *FirstNonPhiInBBEnd = nullptr;
for (BasicBlock::iterator I = BBEnd->begin(), E = BBEnd->end(); I != E; ++I) {
if (PHINode *PN = dyn_cast<PHINode>(I)) {
Value *BB1V = PN->getIncomingValueForBlock(BB1);
Value *BB2V = PN->getIncomingValueForBlock(BB2);
JointValueMap[std::make_pair(BB1V, BB2V)] = PN;
} else {
FirstNonPhiInBBEnd = &*I;
break;
}
}
if (!FirstNonPhiInBBEnd)
return false;
BasicBlock::InstListType::reverse_iterator RI1 = BB1->getInstList().rbegin(),
RE1 = BB1->getInstList().rend(),
RI2 = BB2->getInstList().rbegin(),
RE2 = BB2->getInstList().rend();
while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1)) ++RI1;
if (RI1 == RE1)
return false;
while (RI2 != RE2 && isa<DbgInfoIntrinsic>(&*RI2)) ++RI2;
if (RI2 == RE2)
return false;
++RI1;
++RI2;
bool Changed = false;
while (RI1 != RE1 && RI2 != RE2) {
while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1)) ++RI1;
if (RI1 == RE1)
return Changed;
while (RI2 != RE2 && isa<DbgInfoIntrinsic>(&*RI2)) ++RI2;
if (RI2 == RE2)
return Changed;
Instruction *I1 = &*RI1, *I2 = &*RI2;
auto InstPair = std::make_pair(I1, I2);
if (isa<PHINode>(I1) || isa<PHINode>(I2) ||
isa<TerminatorInst>(I1) || isa<TerminatorInst>(I2) ||
isa<LandingPadInst>(I1) || isa<LandingPadInst>(I2) ||
isa<AllocaInst>(I1) || isa<AllocaInst>(I2) ||
I1->mayHaveSideEffects() || I2->mayHaveSideEffects() ||
I1->mayReadOrWriteMemory() || I2->mayReadOrWriteMemory() ||
!I1->hasOneUse() || !I2->hasOneUse() ||
!JointValueMap.count(InstPair))
return Changed;
ICmpInst *ICmp1 = dyn_cast<ICmpInst>(I1), *ICmp2 = dyn_cast<ICmpInst>(I2);
bool SwapOpnds = false;
if (ICmp1 && ICmp2 &&
ICmp1->getOperand(0) != ICmp2->getOperand(0) &&
ICmp1->getOperand(1) != ICmp2->getOperand(1) &&
(ICmp1->getOperand(0) == ICmp2->getOperand(1) ||
ICmp1->getOperand(1) == ICmp2->getOperand(0))) {
ICmp2->swapOperands();
SwapOpnds = true;
}
if (!I1->isSameOperationAs(I2)) {
if (SwapOpnds)
ICmp2->swapOperands();
return Changed;
}
Value *DifferentOp1 = nullptr, *DifferentOp2 = nullptr;
unsigned Op1Idx = ~0U;
for (unsigned I = 0, E = I1->getNumOperands(); I != E; ++I) {
if (I1->getOperand(I) == I2->getOperand(I))
continue;
if (Op1Idx != ~0U ||
isa<Constant>(I1->getOperand(I)) ||
isa<Constant>(I2->getOperand(I))) {
if (SwapOpnds)
ICmp2->swapOperands();
return Changed;
}
DifferentOp1 = I1->getOperand(I);
Op1Idx = I;
DifferentOp2 = I2->getOperand(I);
}
DEBUG(dbgs() << "SINK common instructions " << *I1 << "\n");
DEBUG(dbgs() << " " << *I2 << "\n");
if (Op1Idx != ~0U) {
auto &NewPN = JointValueMap[std::make_pair(DifferentOp1, DifferentOp2)];
if (!NewPN) {
NewPN =
PHINode::Create(DifferentOp1->getType(), 2,
DifferentOp1->getName() + ".sink", BBEnd->begin());
NewPN->addIncoming(DifferentOp1, BB1);
NewPN->addIncoming(DifferentOp2, BB2);
DEBUG(dbgs() << "Create PHI node " << *NewPN << "\n";);
}
I1->setOperand(Op1Idx, NewPN);
}
PHINode *OldPN = JointValueMap[InstPair];
JointValueMap.erase(InstPair);
bool UpdateRE1 = (I1 == BB1->begin()), UpdateRE2 = (I2 == BB2->begin());
BBEnd->getInstList().splice(FirstNonPhiInBBEnd, BB1->getInstList(), I1);
if (!OldPN->use_empty())
OldPN->replaceAllUsesWith(I1);
OldPN->eraseFromParent();
if (!I2->use_empty())
I2->replaceAllUsesWith(I1);
I1->intersectOptionalDataWith(I2);
I2->eraseFromParent();
if (UpdateRE1)
RE1 = BB1->getInstList().rend();
if (UpdateRE2)
RE2 = BB2->getInstList().rend();
FirstNonPhiInBBEnd = I1;
NumSinkCommons++;
Changed = true;
}
return Changed;
}
static Value *isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB,
BasicBlock *StoreBB, BasicBlock *EndBB) {
StoreInst *StoreToHoist = dyn_cast<StoreInst>(I);
if (!StoreToHoist)
return nullptr;
if (!StoreToHoist->isSimple())
return nullptr;
Value *StorePtr = StoreToHoist->getPointerOperand();
unsigned MaxNumInstToLookAt = 10;
for (BasicBlock::reverse_iterator RI = BrBB->rbegin(),
RE = BrBB->rend(); RI != RE && (--MaxNumInstToLookAt); ++RI) {
Instruction *CurI = &*RI;
if (CurI->mayHaveSideEffects() && !isa<StoreInst>(CurI))
return nullptr;
StoreInst *SI = dyn_cast<StoreInst>(CurI);
if (SI && SI->getPointerOperand() == StorePtr)
return SI->getValueOperand();
else if (SI)
return nullptr; }
return nullptr;
}
static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB) {
Value *BrCond = BI->getCondition();
if (isa<FCmpInst>(BrCond))
return false;
BasicBlock *BB = BI->getParent();
BasicBlock *EndBB = ThenBB->getTerminator()->getSuccessor(0);
bool Invert = false;
if (ThenBB != BI->getSuccessor(0)) {
assert(ThenBB == BI->getSuccessor(1) && "No edge from 'if' block?");
Invert = true;
}
assert(EndBB == BI->getSuccessor(!Invert) && "No edge from to end block");
SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
unsigned SpeculationCost = 0;
Value *SpeculatedStoreValue = nullptr;
StoreInst *SpeculatedStore = nullptr;
for (BasicBlock::iterator BBI = ThenBB->begin(),
BBE = std::prev(ThenBB->end());
BBI != BBE; ++BBI) {
Instruction *I = BBI;
if (isa<DbgInfoIntrinsic>(I))
continue;
++SpeculationCost;
if (SpeculationCost > 1)
return false;
if (!isSafeToSpeculativelyExecute(I) &&
!(HoistCondStores && (SpeculatedStoreValue = isSafeToSpeculateStore(
I, BB, ThenBB, EndBB))))
return false;
if (!SpeculatedStoreValue &&
ComputeSpeculationCost(I) > PHINodeFoldingThreshold)
return false;
if (SpeculatedStoreValue)
SpeculatedStore = cast<StoreInst>(I);
for (User::op_iterator i = I->op_begin(), e = I->op_end();
i != e; ++i) {
Instruction *OpI = dyn_cast<Instruction>(*i);
if (!OpI || OpI->getParent() != BB ||
OpI->mayHaveSideEffects())
continue;
++SinkCandidateUseCounts[OpI];
}
}
for (SmallDenseMap<Instruction *, unsigned, 4>::iterator I =
SinkCandidateUseCounts.begin(), E = SinkCandidateUseCounts.end();
I != E; ++I)
if (I->first->getNumUses() == I->second) {
++SpeculationCost;
if (SpeculationCost > 1)
return false;
}
bool HaveRewritablePHIs = false;
for (BasicBlock::iterator I = EndBB->begin();
PHINode *PN = dyn_cast<PHINode>(I); ++I) {
Value *OrigV = PN->getIncomingValueForBlock(BB);
Value *ThenV = PN->getIncomingValueForBlock(ThenBB);
if (ThenV == OrigV)
continue;
if (passingValueIsAlwaysUndefined(OrigV, PN) ||
passingValueIsAlwaysUndefined(ThenV, PN))
return false;
HaveRewritablePHIs = true;
ConstantExpr *OrigCE = dyn_cast<ConstantExpr>(OrigV);
ConstantExpr *ThenCE = dyn_cast<ConstantExpr>(ThenV);
if (!OrigCE && !ThenCE)
continue;
if ((ThenCE && !isSafeToSpeculativelyExecute(ThenCE)) ||
(OrigCE && !isSafeToSpeculativelyExecute(OrigCE)))
return false;
unsigned OrigCost = OrigCE ? ComputeSpeculationCost(OrigCE) : 0;
unsigned ThenCost = ThenCE ? ComputeSpeculationCost(ThenCE) : 0;
if (OrigCost + ThenCost > 2 * PHINodeFoldingThreshold)
return false;
++SpeculationCost;
if (SpeculationCost > 1)
return false;
}
if (!HaveRewritablePHIs && !(HoistCondStores && SpeculatedStoreValue))
return false;
DEBUG(dbgs() << "SPECULATIVELY EXECUTING BB" << *ThenBB << "\n";);
if (SpeculatedStoreValue) {
IRBuilder<true, NoFolder> Builder(BI);
Value *TrueV = SpeculatedStore->getValueOperand();
Value *FalseV = SpeculatedStoreValue;
if (Invert)
std::swap(TrueV, FalseV);
Value *S = Builder.CreateSelect(BrCond, TrueV, FalseV, TrueV->getName() +
"." + FalseV->getName());
SpeculatedStore->setOperand(0, S);
}
BB->getInstList().splice(BI, ThenBB->getInstList(), ThenBB->begin(),
std::prev(ThenBB->end()));
IRBuilder<true, NoFolder> Builder(BI);
for (BasicBlock::iterator I = EndBB->begin();
PHINode *PN = dyn_cast<PHINode>(I); ++I) {
unsigned OrigI = PN->getBasicBlockIndex(BB);
unsigned ThenI = PN->getBasicBlockIndex(ThenBB);
Value *OrigV = PN->getIncomingValue(OrigI);
Value *ThenV = PN->getIncomingValue(ThenI);
if (OrigV == ThenV)
continue;
Value *TrueV = ThenV, *FalseV = OrigV;
if (Invert)
std::swap(TrueV, FalseV);
Value *V = Builder.CreateSelect(BrCond, TrueV, FalseV,
TrueV->getName() + "." + FalseV->getName());
PN->setIncomingValue(OrigI, V);
PN->setIncomingValue(ThenI, V);
}
++NumSpeculations;
return true;
}
static bool HasNoDuplicateCall(const BasicBlock *BB) {
for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
const CallInst *CI = dyn_cast<CallInst>(I);
if (!CI)
continue;
if (CI->cannotDuplicate())
return true;
}
return false;
}
static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) {
BranchInst *BI = cast<BranchInst>(BB->getTerminator());
unsigned Size = 0;
for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) {
if (isa<DbgInfoIntrinsic>(BBI))
continue;
if (Size > 10) return false; ++Size;
for (User *U : BBI->users()) {
Instruction *UI = cast<Instruction>(U);
if (UI->getParent() != BB || isa<PHINode>(UI)) return false;
}
}
return true;
}
static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout &DL) {
BasicBlock *BB = BI->getParent();
PHINode *PN = dyn_cast<PHINode>(BI->getCondition());
if (!PN || PN->getParent() != BB || !PN->hasOneUse())
return false;
if (PN->getNumIncomingValues() == 1) {
FoldSingleEntryPHINodes(PN->getParent());
return true;
}
if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false;
if (HasNoDuplicateCall(BB)) return false;
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
ConstantInt *CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i));
if (!CB || !CB->getType()->isIntegerTy(1)) continue;
BasicBlock *PredBB = PN->getIncomingBlock(i);
BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue());
if (RealDest == BB) continue; if (isa<IndirectBrInst>(PredBB->getTerminator())) continue;
BasicBlock *EdgeBB = BasicBlock::Create(BB->getContext(),
RealDest->getName()+".critedge",
RealDest->getParent(), RealDest);
BranchInst::Create(RealDest, EdgeBB);
AddPredecessorToBlock(RealDest, EdgeBB, BB);
BasicBlock::iterator InsertPt = EdgeBB->begin();
DenseMap<Value*, Value*> TranslateMap; for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) {
if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB);
continue;
}
Instruction *N = BBI->clone();
if (BBI->hasName()) N->setName(BBI->getName()+".c");
for (User::op_iterator i = N->op_begin(), e = N->op_end();
i != e; ++i) {
DenseMap<Value*, Value*>::iterator PI = TranslateMap.find(*i);
if (PI != TranslateMap.end())
*i = PI->second;
}
if (Value *V = SimplifyInstruction(N, DL)) {
TranslateMap[BBI] = V;
delete N; } else {
EdgeBB->getInstList().insert(InsertPt, N);
if (!BBI->use_empty())
TranslateMap[BBI] = N;
}
}
TerminatorInst *PredBBTI = PredBB->getTerminator();
for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i)
if (PredBBTI->getSuccessor(i) == BB) {
BB->removePredecessor(PredBB);
PredBBTI->setSuccessor(i, EdgeBB);
}
return FoldCondBranchOnPHI(BI, DL) | true;
}
return false;
}
static bool FoldTwoEntryPHINode(PHINode *PN, const DataLayout &DL) {
BasicBlock *BB = PN->getParent();
BasicBlock *IfTrue, *IfFalse;
Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse);
if (!IfCond ||
isa<ConstantInt>(IfCond))
return false;
unsigned NumPhis = 0;
for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I)
if (NumPhis > 2)
return false;
SmallPtrSet<Instruction*, 4> AggressiveInsts;
unsigned MaxCostVal0 = PHINodeFoldingThreshold,
MaxCostVal1 = PHINodeFoldingThreshold;
for (BasicBlock::iterator II = BB->begin(); isa<PHINode>(II);) {
PHINode *PN = cast<PHINode>(II++);
if (Value *V = SimplifyInstruction(PN, DL)) {
PN->replaceAllUsesWith(V);
PN->eraseFromParent();
continue;
}
if (!DominatesMergePoint(PN->getIncomingValue(0), BB, &AggressiveInsts,
MaxCostVal0) ||
!DominatesMergePoint(PN->getIncomingValue(1), BB, &AggressiveInsts,
MaxCostVal1))
return false;
}
PN = dyn_cast<PHINode>(BB->begin());
if (!PN) return true;
if (PN->getType()->isIntegerTy(1) &&
(isa<BinaryOperator>(PN->getIncomingValue(0)) ||
isa<BinaryOperator>(PN->getIncomingValue(1)) ||
isa<BinaryOperator>(IfCond)))
return false;
BasicBlock *DomBlock = nullptr;
BasicBlock *IfBlock1 = PN->getIncomingBlock(0);
BasicBlock *IfBlock2 = PN->getIncomingBlock(1);
if (cast<BranchInst>(IfBlock1->getTerminator())->isConditional()) {
IfBlock1 = nullptr;
} else {
DomBlock = *pred_begin(IfBlock1);
for (BasicBlock::iterator I = IfBlock1->begin();!isa<TerminatorInst>(I);++I)
if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) {
return false;
}
}
if (cast<BranchInst>(IfBlock2->getTerminator())->isConditional()) {
IfBlock2 = nullptr;
} else {
DomBlock = *pred_begin(IfBlock2);
for (BasicBlock::iterator I = IfBlock2->begin();!isa<TerminatorInst>(I);++I)
if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) {
return false;
}
}
DEBUG(dbgs() << "FOUND IF CONDITION! " << *IfCond << " T: "
<< IfTrue->getName() << " F: " << IfFalse->getName() << "\n");
Instruction *InsertPt = DomBlock->getTerminator();
IRBuilder<true, NoFolder> Builder(InsertPt);
if (IfBlock1)
DomBlock->getInstList().splice(InsertPt,
IfBlock1->getInstList(), IfBlock1->begin(),
IfBlock1->getTerminator());
if (IfBlock2)
DomBlock->getInstList().splice(InsertPt,
IfBlock2->getInstList(), IfBlock2->begin(),
IfBlock2->getTerminator());
while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
Value *TrueVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse);
Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue);
SelectInst *NV =
cast<SelectInst>(Builder.CreateSelect(IfCond, TrueVal, FalseVal, ""));
PN->replaceAllUsesWith(NV);
NV->takeName(PN);
PN->eraseFromParent();
}
TerminatorInst *OldTI = DomBlock->getTerminator();
Builder.SetInsertPoint(OldTI);
Builder.CreateBr(BB);
OldTI->eraseFromParent();
return true;
}
static bool SimplifyCondBranchToTwoReturns(BranchInst *BI,
IRBuilder<> &Builder) {
assert(BI->isConditional() && "Must be a conditional branch");
BasicBlock *TrueSucc = BI->getSuccessor(0);
BasicBlock *FalseSucc = BI->getSuccessor(1);
ReturnInst *TrueRet = cast<ReturnInst>(TrueSucc->getTerminator());
ReturnInst *FalseRet = cast<ReturnInst>(FalseSucc->getTerminator());
if (!TrueSucc->getFirstNonPHIOrDbg()->isTerminator())
return false;
if (!FalseSucc->getFirstNonPHIOrDbg()->isTerminator())
return false;
Builder.SetInsertPoint(BI);
if (FalseRet->getNumOperands() == 0) {
TrueSucc->removePredecessor(BI->getParent());
FalseSucc->removePredecessor(BI->getParent());
Builder.CreateRetVoid();
EraseTerminatorInstAndDCECond(BI);
return true;
}
Value *TrueValue = TrueRet->getReturnValue();
Value *FalseValue = FalseRet->getReturnValue();
if (PHINode *TVPN = dyn_cast_or_null<PHINode>(TrueValue))
if (TVPN->getParent() == TrueSucc)
TrueValue = TVPN->getIncomingValueForBlock(BI->getParent());
if (PHINode *FVPN = dyn_cast_or_null<PHINode>(FalseValue))
if (FVPN->getParent() == FalseSucc)
FalseValue = FVPN->getIncomingValueForBlock(BI->getParent());
if (ConstantExpr *TCV = dyn_cast_or_null<ConstantExpr>(TrueValue))
if (TCV->canTrap())
return false;
if (ConstantExpr *FCV = dyn_cast_or_null<ConstantExpr>(FalseValue))
if (FCV->canTrap())
return false;
TrueSucc->removePredecessor(BI->getParent());
FalseSucc->removePredecessor(BI->getParent());
Value *BrCond = BI->getCondition();
if (TrueValue) {
if (TrueValue == FalseValue || isa<UndefValue>(FalseValue)) {
} else if (isa<UndefValue>(TrueValue)) {
TrueValue = FalseValue;
} else {
TrueValue = Builder.CreateSelect(BrCond, TrueValue,
FalseValue, "retval");
}
}
Value *RI = !TrueValue ?
Builder.CreateRetVoid() : Builder.CreateRet(TrueValue);
(void) RI;
DEBUG(dbgs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:"
<< "\n " << *BI << "NewRet = " << *RI
<< "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc);
EraseTerminatorInstAndDCECond(BI);
return true;
}
static bool ExtractBranchMetadata(BranchInst *BI,
uint64_t &ProbTrue, uint64_t &ProbFalse) {
assert(BI->isConditional() &&
"Looking for probabilities on unconditional branch?");
MDNode *ProfileData = BI->getMetadata(LLVMContext::MD_prof);
if (!ProfileData || ProfileData->getNumOperands() != 3) return false;
ConstantInt *CITrue =
mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(1));
ConstantInt *CIFalse =
mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(2));
if (!CITrue || !CIFalse) return false;
ProbTrue = CITrue->getValue().getZExtValue();
ProbFalse = CIFalse->getValue().getZExtValue();
return true;
}
static bool checkCSEInPredecessor(Instruction *Inst, BasicBlock *PB) {
if (!isa<BinaryOperator>(Inst) && !isa<CmpInst>(Inst))
return false;
for (BasicBlock::iterator I = PB->begin(), E = PB->end(); I != E; I++) {
Instruction *PBI = &*I;
if (Inst->isIdenticalTo(PBI)) {
Inst->replaceAllUsesWith(PBI);
Inst->eraseFromParent();
return true;
}
}
return false;
}
bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) {
BasicBlock *BB = BI->getParent();
Instruction *Cond = nullptr;
if (BI->isConditional())
Cond = dyn_cast<Instruction>(BI->getCondition());
else {
if (BasicBlock *PB = BB->getSinglePredecessor())
if (BranchInst *PBI = dyn_cast<BranchInst>(PB->getTerminator()))
if (PBI->isConditional() &&
(BI->getSuccessor(0) == PBI->getSuccessor(0) ||
BI->getSuccessor(0) == PBI->getSuccessor(1))) {
for (BasicBlock::iterator I = BB->begin(), E = BB->end();
I != E; ) {
Instruction *Curr = I++;
if (isa<CmpInst>(Curr)) {
Cond = Curr;
break;
}
if (!checkCSEInPredecessor(Curr, PB))
return false;
}
}
if (!Cond)
return false;
}
if (!Cond || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) ||
Cond->getParent() != BB || !Cond->hasOneUse())
return false;
BasicBlock::iterator CondIt = Cond; ++CondIt;
while (isa<DbgInfoIntrinsic>(CondIt)) ++CondIt;
if (&*CondIt != BI)
return false;
unsigned NumBonusInsts = 0;
for (auto I = BB->begin(); Cond != I; ++I) {
if (isa<DbgInfoIntrinsic>(I))
continue;
if (!I->hasOneUse() || !isSafeToSpeculativelyExecute(I))
return false;
Instruction *User = dyn_cast<Instruction>(I->user_back());
if (User == nullptr || User->getParent() != BB)
return false;
++NumBonusInsts;
if (NumBonusInsts > BonusInstThreshold)
return false;
}
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0)))
if (CE->canTrap())
return false;
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1)))
if (CE->canTrap())
return false;
BasicBlock *TrueDest = BI->getSuccessor(0);
BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : nullptr;
if (TrueDest == BB || FalseDest == BB)
return false;
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
BasicBlock *PredBlock = *PI;
BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
SmallVector<PHINode*, 4> PHIs;
if (!PBI || PBI->isUnconditional() ||
(BI->isConditional() &&
!SafeToMergeTerminators(BI, PBI)) ||
(!BI->isConditional() &&
!isProfitableToFoldUnconditional(BI, PBI, Cond, PHIs)))
continue;
Instruction::BinaryOps Opc = Instruction::BinaryOpsEnd;
bool InvertPredCond = false;
if (BI->isConditional()) {
if (PBI->getSuccessor(0) == TrueDest)
Opc = Instruction::Or;
else if (PBI->getSuccessor(1) == FalseDest)
Opc = Instruction::And;
else if (PBI->getSuccessor(0) == FalseDest)
Opc = Instruction::And, InvertPredCond = true;
else if (PBI->getSuccessor(1) == TrueDest)
Opc = Instruction::Or, InvertPredCond = true;
else
continue;
} else {
if (PBI->getSuccessor(0) != TrueDest && PBI->getSuccessor(1) != TrueDest)
continue;
}
DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
IRBuilder<> Builder(PBI);
if (InvertPredCond) {
Value *NewCond = PBI->getCondition();
if (NewCond->hasOneUse() && isa<CmpInst>(NewCond)) {
CmpInst *CI = cast<CmpInst>(NewCond);
CI->setPredicate(CI->getInversePredicate());
} else {
NewCond = Builder.CreateNot(NewCond,
PBI->getCondition()->getName()+".not");
}
PBI->setCondition(NewCond);
PBI->swapSuccessors();
}
ValueToValueMapTy VMap; for (auto BonusInst = BB->begin(); Cond != BonusInst; ++BonusInst) {
if (isa<DbgInfoIntrinsic>(BonusInst))
continue;
Instruction *NewBonusInst = BonusInst->clone();
RemapInstruction(NewBonusInst, VMap,
RF_NoModuleLevelChanges | RF_IgnoreMissingEntries);
VMap[BonusInst] = NewBonusInst;
NewBonusInst->dropUnknownMetadata(LLVMContext::MD_dbg);
PredBlock->getInstList().insert(PBI, NewBonusInst);
NewBonusInst->takeName(BonusInst);
BonusInst->setName(BonusInst->getName() + ".old");
}
Instruction *New = Cond->clone();
RemapInstruction(New, VMap,
RF_NoModuleLevelChanges | RF_IgnoreMissingEntries);
PredBlock->getInstList().insert(PBI, New);
New->takeName(Cond);
Cond->setName(New->getName() + ".old");
if (BI->isConditional()) {
Instruction *NewCond =
cast<Instruction>(Builder.CreateBinOp(Opc, PBI->getCondition(),
New, "or.cond"));
PBI->setCondition(NewCond);
uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
bool PredHasWeights = ExtractBranchMetadata(PBI, PredTrueWeight,
PredFalseWeight);
bool SuccHasWeights = ExtractBranchMetadata(BI, SuccTrueWeight,
SuccFalseWeight);
SmallVector<uint64_t, 8> NewWeights;
if (PBI->getSuccessor(0) == BB) {
if (PredHasWeights && SuccHasWeights) {
NewWeights.push_back(PredTrueWeight * SuccTrueWeight);
NewWeights.push_back(PredFalseWeight * (SuccFalseWeight +
SuccTrueWeight) + PredTrueWeight * SuccFalseWeight);
}
AddPredecessorToBlock(TrueDest, PredBlock, BB);
PBI->setSuccessor(0, TrueDest);
}
if (PBI->getSuccessor(1) == BB) {
if (PredHasWeights && SuccHasWeights) {
NewWeights.push_back(PredTrueWeight * (SuccFalseWeight +
SuccTrueWeight) + PredFalseWeight * SuccTrueWeight);
NewWeights.push_back(PredFalseWeight * SuccFalseWeight);
}
AddPredecessorToBlock(FalseDest, PredBlock, BB);
PBI->setSuccessor(1, FalseDest);
}
if (NewWeights.size() == 2) {
FitWeights(NewWeights);
SmallVector<uint32_t, 8> MDWeights(NewWeights.begin(),NewWeights.end());
PBI->setMetadata(LLVMContext::MD_prof,
MDBuilder(BI->getContext()).
createBranchWeights(MDWeights));
} else
PBI->setMetadata(LLVMContext::MD_prof, nullptr);
} else {
for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
ConstantInt *PBI_C = cast<ConstantInt>(
PHIs[i]->getIncomingValueForBlock(PBI->getParent()));
assert(PBI_C->getType()->isIntegerTy(1));
Instruction *MergedCond = nullptr;
if (PBI->getSuccessor(0) == TrueDest) {
Instruction *NotCond =
cast<Instruction>(Builder.CreateNot(PBI->getCondition(),
"not.cond"));
MergedCond =
cast<Instruction>(Builder.CreateBinOp(Instruction::And,
NotCond, New,
"and.cond"));
if (PBI_C->isOne())
MergedCond =
cast<Instruction>(Builder.CreateBinOp(Instruction::Or,
PBI->getCondition(), MergedCond,
"or.cond"));
} else {
MergedCond =
cast<Instruction>(Builder.CreateBinOp(Instruction::And,
PBI->getCondition(), New,
"and.cond"));
if (PBI_C->isOne()) {
Instruction *NotCond =
cast<Instruction>(Builder.CreateNot(PBI->getCondition(),
"not.cond"));
MergedCond =
cast<Instruction>(Builder.CreateBinOp(Instruction::Or,
NotCond, MergedCond,
"or.cond"));
}
}
PHIs[i]->setIncomingValue(PHIs[i]->getBasicBlockIndex(PBI->getParent()),
MergedCond);
}
BranchInst *New_PBI = BranchInst::Create(TrueDest, PBI);
EraseTerminatorInstAndDCECond(PBI);
PBI = New_PBI;
}
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
if (isa<DbgInfoIntrinsic>(*I))
I->clone()->insertBefore(PBI);
return true;
}
return false;
}
static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) {
assert(PBI->isConditional() && BI->isConditional());
BasicBlock *BB = BI->getParent();
if (PBI->getCondition() == BI->getCondition() &&
PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
if (BB->getSinglePredecessor()) {
bool CondIsTrue = PBI->getSuccessor(0) == BB;
BI->setCondition(ConstantInt::get(Type::getInt1Ty(BB->getContext()),
CondIsTrue));
return true; }
if (BlockIsSimpleEnoughToThreadThrough(BB)) {
pred_iterator PB = pred_begin(BB), PE = pred_end(BB);
PHINode *NewPN = PHINode::Create(Type::getInt1Ty(BB->getContext()),
std::distance(PB, PE),
BI->getCondition()->getName() + ".pr",
BB->begin());
for (pred_iterator PI = PB; PI != PE; ++PI) {
BasicBlock *P = *PI;
if ((PBI = dyn_cast<BranchInst>(P->getTerminator())) &&
PBI != BI && PBI->isConditional() &&
PBI->getCondition() == BI->getCondition() &&
PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
bool CondIsTrue = PBI->getSuccessor(0) == BB;
NewPN->addIncoming(ConstantInt::get(Type::getInt1Ty(BB->getContext()),
CondIsTrue), P);
} else {
NewPN->addIncoming(BI->getCondition(), P);
}
}
BI->setCondition(NewPN);
return true;
}
}
BasicBlock::iterator BBI = BB->begin();
while (isa<DbgInfoIntrinsic>(BBI))
++BBI;
if (&*BBI != BI)
return false;
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BI->getCondition()))
if (CE->canTrap())
return false;
int PBIOp, BIOp;
if (PBI->getSuccessor(0) == BI->getSuccessor(0))
PBIOp = BIOp = 0;
else if (PBI->getSuccessor(0) == BI->getSuccessor(1))
PBIOp = 0, BIOp = 1;
else if (PBI->getSuccessor(1) == BI->getSuccessor(0))
PBIOp = 1, BIOp = 0;
else if (PBI->getSuccessor(1) == BI->getSuccessor(1))
PBIOp = BIOp = 1;
else
return false;
if (PBI->getSuccessor(PBIOp) == BB)
return false;
BasicBlock *CommonDest = PBI->getSuccessor(PBIOp);
unsigned NumPhis = 0;
for (BasicBlock::iterator II = CommonDest->begin();
isa<PHINode>(II); ++II, ++NumPhis) {
if (NumPhis > 2) return false;
PHINode *PN = cast<PHINode>(II);
Value *BIV = PN->getIncomingValueForBlock(BB);
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BIV))
if (CE->canTrap())
return false;
unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent());
Value *PBIV = PN->getIncomingValue(PBBIdx);
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(PBIV))
if (CE->canTrap())
return false;
}
BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1);
DEBUG(dbgs() << "FOLDING BRs:" << *PBI->getParent()
<< "AND: " << *BI->getParent());
if (OtherDest == BB) {
BasicBlock *InfLoopBlock = BasicBlock::Create(BB->getContext(),
"infloop", BB->getParent());
BranchInst::Create(InfLoopBlock, InfLoopBlock);
OtherDest = InfLoopBlock;
}
DEBUG(dbgs() << *PBI->getParent()->getParent());
Value *PBICond = PBI->getCondition();
IRBuilder<true, NoFolder> Builder(PBI);
if (PBIOp)
PBICond = Builder.CreateNot(PBICond, PBICond->getName()+".not");
Value *BICond = BI->getCondition();
if (BIOp)
BICond = Builder.CreateNot(BICond, BICond->getName()+".not");
Value *Cond = Builder.CreateOr(PBICond, BICond, "brmerge");
PBI->setCondition(Cond);
PBI->setSuccessor(0, CommonDest);
PBI->setSuccessor(1, OtherDest);
uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
bool PredHasWeights = ExtractBranchMetadata(PBI, PredTrueWeight,
PredFalseWeight);
bool SuccHasWeights = ExtractBranchMetadata(BI, SuccTrueWeight,
SuccFalseWeight);
if (PredHasWeights && SuccHasWeights) {
uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
uint64_t PredOther = PBIOp ?PredTrueWeight : PredFalseWeight;
uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
SmallVector<uint64_t, 2> NewWeights;
NewWeights.push_back(PredCommon * (SuccCommon + SuccOther) +
PredOther * SuccCommon);
NewWeights.push_back(PredOther * SuccOther);
FitWeights(NewWeights);
SmallVector<uint32_t, 2> MDWeights(NewWeights.begin(),NewWeights.end());
PBI->setMetadata(LLVMContext::MD_prof,
MDBuilder(BI->getContext()).
createBranchWeights(MDWeights));
}
AddPredecessorToBlock(OtherDest, PBI->getParent(), BB);
PHINode *PN;
for (BasicBlock::iterator II = CommonDest->begin();
(PN = dyn_cast<PHINode>(II)); ++II) {
Value *BIV = PN->getIncomingValueForBlock(BB);
unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent());
Value *PBIV = PN->getIncomingValue(PBBIdx);
if (BIV != PBIV) {
Value *NV = cast<SelectInst>
(Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->getName()+".mux"));
PN->setIncomingValue(PBBIdx, NV);
}
}
DEBUG(dbgs() << "INTO: " << *PBI->getParent());
DEBUG(dbgs() << *PBI->getParent()->getParent());
return true;
}
static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond,
BasicBlock *TrueBB, BasicBlock *FalseBB,
uint32_t TrueWeight,
uint32_t FalseWeight){
BasicBlock *KeepEdge1 = TrueBB;
BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : nullptr;
for (unsigned I = 0, E = OldTerm->getNumSuccessors(); I != E; ++I) {
BasicBlock *Succ = OldTerm->getSuccessor(I);
if (Succ == KeepEdge1)
KeepEdge1 = nullptr;
else if (Succ == KeepEdge2)
KeepEdge2 = nullptr;
else
Succ->removePredecessor(OldTerm->getParent());
}
IRBuilder<> Builder(OldTerm);
Builder.SetCurrentDebugLocation(OldTerm->getDebugLoc());
if (!KeepEdge1 && !KeepEdge2) {
if (TrueBB == FalseBB)
Builder.CreateBr(TrueBB);
else {
BranchInst *NewBI = Builder.CreateCondBr(Cond, TrueBB, FalseBB);
if (TrueWeight != FalseWeight)
NewBI->setMetadata(LLVMContext::MD_prof,
MDBuilder(OldTerm->getContext()).
createBranchWeights(TrueWeight, FalseWeight));
}
} else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
new UnreachableInst(OldTerm->getContext(), OldTerm);
} else {
if (!KeepEdge1)
Builder.CreateBr(TrueBB);
else
Builder.CreateBr(FalseBB);
}
EraseTerminatorInstAndDCECond(OldTerm);
return true;
}
static bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select) {
ConstantInt *TrueVal = dyn_cast<ConstantInt>(Select->getTrueValue());
ConstantInt *FalseVal = dyn_cast<ConstantInt>(Select->getFalseValue());
if (!TrueVal || !FalseVal)
return false;
Value *Condition = Select->getCondition();
BasicBlock *TrueBB = SI->findCaseValue(TrueVal).getCaseSuccessor();
BasicBlock *FalseBB = SI->findCaseValue(FalseVal).getCaseSuccessor();
uint32_t TrueWeight = 0, FalseWeight = 0;
SmallVector<uint64_t, 8> Weights;
bool HasWeights = HasBranchWeights(SI);
if (HasWeights) {
GetBranchWeights(SI, Weights);
if (Weights.size() == 1 + SI->getNumCases()) {
TrueWeight = (uint32_t)Weights[SI->findCaseValue(TrueVal).
getSuccessorIndex()];
FalseWeight = (uint32_t)Weights[SI->findCaseValue(FalseVal).
getSuccessorIndex()];
}
}
return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB,
TrueWeight, FalseWeight);
}
static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) {
BlockAddress *TBA = dyn_cast<BlockAddress>(SI->getTrueValue());
BlockAddress *FBA = dyn_cast<BlockAddress>(SI->getFalseValue());
if (!TBA || !FBA)
return false;
BasicBlock *TrueBB = TBA->getBasicBlock();
BasicBlock *FalseBB = FBA->getBasicBlock();
return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB,
0, 0);
}
static bool TryToSimplifyUncondBranchWithICmpInIt(
ICmpInst *ICI, IRBuilder<> &Builder, const DataLayout &DL,
const TargetTransformInfo &TTI, unsigned BonusInstThreshold,
AssumptionCache *AC) {
BasicBlock *BB = ICI->getParent();
if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse()) return false;
Value *V = ICI->getOperand(0);
ConstantInt *Cst = cast<ConstantInt>(ICI->getOperand(1));
BasicBlock *Pred = BB->getSinglePredecessor();
if (!Pred || !isa<SwitchInst>(Pred->getTerminator())) return false;
SwitchInst *SI = cast<SwitchInst>(Pred->getTerminator());
if (SI->getCondition() != V)
return false;
if (SI->getDefaultDest() != BB) {
ConstantInt *VVal = SI->findCaseDest(BB);
assert(VVal && "Should have a unique destination value");
ICI->setOperand(0, VVal);
if (Value *V = SimplifyInstruction(ICI, DL)) {
ICI->replaceAllUsesWith(V);
ICI->eraseFromParent();
}
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
}
if (SI->findCaseValue(Cst) != SI->case_default()) {
Value *V;
if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
V = ConstantInt::getFalse(BB->getContext());
else
V = ConstantInt::getTrue(BB->getContext());
ICI->replaceAllUsesWith(V);
ICI->eraseFromParent();
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
}
BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0);
PHINode *PHIUse = dyn_cast<PHINode>(ICI->user_back());
if (PHIUse == nullptr || PHIUse != &SuccBlock->front() ||
isa<PHINode>(++BasicBlock::iterator(PHIUse)))
return false;
Constant *DefaultCst = ConstantInt::getTrue(BB->getContext());
Constant *NewCst = ConstantInt::getFalse(BB->getContext());
if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
std::swap(DefaultCst, NewCst);
ICI->replaceAllUsesWith(DefaultCst);
ICI->eraseFromParent();
BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "switch.edge",
BB->getParent(), BB);
SmallVector<uint64_t, 8> Weights;
bool HasWeights = HasBranchWeights(SI);
if (HasWeights) {
GetBranchWeights(SI, Weights);
if (Weights.size() == 1 + SI->getNumCases()) {
Weights[0] = (Weights[0]+1) >> 1;
Weights.push_back(Weights[0]);
SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end());
SI->setMetadata(LLVMContext::MD_prof,
MDBuilder(SI->getContext()).
createBranchWeights(MDWeights));
}
}
SI->addCase(Cst, NewBB);
Builder.SetInsertPoint(NewBB);
Builder.SetCurrentDebugLocation(SI->getDebugLoc());
Builder.CreateBr(SuccBlock);
PHIUse->addIncoming(NewCst, NewBB);
return true;
}
static bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder,
const DataLayout &DL) {
Instruction *Cond = dyn_cast<Instruction>(BI->getCondition());
if (!Cond) return false;
ConstantComparesGatherer ConstantCompare(Cond, DL);
SmallVectorImpl<ConstantInt*> &Values = ConstantCompare.Vals;
Value *CompVal = ConstantCompare.CompValue;
unsigned UsedICmps = ConstantCompare.UsedICmps;
Value *ExtraCase = ConstantCompare.Extra;
if (!CompVal) return false;
if (UsedICmps <= 1)
return false;
bool TrueWhenEqual = (Cond->getOpcode() == Instruction::Or);
array_pod_sort(Values.begin(), Values.end(), ConstantIntSortPredicate);
Values.erase(std::unique(Values.begin(), Values.end()), Values.end());
if (ExtraCase && Values.size() < 2) return false;
BasicBlock *DefaultBB = BI->getSuccessor(1);
BasicBlock *EdgeBB = BI->getSuccessor(0);
if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB);
BasicBlock *BB = BI->getParent();
DEBUG(dbgs() << "Converting 'icmp' chain with " << Values.size()
<< " cases into SWITCH. BB is:\n" << *BB);
if (ExtraCase) {
BasicBlock *NewBB = BB->splitBasicBlock(BI, "switch.early.test");
TerminatorInst *OldTI = BB->getTerminator();
Builder.SetInsertPoint(OldTI);
if (TrueWhenEqual)
Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB);
else
Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB);
OldTI->eraseFromParent();
AddPredecessorToBlock(EdgeBB, BB, NewBB);
DEBUG(dbgs() << " ** 'icmp' chain unhandled condition: " << *ExtraCase
<< "\nEXTRABB = " << *BB);
BB = NewBB;
}
Builder.SetInsertPoint(BI);
if (CompVal->getType()->isPointerTy()) {
CompVal = Builder.CreatePtrToInt(
CompVal, DL.getIntPtrType(CompVal->getType()), "magicptr");
}
SwitchInst *New = Builder.CreateSwitch(CompVal, DefaultBB, Values.size());
for (unsigned i = 0, e = Values.size(); i != e; ++i)
New->addCase(Values[i], EdgeBB);
for (BasicBlock::iterator BBI = EdgeBB->begin();
isa<PHINode>(BBI); ++BBI) {
PHINode *PN = cast<PHINode>(BBI);
Value *InVal = PN->getIncomingValueForBlock(BB);
for (unsigned i = 0, e = Values.size()-1; i != e; ++i)
PN->addIncoming(InVal, BB);
}
EraseTerminatorInstAndDCECond(BI);
DEBUG(dbgs() << " ** 'icmp' chain result is:\n" << *BB << '\n');
return true;
}
bool SimplifyCFGOpt::SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder) {
BasicBlock *BB = RI->getParent();
LandingPadInst *LPInst = dyn_cast<LandingPadInst>(BB->getFirstNonPHI());
if (RI->getValue() != LPInst)
return false;
BasicBlock::iterator I = LPInst, E = RI;
while (++I != E)
if (!isa<DbgInfoIntrinsic>(I))
return false;
for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) {
InvokeInst *II = cast<InvokeInst>((*PI++)->getTerminator());
SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3);
CallInst *Call = CallInst::Create(II->getCalledValue(), Args, "", II);
Call->takeName(II);
Call->setCallingConv(II->getCallingConv());
Call->setAttributes(II->getAttributes());
Call->setDebugLoc(II->getDebugLoc());
II->replaceAllUsesWith(Call);
BB->removePredecessor(II->getParent());
BranchInst::Create(II->getNormalDest(), II);
II->eraseFromParent();
}
BB->eraseFromParent();
return true;
}
bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) {
BasicBlock *BB = RI->getParent();
if (!BB->getFirstNonPHIOrDbg()->isTerminator()) return false;
SmallVector<BasicBlock*, 8> UncondBranchPreds;
SmallVector<BranchInst*, 8> CondBranchPreds;
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
BasicBlock *P = *PI;
TerminatorInst *PTI = P->getTerminator();
if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) {
if (BI->isUnconditional())
UncondBranchPreds.push_back(P);
else
CondBranchPreds.push_back(BI);
}
}
if (!UncondBranchPreds.empty() && DupRet) {
while (!UncondBranchPreds.empty()) {
BasicBlock *Pred = UncondBranchPreds.pop_back_val();
DEBUG(dbgs() << "FOLDING: " << *BB
<< "INTO UNCOND BRANCH PRED: " << *Pred);
(void)FoldReturnIntoUncondBranch(RI, BB, Pred);
}
if (pred_empty(BB))
BB->eraseFromParent();
return true;
}
while (!CondBranchPreds.empty()) {
BranchInst *BI = CondBranchPreds.pop_back_val();
if (isa<ReturnInst>(BI->getSuccessor(0)->getTerminator()) &&
isa<ReturnInst>(BI->getSuccessor(1)->getTerminator()) &&
SimplifyCondBranchToTwoReturns(BI, Builder))
return true;
}
return false;
}
bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) {
BasicBlock *BB = UI->getParent();
bool Changed = false;
while (UI != BB->begin()) {
BasicBlock::iterator BBI = UI;
--BBI;
if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI)) break;
if (BBI->mayHaveSideEffects()) {
if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
if (SI->isVolatile())
break;
} else if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
if (LI->isVolatile())
break;
} else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(BBI)) {
if (RMWI->isVolatile())
break;
} else if (AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(BBI)) {
if (CXI->isVolatile())
break;
} else if (!isa<FenceInst>(BBI) && !isa<VAArgInst>(BBI) &&
!isa<LandingPadInst>(BBI)) {
break;
}
}
if (!BBI->use_empty())
BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
BBI->eraseFromParent();
Changed = true;
}
if (&BB->front() != UI) return Changed;
SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB));
for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
TerminatorInst *TI = Preds[i]->getTerminator();
IRBuilder<> Builder(TI);
if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
if (BI->isUnconditional()) {
if (BI->getSuccessor(0) == BB) {
new UnreachableInst(TI->getContext(), TI);
TI->eraseFromParent();
Changed = true;
}
} else {
if (BI->getSuccessor(0) == BB) {
Builder.CreateBr(BI->getSuccessor(1));
EraseTerminatorInstAndDCECond(BI);
} else if (BI->getSuccessor(1) == BB) {
Builder.CreateBr(BI->getSuccessor(0));
EraseTerminatorInstAndDCECond(BI);
Changed = true;
}
}
} else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
i != e; ++i)
if (i.getCaseSuccessor() == BB) {
BB->removePredecessor(SI->getParent());
SI->removeCase(i);
--i; --e;
Changed = true;
}
} else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
if (II->getUnwindDest() == BB) {
BranchInst *BI = Builder.CreateBr(II->getNormalDest());
II->removeFromParent();
SmallVector<Value*, 8> Args(II->op_begin(), II->op_end()-3);
Builder.SetInsertPoint(BI);
CallInst *CI = Builder.CreateCall(II->getCalledValue(),
Args, II->getName());
CI->setCallingConv(II->getCallingConv());
CI->setAttributes(II->getAttributes());
II->replaceAllUsesWith(CI);
delete II;
Changed = true;
}
}
}
if (pred_empty(BB) &&
BB != &BB->getParent()->getEntryBlock()) {
BB->eraseFromParent();
return true;
}
return Changed;
}
static bool CasesAreContiguous(SmallVectorImpl<ConstantInt *> &Cases) {
assert(Cases.size() >= 1);
array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate);
for (size_t I = 1, E = Cases.size(); I != E; ++I) {
if (Cases[I - 1]->getValue() != Cases[I]->getValue() + 1)
return false;
}
return true;
}
static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) {
assert(SI->getNumCases() > 1 && "Degenerate switch?");
bool HasDefault =
!isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
BasicBlock *DestA = HasDefault ? SI->getDefaultDest() : nullptr;
BasicBlock *DestB = nullptr;
SmallVector <ConstantInt *, 16> CasesA;
SmallVector <ConstantInt *, 16> CasesB;
for (SwitchInst::CaseIt I : SI->cases()) {
BasicBlock *Dest = I.getCaseSuccessor();
if (!DestA) DestA = Dest;
if (Dest == DestA) {
CasesA.push_back(I.getCaseValue());
continue;
}
if (!DestB) DestB = Dest;
if (Dest == DestB) {
CasesB.push_back(I.getCaseValue());
continue;
}
return false; }
assert(DestA && DestB && "Single-destination switch should have been folded.");
assert(DestA != DestB);
assert(DestB != SI->getDefaultDest());
assert(!CasesB.empty() && "There must be non-default cases.");
assert(!CasesA.empty() || HasDefault);
SmallVectorImpl<ConstantInt *> *ContiguousCases = nullptr;
BasicBlock *ContiguousDest = nullptr;
BasicBlock *OtherDest = nullptr;
if (!CasesA.empty() && CasesAreContiguous(CasesA)) {
ContiguousCases = &CasesA;
ContiguousDest = DestA;
OtherDest = DestB;
} else if (CasesAreContiguous(CasesB)) {
ContiguousCases = &CasesB;
ContiguousDest = DestB;
OtherDest = DestA;
} else
return false;
Constant *Offset = ConstantExpr::getNeg(ContiguousCases->back());
Constant *NumCases = ConstantInt::get(Offset->getType(), ContiguousCases->size());
Value *Sub = SI->getCondition();
if (!Offset->isNullValue())
Sub = Builder.CreateAdd(Sub, Offset, Sub->getName() + ".off");
Value *Cmp;
if (NumCases->isNullValue() && !ContiguousCases->empty())
Cmp = ConstantInt::getTrue(SI->getContext());
else
Cmp = Builder.CreateICmpULT(Sub, NumCases, "switch");
BranchInst *NewBI = Builder.CreateCondBr(Cmp, ContiguousDest, OtherDest);
if (HasBranchWeights(SI)) {
SmallVector<uint64_t, 8> Weights;
GetBranchWeights(SI, Weights);
if (Weights.size() == 1 + SI->getNumCases()) {
uint64_t TrueWeight = 0;
uint64_t FalseWeight = 0;
for (size_t I = 0, E = Weights.size(); I != E; ++I) {
if (SI->getSuccessor(I) == ContiguousDest)
TrueWeight += Weights[I];
else
FalseWeight += Weights[I];
}
while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
TrueWeight /= 2;
FalseWeight /= 2;
}
NewBI->setMetadata(LLVMContext::MD_prof,
MDBuilder(SI->getContext()).createBranchWeights(
(uint32_t)TrueWeight, (uint32_t)FalseWeight));
}
}
for (auto BBI = ContiguousDest->begin(); isa<PHINode>(BBI); ++BBI) {
unsigned PreviousEdges = ContiguousCases->size();
if (ContiguousDest == SI->getDefaultDest()) ++PreviousEdges;
for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I)
cast<PHINode>(BBI)->removeIncomingValue(SI->getParent());
}
for (auto BBI = OtherDest->begin(); isa<PHINode>(BBI); ++BBI) {
unsigned PreviousEdges = SI->getNumCases() - ContiguousCases->size();
if (OtherDest == SI->getDefaultDest()) ++PreviousEdges;
for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I)
cast<PHINode>(BBI)->removeIncomingValue(SI->getParent());
}
SI->eraseFromParent();
return true;
}
static bool EliminateDeadSwitchCases(SwitchInst *SI, AssumptionCache *AC,
const DataLayout &DL) {
Value *Cond = SI->getCondition();
unsigned Bits = Cond->getType()->getIntegerBitWidth();
APInt KnownZero(Bits, 0), KnownOne(Bits, 0);
computeKnownBits(Cond, KnownZero, KnownOne, DL, 0, AC, SI);
SmallVector<ConstantInt*, 8> DeadCases;
for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) {
if ((I.getCaseValue()->getValue() & KnownZero) != 0 ||
(I.getCaseValue()->getValue() & KnownOne) != KnownOne) {
DeadCases.push_back(I.getCaseValue());
DEBUG(dbgs() << "SimplifyCFG: switch case '"
<< I.getCaseValue() << "' is dead.\n");
}
}
SmallVector<uint64_t, 8> Weights;
bool HasWeight = HasBranchWeights(SI);
if (HasWeight) {
GetBranchWeights(SI, Weights);
HasWeight = (Weights.size() == 1 + SI->getNumCases());
}
for (unsigned I = 0, E = DeadCases.size(); I != E; ++I) {
SwitchInst::CaseIt Case = SI->findCaseValue(DeadCases[I]);
assert(Case != SI->case_default() &&
"Case was not found. Probably mistake in DeadCases forming.");
if (HasWeight) {
std::swap(Weights[Case.getCaseIndex()+1], Weights.back());
Weights.pop_back();
}
Case.getCaseSuccessor()->removePredecessor(SI->getParent());
SI->removeCase(Case);
}
if (HasWeight && Weights.size() >= 2) {
SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end());
SI->setMetadata(LLVMContext::MD_prof,
MDBuilder(SI->getParent()->getContext()).
createBranchWeights(MDWeights));
}
return !DeadCases.empty();
}
static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue,
BasicBlock *BB,
int *PhiIndex) {
if (BB->getFirstNonPHIOrDbg() != BB->getTerminator())
return nullptr; if (!BB->getSinglePredecessor())
return nullptr;
BranchInst *Branch = dyn_cast<BranchInst>(BB->getTerminator());
if (!Branch || !Branch->isUnconditional())
return nullptr;
BasicBlock *Succ = Branch->getSuccessor(0);
BasicBlock::iterator I = Succ->begin();
while (PHINode *PHI = dyn_cast<PHINode>(I++)) {
int Idx = PHI->getBasicBlockIndex(BB);
assert(Idx >= 0 && "PHI has no entry for predecessor?");
Value *InValue = PHI->getIncomingValue(Idx);
if (InValue != CaseValue) continue;
*PhiIndex = Idx;
return PHI;
}
return nullptr;
}
static bool ForwardSwitchConditionToPHI(SwitchInst *SI) {
typedef DenseMap<PHINode*, SmallVector<int,4> > ForwardingNodesMap;
ForwardingNodesMap ForwardingNodes;
for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) {
ConstantInt *CaseValue = I.getCaseValue();
BasicBlock *CaseDest = I.getCaseSuccessor();
int PhiIndex;
PHINode *PHI = FindPHIForConditionForwarding(CaseValue, CaseDest,
&PhiIndex);
if (!PHI) continue;
ForwardingNodes[PHI].push_back(PhiIndex);
}
bool Changed = false;
for (ForwardingNodesMap::iterator I = ForwardingNodes.begin(),
E = ForwardingNodes.end(); I != E; ++I) {
PHINode *Phi = I->first;
SmallVectorImpl<int> &Indexes = I->second;
if (Indexes.size() < 2) continue;
for (size_t I = 0, E = Indexes.size(); I != E; ++I)
Phi->setIncomingValue(Indexes[I], SI->getCondition());
Changed = true;
}
return Changed;
}
static bool ValidLookupTableConstant(Constant *C) {
if (C->isThreadDependent())
return false;
if (C->isDLLImportDependent())
return false;
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
return CE->isGEPWithNoNotionalOverIndexing();
return isa<ConstantFP>(C) ||
isa<ConstantInt>(C) ||
isa<ConstantPointerNull>(C) ||
isa<GlobalValue>(C) ||
isa<UndefValue>(C);
}
static Constant *LookupConstant(Value *V,
const SmallDenseMap<Value*, Constant*>& ConstantPool) {
if (Constant *C = dyn_cast<Constant>(V))
return C;
return ConstantPool.lookup(V);
}
static Constant *
ConstantFold(Instruction *I, const DataLayout &DL,
const SmallDenseMap<Value *, Constant *> &ConstantPool) {
if (SelectInst *Select = dyn_cast<SelectInst>(I)) {
Constant *A = LookupConstant(Select->getCondition(), ConstantPool);
if (!A)
return nullptr;
if (A->isAllOnesValue())
return LookupConstant(Select->getTrueValue(), ConstantPool);
if (A->isNullValue())
return LookupConstant(Select->getFalseValue(), ConstantPool);
return nullptr;
}
SmallVector<Constant *, 4> COps;
for (unsigned N = 0, E = I->getNumOperands(); N != E; ++N) {
if (Constant *A = LookupConstant(I->getOperand(N), ConstantPool))
COps.push_back(A);
else
return nullptr;
}
if (CmpInst *Cmp = dyn_cast<CmpInst>(I)) {
return ConstantFoldCompareInstOperands(Cmp->getPredicate(), COps[0],
COps[1], DL);
}
return ConstantFoldInstOperands(I->getOpcode(), I->getType(), COps, DL);
}
static bool
GetCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest,
BasicBlock **CommonDest,
SmallVectorImpl<std::pair<PHINode *, Constant *>> &Res,
const DataLayout &DL) {
BasicBlock *Pred = SI->getParent();
SmallDenseMap<Value*, Constant*> ConstantPool;
ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
for (BasicBlock::iterator I = CaseDest->begin(), E = CaseDest->end(); I != E;
++I) {
if (TerminatorInst *T = dyn_cast<TerminatorInst>(I)) {
if (T->getNumSuccessors() != 1)
return false;
Pred = CaseDest;
CaseDest = T->getSuccessor(0);
} else if (isa<DbgInfoIntrinsic>(I)) {
continue;
} else if (Constant *C = ConstantFold(I, DL, ConstantPool)) {
for (auto &Use : I->uses()) {
User *User = Use.getUser();
if (Instruction *I = dyn_cast<Instruction>(User))
if (I->getParent() == CaseDest)
continue;
if (PHINode *Phi = dyn_cast<PHINode>(User))
if (Phi->getIncomingBlock(Use) == CaseDest)
continue;
return false;
}
ConstantPool.insert(std::make_pair(I, C));
} else {
break;
}
}
if (!*CommonDest)
*CommonDest = CaseDest;
if (CaseDest != *CommonDest)
return false;
BasicBlock::iterator I = (*CommonDest)->begin();
while (PHINode *PHI = dyn_cast<PHINode>(I++)) {
int Idx = PHI->getBasicBlockIndex(Pred);
if (Idx == -1)
continue;
Constant *ConstVal = LookupConstant(PHI->getIncomingValue(Idx),
ConstantPool);
if (!ConstVal)
return false;
if (!ValidLookupTableConstant(ConstVal))
return false;
Res.push_back(std::make_pair(PHI, ConstVal));
}
return Res.size() > 0;
}
static void MapCaseToResult(ConstantInt *CaseVal,
SwitchCaseResultVectorTy &UniqueResults,
Constant *Result) {
for (auto &I : UniqueResults) {
if (I.first == Result) {
I.second.push_back(CaseVal);
return;
}
}
UniqueResults.push_back(std::make_pair(Result,
SmallVector<ConstantInt*, 4>(1, CaseVal)));
}
static bool InitializeUniqueCases(SwitchInst *SI, PHINode *&PHI,
BasicBlock *&CommonDest,
SwitchCaseResultVectorTy &UniqueResults,
Constant *&DefaultResult,
const DataLayout &DL) {
for (auto &I : SI->cases()) {
ConstantInt *CaseVal = I.getCaseValue();
SwitchCaseResultsTy Results;
if (!GetCaseResults(SI, CaseVal, I.getCaseSuccessor(), &CommonDest, Results,
DL))
return false;
if (Results.size() > 1)
return false;
MapCaseToResult(CaseVal, UniqueResults, Results.begin()->second);
if (!PHI)
PHI = Results[0].first;
else if (PHI != Results[0].first)
return false;
}
SmallVector<std::pair<PHINode *, Constant *>, 1> DefaultResults;
BasicBlock *DefaultDest = SI->getDefaultDest();
GetCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
DL);
DefaultResult =
DefaultResults.size() == 1 ? DefaultResults.begin()->second : nullptr;
if ((!DefaultResult &&
!isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg())))
return false;
return true;
}
static Value *
ConvertTwoCaseSwitch(const SwitchCaseResultVectorTy &ResultVector,
Constant *DefaultResult, Value *Condition,
IRBuilder<> &Builder) {
assert(ResultVector.size() == 2 &&
"We should have exactly two unique results at this point");
if (ResultVector[0].second.size() == 1 &&
ResultVector[1].second.size() == 1) {
ConstantInt *const FirstCase = ResultVector[0].second[0];
ConstantInt *const SecondCase = ResultVector[1].second[0];
bool DefaultCanTrigger = DefaultResult;
Value *SelectValue = ResultVector[1].first;
if (DefaultCanTrigger) {
Value *const ValueCompare =
Builder.CreateICmpEQ(Condition, SecondCase, "switch.selectcmp");
SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
DefaultResult, "switch.select");
}
Value *const ValueCompare =
Builder.CreateICmpEQ(Condition, FirstCase, "switch.selectcmp");
return Builder.CreateSelect(ValueCompare, ResultVector[0].first, SelectValue,
"switch.select");
}
return nullptr;
}
static void RemoveSwitchAfterSelectConversion(SwitchInst *SI, PHINode *PHI,
Value *SelectValue,
IRBuilder<> &Builder) {
BasicBlock *SelectBB = SI->getParent();
while (PHI->getBasicBlockIndex(SelectBB) >= 0)
PHI->removeIncomingValue(SelectBB);
PHI->addIncoming(SelectValue, SelectBB);
Builder.CreateBr(PHI->getParent());
for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
BasicBlock *Succ = SI->getSuccessor(i);
if (Succ == PHI->getParent())
continue;
Succ->removePredecessor(SelectBB);
}
SI->eraseFromParent();
}
static bool SwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder,
AssumptionCache *AC, const DataLayout &DL) {
Value *const Cond = SI->getCondition();
PHINode *PHI = nullptr;
BasicBlock *CommonDest = nullptr;
Constant *DefaultResult;
SwitchCaseResultVectorTy UniqueResults;
if (!InitializeUniqueCases(SI, PHI, CommonDest, UniqueResults, DefaultResult,
DL))
return false;
if (UniqueResults.size() != 2)
return false;
assert(PHI != nullptr && "PHI for value select not found");
Builder.SetInsertPoint(SI);
Value *SelectValue = ConvertTwoCaseSwitch(
UniqueResults,
DefaultResult, Cond, Builder);
if (SelectValue) {
RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, Builder);
return true;
}
return false;
}
namespace {
class SwitchLookupTable {
public:
SwitchLookupTable(
Module &M, uint64_t TableSize, ConstantInt *Offset,
const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
Constant *DefaultValue, const DataLayout &DL);
Value *BuildLookup(Value *Index, IRBuilder<> &Builder);
static bool WouldFitInRegister(const DataLayout &DL, uint64_t TableSize,
const Type *ElementType);
private:
enum {
SingleValueKind,
LinearMapKind,
BitMapKind,
ArrayKind
} Kind;
Constant *SingleValue;
ConstantInt *BitMap;
IntegerType *BitMapElementTy;
ConstantInt *LinearOffset;
ConstantInt *LinearMultiplier;
GlobalVariable *Array;
};
}
SwitchLookupTable::SwitchLookupTable(
Module &M, uint64_t TableSize, ConstantInt *Offset,
const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
Constant *DefaultValue, const DataLayout &DL)
: SingleValue(nullptr), BitMap(nullptr), BitMapElementTy(nullptr),
LinearOffset(nullptr), LinearMultiplier(nullptr), Array(nullptr) {
assert(Values.size() && "Can't build lookup table without values!");
assert(TableSize >= Values.size() && "Can't fit values in table!");
SingleValue = Values.begin()->second;
Type *ValueType = Values.begin()->second->getType();
SmallVector<Constant*, 64> TableContents(TableSize);
for (size_t I = 0, E = Values.size(); I != E; ++I) {
ConstantInt *CaseVal = Values[I].first;
Constant *CaseRes = Values[I].second;
assert(CaseRes->getType() == ValueType);
uint64_t Idx = (CaseVal->getValue() - Offset->getValue())
.getLimitedValue();
TableContents[Idx] = CaseRes;
if (CaseRes != SingleValue)
SingleValue = nullptr;
}
if (Values.size() < TableSize) {
assert(DefaultValue &&
"Need a default value to fill the lookup table holes.");
assert(DefaultValue->getType() == ValueType);
for (uint64_t I = 0; I < TableSize; ++I) {
if (!TableContents[I])
TableContents[I] = DefaultValue;
}
if (DefaultValue != SingleValue)
SingleValue = nullptr;
}
if (SingleValue) {
Kind = SingleValueKind;
return;
}
if (isa<IntegerType>(ValueType)) {
bool LinearMappingPossible = true;
APInt PrevVal;
APInt DistToPrev;
assert(TableSize >= 2 && "Should be a SingleValue table.");
for (uint64_t I = 0; I < TableSize; ++I) {
ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[I]);
if (!ConstVal) {
LinearMappingPossible = false;
break;
}
APInt Val = ConstVal->getValue();
if (I != 0) {
APInt Dist = Val - PrevVal;
if (I == 1) {
DistToPrev = Dist;
} else if (Dist != DistToPrev) {
LinearMappingPossible = false;
break;
}
}
PrevVal = Val;
}
if (LinearMappingPossible) {
LinearOffset = cast<ConstantInt>(TableContents[0]);
LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
Kind = LinearMapKind;
++NumLinearMaps;
return;
}
}
if (WouldFitInRegister(DL, TableSize, ValueType)) {
IntegerType *IT = cast<IntegerType>(ValueType);
APInt TableInt(TableSize * IT->getBitWidth(), 0);
for (uint64_t I = TableSize; I > 0; --I) {
TableInt <<= IT->getBitWidth();
if (!isa<UndefValue>(TableContents[I - 1])) {
ConstantInt *Val = cast<ConstantInt>(TableContents[I - 1]);
TableInt |= Val->getValue().zext(TableInt.getBitWidth());
}
}
BitMap = ConstantInt::get(M.getContext(), TableInt);
BitMapElementTy = IT;
Kind = BitMapKind;
++NumBitMaps;
return;
}
ArrayType *ArrayTy = ArrayType::get(ValueType, TableSize);
Constant *Initializer = ConstantArray::get(ArrayTy, TableContents);
Array = new GlobalVariable(M, ArrayTy, true,
GlobalVariable::PrivateLinkage,
Initializer,
"switch.table");
Array->setUnnamedAddr(true);
Kind = ArrayKind;
}
Value *SwitchLookupTable::BuildLookup(Value *Index, IRBuilder<> &Builder) {
switch (Kind) {
case SingleValueKind:
return SingleValue;
case LinearMapKind: {
Value *Result = Builder.CreateIntCast(Index, LinearMultiplier->getType(),
false, "switch.idx.cast");
if (!LinearMultiplier->isOne())
Result = Builder.CreateMul(Result, LinearMultiplier, "switch.idx.mult");
if (!LinearOffset->isZero())
Result = Builder.CreateAdd(Result, LinearOffset, "switch.offset");
return Result;
}
case BitMapKind: {
IntegerType *MapTy = BitMap->getType();
Value *ShiftAmt = Builder.CreateZExtOrTrunc(Index, MapTy, "switch.cast");
ShiftAmt = Builder.CreateMul(ShiftAmt,
ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
"switch.shiftamt");
Value *DownShifted = Builder.CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
return Builder.CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
}
case ArrayKind: {
IntegerType *IT = cast<IntegerType>(Index->getType());
uint64_t TableSize = Array->getInitializer()->getType()
->getArrayNumElements();
if (TableSize > (1ULL << (IT->getBitWidth() - 1)))
Index = Builder.CreateZExt(Index,
IntegerType::get(IT->getContext(),
IT->getBitWidth() + 1),
"switch.tableidx.zext");
Value *GEPIndices[] = { Builder.getInt32(0), Index };
Value *GEP = Builder.CreateInBoundsGEP(Array, GEPIndices,
"switch.gep");
return Builder.CreateLoad(GEP, "switch.load");
}
}
llvm_unreachable("Unknown lookup table kind!");
}
bool SwitchLookupTable::WouldFitInRegister(const DataLayout &DL,
uint64_t TableSize,
const Type *ElementType) {
const IntegerType *IT = dyn_cast<IntegerType>(ElementType);
if (!IT)
return false;
if (TableSize >= UINT_MAX/IT->getBitWidth())
return false;
return DL.fitsInLegalInteger(TableSize * IT->getBitWidth());
}
static bool
ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize,
const TargetTransformInfo &TTI, const DataLayout &DL,
const SmallDenseMap<PHINode *, Type *> &ResultTypes) {
if (SI->getNumCases() > TableSize || TableSize >= UINT64_MAX / 10)
return false;
bool AllTablesFitInRegister = true;
bool HasIllegalType = false;
for (const auto &I : ResultTypes) {
Type *Ty = I.second;
HasIllegalType = HasIllegalType || !TTI.isTypeLegal(Ty);
AllTablesFitInRegister = AllTablesFitInRegister &&
SwitchLookupTable::WouldFitInRegister(DL, TableSize, Ty);
if (HasIllegalType && !AllTablesFitInRegister)
break;
}
if (AllTablesFitInRegister)
return true;
if (HasIllegalType)
return false;
return SI->getNumCases() * 10 >= TableSize * 4;
}
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock,
BranchInst *RangeCheckBranch, Constant *DefaultValue,
const SmallVectorImpl<std::pair<ConstantInt*, Constant*> >& Values) {
ICmpInst *CmpInst = dyn_cast<ICmpInst>(PhiUser);
if (!CmpInst)
return;
if (CmpInst->getParent() != PhiBlock)
return;
Constant *CmpOp1 = dyn_cast<Constant>(CmpInst->getOperand(1));
if (!CmpOp1)
return;
Value *RangeCmp = RangeCheckBranch->getCondition();
Constant *TrueConst = ConstantInt::getTrue(RangeCmp->getType());
Constant *FalseConst = ConstantInt::getFalse(RangeCmp->getType());
Constant *DefaultConst = ConstantExpr::getICmp(CmpInst->getPredicate(),
DefaultValue, CmpOp1, true);
if (DefaultConst != TrueConst && DefaultConst != FalseConst)
return;
for (auto ValuePair : Values) {
Constant *CaseConst = ConstantExpr::getICmp(CmpInst->getPredicate(),
ValuePair.second, CmpOp1, true);
if (!CaseConst || CaseConst == DefaultConst)
return;
assert((CaseConst == TrueConst || CaseConst == FalseConst) &&
"Expect true or false as compare result.");
}
BasicBlock *BranchBlock = RangeCheckBranch->getParent();
for (auto PI = pred_begin(PhiBlock), E = pred_end(PhiBlock); PI != E; ++PI) {
BasicBlock *Pred = *PI;
if (Pred != BranchBlock && Pred->getUniquePredecessor() != BranchBlock)
return;
}
if (DefaultConst == FalseConst) {
CmpInst->replaceAllUsesWith(RangeCmp);
++NumTableCmpReuses;
} else {
Value *InvertedTableCmp = BinaryOperator::CreateXor(RangeCmp,
ConstantInt::get(RangeCmp->getType(), 1), "inverted.cmp",
RangeCheckBranch);
CmpInst->replaceAllUsesWith(InvertedTableCmp);
++NumTableCmpReuses;
}
}
static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
const DataLayout &DL,
const TargetTransformInfo &TTI) {
assert(SI->getNumCases() > 1 && "Degenerate switch?");
if (!TTI.shouldBuildLookupTables())
return false;
if (SI->getNumCases() < 3)
return false;
assert(SI->case_begin() != SI->case_end());
SwitchInst::CaseIt CI = SI->case_begin();
ConstantInt *MinCaseVal = CI.getCaseValue();
ConstantInt *MaxCaseVal = CI.getCaseValue();
BasicBlock *CommonDest = nullptr;
typedef SmallVector<std::pair<ConstantInt*, Constant*>, 4> ResultListTy;
SmallDenseMap<PHINode*, ResultListTy> ResultLists;
SmallDenseMap<PHINode*, Constant*> DefaultResults;
SmallDenseMap<PHINode*, Type*> ResultTypes;
SmallVector<PHINode*, 4> PHIs;
for (SwitchInst::CaseIt E = SI->case_end(); CI != E; ++CI) {
ConstantInt *CaseVal = CI.getCaseValue();
if (CaseVal->getValue().slt(MinCaseVal->getValue()))
MinCaseVal = CaseVal;
if (CaseVal->getValue().sgt(MaxCaseVal->getValue()))
MaxCaseVal = CaseVal;
typedef SmallVector<std::pair<PHINode*, Constant*>, 4> ResultsTy;
ResultsTy Results;
if (!GetCaseResults(SI, CaseVal, CI.getCaseSuccessor(), &CommonDest,
Results, DL))
return false;
for (const auto &I : Results) {
PHINode *PHI = I.first;
Constant *Value = I.second;
if (!ResultLists.count(PHI))
PHIs.push_back(PHI);
ResultLists[PHI].push_back(std::make_pair(CaseVal, Value));
}
}
for (PHINode *PHI : PHIs) {
ResultTypes[PHI] = ResultLists[PHI][0].second->getType();
}
uint64_t NumResults = ResultLists[PHIs[0]].size();
APInt RangeSpread = MaxCaseVal->getValue() - MinCaseVal->getValue();
uint64_t TableSize = RangeSpread.getLimitedValue() + 1;
bool TableHasHoles = (NumResults < TableSize);
SmallVector<std::pair<PHINode*, Constant*>, 4> DefaultResultsList;
bool HasDefaultResults = GetCaseResults(SI, nullptr, SI->getDefaultDest(),
&CommonDest, DefaultResultsList, DL);
bool NeedMask = (TableHasHoles && !HasDefaultResults);
if (NeedMask) {
if (SI->getNumCases() < 4) return false;
if (!DL.fitsInLegalInteger(TableSize))
return false;
}
for (const auto &I : DefaultResultsList) {
PHINode *PHI = I.first;
Constant *Result = I.second;
DefaultResults[PHI] = Result;
}
if (!ShouldBuildLookupTable(SI, TableSize, TTI, DL, ResultTypes))
return false;
Module &Mod = *CommonDest->getParent()->getParent();
BasicBlock *LookupBB = BasicBlock::Create(Mod.getContext(),
"switch.lookup",
CommonDest->getParent(),
CommonDest);
Builder.SetInsertPoint(SI);
Value *TableIndex = Builder.CreateSub(SI->getCondition(), MinCaseVal,
"switch.tableidx");
unsigned CaseSize = MinCaseVal->getType()->getPrimitiveSizeInBits();
uint64_t MaxTableSize = CaseSize > 63 ? UINT64_MAX : 1ULL << CaseSize;
assert(MaxTableSize >= TableSize &&
"It is impossible for a switch to have more entries than the max "
"representable value of its input integer type's size.");
const bool DefaultIsReachable =
!isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
BranchInst *RangeCheckBranch = nullptr;
if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
Builder.CreateBr(LookupBB);
} else {
Value *Cmp = Builder.CreateICmpULT(TableIndex, ConstantInt::get(
MinCaseVal->getType(), TableSize));
RangeCheckBranch = Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
}
Builder.SetInsertPoint(LookupBB);
if (NeedMask) {
BasicBlock *MaskBB = LookupBB;
MaskBB->setName("switch.hole_check");
LookupBB = BasicBlock::Create(Mod.getContext(),
"switch.lookup",
CommonDest->getParent(),
CommonDest);
uint64_t TableSizePowOf2 = NextPowerOf2(std::max(7ULL, TableSize - 1ULL));
APInt MaskInt(TableSizePowOf2, 0);
APInt One(TableSizePowOf2, 1);
const ResultListTy &ResultList = ResultLists[PHIs[0]];
for (size_t I = 0, E = ResultList.size(); I != E; ++I) {
uint64_t Idx = (ResultList[I].first->getValue() -
MinCaseVal->getValue()).getLimitedValue();
MaskInt |= One << Idx;
}
ConstantInt *TableMask = ConstantInt::get(Mod.getContext(), MaskInt);
IntegerType *MapTy = TableMask->getType();
Value *MaskIndex = Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
Value *LoBit = Builder.CreateTrunc(Shifted,
Type::getInt1Ty(Mod.getContext()),
"switch.lobit");
Builder.CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
Builder.SetInsertPoint(LookupBB);
AddPredecessorToBlock(SI->getDefaultDest(), MaskBB, SI->getParent());
}
if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
SI->getDefaultDest()->removePredecessor(SI->getParent(),
true);
}
bool ReturnedEarly = false;
for (size_t I = 0, E = PHIs.size(); I != E; ++I) {
PHINode *PHI = PHIs[I];
const ResultListTy &ResultList = ResultLists[PHI];
Constant *DV = NeedMask ? ResultLists[PHI][0].second : DefaultResults[PHI];
SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultList, DV, DL);
Value *Result = Table.BuildLookup(TableIndex, Builder);
if (PHI->hasOneUse() && isa<ReturnInst>(*PHI->user_begin()) &&
PHI->user_back() == CommonDest->getFirstNonPHIOrDbg()) {
Builder.CreateRet(Result);
ReturnedEarly = true;
break;
}
if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
BasicBlock *PhiBlock = PHI->getParent();
for (auto *User : PHI->users()) {
reuseTableCompare(User, PhiBlock, RangeCheckBranch, DV, ResultList);
}
}
PHI->addIncoming(Result, LookupBB);
}
if (!ReturnedEarly)
Builder.CreateBr(CommonDest);
for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
BasicBlock *Succ = SI->getSuccessor(i);
if (Succ == SI->getDefaultDest())
continue;
Succ->removePredecessor(SI->getParent());
}
SI->eraseFromParent();
++NumLookupTables;
if (NeedMask)
++NumLookupTablesHoles;
return true;
}
bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
BasicBlock *BB = SI->getParent();
if (isValueEqualityComparison(SI)) {
if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
Value *Cond = SI->getCondition();
if (SelectInst *Select = dyn_cast<SelectInst>(Cond))
if (SimplifySwitchOnSelect(SI, Select))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
BasicBlock::iterator BBI = BB->begin();
while (isa<DbgInfoIntrinsic>(BBI))
++BBI;
if (SI == &*BBI)
if (FoldValueComparisonIntoPredecessors(SI, Builder))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
}
if (TurnSwitchRangeIntoICmp(SI, Builder))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
if (EliminateDeadSwitchCases(SI, AC, DL))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
if (SwitchToSelect(SI, Builder, AC, DL))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
if (ForwardSwitchConditionToPHI(SI))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
if (SwitchToLookupTable(SI, Builder, DL, TTI))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
return false;
}
bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) {
BasicBlock *BB = IBI->getParent();
bool Changed = false;
SmallPtrSet<Value *, 8> Succs;
for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
BasicBlock *Dest = IBI->getDestination(i);
if (!Dest->hasAddressTaken() || !Succs.insert(Dest).second) {
Dest->removePredecessor(BB);
IBI->removeDestination(i);
--i; --e;
Changed = true;
}
}
if (IBI->getNumDestinations() == 0) {
new UnreachableInst(IBI->getContext(), IBI);
EraseTerminatorInstAndDCECond(IBI);
return true;
}
if (IBI->getNumDestinations() == 1) {
BranchInst::Create(IBI->getDestination(0), IBI);
EraseTerminatorInstAndDCECond(IBI);
return true;
}
if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) {
if (SimplifyIndirectBrOnSelect(IBI, SI))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
}
return Changed;
}
bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder){
BasicBlock *BB = BI->getParent();
if (SinkCommon && SinkThenElseCodeToEnd(BI))
return true;
BasicBlock::iterator I = BB->getFirstNonPHIOrDbg();
if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() &&
TryToSimplifyUncondBranchFromEmptyBlock(BB))
return true;
if (ICmpInst *ICI = dyn_cast<ICmpInst>(I))
if (ICI->isEquality() && isa<ConstantInt>(ICI->getOperand(1))) {
for (++I; isa<DbgInfoIntrinsic>(I); ++I)
;
if (I->isTerminator() &&
TryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, DL, TTI,
BonusInstThreshold, AC))
return true;
}
if (FoldBranchToCommonDest(BI, BonusInstThreshold))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
return false;
}
bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) {
BasicBlock *BB = BI->getParent();
if (isValueEqualityComparison(BI)) {
if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
BasicBlock::iterator I = BB->begin();
while (isa<DbgInfoIntrinsic>(I))
++I;
if (&*I == BI) {
if (FoldValueComparisonIntoPredecessors(BI, Builder))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
} else if (&*I == cast<Instruction>(BI->getCondition())){
++I;
while (isa<DbgInfoIntrinsic>(I))
++I;
if (&*I == BI && FoldValueComparisonIntoPredecessors(BI, Builder))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
}
}
if (SimplifyBranchOnICmpChain(BI, Builder, DL))
return true;
if (FoldBranchToCommonDest(BI, BonusInstThreshold))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
if (BI->getSuccessor(0)->getSinglePredecessor()) {
if (BI->getSuccessor(1)->getSinglePredecessor()) {
if (HoistThenElseCodeToIf(BI))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
} else {
TerminatorInst *Succ0TI = BI->getSuccessor(0)->getTerminator();
if (Succ0TI->getNumSuccessors() == 1 &&
Succ0TI->getSuccessor(0) == BI->getSuccessor(1))
if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0)))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
}
} else if (BI->getSuccessor(1)->getSinglePredecessor()) {
TerminatorInst *Succ1TI = BI->getSuccessor(1)->getTerminator();
if (Succ1TI->getNumSuccessors() == 1 &&
Succ1TI->getSuccessor(0) == BI->getSuccessor(0))
if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1)))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
}
if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition()))
if (PN->getParent() == BI->getParent())
if (FoldCondBranchOnPHI(BI, DL))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
if (PBI != BI && PBI->isConditional())
if (SimplifyCondBranchToCondBranch(PBI, BI))
return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
return false;
}
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) {
Constant *C = dyn_cast<Constant>(V);
if (!C)
return false;
if (I->use_empty())
return false;
if (C->isNullValue()) {
User *Use = *I->user_begin();
for (BasicBlock::iterator i = ++BasicBlock::iterator(I); &*i != Use; ++i)
if (i == I->getParent()->end() || i->mayHaveSideEffects())
return false;
if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Use))
if (GEP->getPointerOperand() == I)
return passingValueIsAlwaysUndefined(V, GEP);
if (BitCastInst *BC = dyn_cast<BitCastInst>(Use))
return passingValueIsAlwaysUndefined(V, BC);
if (LoadInst *LI = dyn_cast<LoadInst>(Use))
if (!LI->isVolatile())
return LI->getPointerAddressSpace() == 0;
if (StoreInst *SI = dyn_cast<StoreInst>(Use))
if (!SI->isVolatile())
return SI->getPointerAddressSpace() == 0 && SI->getPointerOperand() == I;
}
return false;
}
static bool removeUndefIntroducingPredecessor(BasicBlock *BB) {
for (BasicBlock::iterator i = BB->begin();
PHINode *PHI = dyn_cast<PHINode>(i); ++i)
for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
if (passingValueIsAlwaysUndefined(PHI->getIncomingValue(i), PHI)) {
TerminatorInst *T = PHI->getIncomingBlock(i)->getTerminator();
IRBuilder<> Builder(T);
if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
BB->removePredecessor(PHI->getIncomingBlock(i));
if (BI->isUnconditional())
Builder.CreateUnreachable();
else
Builder.CreateBr(BI->getSuccessor(0) == BB ? BI->getSuccessor(1) :
BI->getSuccessor(0));
BI->eraseFromParent();
return true;
}
}
return false;
}
bool SimplifyCFGOpt::run(BasicBlock *BB) {
bool Changed = false;
assert(BB && BB->getParent() && "Block not embedded in function!");
assert(BB->getTerminator() && "Degenerate basic block encountered!");
if ((pred_empty(BB) &&
BB != &BB->getParent()->getEntryBlock()) ||
BB->getSinglePredecessor() == BB) {
DEBUG(dbgs() << "Removing BB: \n" << *BB);
DeleteDeadBlock(BB);
return true;
}
Changed |= ConstantFoldTerminator(BB, true);
Changed |= EliminateDuplicatePHINodes(BB);
Changed |= removeUndefIntroducingPredecessor(BB);
if (MergeBlockIntoPredecessor(BB))
return true;
IRBuilder<> Builder(BB);
if (PHINode *PN = dyn_cast<PHINode>(BB->begin()))
if (PN->getNumIncomingValues() == 2)
Changed |= FoldTwoEntryPHINode(PN, DL);
Builder.SetInsertPoint(BB->getTerminator());
if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
if (BI->isUnconditional()) {
if (SimplifyUncondBranch(BI, Builder)) return true;
} else {
if (SimplifyCondBranch(BI, Builder)) return true;
}
} else if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
if (SimplifyReturn(RI, Builder)) return true;
} else if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator())) {
if (SimplifyResume(RI, Builder)) return true;
} else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
if (SimplifySwitch(SI, Builder)) return true;
} else if (UnreachableInst *UI =
dyn_cast<UnreachableInst>(BB->getTerminator())) {
if (SimplifyUnreachable(UI)) return true;
} else if (IndirectBrInst *IBI =
dyn_cast<IndirectBrInst>(BB->getTerminator())) {
if (SimplifyIndirectBr(IBI)) return true;
}
return Changed;
}
bool llvm::SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
unsigned BonusInstThreshold, AssumptionCache *AC) {
return SimplifyCFGOpt(TTI, BB->getModule()->getDataLayout(),
BonusInstThreshold, AC).run(BB);
}