1 //===- VerifyUseListOrder.cpp - Use List Order Verifier ---------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Pass to verify use-list order doesn't change after serialization.
12 // Despite it being a verifier, this pass *does* transform the module, since it
13 // shuffles the use-list of every value.
15 //===----------------------------------------------------------------------===//
17 #include "llvm/Transforms/IPO.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/AsmParser/Parser.h"
21 #include "llvm/Bitcode/ReaderWriter.h"
22 #include "llvm/IR/LLVMContext.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/IR/UseListOrder.h"
25 #include "llvm/Pass.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/ErrorHandling.h"
28 #include "llvm/Support/FileSystem.h"
29 #include "llvm/Support/FileUtilities.h"
30 #include "llvm/Support/MemoryBuffer.h"
31 #include "llvm/Support/SourceMgr.h"
35 #define DEBUG_TYPE "use-list-order"
42 bool init(const std::string &Ext);
43 bool writeBitcode(const Module &M) const;
44 bool writeAssembly(const Module &M) const;
45 std::unique_ptr<Module> readBitcode(LLVMContext &Context) const;
46 std::unique_ptr<Module> readAssembly(LLVMContext &Context) const;
50 DenseMap<const Value *, unsigned> IDs;
51 std::vector<const Value *> Values;
53 /// \brief Construct a value mapping for module.
55 /// Creates mapping from every value in \c M to an ID. This mapping includes
56 /// un-referencable values.
58 /// Every \a Value that gets serialized in some way should be represented
59 /// here. The order needs to be deterministic, but it's unnecessary to match
60 /// the value-ids in the bitcode writer.
62 /// All constants that are referenced by other values are included in the
63 /// mapping, but others -- which wouldn't be serialized -- are not.
64 ValueMapping(const Module &M);
66 /// \brief Map a value.
68 /// Maps a value. If it's a constant, maps all of its operands first.
69 void map(const Value *V);
70 unsigned lookup(const Value *V) const { return IDs.lookup(V); }
75 bool TempFile::init(const std::string &Ext) {
76 SmallVector<char, 64> Vector;
77 DEBUG(dbgs() << " - create-temp-file\n");
78 if (auto EC = sys::fs::createTemporaryFile("use-list-order", Ext, Vector)) {
80 DEBUG(dbgs() << "error: " << EC.message() << "\n");
83 assert(!Vector.empty());
85 Filename.assign(Vector.data(), Vector.data() + Vector.size());
86 Remover.setFile(Filename);
87 DEBUG(dbgs() << " - filename = " << Filename << "\n");
91 bool TempFile::writeBitcode(const Module &M) const {
92 DEBUG(dbgs() << " - write bitcode\n");
93 std::string ErrorInfo;
94 raw_fd_ostream OS(Filename.c_str(), ErrorInfo, sys::fs::F_None);
95 if (!ErrorInfo.empty()) {
96 DEBUG(dbgs() << "error: " << ErrorInfo << "\n");
100 WriteBitcodeToFile(&M, OS);
104 bool TempFile::writeAssembly(const Module &M) const {
105 DEBUG(dbgs() << " - write assembly\n");
106 std::string ErrorInfo;
107 raw_fd_ostream OS(Filename.c_str(), ErrorInfo, sys::fs::F_Text);
108 if (!ErrorInfo.empty()) {
109 DEBUG(dbgs() << "error: " << ErrorInfo << "\n");
117 std::unique_ptr<Module> TempFile::readBitcode(LLVMContext &Context) const {
118 DEBUG(dbgs() << " - read bitcode\n");
119 ErrorOr<std::unique_ptr<MemoryBuffer>> BufferOr =
120 MemoryBuffer::getFile(Filename);
122 DEBUG(dbgs() << "error: " << BufferOr.getError().message() << "\n");
126 std::unique_ptr<MemoryBuffer> Buffer = std::move(BufferOr.get());
127 ErrorOr<Module *> ModuleOr = parseBitcodeFile(Buffer.release(), Context);
129 DEBUG(dbgs() << "error: " << ModuleOr.getError().message() << "\n");
132 return std::unique_ptr<Module>(ModuleOr.get());
135 std::unique_ptr<Module> TempFile::readAssembly(LLVMContext &Context) const {
136 DEBUG(dbgs() << " - read assembly\n");
138 std::unique_ptr<Module> M(ParseAssemblyFile(Filename, Err, Context));
140 DEBUG(dbgs() << "error: "; Err.print("verify-use-list-order", dbgs()));
144 ValueMapping::ValueMapping(const Module &M) {
145 // Every value should be mapped, including things like void instructions and
146 // basic blocks that are kept out of the ValueEnumerator.
148 // The current mapping order makes it easier to debug the tables. It happens
149 // to be similar to the ID mapping when writing ValueEnumerator, but they
150 // aren't (and needn't be) in sync.
153 for (const GlobalVariable &G : M.globals())
155 for (const GlobalAlias &A : M.aliases())
157 for (const Function &F : M)
160 // Constants used by globals.
161 for (const GlobalVariable &G : M.globals())
162 if (G.hasInitializer())
163 map(G.getInitializer());
164 for (const GlobalAlias &A : M.aliases())
166 for (const Function &F : M)
167 if (F.hasPrefixData())
168 map(F.getPrefixData());
171 for (const Function &F : M) {
172 for (const Argument &A : F.args())
174 for (const BasicBlock &BB : F)
176 for (const BasicBlock &BB : F)
177 for (const Instruction &I : BB)
180 // Constants used by instructions.
181 for (const BasicBlock &BB : F)
182 for (const Instruction &I : BB)
183 for (const Value *Op : I.operands())
184 if ((isa<Constant>(Op) && !isa<GlobalValue>(*Op)) ||
190 void ValueMapping::map(const Value *V) {
194 if (auto *C = dyn_cast<Constant>(V))
195 if (!isa<GlobalValue>(C))
196 for (const Value *Op : C->operands())
200 IDs[V] = Values.size();
204 static void dumpMapping(const ValueMapping &VM) {
205 dbgs() << "value-mapping (size = " << VM.Values.size() << "):\n";
206 for (unsigned I = 0, E = VM.Values.size(); I != E; ++I) {
207 dbgs() << " - id = " << I << ", value = ";
208 VM.Values[I]->dump();
212 static void debugValue(const ValueMapping &M, unsigned I, StringRef Desc) {
213 const Value *V = M.Values[I];
214 dbgs() << " - " << Desc << " value = ";
216 for (const Use &U : V->uses()) {
217 dbgs() << " => use: op = " << U.getOperandNo()
218 << ", user-id = " << M.IDs.lookup(U.getUser()) << ", user = ";
223 static void debugUserMismatch(const ValueMapping &L, const ValueMapping &R,
225 dbgs() << " - fail: user mismatch: ID = " << I << "\n";
226 debugValue(L, I, "LHS");
227 debugValue(R, I, "RHS");
235 static void debugSizeMismatch(const ValueMapping &L, const ValueMapping &R) {
236 dbgs() << " - fail: map size: " << L.Values.size()
237 << " != " << R.Values.size() << "\n";
245 static bool matches(const ValueMapping &LM, const ValueMapping &RM) {
246 DEBUG(dbgs() << "compare value maps\n");
247 if (LM.Values.size() != RM.Values.size()) {
248 DEBUG(debugSizeMismatch(LM, RM));
252 // This mapping doesn't include dangling constant users, since those don't
253 // get serialized. However, checking if users are constant and calling
254 // isConstantUsed() on every one is very expensive. Instead, just check if
255 // the user is mapped.
256 auto skipUnmappedUsers =
257 [&](Value::const_use_iterator &U, Value::const_use_iterator E,
258 const ValueMapping &M) {
259 while (U != E && !M.lookup(U->getUser()))
263 // Iterate through all values, and check that both mappings have the same
265 for (unsigned I = 0, E = LM.Values.size(); I != E; ++I) {
266 const Value *L = LM.Values[I];
267 const Value *R = RM.Values[I];
268 auto LU = L->use_begin(), LE = L->use_end();
269 auto RU = R->use_begin(), RE = R->use_end();
270 skipUnmappedUsers(LU, LE, LM);
271 skipUnmappedUsers(RU, RE, RM);
275 DEBUG(debugUserMismatch(LM, RM, I));
278 if (LM.lookup(LU->getUser()) != RM.lookup(RU->getUser())) {
279 DEBUG(debugUserMismatch(LM, RM, I));
282 if (LU->getOperandNo() != RU->getOperandNo()) {
283 DEBUG(debugUserMismatch(LM, RM, I));
286 skipUnmappedUsers(++LU, LE, LM);
287 skipUnmappedUsers(++RU, RE, RM);
290 DEBUG(debugUserMismatch(LM, RM, I));
298 static bool verifyBitcodeUseListOrder(const Module &M) {
299 DEBUG(dbgs() << "*** verify-use-list-order: bitcode ***\n");
304 if (F.writeBitcode(M))
308 std::unique_ptr<Module> OtherM = F.readBitcode(Context);
312 return matches(ValueMapping(M), ValueMapping(*OtherM));
315 static bool verifyAssemblyUseListOrder(const Module &M) {
316 DEBUG(dbgs() << "*** verify-use-list-order: assembly ***\n");
321 if (F.writeAssembly(M))
325 std::unique_ptr<Module> OtherM = F.readAssembly(Context);
329 return matches(ValueMapping(M), ValueMapping(*OtherM));
333 class VerifyUseListOrder : public ModulePass {
336 VerifyUseListOrder();
337 bool runOnModule(Module &M) override;
339 } // end anonymous namespace
341 char VerifyUseListOrder::ID = 0;
342 INITIALIZE_PASS(VerifyUseListOrder, "verify-use-list-order",
343 "Verify Use List Order", false, false)
344 VerifyUseListOrder::VerifyUseListOrder() : ModulePass(ID) {
345 initializeVerifyUseListOrderPass(*PassRegistry::getPassRegistry());
348 bool VerifyUseListOrder::runOnModule(Module &M) {
349 DEBUG(dbgs() << "*** verify-use-list-order ***\n");
350 if (!shouldPreserveBitcodeUseListOrder()) {
351 // Can't verify if order isn't preserved.
352 DEBUG(dbgs() << "warning: cannot verify bitcode; "
353 "try -preserve-bc-use-list-order\n");
358 if (!verifyBitcodeUseListOrder(M))
359 report_fatal_error("bitcode use-list order changed");
361 if (shouldPreserveBitcodeUseListOrder())
362 if (!verifyAssemblyUseListOrder(M))
363 report_fatal_error("assembly use-list order changed");
368 ModulePass *llvm::createVerifyUseListOrderPass() {
369 return new VerifyUseListOrder;