#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LibCallSemantics.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DIBuilder.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
#define DEBUG_TYPE "local"
STATISTIC(NumRemoved, "Number of unreachable basic blocks removed");
bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
const TargetLibraryInfo *TLI) {
TerminatorInst *T = BB->getTerminator();
IRBuilder<> Builder(T);
if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
if (BI->isUnconditional()) return false; BasicBlock *Dest1 = BI->getSuccessor(0);
BasicBlock *Dest2 = BI->getSuccessor(1);
if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1;
OldDest->removePredecessor(BB);
Builder.CreateBr(Destination);
BI->eraseFromParent();
return true;
}
if (Dest2 == Dest1) {
assert(BI->getParent() && "Terminator not inserted in block!");
Dest1->removePredecessor(BI->getParent());
Builder.CreateBr(Dest1);
Value *Cond = BI->getCondition();
BI->eraseFromParent();
if (DeleteDeadConditions)
RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
return true;
}
return false;
}
if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition());
BasicBlock *DefaultDest = SI->getDefaultDest();
BasicBlock *TheOnlyDest = DefaultDest;
if (isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()) &&
SI->getNumCases() > 0) {
TheOnlyDest = SI->case_begin().getCaseSuccessor();
}
for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
i != e; ++i) {
if (i.getCaseValue() == CI) {
TheOnlyDest = i.getCaseSuccessor();
break;
}
if (i.getCaseSuccessor() == DefaultDest) {
MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
unsigned NCases = SI->getNumCases();
if (NCases > 1 && MD && MD->getNumOperands() == 2 + NCases) {
SmallVector<uint32_t, 8> Weights;
for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e;
++MD_i) {
ConstantInt *CI =
mdconst::dyn_extract<ConstantInt>(MD->getOperand(MD_i));
assert(CI);
Weights.push_back(CI->getValue().getZExtValue());
}
unsigned idx = i.getCaseIndex();
Weights[0] += Weights[idx+1];
std::swap(Weights[idx+1], Weights.back());
Weights.pop_back();
SI->setMetadata(LLVMContext::MD_prof,
MDBuilder(BB->getContext()).
createBranchWeights(Weights));
}
DefaultDest->removePredecessor(SI->getParent());
SI->removeCase(i);
--i; --e;
continue;
}
if (i.getCaseSuccessor() != TheOnlyDest) TheOnlyDest = nullptr;
}
if (CI && !TheOnlyDest) {
TheOnlyDest = SI->getDefaultDest();
}
if (TheOnlyDest) {
Builder.CreateBr(TheOnlyDest);
BasicBlock *BB = SI->getParent();
for (BasicBlock *Succ : SI->successors()) {
if (Succ == TheOnlyDest)
TheOnlyDest = nullptr; else
Succ->removePredecessor(BB);
}
Value *Cond = SI->getCondition();
SI->eraseFromParent();
if (DeleteDeadConditions)
RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
return true;
}
if (SI->getNumCases() == 1) {
SwitchInst::CaseIt FirstCase = SI->case_begin();
Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
FirstCase.getCaseValue(), "cond");
BranchInst *NewBr = Builder.CreateCondBr(Cond,
FirstCase.getCaseSuccessor(),
SI->getDefaultDest());
MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
if (MD && MD->getNumOperands() == 3) {
ConstantInt *SICase =
mdconst::dyn_extract<ConstantInt>(MD->getOperand(2));
ConstantInt *SIDef =
mdconst::dyn_extract<ConstantInt>(MD->getOperand(1));
assert(SICase && SIDef);
NewBr->setMetadata(LLVMContext::MD_prof,
MDBuilder(BB->getContext()).
createBranchWeights(SICase->getValue().getZExtValue(),
SIDef->getValue().getZExtValue()));
}
MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit);
if (MakeImplicitMD)
NewBr->setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD);
SI->eraseFromParent();
return true;
}
return false;
}
if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) {
if (BlockAddress *BA =
dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
BasicBlock *TheOnlyDest = BA->getBasicBlock();
Builder.CreateBr(TheOnlyDest);
for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
if (IBI->getDestination(i) == TheOnlyDest)
TheOnlyDest = nullptr;
else
IBI->getDestination(i)->removePredecessor(IBI->getParent());
}
Value *Address = IBI->getAddress();
IBI->eraseFromParent();
if (DeleteDeadConditions)
RecursivelyDeleteTriviallyDeadInstructions(Address, TLI);
if (TheOnlyDest) {
BB->getTerminator()->eraseFromParent();
new UnreachableInst(BB->getContext(), BB);
}
return true;
}
}
return false;
}
bool llvm::isInstructionTriviallyDead(Instruction *I,
const TargetLibraryInfo *TLI) {
if (!I->use_empty() || isa<TerminatorInst>(I)) return false;
if (I->isEHPad())
return false;
if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) {
if (DDI->getAddress())
return false;
return true;
}
if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) {
if (DVI->getValue())
return false;
return true;
}
if (!I->mayHaveSideEffects()) return true;
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
if (II->getIntrinsicID() == Intrinsic::stacksave)
return true;
if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
II->getIntrinsicID() == Intrinsic::lifetime_end)
return isa<UndefValue>(II->getArgOperand(1));
if (II->getIntrinsicID() == Intrinsic::assume) {
if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0)))
return !Cond->isZero();
return false;
}
}
if (isAllocLikeFn(I, TLI)) return true;
if (CallInst *CI = isFreeCall(I, TLI))
if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0)))
return C->isNullValue() || isa<UndefValue>(C);
return false;
}
bool
llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V,
const TargetLibraryInfo *TLI) {
Instruction *I = dyn_cast<Instruction>(V);
if (!I || !I->use_empty() || !isInstructionTriviallyDead(I, TLI))
return false;
SmallVector<Instruction*, 16> DeadInsts;
DeadInsts.push_back(I);
do {
I = DeadInsts.pop_back_val();
for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
Value *OpV = I->getOperand(i);
I->setOperand(i, nullptr);
if (!OpV->use_empty()) continue;
if (Instruction *OpI = dyn_cast<Instruction>(OpV))
if (isInstructionTriviallyDead(OpI, TLI))
DeadInsts.push_back(OpI);
}
I->eraseFromParent();
} while (!DeadInsts.empty());
return true;
}
static bool areAllUsesEqual(Instruction *I) {
Value::user_iterator UI = I->user_begin();
Value::user_iterator UE = I->user_end();
if (UI == UE)
return true;
User *TheUse = *UI;
for (++UI; UI != UE; ++UI) {
if (*UI != TheUse)
return false;
}
return true;
}
bool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN,
const TargetLibraryInfo *TLI) {
SmallPtrSet<Instruction*, 4> Visited;
for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects();
I = cast<Instruction>(*I->user_begin())) {
if (I->use_empty())
return RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
if (!Visited.insert(I).second) {
I->replaceAllUsesWith(UndefValue::get(I->getType()));
(void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
return true;
}
}
return false;
}
static bool
simplifyAndDCEInstruction(Instruction *I,
SmallSetVector<Instruction *, 16> &WorkList,
const DataLayout &DL,
const TargetLibraryInfo *TLI) {
if (isInstructionTriviallyDead(I, TLI)) {
for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
Value *OpV = I->getOperand(i);
I->setOperand(i, nullptr);
if (!OpV->use_empty() || I == OpV)
continue;
if (Instruction *OpI = dyn_cast<Instruction>(OpV))
if (isInstructionTriviallyDead(OpI, TLI))
WorkList.insert(OpI);
}
I->eraseFromParent();
return true;
}
if (Value *SimpleV = SimplifyInstruction(I, DL)) {
for (User *U : I->users())
if (U != I)
WorkList.insert(cast<Instruction>(U));
I->replaceAllUsesWith(SimpleV);
I->eraseFromParent();
return true;
}
return false;
}
bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB,
const TargetLibraryInfo *TLI) {
bool MadeChange = false;
const DataLayout &DL = BB->getModule()->getDataLayout();
#ifndef NDEBUG
AssertingVH<Instruction> TerminatorVH(&BB->back());
#endif
SmallSetVector<Instruction *, 16> WorkList;
for (BasicBlock::iterator BI = BB->begin(), E = std::prev(BB->end()); BI != E;) {
assert(!BI->isTerminator());
Instruction *I = &*BI;
++BI;
if (!WorkList.count(I))
MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
}
while (!WorkList.empty()) {
Instruction *I = WorkList.pop_back_val();
MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
}
return MadeChange;
}
void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred) {
if (!isa<PHINode>(BB->begin()))
return;
BB->removePredecessor(Pred, true);
WeakVH PhiIt = &BB->front();
while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) {
PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt));
Value *OldPhiIt = PhiIt;
if (!recursivelySimplifyInstruction(PN))
continue;
if (PhiIt != OldPhiIt) PhiIt = &BB->front();
}
}
void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) {
while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
Value *NewVal = PN->getIncomingValue(0);
if (NewVal == PN) NewVal = UndefValue::get(PN->getType());
PN->replaceAllUsesWith(NewVal);
PN->eraseFromParent();
}
BasicBlock *PredBB = DestBB->getSinglePredecessor();
assert(PredBB && "Block doesn't have a single predecessor!");
if (DestBB->hasAddressTaken()) {
BlockAddress *BA = BlockAddress::get(DestBB);
Constant *Replacement =
ConstantInt::get(llvm::Type::getInt32Ty(BA->getContext()), 1);
BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
BA->getType()));
BA->destroyConstant();
}
PredBB->replaceAllUsesWith(DestBB);
PredBB->getTerminator()->eraseFromParent();
DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
if (PredBB == &DestBB->getParent()->getEntryBlock())
DestBB->moveAfter(PredBB);
if (DT) {
BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock();
DT->changeImmediateDominator(DestBB, PredBBIDom);
DT->eraseNode(PredBB);
}
PredBB->eraseFromParent();
}
static bool CanMergeValues(Value *First, Value *Second) {
return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);
}
static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into "
<< Succ->getName() << "\n");
if (Succ->getSinglePredecessor()) return true;
SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB));
for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
PHINode *PN = cast<PHINode>(I);
PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB));
if (BBPN && BBPN->getParent() == BB) {
for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
BasicBlock *IBB = PN->getIncomingBlock(PI);
if (BBPreds.count(IBB) &&
!CanMergeValues(BBPN->getIncomingValueForBlock(IBB),
PN->getIncomingValue(PI))) {
DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in "
<< Succ->getName() << " is conflicting with "
<< BBPN->getName() << " with regard to common predecessor "
<< IBB->getName() << "\n");
return false;
}
}
} else {
Value* Val = PN->getIncomingValueForBlock(BB);
for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
BasicBlock *IBB = PN->getIncomingBlock(PI);
if (BBPreds.count(IBB) &&
!CanMergeValues(Val, PN->getIncomingValue(PI))) {
DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in "
<< Succ->getName() << " is conflicting with regard to common "
<< "predecessor " << IBB->getName() << "\n");
return false;
}
}
}
}
return true;
}
typedef SmallVector<BasicBlock *, 16> PredBlockVector;
typedef DenseMap<BasicBlock *, Value *> IncomingValueMap;
static Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB,
IncomingValueMap &IncomingValues) {
if (!isa<UndefValue>(OldVal)) {
assert((!IncomingValues.count(BB) ||
IncomingValues.find(BB)->second == OldVal) &&
"Expected OldVal to match incoming value from BB!");
IncomingValues.insert(std::make_pair(BB, OldVal));
return OldVal;
}
IncomingValueMap::const_iterator It = IncomingValues.find(BB);
if (It != IncomingValues.end()) return It->second;
return OldVal;
}
static void gatherIncomingValuesToPhi(PHINode *PN,
IncomingValueMap &IncomingValues) {
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
BasicBlock *BB = PN->getIncomingBlock(i);
Value *V = PN->getIncomingValue(i);
if (!isa<UndefValue>(V))
IncomingValues.insert(std::make_pair(BB, V));
}
}
static void replaceUndefValuesInPhi(PHINode *PN,
const IncomingValueMap &IncomingValues) {
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
Value *V = PN->getIncomingValue(i);
if (!isa<UndefValue>(V)) continue;
BasicBlock *BB = PN->getIncomingBlock(i);
IncomingValueMap::const_iterator It = IncomingValues.find(BB);
if (It == IncomingValues.end()) continue;
PN->setIncomingValue(i, It->second);
}
}
static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB,
const PredBlockVector &BBPreds,
PHINode *PN) {
Value *OldVal = PN->removeIncomingValue(BB, false);
assert(OldVal && "No entry in PHI for Pred BB!");
IncomingValueMap IncomingValues;
gatherIncomingValuesToPhi(PN, IncomingValues);
if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
PHINode *OldValPN = cast<PHINode>(OldVal);
for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) {
BasicBlock *PredBB = OldValPN->getIncomingBlock(i);
Value *PredVal = OldValPN->getIncomingValue(i);
Value *Selected = selectIncomingValueForBlock(PredVal, PredBB,
IncomingValues);
PN->addIncoming(Selected, PredBB);
}
} else {
for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) {
BasicBlock *PredBB = BBPreds[i];
Value *Selected = selectIncomingValueForBlock(OldVal, PredBB,
IncomingValues);
PN->addIncoming(Selected, PredBB);
}
}
replaceUndefValuesInPhi(PN, IncomingValues);
}
bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) {
assert(BB != &BB->getParent()->getEntryBlock() &&
"TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
if (BB == Succ) return false;
if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false;
if (!Succ->getSinglePredecessor()) {
BasicBlock::iterator BBI = BB->begin();
while (isa<PHINode>(*BBI)) {
for (Use &U : BBI->uses()) {
if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) {
if (PN->getIncomingBlock(U) != BB)
return false;
} else {
return false;
}
}
++BBI;
}
}
DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
if (isa<PHINode>(Succ->begin())) {
const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB));
for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
PHINode *PN = cast<PHINode>(I);
redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN);
}
}
if (Succ->getSinglePredecessor()) {
BB->getTerminator()->eraseFromParent();
Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(),
BB->getInstList());
} else {
while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
assert(PN->use_empty() && "There shouldn't be any uses here!");
PN->eraseFromParent();
}
}
BB->replaceAllUsesWith(Succ);
if (!Succ->hasName()) Succ->takeName(BB);
BB->eraseFromParent(); return true;
}
bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
struct PHIDenseMapInfo {
static PHINode *getEmptyKey() {
return DenseMapInfo<PHINode *>::getEmptyKey();
}
static PHINode *getTombstoneKey() {
return DenseMapInfo<PHINode *>::getTombstoneKey();
}
static unsigned getHashValue(PHINode *PN) {
return static_cast<unsigned>(hash_combine(
hash_combine_range(PN->value_op_begin(), PN->value_op_end()),
hash_combine_range(PN->block_begin(), PN->block_end())));
}
static bool isEqual(PHINode *LHS, PHINode *RHS) {
if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
RHS == getEmptyKey() || RHS == getTombstoneKey())
return LHS == RHS;
return LHS->isIdenticalTo(RHS);
}
};
DenseSet<PHINode *, PHIDenseMapInfo> PHISet;
bool Changed = false;
for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) {
auto Inserted = PHISet.insert(PN);
if (!Inserted.second) {
PN->replaceAllUsesWith(*Inserted.first);
PN->eraseFromParent();
Changed = true;
PHISet.clear();
I = BB->begin();
}
}
return Changed;
}
static unsigned enforceKnownAlignment(Value *V, unsigned Align,
unsigned PrefAlign,
const DataLayout &DL) {
V = V->stripPointerCasts();
if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
if (DL.exceedsNaturalStackAlignment(PrefAlign))
return Align;
if (AI->getAlignment() >= PrefAlign)
return AI->getAlignment();
AI->setAlignment(PrefAlign);
return PrefAlign;
}
if (auto *GO = dyn_cast<GlobalObject>(V)) {
if (!GO->isStrongDefinitionForLinker())
return Align;
if (GO->getAlignment() >= PrefAlign)
return GO->getAlignment();
if (!GO->hasSection() || GO->getAlignment() == 0)
GO->setAlignment(PrefAlign);
return GO->getAlignment();
}
return Align;
}
unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign,
const DataLayout &DL,
const Instruction *CxtI,
AssumptionCache *AC,
const DominatorTree *DT) {
assert(V->getType()->isPointerTy() &&
"getOrEnforceKnownAlignment expects a pointer!");
unsigned BitWidth = DL.getPointerTypeSizeInBits(V->getType());
APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
computeKnownBits(V, KnownZero, KnownOne, DL, 0, AC, CxtI, DT);
unsigned TrailZ = KnownZero.countTrailingOnes();
TrailZ = std::min(TrailZ, unsigned(sizeof(unsigned) * CHAR_BIT - 1));
unsigned Align = 1u << std::min(BitWidth - 1, TrailZ);
Align = std::min(Align, +Value::MaximumAlignment);
if (PrefAlign > Align)
Align = enforceKnownAlignment(V, Align, PrefAlign, DL);
return Align;
}
static bool LdStHasDebugValue(const DILocalVariable *DIVar, Instruction *I) {
llvm::BasicBlock::InstListType::iterator PrevI(I);
if (PrevI != I->getParent()->getInstList().begin()) {
--PrevI;
if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(PrevI))
if (DVI->getValue() == I->getOperand(0) &&
DVI->getOffset() == 0 &&
DVI->getVariable() == DIVar)
return true;
}
return false;
}
bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
StoreInst *SI, DIBuilder &Builder) {
auto *DIVar = DDI->getVariable();
auto *DIExpr = DDI->getExpression();
assert(DIVar && "Missing variable");
if (LdStHasDebugValue(DIVar, SI))
return true;
Argument *ExtendedArg = nullptr;
if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0)))
ExtendedArg = dyn_cast<Argument>(ZExt->getOperand(0));
if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0)))
ExtendedArg = dyn_cast<Argument>(SExt->getOperand(0));
if (ExtendedArg)
Builder.insertDbgValueIntrinsic(ExtendedArg, 0, DIVar, DIExpr,
DDI->getDebugLoc(), SI);
else
Builder.insertDbgValueIntrinsic(SI->getOperand(0), 0, DIVar, DIExpr,
DDI->getDebugLoc(), SI);
return true;
}
bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
LoadInst *LI, DIBuilder &Builder) {
auto *DIVar = DDI->getVariable();
auto *DIExpr = DDI->getExpression();
assert(DIVar && "Missing variable");
if (LdStHasDebugValue(DIVar, LI))
return true;
Builder.insertDbgValueIntrinsic(LI->getOperand(0), 0, DIVar, DIExpr,
DDI->getDebugLoc(), LI);
return true;
}
static bool isArray(AllocaInst *AI) {
return AI->isArrayAllocation() ||
AI->getType()->getElementType()->isArrayTy();
}
bool llvm::LowerDbgDeclare(Function &F) {
DIBuilder DIB(*F.getParent(), false);
SmallVector<DbgDeclareInst *, 4> Dbgs;
for (auto &FI : F)
for (Instruction &BI : FI)
if (auto DDI = dyn_cast<DbgDeclareInst>(&BI))
Dbgs.push_back(DDI);
if (Dbgs.empty())
return false;
for (auto &I : Dbgs) {
DbgDeclareInst *DDI = I;
AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
if (AI && !isArray(AI)) {
for (User *U : AI->users())
if (StoreInst *SI = dyn_cast<StoreInst>(U))
ConvertDebugDeclareToDebugValue(DDI, SI, DIB);
else if (LoadInst *LI = dyn_cast<LoadInst>(U))
ConvertDebugDeclareToDebugValue(DDI, LI, DIB);
else if (CallInst *CI = dyn_cast<CallInst>(U)) {
DIB.insertDbgValueIntrinsic(AI, 0, DDI->getVariable(),
DDI->getExpression(), DDI->getDebugLoc(),
CI);
}
DDI->eraseFromParent();
}
}
return true;
}
DbgDeclareInst *llvm::FindAllocaDbgDeclare(Value *V) {
if (auto *L = LocalAsMetadata::getIfExists(V))
if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L))
for (User *U : MDV->users())
if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(U))
return DDI;
return nullptr;
}
bool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
DIBuilder &Builder, bool Deref, int Offset) {
DbgDeclareInst *DDI = FindAllocaDbgDeclare(AI);
if (!DDI)
return false;
DebugLoc Loc = DDI->getDebugLoc();
auto *DIVar = DDI->getVariable();
auto *DIExpr = DDI->getExpression();
assert(DIVar && "Missing variable");
if (Deref || Offset) {
SmallVector<uint64_t, 4> NewDIExpr;
if (Deref)
NewDIExpr.push_back(dwarf::DW_OP_deref);
if (Offset > 0) {
NewDIExpr.push_back(dwarf::DW_OP_plus);
NewDIExpr.push_back(Offset);
} else if (Offset < 0) {
NewDIExpr.push_back(dwarf::DW_OP_minus);
NewDIExpr.push_back(-Offset);
}
if (DIExpr)
NewDIExpr.append(DIExpr->elements_begin(), DIExpr->elements_end());
DIExpr = Builder.createExpression(NewDIExpr);
}
Builder.insertDeclare(NewAllocaAddress, DIVar, DIExpr, Loc,
AI->getNextNode());
DDI->eraseFromParent();
return true;
}
static void changeToUnreachable(Instruction *I, bool UseLLVMTrap) {
BasicBlock *BB = I->getParent();
for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
(*SI)->removePredecessor(BB);
if (UseLLVMTrap) {
Function *TrapFn =
Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);
CallInst *CallTrap = CallInst::Create(TrapFn, "", I);
CallTrap->setDebugLoc(I->getDebugLoc());
}
new UnreachableInst(I->getContext(), I);
BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
while (BBI != BBE) {
if (!BBI->use_empty())
BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
BB->getInstList().erase(BBI++);
}
}
static void changeToCall(InvokeInst *II) {
SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3);
CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, "", II);
NewCall->takeName(II);
NewCall->setCallingConv(II->getCallingConv());
NewCall->setAttributes(II->getAttributes());
NewCall->setDebugLoc(II->getDebugLoc());
II->replaceAllUsesWith(NewCall);
BranchInst::Create(II->getNormalDest(), II);
II->getUnwindDest()->removePredecessor(II->getParent());
II->eraseFromParent();
}
static bool markAliveBlocks(Function &F,
SmallPtrSetImpl<BasicBlock*> &Reachable) {
SmallVector<BasicBlock*, 128> Worklist;
BasicBlock *BB = &F.front();
Worklist.push_back(BB);
Reachable.insert(BB);
bool Changed = false;
do {
BB = Worklist.pop_back_val();
for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(BBI))
if (II->getIntrinsicID() == Intrinsic::assume) {
bool MakeUnreachable = false;
if (isa<UndefValue>(II->getArgOperand(0)))
MakeUnreachable = true;
else if (ConstantInt *Cond =
dyn_cast<ConstantInt>(II->getArgOperand(0)))
MakeUnreachable = Cond->isZero();
if (MakeUnreachable) {
changeToUnreachable(&*BBI, false);
Changed = true;
break;
}
}
if (CallInst *CI = dyn_cast<CallInst>(BBI)) {
if (CI->doesNotReturn()) {
++BBI;
if (!isa<UnreachableInst>(BBI)) {
changeToUnreachable(&*BBI, false);
Changed = true;
}
break;
}
}
if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
if (SI->isVolatile()) continue;
Value *Ptr = SI->getOperand(1);
if (isa<UndefValue>(Ptr) ||
(isa<ConstantPointerNull>(Ptr) &&
SI->getPointerAddressSpace() == 0)) {
changeToUnreachable(SI, true);
Changed = true;
break;
}
}
}
if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) {
Value *Callee = II->getCalledValue();
if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
changeToUnreachable(II, true);
Changed = true;
} else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
if (II->use_empty() && II->onlyReadsMemory()) {
BranchInst::Create(II->getNormalDest(), II);
II->getUnwindDest()->removePredecessor(II->getParent());
II->eraseFromParent();
} else
changeToCall(II);
Changed = true;
}
}
Changed |= ConstantFoldTerminator(BB, true);
for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
if (Reachable.insert(*SI).second)
Worklist.push_back(*SI);
} while (!Worklist.empty());
return Changed;
}
void llvm::removeUnwindEdge(BasicBlock *BB) {
TerminatorInst *TI = BB->getTerminator();
if (auto *II = dyn_cast<InvokeInst>(TI)) {
changeToCall(II);
return;
}
TerminatorInst *NewTI;
BasicBlock *UnwindDest;
if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
UnwindDest = CRI->getUnwindDest();
} else if (auto *CEP = dyn_cast<CleanupEndPadInst>(TI)) {
NewTI = CleanupEndPadInst::Create(CEP->getCleanupPad(), nullptr, CEP);
UnwindDest = CEP->getUnwindDest();
} else if (auto *CEP = dyn_cast<CatchEndPadInst>(TI)) {
NewTI = CatchEndPadInst::Create(CEP->getContext(), nullptr, CEP);
UnwindDest = CEP->getUnwindDest();
} else if (auto *TPI = dyn_cast<TerminatePadInst>(TI)) {
SmallVector<Value *, 3> TerminatePadArgs;
for (Value *Operand : TPI->arg_operands())
TerminatePadArgs.push_back(Operand);
NewTI = TerminatePadInst::Create(TPI->getContext(), nullptr,
TerminatePadArgs, TPI);
UnwindDest = TPI->getUnwindDest();
} else {
llvm_unreachable("Could not find unwind successor");
}
NewTI->takeName(TI);
NewTI->setDebugLoc(TI->getDebugLoc());
UnwindDest->removePredecessor(BB);
TI->eraseFromParent();
}
bool llvm::removeUnreachableBlocks(Function &F) {
SmallPtrSet<BasicBlock*, 128> Reachable;
bool Changed = markAliveBlocks(F, Reachable);
if (Reachable.size() == F.size())
return Changed;
assert(Reachable.size() < F.size());
NumRemoved += F.size()-Reachable.size();
for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) {
if (Reachable.count(&*BB))
continue;
for (succ_iterator SI = succ_begin(&*BB), SE = succ_end(&*BB); SI != SE;
++SI)
if (Reachable.count(*SI))
(*SI)->removePredecessor(&*BB);
BB->dropAllReferences();
}
for (Function::iterator I = ++F.begin(); I != F.end();)
if (!Reachable.count(&*I))
I = F.getBasicBlockList().erase(I);
else
++I;
return true;
}
void llvm::combineMetadata(Instruction *K, const Instruction *J,
ArrayRef<unsigned> KnownIDs) {
SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
K->dropUnknownNonDebugMetadata(KnownIDs);
K->getAllMetadataOtherThanDebugLoc(Metadata);
for (unsigned i = 0, n = Metadata.size(); i < n; ++i) {
unsigned Kind = Metadata[i].first;
MDNode *JMD = J->getMetadata(Kind);
MDNode *KMD = Metadata[i].second;
switch (Kind) {
default:
K->setMetadata(Kind, nullptr); break;
case LLVMContext::MD_dbg:
llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg");
case LLVMContext::MD_tbaa:
K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD));
break;
case LLVMContext::MD_alias_scope:
K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD));
break;
case LLVMContext::MD_noalias:
K->setMetadata(Kind, MDNode::intersect(JMD, KMD));
break;
case LLVMContext::MD_range:
K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD));
break;
case LLVMContext::MD_fpmath:
K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD));
break;
case LLVMContext::MD_invariant_load:
K->setMetadata(Kind, JMD);
break;
case LLVMContext::MD_nonnull:
K->setMetadata(Kind, JMD);
break;
case LLVMContext::MD_invariant_group:
break;
case LLVMContext::MD_align:
K->setMetadata(Kind,
MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD));
break;
case LLVMContext::MD_dereferenceable:
case LLVMContext::MD_dereferenceable_or_null:
K->setMetadata(Kind,
MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD));
break;
}
}
if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group))
if (isa<LoadInst>(K) || isa<StoreInst>(K))
K->setMetadata(LLVMContext::MD_invariant_group, JMD);
}
unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
DominatorTree &DT,
const BasicBlockEdge &Root) {
assert(From->getType() == To->getType());
unsigned Count = 0;
for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
UI != UE; ) {
Use &U = *UI++;
if (DT.dominates(Root, U)) {
U.set(To);
DEBUG(dbgs() << "Replace dominated use of '"
<< From->getName() << "' as "
<< *To << " in " << *U << "\n");
++Count;
}
}
return Count;
}
unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
DominatorTree &DT,
const BasicBlock *BB) {
assert(From->getType() == To->getType());
unsigned Count = 0;
for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
UI != UE;) {
Use &U = *UI++;
auto *I = cast<Instruction>(U.getUser());
if (DT.dominates(BB, I->getParent())) {
U.set(To);
DEBUG(dbgs() << "Replace dominated use of '" << From->getName() << "' as "
<< *To << " in " << *U << "\n");
++Count;
}
}
return Count;
}
bool llvm::callsGCLeafFunction(ImmutableCallSite CS) {
if (isa<IntrinsicInst>(CS.getInstruction()))
return true;
if (const Function *F = CS.getCalledFunction())
return F->hasFnAttribute("gc-leaf-function");
return false;
}