// traversing the function in depth-first order to rewrite loads and stores as
// appropriate.
//
-// The algorithm used here is based on:
-//
-// Sreedhar and Gao. A linear time algorithm for placing phi-nodes.
-// In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of
-// Programming Languages
-// POPL '95. ACM, New York, NY, 62-73.
-//
-// It has been modified to not explicitly use the DJ graph data structure and to
-// directly compute pruned SSA using per-variable liveness information.
-//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "mem2reg"
#include "llvm/Transforms/Utils/PromoteMemToReg.h"
+#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/STLExtras.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/IteratedDominanceFrontier.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/Support/CFG.h"
+#include "llvm/IR/Module.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");
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 (Value::const_use_iterator UI = AI->use_begin(), UE = AI->use_end();
- UI != UE; ++UI) { // Loop over all of the uses of the alloca
- const User *U = *UI;
+ 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.
II->getIntrinsicID() != Intrinsic::lifetime_end)
return false;
} else if (const BitCastInst *BCI = dyn_cast<BitCastInst>(U)) {
- if (BCI->getType() != Type::getInt8PtrTy(U->getContext()))
+ 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()))
+ if (GEPI->getType() != Type::getInt8PtrTy(U->getContext(), AS))
return false;
if (!GEPI->hasAllZeroIndices())
return false;
namespace {
-struct AllocaInfo;
+struct AllocaInfo {
+ SmallVector<BasicBlock *, 32> DefiningBlocks;
+ SmallVector<BasicBlock *, 32> UsingBlocks;
+
+ StoreInst *OnlyStore;
+ BasicBlock *OnlyBlock;
+ bool OnlyUsedInOneBlock;
+
+ Value *AllocaPointerVal;
+ DbgDeclareInst *DbgDeclare;
+
+ void clear() {
+ DefiningBlocks.clear();
+ UsingBlocks.clear();
+ OnlyStore = nullptr;
+ OnlyBlock = nullptr;
+ OnlyUsedInOneBlock = true;
+ 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.
+ void AnalyzeAlloca(AllocaInst *AI) {
+ clear();
+
+ // 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)
+ OnlyBlock = User->getParent();
+ else if (OnlyBlock != User->getParent())
+ OnlyUsedInOneBlock = false;
+ }
+ }
+
+ DbgDeclare = FindAllocaDbgDeclare(AI);
+ }
+};
// Data package used by RenamePass()
class RenamePassData {
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;
/// The alloca instructions being promoted.
std::vector<AllocaInst *> Allocas;
DominatorTree &DT;
- DIBuilder *DIB;
+ DIBuilder DIB;
/// An AliasSetTracker object to update. If null, don't update it.
AliasSetTracker *AST;
+ /// A cache of @llvm.assume intrinsics used by SimplifyInstruction.
+ AssumptionCache *AC;
+
/// Reverse mapping of Allocas.
DenseMap<AllocaInst *, unsigned> AllocaLookup;
/// behavior.
DenseMap<BasicBlock *, unsigned> BBNumbers;
- /// Maps DomTreeNodes to their level in the dominator tree.
- DenseMap<DomTreeNode *, unsigned> DomLevels;
-
/// Lazily compute the number of predecessors a block has.
DenseMap<const BasicBlock *, unsigned> BBNumPreds;
public:
- PromoteMem2Reg(const std::vector<AllocaInst *> &Allocas, DominatorTree &DT,
- AliasSetTracker *AST)
- : Allocas(Allocas), DT(DT), DIB(0), AST(AST) {}
- ~PromoteMem2Reg() { delete DIB; }
+ PromoteMem2Reg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT,
+ AliasSetTracker *AST, AssumptionCache *AC)
+ : Allocas(Allocas.begin(), Allocas.end()), DT(DT),
+ DIB(*DT.getRoot()->getParent()->getParent(), /*AllowUnresolved*/ false),
+ AST(AST), AC(AC) {}
void run();
- /// Return true if BB1 dominates BB2 using the DominatorTree.
- bool dominates(BasicBlock *BB1, BasicBlock *BB2) const {
- return DT.dominates(BB1, BB2);
- }
-
private:
void RemoveFromAllocasList(unsigned &AllocaIdx) {
Allocas[AllocaIdx] = Allocas.back();
return NP - 1;
}
- void DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum,
- AllocaInfo &Info);
void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info,
- const SmallPtrSet<BasicBlock *, 32> &DefBlocks,
- SmallPtrSet<BasicBlock *, 32> &LiveInBlocks);
-
- void RewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info,
- LargeBlockInfo &LBI);
- void PromoteSingleBlockAlloca(AllocaInst *AI, AllocaInfo &Info,
- LargeBlockInfo &LBI);
-
+ const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
+ SmallPtrSetImpl<BasicBlock *> &LiveInBlocks);
void RenamePass(BasicBlock *BB, BasicBlock *Pred,
RenamePassData::ValVector &IncVals,
std::vector<RenamePassData> &Worklist);
bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version);
};
-struct AllocaInfo {
- SmallVector<BasicBlock *, 32> DefiningBlocks;
- SmallVector<BasicBlock *, 32> UsingBlocks;
+} // end of anonymous namespace
- StoreInst *OnlyStore;
- BasicBlock *OnlyBlock;
- bool OnlyUsedInOneBlock;
+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.
- Value *AllocaPointerVal;
- DbgDeclareInst *DbgDeclare;
+ 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;
- void clear() {
- DefiningBlocks.clear();
- UsingBlocks.clear();
- OnlyStore = 0;
- OnlyBlock = 0;
- OnlyUsedInOneBlock = true;
- AllocaPointerVal = 0;
- DbgDeclare = 0;
+ 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();
}
+}
- /// 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.
- void AnalyzeAlloca(AllocaInst *AI) {
- clear();
+/// \brief Rewrite as many loads as possible given a single store.
+///
+/// When there is only a single store, we can use the domtree to trivially
+/// replace all of the dominated loads with the stored value. Do so, and return
+/// true if this has successfully promoted the alloca entirely. If this returns
+/// false there were some loads which were not dominated by the single store
+/// and thus must be phi-ed with undef. We fall back to the standard alloca
+/// promotion algorithm in that case.
+static bool rewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info,
+ LargeBlockInfo &LBI,
+ DominatorTree &DT,
+ AliasSetTracker *AST) {
+ StoreInst *OnlyStore = Info.OnlyStore;
+ bool StoringGlobalVal = !isa<Instruction>(OnlyStore->getOperand(0));
+ BasicBlock *StoreBB = OnlyStore->getParent();
+ int StoreIndex = -1;
- // 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 (Value::use_iterator UI = AI->use_begin(), E = AI->use_end();
- UI != E;) {
- Instruction *User = cast<Instruction>(*UI++);
+ // Clear out UsingBlocks. We will reconstruct it here if needed.
+ Info.UsingBlocks.clear();
- 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;
- }
+ 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");
+ continue;
+ }
+ LoadInst *LI = cast<LoadInst>(UserInst);
- if (OnlyUsedInOneBlock) {
- if (OnlyBlock == 0)
- OnlyBlock = User->getParent();
- else if (OnlyBlock != User->getParent())
- OnlyUsedInOneBlock = false;
+ // Okay, if we have a load from the alloca, we want to replace it with the
+ // only value stored to the alloca. We can do this if the value is
+ // dominated by the store. If not, we use the rest of the mem2reg machinery
+ // to insert the phi nodes as needed.
+ if (!StoringGlobalVal) { // Non-instructions are always dominated.
+ if (LI->getParent() == StoreBB) {
+ // If we have a use that is in the same block as the store, compare the
+ // indices of the two instructions to see which one came first. If the
+ // load came before the store, we can't handle it.
+ if (StoreIndex == -1)
+ StoreIndex = LBI.getInstructionIndex(OnlyStore);
+
+ if (unsigned(StoreIndex) > LBI.getInstructionIndex(LI)) {
+ // Can't handle this load, bail out.
+ Info.UsingBlocks.push_back(StoreBB);
+ continue;
+ }
+
+ } else if (LI->getParent() != StoreBB &&
+ !DT.dominates(StoreBB, LI->getParent())) {
+ // If the load and store are in different blocks, use BB dominance to
+ // check their relationships. If the store doesn't dom the use, bail
+ // out.
+ Info.UsingBlocks.push_back(LI->getParent());
+ continue;
}
}
- DbgDeclare = FindAllocaDbgDeclare(AI);
+ // Otherwise, we *can* safely rewrite this load.
+ Value *ReplVal = OnlyStore->getOperand(0);
+ // If the replacement value is the load, this must occur in unreachable
+ // code.
+ if (ReplVal == LI)
+ ReplVal = UndefValue::get(LI->getType());
+ LI->replaceAllUsesWith(ReplVal);
+ if (AST && LI->getType()->isPointerTy())
+ AST->deleteValue(LI);
+ LI->eraseFromParent();
+ LBI.deleteValue(LI);
}
-};
-typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
-
-struct DomTreeNodeCompare {
- bool operator()(const DomTreeNodePair &LHS, const DomTreeNodePair &RHS) {
- return LHS.second < RHS.second;
+ // Finally, after the scan, check to see if the store is all that is left.
+ if (!Info.UsingBlocks.empty())
+ return false; // If not, we'll have to fall back for the remainder.
+
+ // Record debuginfo for the store and remove the declaration's
+ // debuginfo.
+ if (DbgDeclareInst *DDI = Info.DbgDeclare) {
+ DIBuilder DIB(*AI->getParent()->getParent()->getParent(),
+ /*AllowUnresolved*/ false);
+ ConvertDebugDeclareToDebugValue(DDI, Info.OnlyStore, DIB);
+ DDI->eraseFromParent();
+ LBI.deleteValue(DDI);
}
-};
+ // Remove the (now dead) store and alloca.
+ Info.OnlyStore->eraseFromParent();
+ LBI.deleteValue(Info.OnlyStore);
-} // end of anonymous namespace
+ if (AST)
+ AST->deleteValue(AI);
+ AI->eraseFromParent();
+ LBI.deleteValue(AI);
+ return true;
+}
-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.
+/// 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
+/// using the Alloca.
+///
+/// If we cannot promote this alloca (because it is read before it is written),
+/// return true. This is necessary in cases where, due to control flow, the
+/// alloca is potentially undefined on some control flow paths. e.g. code like
+/// this is potentially correct:
+///
+/// for (...) { if (c) { A = undef; undef = B; } }
+///
+/// ... so long as A is not used before undef is set.
+static void promoteSingleBlockAlloca(AllocaInst *AI, const AllocaInfo &Info,
+ LargeBlockInfo &LBI,
+ AliasSetTracker *AST) {
+ // The trickiest case to handle is when we have large blocks. Because of this,
+ // this code is optimized assuming that large blocks happen. This does not
+ // significantly pessimize the small block case. This uses LargeBlockInfo to
+ // make it efficient to get the index of various operations in the block.
- for (Value::use_iterator UI = AI->use_begin(), UE = AI->use_end();
- UI != UE;) {
- Instruction *I = cast<Instruction>(*UI);
- ++UI;
- if (isa<LoadInst>(I) || isa<StoreInst>(I))
+ // Walk the use-def list of the alloca, getting the locations of all stores.
+ typedef SmallVector<std::pair<unsigned, StoreInst *>, 64> StoresByIndexTy;
+ StoresByIndexTy StoresByIndex;
+
+ 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(), less_first());
+
+ // Walk all of the loads from this alloca, replacing them with the nearest
+ // store above them, if any.
+ for (auto UI = AI->user_begin(), E = AI->user_end(); UI != E;) {
+ LoadInst *LI = dyn_cast<LoadInst>(*UI++);
+ if (!LI)
continue;
- 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 (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
- UI != UE;) {
- Instruction *Inst = cast<Instruction>(*UI);
- ++UI;
- Inst->eraseFromParent();
- }
+ unsigned LoadIdx = LBI.getInstructionIndex(LI);
+
+ // 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 *>(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(std::prev(I)->second->getOperand(0));
+
+ if (AST && LI->getType()->isPointerTy())
+ AST->deleteValue(LI);
+ LI->eraseFromParent();
+ LBI.deleteValue(LI);
+ }
+
+ // Remove the (now dead) stores and alloca.
+ while (!AI->use_empty()) {
+ 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(),
+ /*AllowUnresolved*/ false);
+ ConvertDebugDeclareToDebugValue(DDI, SI, DIB);
}
- I->eraseFromParent();
+ SI->eraseFromParent();
+ LBI.deleteValue(SI);
+ }
+
+ if (AST)
+ AST->deleteValue(AI);
+ AI->eraseFromParent();
+ LBI.deleteValue(AI);
+
+ // The alloca's debuginfo can be removed as well.
+ if (DbgDeclareInst *DDI = Info.DbgDeclare) {
+ DDI->eraseFromParent();
+ LBI.deleteValue(DDI);
}
+
+ ++NumLocalPromoted;
}
void PromoteMem2Reg::run() {
AllocaInfo Info;
LargeBlockInfo LBI;
+ IDFCalculator IDF(DT);
for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
AllocaInst *AI = Allocas[AllocaNum];
// 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) {
- RewriteSingleStoreAlloca(AI, Info, LBI);
-
- // Finally, after the scan, check to see if the store is all that is left.
- if (Info.UsingBlocks.empty()) {
- // Record debuginfo for the store and remove the declaration's
- // debuginfo.
- if (DbgDeclareInst *DDI = Info.DbgDeclare) {
- if (!DIB)
- DIB = new DIBuilder(*DDI->getParent()->getParent()->getParent());
- ConvertDebugDeclareToDebugValue(DDI, Info.OnlyStore, *DIB);
- DDI->eraseFromParent();
- }
- // Remove the (now dead) store and alloca.
- Info.OnlyStore->eraseFromParent();
- LBI.deleteValue(Info.OnlyStore);
-
- if (AST)
- AST->deleteValue(AI);
- AI->eraseFromParent();
- LBI.deleteValue(AI);
-
+ if (rewriteSingleStoreAlloca(AI, Info, LBI, DT, AST)) {
// The alloca has been processed, move on.
RemoveFromAllocasList(AllocaNum);
-
++NumSingleStore;
continue;
}
// If the alloca is only read and written in one basic block, just perform a
// linear sweep over the block to eliminate it.
if (Info.OnlyUsedInOneBlock) {
- PromoteSingleBlockAlloca(AI, Info, LBI);
-
- // Finally, after the scan, check to see if the stores are all that is
- // left.
- if (Info.UsingBlocks.empty()) {
-
- // Remove the (now dead) stores and alloca.
- while (!AI->use_empty()) {
- StoreInst *SI = cast<StoreInst>(AI->use_back());
- // Record debuginfo for the store before removing it.
- if (DbgDeclareInst *DDI = Info.DbgDeclare) {
- if (!DIB)
- DIB = new DIBuilder(*SI->getParent()->getParent()->getParent());
- ConvertDebugDeclareToDebugValue(DDI, SI, *DIB);
- }
- SI->eraseFromParent();
- LBI.deleteValue(SI);
- }
-
- if (AST)
- AST->deleteValue(AI);
- AI->eraseFromParent();
- LBI.deleteValue(AI);
-
- // The alloca has been processed, move on.
- RemoveFromAllocasList(AllocaNum);
-
- // The alloca's debuginfo can be removed as well.
- if (DbgDeclareInst *DDI = Info.DbgDeclare)
- DDI->eraseFromParent();
+ promoteSingleBlockAlloca(AI, Info, LBI, AST);
- ++NumLocalPromoted;
- continue;
- }
- }
-
- // If we haven't computed dominator tree levels, do so now.
- if (DomLevels.empty()) {
- SmallVector<DomTreeNode *, 32> Worklist;
-
- DomTreeNode *Root = DT.getRootNode();
- DomLevels[Root] = 0;
- Worklist.push_back(Root);
-
- while (!Worklist.empty()) {
- DomTreeNode *Node = Worklist.pop_back_val();
- unsigned ChildLevel = DomLevels[Node] + 1;
- for (DomTreeNode::iterator CI = Node->begin(), CE = Node->end();
- CI != CE; ++CI) {
- DomLevels[*CI] = ChildLevel;
- Worklist.push_back(*CI);
- }
- }
+ // The alloca has been processed, move on.
+ RemoveFromAllocasList(AllocaNum);
+ continue;
}
// If we haven't computed a numbering for the BB's in the function, do so
// now.
if (BBNumbers.empty()) {
unsigned ID = 0;
- for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
- BBNumbers[I] = ID++;
+ for (auto &BB : F)
+ BBNumbers[&BB] = ID++;
}
// If we have an AST to keep updated, remember some pointer value that is
// 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 nodes.
- DetermineInsertionPoint(AI, AllocaNum, Info);
+
+
+ // Unique the set of defining blocks for efficient lookup.
+ SmallPtrSet<BasicBlock *, 32> DefBlocks;
+ DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end());
+
+ // Determine which blocks the value is live in. These are blocks which lead
+ // to uses.
+ SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
+ ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks);
+
+ // 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 nodes.
+ IDF.setLiveInBlocks(LiveInBlocks);
+ IDF.setDefiningBlocks(DefBlocks);
+ SmallVector<BasicBlock *, 32> PHIBlocks;
+ IDF.calculate(PHIBlocks);
+ if (PHIBlocks.size() > 1)
+ std::sort(PHIBlocks.begin(), PHIBlocks.end(),
+ [this](BasicBlock *A, BasicBlock *B) {
+ return BBNumbers.lookup(A) < BBNumbers.lookup(B);
+ });
+
+ unsigned CurrentVersion = 0;
+ for (unsigned i = 0, e = PHIBlocks.size(); i != e; ++i)
+ QueuePhiNode(PHIBlocks[i], AllocaNum, CurrentVersion);
}
if (Allocas.empty())
// 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());
A->eraseFromParent();
}
+ const DataLayout &DL = F.getParent()->getDataLayout();
+
// Remove alloca's dbg.declare instrinsics from the function.
for (unsigned i = 0, e = AllocaDbgDeclares.size(); i != e; ++i)
if (DbgDeclareInst *DDI = AllocaDbgDeclares[i])
// 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, DL, nullptr, &DT, AC)) {
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
// The block really is live in here, insert it into the set. If already in
// the set, then it has already been processed.
- if (!LiveInBlocks.insert(BB))
+ if (!LiveInBlocks.insert(BB).second)
continue;
// Since the value is live into BB, it is either defined in a predecessor or
}
}
-/// 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
-/// nodes.
-void PromoteMem2Reg::DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum,
- AllocaInfo &Info) {
- // Unique the set of defining blocks for efficient lookup.
- SmallPtrSet<BasicBlock *, 32> DefBlocks;
- DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end());
-
- // Determine which blocks the value is live in. These are blocks which lead
- // to uses.
- SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
- ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks);
-
- // 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;
- IDFPriorityQueue PQ;
-
- for (SmallPtrSet<BasicBlock *, 32>::const_iterator I = DefBlocks.begin(),
- E = DefBlocks.end();
- I != E; ++I) {
- if (DomTreeNode *Node = DT.getNode(*I))
- PQ.push(std::make_pair(Node, DomLevels[Node]));
- }
-
- SmallVector<std::pair<unsigned, BasicBlock *>, 32> DFBlocks;
- SmallPtrSet<DomTreeNode *, 32> Visited;
- SmallVector<DomTreeNode *, 32> Worklist;
- while (!PQ.empty()) {
- DomTreeNodePair RootPair = PQ.top();
- PQ.pop();
- DomTreeNode *Root = RootPair.first;
- unsigned RootLevel = RootPair.second;
-
- // Walk all dominator tree children of Root, inspecting their CFG edges with
- // targets elsewhere on the dominator tree. Only targets whose level is at
- // most Root's level are added to the iterated dominance frontier of the
- // definition set.
-
- Worklist.clear();
- Worklist.push_back(Root);
-
- while (!Worklist.empty()) {
- DomTreeNode *Node = Worklist.pop_back_val();
- BasicBlock *BB = Node->getBlock();
-
- for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE;
- ++SI) {
- DomTreeNode *SuccNode = DT.getNode(*SI);
-
- // Quickly skip all CFG edges that are also dominator tree edges instead
- // of catching them below.
- if (SuccNode->getIDom() == Node)
- continue;
-
- unsigned SuccLevel = DomLevels[SuccNode];
- if (SuccLevel > RootLevel)
- continue;
-
- if (!Visited.insert(SuccNode))
- continue;
-
- BasicBlock *SuccBB = SuccNode->getBlock();
- if (!LiveInBlocks.count(SuccBB))
- continue;
-
- DFBlocks.push_back(std::make_pair(BBNumbers[SuccBB], SuccBB));
- if (!DefBlocks.count(SuccBB))
- PQ.push(std::make_pair(SuccNode, SuccLevel));
- }
-
- for (DomTreeNode::iterator CI = Node->begin(), CE = Node->end(); CI != CE;
- ++CI) {
- if (!Visited.count(*CI))
- Worklist.push_back(*CI);
- }
- }
- }
-
- if (DFBlocks.size() > 1)
- std::sort(DFBlocks.begin(), DFBlocks.end());
-
- unsigned CurrentVersion = 0;
- for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i)
- QueuePhiNode(DFBlocks[i].second, AllocaNum, CurrentVersion);
-}
-
-/// 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.
-void PromoteMem2Reg::RewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info,
- LargeBlockInfo &LBI) {
- StoreInst *OnlyStore = Info.OnlyStore;
- bool StoringGlobalVal = !isa<Instruction>(OnlyStore->getOperand(0));
- BasicBlock *StoreBB = OnlyStore->getParent();
- int StoreIndex = -1;
-
- // 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;) {
- Instruction *UserInst = cast<Instruction>(*UI++);
- if (!isa<LoadInst>(UserInst)) {
- assert(UserInst == OnlyStore && "Should only have load/stores");
- continue;
- }
- LoadInst *LI = cast<LoadInst>(UserInst);
-
- // Okay, if we have a load from the alloca, we want to replace it with the
- // only value stored to the alloca. We can do this if the value is
- // dominated by the store. If not, we use the rest of the mem2reg machinery
- // to insert the phi nodes as needed.
- if (!StoringGlobalVal) { // Non-instructions are always dominated.
- if (LI->getParent() == StoreBB) {
- // If we have a use that is in the same block as the store, compare the
- // indices of the two instructions to see which one came first. If the
- // load came before the store, we can't handle it.
- if (StoreIndex == -1)
- StoreIndex = LBI.getInstructionIndex(OnlyStore);
-
- if (unsigned(StoreIndex) > LBI.getInstructionIndex(LI)) {
- // Can't handle this load, bail out.
- Info.UsingBlocks.push_back(StoreBB);
- continue;
- }
-
- } else if (LI->getParent() != StoreBB &&
- !dominates(StoreBB, LI->getParent())) {
- // If the load and store are in different blocks, use BB dominance to
- // check their relationships. If the store doesn't dom the use, bail
- // out.
- Info.UsingBlocks.push_back(LI->getParent());
- continue;
- }
- }
-
- // Otherwise, we *can* safely rewrite this load.
- Value *ReplVal = OnlyStore->getOperand(0);
- // If the replacement value is the load, this must occur in unreachable
- // code.
- if (ReplVal == LI)
- ReplVal = UndefValue::get(LI->getType());
- LI->replaceAllUsesWith(ReplVal);
- if (AST && LI->getType()->isPointerTy())
- AST->deleteValue(LI);
- LI->eraseFromParent();
- LBI.deleteValue(LI);
- }
-}
-
-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
-/// using the Alloca.
-///
-/// If we cannot promote this alloca (because it is read before it is written),
-/// return true. This is necessary in cases where, due to control flow, the
-/// alloca is potentially undefined on some control flow paths. e.g. code like
-/// this is potentially correct:
-///
-/// for (...) { if (c) { A = undef; undef = B; } }
-///
-/// ... so long as A is not used before undef is set.
-void PromoteMem2Reg::PromoteSingleBlockAlloca(AllocaInst *AI, AllocaInfo &Info,
- LargeBlockInfo &LBI) {
- // The trickiest case to handle is when we have large blocks. Because of this,
- // this code is optimized assuming that large blocks happen. This does not
- // significantly pessimize the small block case. This uses LargeBlockInfo to
- // make it efficient to get the index of various operations in the block.
-
- // Clear out UsingBlocks. We will reconstruct it here if needed.
- Info.UsingBlocks.clear();
-
- // Walk the use-def list of the alloca, getting the locations of all stores.
- 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))
- StoresByIndex.push_back(std::make_pair(LBI.getInstructionIndex(SI), SI));
-
- // If there are no stores to the alloca, just replace any loads with undef.
- if (StoresByIndex.empty()) {
- for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;)
- if (LoadInst *LI = dyn_cast<LoadInst>(*UI++)) {
- LI->replaceAllUsesWith(UndefValue::get(LI->getType()));
- if (AST && LI->getType()->isPointerTy())
- AST->deleteValue(LI);
- LBI.deleteValue(LI);
- LI->eraseFromParent();
- }
- return;
- }
-
- // Sort the stores by their index, making it efficient to do a lookup with a
- // binary search.
- std::sort(StoresByIndex.begin(), StoresByIndex.end());
-
- // 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;) {
- LoadInst *LI = dyn_cast<LoadInst>(*UI++);
- if (!LI)
- continue;
-
- unsigned LoadIdx = LBI.getInstructionIndex(LI);
-
- // Find the nearest store that has a lower than this load.
- StoresByIndexTy::iterator I = std::lower_bound(
- StoresByIndex.begin(), StoresByIndex.end(),
- std::pair<unsigned, StoreInst *>(LoadIdx, static_cast<StoreInst *>(0)),
- StoreIndexSearchPredicate());
-
- // If there is no store before this load, then we can't promote this load.
- if (I == StoresByIndex.begin()) {
- // Can't handle this load, bail out.
- Info.UsingBlocks.push_back(LI->getParent());
- continue;
- }
-
- // Otherwise, there was a store before this load, the load takes its value.
- --I;
- LI->replaceAllUsesWith(I->second->getOperand(0));
- if (AST && LI->getType()->isPointerTy())
- AST->deleteValue(LI);
- LI->eraseFromParent();
- LBI.deleteValue(LI);
- }
-}
-
/// \brief Queue a phi-node to be added to a basic-block for a specific Alloca.
///
/// Returns true if there wasn't already a phi-node for that variable
// operands so far. Remember this count.
unsigned NewPHINumOperands = APN->getNumOperands();
- unsigned NumEdges = 0;
- for (succ_iterator I = succ_begin(Pred), E = succ_end(Pred); I != E; ++I)
- if (*I == BB)
- ++NumEdges;
+ unsigned NumEdges = std::count(succ_begin(Pred), succ_end(Pred), BB);
assert(NumEdges && "Must be at least one edge from Pred to BB!");
// Add entries for all the phis.
// 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
}
// Don't revisit blocks.
- if (!Visited.insert(BB))
+ if (!Visited.insert(BB).second)
return;
for (BasicBlock::iterator II = BB->begin(); !isa<TerminatorInst>(II);) {
// what value were we writing?
IncomingVals[ai->second] = SI->getOperand(0);
// Record debuginfo for the store before removing it.
- if (DbgDeclareInst *DDI = AllocaDbgDeclares[ai->second]) {
- if (!DIB)
- DIB = new DIBuilder(*SI->getParent()->getParent()->getParent());
- ConvertDebugDeclareToDebugValue(DDI, SI, *DIB);
- }
+ if (DbgDeclareInst *DDI = AllocaDbgDeclares[ai->second])
+ ConvertDebugDeclareToDebugValue(DDI, SI, DIB);
BB->getInstList().erase(SI);
}
}
++I;
for (; I != E; ++I)
- if (VisitedSuccs.insert(*I))
+ if (VisitedSuccs.insert(*I).second)
Worklist.push_back(RenamePassData(*I, Pred, IncomingVals));
goto NextIteration;
}
-void llvm::PromoteMemToReg(const std::vector<AllocaInst *> &Allocas,
- DominatorTree &DT, AliasSetTracker *AST) {
+void llvm::PromoteMemToReg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT,
+ AliasSetTracker *AST, AssumptionCache *AC) {
// If there is nothing to do, bail out...
if (Allocas.empty())
return;
- PromoteMem2Reg(Allocas, DT, AST).run();
+ PromoteMem2Reg(Allocas, DT, AST, AC).run();
}
projects / oota-llvm.git / blobdiff