diff --git a/llvm/include/llvm/Analysis/AliasAnalysis.h b/llvm/include/llvm/Analysis/AliasAnalysis.h
--- a/llvm/include/llvm/Analysis/AliasAnalysis.h
+++ b/llvm/include/llvm/Analysis/AliasAnalysis.h
@@ -59,7 +59,6 @@
class BasicAAResult;
class BasicBlock;
class DominatorTree;
-class OrderedBasicBlock;
class Value;
/// The possible results of an alias query.
@@ -689,19 +688,16 @@
/// Return information about whether a particular call site modifies
/// or reads the specified memory location \p MemLoc before instruction \p I
- /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
- /// instruction ordering queries inside the BasicBlock containing \p I.
+ /// in a BasicBlock.
/// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being
/// set.
ModRefInfo callCapturesBefore(const Instruction *I,
- const MemoryLocation &MemLoc, DominatorTree *DT,
- OrderedBasicBlock *OBB = nullptr);
+ const MemoryLocation &MemLoc, DominatorTree *DT);
/// A convenience wrapper to synthesize a memory location.
ModRefInfo callCapturesBefore(const Instruction *I, const Value *P,
- LocationSize Size, DominatorTree *DT,
- OrderedBasicBlock *OBB = nullptr) {
- return callCapturesBefore(I, MemoryLocation(P, Size), DT, OBB);
+ LocationSize Size, DominatorTree *DT) {
+ return callCapturesBefore(I, MemoryLocation(P, Size), DT);
}
/// @}
diff --git a/llvm/include/llvm/Analysis/CaptureTracking.h b/llvm/include/llvm/Analysis/CaptureTracking.h
--- a/llvm/include/llvm/Analysis/CaptureTracking.h
+++ b/llvm/include/llvm/Analysis/CaptureTracking.h
@@ -20,7 +20,6 @@
class DataLayout;
class Instruction;
class DominatorTree;
- class OrderedBasicBlock;
/// The default value for MaxUsesToExplore argument. It's relatively small to
/// keep the cost of analysis reasonable for clients like BasicAliasAnalysis,
@@ -53,14 +52,12 @@
/// it or not. The boolean StoreCaptures specified whether storing the value
/// (or part of it) into memory anywhere automatically counts as capturing it
/// or not. Captures by the provided instruction are considered if the
- /// final parameter is true. An ordered basic block in \p OBB could be used
- /// to speed up capture-tracker queries.
+ /// final parameter is true.
/// MaxUsesToExplore specifies how many uses should the analysis explore for
/// one value before giving up due too "too many uses".
bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
bool StoreCaptures, const Instruction *I,
const DominatorTree *DT, bool IncludeI = false,
- OrderedBasicBlock *OBB = nullptr,
unsigned MaxUsesToExplore = DefaultMaxUsesToExplore);
/// This callback is used in conjunction with PointerMayBeCaptured. In
diff --git a/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h b/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h
--- a/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ b/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -384,8 +384,7 @@
///
/// See the class comment for more details. It is illegal to call this on
/// non-memory instructions.
- MemDepResult getDependency(Instruction *QueryInst,
- OrderedBasicBlock *OBB = nullptr);
+ MemDepResult getDependency(Instruction *QueryInst);
/// Perform a full dependency query for the specified call, returning the set
/// of blocks that the value is potentially live across.
@@ -451,14 +450,12 @@
BasicBlock::iterator ScanIt,
BasicBlock *BB,
Instruction *QueryInst = nullptr,
- unsigned *Limit = nullptr,
- OrderedBasicBlock *OBB = nullptr);
+ unsigned *Limit = nullptr);
MemDepResult
getSimplePointerDependencyFrom(const MemoryLocation &MemLoc, bool isLoad,
BasicBlock::iterator ScanIt, BasicBlock *BB,
- Instruction *QueryInst, unsigned *Limit,
- OrderedBasicBlock *OBB);
+ Instruction *QueryInst, unsigned *Limit);
/// This analysis looks for other loads and stores with invariant.group
/// metadata and the same pointer operand. Returns Unknown if it does not
diff --git a/llvm/include/llvm/Analysis/OrderedBasicBlock.h b/llvm/include/llvm/Analysis/OrderedBasicBlock.h
deleted file mode 100644
--- a/llvm/include/llvm/Analysis/OrderedBasicBlock.h
+++ /dev/null
@@ -1,74 +0,0 @@
-//===- llvm/Analysis/OrderedBasicBlock.h --------------------- -*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// This file defines the OrderedBasicBlock class. OrderedBasicBlock maintains
-// an interface where clients can query if one instruction comes before another
-// in a BasicBlock. Since BasicBlock currently lacks a reliable way to query
-// relative position between instructions one can use OrderedBasicBlock to do
-// such queries. OrderedBasicBlock is lazily built on a source BasicBlock and
-// maintains an internal Instruction -> Position map. A OrderedBasicBlock
-// instance should be discarded whenever the source BasicBlock changes.
-//
-// It's currently used by the CaptureTracker in order to find relative
-// positions of a pair of instructions inside a BasicBlock.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_ORDEREDBASICBLOCK_H
-#define LLVM_ANALYSIS_ORDEREDBASICBLOCK_H
-
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/IR/BasicBlock.h"
-
-namespace llvm {
-
-class Instruction;
-class BasicBlock;
-
-class OrderedBasicBlock {
-private:
- /// Map a instruction to its position in a BasicBlock.
- SmallDenseMap<const Instruction *, unsigned, 32> NumberedInsts;
-
- /// Keep track of last instruction inserted into \p NumberedInsts.
- /// It speeds up queries for uncached instructions by providing a start point
- /// for new queries in OrderedBasicBlock::comesBefore.
- BasicBlock::const_iterator LastInstFound;
-
- /// The position/number to tag the next instruction to be found.
- unsigned NextInstPos;
-
- /// The source BasicBlock to map.
- const BasicBlock *BB;
-
- /// Given no cached results, find if \p A comes before \p B in \p BB.
- /// Cache and number out instruction while walking \p BB.
- bool comesBefore(const Instruction *A, const Instruction *B);
-
-public:
- OrderedBasicBlock(const BasicBlock *BasicB);
-
- /// Find out whether \p A dominates \p B, meaning whether \p A
- /// comes before \p B in \p BB. This is a simplification that considers
- /// cached instruction positions and ignores other basic blocks, being
- /// only relevant to compare relative instructions positions inside \p BB.
- /// Returns false for A == B.
- bool dominates(const Instruction *A, const Instruction *B);
-
- /// Remove \p from the ordering, if it is present.
- void eraseInstruction(const Instruction *I);
-
- /// Replace \p Old with \p New in the ordering. \p New is assigned the
- /// numbering of \p Old, so it must be inserted at the same position in the
- /// IR.
- void replaceInstruction(const Instruction *Old, const Instruction *New);
-};
-
-} // End llvm namespace
-
-#endif
diff --git a/llvm/include/llvm/Analysis/OrderedInstructions.h b/llvm/include/llvm/Analysis/OrderedInstructions.h
--- a/llvm/include/llvm/Analysis/OrderedInstructions.h
+++ b/llvm/include/llvm/Analysis/OrderedInstructions.h
@@ -9,10 +9,9 @@
// This file defines an efficient way to check for dominance relation between 2
// instructions.
//
-// This interface dispatches to appropriate dominance check given 2
-// instructions, i.e. in case the instructions are in the same basic block,
-// OrderedBasicBlock (with instruction numbering and caching) are used.
-// Otherwise, dominator tree is used.
+// FIXME: This is really just a convenience wrapper to check dominance between
+// two arbitrary instructions in different basic blocks. We should fold it into
+// DominatorTree, which is the more widely used interface.
//
//===----------------------------------------------------------------------===//
@@ -20,17 +19,12 @@
#define LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H
#include "llvm/ADT/DenseMap.h"
-#include "llvm/Analysis/OrderedBasicBlock.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Operator.h"
namespace llvm {
class OrderedInstructions {
- /// Used to check dominance for instructions in same basic block.
- mutable DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>>
- OBBMap;
-
/// The dominator tree of the parent function.
DominatorTree *DT;
@@ -51,12 +45,6 @@
/// or if the first instruction comes before the second in the same basic
/// block.
bool dfsBefore(const Instruction *, const Instruction *) const;
-
- /// Invalidate the OrderedBasicBlock cache when its basic block changes.
- /// i.e. If an instruction is deleted or added to the basic block, the user
- /// should call this function to invalidate the OrderedBasicBlock cache for
- /// this basic block.
- void invalidateBlock(const BasicBlock *BB) { OBBMap.erase(BB); }
};
} // end namespace llvm
diff --git a/llvm/include/llvm/IR/BasicBlock.h b/llvm/include/llvm/IR/BasicBlock.h
--- a/llvm/include/llvm/IR/BasicBlock.h
+++ b/llvm/include/llvm/IR/BasicBlock.h
@@ -402,7 +402,9 @@
/// Returns true if there are any uses of this basic block other than
/// direct branches, switches, etc. to it.
- bool hasAddressTaken() const { return getSubclassDataFromValue() != 0; }
+ bool hasAddressTaken() const {
+ return getBasicBlockBits().BlockAddressRefCount != 0;
+ }
/// Update all phi nodes in this basic block to refer to basic block \p New
/// instead of basic block \p Old.
@@ -437,16 +439,61 @@
Optional<uint64_t> getIrrLoopHeaderWeight() const;
+ /// Returns true if the Order field of child Instructions is valid.
+ bool isInstrOrderValid() const {
+ return getBasicBlockBits().InstrOrderValid;
+ }
+
+ /// Mark instruction ordering invalid. Done on every instruction insert.
+ void invalidateOrders() {
+ validateInstrOrdering();
+ BasicBlockBits Bits = getBasicBlockBits();
+ Bits.InstrOrderValid = false;
+ setBasicBlockBits(Bits);
+ }
+
+ /// Renumber instructions and mark the ordering as valid.
+ void renumberInstructions();
+
+ /// Returns false if the instruction ordering is incorrect in an debug build.
+ /// Always returns true when assertions are disabled. The method does not
+ /// assert internally so that we get better location info.
+ void validateInstrOrdering() const;
+
private:
+ /// Bitfield to help interpret the bits in Value::SubclassData.
+ struct BasicBlockBits {
+ unsigned short BlockAddressRefCount : 15;
+ unsigned short InstrOrderValid : 1;
+ };
+
+ /// Safely reinterpret the subclass data bits to a more useful form.
+ BasicBlockBits getBasicBlockBits() const {
+ static_assert(sizeof(BasicBlockBits) == sizeof(unsigned short),
+ "too many bits for Value::SubclassData");
+ unsigned short ValueData = getSubclassDataFromValue();
+ BasicBlockBits AsBits;
+ memcpy(&AsBits, &ValueData, sizeof(AsBits));
+ return AsBits;
+ }
+
+ /// Reinterpret our subclass bits and store them back into Value.
+ void setBasicBlockBits(BasicBlockBits AsBits) {
+ unsigned short D;
+ memcpy(&D, &AsBits, sizeof(D));
+ Value::setValueSubclassData(D);
+ }
+
/// Increment the internal refcount of the number of BlockAddresses
/// referencing this BasicBlock by \p Amt.
///
/// This is almost always 0, sometimes one possibly, but almost never 2, and
/// inconceivably 3 or more.
void AdjustBlockAddressRefCount(int Amt) {
- setValueSubclassData(getSubclassDataFromValue()+Amt);
- assert((int)(signed char)getSubclassDataFromValue() >= 0 &&
- "Refcount wrap-around");
+ BasicBlockBits Bits = getBasicBlockBits();
+ Bits.BlockAddressRefCount += Amt;
+ setBasicBlockBits(Bits);
+ assert(Bits.BlockAddressRefCount < 255 && "Refcount wrap-around");
}
/// Shadow Value::setValueSubclassData with a private forwarding method so
@@ -463,6 +510,12 @@
/// This assumes that \p It is not at the end of a block.
BasicBlock::iterator skipDebugIntrinsics(BasicBlock::iterator It);
+#ifdef NDEBUG
+/// In release builds, this is a no-op. For !NDEBUG builds, the checks are
+/// implemented in the .cpp file to avoid circular header deps.
+inline void Instruction::validateInstrOrdering() const {}
+#endif
+
} // end namespace llvm
#endif // LLVM_IR_BASICBLOCK_H
diff --git a/llvm/include/llvm/IR/Instruction.h b/llvm/include/llvm/IR/Instruction.h
--- a/llvm/include/llvm/IR/Instruction.h
+++ b/llvm/include/llvm/IR/Instruction.h
@@ -45,6 +45,10 @@
BasicBlock *Parent;
DebugLoc DbgLoc; // 'dbg' Metadata cache.
+ /// Relative order of this instruction in its parent basic block. Used for
+ /// O(1) local dominance checks between instructions.
+ mutable unsigned Order = 0;
+
enum {
/// This is a bit stored in the SubClassData field which indicates whether
/// this instruction has metadata attached to it or not.
@@ -117,6 +121,13 @@
/// the basic block that MovePos lives in, right after MovePos.
void moveAfter(Instruction *MovePos);
+ /// Given an instruction Other in the same basic block as this instruction,
+ /// return true if this instruction comes before Other. In this worst case,
+ /// this takes linear time in the number of instructions in the block. The
+ /// results are cached, so in common cases when the block remains unmodified,
+ /// it takes constant time.
+ bool comesBefore(const Instruction *Other) const;
+
//===--------------------------------------------------------------------===//
// Subclass classification.
//===--------------------------------------------------------------------===//
@@ -738,6 +749,7 @@
private:
friend class SymbolTableListTraits<Instruction>;
+ friend class BasicBlock; // For renumbering.
// Shadow Value::setValueSubclassData with a private forwarding method so that
// subclasses cannot accidentally use it.
diff --git a/llvm/lib/Analysis/AliasAnalysis.cpp b/llvm/lib/Analysis/AliasAnalysis.cpp
--- a/llvm/lib/Analysis/AliasAnalysis.cpp
+++ b/llvm/lib/Analysis/AliasAnalysis.cpp
@@ -630,16 +630,14 @@
/// Return information about whether a particular call site modifies
/// or reads the specified memory location \p MemLoc before instruction \p I
-/// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
-/// instruction-ordering queries inside the BasicBlock containing \p I.
+/// in a BasicBlock.
/// FIXME: this is really just shoring-up a deficiency in alias analysis.
/// BasicAA isn't willing to spend linear time determining whether an alloca
/// was captured before or after this particular call, while we are. However,
/// with a smarter AA in place, this test is just wasting compile time.
ModRefInfo AAResults::callCapturesBefore(const Instruction *I,
const MemoryLocation &MemLoc,
- DominatorTree *DT,
- OrderedBasicBlock *OBB) {
+ DominatorTree *DT) {
if (!DT)
return ModRefInfo::ModRef;
@@ -655,8 +653,7 @@
if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
/* StoreCaptures */ true, I, DT,
- /* include Object */ true,
- /* OrderedBasicBlock */ OBB))
+ /* include Object */ true))
return ModRefInfo::ModRef;
unsigned ArgNo = 0;
diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt
--- a/llvm/lib/Analysis/CMakeLists.txt
+++ b/llvm/lib/Analysis/CMakeLists.txt
@@ -70,7 +70,6 @@
ObjCARCAnalysisUtils.cpp
ObjCARCInstKind.cpp
OptimizationRemarkEmitter.cpp
- OrderedBasicBlock.cpp
OrderedInstructions.cpp
PHITransAddr.cpp
PhiValues.cpp
diff --git a/llvm/lib/Analysis/CaptureTracking.cpp b/llvm/lib/Analysis/CaptureTracking.cpp
--- a/llvm/lib/Analysis/CaptureTracking.cpp
+++ b/llvm/lib/Analysis/CaptureTracking.cpp
@@ -20,7 +20,6 @@
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CFG.h"
-#include "llvm/Analysis/OrderedBasicBlock.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
@@ -76,8 +75,8 @@
struct CapturesBefore : public CaptureTracker {
CapturesBefore(bool ReturnCaptures, const Instruction *I, const DominatorTree *DT,
- bool IncludeI, OrderedBasicBlock *IC)
- : OrderedBB(IC), BeforeHere(I), DT(DT),
+ bool IncludeI)
+ : BeforeHere(I), DT(DT),
ReturnCaptures(ReturnCaptures), IncludeI(IncludeI), Captured(false) {}
void tooManyUses() override { Captured = true; }
@@ -90,9 +89,7 @@
return true;
// Compute the case where both instructions are inside the same basic
- // block. Since instructions in the same BB as BeforeHere are numbered in
- // 'OrderedBB', avoid using 'dominates' and 'isPotentiallyReachable'
- // which are very expensive for large basic blocks.
+ // block.
if (BB == BeforeHere->getParent()) {
// 'I' dominates 'BeforeHere' => not safe to prune.
//
@@ -102,7 +99,7 @@
// UseBB == BB, avoid pruning.
if (isa<InvokeInst>(BeforeHere) || isa<PHINode>(I) || I == BeforeHere)
return false;
- if (!OrderedBB->dominates(BeforeHere, I))
+ if (!BeforeHere->comesBefore(I))
return false;
// 'BeforeHere' comes before 'I', it's safe to prune if we also
@@ -153,7 +150,6 @@
return true;
}
- OrderedBasicBlock *OrderedBB;
const Instruction *BeforeHere;
const DominatorTree *DT;
@@ -196,31 +192,23 @@
/// returning the value (or part of it) from the function counts as capturing
/// it or not. The boolean StoreCaptures specified whether storing the value
/// (or part of it) into memory anywhere automatically counts as capturing it
-/// or not. A ordered basic block \p OBB can be used in order to speed up
-/// queries about relative order among instructions in the same basic block.
+/// or not.
bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
bool StoreCaptures, const Instruction *I,
const DominatorTree *DT, bool IncludeI,
- OrderedBasicBlock *OBB,
unsigned MaxUsesToExplore) {
assert(!isa<GlobalValue>(V) &&
"It doesn't make sense to ask whether a global is captured.");
- bool UseNewOBB = OBB == nullptr;
if (!DT)
return PointerMayBeCaptured(V, ReturnCaptures, StoreCaptures,
MaxUsesToExplore);
- if (UseNewOBB)
- OBB = new OrderedBasicBlock(I->getParent());
// TODO: See comment in PointerMayBeCaptured regarding what could be done
// with StoreCaptures.
- CapturesBefore CB(ReturnCaptures, I, DT, IncludeI, OBB);
+ CapturesBefore CB(ReturnCaptures, I, DT, IncludeI);
PointerMayBeCaptured(V, &CB, MaxUsesToExplore);
-
- if (UseNewOBB)
- delete OBB;
return CB.Captured;
}
diff --git a/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp b/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp
--- a/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp
+++ b/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp
@@ -104,18 +104,14 @@
const BasicBlock *BB) {
if (isSpecialInstruction(Inst))
FirstSpecialInsts.erase(BB);
- OI.invalidateBlock(BB);
}
void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
if (isSpecialInstruction(Inst))
FirstSpecialInsts.erase(Inst->getParent());
- OI.invalidateBlock(Inst->getParent());
}
void InstructionPrecedenceTracking::clear() {
- for (auto It : FirstSpecialInsts)
- OI.invalidateBlock(It.first);
FirstSpecialInsts.clear();
#ifndef NDEBUG
// The map should be valid after clearing (at least empty).
diff --git a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
--- a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -23,7 +23,6 @@
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryLocation.h"
-#include "llvm/Analysis/OrderedBasicBlock.h"
#include "llvm/Analysis/PHITransAddr.h"
#include "llvm/Analysis/PhiValues.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
@@ -250,8 +249,7 @@
MemDepResult MemoryDependenceResults::getPointerDependencyFrom(
const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
- BasicBlock *BB, Instruction *QueryInst, unsigned *Limit,
- OrderedBasicBlock *OBB) {
+ BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
MemDepResult InvariantGroupDependency = MemDepResult::getUnknown();
if (QueryInst != nullptr) {
if (auto *LI = dyn_cast<LoadInst>(QueryInst)) {
@@ -262,7 +260,7 @@
}
}
MemDepResult SimpleDep = getSimplePointerDependencyFrom(
- MemLoc, isLoad, ScanIt, BB, QueryInst, Limit, OBB);
+ MemLoc, isLoad, ScanIt, BB, QueryInst, Limit);
if (SimpleDep.isDef())
return SimpleDep;
// Non-local invariant group dependency indicates there is non local Def
@@ -363,8 +361,7 @@
MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
- BasicBlock *BB, Instruction *QueryInst, unsigned *Limit,
- OrderedBasicBlock *OBB) {
+ BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
bool isInvariantLoad = false;
unsigned DefaultLimit = getDefaultBlockScanLimit();
@@ -411,15 +408,6 @@
const DataLayout &DL = BB->getModule()->getDataLayout();
- // If the caller did not provide an ordered basic block,
- // create one to lazily compute and cache instruction
- // positions inside a BB. This is used to provide fast queries for relative
- // position between two instructions in a BB and can be used by
- // AliasAnalysis::callCapturesBefore.
- OrderedBasicBlock OBBTmp(BB);
- if (!OBB)
- OBB = &OBBTmp;
-
// Return "true" if and only if the instruction I is either a non-simple
// load or a non-simple store.
auto isNonSimpleLoadOrStore = [](Instruction *I) -> bool {
@@ -609,7 +597,7 @@
ModRefInfo MR = AA.getModRefInfo(Inst, MemLoc);
// If necessary, perform additional analysis.
if (isModAndRefSet(MR))
- MR = AA.callCapturesBefore(Inst, MemLoc, &DT, OBB);
+ MR = AA.callCapturesBefore(Inst, MemLoc, &DT);
switch (clearMust(MR)) {
case ModRefInfo::NoModRef:
// If the call has no effect on the queried pointer, just ignore it.
@@ -635,8 +623,7 @@
return MemDepResult::getNonFuncLocal();
}
-MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst,
- OrderedBasicBlock *OBB) {
+MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst) {
Instruction *ScanPos = QueryInst;
// Check for a cached result
@@ -676,7 +663,7 @@
LocalCache =
getPointerDependencyFrom(MemLoc, isLoad, ScanPos->getIterator(),
- QueryParent, QueryInst, nullptr, OBB);
+ QueryParent, QueryInst, nullptr);
} else if (auto *QueryCall = dyn_cast<CallBase>(QueryInst)) {
bool isReadOnly = AA.onlyReadsMemory(QueryCall);
LocalCache = getCallDependencyFrom(QueryCall, isReadOnly,
diff --git a/llvm/lib/Analysis/OrderedBasicBlock.cpp b/llvm/lib/Analysis/OrderedBasicBlock.cpp
deleted file mode 100644
--- a/llvm/lib/Analysis/OrderedBasicBlock.cpp
+++ /dev/null
@@ -1,111 +0,0 @@
-//===- OrderedBasicBlock.cpp --------------------------------- -*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// This file implements the OrderedBasicBlock class. OrderedBasicBlock
-// maintains an interface where clients can query if one instruction comes
-// before another in a BasicBlock. Since BasicBlock currently lacks a reliable
-// way to query relative position between instructions one can use
-// OrderedBasicBlock to do such queries. OrderedBasicBlock is lazily built on a
-// source BasicBlock and maintains an internal Instruction -> Position map. A
-// OrderedBasicBlock instance should be discarded whenever the source
-// BasicBlock changes.
-//
-// It's currently used by the CaptureTracker in order to find relative
-// positions of a pair of instructions inside a BasicBlock.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Analysis/OrderedBasicBlock.h"
-#include "llvm/IR/Instruction.h"
-using namespace llvm;
-
-OrderedBasicBlock::OrderedBasicBlock(const BasicBlock *BasicB)
- : NextInstPos(0), BB(BasicB) {
- LastInstFound = BB->end();
-}
-
-/// Given no cached results, find if \p A comes before \p B in \p BB.
-/// Cache and number out instruction while walking \p BB.
-bool OrderedBasicBlock::comesBefore(const Instruction *A,
- const Instruction *B) {
- const Instruction *Inst = nullptr;
- assert(!(LastInstFound == BB->end() && NextInstPos != 0) &&
- "Instruction supposed to be in NumberedInsts");
- assert(A->getParent() == BB && "Instruction supposed to be in the block!");
- assert(B->getParent() == BB && "Instruction supposed to be in the block!");
-
- // Start the search with the instruction found in the last lookup round.
- auto II = BB->begin();
- auto IE = BB->end();
- if (LastInstFound != IE)
- II = std::next(LastInstFound);
-
- // Number all instructions up to the point where we find 'A' or 'B'.
- for (; II != IE; ++II) {
- Inst = cast<Instruction>(II);
- NumberedInsts[Inst] = NextInstPos++;
- if (Inst == A || Inst == B)
- break;
- }
-
- assert(II != IE && "Instruction not found?");
- assert((Inst == A || Inst == B) && "Should find A or B");
- LastInstFound = II;
- return Inst != B;
-}
-
-/// Find out whether \p A dominates \p B, meaning whether \p A
-/// comes before \p B in \p BB. This is a simplification that considers
-/// cached instruction positions and ignores other basic blocks, being
-/// only relevant to compare relative instructions positions inside \p BB.
-bool OrderedBasicBlock::dominates(const Instruction *A, const Instruction *B) {
- assert(A->getParent() == B->getParent() &&
- "Instructions must be in the same basic block!");
- assert(A->getParent() == BB && "Instructions must be in the tracked block!");
-
- // First we lookup the instructions. If they don't exist, lookup will give us
- // back ::end(). If they both exist, we compare the numbers. Otherwise, if NA
- // exists and NB doesn't, it means NA must come before NB because we would
- // have numbered NB as well if it didn't. The same is true for NB. If it
- // exists, but NA does not, NA must come after it. If neither exist, we need
- // to number the block and cache the results (by calling comesBefore).
- auto NAI = NumberedInsts.find(A);
- auto NBI = NumberedInsts.find(B);
- if (NAI != NumberedInsts.end() && NBI != NumberedInsts.end())
- return NAI->second < NBI->second;
- if (NAI != NumberedInsts.end())
- return true;
- if (NBI != NumberedInsts.end())
- return false;
-
- return comesBefore(A, B);
-}
-
-void OrderedBasicBlock::eraseInstruction(const Instruction *I) {
- if (LastInstFound != BB->end() && I == &*LastInstFound) {
- if (LastInstFound == BB->begin()) {
- LastInstFound = BB->end();
- NextInstPos = 0;
- } else
- LastInstFound--;
- }
-
- NumberedInsts.erase(I);
-}
-
-void OrderedBasicBlock::replaceInstruction(const Instruction *Old,
- const Instruction *New) {
- auto OI = NumberedInsts.find(Old);
- if (OI == NumberedInsts.end())
- return;
-
- NumberedInsts.insert({New, OI->second});
- if (LastInstFound != BB->end() && Old == &*LastInstFound)
- LastInstFound = New->getIterator();
- NumberedInsts.erase(Old);
-}
diff --git a/llvm/lib/Analysis/OrderedInstructions.cpp b/llvm/lib/Analysis/OrderedInstructions.cpp
--- a/llvm/lib/Analysis/OrderedInstructions.cpp
+++ b/llvm/lib/Analysis/OrderedInstructions.cpp
@@ -18,16 +18,11 @@
assert(InstA->getParent() == InstB->getParent() &&
"Instructions must be in the same basic block");
- const BasicBlock *IBB = InstA->getParent();
- auto OBB = OBBMap.find(IBB);
- if (OBB == OBBMap.end())
- OBB = OBBMap.insert({IBB, std::make_unique<OrderedBasicBlock>(IBB)}).first;
- return OBB->second->dominates(InstA, InstB);
+ return InstA->comesBefore(InstB);
}
-/// Given 2 instructions, use OrderedBasicBlock to check for dominance relation
-/// if the instructions are in the same basic block, Otherwise, use dominator
-/// tree.
+/// Given 2 instructions, check for dominance relation if the instructions are
+/// in the same basic block. Otherwise, use dominator tree.
bool OrderedInstructions::dominates(const Instruction *InstA,
const Instruction *InstB) const {
// Use ordered basic block to do dominance check in case the 2 instructions
diff --git a/llvm/lib/IR/BasicBlock.cpp b/llvm/lib/IR/BasicBlock.cpp
--- a/llvm/lib/IR/BasicBlock.cpp
+++ b/llvm/lib/IR/BasicBlock.cpp
@@ -33,6 +33,10 @@
return getType()->getContext();
}
+template <> void llvm::invalidateParentIListOrdering(BasicBlock *BB) {
+ BB->invalidateOrders();
+}
+
// Explicit instantiation of SymbolTableListTraits since some of the methods
// are not in the public header file...
template class llvm::SymbolTableListTraits<Instruction>;
@@ -61,6 +65,8 @@
}
BasicBlock::~BasicBlock() {
+ validateInstrOrdering();
+
// If the address of the block is taken and it is being deleted (e.g. because
// it is dead), this means that there is either a dangling constant expr
// hanging off the block, or an undefined use of the block (source code
@@ -506,3 +512,29 @@
++It;
return It;
}
+
+void BasicBlock::renumberInstructions() {
+ unsigned Order = 0;
+ for (Instruction &I : *this)
+ I.Order = Order++;
+
+ // Set the bit to indicate that the instruction order valid and cached.
+ BasicBlockBits Bits = getBasicBlockBits();
+ Bits.InstrOrderValid = true;
+ setBasicBlockBits(Bits);
+}
+
+#ifndef NDEBUG
+/// In asserts builds, this checks the numbering. In non-asserts builds, it
+/// is defined as an inline function returning true in BasicBlock.h.
+void BasicBlock::validateInstrOrdering() const {
+ if (!isInstrOrderValid())
+ return;
+ const Instruction *Prev = nullptr;
+ for (const Instruction &I : *this) {
+ assert((!Prev || Prev->comesBefore(&I)) &&
+ "cached instruction ordering is incorrect");
+ Prev = &I;
+ }
+}
+#endif
diff --git a/llvm/lib/IR/Instruction.cpp b/llvm/lib/IR/Instruction.cpp
--- a/llvm/lib/IR/Instruction.cpp
+++ b/llvm/lib/IR/Instruction.cpp
@@ -97,6 +97,15 @@
BB.getInstList().splice(I, getParent()->getInstList(), getIterator());
}
+bool Instruction::comesBefore(const Instruction *Other) const {
+ assert(Parent && Other->Parent &&
+ "instructions without BB parents have no order");
+ assert(Parent == Other->Parent && "cross-BB instruction order comparison");
+ if (!Parent->isInstrOrderValid())
+ Parent->renumberInstructions();
+ return Order < Other->Order;
+}
+
void Instruction::setHasNoUnsignedWrap(bool b) {
cast<OverflowingBinaryOperator>(this)->setHasNoUnsignedWrap(b);
}
diff --git a/llvm/lib/IR/SymbolTableListTraitsImpl.h b/llvm/lib/IR/SymbolTableListTraitsImpl.h
--- a/llvm/lib/IR/SymbolTableListTraitsImpl.h
+++ b/llvm/lib/IR/SymbolTableListTraitsImpl.h
@@ -20,6 +20,11 @@
namespace llvm {
+/// Notify basic blocks when an instruction is inserted.
+template <typename ParentClass>
+inline void invalidateParentIListOrdering(ParentClass *Parent) {}
+template <> void invalidateParentIListOrdering(BasicBlock *BB);
+
/// setSymTabObject - This is called when (f.e.) the parent of a basic block
/// changes. This requires us to remove all the instruction symtab entries from
/// the current function and reinsert them into the new function.
@@ -64,6 +69,7 @@
assert(!V->getParent() && "Value already in a container!!");
ItemParentClass *Owner = getListOwner();
V->setParent(Owner);
+ invalidateParentIListOrdering(Owner);
if (V->hasName())
if (ValueSymbolTable *ST = getSymTab(Owner))
ST->reinsertValue(V);
@@ -81,8 +87,13 @@
template <typename ValueSubClass>
void SymbolTableListTraits<ValueSubClass>::transferNodesFromList(
SymbolTableListTraits &L2, iterator first, iterator last) {
- // We only have to do work here if transferring instructions between BBs
- ItemParentClass *NewIP = getListOwner(), *OldIP = L2.getListOwner();
+ // Transfering nodes, even within the same BB, invalidates the ordering. The
+ // list that we removed the nodes from still has a valid ordering.
+ ItemParentClass *NewIP = getListOwner();
+ invalidateParentIListOrdering(NewIP);
+
+ // Nothing else needs to be done if we're reording nodes within the same list.
+ ItemParentClass *OldIP = L2.getListOwner();
if (NewIP == OldIP)
return;
diff --git a/llvm/lib/Target/ARM/ARMParallelDSP.cpp b/llvm/lib/Target/ARM/ARMParallelDSP.cpp
--- a/llvm/lib/Target/ARM/ARMParallelDSP.cpp
+++ b/llvm/lib/Target/ARM/ARMParallelDSP.cpp
@@ -20,7 +20,6 @@
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/LoopAccessAnalysis.h"
-#include "llvm/Analysis/OrderedBasicBlock.h"
#include "llvm/CodeGen/TargetPassConfig.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicsARM.h"
@@ -352,7 +351,6 @@
SmallVector<Instruction*, 8> Writes;
LoadPairs.clear();
WideLoads.clear();
- OrderedBasicBlock OrderedBB(BB);
// Collect loads and instruction that may write to memory. For now we only
// record loads which are simple, sign-extended and have a single user.
@@ -384,7 +382,7 @@
if (!isModOrRefSet(intersectModRef(AA->getModRefInfo(Write, ReadLoc),
ModRefInfo::ModRef)))
continue;
- if (OrderedBB.dominates(Write, Read))
+ if (Write->comesBefore(Read))
RAWDeps[Read].insert(Write);
}
}
@@ -392,8 +390,9 @@
// Check whether there's not a write between the two loads which would
// prevent them from being safely merged.
auto SafeToPair = [&](LoadInst *Base, LoadInst *Offset) {
- LoadInst *Dominator = OrderedBB.dominates(Base, Offset) ? Base : Offset;
- LoadInst *Dominated = OrderedBB.dominates(Base, Offset) ? Offset : Base;
+ bool BaseFirst = Base->comesBefore(Offset);
+ LoadInst *Dominator = BaseFirst ? Base : Offset;
+ LoadInst *Dominated = BaseFirst ? Offset : Base;
if (RAWDeps.count(Dominated)) {
InstSet &WritesBefore = RAWDeps[Dominated];
@@ -401,7 +400,7 @@
for (auto Before : WritesBefore) {
// We can't move the second load backward, past a write, to merge
// with the first load.
- if (OrderedBB.dominates(Dominator, Before))
+ if (Dominator->comesBefore(Before))
return false;
}
}
@@ -705,12 +704,11 @@
}
// Roughly sort the mul pairs in their program order.
- OrderedBasicBlock OrderedBB(R.getRoot()->getParent());
- llvm::sort(R.getMulPairs(), [&OrderedBB](auto &PairA, auto &PairB) {
- const Instruction *A = PairA.first->Root;
- const Instruction *B = PairB.first->Root;
- return OrderedBB.dominates(A, B);
- });
+ llvm::sort(R.getMulPairs(), [](auto &PairA, auto &PairB) {
+ const Instruction *A = PairA.first->Root;
+ const Instruction *B = PairB.first->Root;
+ return A->comesBefore(B);
+ });
IntegerType *Ty = IntegerType::get(M->getContext(), 32);
for (auto &Pair : R.getMulPairs()) {
diff --git a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
--- a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
@@ -31,7 +31,6 @@
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
-#include "llvm/Analysis/OrderedBasicBlock.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
@@ -118,7 +117,7 @@
static void
deleteDeadInstruction(Instruction *I, BasicBlock::iterator *BBI,
MemoryDependenceResults &MD, const TargetLibraryInfo &TLI,
- InstOverlapIntervalsTy &IOL, OrderedBasicBlock &OBB,
+ InstOverlapIntervalsTy &IOL,
MapVector<Instruction *, bool> &ThrowableInst,
SmallSetVector<const Value *, 16> *ValueSet = nullptr) {
SmallVector<Instruction*, 32> NowDeadInsts;
@@ -161,7 +160,6 @@
if (ValueSet) ValueSet->remove(DeadInst);
IOL.erase(DeadInst);
- OBB.eraseInstruction(DeadInst);
if (NewIter == DeadInst->getIterator())
NewIter = DeadInst->eraseFromParent();
@@ -687,7 +685,7 @@
static bool handleFree(CallInst *F, AliasAnalysis *AA,
MemoryDependenceResults *MD, DominatorTree *DT,
const TargetLibraryInfo *TLI,
- InstOverlapIntervalsTy &IOL, OrderedBasicBlock &OBB,
+ InstOverlapIntervalsTy &IOL,
MapVector<Instruction *, bool> &ThrowableInst) {
bool MadeChange = false;
@@ -722,7 +720,7 @@
// DCE instructions only used to calculate that store.
BasicBlock::iterator BBI(Dependency);
- deleteDeadInstruction(Dependency, &BBI, *MD, *TLI, IOL, OBB,
+ deleteDeadInstruction(Dependency, &BBI, *MD, *TLI, IOL,
ThrowableInst);
++NumFastStores;
MadeChange = true;
@@ -780,7 +778,7 @@
static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA,
MemoryDependenceResults *MD,
const TargetLibraryInfo *TLI,
- InstOverlapIntervalsTy &IOL, OrderedBasicBlock &OBB,
+ InstOverlapIntervalsTy &IOL,
MapVector<Instruction *, bool> &ThrowableInst) {
bool MadeChange = false;
@@ -842,7 +840,7 @@
<< '\n');
// DCE instructions only used to calculate that store.
- deleteDeadInstruction(Dead, &BBI, *MD, *TLI, IOL, OBB, ThrowableInst,
+ deleteDeadInstruction(Dead, &BBI, *MD, *TLI, IOL, ThrowableInst,
&DeadStackObjects);
++NumFastStores;
MadeChange = true;
@@ -854,7 +852,7 @@
if (isInstructionTriviallyDead(&*BBI, TLI)) {
LLVM_DEBUG(dbgs() << "DSE: Removing trivially dead instruction:\n DEAD: "
<< *&*BBI << '\n');
- deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, IOL, OBB, ThrowableInst,
+ deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, IOL, ThrowableInst,
&DeadStackObjects);
++NumFastOther;
MadeChange = true;
@@ -1061,7 +1059,6 @@
const DataLayout &DL,
const TargetLibraryInfo *TLI,
InstOverlapIntervalsTy &IOL,
- OrderedBasicBlock &OBB,
MapVector<Instruction *, bool> &ThrowableInst) {
// Must be a store instruction.
StoreInst *SI = dyn_cast<StoreInst>(Inst);
@@ -1078,7 +1075,7 @@
dbgs() << "DSE: Remove Store Of Load from same pointer:\n LOAD: "
<< *DepLoad << "\n STORE: " << *SI << '\n');
- deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, OBB, ThrowableInst);
+ deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, ThrowableInst);
++NumRedundantStores;
return true;
}
@@ -1096,7 +1093,7 @@
dbgs() << "DSE: Remove null store to the calloc'ed object:\n DEAD: "
<< *Inst << "\n OBJECT: " << *UnderlyingPointer << '\n');
- deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, OBB, ThrowableInst);
+ deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, ThrowableInst);
++NumRedundantStores;
return true;
}
@@ -1110,7 +1107,6 @@
const DataLayout &DL = BB.getModule()->getDataLayout();
bool MadeChange = false;
- OrderedBasicBlock OBB(&BB);
MapVector<Instruction *, bool> ThrowableInst;
// A map of interval maps representing partially-overwritten value parts.
@@ -1120,7 +1116,7 @@
for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
// Handle 'free' calls specially.
if (CallInst *F = isFreeCall(&*BBI, TLI)) {
- MadeChange |= handleFree(F, AA, MD, DT, TLI, IOL, OBB, ThrowableInst);
+ MadeChange |= handleFree(F, AA, MD, DT, TLI, IOL, ThrowableInst);
// Increment BBI after handleFree has potentially deleted instructions.
// This ensures we maintain a valid iterator.
++BBI;
@@ -1139,14 +1135,14 @@
continue;
// eliminateNoopStore will update in iterator, if necessary.
- if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL, OBB,
+ if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL,
ThrowableInst)) {
MadeChange = true;
continue;
}
// If we find something that writes memory, get its memory dependence.
- MemDepResult InstDep = MD->getDependency(Inst, &OBB);
+ MemDepResult InstDep = MD->getDependency(Inst);
// Ignore any store where we can't find a local dependence.
// FIXME: cross-block DSE would be fun. :)
@@ -1197,7 +1193,7 @@
// If the underlying object is a non-escaping memory allocation, any store
// to it is dead along the unwind edge. Otherwise, we need to preserve
// the store.
- if (LastThrowing && OBB.dominates(DepWrite, LastThrowing)) {
+ if (LastThrowing && DepWrite->comesBefore(LastThrowing)) {
const Value* Underlying = GetUnderlyingObject(DepLoc.Ptr, DL);
bool IsStoreDeadOnUnwind = isa<AllocaInst>(Underlying);
if (!IsStoreDeadOnUnwind) {
@@ -1228,13 +1224,13 @@
<< "\n KILLER: " << *Inst << '\n');
// Delete the store and now-dead instructions that feed it.
- deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, OBB,
+ deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL,
ThrowableInst);
++NumFastStores;
MadeChange = true;
// We erased DepWrite; start over.
- InstDep = MD->getDependency(Inst, &OBB);
+ InstDep = MD->getDependency(Inst);
continue;
} else if ((OR == OW_End && isShortenableAtTheEnd(DepWrite)) ||
((OR == OW_Begin &&
@@ -1307,13 +1303,10 @@
SI->copyMetadata(*DepWrite, MDToKeep);
++NumModifiedStores;
- // Remove earlier, wider, store
- OBB.replaceInstruction(DepWrite, SI);
-
// Delete the old stores and now-dead instructions that feed them.
- deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL, OBB,
+ deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL,
ThrowableInst);
- deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, OBB,
+ deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL,
ThrowableInst);
MadeChange = true;
@@ -1349,7 +1342,7 @@
// If this block ends in a return, unwind, or unreachable, all allocas are
// dead at its end, which means stores to them are also dead.
if (BB.getTerminator()->getNumSuccessors() == 0)
- MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, OBB, ThrowableInst);
+ MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, ThrowableInst);
return MadeChange;
}
diff --git a/llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp b/llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp
--- a/llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp
+++ b/llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp
@@ -50,7 +50,6 @@
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/MemoryLocation.h"
-#include "llvm/Analysis/OrderedBasicBlock.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
@@ -502,7 +501,6 @@
}
void Vectorizer::reorder(Instruction *I) {
- OrderedBasicBlock OBB(I->getParent());
SmallPtrSet<Instruction *, 16> InstructionsToMove;
SmallVector<Instruction *, 16> Worklist;
@@ -520,7 +518,7 @@
if (IM->getParent() != I->getParent())
continue;
- if (!OBB.dominates(IM, I)) {
+ if (!IM->comesBefore(I)) {
InstructionsToMove.insert(IM);
Worklist.push_back(IM);
}
@@ -636,8 +634,6 @@
}
}
- OrderedBasicBlock OBB(Chain[0]->getParent());
-
// Loop until we find an instruction in ChainInstrs that we can't vectorize.
unsigned ChainInstrIdx = 0;
Instruction *BarrierMemoryInstr = nullptr;
@@ -647,14 +643,14 @@
// If a barrier memory instruction was found, chain instructions that follow
// will not be added to the valid prefix.
- if (BarrierMemoryInstr && OBB.dominates(BarrierMemoryInstr, ChainInstr))
+ if (BarrierMemoryInstr && BarrierMemoryInstr->comesBefore(ChainInstr))
break;
// Check (in BB order) if any instruction prevents ChainInstr from being
// vectorized. Find and store the first such "conflicting" instruction.
for (Instruction *MemInstr : MemoryInstrs) {
// If a barrier memory instruction was found, do not check past it.
- if (BarrierMemoryInstr && OBB.dominates(BarrierMemoryInstr, MemInstr))
+ if (BarrierMemoryInstr && BarrierMemoryInstr->comesBefore(MemInstr))
break;
auto *MemLoad = dyn_cast<LoadInst>(MemInstr);
@@ -673,12 +669,12 @@
// vectorize it (the vectorized load is inserted at the location of the
// first load in the chain).
if (isa<StoreInst>(MemInstr) && ChainLoad &&
- (IsInvariantLoad(ChainLoad) || OBB.dominates(ChainLoad, MemInstr)))
+ (IsInvariantLoad(ChainLoad) || ChainLoad->comesBefore(MemInstr)))
continue;
// Same case, but in reverse.
if (MemLoad && isa<StoreInst>(ChainInstr) &&
- (IsInvariantLoad(MemLoad) || OBB.dominates(MemLoad, ChainInstr)))
+ (IsInvariantLoad(MemLoad) || MemLoad->comesBefore(ChainInstr)))
continue;
if (!AA.isNoAlias(MemoryLocation::get(MemInstr),
@@ -704,7 +700,7 @@
// the basic block.
if (IsLoadChain && BarrierMemoryInstr) {
// The BarrierMemoryInstr is a store that precedes ChainInstr.
- assert(OBB.dominates(BarrierMemoryInstr, ChainInstr));
+ assert(BarrierMemoryInstr->comesBefore(ChainInstr));
break;
}
}
diff --git a/llvm/unittests/Analysis/CMakeLists.txt b/llvm/unittests/Analysis/CMakeLists.txt
--- a/llvm/unittests/Analysis/CMakeLists.txt
+++ b/llvm/unittests/Analysis/CMakeLists.txt
@@ -25,7 +25,6 @@
LoopInfoTest.cpp
MemoryBuiltinsTest.cpp
MemorySSATest.cpp
- OrderedBasicBlockTest.cpp
OrderedInstructionsTest.cpp
PhiValuesTest.cpp
ProfileSummaryInfoTest.cpp
diff --git a/llvm/unittests/Analysis/CaptureTrackingTest.cpp b/llvm/unittests/Analysis/CaptureTrackingTest.cpp
--- a/llvm/unittests/Analysis/CaptureTrackingTest.cpp
+++ b/llvm/unittests/Analysis/CaptureTrackingTest.cpp
@@ -7,7 +7,6 @@
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/CaptureTracking.h"
-#include "llvm/Analysis/OrderedBasicBlock.h"
#include "llvm/AsmParser/Parser.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
@@ -62,14 +61,13 @@
BasicBlock *EntryBB = &F->getEntryBlock();
DominatorTree DT(*F);
- OrderedBasicBlock OBB(EntryBB);
Instruction *Ret = EntryBB->getTerminator();
ASSERT_TRUE(isa<ReturnInst>(Ret));
- ASSERT_FALSE(PointerMayBeCapturedBefore(Arg, true, true, Ret, &DT, false,
- &OBB, FalseMaxUsesLimit));
+ ASSERT_FALSE(PointerMayBeCapturedBefore(Arg, true, true, Ret, &DT, false,
+ FalseMaxUsesLimit));
ASSERT_TRUE(PointerMayBeCapturedBefore(Arg, true, true, Ret, &DT, false,
- &OBB, TrueMaxUsesLimit));
+ TrueMaxUsesLimit));
};
Test("test_few_uses", 6, 4);
diff --git a/llvm/unittests/Analysis/OrderedBasicBlockTest.cpp b/llvm/unittests/Analysis/OrderedBasicBlockTest.cpp
deleted file mode 100644
--- a/llvm/unittests/Analysis/OrderedBasicBlockTest.cpp
+++ /dev/null
@@ -1,57 +0,0 @@
-//===- OrderedBasicBlockTest.cpp - OrderedBasicBlock unit tests -----------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Analysis/OrderedBasicBlock.h"
-#include "llvm/AsmParser/Parser.h"
-#include "llvm/IR/BasicBlock.h"
-#include "llvm/IR/Function.h"
-#include "llvm/IR/LLVMContext.h"
-#include "llvm/IR/Module.h"
-#include "llvm/Support/DataTypes.h"
-#include "llvm/Support/SourceMgr.h"
-#include "gtest/gtest.h"
-
-namespace llvm {
-namespace {
-
-class OrderedBasicBlockTest : public testing::Test {
-protected:
- LLVMContext C;
-
- std::unique_ptr<Module> makeLLVMModule() {
- const char *ModuleString = R"(define i32 @f(i32 %x) {
- %add = add i32 %x, 42
- ret i32 %add
- })";
- SMDiagnostic Err;
- auto foo = parseAssemblyString(ModuleString, Err, C);
- return foo;
- }
-};
-
-TEST_F(OrderedBasicBlockTest, Basic) {
- auto M = makeLLVMModule();
- Function *F = M->getFunction("f");
- BasicBlock::iterator I = F->front().begin();
- Instruction *Add = &*I++;
- Instruction *Ret = &*I++;
-
- OrderedBasicBlock OBB(&F->front());
- // Intentionally duplicated to verify cached and uncached are the same.
- EXPECT_FALSE(OBB.dominates(Add, Add));
- EXPECT_FALSE(OBB.dominates(Add, Add));
- EXPECT_TRUE(OBB.dominates(Add, Ret));
- EXPECT_TRUE(OBB.dominates(Add, Ret));
- EXPECT_FALSE(OBB.dominates(Ret, Add));
- EXPECT_FALSE(OBB.dominates(Ret, Add));
- EXPECT_FALSE(OBB.dominates(Ret, Ret));
- EXPECT_FALSE(OBB.dominates(Ret, Ret));
-}
-
-} // end anonymous namespace
-} // end namespace llvm
diff --git a/llvm/unittests/IR/BasicBlockTest.cpp b/llvm/unittests/IR/BasicBlockTest.cpp
--- a/llvm/unittests/IR/BasicBlockTest.cpp
+++ b/llvm/unittests/IR/BasicBlockTest.cpp
@@ -8,11 +8,13 @@
#include "llvm/IR/BasicBlock.h"
#include "llvm/ADT/STLExtras.h"
+#include "llvm/AsmParser/Parser.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/NoFolder.h"
+#include "llvm/Support/SourceMgr.h"
#include "gmock/gmock-matchers.h"
#include "gtest/gtest.h"
#include <memory>
@@ -129,5 +131,130 @@
delete V;
}
+TEST(BasicBlockTest, ComesBefore) {
+ const char *ModuleString = R"(define i32 @f(i32 %x) {
+ %add = add i32 %x, 42
+ ret i32 %add
+ })";
+ LLVMContext Ctx;
+ SMDiagnostic Err;
+ auto M = parseAssemblyString(ModuleString, Err, Ctx);
+ ASSERT_TRUE(M.get());
+
+ Function *F = M->getFunction("f");
+ BasicBlock &BB = F->front();
+ BasicBlock::iterator I = BB.begin();
+ Instruction *Add = &*I++;
+ Instruction *Ret = &*I++;
+
+ // Intentionally duplicated to verify cached and uncached are the same.
+ EXPECT_FALSE(BB.isInstrOrderValid());
+ EXPECT_FALSE(Add->comesBefore(Add));
+ EXPECT_TRUE(BB.isInstrOrderValid());
+ EXPECT_FALSE(Add->comesBefore(Add));
+ BB.invalidateOrders();
+ EXPECT_FALSE(BB.isInstrOrderValid());
+ EXPECT_TRUE(Add->comesBefore(Ret));
+ EXPECT_TRUE(BB.isInstrOrderValid());
+ EXPECT_TRUE(Add->comesBefore(Ret));
+ BB.invalidateOrders();
+ EXPECT_FALSE(Ret->comesBefore(Add));
+ EXPECT_FALSE(Ret->comesBefore(Add));
+ BB.invalidateOrders();
+ EXPECT_FALSE(Ret->comesBefore(Ret));
+ EXPECT_FALSE(Ret->comesBefore(Ret));
+}
+
+class InstrOrderInvalidationTest : public ::testing::Test {
+protected:
+ void SetUp() override {
+ M.reset(new Module("MyModule", Ctx));
+ Nop = Intrinsic::getDeclaration(M.get(), Intrinsic::donothing);
+ FunctionType *FT = FunctionType::get(Type::getVoidTy(Ctx), {}, false);
+ Function *F = Function::Create(FT, Function::ExternalLinkage, "foo", *M);
+ BB = BasicBlock::Create(Ctx, "entry", F);
+
+ IRBuilder<> Builder(BB);
+ I1 = Builder.CreateCall(Nop);
+ I2 = Builder.CreateCall(Nop);
+ I3 = Builder.CreateCall(Nop);
+ Ret = Builder.CreateRetVoid();
+ }
+
+ LLVMContext Ctx;
+ std::unique_ptr<Module> M;
+ Function *Nop = nullptr;
+ BasicBlock *BB = nullptr;
+ Instruction *I1 = nullptr;
+ Instruction *I2 = nullptr;
+ Instruction *I3 = nullptr;
+ Instruction *Ret = nullptr;
+};
+
+TEST_F(InstrOrderInvalidationTest, InsertInvalidation) {
+ EXPECT_FALSE(BB->isInstrOrderValid());
+ EXPECT_TRUE(I1->comesBefore(I2));
+ EXPECT_TRUE(BB->isInstrOrderValid());
+ EXPECT_TRUE(I2->comesBefore(I3));
+ EXPECT_TRUE(I3->comesBefore(Ret));
+ EXPECT_TRUE(BB->isInstrOrderValid());
+
+ // Invalidate orders.
+ IRBuilder<> Builder(BB, I2->getIterator());
+ Instruction *I1a = Builder.CreateCall(Nop);
+ EXPECT_FALSE(BB->isInstrOrderValid());
+ EXPECT_TRUE(I1->comesBefore(I1a));
+ EXPECT_TRUE(BB->isInstrOrderValid());
+ EXPECT_TRUE(I1a->comesBefore(I2));
+ EXPECT_TRUE(I2->comesBefore(I3));
+ EXPECT_TRUE(I3->comesBefore(Ret));
+ EXPECT_TRUE(BB->isInstrOrderValid());
+}
+
+TEST_F(InstrOrderInvalidationTest, SpliceInvalidation) {
+ EXPECT_TRUE(I1->comesBefore(I2));
+ EXPECT_TRUE(I2->comesBefore(I3));
+ EXPECT_TRUE(I3->comesBefore(Ret));
+ EXPECT_TRUE(BB->isInstrOrderValid());
+
+ // Use Instruction::moveBefore, which uses splice.
+ I2->moveBefore(I1);
+ EXPECT_FALSE(BB->isInstrOrderValid());
+
+ EXPECT_TRUE(I2->comesBefore(I1));
+ EXPECT_TRUE(I1->comesBefore(I3));
+ EXPECT_TRUE(I3->comesBefore(Ret));
+ EXPECT_TRUE(BB->isInstrOrderValid());
+}
+
+TEST_F(InstrOrderInvalidationTest, RemoveNoInvalidation) {
+ // Cache the instruction order.
+ EXPECT_FALSE(BB->isInstrOrderValid());
+ EXPECT_TRUE(I1->comesBefore(I2));
+ EXPECT_TRUE(BB->isInstrOrderValid());
+
+ // Removing does not invalidate instruction order.
+ I2->removeFromParent();
+ I2->deleteValue();
+ I2 = nullptr;
+ EXPECT_TRUE(BB->isInstrOrderValid());
+ EXPECT_TRUE(I1->comesBefore(I3));
+ EXPECT_EQ(std::next(I1->getIterator()), I3->getIterator());
+}
+
+TEST_F(InstrOrderInvalidationTest, EraseNoInvalidation) {
+ // Cache the instruction order.
+ EXPECT_FALSE(BB->isInstrOrderValid());
+ EXPECT_TRUE(I1->comesBefore(I2));
+ EXPECT_TRUE(BB->isInstrOrderValid());
+
+ // Removing does not invalidate instruction order.
+ I2->eraseFromParent();
+ I2 = nullptr;
+ EXPECT_TRUE(BB->isInstrOrderValid());
+ EXPECT_TRUE(I1->comesBefore(I3));
+ EXPECT_EQ(std::next(I1->getIterator()), I3->getIterator());
+}
+
} // End anonymous namespace.
} // End llvm namespace.
diff --git a/llvm/utils/gn/secondary/llvm/lib/Analysis/BUILD.gn b/llvm/utils/gn/secondary/llvm/lib/Analysis/BUILD.gn
--- a/llvm/utils/gn/secondary/llvm/lib/Analysis/BUILD.gn
+++ b/llvm/utils/gn/secondary/llvm/lib/Analysis/BUILD.gn
@@ -84,7 +84,6 @@
"ObjCARCAnalysisUtils.cpp",
"ObjCARCInstKind.cpp",
"OptimizationRemarkEmitter.cpp",
- "OrderedBasicBlock.cpp",
"OrderedInstructions.cpp",
"PHITransAddr.cpp",
"PhiValues.cpp",
diff --git a/llvm/utils/gn/secondary/llvm/unittests/Analysis/BUILD.gn b/llvm/utils/gn/secondary/llvm/unittests/Analysis/BUILD.gn
--- a/llvm/utils/gn/secondary/llvm/unittests/Analysis/BUILD.gn
+++ b/llvm/utils/gn/secondary/llvm/unittests/Analysis/BUILD.gn
@@ -27,7 +27,6 @@
"LoopInfoTest.cpp",
"MemoryBuiltinsTest.cpp",
"MemorySSATest.cpp",
- "OrderedBasicBlockTest.cpp",
"OrderedInstructionsTest.cpp",
"PhiValuesTest.cpp",
"ProfileSummaryInfoTest.cpp",