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