#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Constants.h"
#include "llvm/GlobalAlias.h"
#include "llvm/GlobalVariable.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Instructions.h"
#include "llvm/Intrinsics.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Operator.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/DebugInfo.h"
#include "llvm/Analysis/DIBuilder.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/ProfileInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/IRBuilder.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
bool llvm::ConstantFoldTerminator(BasicBlock *BB) {
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);
BI->eraseFromParent();
return true;
}
return false;
}
if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition());
BasicBlock *TheOnlyDest = SI->getSuccessor(0); BasicBlock *DefaultDest = TheOnlyDest;
assert(TheOnlyDest == SI->getDefaultDest() &&
"Default destination is not successor #0?");
for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) {
if (SI->getSuccessorValue(i) == CI) {
TheOnlyDest = SI->getSuccessor(i);
break;
}
if (SI->getSuccessor(i) == DefaultDest) {
DefaultDest->removePredecessor(SI->getParent());
SI->removeCase(i);
--i; --e; continue;
}
if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0;
}
if (CI && !TheOnlyDest) {
TheOnlyDest = SI->getDefaultDest();
}
if (TheOnlyDest) {
Builder.CreateBr(TheOnlyDest);
BasicBlock *BB = SI->getParent();
for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
BasicBlock *Succ = SI->getSuccessor(i);
if (Succ == TheOnlyDest)
TheOnlyDest = 0; else
Succ->removePredecessor(BB);
}
BB->getInstList().erase(SI);
return true;
}
if (SI->getNumSuccessors() == 2) {
Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
SI->getSuccessorValue(1), "cond");
Builder.CreateCondBr(Cond, SI->getSuccessor(1), SI->getSuccessor(0));
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 = 0;
else
IBI->getDestination(i)->removePredecessor(IBI->getParent());
}
IBI->eraseFromParent();
if (TheOnlyDest) {
BB->getTerminator()->eraseFromParent();
new UnreachableInst(BB->getContext(), BB);
}
return true;
}
}
return false;
}
bool llvm::isInstructionTriviallyDead(Instruction *I) {
if (!I->use_empty() || isa<TerminatorInst>(I)) 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;
return false;
}
bool llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V) {
Instruction *I = dyn_cast<Instruction>(V);
if (!I || !I->use_empty() || !isInstructionTriviallyDead(I))
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, 0);
if (!OpV->use_empty()) continue;
if (Instruction *OpI = dyn_cast<Instruction>(OpV))
if (isInstructionTriviallyDead(OpI))
DeadInsts.push_back(OpI);
}
I->eraseFromParent();
} while (!DeadInsts.empty());
return true;
}
static bool areAllUsesEqual(Instruction *I) {
Value::use_iterator UI = I->use_begin();
Value::use_iterator UE = I->use_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) {
SmallPtrSet<Instruction*, 4> Visited;
for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects();
I = cast<Instruction>(*I->use_begin())) {
if (I->use_empty())
return RecursivelyDeleteTriviallyDeadInstructions(I);
if (!Visited.insert(I)) {
I->replaceAllUsesWith(UndefValue::get(I->getType()));
(void)RecursivelyDeleteTriviallyDeadInstructions(I);
return true;
}
}
return false;
}
bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, const TargetData *TD) {
bool MadeChange = false;
for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
Instruction *Inst = BI++;
if (Value *V = SimplifyInstruction(Inst, TD)) {
WeakVH BIHandle(BI);
ReplaceAndSimplifyAllUses(Inst, V, TD);
MadeChange = true;
if (BIHandle != BI)
BI = BB->begin();
continue;
}
if (Inst->isTerminator())
break;
WeakVH BIHandle(BI);
MadeChange |= RecursivelyDeleteTriviallyDeadInstructions(Inst);
if (BIHandle != BI)
BI = BB->begin();
}
return MadeChange;
}
void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred,
TargetData *TD) {
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 *PNV = SimplifyInstruction(PN, TD);
if (PNV == 0) continue;
assert(PNV != PN && "SimplifyInstruction broken!");
Value *OldPhiIt = PhiIt;
ReplaceAndSimplifyAllUses(PN, PNV, TD);
if (PhiIt != OldPhiIt) PhiIt = &BB->front();
}
}
void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) {
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!");
PredBB->getTerminator()->eraseFromParent();
DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
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);
if (P) {
DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>();
if (DT) {
BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock();
DT->changeImmediateDominator(DestBB, PredBBIDom);
DT->eraseNode(PredBB);
}
ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>();
if (PI) {
PI->replaceAllUses(PredBB, DestBB);
PI->removeEdge(ProfileInfo::getEdge(PredBB, DestBB));
}
}
PredBB->eraseFromParent();
}
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;
typedef SmallPtrSet<BasicBlock*, 16> BlockSet;
BlockSet BBPreds(pred_begin(BB), pred_end(BB));
BlockSet CommonPreds;
for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ);
PI != PE; ++PI) {
BasicBlock *P = *PI;
if (BBPreds.count(P))
CommonPreds.insert(P);
}
if (CommonPreds.empty())
return true;
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 (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end();
PI != PE; PI++) {
if (BBPN->getIncomingValueForBlock(*PI)
!= PN->getIncomingValueForBlock(*PI)) {
DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in "
<< Succ->getName() << " is conflicting with "
<< BBPN->getName() << " with regard to common predecessor "
<< (*PI)->getName() << "\n");
return false;
}
}
} else {
Value* Val = PN->getIncomingValueForBlock(BB);
for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end();
PI != PE; PI++) {
if (Val != PN->getIncomingValueForBlock(*PI)) {
DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in "
<< Succ->getName() << " is conflicting with regard to common "
<< "predecessor " << (*PI)->getName() << "\n");
return false;
}
}
}
}
return true;
}
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 (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end();
UI != E; ++UI) {
if (PHINode* PN = dyn_cast<PHINode>(*UI)) {
if (PN->getIncomingBlock(UI) != BB)
return false;
} else {
return false;
}
}
++BBI;
}
}
DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
if (isa<PHINode>(Succ->begin())) {
const SmallVector<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB));
for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
PHINode *PN = cast<PHINode>(I);
Value *OldVal = PN->removeIncomingValue(BB, false);
assert(OldVal && "No entry in PHI for Pred BB!");
if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
PHINode *OldValPN = cast<PHINode>(OldVal);
for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i)
PN->addIncoming(OldValPN->getIncomingValue(i),
OldValPN->getIncomingBlock(i));
} else {
for (unsigned i = 0, e = BBPreds.size(); i != e; ++i)
PN->addIncoming(OldVal, BBPreds[i]);
}
}
}
while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
if (Succ->getSinglePredecessor()) {
Succ->getInstList().splice(Succ->begin(),
BB->getInstList(), BB->begin());
} else {
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) {
bool Changed = false;
DenseMap<uintptr_t, PHINode *> HashMap;
DenseMap<PHINode *, PHINode *> CollisionMap;
for (BasicBlock::iterator I = BB->begin();
PHINode *PN = dyn_cast<PHINode>(I++); ) {
uintptr_t Hash = 0;
for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) {
Hash ^= reinterpret_cast<uintptr_t>(static_cast<Value *>(*I));
Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7));
}
Hash >>= 1;
std::pair<DenseMap<uintptr_t, PHINode *>::iterator, bool> Pair =
HashMap.insert(std::make_pair(Hash, PN));
if (Pair.second) continue;
for (PHINode *OtherPN = Pair.first->second; ; ) {
if (OtherPN->isIdenticalTo(PN)) {
PN->replaceAllUsesWith(OtherPN);
PN->eraseFromParent();
Changed = true;
break;
}
DenseMap<PHINode *, PHINode *>::iterator I = CollisionMap.find(OtherPN);
if (I == CollisionMap.end()) {
PHINode *Old = Pair.first->second;
Pair.first->second = PN;
CollisionMap[PN] = Old;
break;
}
OtherPN = I->second;
}
}
return Changed;
}
static unsigned enforceKnownAlignment(Value *V, unsigned Align,
unsigned PrefAlign) {
User *U = dyn_cast<User>(V);
if (!U) return Align;
switch (Operator::getOpcode(U)) {
default: break;
case Instruction::BitCast:
return enforceKnownAlignment(U->getOperand(0), Align, PrefAlign);
case Instruction::GetElementPtr: {
bool AllZeroOperands = true;
for (User::op_iterator i = U->op_begin() + 1, e = U->op_end(); i != e; ++i)
if (!isa<Constant>(*i) ||
!cast<Constant>(*i)->isNullValue()) {
AllZeroOperands = false;
break;
}
if (AllZeroOperands) {
return enforceKnownAlignment(U->getOperand(0), Align, PrefAlign);
}
return Align;
}
case Instruction::Alloca: {
AllocaInst *AI = cast<AllocaInst>(V);
if (AI->getAlignment() >= PrefAlign)
return AI->getAlignment();
AI->setAlignment(PrefAlign);
return PrefAlign;
}
}
if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
if (GV->isDeclaration()) return Align;
if (GV->getAlignment() >= PrefAlign)
return GV->getAlignment();
if (!GV->hasSection() || GV->getAlignment() == 0)
GV->setAlignment(PrefAlign);
return GV->getAlignment();
}
return Align;
}
unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign,
const TargetData *TD) {
assert(V->getType()->isPointerTy() &&
"getOrEnforceKnownAlignment expects a pointer!");
unsigned BitWidth = TD ? TD->getPointerSizeInBits() : 64;
APInt Mask = APInt::getAllOnesValue(BitWidth);
APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD);
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);
return Align;
}
bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
StoreInst *SI, DIBuilder &Builder) {
DIVariable DIVar(DDI->getVariable());
if (!DIVar.Verify())
return false;
Instruction *DbgVal = NULL;
Argument *ExtendedArg = NULL;
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)
DbgVal = Builder.insertDbgValueIntrinsic(ExtendedArg, 0, DIVar, SI);
else
DbgVal = Builder.insertDbgValueIntrinsic(SI->getOperand(0), 0, DIVar, SI);
DebugLoc SIDL = SI->getDebugLoc();
if (!SIDL.isUnknown())
DbgVal->setDebugLoc(SIDL);
else
DbgVal->setDebugLoc(DDI->getDebugLoc());
return true;
}
bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
LoadInst *LI, DIBuilder &Builder) {
DIVariable DIVar(DDI->getVariable());
if (!DIVar.Verify())
return false;
Instruction *DbgVal =
Builder.insertDbgValueIntrinsic(LI->getOperand(0), 0,
DIVar, LI);
DebugLoc LIDL = LI->getDebugLoc();
if (!LIDL.isUnknown())
DbgVal->setDebugLoc(LIDL);
else
DbgVal->setDebugLoc(DDI->getDebugLoc());
return true;
}
bool llvm::LowerDbgDeclare(Function &F) {
DIBuilder DIB(*F.getParent());
SmallVector<DbgDeclareInst *, 4> Dbgs;
for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ++BI) {
if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(BI))
Dbgs.push_back(DDI);
}
if (Dbgs.empty())
return false;
for (SmallVector<DbgDeclareInst *, 4>::iterator I = Dbgs.begin(),
E = Dbgs.end(); I != E; ++I) {
DbgDeclareInst *DDI = *I;
if (AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress())) {
bool RemoveDDI = true;
for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end();
UI != E; ++UI)
if (StoreInst *SI = dyn_cast<StoreInst>(*UI))
ConvertDebugDeclareToDebugValue(DDI, SI, DIB);
else if (LoadInst *LI = dyn_cast<LoadInst>(*UI))
ConvertDebugDeclareToDebugValue(DDI, LI, DIB);
else
RemoveDDI = false;
if (RemoveDDI)
DDI->eraseFromParent();
}
}
return true;
}