[IR] Add hasNPredecessors, hasNPredecessorsOrMore to BasicBlock
Add methods to BasicBlock which make it easier to efficiently check
whether a block has N (or more) predecessors.
This can be more efficient than using pred_size(), which is a linear
time operation.
We might consider adding similar methods for successors. I haven't done
so in this patch because succ_size() is already O(1).
With this patch applied, I measured a 0.065% compile-time reduction in
user time for running `opt -O3` on the sqlite3 amalgamation (30 trials).
The change in mergeStoreIntoSuccessor alone saves 45 million linked list
iterations in a stage2 Release build of llc.
See llvm.org/PR39702 for a harder but more general way of achieving
similar results.
Differential Revision: https://reviews.llvm.org/D54686
llvm-svn: 347256
diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp
index 0dcd737..d9e0c15 100644
--- a/llvm/lib/Transforms/Utils/Local.cpp
+++ b/llvm/lib/Transforms/Utils/Local.cpp
@@ -682,10 +682,9 @@
// DTU updates: Collect all the edges that enter
// PredBB. These dominator edges will be redirected to DestBB.
- std::vector <DominatorTree::UpdateType> Updates;
+ SmallVector<DominatorTree::UpdateType, 32> Updates;
if (DTU) {
- Updates.reserve(1 + (2 * pred_size(PredBB)));
Updates.push_back({DominatorTree::Delete, PredBB, DestBB});
for (auto I = pred_begin(PredBB), E = pred_end(PredBB); I != E; ++I) {
Updates.push_back({DominatorTree::Delete, *I, PredBB});
@@ -989,9 +988,8 @@
LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
- std::vector<DominatorTree::UpdateType> Updates;
+ SmallVector<DominatorTree::UpdateType, 32> Updates;
if (DTU) {
- Updates.reserve(1 + (2 * pred_size(BB)));
Updates.push_back({DominatorTree::Delete, BB, Succ});
// All predecessors of BB will be moved to Succ.
for (auto I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {