diff --git a/llvm/include/llvm/Transforms/Scalar/GVN.h b/llvm/include/llvm/Transforms/Scalar/GVN.h --- a/llvm/include/llvm/Transforms/Scalar/GVN.h +++ b/llvm/include/llvm/Transforms/Scalar/GVN.h @@ -19,6 +19,7 @@ #include "llvm/ADT/MapVector.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/TinyPtrVector.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/PassManager.h" @@ -232,12 +233,10 @@ /// A mapping from value numbers to lists of Value*'s that /// have that value number. Use findLeader to query it. struct LeaderTableEntry { - Value *Val; - const BasicBlock *BB; - LeaderTableEntry *Next; + TinyPtrVector<Value *> Val; + TinyPtrVector<const BasicBlock *> BB; }; DenseMap<uint32_t, LeaderTableEntry> LeaderTable; - BumpPtrAllocator TableAllocator; // Block-local map of equivalent values to their leader, does not // propagate to any successors. Entries added mid-block are applied @@ -266,45 +265,26 @@ /// Push a new Value to the LeaderTable onto the list for its value number. void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) { LeaderTableEntry &Curr = LeaderTable[N]; - if (!Curr.Val) { - Curr.Val = V; - Curr.BB = BB; - return; - } - - LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>(); - Node->Val = V; - Node->BB = BB; - Node->Next = Curr.Next; - Curr.Next = Node; + Curr.Val.push_back(V); + Curr.BB.push_back(BB); } /// Scan the list of values corresponding to a given /// value number, and remove the given instruction if encountered. void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) { - LeaderTableEntry *Prev = nullptr; - LeaderTableEntry *Curr = &LeaderTable[N]; - - while (Curr && (Curr->Val != I || Curr->BB != BB)) { - Prev = Curr; - Curr = Curr->Next; - } - - if (!Curr) - return; - - if (Prev) { - Prev->Next = Curr->Next; - } else { - if (!Curr->Next) { - Curr->Val = nullptr; - Curr->BB = nullptr; - } else { - LeaderTableEntry *Next = Curr->Next; - Curr->Val = Next->Val; - Curr->BB = Next->BB; - Curr->Next = Next->Next; + LeaderTableEntry &entry = LeaderTable[N]; + auto VI = entry.Val.begin(); + auto VE = entry.Val.end(); + auto BI = entry.BB.end(); + while (VI != VE) { + if (*VI == I && *BI == BB) { + auto eraseVI = VI--; + entry.Val.erase(eraseVI); + auto eraseBI = BI--; + entry.BB.erase(eraseBI); } + ++VI; + ++BI; } } diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp --- a/llvm/lib/Transforms/Scalar/GVN.cpp +++ b/llvm/lib/Transforms/Scalar/GVN.cpp @@ -2105,10 +2105,14 @@ /// defined in \p BB. bool GVNPass::ValueTable::areAllValsInBB(uint32_t Num, const BasicBlock *BB, GVNPass &Gvn) { - LeaderTableEntry *Vals = &Gvn.LeaderTable[Num]; - while (Vals && Vals->BB == BB) - Vals = Vals->Next; - return !Vals; + const LeaderTableEntry &entry = Gvn.LeaderTable[Num]; + for (const BasicBlock *entryBB : entry.BB) { + if (entryBB != BB) { + return false; + } + } + + return true; } /// Wrap phiTranslateImpl to provide caching functionality. @@ -2130,12 +2134,11 @@ const BasicBlock *PhiBlock, GVNPass &Gvn) { CallInst *Call = nullptr; - LeaderTableEntry *Vals = &Gvn.LeaderTable[Num]; - while (Vals) { - Call = dyn_cast<CallInst>(Vals->Val); + const LeaderTableEntry &entry = Gvn.LeaderTable[Num]; + for (Value *Val : entry.Val) { + Call = dyn_cast<CallInst>(Val); if (Call && Call->getParent() == PhiBlock) break; - Vals = Vals->Next; } if (AA->doesNotAccessMemory(Call)) @@ -2228,23 +2231,18 @@ // question. This is fast because dominator tree queries consist of only // a few comparisons of DFS numbers. Value *GVNPass::findLeader(const BasicBlock *BB, uint32_t num) { - LeaderTableEntry Vals = LeaderTable[num]; - if (!Vals.Val) return nullptr; + const LeaderTableEntry &entry = LeaderTable[num]; + if (entry.Val.empty()) + return nullptr; Value *Val = nullptr; - if (DT->dominates(Vals.BB, BB)) { - Val = Vals.Val; - if (isa<Constant>(Val)) return Val; - } - - LeaderTableEntry* Next = Vals.Next; - while (Next) { - if (DT->dominates(Next->BB, BB)) { - if (isa<Constant>(Next->Val)) return Next->Val; - if (!Val) Val = Next->Val; + for (size_t i = 0, e = entry.Val.size(); i != e; ++i) { + if (DT->dominates(entry.BB[i], BB)) { + if (isa<Constant>(entry.Val[i])) + return entry.Val[i]; + if (!Val) + Val = entry.Val[i]; } - - Next = Next->Next; } return Val; @@ -3033,7 +3031,6 @@ VN.clear(); LeaderTable.clear(); BlockRPONumber.clear(); - TableAllocator.Reset(); ICF->clear(); InvalidBlockRPONumbers = true; } @@ -3046,12 +3043,10 @@ // Walk through the value number scope to make sure the instruction isn't // ferreted away in it. for (const auto &I : LeaderTable) { - const LeaderTableEntry *Node = &I.second; - assert(Node->Val != Inst && "Inst still in value numbering scope!"); - - while (Node->Next) { - Node = Node->Next; - assert(Node->Val != Inst && "Inst still in value numbering scope!"); + const LeaderTableEntry &entry = I.second; + for (Value *Val : entry.Val) { + (void)Val; + assert(Val != Inst && "Inst still in value numbering scope!"); } } }