#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/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"
BasicBlock *BB = SI->getParent();
// Remove entries from PHI nodes which we no longer branch to...
- for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
+ for (BasicBlock *Succ : SI->successors()) {
// Found case matching a constant operand?
- BasicBlock *Succ = SI->getSuccessor(i);
if (Succ == TheOnlyDest)
TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest
else
const TargetLibraryInfo *TLI) {
if (!I->use_empty() || isa<TerminatorInst>(I)) return false;
- // We don't want the landingpad instruction removed by anything this general.
- if (isa<LandingPadInst>(I))
+ // We don't want the landingpad-like instructions removed by anything this
+ // general.
+ if (I->isEHPad())
return false;
// We don't want debug info removed by anything this general, unless
///
/// This returns true if it changed the code, note that it can delete
/// instructions in other blocks as well in this block.
-bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, const DataLayout *TD,
+bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB,
const TargetLibraryInfo *TLI) {
bool MadeChange = false;
Instruction *Inst = BI++;
WeakVH BIHandle(BI);
- if (recursivelySimplifyInstruction(Inst, TD, TLI)) {
+ if (recursivelySimplifyInstruction(Inst, TLI)) {
MadeChange = true;
if (BIHandle != BI)
BI = BB->begin();
///
/// .. and delete the predecessor corresponding to the '1', this will attempt to
/// recursively fold the and to 0.
-void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred,
- DataLayout *TD) {
+void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred) {
// This only adjusts blocks with PHI nodes.
if (!isa<PHINode>(BB->begin()))
return;
PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt));
Value *OldPhiIt = PhiIt;
- if (!recursivelySimplifyInstruction(PN, TD))
+ if (!recursivelySimplifyInstruction(PN))
continue;
// If recursive simplification ended up deleting the next PHI node we would
/// orders them so it usually won't matter.
///
bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
- bool Changed = false;
-
// This implementation doesn't currently consider undef operands
// specially. Theoretically, two phis which are identical except for
// one having an undef where the other doesn't could be collapsed.
- // Map from PHI hash values to PHI nodes. If multiple PHIs have
- // the same hash value, the element is the first PHI in the
- // linked list in CollisionMap.
- DenseMap<uintptr_t, PHINode *> HashMap;
+ struct PHIDenseMapInfo {
+ static PHINode *getEmptyKey() {
+ return DenseMapInfo<PHINode *>::getEmptyKey();
+ }
+ static PHINode *getTombstoneKey() {
+ return DenseMapInfo<PHINode *>::getTombstoneKey();
+ }
+ static unsigned getHashValue(PHINode *PN) {
+ // Compute a hash value on the operands. Instcombine will likely have
+ // sorted them, which helps expose duplicates, but we have to check all
+ // the operands to be safe in case instcombine hasn't run.
+ 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);
+ }
+ };
- // Maintain linked lists of PHI nodes with common hash values.
- DenseMap<PHINode *, PHINode *> CollisionMap;
+ // Set of unique PHINodes.
+ DenseSet<PHINode *, PHIDenseMapInfo> PHISet;
// Examine each PHI.
- for (BasicBlock::iterator I = BB->begin();
- PHINode *PN = dyn_cast<PHINode>(I++); ) {
- // Compute a hash value on the operands. Instcombine will likely have sorted
- // them, which helps expose duplicates, but we have to check all the
- // operands to be safe in case instcombine hasn't run.
- uintptr_t Hash = 0;
- // This hash algorithm is quite weak as hash functions go, but it seems
- // to do a good enough job for this particular purpose, and is very quick.
- 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));
- }
- for (PHINode::block_iterator I = PN->block_begin(), E = PN->block_end();
- I != E; ++I) {
- Hash ^= reinterpret_cast<uintptr_t>(static_cast<BasicBlock *>(*I));
- Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7));
- }
- // Avoid colliding with the DenseMap sentinels ~0 and ~0-1.
- Hash >>= 1;
- // If we've never seen this hash value before, it's a unique PHI.
- std::pair<DenseMap<uintptr_t, PHINode *>::iterator, bool> Pair =
- HashMap.insert(std::make_pair(Hash, PN));
- if (Pair.second) continue;
- // Otherwise it's either a duplicate or a hash collision.
- for (PHINode *OtherPN = Pair.first->second; ; ) {
- if (OtherPN->isIdenticalTo(PN)) {
- // A duplicate. Replace this PHI with its duplicate.
- PN->replaceAllUsesWith(OtherPN);
- PN->eraseFromParent();
- Changed = true;
- break;
- }
- // A non-duplicate hash collision.
- DenseMap<PHINode *, PHINode *>::iterator I = CollisionMap.find(OtherPN);
- if (I == CollisionMap.end()) {
- // Set this PHI to be the head of the linked list of colliding PHIs.
- PHINode *Old = Pair.first->second;
- Pair.first->second = PN;
- CollisionMap[PN] = Old;
- break;
- }
- // Proceed to the next PHI in the list.
- OtherPN = I->second;
+ bool Changed = false;
+ for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) {
+ auto Inserted = PHISet.insert(PN);
+ if (!Inserted.second) {
+ // A duplicate. Replace this PHI with its duplicate.
+ PN->replaceAllUsesWith(*Inserted.first);
+ PN->eraseFromParent();
+ Changed = true;
}
}
/// their preferred alignment from the beginning.
///
static unsigned enforceKnownAlignment(Value *V, unsigned Align,
- unsigned PrefAlign, const DataLayout *TD) {
+ unsigned PrefAlign,
+ const DataLayout &DL) {
V = V->stripPointerCasts();
if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
// If the preferred alignment is greater than the natural stack alignment
// then don't round up. This avoids dynamic stack realignment.
- if (TD && TD->exceedsNaturalStackAlignment(PrefAlign))
+ if (DL.exceedsNaturalStackAlignment(PrefAlign))
return Align;
// If there is a requested alignment and if this is an alloca, round up.
if (AI->getAlignment() >= PrefAlign)
if (auto *GO = dyn_cast<GlobalObject>(V)) {
// If there is a large requested alignment and we can, bump up the alignment
- // of the global.
- if (GO->isDeclaration())
- return Align;
- // If the memory we set aside for the global may not be the memory used by
- // the final program then it is impossible for us to reliably enforce the
- // preferred alignment.
- if (GO->isWeakForLinker())
+ // of the global. If the memory we set aside for the global may not be the
+ // memory used by the final program then it is impossible for us to reliably
+ // enforce the preferred alignment.
+ if (!GO->isStrongDefinitionForLinker())
return Align;
if (GO->getAlignment() >= PrefAlign)
/// and it is more than the alignment of the ultimate object, see if we can
/// increase the alignment of the ultimate object, making this check succeed.
unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign,
- const DataLayout *DL,
- AssumptionCache *AC,
+ const DataLayout &DL,
const Instruction *CxtI,
+ AssumptionCache *AC,
const DominatorTree *DT) {
assert(V->getType()->isPointerTy() &&
"getOrEnforceKnownAlignment expects a pointer!");
- unsigned BitWidth = DL ? DL->getPointerTypeSizeInBits(V->getType()) : 64;
+ unsigned BitWidth = DL.getPointerTypeSizeInBits(V->getType());
APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
computeKnownBits(V, KnownZero, KnownOne, DL, 0, AC, CxtI, DT);
///
/// See if there is a dbg.value intrinsic for DIVar before I.
-static bool LdStHasDebugValue(DIVariable &DIVar, Instruction *I) {
+static bool LdStHasDebugValue(const DILocalVariable *DIVar, Instruction *I) {
// Since we can't guarantee that the original dbg.declare instrinsic
// is removed by LowerDbgDeclare(), we need to make sure that we are
// not inserting the same dbg.value intrinsic over and over.
/// that has an associated llvm.dbg.decl intrinsic.
bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
StoreInst *SI, DIBuilder &Builder) {
- DIVariable DIVar(DDI->getVariable());
- DIExpression DIExpr(DDI->getExpression());
- assert((!DIVar || DIVar.isVariable()) &&
- "Variable in DbgDeclareInst should be either null or a DIVariable.");
- if (!DIVar)
- return false;
+ auto *DIVar = DDI->getVariable();
+ auto *DIExpr = DDI->getExpression();
+ assert(DIVar && "Missing variable");
if (LdStHasDebugValue(DIVar, SI))
return true;
- Instruction *DbgVal = nullptr;
// If an argument is zero extended then use argument directly. The ZExt
// may be zapped by an optimization pass in future.
Argument *ExtendedArg = nullptr;
if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0)))
ExtendedArg = dyn_cast<Argument>(SExt->getOperand(0));
if (ExtendedArg)
- DbgVal = Builder.insertDbgValueIntrinsic(ExtendedArg, 0, DIVar, DIExpr, SI);
+ Builder.insertDbgValueIntrinsic(ExtendedArg, 0, DIVar, DIExpr,
+ DDI->getDebugLoc(), SI);
else
- DbgVal = Builder.insertDbgValueIntrinsic(SI->getOperand(0), 0, DIVar,
- DIExpr, SI);
- DbgVal->setDebugLoc(DDI->getDebugLoc());
+ Builder.insertDbgValueIntrinsic(SI->getOperand(0), 0, DIVar, DIExpr,
+ DDI->getDebugLoc(), SI);
return true;
}
/// that has an associated llvm.dbg.decl intrinsic.
bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
LoadInst *LI, DIBuilder &Builder) {
- DIVariable DIVar(DDI->getVariable());
- DIExpression DIExpr(DDI->getExpression());
- assert((!DIVar || DIVar.isVariable()) &&
- "Variable in DbgDeclareInst should be either null or a DIVariable.");
- if (!DIVar)
- return false;
+ auto *DIVar = DDI->getVariable();
+ auto *DIExpr = DDI->getExpression();
+ assert(DIVar && "Missing variable");
if (LdStHasDebugValue(DIVar, LI))
return true;
- Instruction *DbgVal =
- Builder.insertDbgValueIntrinsic(LI->getOperand(0), 0, DIVar, DIExpr, LI);
- DbgVal->setDebugLoc(DDI->getDebugLoc());
+ Builder.insertDbgValueIntrinsic(LI->getOperand(0), 0, DIVar, DIExpr,
+ DDI->getDebugLoc(), LI);
return true;
}
// This is a call by-value or some other instruction that
// takes a pointer to the variable. Insert a *value*
// intrinsic that describes the alloca.
- auto DbgVal = DIB.insertDbgValueIntrinsic(
- AI, 0, DIVariable(DDI->getVariable()),
- DIExpression(DDI->getExpression()), CI);
- DbgVal->setDebugLoc(DDI->getDebugLoc());
+ DIB.insertDbgValueIntrinsic(AI, 0, DDI->getVariable(),
+ DDI->getExpression(), DDI->getDebugLoc(),
+ CI);
}
DDI->eraseFromParent();
}
}
bool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
- DIBuilder &Builder) {
+ DIBuilder &Builder, bool Deref) {
DbgDeclareInst *DDI = FindAllocaDbgDeclare(AI);
if (!DDI)
return false;
- DIVariable DIVar(DDI->getVariable());
- DIExpression DIExpr(DDI->getExpression());
- assert((!DIVar || DIVar.isVariable()) &&
- "Variable in DbgDeclareInst should be either null or a DIVariable.");
- if (!DIVar)
- return false;
-
- // Create a copy of the original DIDescriptor for user variable, prepending
- // "deref" operation to a list of address elements, as new llvm.dbg.declare
- // will take a value storing address of the memory for variable, not
- // alloca itself.
- SmallVector<int64_t, 4> NewDIExpr;
- NewDIExpr.push_back(dwarf::DW_OP_deref);
- if (DIExpr)
- for (unsigned i = 0, n = DIExpr.getNumElements(); i < n; ++i)
- NewDIExpr.push_back(DIExpr.getElement(i));
+ DebugLoc Loc = DDI->getDebugLoc();
+ auto *DIVar = DDI->getVariable();
+ auto *DIExpr = DDI->getExpression();
+ assert(DIVar && "Missing variable");
+
+ if (Deref) {
+ // Create a copy of the original DIDescriptor for user variable, prepending
+ // "deref" operation to a list of address elements, as new llvm.dbg.declare
+ // will take a value storing address of the memory for variable, not
+ // alloca itself.
+ SmallVector<uint64_t, 4> NewDIExpr;
+ NewDIExpr.push_back(dwarf::DW_OP_deref);
+ if (DIExpr)
+ NewDIExpr.append(DIExpr->elements_begin(), DIExpr->elements_end());
+ DIExpr = Builder.createExpression(NewDIExpr);
+ }
// Insert llvm.dbg.declare in the same basic block as the original alloca,
// and remove old llvm.dbg.declare.
BasicBlock *BB = AI->getParent();
- Builder.insertDeclare(NewAllocaAddress, DIVar,
- Builder.createExpression(NewDIExpr), BB);
+ Builder.insertDeclare(NewAllocaAddress, DIVar, DIExpr, Loc, BB);
DDI->eraseFromParent();
return true;
}
II->eraseFromParent();
}
-static bool markAliveBlocks(BasicBlock *BB,
+static bool markAliveBlocks(Function &F,
SmallPtrSetImpl<BasicBlock*> &Reachable) {
SmallVector<BasicBlock*, 128> Worklist;
+ BasicBlock *BB = F.begin();
Worklist.push_back(BB);
Reachable.insert(BB);
bool Changed = false;
if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
changeToUnreachable(II, true);
Changed = true;
- } else if (II->doesNotThrow()) {
+ } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
if (II->use_empty() && II->onlyReadsMemory()) {
// jump to the normal destination branch.
BranchInst::Create(II->getNormalDest(), II);
/// otherwise.
bool llvm::removeUnreachableBlocks(Function &F) {
SmallPtrSet<BasicBlock*, 128> Reachable;
- bool Changed = markAliveBlocks(F.begin(), Reachable);
+ bool Changed = markAliveBlocks(F, Reachable);
// If there are unreachable blocks in the CFG...
if (Reachable.size() == F.size())
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;
}
}
}
+
+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;
+}
projects / oota-llvm.git / blobdiff