//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "mem2reg"
#include "llvm/Transforms/Utils/PromoteMemToReg.h"
#include "llvm/ADT/ArrayRef.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/AliasSetTracker.h"
-#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/ValueTracking.h"
-#include "llvm/DIBuilder.h"
-#include "llvm/DebugInfo.h"
+#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
+#include "llvm/IR/DIBuilder.h"
+#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Metadata.h"
-#include "llvm/InstVisitor.h"
-#include "llvm/Support/CFG.h"
#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
#include <queue>
using namespace llvm;
+#define DEBUG_TYPE "mem2reg"
+
STATISTIC(NumLocalPromoted, "Number of alloca's promoted within one block");
STATISTIC(NumSingleStore, "Number of alloca's promoted with a single store");
STATISTIC(NumDeadAlloca, "Number of dead alloca's removed");
STATISTIC(NumPHIInsert, "Number of PHI nodes inserted");
+bool llvm::isAllocaPromotable(const AllocaInst *AI) {
+ // FIXME: If the memory unit is of pointer or integer type, we can permit
+ // assignments to subsections of the memory unit.
+ unsigned AS = AI->getType()->getAddressSpace();
+
+ // Only allow direct and non-volatile loads and stores...
+ for (const User *U : AI->users()) {
+ if (const LoadInst *LI = dyn_cast<LoadInst>(U)) {
+ // Note that atomic loads can be transformed; atomic semantics do
+ // not have any meaning for a local alloca.
+ if (LI->isVolatile())
+ return false;
+ } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) {
+ if (SI->getOperand(0) == AI)
+ return false; // Don't allow a store OF the AI, only INTO the AI.
+ // Note that atomic stores can be transformed; atomic semantics do
+ // not have any meaning for a local alloca.
+ if (SI->isVolatile())
+ return false;
+ } else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(U)) {
+ if (II->getIntrinsicID() != Intrinsic::lifetime_start &&
+ II->getIntrinsicID() != Intrinsic::lifetime_end)
+ return false;
+ } else if (const BitCastInst *BCI = dyn_cast<BitCastInst>(U)) {
+ if (BCI->getType() != Type::getInt8PtrTy(U->getContext(), AS))
+ return false;
+ if (!onlyUsedByLifetimeMarkers(BCI))
+ return false;
+ } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) {
+ if (GEPI->getType() != Type::getInt8PtrTy(U->getContext(), AS))
+ return false;
+ if (!GEPI->hasAllZeroIndices())
+ return false;
+ if (!onlyUsedByLifetimeMarkers(GEPI))
+ return false;
+ } else {
+ return false;
+ }
+ }
+
+ return true;
+}
+
namespace {
-struct AllocaInfo : private InstVisitor<AllocaInfo, bool> {
+struct AllocaInfo {
SmallVector<BasicBlock *, 32> DefiningBlocks;
SmallVector<BasicBlock *, 32> UsingBlocks;
- SmallVector<Instruction *, 8> DeadInsts;
- Type *AllocaTy;
StoreInst *OnlyStore;
BasicBlock *OnlyBlock;
bool OnlyUsedInOneBlock;
void clear() {
DefiningBlocks.clear();
UsingBlocks.clear();
- DeadInsts.clear();
- AllocaTy = 0;
- OnlyStore = 0;
- OnlyBlock = 0;
+ OnlyStore = nullptr;
+ OnlyBlock = nullptr;
OnlyUsedInOneBlock = true;
- AllocaPointerVal = 0;
- DbgDeclare = 0;
+ AllocaPointerVal = nullptr;
+ DbgDeclare = nullptr;
}
/// Scan the uses of the specified alloca, filling in the AllocaInfo used
/// by the rest of the pass to reason about the uses of this alloca.
- bool analyzeAlloca(AllocaInst &AI) {
+ void AnalyzeAlloca(AllocaInst *AI) {
clear();
- AllocaTy = AI.getAllocatedType();
- enqueueUsers(AI);
-
- // Walk queued up uses in the worklist to handle nested uses.
- while (!UseWorklist.empty()) {
- U = UseWorklist.pop_back_val();
- Instruction &I = *cast<Instruction>(U->getUser());
- if (!visit(I))
- return false; // Propagate failure to promote up.
+ // As we scan the uses of the alloca instruction, keep track of stores,
+ // and decide whether all of the loads and stores to the alloca are within
+ // the same basic block.
+ for (auto UI = AI->user_begin(), E = AI->user_end(); UI != E;) {
+ Instruction *User = cast<Instruction>(*UI++);
+
+ if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
+ // Remember the basic blocks which define new values for the alloca
+ DefiningBlocks.push_back(SI->getParent());
+ AllocaPointerVal = SI->getOperand(0);
+ OnlyStore = SI;
+ } else {
+ LoadInst *LI = cast<LoadInst>(User);
+ // Otherwise it must be a load instruction, keep track of variable
+ // reads.
+ UsingBlocks.push_back(LI->getParent());
+ AllocaPointerVal = LI;
+ }
if (OnlyUsedInOneBlock) {
- if (OnlyBlock == 0)
- OnlyBlock = I.getParent();
- else if (OnlyBlock != I.getParent())
+ if (!OnlyBlock)
+ OnlyBlock = User->getParent();
+ else if (OnlyBlock != User->getParent())
OnlyUsedInOneBlock = false;
}
}
- DbgDeclare = FindAllocaDbgDeclare(&AI);
- return true;
- }
-
-private:
- // Befriend the base class so it can call through private visitor methods.
- friend class InstVisitor<AllocaInfo, bool>;
-
- /// \brief A use pointer that is non-null when visiting uses.
- Use *U;
-
- /// \brief A worklist for recursively visiting all uses of an alloca.
- SmallVector<Use *, 8> UseWorklist;
-
- /// \brief A set for preventing cyclic visitation.
- SmallPtrSet<Use *, 8> VisitedUses;
-
- void enqueueUsers(Instruction &I) {
- for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE;
- ++UI)
- if (VisitedUses.insert(&UI.getUse()))
- UseWorklist.push_back(&UI.getUse());
- }
-
- bool visitLoadInst(LoadInst &LI) {
- if (LI.isVolatile() || LI.getType() != AllocaTy)
- return false;
-
- // Keep track of variable reads.
- UsingBlocks.push_back(LI.getParent());
- AllocaPointerVal = &LI;
- return true;
- }
-
- bool visitStoreInst(StoreInst &SI) {
- if (SI.isVolatile() || SI.getValueOperand() == U->get() ||
- SI.getValueOperand()->getType() != AllocaTy)
- return false;
-
- // Remember the basic blocks which define new values for the alloca
- DefiningBlocks.push_back(SI.getParent());
- AllocaPointerVal = SI.getOperand(0);
- OnlyStore = &SI;
- return true;
- }
-
- bool visitBitCastInst(BitCastInst &BC) {
- if (BC.use_empty())
- DeadInsts.push_back(&BC);
- else
- enqueueUsers(BC);
- return true;
- }
-
- bool visitGetElementPtrInst(GetElementPtrInst &GEPI) {
- if (GEPI.use_empty()) {
- DeadInsts.push_back(&GEPI);
- return true;
- }
-
- enqueueUsers(GEPI);
-
- return GEPI.hasAllZeroIndices();
+ DbgDeclare = FindAllocaDbgDeclare(AI);
}
-
- // We can promote through debug info intrinsics as they don't alter the
- // value stored in memory.
- bool visitDbgInfoIntrinsic(DbgInfoIntrinsic &I) {
- DeadInsts.push_back(&I);
- return true;
- }
-
- bool visitIntrinsicInst(IntrinsicInst &II) {
- switch (II.getIntrinsicID()) {
- default:
- return false;
-
- // Lifetime intrinsics don't preclude promoting the memory to a register.
- // FIXME: We should use these to promote to undef when outside of a valid
- // lifetime.
- case Intrinsic::lifetime_start:
- case Intrinsic::lifetime_end:
- DeadInsts.push_back(&II);
- return true;
- }
- }
-
- // The fallback is that the alloca cannot be promoted.
- bool visitInstruction(Instruction &I) { return false; }
};
// Data package used by RenamePass()
public:
typedef std::vector<Value *> ValVector;
- RenamePassData() : BB(NULL), Pred(NULL), Values() {}
+ RenamePassData() : BB(nullptr), Pred(nullptr), Values() {}
RenamePassData(BasicBlock *B, BasicBlock *P, const ValVector &V)
: BB(B), Pred(P), Values(V) {}
BasicBlock *BB;
void DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum,
AllocaInfo &Info);
void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info,
- const SmallPtrSet<BasicBlock *, 32> &DefBlocks,
- SmallPtrSet<BasicBlock *, 32> &LiveInBlocks);
+ const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
+ SmallPtrSetImpl<BasicBlock *> &LiveInBlocks);
void RenamePass(BasicBlock *BB, BasicBlock *Pred,
RenamePassData::ValVector &IncVals,
std::vector<RenamePassData> &Worklist);
} // end of anonymous namespace
-/// \brief Walk a small vector of dead instructions and recursively remove them
-/// and subsequently dead instructions.
-///
-/// This is only valid to call on dead instructions using an alloca which is
-/// promotable, as we leverage that assumption to delete them faster.
-static void removeDeadInstructions(AllocaInst *AI,
- SmallVectorImpl<Instruction *> &DeadInsts) {
- while (!DeadInsts.empty()) {
- Instruction *I = DeadInsts.pop_back_val();
-
- // Don't delete the alloca itself.
- if (I == AI)
- continue;
-
- // Note that we open code the deletion algorithm here because we know
- // apriori that all of the instructions using an alloca that reaches here
- // are trivially dead when their use list becomes empty (The only risk are
- // lifetime markers which we specifically want to nuke). By coding it here
- // we can skip the triviality test and be more efficient.
- //
- // Null out all of the instruction's operands to see if any operand becomes
- // dead as we go.
- for (User::op_iterator OI = I->op_begin(), OE = I->op_end(); OI != OE;
- ++OI) {
- Instruction *Op = dyn_cast<Instruction>(*OI);
- if (!Op)
- continue;
+static void removeLifetimeIntrinsicUsers(AllocaInst *AI) {
+ // Knowing that this alloca is promotable, we know that it's safe to kill all
+ // instructions except for load and store.
- OI->set(0);
- if (!Op->use_empty())
- continue;
+ for (auto UI = AI->user_begin(), UE = AI->user_end(); UI != UE;) {
+ Instruction *I = cast<Instruction>(*UI);
+ ++UI;
+ if (isa<LoadInst>(I) || isa<StoreInst>(I))
+ continue;
- DeadInsts.push_back(Op);
+ if (!I->getType()->isVoidTy()) {
+ // The only users of this bitcast/GEP instruction are lifetime intrinsics.
+ // Follow the use/def chain to erase them now instead of leaving it for
+ // dead code elimination later.
+ for (auto UUI = I->user_begin(), UUE = I->user_end(); UUI != UUE;) {
+ Instruction *Inst = cast<Instruction>(*UUI);
+ ++UUI;
+ Inst->eraseFromParent();
+ }
}
I->eraseFromParent();
}
// Clear out UsingBlocks. We will reconstruct it here if needed.
Info.UsingBlocks.clear();
- for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;) {
+ for (auto UI = AI->user_begin(), E = AI->user_end(); UI != E;) {
Instruction *UserInst = cast<Instruction>(*UI++);
if (!isa<LoadInst>(UserInst)) {
assert(UserInst == OnlyStore && "Should only have load/stores");
DIBuilder DIB(*AI->getParent()->getParent()->getParent());
ConvertDebugDeclareToDebugValue(DDI, Info.OnlyStore, DIB);
DDI->eraseFromParent();
+ LBI.deleteValue(DDI);
}
// Remove the (now dead) store and alloca.
Info.OnlyStore->eraseFromParent();
return true;
}
-namespace {
-/// This is a helper predicate used to search by the first element of a pair.
-struct StoreIndexSearchPredicate {
- bool operator()(const std::pair<unsigned, StoreInst *> &LHS,
- const std::pair<unsigned, StoreInst *> &RHS) {
- return LHS.first < RHS.first;
- }
-};
-}
-
/// Many allocas are only used within a single basic block. If this is the
/// case, avoid traversing the CFG and inserting a lot of potentially useless
/// PHI nodes by just performing a single linear pass over the basic block
typedef SmallVector<std::pair<unsigned, StoreInst *>, 64> StoresByIndexTy;
StoresByIndexTy StoresByIndex;
- for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;
- ++UI)
- if (StoreInst *SI = dyn_cast<StoreInst>(*UI))
+ for (User *U : AI->users())
+ if (StoreInst *SI = dyn_cast<StoreInst>(U))
StoresByIndex.push_back(std::make_pair(LBI.getInstructionIndex(SI), SI));
// Sort the stores by their index, making it efficient to do a lookup with a
// binary search.
- std::sort(StoresByIndex.begin(), StoresByIndex.end(),
- StoreIndexSearchPredicate());
+ std::sort(StoresByIndex.begin(), StoresByIndex.end(), less_first());
// Walk all of the loads from this alloca, replacing them with the nearest
// store above them, if any.
- for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;) {
+ for (auto UI = AI->user_begin(), E = AI->user_end(); UI != E;) {
LoadInst *LI = dyn_cast<LoadInst>(*UI++);
if (!LI)
continue;
// Find the nearest store that has a lower index than this load.
StoresByIndexTy::iterator I =
std::lower_bound(StoresByIndex.begin(), StoresByIndex.end(),
- std::make_pair(LoadIdx, static_cast<StoreInst *>(0)),
- StoreIndexSearchPredicate());
+ std::make_pair(LoadIdx,
+ static_cast<StoreInst *>(nullptr)),
+ less_first());
if (I == StoresByIndex.begin())
// If there is no store before this load, the load takes the undef value.
LI->replaceAllUsesWith(UndefValue::get(LI->getType()));
else
// Otherwise, there was a store before this load, the load takes its value.
- LI->replaceAllUsesWith(llvm::prior(I)->second->getOperand(0));
+ LI->replaceAllUsesWith(std::prev(I)->second->getOperand(0));
if (AST && LI->getType()->isPointerTy())
AST->deleteValue(LI);
// Remove the (now dead) stores and alloca.
while (!AI->use_empty()) {
- StoreInst *SI = cast<StoreInst>(AI->use_back());
+ StoreInst *SI = cast<StoreInst>(AI->user_back());
// Record debuginfo for the store before removing it.
if (DbgDeclareInst *DDI = Info.DbgDeclare) {
DIBuilder DIB(*AI->getParent()->getParent()->getParent());
LBI.deleteValue(AI);
// The alloca's debuginfo can be removed as well.
- if (DbgDeclareInst *DDI = Info.DbgDeclare)
+ if (DbgDeclareInst *DDI = Info.DbgDeclare) {
DDI->eraseFromParent();
+ LBI.deleteValue(DDI);
+ }
++NumLocalPromoted;
}
for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
AllocaInst *AI = Allocas[AllocaNum];
+ assert(isAllocaPromotable(AI) && "Cannot promote non-promotable alloca!");
assert(AI->getParent()->getParent() == &F &&
"All allocas should be in the same function, which is same as DF!");
- // Calculate the set of read and write-locations for each alloca. This is
- // analogous to finding the 'uses' and 'definitions' of each variable.
- bool Good = Info.analyzeAlloca(*AI);
- (void)Good;
- assert(Good && "Cannot promote non-promotable alloca!");
-
- // Nuke all of the dead instructions.
- removeDeadInstructions(AI, Info.DeadInsts);
+ removeLifetimeIntrinsicUsers(AI);
if (AI->use_empty()) {
// If there are no uses of the alloca, just delete it now.
continue;
}
+ // Calculate the set of read and write-locations for each alloca. This is
+ // analogous to finding the 'uses' and 'definitions' of each variable.
+ Info.AnalyzeAlloca(AI);
+
// If there is only a single store to this value, replace any loads of
// it that are directly dominated by the definition with the value stored.
if (Info.DefiningBlocks.size() == 1) {
// and inserting the phi nodes we marked as necessary
//
std::vector<RenamePassData> RenamePassWorkList;
- RenamePassWorkList.push_back(RenamePassData(F.begin(), 0, Values));
+ RenamePassWorkList.push_back(RenamePassData(F.begin(), nullptr, Values));
do {
RenamePassData RPD;
RPD.swap(RenamePassWorkList.back());
// Iterating over NewPhiNodes is deterministic, so it is safe to try to
// simplify and RAUW them as we go. If it was not, we could add uses to
- // the values we replace with in a non deterministic order, thus creating
- // non deterministic def->use chains.
+ // the values we replace with in a non-deterministic order, thus creating
+ // non-deterministic def->use chains.
for (DenseMap<std::pair<unsigned, unsigned>, PHINode *>::iterator
I = NewPhiNodes.begin(),
E = NewPhiNodes.end();
PHINode *PN = I->second;
// If this PHI node merges one value and/or undefs, get the value.
- if (Value *V = SimplifyInstruction(PN, 0, 0, &DT)) {
+ if (Value *V = SimplifyInstruction(PN, nullptr, nullptr, &DT)) {
if (AST && PN->getType()->isPointerTy())
AST->deleteValue(PN);
PN->replaceAllUsesWith(V);
/// inserted phi nodes would be dead).
void PromoteMem2Reg::ComputeLiveInBlocks(
AllocaInst *AI, AllocaInfo &Info,
- const SmallPtrSet<BasicBlock *, 32> &DefBlocks,
- SmallPtrSet<BasicBlock *, 32> &LiveInBlocks) {
+ const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
+ SmallPtrSetImpl<BasicBlock *> &LiveInBlocks) {
// To determine liveness, we must iterate through the predecessors of blocks
// where the def is live. Blocks are added to the worklist if we need to
}
}
-namespace {
-typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
-
-struct DomTreeNodeCompare {
- bool operator()(const DomTreeNodePair &LHS, const DomTreeNodePair &RHS) {
- return LHS.second < RHS.second;
- }
-};
-} // end anonymous namespace
-
/// At this point, we're committed to promoting the alloca using IDF's, and the
/// standard SSA construction algorithm. Determine which blocks need phi nodes
/// and see if we can optimize out some work by avoiding insertion of dead phi
// Use a priority queue keyed on dominator tree level so that inserted nodes
// are handled from the bottom of the dominator tree upwards.
- typedef std::priority_queue<DomTreeNodePair,
- SmallVector<DomTreeNodePair, 32>,
- DomTreeNodeCompare> IDFPriorityQueue;
+ typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
+ typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
+ less_second> IDFPriorityQueue;
IDFPriorityQueue PQ;
for (SmallPtrSet<BasicBlock *, 32>::const_iterator I = DefBlocks.begin(),
// Get the next phi node.
++PNI;
APN = dyn_cast<PHINode>(PNI);
- if (APN == 0)
+ if (!APN)
break;
// Verify that it is missing entries. If not, it is not being inserted
goto NextIteration;
}
-bool llvm::isAllocaPromotable(const AllocaInst *AI) {
- // We cast away constness because we re-use the non-const analysis that the
- // actual promotion routine uses. While it is non-const, it doesn't actually
- // mutate anything at this phase, and we discard the non-const results that
- // promotion uses to mutate the alloca.
- return AllocaInfo().analyzeAlloca(*const_cast<AllocaInst *>(AI));
-}
-
-void llvm::PromoteMemToReg(ArrayRef<AllocaInst *> Allocas,
- DominatorTree &DT, AliasSetTracker *AST) {
+void llvm::PromoteMemToReg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT,
+ AliasSetTracker *AST) {
// If there is nothing to do, bail out...
if (Allocas.empty())
return;
projects / oota-llvm.git / blobdiff