[IR] Lazily number instructions for local dominance queries
authorReid Kleckner <rnk@google.com>
Tue, 18 Feb 2020 22:33:54 +0000 (14:33 -0800)
committerReid Kleckner <rnk@google.com>
Tue, 18 Feb 2020 22:44:24 +0000 (14:44 -0800)
commit0c2b09a9b6246aebd301ad75b5d78ac1e7daa9c4
tree78e0ee3538d98817390b8f9513108b835dcd7191
parentcf4574299a279beeb8acb894583962ec0f41286c
[IR] Lazily number instructions for local dominance queries

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.

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.

Reviewed By: lattner, vsk, fhahn, dexonsmith

Differential Revision: https://reviews.llvm.org/D51664
26 files changed:
llvm/include/llvm/Analysis/AliasAnalysis.h
llvm/include/llvm/Analysis/CaptureTracking.h
llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h
llvm/include/llvm/Analysis/OrderedBasicBlock.h [deleted file]
llvm/include/llvm/Analysis/OrderedInstructions.h
llvm/include/llvm/IR/BasicBlock.h
llvm/include/llvm/IR/Instruction.h
llvm/lib/Analysis/AliasAnalysis.cpp
llvm/lib/Analysis/CMakeLists.txt
llvm/lib/Analysis/CaptureTracking.cpp
llvm/lib/Analysis/InstructionPrecedenceTracking.cpp
llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
llvm/lib/Analysis/OrderedBasicBlock.cpp [deleted file]
llvm/lib/Analysis/OrderedInstructions.cpp
llvm/lib/IR/BasicBlock.cpp
llvm/lib/IR/Instruction.cpp
llvm/lib/IR/SymbolTableListTraitsImpl.h
llvm/lib/Target/ARM/ARMParallelDSP.cpp
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp
llvm/unittests/Analysis/CMakeLists.txt
llvm/unittests/Analysis/CaptureTrackingTest.cpp
llvm/unittests/Analysis/OrderedBasicBlockTest.cpp [deleted file]
llvm/unittests/IR/BasicBlockTest.cpp
llvm/utils/gn/secondary/llvm/lib/Analysis/BUILD.gn
llvm/utils/gn/secondary/llvm/unittests/Analysis/BUILD.gn