1*06f32e7eSjoerg //===- verify-uselistorder.cpp - The LLVM Modular Optimizer ---------------===// 2*06f32e7eSjoerg // 3*06f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*06f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information. 5*06f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*06f32e7eSjoerg // 7*06f32e7eSjoerg //===----------------------------------------------------------------------===// 8*06f32e7eSjoerg // 9*06f32e7eSjoerg // Verify that use-list order can be serialized correctly. After reading the 10*06f32e7eSjoerg // provided IR, this tool shuffles the use-lists and then writes and reads to a 11*06f32e7eSjoerg // separate Module whose use-list orders are compared to the original. 12*06f32e7eSjoerg // 13*06f32e7eSjoerg // The shuffles are deterministic, but guarantee that use-lists will change. 14*06f32e7eSjoerg // The algorithm per iteration is as follows: 15*06f32e7eSjoerg // 16*06f32e7eSjoerg // 1. Seed the random number generator. The seed is different for each 17*06f32e7eSjoerg // shuffle. Shuffle 0 uses default+0, shuffle 1 uses default+1, and so on. 18*06f32e7eSjoerg // 19*06f32e7eSjoerg // 2. Visit every Value in a deterministic order. 20*06f32e7eSjoerg // 21*06f32e7eSjoerg // 3. Assign a random number to each Use in the Value's use-list in order. 22*06f32e7eSjoerg // 23*06f32e7eSjoerg // 4. If the numbers are already in order, reassign numbers until they aren't. 24*06f32e7eSjoerg // 25*06f32e7eSjoerg // 5. Sort the use-list using Value::sortUseList(), which is a stable sort. 26*06f32e7eSjoerg // 27*06f32e7eSjoerg //===----------------------------------------------------------------------===// 28*06f32e7eSjoerg 29*06f32e7eSjoerg #include "llvm/ADT/DenseMap.h" 30*06f32e7eSjoerg #include "llvm/ADT/DenseSet.h" 31*06f32e7eSjoerg #include "llvm/AsmParser/Parser.h" 32*06f32e7eSjoerg #include "llvm/Bitcode/BitcodeReader.h" 33*06f32e7eSjoerg #include "llvm/Bitcode/BitcodeWriter.h" 34*06f32e7eSjoerg #include "llvm/IR/LLVMContext.h" 35*06f32e7eSjoerg #include "llvm/IR/Module.h" 36*06f32e7eSjoerg #include "llvm/IR/UseListOrder.h" 37*06f32e7eSjoerg #include "llvm/IR/Verifier.h" 38*06f32e7eSjoerg #include "llvm/IRReader/IRReader.h" 39*06f32e7eSjoerg #include "llvm/Support/CommandLine.h" 40*06f32e7eSjoerg #include "llvm/Support/Debug.h" 41*06f32e7eSjoerg #include "llvm/Support/ErrorHandling.h" 42*06f32e7eSjoerg #include "llvm/Support/FileSystem.h" 43*06f32e7eSjoerg #include "llvm/Support/FileUtilities.h" 44*06f32e7eSjoerg #include "llvm/Support/InitLLVM.h" 45*06f32e7eSjoerg #include "llvm/Support/MemoryBuffer.h" 46*06f32e7eSjoerg #include "llvm/Support/SourceMgr.h" 47*06f32e7eSjoerg #include "llvm/Support/SystemUtils.h" 48*06f32e7eSjoerg #include "llvm/Support/raw_ostream.h" 49*06f32e7eSjoerg #include <random> 50*06f32e7eSjoerg #include <vector> 51*06f32e7eSjoerg 52*06f32e7eSjoerg using namespace llvm; 53*06f32e7eSjoerg 54*06f32e7eSjoerg #define DEBUG_TYPE "uselistorder" 55*06f32e7eSjoerg 56*06f32e7eSjoerg static cl::opt<std::string> InputFilename(cl::Positional, 57*06f32e7eSjoerg cl::desc("<input bitcode file>"), 58*06f32e7eSjoerg cl::init("-"), 59*06f32e7eSjoerg cl::value_desc("filename")); 60*06f32e7eSjoerg 61*06f32e7eSjoerg static cl::opt<bool> SaveTemps("save-temps", cl::desc("Save temp files"), 62*06f32e7eSjoerg cl::init(false)); 63*06f32e7eSjoerg 64*06f32e7eSjoerg static cl::opt<unsigned> 65*06f32e7eSjoerg NumShuffles("num-shuffles", 66*06f32e7eSjoerg cl::desc("Number of times to shuffle and verify use-lists"), 67*06f32e7eSjoerg cl::init(1)); 68*06f32e7eSjoerg 69*06f32e7eSjoerg namespace { 70*06f32e7eSjoerg 71*06f32e7eSjoerg struct TempFile { 72*06f32e7eSjoerg std::string Filename; 73*06f32e7eSjoerg FileRemover Remover; 74*06f32e7eSjoerg bool init(const std::string &Ext); 75*06f32e7eSjoerg bool writeBitcode(const Module &M) const; 76*06f32e7eSjoerg bool writeAssembly(const Module &M) const; 77*06f32e7eSjoerg std::unique_ptr<Module> readBitcode(LLVMContext &Context) const; 78*06f32e7eSjoerg std::unique_ptr<Module> readAssembly(LLVMContext &Context) const; 79*06f32e7eSjoerg }; 80*06f32e7eSjoerg 81*06f32e7eSjoerg struct ValueMapping { 82*06f32e7eSjoerg DenseMap<const Value *, unsigned> IDs; 83*06f32e7eSjoerg std::vector<const Value *> Values; 84*06f32e7eSjoerg 85*06f32e7eSjoerg /// Construct a value mapping for module. 86*06f32e7eSjoerg /// 87*06f32e7eSjoerg /// Creates mapping from every value in \c M to an ID. This mapping includes 88*06f32e7eSjoerg /// un-referencable values. 89*06f32e7eSjoerg /// 90*06f32e7eSjoerg /// Every \a Value that gets serialized in some way should be represented 91*06f32e7eSjoerg /// here. The order needs to be deterministic, but it's unnecessary to match 92*06f32e7eSjoerg /// the value-ids in the bitcode writer. 93*06f32e7eSjoerg /// 94*06f32e7eSjoerg /// All constants that are referenced by other values are included in the 95*06f32e7eSjoerg /// mapping, but others -- which wouldn't be serialized -- are not. 96*06f32e7eSjoerg ValueMapping(const Module &M); 97*06f32e7eSjoerg 98*06f32e7eSjoerg /// Map a value. 99*06f32e7eSjoerg /// 100*06f32e7eSjoerg /// Maps a value. If it's a constant, maps all of its operands first. 101*06f32e7eSjoerg void map(const Value *V); 102*06f32e7eSjoerg unsigned lookup(const Value *V) const { return IDs.lookup(V); } 103*06f32e7eSjoerg }; 104*06f32e7eSjoerg 105*06f32e7eSjoerg } // end namespace 106*06f32e7eSjoerg 107*06f32e7eSjoerg bool TempFile::init(const std::string &Ext) { 108*06f32e7eSjoerg SmallVector<char, 64> Vector; 109*06f32e7eSjoerg LLVM_DEBUG(dbgs() << " - create-temp-file\n"); 110*06f32e7eSjoerg if (auto EC = sys::fs::createTemporaryFile("uselistorder", Ext, Vector)) { 111*06f32e7eSjoerg errs() << "verify-uselistorder: error: " << EC.message() << "\n"; 112*06f32e7eSjoerg return true; 113*06f32e7eSjoerg } 114*06f32e7eSjoerg assert(!Vector.empty()); 115*06f32e7eSjoerg 116*06f32e7eSjoerg Filename.assign(Vector.data(), Vector.data() + Vector.size()); 117*06f32e7eSjoerg Remover.setFile(Filename, !SaveTemps); 118*06f32e7eSjoerg if (SaveTemps) 119*06f32e7eSjoerg outs() << " - filename = " << Filename << "\n"; 120*06f32e7eSjoerg return false; 121*06f32e7eSjoerg } 122*06f32e7eSjoerg 123*06f32e7eSjoerg bool TempFile::writeBitcode(const Module &M) const { 124*06f32e7eSjoerg LLVM_DEBUG(dbgs() << " - write bitcode\n"); 125*06f32e7eSjoerg std::error_code EC; 126*06f32e7eSjoerg raw_fd_ostream OS(Filename, EC, sys::fs::OF_None); 127*06f32e7eSjoerg if (EC) { 128*06f32e7eSjoerg errs() << "verify-uselistorder: error: " << EC.message() << "\n"; 129*06f32e7eSjoerg return true; 130*06f32e7eSjoerg } 131*06f32e7eSjoerg 132*06f32e7eSjoerg WriteBitcodeToFile(M, OS, /* ShouldPreserveUseListOrder */ true); 133*06f32e7eSjoerg return false; 134*06f32e7eSjoerg } 135*06f32e7eSjoerg 136*06f32e7eSjoerg bool TempFile::writeAssembly(const Module &M) const { 137*06f32e7eSjoerg LLVM_DEBUG(dbgs() << " - write assembly\n"); 138*06f32e7eSjoerg std::error_code EC; 139*06f32e7eSjoerg raw_fd_ostream OS(Filename, EC, sys::fs::OF_Text); 140*06f32e7eSjoerg if (EC) { 141*06f32e7eSjoerg errs() << "verify-uselistorder: error: " << EC.message() << "\n"; 142*06f32e7eSjoerg return true; 143*06f32e7eSjoerg } 144*06f32e7eSjoerg 145*06f32e7eSjoerg M.print(OS, nullptr, /* ShouldPreserveUseListOrder */ true); 146*06f32e7eSjoerg return false; 147*06f32e7eSjoerg } 148*06f32e7eSjoerg 149*06f32e7eSjoerg std::unique_ptr<Module> TempFile::readBitcode(LLVMContext &Context) const { 150*06f32e7eSjoerg LLVM_DEBUG(dbgs() << " - read bitcode\n"); 151*06f32e7eSjoerg ErrorOr<std::unique_ptr<MemoryBuffer>> BufferOr = 152*06f32e7eSjoerg MemoryBuffer::getFile(Filename); 153*06f32e7eSjoerg if (!BufferOr) { 154*06f32e7eSjoerg errs() << "verify-uselistorder: error: " << BufferOr.getError().message() 155*06f32e7eSjoerg << "\n"; 156*06f32e7eSjoerg return nullptr; 157*06f32e7eSjoerg } 158*06f32e7eSjoerg 159*06f32e7eSjoerg MemoryBuffer *Buffer = BufferOr.get().get(); 160*06f32e7eSjoerg Expected<std::unique_ptr<Module>> ModuleOr = 161*06f32e7eSjoerg parseBitcodeFile(Buffer->getMemBufferRef(), Context); 162*06f32e7eSjoerg if (!ModuleOr) { 163*06f32e7eSjoerg logAllUnhandledErrors(ModuleOr.takeError(), errs(), 164*06f32e7eSjoerg "verify-uselistorder: error: "); 165*06f32e7eSjoerg return nullptr; 166*06f32e7eSjoerg } 167*06f32e7eSjoerg return std::move(ModuleOr.get()); 168*06f32e7eSjoerg } 169*06f32e7eSjoerg 170*06f32e7eSjoerg std::unique_ptr<Module> TempFile::readAssembly(LLVMContext &Context) const { 171*06f32e7eSjoerg LLVM_DEBUG(dbgs() << " - read assembly\n"); 172*06f32e7eSjoerg SMDiagnostic Err; 173*06f32e7eSjoerg std::unique_ptr<Module> M = parseAssemblyFile(Filename, Err, Context); 174*06f32e7eSjoerg if (!M.get()) 175*06f32e7eSjoerg Err.print("verify-uselistorder", errs()); 176*06f32e7eSjoerg return M; 177*06f32e7eSjoerg } 178*06f32e7eSjoerg 179*06f32e7eSjoerg ValueMapping::ValueMapping(const Module &M) { 180*06f32e7eSjoerg // Every value should be mapped, including things like void instructions and 181*06f32e7eSjoerg // basic blocks that are kept out of the ValueEnumerator. 182*06f32e7eSjoerg // 183*06f32e7eSjoerg // The current mapping order makes it easier to debug the tables. It happens 184*06f32e7eSjoerg // to be similar to the ID mapping when writing ValueEnumerator, but they 185*06f32e7eSjoerg // aren't (and needn't be) in sync. 186*06f32e7eSjoerg 187*06f32e7eSjoerg // Globals. 188*06f32e7eSjoerg for (const GlobalVariable &G : M.globals()) 189*06f32e7eSjoerg map(&G); 190*06f32e7eSjoerg for (const GlobalAlias &A : M.aliases()) 191*06f32e7eSjoerg map(&A); 192*06f32e7eSjoerg for (const GlobalIFunc &IF : M.ifuncs()) 193*06f32e7eSjoerg map(&IF); 194*06f32e7eSjoerg for (const Function &F : M) 195*06f32e7eSjoerg map(&F); 196*06f32e7eSjoerg 197*06f32e7eSjoerg // Constants used by globals. 198*06f32e7eSjoerg for (const GlobalVariable &G : M.globals()) 199*06f32e7eSjoerg if (G.hasInitializer()) 200*06f32e7eSjoerg map(G.getInitializer()); 201*06f32e7eSjoerg for (const GlobalAlias &A : M.aliases()) 202*06f32e7eSjoerg map(A.getAliasee()); 203*06f32e7eSjoerg for (const GlobalIFunc &IF : M.ifuncs()) 204*06f32e7eSjoerg map(IF.getResolver()); 205*06f32e7eSjoerg for (const Function &F : M) { 206*06f32e7eSjoerg if (F.hasPrefixData()) 207*06f32e7eSjoerg map(F.getPrefixData()); 208*06f32e7eSjoerg if (F.hasPrologueData()) 209*06f32e7eSjoerg map(F.getPrologueData()); 210*06f32e7eSjoerg if (F.hasPersonalityFn()) 211*06f32e7eSjoerg map(F.getPersonalityFn()); 212*06f32e7eSjoerg } 213*06f32e7eSjoerg 214*06f32e7eSjoerg // Function bodies. 215*06f32e7eSjoerg for (const Function &F : M) { 216*06f32e7eSjoerg for (const Argument &A : F.args()) 217*06f32e7eSjoerg map(&A); 218*06f32e7eSjoerg for (const BasicBlock &BB : F) 219*06f32e7eSjoerg map(&BB); 220*06f32e7eSjoerg for (const BasicBlock &BB : F) 221*06f32e7eSjoerg for (const Instruction &I : BB) 222*06f32e7eSjoerg map(&I); 223*06f32e7eSjoerg 224*06f32e7eSjoerg // Constants used by instructions. 225*06f32e7eSjoerg for (const BasicBlock &BB : F) 226*06f32e7eSjoerg for (const Instruction &I : BB) 227*06f32e7eSjoerg for (const Value *Op : I.operands()) 228*06f32e7eSjoerg if ((isa<Constant>(Op) && !isa<GlobalValue>(*Op)) || 229*06f32e7eSjoerg isa<InlineAsm>(Op)) 230*06f32e7eSjoerg map(Op); 231*06f32e7eSjoerg } 232*06f32e7eSjoerg } 233*06f32e7eSjoerg 234*06f32e7eSjoerg void ValueMapping::map(const Value *V) { 235*06f32e7eSjoerg if (IDs.lookup(V)) 236*06f32e7eSjoerg return; 237*06f32e7eSjoerg 238*06f32e7eSjoerg if (auto *C = dyn_cast<Constant>(V)) 239*06f32e7eSjoerg if (!isa<GlobalValue>(C)) 240*06f32e7eSjoerg for (const Value *Op : C->operands()) 241*06f32e7eSjoerg map(Op); 242*06f32e7eSjoerg 243*06f32e7eSjoerg Values.push_back(V); 244*06f32e7eSjoerg IDs[V] = Values.size(); 245*06f32e7eSjoerg } 246*06f32e7eSjoerg 247*06f32e7eSjoerg #ifndef NDEBUG 248*06f32e7eSjoerg static void dumpMapping(const ValueMapping &VM) { 249*06f32e7eSjoerg dbgs() << "value-mapping (size = " << VM.Values.size() << "):\n"; 250*06f32e7eSjoerg for (unsigned I = 0, E = VM.Values.size(); I != E; ++I) { 251*06f32e7eSjoerg dbgs() << " - id = " << I << ", value = "; 252*06f32e7eSjoerg VM.Values[I]->dump(); 253*06f32e7eSjoerg } 254*06f32e7eSjoerg } 255*06f32e7eSjoerg 256*06f32e7eSjoerg static void debugValue(const ValueMapping &M, unsigned I, StringRef Desc) { 257*06f32e7eSjoerg const Value *V = M.Values[I]; 258*06f32e7eSjoerg dbgs() << " - " << Desc << " value = "; 259*06f32e7eSjoerg V->dump(); 260*06f32e7eSjoerg for (const Use &U : V->uses()) { 261*06f32e7eSjoerg dbgs() << " => use: op = " << U.getOperandNo() 262*06f32e7eSjoerg << ", user-id = " << M.IDs.lookup(U.getUser()) << ", user = "; 263*06f32e7eSjoerg U.getUser()->dump(); 264*06f32e7eSjoerg } 265*06f32e7eSjoerg } 266*06f32e7eSjoerg 267*06f32e7eSjoerg static void debugUserMismatch(const ValueMapping &L, const ValueMapping &R, 268*06f32e7eSjoerg unsigned I) { 269*06f32e7eSjoerg dbgs() << " - fail: user mismatch: ID = " << I << "\n"; 270*06f32e7eSjoerg debugValue(L, I, "LHS"); 271*06f32e7eSjoerg debugValue(R, I, "RHS"); 272*06f32e7eSjoerg 273*06f32e7eSjoerg dbgs() << "\nlhs-"; 274*06f32e7eSjoerg dumpMapping(L); 275*06f32e7eSjoerg dbgs() << "\nrhs-"; 276*06f32e7eSjoerg dumpMapping(R); 277*06f32e7eSjoerg } 278*06f32e7eSjoerg 279*06f32e7eSjoerg static void debugSizeMismatch(const ValueMapping &L, const ValueMapping &R) { 280*06f32e7eSjoerg dbgs() << " - fail: map size: " << L.Values.size() 281*06f32e7eSjoerg << " != " << R.Values.size() << "\n"; 282*06f32e7eSjoerg dbgs() << "\nlhs-"; 283*06f32e7eSjoerg dumpMapping(L); 284*06f32e7eSjoerg dbgs() << "\nrhs-"; 285*06f32e7eSjoerg dumpMapping(R); 286*06f32e7eSjoerg } 287*06f32e7eSjoerg #endif 288*06f32e7eSjoerg 289*06f32e7eSjoerg static bool matches(const ValueMapping &LM, const ValueMapping &RM) { 290*06f32e7eSjoerg LLVM_DEBUG(dbgs() << "compare value maps\n"); 291*06f32e7eSjoerg if (LM.Values.size() != RM.Values.size()) { 292*06f32e7eSjoerg LLVM_DEBUG(debugSizeMismatch(LM, RM)); 293*06f32e7eSjoerg return false; 294*06f32e7eSjoerg } 295*06f32e7eSjoerg 296*06f32e7eSjoerg // This mapping doesn't include dangling constant users, since those don't 297*06f32e7eSjoerg // get serialized. However, checking if users are constant and calling 298*06f32e7eSjoerg // isConstantUsed() on every one is very expensive. Instead, just check if 299*06f32e7eSjoerg // the user is mapped. 300*06f32e7eSjoerg auto skipUnmappedUsers = 301*06f32e7eSjoerg [&](Value::const_use_iterator &U, Value::const_use_iterator E, 302*06f32e7eSjoerg const ValueMapping &M) { 303*06f32e7eSjoerg while (U != E && !M.lookup(U->getUser())) 304*06f32e7eSjoerg ++U; 305*06f32e7eSjoerg }; 306*06f32e7eSjoerg 307*06f32e7eSjoerg // Iterate through all values, and check that both mappings have the same 308*06f32e7eSjoerg // users. 309*06f32e7eSjoerg for (unsigned I = 0, E = LM.Values.size(); I != E; ++I) { 310*06f32e7eSjoerg const Value *L = LM.Values[I]; 311*06f32e7eSjoerg const Value *R = RM.Values[I]; 312*06f32e7eSjoerg auto LU = L->use_begin(), LE = L->use_end(); 313*06f32e7eSjoerg auto RU = R->use_begin(), RE = R->use_end(); 314*06f32e7eSjoerg skipUnmappedUsers(LU, LE, LM); 315*06f32e7eSjoerg skipUnmappedUsers(RU, RE, RM); 316*06f32e7eSjoerg 317*06f32e7eSjoerg while (LU != LE) { 318*06f32e7eSjoerg if (RU == RE) { 319*06f32e7eSjoerg LLVM_DEBUG(debugUserMismatch(LM, RM, I)); 320*06f32e7eSjoerg return false; 321*06f32e7eSjoerg } 322*06f32e7eSjoerg if (LM.lookup(LU->getUser()) != RM.lookup(RU->getUser())) { 323*06f32e7eSjoerg LLVM_DEBUG(debugUserMismatch(LM, RM, I)); 324*06f32e7eSjoerg return false; 325*06f32e7eSjoerg } 326*06f32e7eSjoerg if (LU->getOperandNo() != RU->getOperandNo()) { 327*06f32e7eSjoerg LLVM_DEBUG(debugUserMismatch(LM, RM, I)); 328*06f32e7eSjoerg return false; 329*06f32e7eSjoerg } 330*06f32e7eSjoerg skipUnmappedUsers(++LU, LE, LM); 331*06f32e7eSjoerg skipUnmappedUsers(++RU, RE, RM); 332*06f32e7eSjoerg } 333*06f32e7eSjoerg if (RU != RE) { 334*06f32e7eSjoerg LLVM_DEBUG(debugUserMismatch(LM, RM, I)); 335*06f32e7eSjoerg return false; 336*06f32e7eSjoerg } 337*06f32e7eSjoerg } 338*06f32e7eSjoerg 339*06f32e7eSjoerg return true; 340*06f32e7eSjoerg } 341*06f32e7eSjoerg 342*06f32e7eSjoerg static void verifyAfterRoundTrip(const Module &M, 343*06f32e7eSjoerg std::unique_ptr<Module> OtherM) { 344*06f32e7eSjoerg if (!OtherM) 345*06f32e7eSjoerg report_fatal_error("parsing failed"); 346*06f32e7eSjoerg if (verifyModule(*OtherM, &errs())) 347*06f32e7eSjoerg report_fatal_error("verification failed"); 348*06f32e7eSjoerg if (!matches(ValueMapping(M), ValueMapping(*OtherM))) 349*06f32e7eSjoerg report_fatal_error("use-list order changed"); 350*06f32e7eSjoerg } 351*06f32e7eSjoerg 352*06f32e7eSjoerg static void verifyBitcodeUseListOrder(const Module &M) { 353*06f32e7eSjoerg TempFile F; 354*06f32e7eSjoerg if (F.init("bc")) 355*06f32e7eSjoerg report_fatal_error("failed to initialize bitcode file"); 356*06f32e7eSjoerg 357*06f32e7eSjoerg if (F.writeBitcode(M)) 358*06f32e7eSjoerg report_fatal_error("failed to write bitcode"); 359*06f32e7eSjoerg 360*06f32e7eSjoerg LLVMContext Context; 361*06f32e7eSjoerg verifyAfterRoundTrip(M, F.readBitcode(Context)); 362*06f32e7eSjoerg } 363*06f32e7eSjoerg 364*06f32e7eSjoerg static void verifyAssemblyUseListOrder(const Module &M) { 365*06f32e7eSjoerg TempFile F; 366*06f32e7eSjoerg if (F.init("ll")) 367*06f32e7eSjoerg report_fatal_error("failed to initialize assembly file"); 368*06f32e7eSjoerg 369*06f32e7eSjoerg if (F.writeAssembly(M)) 370*06f32e7eSjoerg report_fatal_error("failed to write assembly"); 371*06f32e7eSjoerg 372*06f32e7eSjoerg LLVMContext Context; 373*06f32e7eSjoerg verifyAfterRoundTrip(M, F.readAssembly(Context)); 374*06f32e7eSjoerg } 375*06f32e7eSjoerg 376*06f32e7eSjoerg static void verifyUseListOrder(const Module &M) { 377*06f32e7eSjoerg outs() << "verify bitcode\n"; 378*06f32e7eSjoerg verifyBitcodeUseListOrder(M); 379*06f32e7eSjoerg outs() << "verify assembly\n"; 380*06f32e7eSjoerg verifyAssemblyUseListOrder(M); 381*06f32e7eSjoerg } 382*06f32e7eSjoerg 383*06f32e7eSjoerg static void shuffleValueUseLists(Value *V, std::minstd_rand0 &Gen, 384*06f32e7eSjoerg DenseSet<Value *> &Seen) { 385*06f32e7eSjoerg if (!Seen.insert(V).second) 386*06f32e7eSjoerg return; 387*06f32e7eSjoerg 388*06f32e7eSjoerg if (auto *C = dyn_cast<Constant>(V)) 389*06f32e7eSjoerg if (!isa<GlobalValue>(C)) 390*06f32e7eSjoerg for (Value *Op : C->operands()) 391*06f32e7eSjoerg shuffleValueUseLists(Op, Gen, Seen); 392*06f32e7eSjoerg 393*06f32e7eSjoerg if (V->use_empty() || std::next(V->use_begin()) == V->use_end()) 394*06f32e7eSjoerg // Nothing to shuffle for 0 or 1 users. 395*06f32e7eSjoerg return; 396*06f32e7eSjoerg 397*06f32e7eSjoerg // Generate random numbers between 10 and 99, which will line up nicely in 398*06f32e7eSjoerg // debug output. We're not worried about collisons here. 399*06f32e7eSjoerg LLVM_DEBUG(dbgs() << "V = "; V->dump()); 400*06f32e7eSjoerg std::uniform_int_distribution<short> Dist(10, 99); 401*06f32e7eSjoerg SmallDenseMap<const Use *, short, 16> Order; 402*06f32e7eSjoerg auto compareUses = 403*06f32e7eSjoerg [&Order](const Use &L, const Use &R) { return Order[&L] < Order[&R]; }; 404*06f32e7eSjoerg do { 405*06f32e7eSjoerg for (const Use &U : V->uses()) { 406*06f32e7eSjoerg auto I = Dist(Gen); 407*06f32e7eSjoerg Order[&U] = I; 408*06f32e7eSjoerg LLVM_DEBUG(dbgs() << " - order: " << I << ", op = " << U.getOperandNo() 409*06f32e7eSjoerg << ", U = "; 410*06f32e7eSjoerg U.getUser()->dump()); 411*06f32e7eSjoerg } 412*06f32e7eSjoerg } while (std::is_sorted(V->use_begin(), V->use_end(), compareUses)); 413*06f32e7eSjoerg 414*06f32e7eSjoerg LLVM_DEBUG(dbgs() << " => shuffle\n"); 415*06f32e7eSjoerg V->sortUseList(compareUses); 416*06f32e7eSjoerg 417*06f32e7eSjoerg LLVM_DEBUG({ 418*06f32e7eSjoerg for (const Use &U : V->uses()) { 419*06f32e7eSjoerg dbgs() << " - order: " << Order.lookup(&U) 420*06f32e7eSjoerg << ", op = " << U.getOperandNo() << ", U = "; 421*06f32e7eSjoerg U.getUser()->dump(); 422*06f32e7eSjoerg } 423*06f32e7eSjoerg }); 424*06f32e7eSjoerg } 425*06f32e7eSjoerg 426*06f32e7eSjoerg static void reverseValueUseLists(Value *V, DenseSet<Value *> &Seen) { 427*06f32e7eSjoerg if (!Seen.insert(V).second) 428*06f32e7eSjoerg return; 429*06f32e7eSjoerg 430*06f32e7eSjoerg if (auto *C = dyn_cast<Constant>(V)) 431*06f32e7eSjoerg if (!isa<GlobalValue>(C)) 432*06f32e7eSjoerg for (Value *Op : C->operands()) 433*06f32e7eSjoerg reverseValueUseLists(Op, Seen); 434*06f32e7eSjoerg 435*06f32e7eSjoerg if (V->use_empty() || std::next(V->use_begin()) == V->use_end()) 436*06f32e7eSjoerg // Nothing to shuffle for 0 or 1 users. 437*06f32e7eSjoerg return; 438*06f32e7eSjoerg 439*06f32e7eSjoerg LLVM_DEBUG({ 440*06f32e7eSjoerg dbgs() << "V = "; 441*06f32e7eSjoerg V->dump(); 442*06f32e7eSjoerg for (const Use &U : V->uses()) { 443*06f32e7eSjoerg dbgs() << " - order: op = " << U.getOperandNo() << ", U = "; 444*06f32e7eSjoerg U.getUser()->dump(); 445*06f32e7eSjoerg } 446*06f32e7eSjoerg dbgs() << " => reverse\n"; 447*06f32e7eSjoerg }); 448*06f32e7eSjoerg 449*06f32e7eSjoerg V->reverseUseList(); 450*06f32e7eSjoerg 451*06f32e7eSjoerg LLVM_DEBUG({ 452*06f32e7eSjoerg for (const Use &U : V->uses()) { 453*06f32e7eSjoerg dbgs() << " - order: op = " << U.getOperandNo() << ", U = "; 454*06f32e7eSjoerg U.getUser()->dump(); 455*06f32e7eSjoerg } 456*06f32e7eSjoerg }); 457*06f32e7eSjoerg } 458*06f32e7eSjoerg 459*06f32e7eSjoerg template <class Changer> 460*06f32e7eSjoerg static void changeUseLists(Module &M, Changer changeValueUseList) { 461*06f32e7eSjoerg // Visit every value that would be serialized to an IR file. 462*06f32e7eSjoerg // 463*06f32e7eSjoerg // Globals. 464*06f32e7eSjoerg for (GlobalVariable &G : M.globals()) 465*06f32e7eSjoerg changeValueUseList(&G); 466*06f32e7eSjoerg for (GlobalAlias &A : M.aliases()) 467*06f32e7eSjoerg changeValueUseList(&A); 468*06f32e7eSjoerg for (GlobalIFunc &IF : M.ifuncs()) 469*06f32e7eSjoerg changeValueUseList(&IF); 470*06f32e7eSjoerg for (Function &F : M) 471*06f32e7eSjoerg changeValueUseList(&F); 472*06f32e7eSjoerg 473*06f32e7eSjoerg // Constants used by globals. 474*06f32e7eSjoerg for (GlobalVariable &G : M.globals()) 475*06f32e7eSjoerg if (G.hasInitializer()) 476*06f32e7eSjoerg changeValueUseList(G.getInitializer()); 477*06f32e7eSjoerg for (GlobalAlias &A : M.aliases()) 478*06f32e7eSjoerg changeValueUseList(A.getAliasee()); 479*06f32e7eSjoerg for (GlobalIFunc &IF : M.ifuncs()) 480*06f32e7eSjoerg changeValueUseList(IF.getResolver()); 481*06f32e7eSjoerg for (Function &F : M) { 482*06f32e7eSjoerg if (F.hasPrefixData()) 483*06f32e7eSjoerg changeValueUseList(F.getPrefixData()); 484*06f32e7eSjoerg if (F.hasPrologueData()) 485*06f32e7eSjoerg changeValueUseList(F.getPrologueData()); 486*06f32e7eSjoerg if (F.hasPersonalityFn()) 487*06f32e7eSjoerg changeValueUseList(F.getPersonalityFn()); 488*06f32e7eSjoerg } 489*06f32e7eSjoerg 490*06f32e7eSjoerg // Function bodies. 491*06f32e7eSjoerg for (Function &F : M) { 492*06f32e7eSjoerg for (Argument &A : F.args()) 493*06f32e7eSjoerg changeValueUseList(&A); 494*06f32e7eSjoerg for (BasicBlock &BB : F) 495*06f32e7eSjoerg changeValueUseList(&BB); 496*06f32e7eSjoerg for (BasicBlock &BB : F) 497*06f32e7eSjoerg for (Instruction &I : BB) 498*06f32e7eSjoerg changeValueUseList(&I); 499*06f32e7eSjoerg 500*06f32e7eSjoerg // Constants used by instructions. 501*06f32e7eSjoerg for (BasicBlock &BB : F) 502*06f32e7eSjoerg for (Instruction &I : BB) 503*06f32e7eSjoerg for (Value *Op : I.operands()) 504*06f32e7eSjoerg if ((isa<Constant>(Op) && !isa<GlobalValue>(*Op)) || 505*06f32e7eSjoerg isa<InlineAsm>(Op)) 506*06f32e7eSjoerg changeValueUseList(Op); 507*06f32e7eSjoerg } 508*06f32e7eSjoerg 509*06f32e7eSjoerg if (verifyModule(M, &errs())) 510*06f32e7eSjoerg report_fatal_error("verification failed"); 511*06f32e7eSjoerg } 512*06f32e7eSjoerg 513*06f32e7eSjoerg static void shuffleUseLists(Module &M, unsigned SeedOffset) { 514*06f32e7eSjoerg std::minstd_rand0 Gen(std::minstd_rand0::default_seed + SeedOffset); 515*06f32e7eSjoerg DenseSet<Value *> Seen; 516*06f32e7eSjoerg changeUseLists(M, [&](Value *V) { shuffleValueUseLists(V, Gen, Seen); }); 517*06f32e7eSjoerg LLVM_DEBUG(dbgs() << "\n"); 518*06f32e7eSjoerg } 519*06f32e7eSjoerg 520*06f32e7eSjoerg static void reverseUseLists(Module &M) { 521*06f32e7eSjoerg DenseSet<Value *> Seen; 522*06f32e7eSjoerg changeUseLists(M, [&](Value *V) { reverseValueUseLists(V, Seen); }); 523*06f32e7eSjoerg LLVM_DEBUG(dbgs() << "\n"); 524*06f32e7eSjoerg } 525*06f32e7eSjoerg 526*06f32e7eSjoerg int main(int argc, char **argv) { 527*06f32e7eSjoerg InitLLVM X(argc, argv); 528*06f32e7eSjoerg 529*06f32e7eSjoerg // Enable debug stream buffering. 530*06f32e7eSjoerg EnableDebugBuffering = true; 531*06f32e7eSjoerg 532*06f32e7eSjoerg LLVMContext Context; 533*06f32e7eSjoerg 534*06f32e7eSjoerg cl::ParseCommandLineOptions(argc, argv, 535*06f32e7eSjoerg "llvm tool to verify use-list order\n"); 536*06f32e7eSjoerg 537*06f32e7eSjoerg SMDiagnostic Err; 538*06f32e7eSjoerg 539*06f32e7eSjoerg // Load the input module... 540*06f32e7eSjoerg std::unique_ptr<Module> M = parseIRFile(InputFilename, Err, Context); 541*06f32e7eSjoerg 542*06f32e7eSjoerg if (!M.get()) { 543*06f32e7eSjoerg Err.print(argv[0], errs()); 544*06f32e7eSjoerg return 1; 545*06f32e7eSjoerg } 546*06f32e7eSjoerg if (verifyModule(*M, &errs())) { 547*06f32e7eSjoerg errs() << argv[0] << ": " << InputFilename 548*06f32e7eSjoerg << ": error: input module is broken!\n"; 549*06f32e7eSjoerg return 1; 550*06f32e7eSjoerg } 551*06f32e7eSjoerg 552*06f32e7eSjoerg // Verify the use lists now and after reversing them. 553*06f32e7eSjoerg outs() << "*** verify-uselistorder ***\n"; 554*06f32e7eSjoerg verifyUseListOrder(*M); 555*06f32e7eSjoerg outs() << "reverse\n"; 556*06f32e7eSjoerg reverseUseLists(*M); 557*06f32e7eSjoerg verifyUseListOrder(*M); 558*06f32e7eSjoerg 559*06f32e7eSjoerg for (unsigned I = 0, E = NumShuffles; I != E; ++I) { 560*06f32e7eSjoerg outs() << "\n"; 561*06f32e7eSjoerg 562*06f32e7eSjoerg // Shuffle with a different (deterministic) seed each time. 563*06f32e7eSjoerg outs() << "shuffle (" << I + 1 << " of " << E << ")\n"; 564*06f32e7eSjoerg shuffleUseLists(*M, I); 565*06f32e7eSjoerg 566*06f32e7eSjoerg // Verify again before and after reversing. 567*06f32e7eSjoerg verifyUseListOrder(*M); 568*06f32e7eSjoerg outs() << "reverse\n"; 569*06f32e7eSjoerg reverseUseLists(*M); 570*06f32e7eSjoerg verifyUseListOrder(*M); 571*06f32e7eSjoerg } 572*06f32e7eSjoerg 573*06f32e7eSjoerg return 0; 574*06f32e7eSjoerg } 575