Index: llvm/lib/IR/AsmWriter.cpp =================================================================== --- llvm/lib/IR/AsmWriter.cpp +++ llvm/lib/IR/AsmWriter.cpp @@ -63,7 +63,6 @@ #include "llvm/IR/Type.h" #include "llvm/IR/TypeFinder.h" #include "llvm/IR/Use.h" -#include "llvm/IR/UseListOrder.h" #include "llvm/IR/User.h" #include "llvm/IR/Value.h" #include "llvm/Support/AtomicOrdering.h" @@ -95,26 +94,10 @@ // Helper Functions //===----------------------------------------------------------------------===// -namespace { - -struct OrderMap { - DenseMap> IDs; - - unsigned size() const { return IDs.size(); } - std::pair &operator[](const Value *V) { return IDs[V]; } - - std::pair lookup(const Value *V) const { - return IDs.lookup(V); - } +using OrderMap = MapVector; - void index(const Value *V) { - // Explicitly sequence get-size and insert-value operations to avoid UB. - unsigned ID = IDs.size() + 1; - IDs[V].first = ID; - } -}; - -} // end anonymous namespace +using UseListOrderMap = + DenseMap>>; /// Look for a value that might be wrapped as metadata, e.g. a value in a /// metadata operand. Returns the input value as-is if it is not wrapped. @@ -126,7 +109,7 @@ } static void orderValue(const Value *V, OrderMap &OM) { - if (OM.lookup(V).first) + if (OM.lookup(V)) return; if (const Constant *C = dyn_cast(V)) @@ -137,7 +120,8 @@ // Note: we cannot cache this lookup above, since inserting into the map // changes the map's size, and thus affects the other IDs. - OM.index(V); + unsigned ID = OM.size() + 1; + OM[V] = ID; } static OrderMap orderModule(const Module *M) { @@ -187,33 +171,32 @@ return OM; } -static void predictValueUseListOrderImpl(const Value *V, const Function *F, - unsigned ID, const OrderMap &OM, - UseListOrderStack &Stack) { +static std::vector predictValueUseListOrder( + const Value *V, unsigned ID, const OrderMap &OM) { // Predict use-list order for this one. using Entry = std::pair; SmallVector List; for (const Use &U : V->uses()) // Check if this user will be serialized. - if (OM.lookup(U.getUser()).first) + if (OM.lookup(U.getUser())) List.push_back(std::make_pair(&U, List.size())); if (List.size() < 2) // We may have lost some users. - return; + return {}; bool GetsReversed = !isa(V) && !isa(V) && !isa(V); if (auto *BA = dyn_cast(V)) - ID = OM.lookup(BA->getBasicBlock()).first; + ID = OM.lookup(BA->getBasicBlock()); llvm::sort(List, [&](const Entry &L, const Entry &R) { const Use *LU = L.first; const Use *RU = R.first; if (LU == RU) return false; - auto LID = OM.lookup(LU->getUser()).first; - auto RID = OM.lookup(RU->getUser()).first; + auto LID = OM.lookup(LU->getUser()); + auto RID = OM.lookup(RU->getUser()); // If ID is 4, then expect: 7 6 5 1 2 3. if (LID < RID) { @@ -241,89 +224,36 @@ return L.second < R.second; })) // Order is already correct. - return; + return {}; // Store the shuffle. - Stack.emplace_back(V, F, List.size()); - assert(List.size() == Stack.back().Shuffle.size() && "Wrong size"); + std::vector Shuffle(List.size()); for (size_t I = 0, E = List.size(); I != E; ++I) - Stack.back().Shuffle[I] = List[I].second; + Shuffle[I] = List[I].second; + return Shuffle; } -static void predictValueUseListOrder(const Value *V, const Function *F, - OrderMap &OM, UseListOrderStack &Stack) { - auto &IDPair = OM[V]; - assert(IDPair.first && "Unmapped value"); - if (IDPair.second) - // Already predicted. - return; - - // Do the actual prediction. - IDPair.second = true; - if (!V->use_empty() && std::next(V->use_begin()) != V->use_end()) - predictValueUseListOrderImpl(V, F, IDPair.first, OM, Stack); - - // Recursive descent into constants. - if (const Constant *C = dyn_cast(V)) - if (C->getNumOperands()) // Visit GlobalValues. - for (const Value *Op : C->operands()) - if (isa(Op)) // Visit GlobalValues. - predictValueUseListOrder(Op, F, OM, Stack); -} - -static UseListOrderStack predictUseListOrder(const Module *M) { +static UseListOrderMap predictUseListOrder(const Module *M) { OrderMap OM = orderModule(M); - - // Use-list orders need to be serialized after all the users have been added - // to a value, or else the shuffles will be incomplete. Store them per - // function in a stack. - // - // Aside from function order, the order of values doesn't matter much here. - UseListOrderStack Stack; - - // We want to visit the functions backward now so we can list function-local - // constants in the last Function they're used in. Module-level constants - // have already been visited above. - for (const Function &F : make_range(M->rbegin(), M->rend())) { - if (F.isDeclaration()) - continue; - for (const BasicBlock &BB : F) - predictValueUseListOrder(&BB, &F, OM, Stack); - for (const Argument &A : F.args()) - predictValueUseListOrder(&A, &F, OM, Stack); - for (const BasicBlock &BB : F) - for (const Instruction &I : BB) - for (const Value *Op : I.operands()) { - Op = skipMetadataWrapper(Op); - if (isa(*Op) || isa(*Op)) // Visit GlobalValues. - predictValueUseListOrder(Op, &F, OM, Stack); - } - for (const BasicBlock &BB : F) - for (const Instruction &I : BB) - predictValueUseListOrder(&I, &F, OM, Stack); - } - - // Visit globals last. - for (const GlobalVariable &G : M->globals()) - predictValueUseListOrder(&G, nullptr, OM, Stack); - for (const Function &F : *M) - predictValueUseListOrder(&F, nullptr, OM, Stack); - for (const GlobalAlias &A : M->aliases()) - predictValueUseListOrder(&A, nullptr, OM, Stack); - for (const GlobalIFunc &I : M->ifuncs()) - predictValueUseListOrder(&I, nullptr, OM, Stack); - for (const GlobalVariable &G : M->globals()) - if (G.hasInitializer()) - predictValueUseListOrder(G.getInitializer(), nullptr, OM, Stack); - for (const GlobalAlias &A : M->aliases()) - predictValueUseListOrder(A.getAliasee(), nullptr, OM, Stack); - for (const GlobalIFunc &I : M->ifuncs()) - predictValueUseListOrder(I.getResolver(), nullptr, OM, Stack); - for (const Function &F : *M) - for (const Use &U : F.operands()) - predictValueUseListOrder(U.get(), nullptr, OM, Stack); - - return Stack; + UseListOrderMap ULOM; + for (const auto &Pair : OM) { + const Value *V = Pair.first; + if (!V->use_empty() && std::next(V->use_begin()) != V->use_end()) { + std::vector Shuffle = + predictValueUseListOrder(V, Pair.second, OM); + if (!Shuffle.empty()) { + const Function *F = nullptr; + if (auto *I = dyn_cast(V)) + F = I->getFunction(); + if (auto *A = dyn_cast(V)) + F = A->getParent(); + if (auto *BB = dyn_cast(V)) + F = BB->getParent(); + ULOM[F][V] = std::move(Shuffle); + } + } + } + return ULOM; } static const Module *getModuleFromVal(const Value *V) { @@ -2643,7 +2573,7 @@ SetVector Comdats; bool IsForDebug; bool ShouldPreserveUseListOrder; - UseListOrderStack UseListOrders; + UseListOrderMap UseListOrders; SmallVector MDNames; /// Synchronization scope names registered with LLVMContext. SmallVector SSNs; @@ -2692,7 +2622,7 @@ void printInstructionLine(const Instruction &I); void printInstruction(const Instruction &I); - void printUseListOrder(const UseListOrder &Order); + void printUseListOrder(const Value *V, const std::vector &Shuffle); void printUseLists(const Function *F); void printModuleSummaryIndex(); @@ -2926,15 +2856,14 @@ for (const GlobalIFunc &GI : M->ifuncs()) printIndirectSymbol(&GI); - // Output global use-lists. - printUseLists(nullptr); - // Output all of the functions. for (const Function &F : *M) { Out << '\n'; printFunction(&F); } - assert(UseListOrders.empty() && "All use-lists should have been consumed"); + + // Output global use-lists. + printUseLists(nullptr); // Output all attribute groups. if (!Machine.as_empty()) { @@ -4527,43 +4456,39 @@ << I.first.getAsString(true) << " }\n"; } -void AssemblyWriter::printUseListOrder(const UseListOrder &Order) { +void AssemblyWriter::printUseListOrder(const Value *V, + const std::vector &Shuffle) { bool IsInFunction = Machine.getFunction(); if (IsInFunction) Out << " "; Out << "uselistorder"; - if (const BasicBlock *BB = - IsInFunction ? nullptr : dyn_cast(Order.V)) { + if (const BasicBlock *BB = IsInFunction ? nullptr : dyn_cast(V)) { Out << "_bb "; writeOperand(BB->getParent(), false); Out << ", "; writeOperand(BB, false); } else { Out << " "; - writeOperand(Order.V, true); + writeOperand(V, true); } Out << ", { "; - assert(Order.Shuffle.size() >= 2 && "Shuffle too small"); - Out << Order.Shuffle[0]; - for (unsigned I = 1, E = Order.Shuffle.size(); I != E; ++I) - Out << ", " << Order.Shuffle[I]; + assert(Shuffle.size() >= 2 && "Shuffle too small"); + Out << Shuffle[0]; + for (unsigned I = 1, E = Shuffle.size(); I != E; ++I) + Out << ", " << Shuffle[I]; Out << " }\n"; } void AssemblyWriter::printUseLists(const Function *F) { - auto hasMore = - [&]() { return !UseListOrders.empty() && UseListOrders.back().F == F; }; - if (!hasMore()) - // Nothing to do. + auto It = UseListOrders.find(F); + if (It == UseListOrders.end()) return; Out << "\n; uselistorder directives\n"; - while (hasMore()) { - printUseListOrder(UseListOrders.back()); - UseListOrders.pop_back(); - } + for (const auto &Pair : It->second) + printUseListOrder(Pair.first, Pair.second); } //===----------------------------------------------------------------------===// Index: llvm/test/Bitcode/use-list-order2.ll =================================================================== --- llvm/test/Bitcode/use-list-order2.ll +++ llvm/test/Bitcode/use-list-order2.ll @@ -1,5 +1,4 @@ ; RUN: verify-uselistorder %s -; XFAIL: * ; Test 1 @g1 = global i8 0