summaryrefslogtreecommitdiffstats
path: root/llvm/lib
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib')
-rw-r--r--llvm/lib/Transforms/Scalar/GVN.cpp481
1 files changed, 240 insertions, 241 deletions
diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp
index 6db5e348de9..859f14ed024 100644
--- a/llvm/lib/Transforms/Scalar/GVN.cpp
+++ b/llvm/lib/Transforms/Scalar/GVN.cpp
@@ -511,272 +511,271 @@ void ValueTable::verifyRemoved(const Value *V) const {
//===----------------------------------------------------------------------===//
namespace {
- class GVN;
- /// Represents a particular available value that we know how to materialize.
- /// Materialization of an AvailableValue never fails. An AvailableValue is
- /// implicitly associated with a rematerialization point which is the
- /// location of the instruction from which it was formed.
- struct AvailableValue {
- enum ValType {
- SimpleVal, // A simple offsetted value that is accessed.
- LoadVal, // A value produced by a load.
- MemIntrin, // A memory intrinsic which is loaded from.
- UndefVal // A UndefValue representing a value from dead block (which
- // is not yet physically removed from the CFG).
- };
-
- /// V - The value that is live out of the block.
- PointerIntPair<Value *, 2, ValType> Val;
-
- /// Offset - The byte offset in Val that is interesting for the load query.
- unsigned Offset;
-
- static AvailableValue get(Value *V,
- unsigned Offset = 0) {
- AvailableValue Res;
- Res.Val.setPointer(V);
- Res.Val.setInt(SimpleVal);
- Res.Offset = Offset;
- return Res;
- }
-
- static AvailableValue getMI(MemIntrinsic *MI,
- unsigned Offset = 0) {
- AvailableValue Res;
- Res.Val.setPointer(MI);
- Res.Val.setInt(MemIntrin);
- Res.Offset = Offset;
- return Res;
- }
-
- static AvailableValue getLoad(LoadInst *LI,
- unsigned Offset = 0) {
- AvailableValue Res;
- Res.Val.setPointer(LI);
- Res.Val.setInt(LoadVal);
- Res.Offset = Offset;
- return Res;
- }
+class GVN;
+
+/// Represents a particular available value that we know how to materialize.
+/// Materialization of an AvailableValue never fails. An AvailableValue is
+/// implicitly associated with a rematerialization point which is the
+/// location of the instruction from which it was formed.
+struct AvailableValue {
+ enum ValType {
+ SimpleVal, // A simple offsetted value that is accessed.
+ LoadVal, // A value produced by a load.
+ MemIntrin, // A memory intrinsic which is loaded from.
+ UndefVal // A UndefValue representing a value from dead block (which
+ // is not yet physically removed from the CFG).
+ };
- static AvailableValue getUndef() {
- AvailableValue Res;
- Res.Val.setPointer(nullptr);
- Res.Val.setInt(UndefVal);
- Res.Offset = 0;
- return Res;
- }
+ /// V - The value that is live out of the block.
+ PointerIntPair<Value *, 2, ValType> Val;
- bool isSimpleValue() const { return Val.getInt() == SimpleVal; }
- bool isCoercedLoadValue() const { return Val.getInt() == LoadVal; }
- bool isMemIntrinValue() const { return Val.getInt() == MemIntrin; }
- bool isUndefValue() const { return Val.getInt() == UndefVal; }
-
- Value *getSimpleValue() const {
- assert(isSimpleValue() && "Wrong accessor");
- return Val.getPointer();
- }
-
- LoadInst *getCoercedLoadValue() const {
- assert(isCoercedLoadValue() && "Wrong accessor");
- return cast<LoadInst>(Val.getPointer());
- }
-
- MemIntrinsic *getMemIntrinValue() const {
- assert(isMemIntrinValue() && "Wrong accessor");
- return cast<MemIntrinsic>(Val.getPointer());
- }
+ /// Offset - The byte offset in Val that is interesting for the load query.
+ unsigned Offset;
- /// Emit code at the specified insertion point to adjust the value defined
- /// here to the specified type. This handles various coercion cases.
- Value *MaterializeAdjustedValue(LoadInst *LI, Instruction *InsertPt,
- GVN &gvn) const;
- };
+ static AvailableValue get(Value *V, unsigned Offset = 0) {
+ AvailableValue Res;
+ Res.Val.setPointer(V);
+ Res.Val.setInt(SimpleVal);
+ Res.Offset = Offset;
+ return Res;
+ }
- /// Represents an AvailableValue which can be rematerialized at the end of
- /// the associated BasicBlock.
- struct AvailableValueInBlock {
- /// BB - The basic block in question.
- BasicBlock *BB;
+ static AvailableValue getMI(MemIntrinsic *MI, unsigned Offset = 0) {
+ AvailableValue Res;
+ Res.Val.setPointer(MI);
+ Res.Val.setInt(MemIntrin);
+ Res.Offset = Offset;
+ return Res;
+ }
- /// AV - The actual available value
- AvailableValue AV;
+ static AvailableValue getLoad(LoadInst *LI, unsigned Offset = 0) {
+ AvailableValue Res;
+ Res.Val.setPointer(LI);
+ Res.Val.setInt(LoadVal);
+ Res.Offset = Offset;
+ return Res;
+ }
- static AvailableValueInBlock get(BasicBlock *BB, AvailableValue &&AV) {
- AvailableValueInBlock Res;
- Res.BB = BB;
- Res.AV = std::move(AV);
- return Res;
- }
+ static AvailableValue getUndef() {
+ AvailableValue Res;
+ Res.Val.setPointer(nullptr);
+ Res.Val.setInt(UndefVal);
+ Res.Offset = 0;
+ return Res;
+ }
- static AvailableValueInBlock get(BasicBlock *BB, Value *V,
- unsigned Offset = 0) {
- return get(BB, AvailableValue::get(V, Offset));
- }
- static AvailableValueInBlock getUndef(BasicBlock *BB) {
- return get(BB, AvailableValue::getUndef());
- }
-
- /// Emit code at the end of this block to adjust the value defined here to
- /// the specified type. This handles various coercion cases.
- Value *MaterializeAdjustedValue(LoadInst *LI, GVN &gvn) const {
- return AV.MaterializeAdjustedValue(LI, BB->getTerminator(), gvn);
- }
- };
+ bool isSimpleValue() const { return Val.getInt() == SimpleVal; }
+ bool isCoercedLoadValue() const { return Val.getInt() == LoadVal; }
+ bool isMemIntrinValue() const { return Val.getInt() == MemIntrin; }
+ bool isUndefValue() const { return Val.getInt() == UndefVal; }
- class GVN : public FunctionPass {
- bool NoLoads;
- MemoryDependenceResults *MD;
- DominatorTree *DT;
- const TargetLibraryInfo *TLI;
- AssumptionCache *AC;
- SetVector<BasicBlock *> DeadBlocks;
-
- ValueTable VN;
-
- /// A mapping from value numbers to lists of Value*'s that
- /// have that value number. Use findLeader to query it.
- struct LeaderTableEntry {
- Value *Val;
- const BasicBlock *BB;
- LeaderTableEntry *Next;
- };
- DenseMap<uint32_t, LeaderTableEntry> LeaderTable;
- BumpPtrAllocator TableAllocator;
-
- // Block-local map of equivalent values to their leader, does not
- // propagate to any successors. Entries added mid-block are applied
- // to the remaining instructions in the block.
- SmallMapVector<llvm::Value *, llvm::Constant *, 4> ReplaceWithConstMap;
- SmallVector<Instruction*, 8> InstrsToErase;
-
- typedef SmallVector<NonLocalDepResult, 64> LoadDepVect;
- typedef SmallVector<AvailableValueInBlock, 64> AvailValInBlkVect;
- typedef SmallVector<BasicBlock*, 64> UnavailBlkVect;
+ Value *getSimpleValue() const {
+ assert(isSimpleValue() && "Wrong accessor");
+ return Val.getPointer();
+ }
- public:
- static char ID; // Pass identification, replacement for typeid
- explicit GVN(bool noloads = false)
- : FunctionPass(ID), NoLoads(noloads), MD(nullptr) {
- initializeGVNPass(*PassRegistry::getPassRegistry());
- }
+ LoadInst *getCoercedLoadValue() const {
+ assert(isCoercedLoadValue() && "Wrong accessor");
+ return cast<LoadInst>(Val.getPointer());
+ }
- bool runOnFunction(Function &F) override;
+ MemIntrinsic *getMemIntrinValue() const {
+ assert(isMemIntrinValue() && "Wrong accessor");
+ return cast<MemIntrinsic>(Val.getPointer());
+ }
- /// This removes the specified instruction from
- /// our various maps and marks it for deletion.
- void markInstructionForDeletion(Instruction *I) {
- VN.erase(I);
- InstrsToErase.push_back(I);
- }
+ /// Emit code at the specified insertion point to adjust the value defined
+ /// here to the specified type. This handles various coercion cases.
+ Value *MaterializeAdjustedValue(LoadInst *LI, Instruction *InsertPt,
+ GVN &gvn) const;
+};
- DominatorTree &getDominatorTree() const { return *DT; }
- AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
- MemoryDependenceResults &getMemDep() const { return *MD; }
- private:
- /// Push a new Value to the LeaderTable onto the list for its value number.
- void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
- LeaderTableEntry &Curr = LeaderTable[N];
- if (!Curr.Val) {
- Curr.Val = V;
- Curr.BB = BB;
- return;
- }
+/// Represents an AvailableValue which can be rematerialized at the end of
+/// the associated BasicBlock.
+struct AvailableValueInBlock {
+ /// BB - The basic block in question.
+ BasicBlock *BB;
- LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
- Node->Val = V;
- Node->BB = BB;
- Node->Next = Curr.Next;
- Curr.Next = Node;
- }
+ /// AV - The actual available value
+ AvailableValue AV;
- /// Scan the list of values corresponding to a given
- /// value number, and remove the given instruction if encountered.
- void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
- LeaderTableEntry* Prev = nullptr;
- LeaderTableEntry* Curr = &LeaderTable[N];
+ static AvailableValueInBlock get(BasicBlock *BB, AvailableValue &&AV) {
+ AvailableValueInBlock Res;
+ Res.BB = BB;
+ Res.AV = std::move(AV);
+ return Res;
+ }
- while (Curr && (Curr->Val != I || Curr->BB != BB)) {
- Prev = Curr;
- Curr = Curr->Next;
- }
+ static AvailableValueInBlock get(BasicBlock *BB, Value *V,
+ unsigned Offset = 0) {
+ return get(BB, AvailableValue::get(V, Offset));
+ }
+ static AvailableValueInBlock getUndef(BasicBlock *BB) {
+ return get(BB, AvailableValue::getUndef());
+ }
+
+ /// Emit code at the end of this block to adjust the value defined here to
+ /// the specified type. This handles various coercion cases.
+ Value *MaterializeAdjustedValue(LoadInst *LI, GVN &gvn) const {
+ return AV.MaterializeAdjustedValue(LI, BB->getTerminator(), gvn);
+ }
+};
- if (!Curr)
- return;
+class GVN : public FunctionPass {
+ bool NoLoads;
+ MemoryDependenceResults *MD;
+ DominatorTree *DT;
+ const TargetLibraryInfo *TLI;
+ AssumptionCache *AC;
+ SetVector<BasicBlock *> DeadBlocks;
+
+ ValueTable VN;
+
+ /// A mapping from value numbers to lists of Value*'s that
+ /// have that value number. Use findLeader to query it.
+ struct LeaderTableEntry {
+ Value *Val;
+ const BasicBlock *BB;
+ LeaderTableEntry *Next;
+ };
+ DenseMap<uint32_t, LeaderTableEntry> LeaderTable;
+ BumpPtrAllocator TableAllocator;
- if (Prev) {
- Prev->Next = Curr->Next;
- } else {
- if (!Curr->Next) {
- Curr->Val = nullptr;
- Curr->BB = nullptr;
- } else {
- LeaderTableEntry* Next = Curr->Next;
- Curr->Val = Next->Val;
- Curr->BB = Next->BB;
- Curr->Next = Next->Next;
- }
- }
+ // Block-local map of equivalent values to their leader, does not
+ // propagate to any successors. Entries added mid-block are applied
+ // to the remaining instructions in the block.
+ SmallMapVector<llvm::Value *, llvm::Constant *, 4> ReplaceWithConstMap;
+ SmallVector<Instruction *, 8> InstrsToErase;
+
+ typedef SmallVector<NonLocalDepResult, 64> LoadDepVect;
+ typedef SmallVector<AvailableValueInBlock, 64> AvailValInBlkVect;
+ typedef SmallVector<BasicBlock *, 64> UnavailBlkVect;
+
+public:
+ static char ID; // Pass identification, replacement for typeid
+ explicit GVN(bool noloads = false)
+ : FunctionPass(ID), NoLoads(noloads), MD(nullptr) {
+ initializeGVNPass(*PassRegistry::getPassRegistry());
+ }
+
+ bool runOnFunction(Function &F) override;
+
+ /// This removes the specified instruction from
+ /// our various maps and marks it for deletion.
+ void markInstructionForDeletion(Instruction *I) {
+ VN.erase(I);
+ InstrsToErase.push_back(I);
+ }
+
+ DominatorTree &getDominatorTree() const { return *DT; }
+ AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
+ MemoryDependenceResults &getMemDep() const { return *MD; }
+
+private:
+ /// Push a new Value to the LeaderTable onto the list for its value number.
+ void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
+ LeaderTableEntry &Curr = LeaderTable[N];
+ if (!Curr.Val) {
+ Curr.Val = V;
+ Curr.BB = BB;
+ return;
}
- // List of critical edges to be split between iterations.
- SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit;
+ LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
+ Node->Val = V;
+ Node->BB = BB;
+ Node->Next = Curr.Next;
+ Curr.Next = Node;
+ }
- // This transformation requires dominator postdominator info
- void getAnalysisUsage(AnalysisUsage &AU) const override {
- AU.addRequired<AssumptionCacheTracker>();
- AU.addRequired<DominatorTreeWrapperPass>();
- AU.addRequired<TargetLibraryInfoWrapperPass>();
- if (!NoLoads)
- AU.addRequired<MemoryDependenceWrapperPass>();
- AU.addRequired<AAResultsWrapperPass>();
+ /// Scan the list of values corresponding to a given
+ /// value number, and remove the given instruction if encountered.
+ void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
+ LeaderTableEntry *Prev = nullptr;
+ LeaderTableEntry *Curr = &LeaderTable[N];
- AU.addPreserved<DominatorTreeWrapperPass>();
- AU.addPreserved<GlobalsAAWrapperPass>();
+ while (Curr && (Curr->Val != I || Curr->BB != BB)) {
+ Prev = Curr;
+ Curr = Curr->Next;
}
+ if (!Curr)
+ return;
- // Helper functions of redundant load elimination
- bool processLoad(LoadInst *L);
- bool processNonLocalLoad(LoadInst *L);
- bool processAssumeIntrinsic(IntrinsicInst *II);
- /// Given a local dependency (Def or Clobber) determine if a value is
- /// available for the load. Returns true if an value is known to be
- /// available and populates Res. Returns false otherwise.
- bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
- Value *Address, AvailableValue &Res);
- /// Given a list of non-local dependencies, determine if a value is
- /// available for the load in each specified block. If it is, add it to
- /// ValuesPerBlock. If not, add it to UnavailableBlocks.
- void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
- AvailValInBlkVect &ValuesPerBlock,
- UnavailBlkVect &UnavailableBlocks);
- bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
- UnavailBlkVect &UnavailableBlocks);
-
- // Other helper routines
- bool processInstruction(Instruction *I);
- bool processBlock(BasicBlock *BB);
- void dump(DenseMap<uint32_t, Value*> &d);
- bool iterateOnFunction(Function &F);
- bool performPRE(Function &F);
- bool performScalarPRE(Instruction *I);
- bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
- unsigned int ValNo);
- Value *findLeader(const BasicBlock *BB, uint32_t num);
- void cleanupGlobalSets();
- void verifyRemoved(const Instruction *I) const;
- bool splitCriticalEdges();
- BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
- bool replaceOperandsWithConsts(Instruction *I) const;
- bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
- bool DominatesByEdge);
- bool processFoldableCondBr(BranchInst *BI);
- void addDeadBlock(BasicBlock *BB);
- void assignValNumForDeadCode();
- };
+ if (Prev) {
+ Prev->Next = Curr->Next;
+ } else {
+ if (!Curr->Next) {
+ Curr->Val = nullptr;
+ Curr->BB = nullptr;
+ } else {
+ LeaderTableEntry *Next = Curr->Next;
+ Curr->Val = Next->Val;
+ Curr->BB = Next->BB;
+ Curr->Next = Next->Next;
+ }
+ }
+ }
- char GVN::ID = 0;
-}
+ // List of critical edges to be split between iterations.
+ SmallVector<std::pair<TerminatorInst *, unsigned>, 4> toSplit;
+
+ // This transformation requires dominator postdominator info
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
+ AU.addRequired<AssumptionCacheTracker>();
+ AU.addRequired<DominatorTreeWrapperPass>();
+ AU.addRequired<TargetLibraryInfoWrapperPass>();
+ if (!NoLoads)
+ AU.addRequired<MemoryDependenceWrapperPass>();
+ AU.addRequired<AAResultsWrapperPass>();
+
+ AU.addPreserved<DominatorTreeWrapperPass>();
+ AU.addPreserved<GlobalsAAWrapperPass>();
+ }
+
+ // Helper functions of redundant load elimination
+ bool processLoad(LoadInst *L);
+ bool processNonLocalLoad(LoadInst *L);
+ bool processAssumeIntrinsic(IntrinsicInst *II);
+ /// Given a local dependency (Def or Clobber) determine if a value is
+ /// available for the load. Returns true if an value is known to be
+ /// available and populates Res. Returns false otherwise.
+ bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
+ Value *Address, AvailableValue &Res);
+ /// Given a list of non-local dependencies, determine if a value is
+ /// available for the load in each specified block. If it is, add it to
+ /// ValuesPerBlock. If not, add it to UnavailableBlocks.
+ void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
+ AvailValInBlkVect &ValuesPerBlock,
+ UnavailBlkVect &UnavailableBlocks);
+ bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
+ UnavailBlkVect &UnavailableBlocks);
+
+ // Other helper routines
+ bool processInstruction(Instruction *I);
+ bool processBlock(BasicBlock *BB);
+ void dump(DenseMap<uint32_t, Value *> &d);
+ bool iterateOnFunction(Function &F);
+ bool performPRE(Function &F);
+ bool performScalarPRE(Instruction *I);
+ bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
+ unsigned int ValNo);
+ Value *findLeader(const BasicBlock *BB, uint32_t num);
+ void cleanupGlobalSets();
+ void verifyRemoved(const Instruction *I) const;
+ bool splitCriticalEdges();
+ BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
+ bool replaceOperandsWithConsts(Instruction *I) const;
+ bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
+ bool DominatesByEdge);
+ bool processFoldableCondBr(BranchInst *BI);
+ void addDeadBlock(BasicBlock *BB);
+ void assignValNumForDeadCode();
+};
+
+char GVN::ID = 0;
+
+} // End anonymous namespace.
// The public interface to this file...
FunctionPass *llvm::createGVNPass(bool NoLoads) {
OpenPOWER on IntegriCloud