#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/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/ProfileInfo.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
static Value *getUnderlyingObjectWithOffset(Value *V, const TargetData *TD,
uint64_t &ByteOffset,
unsigned MaxLookup = 6) {
if (!V->getType()->isPointerTy())
return V;
for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
if (!GEP->hasAllConstantIndices())
return V;
SmallVector<Value*, 8> Indices(GEP->op_begin() + 1, GEP->op_end());
ByteOffset += TD->getIndexedOffset(GEP->getPointerOperandType(),
&Indices[0], Indices.size());
V = GEP->getPointerOperand();
} else if (Operator::getOpcode(V) == Instruction::BitCast) {
V = cast<Operator>(V)->getOperand(0);
} else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
if (GA->mayBeOverridden())
return V;
V = GA->getAliasee();
} else {
return V;
}
assert(V->getType()->isPointerTy() && "Unexpected operand type!");
}
return V;
}
bool llvm::isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom,
unsigned Align, const TargetData *TD) {
uint64_t ByteOffset = 0;
Value *Base = V;
if (TD)
Base = getUnderlyingObjectWithOffset(V, TD, ByteOffset);
const Type *BaseType = 0;
unsigned BaseAlign = 0;
if (const AllocaInst *AI = dyn_cast<AllocaInst>(Base)) {
BaseType = AI->getAllocatedType();
BaseAlign = AI->getAlignment();
} else if (const GlobalValue *GV = dyn_cast<GlobalValue>(Base)) {
if (!isa<GlobalAlias>(GV) && !GV->mayBeOverridden()) {
BaseType = GV->getType()->getElementType();
BaseAlign = GV->getAlignment();
}
}
if (BaseType && BaseType->isSized()) {
if (TD && BaseAlign == 0)
BaseAlign = TD->getPrefTypeAlignment(BaseType);
if (Align <= BaseAlign) {
if (!TD)
return true;
const PointerType *AddrTy = cast<PointerType>(V->getType());
uint64_t LoadSize = TD->getTypeStoreSize(AddrTy->getElementType());
if (ByteOffset + LoadSize <= TD->getTypeAllocSize(BaseType) &&
(Align == 0 || (ByteOffset % Align) == 0))
return true;
}
}
BasicBlock::iterator BBI = ScanFrom, E = ScanFrom->getParent()->begin();
while (BBI != E) {
--BBI;
if (isa<CallInst>(BBI) && BBI->mayWriteToMemory() &&
!isa<DbgInfoIntrinsic>(BBI))
return false;
if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
if (LI->getOperand(0) == V) return true;
} else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
if (SI->getOperand(1) == V) return true;
}
}
return false;
}
bool llvm::ConstantFoldTerminator(BasicBlock *BB) {
TerminatorInst *T = BB->getTerminator();
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;
assert(BI->getParent() && "Terminator not inserted in block!");
OldDest->removePredecessor(BI->getParent());
BI->setUnconditionalDest(Destination);
return true;
}
if (Dest2 == Dest1) {
assert(BI->getParent() && "Terminator not inserted in block!");
Dest1->removePredecessor(BI->getParent());
BI->setUnconditionalDest(Dest1);
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) {
BranchInst::Create(TheOnlyDest, SI);
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 = new ICmpInst(SI, ICmpInst::ICMP_EQ, SI->getCondition(),
SI->getSuccessorValue(1), "cond");
BranchInst::Create(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI);
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();
BranchInst::Create(TheOnlyDest, IBI);
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 (isa<DbgInfoIntrinsic>(I)) return false;
if (isa<MemoryUseIntrinsic>(I)) return false;
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;
}
bool
llvm::RecursivelyDeleteDeadPHINode(PHINode *PN) {
if (!PN->hasOneUse())
return false;
bool Changed = false;
SmallPtrSet<PHINode *, 4> PHIs;
PHIs.insert(PN);
for (Instruction *J = cast<Instruction>(*PN->use_begin());
J->hasOneUse() && !J->mayHaveSideEffects();
J = cast<Instruction>(*J->use_begin()))
if (PHINode *JP = dyn_cast<PHINode>(J))
if (!PHIs.insert(cast<PHINode>(JP))) {
JP->replaceAllUsesWith(UndefValue::get(JP->getType()));
(void)RecursivelyDeleteTriviallyDeadInstructions(JP);
Changed = true;
break;
}
return Changed;
}
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 == 0)
BI = BB->begin();
continue;
}
MadeChange |= RecursivelyDeleteTriviallyDeadInstructions(Inst);
}
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 = PN->hasConstantValue();
if (PNV == 0) continue;
assert(PNV != PN && "hasConstantValue broken");
ReplaceAndSimplifyAllUses(PN, PNV, TD);
if (PhiIt == 0) 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) {
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)
if (BBPreds.count(*PI))
CommonPreds.insert(*PI);
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) {
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));
}
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;
}