[IR] Lazily number instructions for local dominance queries

[rnk]

Summary

Essentially, fold OrderedBasicBlock into BasicBlock, and make it
auto-invalidate the instruction ordering when new instructions are
added. Notably, we don't need to invalidate it when removing
instructions, which is helpful when a pass mostly delete dead
instructions rather than transforming them.

The downside is that Instruction grows from 56 bytes to 64 bytes. The
resulting LLVM code is substantially simpler and automatically handles
invalidation, which makes me think that this is the right speed and size
tradeoff. There's more low-hanging fruit in MemorySSA and DSE, which
maintain their own instruction orderings today.

The important change is in SymbolTableTraitsImpl.h, where the numbering
is invalidated. Everything else should be straightforward.

We probably want to implement a fancier re-numbering scheme so that
local updates don't invalidate the ordering, but I plan for that to be
future work, maybe for someone else.

[rnk]

llvm/include/llvm/IR/SymbolTableListTraits.h

61–64 ↗

(On Diff #163948)

Oops, I'll revert this.

[rnk]

• remove stale changes

[george.burgess.iv]

I have zero context on the various ways we can/do add instructions to a BB, so I can't immediately be helpful with the tricky part of this review. :) I've no complaints about the general direction of this patch, though.

When the code's more polished, would it be reasonable to also stick a verifier of this somewhere (that we maybe just run per-query or per-pass on EXPENSIVE_CHECKS builds, or something)?

[rnk]

In D51664#1224779, @george.burgess.iv wrote:

When the code's more polished, would it be reasonable to also stick a verifier of this somewhere (that we maybe just run per-query or per-pass on EXPENSIVE_CHECKS builds, or something)?

We could do it if expensive checks are enabled, but I think checks in NDEBUG that don't affect the asymptotic performance are the most useful. Maybe before inserting an instruction, if the numbering was previously considered valid, we can assert that it actually was? This way, we do linear work the first time we create the ordering, and then do linear work when we invalidate it. We could also check when destroying the BB, since that also does linear work.

[rnk]

• add instruction order validation
• invalidate order when splicing instructions
• call transferNodesFromList for same-list transfers

[dexonsmith]

This is awesome to see!

@ahatanak, you had a prototype of something similar a couple of years ago. Can you take a look?

The downside is that Instruction grows from 56 bytes to 64 bytes,

What's the growth for 32-bit pointers?

and I
don't have a good way to measure what that costs in practice. As the one
who removed the vtable from Value, I will say that this is how I would
like to spend the 8 bytes that I saved a year ago in r303362.

The two memory-sensitive cases I'm aware of are embedded compilers and LTO (with debug info).

It would be good to get someone to comment on the former.

On the latter: we still support users of -flto=full, so it would be interesting to know how big a regression in peak memory this would be. In the past, I've gotten numbers by running a build with -flto, using -save-temps when invoking the ld64, and then running llc on the optimized (but not CodeGen'ed) bitcode file (since the peak is in CodeGen). If you're really curious, that still seems like a decent way to look at the impact. But I doubt this will even register a difference; Instructions are usually malloc-allocated, and malloc is often 16-byte aligned.

[rnk]

Any opinions on this? I'm eager to get it in so I can release it and get some faster builds, but I know it's a core data structure change.

[fhahn]

FWIW, it seems like OrderedBB invalidation is causing bugs at least in LoopSafetyInfo (D50377) which @mkazantsev is currently working on fixing. There might be other places that get this wrong too, so having automatic invalidation seems like another good plus on top of the speedups.

[george.burgess.iv]

This looks good to me, but like said, I don't have sufficient context to stamp it with great confidence.

Thanks again!

llvm/include/llvm/IR/BasicBlock.h

459

nit: I'd expect a function named this to assert(). Can we rename it to something that sounds more boolean-y like isInstrOrderingValid() (?) and/or add LLVM_NODISCARD?

459

nit * 2: I don't know what precedent is set elsewhere, but personally, I feel that if the intent is for this to only be used in NDEBUG builds, we should wrap this function decl in #ifndef NDEBUG.

Mostly because I'd prefer the compiler tells me to reconsider my life choices over silently getting potentially-incorrect results. If it turns out that there's a case where the latter is preferable, it's a ~4 line diff. :)

[mkazantsev]

I've run a big corpus of fuzz tests on this patch and it passed OK. So the patch seems good to me in terms of stability. Unfortunately I don't have time to give a proper code review on that. :(

It also makes my work on ICF tracking much easier as @fhahn has mentioned. So I'd also be happy to see it checked in. :)

[rnk]

@gbiv suggested that I test this on a large codebase, so I went ahead and built the Chrome unit_tests target with this, and the validation checks passed.

I'm going to address his comments, and otherwise I think we should go forward with this.

[mkazantsev]

I don't see any fundamental flaws in the algorithm, it looks pretty robust. I have some nit comments, otherwise it LGTM. (Note that I'm maybe not the most qualified person to approve changes in such fundamental components as BasicBlock and Instruction, but this change seems profitable).

llvm/unittests/IR/BasicBlockTest.cpp

153

EXPECT_TRUE/FALSE(BB->isInstrOrderValid()) before and after that to make sure that it works at all?

[mkazantsev]

llvm/include/llvm/IR/BasicBlock.h

444

I would rather use some named constant instead of 1; it is widespread use across the code and may be confusing for a reader. Just a suggestion.

459

Agreed here.

llvm/lib/IR/Instruction.cpp

101

Maybe also makes sense to assert that Parent is not nullptr (i.e. instructions not detached).

llvm/unittests/IR/BasicBlockTest.cpp

187

Do you mind adding the similar check for Instruction->removeFromParent and Instruction->eraseFromParent?

[rnk]

• Use private bitfield for subclass data
• Change cached order invalidation
• Add tests for removal and erasure

[rnk]

llvm/include/llvm/IR/BasicBlock.h

444

I rewrote this to use a bitfield. I think it's easier to understand now.

459

So, isInstrOrderingValid would conflict with isInstrOrderValid, which gives you the cached answer.

I'll just make it void and assert internally in !NDEBUG builds.

llvm/unittests/IR/BasicBlockTest.cpp

187

Done, but they don't invalidate ordering, so I check for that instead.

[rnk]

• Fix one last use of setValueSubclassData

[kuhar]

llvm/include/llvm/IR/BasicBlock.h

513

Does it make sense to disable this when EXPENSIVE_CHECKS are set?

llvm/lib/Analysis/OrderedInstructions.cpp

31

Is the separate function localDominates still needed? Seems like the body is trivial and could be inlined here?

llvm/lib/IR/BasicBlock.cpp

519

Is it possible to use noncontiguous indices? If the indices are spread apart, you should be able to perform most insertions without renumbering instructions.

llvm/lib/IR/SymbolTableListTraitsImpl.h

100

Isn't it enough to invalidate only the indices of instructions that follow the first inserted one?

[rnk]

• remove localDominates

[rnk]

Any other thoughts on this?

llvm/include/llvm/IR/BasicBlock.h

513

I would assume EXPENSIVE_CHECKS implies !NDEBUG, and these checks are on when assertions enabled.

llvm/lib/Analysis/OrderedInstructions.cpp

31

Sure, fixed.

llvm/lib/IR/BasicBlock.cpp

519

I want to put that out of scope of the initial change. We can do all kinds of fancy tricks here to avoid invalidating the ordering, but it's hard to provide meaningfully better algorithmic guarantees. And, the more complex code will require more complex testing, and it might have bugs. I'd rather come back and implement a more complex algorithm once profiling shows that there is a bottleneck, especially since it's often easier to remove these bottlenecks by delaying insertion.

llvm/lib/IR/SymbolTableListTraitsImpl.h

100

Yes, but recording that info and leveraging it is complex, and it doesn't change the asymptotic performance. We'd need more than a bit in BasicBlock to do it.

[kuhar]

llvm/include/llvm/IR/BasicBlock.h

513

I think you can use expensive checks independently of build type

llvm/lib/IR/BasicBlock.cpp

519

Sure, makes perfect sense. I'm not very familiar with the IR part of llvm, but I'd prefer to see a comment that explains that in a relevant place if you believe that this is a good future direction.

llvm/lib/IR/SymbolTableListTraitsImpl.h

100

Makes sense.
How expensive is it to add new data members to BasicBlock? Do you know of any attempts to stick some data inside and measure how it affects compilation times?

[george.burgess.iv]

llvm/include/llvm/IR/BasicBlock.h

513

Sounds to me like a bug in EXPENSIVE_CHECKS if it can be used without assertions.

Personally, every time I've written #if EXPENSIVE_CHECKS code, I've assumed that assertions are on. Glancing at a handful of users, the most common case I can find by far is:

#ifdef EXPENSIVE_CHECKS
assert(...); // Or call a function that just does a lot of asserts
#endif

Moreover, I can't think of a case where I'd say "build an LLVM that spends as much time as it wants verifying itself, but not with assertions."

[sanjoy]

The downside is that Instruction grows from 56 bytes to 64 bytes, and I don't have a good way to measure what that costs in practice.

In the commit that removed the table you said "Removing the virtual table pointer from Value saves 1% of RSS when doing LTO of llc on Linux."; so I'd expect the regression to be in the same ballpark?

[rnk]

In D51664#1243763, @sanjoy wrote:

The downside is that Instruction grows from 56 bytes to 64 bytes, and I don't have a good way to measure what that costs in practice.

In the commit that removed the table you said "Removing the virtual table pointer from Value saves 1% of RSS when doing LTO of llc on Linux."; so I'd expect the regression to be in the same ballpark?

I've started running a full LTO step of llc, but it's taking quite a while (>20min). I recall I picked LTO of llc last time because it completed in a few minutes, so I could repeat the measurement a few times to build confidence that it wasn't noise. Something may have changed. :( We'll see what comes back soon, I guess.

If I get no results, at least 1% RSS is an upper bound on increased LTO memory usage. I'm happy to trade that for 40% shorter compile time of the slowest TUs in clang.

[sanjoy]

If I get no results, at least 1% RSS is an upper bound on increased LTO memory usage. I'm happy to trade that for 40% shorter compile time of the slowest TUs in clang.

That I agree with. :)

Though, as I said on the llvm-dev thread, we may be able to get the best of both worlds by using something like the waymarking algorithm.

[rnk]

In D51664#1243954, @sanjoy wrote:

If I get no results, at least 1% RSS is an upper bound on increased LTO memory usage. I'm happy to trade that for 40% shorter compile time of the slowest TUs in clang.

That I agree with. :)

I'm only patient enough to get two runs, before and after, and max RSS before the patch was 4816464 kb, and after, 4867836 kb. That's an increase of 1.06%. In absolute terms, ~50MB of wasted memory for Instruction positions feels high.

Though, as I said on the llvm-dev thread, we may be able to get the best of both worlds by using something like the waymarking algorithm.

That's probably possible, but I'm a little afraid to try to steal bits from ilist next/prev pointers. The complexity cost of stealing those bits from ilist is likely to be more than is really worth it, and it's not clear if we want to use linked lists over the long term. I would rather get right complexity first, and then make a follow-up change to try to reduce the memory usage. I don't want to let the perfect be the enemy of the good.

[lattner]

As I mentioned on llvmdev, I'm strongly opposed to this patch without a significant amount of analysis and diligence applied to it. I'm concerned about both memory and compile time impact. We don't just add random caches to the core IR to speed up particular clients. We care a lot about sizeof(Instruction) and its subclasses, and this adds bloat to all of them. Similarly, you don't seem interested in evaluating "tricks" to make this efficient in practice (sparse numbering), nor have you evaluated other implementation choices that will probably also work with less impact. Let's continue discussing this on llvm-dev.

[lattner]

To be clear, I'm not necessarily saying that this patch is the wrong thing to do, I would just like more diligence and experimentation with alternate approaches. Thanks :-)

[nikic]

llvm/include/llvm/IR/BasicBlock.h

516

This should probably be BasicBlock::validateInstrOrdering() rather than Instruction::validateInstrOrdering().

[rnk]

rebase

[rnk]

• rebase

[lattner]

Hi Reid,

After giving you a hard time about this a few months ago, I've come around to believing that this is the right thing to do. Certain classes of algorithms really do benefit from having a lexicographic ordering comparison that is fast, and I think that this general approach is the best way to go.

-Chris

[lattner]

I haven't reviewed the patch in full detail, but the predicate "comesBefore" should probably be something like "isBeforeInBlock".

[rnk]

In D51664#1357417, @lattner wrote:

After giving you a hard time about this a few months ago, I've come around to believing that this is the right thing to do. Certain classes of algorithms really do benefit from having a lexicographic ordering comparison that is fast, and I think that this general approach is the best way to go.

Thanks! I'll bring it up on the dev list. I do know that @chandlerc wants to see a version of this that uses out of line numbers in a hash table, similar to the way we maintain value names out of line in a symbol table, but still done as part of the IR. I wanted to prototype that and compare.

[chandlerc]

In D51664#1358377, @rnk wrote:

In D51664#1357417, @lattner wrote:

After giving you a hard time about this a few months ago, I've come around to believing that this is the right thing to do. Certain classes of algorithms really do benefit from having a lexicographic ordering comparison that is fast, and I think that this general approach is the best way to go.

Thanks! I'll bring it up on the dev list. I do know that @chandlerc wants to see a version of this that uses out of line numbers in a hash table, similar to the way we maintain value names out of line in a symbol table, but still done as part of the IR. I wanted to prototype that and compare.

To be super clear, I definitely want *some* solution here. I'm completely on board with this being a real problem and we should solve it.

And if even getting reasonable data proves to be tons of work, I think its fine to say that and move on. In our conversation I was worried we weren't even checking to see if a side table was an effective strategy. I don't have any reason to believe this is going to be so important that it is worth *tons* of effort to validate both alternatives, it just seems useful to try a quick prototype.

[rnk]

• rebase over r351992

[qcolombet]

Hi Reid,

Thanks for doing this.

Instead of changing the instruction and basic block classes, could we instead provide an enhanced version of ilist that does that?
E.g., something based on https://scholar.google.com/scholar?cluster=5225046542682967685&hl=en&as_sdt=0,5 (and we can add laziness on top if we want)

The rationale is that I wanted to do something similar in the Machine representation as well (and rework the SlotIndexes in the process) and was thinking that an improved version of ilist would do that for us while allowing to share the code in the middle-end and backend.

Bottom line, I was hoping this work would solve the dominance problem instead of basic block for the backend as well :).

Cheers,
-Quentin

[rnk]

• rebase

[fhahn]

For DSE, it seems quite straight-forward to preserve OrderedBB (we just remove instructions or replace existing ones with another one). I've added D59789 sketching that. This could be a stop-gap until this patch gets through.

[vsk]

Is there still interest in pushing this forward? I like the approach taken here. We also just got a report of clang spending 21 minutes inside of DeadStoreElimination, and the lion's share of that time was within OrderedBasicBlock::comesBefore..

[rnk]

I still think we should do this. I think @fhahn is reimplementing DSE using MemorySSA, so presumably the DSE cases won't be an issue soon, but setting all that aside, I still think it would be nice if we could say once and for all that Instruction::dominates(Instruction*) is amortized O(1) if you haven't modified the instruction stream. Otherwise this kind of pathology will pop up again. Putting the ordering on the IR saves clients from ferrying around and maintaining OrderedInstructions / OrderedBasicBlock data structures, and that seems like a win.

[rnk]

I meant to add that @rriddle adopted this approach in MLIR:
https://github.com/llvm/llvm-project/blob/master/mlir/include/mlir/IR/Operation.h#L615

[dexonsmith]

In D51664#1877029, @rnk wrote:

I still think we should do this. I think @fhahn is reimplementing DSE using MemorySSA, so presumably the DSE cases won't be an issue soon, but setting all that aside, I still think it would be nice if we could say once and for all that Instruction::dominates(Instruction*) is amortized O(1) if you haven't modified the instruction stream. Otherwise this kind of pathology will pop up again. Putting the ordering on the IR saves clients from ferrying around and maintaining OrderedInstructions / OrderedBasicBlock data structures, and that seems like a win.

I'm strongly in favour of this too. Is there any reviewer you're specifically waiting for? Or should the RFC be bumped to ensure there's consensus before you spend the time rebasing?

[rriddle]

In D51664#1877032, @rnk wrote:

I meant to add that @rriddle adopted this approach in MLIR:
https://github.com/llvm/llvm-project/blob/master/mlir/include/mlir/IR/Operation.h#L615

Yes, we've been using this in MLIR for at least a year now. There have been quite a few cases in MLIR, unrelated to DSE, that have really benefited from O(1) dominance checks readily available. There has only been one situation that I can recall where recomputing the block order showed up on a profile, but adding in some basic striding to the order assignment completely fixed it.

[rnk]

• rebase

[rnk]

I reposted the RFC to llvm-dev, and I think this time we'll reach a different consensus.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1311

I don't have an equivalent API for this. I don't have a good way to profile to check if that is or is not the case.

[lattner]

I haven't carefully reviewed the patch, but I think this is the right thing to do architecturally for the compiler. Thank you for driving this Reid. I'd appreciate it if someone could scrutinize the patch though!

[rnk]

Thanks! I was planning to wait a bit more after restarting the RFC to land this, but I think we have a lot of support here, and I don't have a lot of reasons to wait. I'm going to go ahead and push it, and if there are problems or objections, we can revert.

[mkazantsev]

WOW! Thanks!

[hfinkel]

In D51664#1881963, @mkazantsev wrote:

WOW! Thanks!

+1

I think that this is a really nice step forward and will make a lot of things easier in the future.

llvm/include/llvm/Analysis/AliasAnalysis.h

 #include <vector>
 
 namespace llvm {
 
 class AnalysisUsage;
 class BasicAAResult;
 class BasicBlock;
 class DominatorTree;
-class OrderedBasicBlock;
 class Value;
 
 /// The possible results of an alias query.
 ///
 /// These results are always computed between two MemoryLocation objects as
 /// a query to some alias analysis.
 ///
 /// Note that these are unscoped enumerations because we would like to support
public:
 
   /// Return information about whether two call sites may refer to the same set
   /// of memory locations. See the AA documentation for details:
   ///   http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
   ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2);
 
   /// 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);
   }
 
   /// @}
   //===--------------------------------------------------------------------===//
   /// \name Higher level methods for querying mod/ref information.
   /// @{
 
   /// Check if it is possible for execution of the specified basic block to

llvm/include/llvm/Analysis/CaptureTracking.h

 
 namespace llvm {
 
   class Value;
   class Use;
   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,
   /// where the results can't be cached.
   /// TODO: we should probably introduce a caching CaptureTracking analysis and
   /// use it where possible. The caching version can use much higher limit or
   /// don't have this cap at all.
   unsigned constexpr DefaultMaxUsesToExplore = 20;
namespace llvm {
   /// captured by the enclosing function (which is required to exist). If a
   /// DominatorTree is provided, only captures which happen before the given
   /// instruction are considered. This routine can be expensive, so consider
   /// caching the results.  The boolean ReturnCaptures specifies whether
   /// 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. 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
   /// addition to the interface here, you'll need to provide your own getters
   /// to see whether anything was captured.
   struct CaptureTracker {
     virtual ~CaptureTracker();
 

llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h

public:
   /// The return value of this method is the default limit that will be
   /// used if no limit is explicitly passed in.
   unsigned getDefaultBlockScanLimit() const;
 
   /// Returns the instruction on which a memory operation depends.
   ///
   /// 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.
   ///
   /// The returned set of results will include a "NonLocal" result for all
   /// blocks where the value is live across.
   ///
   /// This method assumes the instruction returns a "NonLocal" dependency
public:
   /// the number of instructions left to examine. If a null pointer is passed
   /// in, the limit will default to the value of -memdep-block-scan-limit.
   ///
   /// Note that this is an uncached query, and thus may be inefficient.
   MemDepResult getPointerDependencyFrom(const MemoryLocation &Loc, bool isLoad,
                                         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
   /// find anything, and Def if it can be assumed that 2 instructions load or
   /// store the same value and NonLocal which indicate that non-local Def was
   /// found, which can be retrieved by calling getNonLocalPointerDependency
   /// with the same queried instruction.
   MemDepResult getInvariantGroupPointerDependency(LoadInst *LI, BasicBlock *BB);

llvm/include/llvm/Analysis/OrderedBasicBlock.h

-//===- 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

llvm/include/llvm/Analysis/OrderedInstructions.h

 //===- llvm/Transforms/Utils/OrderedInstructions.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 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.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H
 #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;
 
   /// Return true if the first instruction comes before the second in the
   /// same basic block. It will create an ordered basic block, if it does
   /// not yet exist in OBBMap.
   bool localDominates(const Instruction *, const Instruction *) const;
 
 public:
   /// Constructor.
   OrderedInstructions(DominatorTree *DT) : DT(DT) {}
 
   /// Return true if first instruction dominates the second.
   bool dominates(const Instruction *, const Instruction *) const;
 
   /// Return true if the first instruction comes before the second in the
   /// dominator tree DFS traversal if they are in different basic blocks,
   /// 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
 
 #endif // LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H

llvm/include/llvm/IR/BasicBlock.h

public:
   /// keeping loop information consistent, use the SplitBlock utility function.
   BasicBlock *splitBasicBlock(iterator I, const Twine &BBName = "");
   BasicBlock *splitBasicBlock(Instruction *I, const Twine &BBName = "") {
     return splitBasicBlock(I->getIterator(), BBName);
   }
 
   /// 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.
   void replacePhiUsesWith(BasicBlock *Old, BasicBlock *New);
 
   /// Update all phi nodes in this basic block's successors to refer to basic
   /// block \p New instead of basic block \p Old.
   void replaceSuccessorsPhiUsesWith(BasicBlock *Old, BasicBlock *New);
return const_cast<LandingPadInst *>(
                     static_cast<const BasicBlock *>(this)->getLandingPadInst());
   }
 
   /// Return true if it is legal to hoist instructions into this block.
   bool isLegalToHoistInto() const;
 
   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
   /// that any future subclasses cannot accidentally use it.
   void setValueSubclassData(unsigned short D) {
     Value::setValueSubclassData(D);
   }
 };
 
 // Create wrappers for C Binding types (see CBindingWrapping.h).
 DEFINE_SIMPLE_CONVERSION_FUNCTIONS(BasicBlock, LLVMBasicBlockRef)
 
 /// Advance \p It while it points to a debug instruction and return the result.
 /// 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

llvm/include/llvm/IR/Instruction.h

template <> struct ilist_alloc_traits<Instruction> {
   static inline void deleteNode(Instruction *V);
 };
 
 class Instruction : public User,
                     public ilist_node_with_parent<Instruction, BasicBlock> {
   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.
     HasMetadataBit = 1 << 15
   };
 
 protected:
   ~Instruction(); // Use deleteValue() to delete a generic Instruction.
public:
   ///
   /// \pre I is a valid iterator into BB.
   void moveBefore(BasicBlock &BB, SymbolTableList<Instruction>::iterator I);
 
   /// Unlink this instruction from its current basic block and insert it into
   /// 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.
   //===--------------------------------------------------------------------===//
 
   /// Returns a member of one of the enums like Instruction::Add.
   unsigned getOpcode() const { return getValueID() - InstructionVal; }
 
   const char *getOpcodeName() const { return getOpcodeName(getOpcode()); }

 #define  FIRST_OTHER_INST(N)             OtherOpsBegin = N,
 #define HANDLE_OTHER_INST(N, OPC, CLASS) OPC = N,
 #define   LAST_OTHER_INST(N)             OtherOpsEnd = N+1
 #include "llvm/IR/Instruction.def"
   };
 
 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.
   void setValueSubclassData(unsigned short D) {
     Value::setValueSubclassData(D);
   }
 
   unsigned short getSubclassDataFromValue() const {

llvm/lib/Analysis/AliasAnalysis.cpp

if (AR == MustAlias)
       return ModRefInfo::MustModRef;
   }
 
   return ModRefInfo::ModRef;
 }
 
 /// 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;
 
   const Value *Object =
       GetUnderlyingObject(MemLoc.Ptr, I->getModule()->getDataLayout());
   if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
       isa<Constant>(Object))
     return ModRefInfo::ModRef;
 
   const auto *Call = dyn_cast<CallBase>(I);
   if (!Call || Call == Object)
     return ModRefInfo::ModRef;
 
   if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
                                  /* StoreCaptures */ true, I, DT,
-                                 /* include Object */ true,
-                                 /* OrderedBasicBlock */ OBB))
+                                 /* include Object */ true))
     return ModRefInfo::ModRef;
 
   unsigned ArgNo = 0;
   ModRefInfo R = ModRefInfo::NoModRef;
   bool IsMustAlias = true;
   // Set flag only if no May found and all operands processed.
   for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end();
        CI != CE; ++CI, ++ArgNo) {

llvm/lib/Analysis/CMakeLists.txt

add_llvm_component_library(LLVMAnalysis
   MemorySSAUpdater.cpp
   ModuleDebugInfoPrinter.cpp
   ModuleSummaryAnalysis.cpp
   MustExecute.cpp
   ObjCARCAliasAnalysis.cpp
   ObjCARCAnalysisUtils.cpp
   ObjCARCInstKind.cpp
   OptimizationRemarkEmitter.cpp
-  OrderedBasicBlock.cpp
   OrderedInstructions.cpp
   PHITransAddr.cpp
   PhiValues.cpp
   PostDominators.cpp
   ProfileSummaryInfo.cpp
   PtrUseVisitor.cpp
   RegionInfo.cpp
   RegionPass.cpp

llvm/lib/Analysis/CaptureTracking.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/ADT/SmallSet.h"
 #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"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 
 using namespace llvm;
 
namespace {
 
   /// Only find pointer captures which happen before the given instruction. Uses
   /// the dominator tree to determine whether one instruction is before another.
   /// Only support the case where the Value is defined in the same basic block
   /// as the given instruction and the use.
   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; }
 
     bool isSafeToPrune(Instruction *I) {
       BasicBlock *BB = I->getParent();
       // We explore this usage only if the usage can reach "BeforeHere".
       // If use is not reachable from entry, there is no need to explore.
       if (BeforeHere != I && !DT->isReachableFromEntry(BB))
         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.
         //
         // The value defined by an invoke dominates an instruction only
         // if it dominates every instruction in UseBB. A PHI is dominated only
         // if the instruction dominates every possible use in the UseBB. Since
         // 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
         // guarantee that 'I' never reaches 'BeforeHere' through a back-edge or
         // by its successors, i.e, prune if:
         //
         //  (1) BB is an entry block or have no successors.
         //  (2) There's no path coming back through BB successors.
bool captured(const Use *U) override {
 
       if (!shouldExplore(U))
         return false;
 
       Captured = true;
       return true;
     }
 
-    OrderedBasicBlock *OrderedBB;
     const Instruction *BeforeHere;
     const DominatorTree *DT;
 
     bool ReturnCaptures;
     bool IncludeI;
 
     bool Captured;
   };

 /// PointerMayBeCapturedBefore - Return true if this pointer value may be
 /// captured by the enclosing function (which is required to exist). If a
 /// DominatorTree is provided, only captures which happen before the given
 /// instruction are considered. This routine can be expensive, so consider
 /// caching the results.  The boolean ReturnCaptures specifies whether
 /// 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;
 }
 
 void llvm::PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker,
                                 unsigned MaxUsesToExplore) {
   assert(V->getType()->isPointerTy() && "Capture is for pointers only!");
   SmallVector<const Use *, DefaultMaxUsesToExplore> Worklist;
   SmallSet<const Use *, DefaultMaxUsesToExplore> Visited;

llvm/lib/Analysis/InstructionPrecedenceTracking.cpp

for (auto &It : FirstSpecialInsts)
     validate(It.first);
 }
 #endif
 
 void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst,
                                                         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).
   validateAll();
 #endif
 }
 
 bool ImplicitControlFlowTracking::isSpecialInstruction(

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #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"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
if (auto *SI = dyn_cast<StoreInst>(Inst))
     return SI->isVolatile();
   if (auto *AI = dyn_cast<AtomicCmpXchgInst>(Inst))
     return AI->isVolatile();
   return false;
 }
 
 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)) {
       InvariantGroupDependency = getInvariantGroupPointerDependency(LI, BB);
 
       if (InvariantGroupDependency.isDef())
         return InvariantGroupDependency;
     }
   }
   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
   // (it only returns nonLocal if it finds nonLocal def), which is better than
   // local clobber and everything else.
   if (InvariantGroupDependency.isNonLocal())
     return InvariantGroupDependency;
 
NonLocalDefsCache.try_emplace(
       LI, NonLocalDepResult(ClosestDependency->getParent(),
                             MemDepResult::getDef(ClosestDependency), nullptr));
   ReverseNonLocalDefsCache[ClosestDependency].insert(LI);
   return MemDepResult::getNonLocal();
 }
 
 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();
   if (!Limit)
     Limit = &DefaultLimit;
 
   // We must be careful with atomic accesses, as they may allow another thread
   //   to touch this location, clobbering it. We are conservative: if the
MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
   if (isLoad && QueryInst) {
     LoadInst *LI = dyn_cast<LoadInst>(QueryInst);
     if (LI && LI->hasMetadata(LLVMContext::MD_invariant_load))
       isInvariantLoad = true;
   }
 
   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 {
     if (auto *LI = dyn_cast<LoadInst>(I))
       return !LI->isSimple();
     if (auto *SI = dyn_cast<StoreInst>(I))
       return !SI->isSimple();
     return false;
#endif
     if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
       if (isLoad && FI->getOrdering() == AtomicOrdering::Release)
         continue;
 
     // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
     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.
       continue;
     case ModRefInfo::Mod:
       return MemDepResult::getClobber(Inst);
     case ModRefInfo::Ref:
       // If the call is known to never store to the pointer, and if this is a
#endif
 
   // No dependence found.  If this is the entry block of the function, it is
   // unknown, otherwise it is non-local.
   if (BB != &BB->getParent()->getEntryBlock())
     return MemDepResult::getNonLocal();
   return MemDepResult::getNonFuncLocal();
 }
 
-MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst,
-                                                    OrderedBasicBlock *OBB) {
+MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst) {
   Instruction *ScanPos = QueryInst;
 
   // Check for a cached result
   MemDepResult &LocalCache = LocalDeps[QueryInst];
 
   // If the cached entry is non-dirty, just return it.  Note that this depends
   // on MemDepResult's default constructing to 'dirty'.
   if (!LocalCache.isDirty())
if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
     if (MemLoc.Ptr) {
       // If we can do a pointer scan, make it happen.
       bool isLoad = !isModSet(MR);
       if (auto *II = dyn_cast<IntrinsicInst>(QueryInst))
         isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start;
 
       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,
                                          ScanPos->getIterator(), QueryParent);
     } else
       // Non-memory instruction.
       LocalCache = MemDepResult::getUnknown();
   }

llvm/lib/Analysis/OrderedBasicBlock.cpp

-//===- 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);
-}

llvm/lib/Analysis/OrderedInstructions.cpp

 #include "llvm/Analysis/OrderedInstructions.h"
 using namespace llvm;
 
 bool OrderedInstructions::localDominates(const Instruction *InstA,
                                          const Instruction *InstB) const {
   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
   // are in the same basic block.
   if (InstA->getParent() == InstB->getParent())
     return localDominates(InstA, InstB);
   return DT->dominates(InstA->getParent(), InstB->getParent());
 }
 
 bool OrderedInstructions::dfsBefore(const Instruction *InstA,
                                     const Instruction *InstB) const {
   // Use ordered basic block in case the 2 instructions are in the same basic
   // block.
   if (InstA->getParent() == InstB->getParent())
     return localDominates(InstA, InstB);
 
   DomTreeNode *DA = DT->getNode(InstA->getParent());
   DomTreeNode *DB = DT->getNode(InstB->getParent());
   return DA->getDFSNumIn() < DB->getDFSNumIn();
 }

llvm/lib/IR/BasicBlock.cpp

if (Function *F = getParent())
     return F->getValueSymbolTable();
   return nullptr;
 }
 
 LLVMContext &BasicBlock::getContext() const {
   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>;
 
 BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
                        BasicBlock *InsertBefore)
   : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) {
 
void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) {
 
   if (InsertBefore)
     NewParent->getBasicBlockList().insert(InsertBefore->getIterator(), this);
   else
     NewParent->getBasicBlockList().push_back(this);
 }
 
 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
   // expecting the address of a label to keep the block alive even though there
   // is no indirect branch).  Handle these cases by zapping the BlockAddress
   // nodes.  There are no other possible uses at this point.
   if (hasAddressTaken()) {
     assert(!use_empty() && "There should be at least one blockaddress!");
Optional<uint64_t> BasicBlock::getIrrLoopHeaderWeight() const {
   return Optional<uint64_t>();
 }
 
 BasicBlock::iterator llvm::skipDebugIntrinsics(BasicBlock::iterator It) {
   while (isa<DbgInfoIntrinsic>(It))
     ++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

llvm/lib/IR/Instruction.cpp

 }
 
 void Instruction::moveBefore(BasicBlock &BB,
                              SymbolTableList<Instruction>::iterator I) {
   assert(I == BB.end() || I->getParent() == &BB);
   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);
 }
 
 void Instruction::setHasNoSignedWrap(bool b) {
   cast<OverflowingBinaryOperator>(this)->setHasNoSignedWrap(b);
 }
 

llvm/lib/IR/SymbolTableListTraitsImpl.h

 #ifndef LLVM_LIB_IR_SYMBOLTABLELISTTRAITSIMPL_H
 #define LLVM_LIB_IR_SYMBOLTABLELISTTRAITSIMPL_H
 
 #include "llvm/IR/SymbolTableListTraits.h"
 #include "llvm/IR/ValueSymbolTable.h"
 
 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.
 template <typename ValueSubClass>
 template <typename TPtr>
 void SymbolTableListTraits<ValueSubClass>::setSymTabObject(TPtr *Dest,
                                                            TPtr Src) {
   // Get the old symtab and value list before doing the assignment.

 
 }
 
 template <typename ValueSubClass>
 void SymbolTableListTraits<ValueSubClass>::addNodeToList(ValueSubClass *V) {
   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);
 }
 
 template <typename ValueSubClass>
 void SymbolTableListTraits<ValueSubClass>::removeNodeFromList(
     ValueSubClass *V) {
   V->setParent(nullptr);
   if (V->hasName())
     if (ValueSymbolTable *ST = getSymTab(getListOwner()))
       ST->removeValueName(V->getValueName());
 }
 
 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;
 
   // We only have to update symbol table entries if we are transferring the
   // instructions to a different symtab object...
   ValueSymbolTable *NewST = getSymTab(NewIP);
   ValueSymbolTable *OldST = getSymTab(OldIP);
   if (NewST != OldST) {
     for (; first != last; ++first) {
       ValueSubClass &V = *first;
       bool HasName = V.hasName();
       if (OldST && HasName)

llvm/lib/Target/ARM/ARMParallelDSP.cpp

 //===----------------------------------------------------------------------===//
 
 #include "ARM.h"
 #include "ARMSubtarget.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #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"
 #include "llvm/IR/NoFolder.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Pass.h"
 #include "llvm/PassRegistry.h"
 #include "llvm/PassSupport.h"

 
 /// Iterate through the block and record base, offset pairs of loads which can
 /// be widened into a single load.
 bool ARMParallelDSP::RecordMemoryOps(BasicBlock *BB) {
   SmallVector<LoadInst*, 8> Loads;
   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.
   // TODO: Allow zero-extended loads.
   for (auto &I : *BB) {
     if (I.mayWriteToMemory())
       Writes.push_back(&I);
     auto *Ld = dyn_cast<LoadInst>(&I);
bool ARMParallelDSP::RecordMemoryOps(BasicBlock *BB) {
   for (auto Write : Writes) {
     for (auto Read : Loads) {
       MemoryLocation ReadLoc =
         MemoryLocation(Read->getPointerOperand(), Size);
 
       if (!isModOrRefSet(intersectModRef(AA->getModRefInfo(Write, ReadLoc),
           ModRefInfo::ModRef)))
         continue;
-      if (OrderedBB.dominates(Write, Read))
+      if (Write->comesBefore(Read))
         RAWDeps[Read].insert(Write);
     }
   }
 
   // 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];
 
       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;
       }
     }
     return true;
   };
 
   // Record base, offset load pairs.
   for (auto *Base : Loads) {
Acc = R.is64Bit() ?
       ConstantInt::get(IntegerType::get(M->getContext(), 64), 0) :
       ConstantInt::get(IntegerType::get(M->getContext(), 32), 0);
   } else if (Acc->getType() != R.getType()) {
     Builder.SetInsertPoint(R.getRoot());
     Acc = Builder.CreateSExt(Acc, R.getType());
   }
 
   // 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) {
+    return A->comesBefore(B);
 
   IntegerType *Ty = IntegerType::get(M->getContext(), 32);
   for (auto &Pair : R.getMulPairs()) {
     MulCandidate *LHSMul = Pair.first;
     MulCandidate *RHSMul = Pair.second;
     LoadInst *BaseLHS = LHSMul->getBaseLoad();
     LoadInst *BaseRHS = RHSMul->getBaseLoad();
     LoadInst *WideLHS = WideLoads.count(BaseLHS) ?

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #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"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"

 
 /// Delete this instruction.  Before we do, go through and zero out all the
 /// operands of this instruction.  If any of them become dead, delete them and
 /// the computation tree that feeds them.
 /// If ValueSet is non-null, remove any deleted instructions from it as well.
 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;
 
   NowDeadInsts.push_back(I);
   --NumFastOther;
 
   // Keeping the iterator straight is a pain, so we let this routine tell the
for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
 
       if (Instruction *OpI = dyn_cast<Instruction>(Op))
         if (isInstructionTriviallyDead(OpI, &TLI))
           NowDeadInsts.push_back(OpI);
     }
 
     if (ValueSet) ValueSet->remove(DeadInst);
     IOL.erase(DeadInst);
-    OBB.eraseInstruction(DeadInst);
 
     if (NewIter == DeadInst->getIterator())
       NewIter = DeadInst->eraseFromParent();
     else
       DeadInst->eraseFromParent();
   } while (!NowDeadInsts.empty());
   *BBI = NewIter;
   // Pop dead entries from back of ThrowableInst till we find an alive entry.
static void findUnconditionalPreds(SmallVectorImpl<BasicBlock *> &Blocks,
   }
 }
 
 /// Handle frees of entire structures whose dependency is a store
 /// to a field of that structure.
 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;
 
   MemoryLocation Loc = MemoryLocation(F->getOperand(0));
   SmallVector<BasicBlock *, 16> Blocks;
   Blocks.push_back(F->getParent());
   const DataLayout &DL = F->getModule()->getDataLayout();
 
while (Dep.isDef() || Dep.isClobber()) {
         break;
 
       LLVM_DEBUG(
           dbgs() << "DSE: Dead Store to soon to be freed memory:\n  DEAD: "
                  << *Dependency << '\n');
 
       // 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;
 
       // Inst's old Dependency is now deleted. Compute the next dependency,
       // which may also be dead, as in
       //    s[0] = 0;
       //    s[1] = 0; // This has just been deleted.

 /// Ex:
 /// %A = alloca i32
 /// ...
 /// store i32 1, i32* %A
 /// ret void
 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;
 
   // Keep track of all of the stack objects that are dead at the end of the
   // function.
   SmallSetVector<const Value*, 16> DeadStackObjects;
 
   // Find all of the alloca'd pointers in the entry block.
if (hasAnalyzableMemoryWrite(&*BBI, *TLI) && isRemovable(&*BBI)) {
                         I != E; ++I) {
                      dbgs() << **I;
                      if (std::next(I) != E)
                        dbgs() << ", ";
                    } dbgs()
                    << '\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;
         continue;
       }
     }
 
     // Remove any dead non-memory-mutating instructions.
     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;
       continue;
     }
 
     if (isa<AllocaInst>(BBI)) {
       // Remove allocas from the list of dead stack objects; there can't be
static bool removePartiallyOverlappedStores(AliasAnalysis *AA,
   return Changed;
 }
 
 static bool eliminateNoopStore(Instruction *Inst, BasicBlock::iterator &BBI,
                                AliasAnalysis *AA, MemoryDependenceResults *MD,
                                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);
   if (!SI)
     return false;
 
   // If we're storing the same value back to a pointer that we just loaded from,
   // then the store can be removed.
   if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
     if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
         isRemovable(SI) && memoryIsNotModifiedBetween(DepLoad, SI, AA)) {
 
       LLVM_DEBUG(
           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;
     }
   }
 
   // Remove null stores into the calloc'ed objects
   Constant *StoredConstant = dyn_cast<Constant>(SI->getValueOperand());
   if (StoredConstant && StoredConstant->isNullValue() && isRemovable(SI)) {
     Instruction *UnderlyingPointer =
         dyn_cast<Instruction>(GetUnderlyingObject(SI->getPointerOperand(), DL));
 
     if (UnderlyingPointer && isCallocLikeFn(UnderlyingPointer, TLI) &&
         memoryIsNotModifiedBetween(UnderlyingPointer, SI, AA)) {
       LLVM_DEBUG(
           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;
     }
   }
   return false;
 }
 
 static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
                                 MemoryDependenceResults *MD, DominatorTree *DT,
                                 const TargetLibraryInfo *TLI) {
   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.
   InstOverlapIntervalsTy IOL;
 
   // Do a top-down walk on the BB.
   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;
       continue;
     }
 
     Instruction *Inst = &*BBI++;
 
     if (Inst->mayThrow()) {
       ThrowableInst[Inst] = true;
       continue;
     }
 
     // Check to see if Inst writes to memory.  If not, continue.
     if (!hasAnalyzableMemoryWrite(Inst, *TLI))
       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. :)
     if (!InstDep.isDef() && !InstDep.isClobber())
       continue;
 
     // Figure out what location is being stored to.
     MemoryLocation Loc = getLocForWrite(Inst);
while (InstDep.isDef() || InstDep.isClobber()) {
       // Make sure we don't look past a call which might throw. This is an
       // issue because MemoryDependenceAnalysis works in the wrong direction:
       // it finds instructions which dominate the current instruction, rather than
       // instructions which are post-dominated by the current instruction.
       //
       // 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) {
             // We're looking for a call to an allocation function
             // where the allocation doesn't escape before the last
             // throwing instruction; PointerMayBeCaptured
             // reasonably fast approximation.
             IsStoreDeadOnUnwind = isAllocLikeFn(Underlying, TLI) &&
while (InstDep.isDef() || InstDep.isClobber()) {
         OverwriteResult OR = isOverwrite(Loc, DepLoc, DL, *TLI, DepWriteOffset,
                                          InstWriteOffset, DepWrite, IOL, *AA,
                                          BB.getParent());
         if (OR == OW_Complete) {
           LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *DepWrite
                             << "\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 &&
                      isShortenableAtTheBeginning(DepWrite)))) {
           assert(!EnablePartialOverwriteTracking && "Do not expect to perform "
                                                     "when partial-overwrite "
                                                     "tracking is enabled");
           // The overwrite result is known, so these must be known, too.
while (InstDep.isDef() || InstDep.isClobber()) {
 
             unsigned MDToKeep[] = {LLVMContext::MD_dbg, LLVMContext::MD_tbaa,
                                    LLVMContext::MD_alias_scope,
                                    LLVMContext::MD_noalias,
                                    LLVMContext::MD_nontemporal};
             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;
 
             // We erased DepWrite and Inst (Loc); start over.
             break;
           }
         }
       }
static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
   }
 
   if (EnablePartialOverwriteTracking)
     MadeChange |= removePartiallyOverlappedStores(AA, DL, IOL);
 
   // 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;
 }
 
 static bool eliminateDeadStores(Function &F, AliasAnalysis *AA,
                                 MemoryDependenceResults *MD, DominatorTree *DT,
                                 const TargetLibraryInfo *TLI) {
   bool MadeChange = false;

llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp

 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #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"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
if (auto *SelectB = dyn_cast<SelectInst>(PtrB)) {
              areConsecutivePointers(SelectA->getFalseValue(),
                                     SelectB->getFalseValue(), PtrDelta, Depth);
     }
   }
   return false;
 }
 
 void Vectorizer::reorder(Instruction *I) {
-  OrderedBasicBlock OBB(I->getParent());
   SmallPtrSet<Instruction *, 16> InstructionsToMove;
   SmallVector<Instruction *, 16> Worklist;
 
   Worklist.push_back(I);
   while (!Worklist.empty()) {
     Instruction *IW = Worklist.pop_back_val();
     int NumOperands = IW->getNumOperands();
     for (int i = 0; i < NumOperands; i++) {
       Instruction *IM = dyn_cast<Instruction>(IW->getOperand(i));
       if (!IM || IM->getOpcode() == Instruction::PHI)
         continue;
 
       // If IM is in another BB, no need to move it, because this pass only
       // vectorizes instructions within one BB.
       if (IM->getParent() != I->getParent())
         continue;
 
-      if (!OBB.dominates(IM, I)) {
+      if (!IM->comesBefore(I)) {
         InstructionsToMove.insert(IM);
         Worklist.push_back(IM);
       }
     }
   }
 
   // All instructions to move should follow I. Start from I, not from begin().
   for (auto BBI = I->getIterator(), E = I->getParent()->end(); BBI != E;
if (isa<LoadInst>(I) || isa<StoreInst>(I)) {
       break;
     } else if (!IsLoadChain && (I.mayReadOrWriteMemory() || I.mayThrow())) {
       LLVM_DEBUG(dbgs() << "LSV: Found may-read/write/throw operation: " << I
                         << '\n');
       break;
     }
   }
 
-  OrderedBasicBlock OBB(Chain[0]->getParent());
-
   // Loop until we find an instruction in ChainInstrs that we can't vectorize.
   unsigned ChainInstrIdx = 0;
   Instruction *BarrierMemoryInstr = nullptr;
 
   for (unsigned E = ChainInstrs.size(); ChainInstrIdx < E; ++ChainInstrIdx) {
     Instruction *ChainInstr = ChainInstrs[ChainInstrIdx];
 
     // 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);
       auto *ChainLoad = dyn_cast<LoadInst>(ChainInstr);
       if (MemLoad && ChainLoad)
         continue;
 
       // We can ignore the alias if the we have a load store pair and the load
       // is known to be invariant. The load cannot be clobbered by the store.
       auto IsInvariantLoad = [](const LoadInst *LI) -> bool {
         return LI->hasMetadata(LLVMContext::MD_invariant_load);
       };
 
       // We can ignore the alias as long as the load comes before the store,
       // because that means we won't be moving the load past the store to
       // 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),
                         MemoryLocation::get(ChainInstr))) {
         LLVM_DEBUG({
           dbgs() << "LSV: Found alias:\n"
                     "  Aliasing instruction and pointer:\n"
                  << "  " << *MemInstr << '\n'
for (Instruction *MemInstr : MemoryInstrs) {
       }
     }
     // Continue the search only for store chains, since vectorizing stores that
     // precede an aliasing load is valid. Conversely, vectorizing loads is valid
     // up to an aliasing store, but should not pull loads from further down in
     // the basic block.
     if (IsLoadChain && BarrierMemoryInstr) {
       // The BarrierMemoryInstr is a store that precedes ChainInstr.
-      assert(OBB.dominates(BarrierMemoryInstr, ChainInstr));
+      assert(BarrierMemoryInstr->comesBefore(ChainInstr));
       break;
     }
   }
 
   // Find the largest prefix of Chain whose elements are all in
   // ChainInstrs[0, ChainInstrIdx).  This is the largest vectorizable prefix of
   // Chain.  (Recall that Chain is in address order, but ChainInstrs is in BB
   // order.)

llvm/unittests/Analysis/CMakeLists.txt

add_llvm_unittest(AnalysisTests
   DomTreeUpdaterTest.cpp
   GlobalsModRefTest.cpp
   IVDescriptorsTest.cpp
   LazyCallGraphTest.cpp
   LoadsTest.cpp
   LoopInfoTest.cpp
   MemoryBuiltinsTest.cpp
   MemorySSATest.cpp
-  OrderedBasicBlockTest.cpp
   OrderedInstructionsTest.cpp
   PhiValuesTest.cpp
   ProfileSummaryInfoTest.cpp
   ScalarEvolutionTest.cpp
   VectorFunctionABITest.cpp
   SparsePropagation.cpp
   TargetLibraryInfoTest.cpp
   TBAATest.cpp
   UnrollAnalyzerTest.cpp
   ValueLatticeTest.cpp
   ValueTrackingTest.cpp
   VectorUtilsTest.cpp
   )

llvm/unittests/Analysis/CaptureTrackingTest.cpp

 //=======- CaptureTrackingTest.cpp - Unit test for the Capture Tracking ---===//
 //
 // 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/CaptureTracking.h"
-#include "llvm/Analysis/OrderedBasicBlock.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 
auto Test = [&M](const char *FName, unsigned FalseMaxUsesLimit,
     ASSERT_NE(F, nullptr);
     Value *Arg = &*F->arg_begin();
     ASSERT_NE(Arg, nullptr);
     ASSERT_FALSE(PointerMayBeCaptured(Arg, true, true, FalseMaxUsesLimit));
     ASSERT_TRUE(PointerMayBeCaptured(Arg, true, true, TrueMaxUsesLimit));
 
     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);
   Test("test_many_uses", 50, 30);
 }

llvm/unittests/Analysis/OrderedBasicBlockTest.cpp

-//===- 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

llvm/unittests/IR/BasicBlockTest.cpp

 //===- llvm/unittest/IR/BasicBlockTest.cpp - BasicBlock 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/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>
 
 namespace llvm {
 namespace {
 
 TEST(BasicBlockTest, PhiRange) {
TEST(BasicBlockTest, TestInstructionsWithoutDebug) {
 
   EXPECT_EQ(static_cast<size_t>(BB1->sizeWithoutDebug()), Exp.size());
   EXPECT_EQ(static_cast<size_t>(BBConst->sizeWithoutDebug()), Exp.size());
 
   delete M;
   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.

llvm/utils/gn/secondary/llvm/lib/Analysis/BUILD.gn

sources = [
     "MemorySSAUpdater.cpp",
     "ModuleDebugInfoPrinter.cpp",
     "ModuleSummaryAnalysis.cpp",
     "MustExecute.cpp",
     "ObjCARCAliasAnalysis.cpp",
     "ObjCARCAnalysisUtils.cpp",
     "ObjCARCInstKind.cpp",
     "OptimizationRemarkEmitter.cpp",
-    "OrderedBasicBlock.cpp",
     "OrderedInstructions.cpp",
     "PHITransAddr.cpp",
     "PhiValues.cpp",
     "PostDominators.cpp",
     "ProfileSummaryInfo.cpp",
     "PtrUseVisitor.cpp",
     "RegionInfo.cpp",
     "RegionPass.cpp",

llvm/utils/gn/secondary/llvm/unittests/Analysis/BUILD.gn

sources = [
     "DomTreeUpdaterTest.cpp",
     "GlobalsModRefTest.cpp",
     "IVDescriptorsTest.cpp",
     "LazyCallGraphTest.cpp",
     "LoadsTest.cpp",
     "LoopInfoTest.cpp",
     "MemoryBuiltinsTest.cpp",
     "MemorySSATest.cpp",
-    "OrderedBasicBlockTest.cpp",
     "OrderedInstructionsTest.cpp",
     "PhiValuesTest.cpp",
     "ProfileSummaryInfoTest.cpp",
     "ScalarEvolutionTest.cpp",
     "SparsePropagation.cpp",
     "TBAATest.cpp",
     "TargetLibraryInfoTest.cpp",
     "UnrollAnalyzerTest.cpp",
     "ValueLatticeTest.cpp",
     "ValueTrackingTest.cpp",
     "VectorFunctionABITest.cpp",
     "VectorUtilsTest.cpp",
   ]
 }