lib/IR/UseListOrder.cpp

   1 //===- UseListOrder.cpp - Implement Use List Order functions --------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Implement use list order functions to modify use-list order and verify it
  11 // doesn't change after serialization.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/IR/UseListOrder.h"
  16
  17 #include "llvm/ADT/DenseMap.h"
  18 #include "llvm/ADT/DenseSet.h"
  19 #include "llvm/AsmParser/Parser.h"
  20 #include "llvm/Bitcode/ReaderWriter.h"
  21 #include "llvm/IR/LLVMContext.h"
  22 #include "llvm/IR/Module.h"
  23 #include "llvm/Support/CommandLine.h"
  24 #include "llvm/Support/Debug.h"
  25 #include "llvm/Support/FileSystem.h"
  26 #include "llvm/Support/FileUtilities.h"
  27 #include "llvm/Support/MemoryBuffer.h"
  28 #include "llvm/Support/SourceMgr.h"
  29
  30 #include <random>
  31 #include <vector>
  32
  33 #define DEBUG_TYPE "use-list-order"
  34
  35 using namespace llvm;
  36
  37 static cl::opt<bool> PreserveBitcodeUseListOrder(
  38     "preserve-bc-use-list-order",
  39     cl::desc("Experimental support to preserve bitcode use-list order."),
  40     cl::init(false), cl::Hidden);
  41
  42 bool llvm::shouldPreserveBitcodeUseListOrder() {
  43   return PreserveBitcodeUseListOrder;
  44 }
  45
  46 static void shuffleValueUseLists(Value *V, std::minstd_rand0 &Gen,
  47                                  DenseSet<Value *> &Seen) {
  48   if (!Seen.insert(V).second)
  49     return;
  50
  51   if (auto *C = dyn_cast<Constant>(V))
  52     if (!isa<GlobalValue>(C))
  53       for (Value *Op : C->operands())
  54         shuffleValueUseLists(Op, Gen, Seen);
  55
  56   if (V->use_empty() || std::next(V->use_begin()) == V->use_end())
  57     // Nothing to shuffle for 0 or 1 users.
  58     return;
  59
  60   // Generate random numbers between 10 and 99, which will line up nicely in
  61   // debug output.  We're not worried about collisons here.
  62   DEBUG(dbgs() << "V = "; V->dump());
  63   std::uniform_int_distribution<short> Dist(10, 99);
  64   SmallDenseMap<const Use *, short, 16> Order;
  65   for (const Use &U : V->uses()) {
  66     auto I = Dist(Gen);
  67     Order[&U] = I;
  68     DEBUG(dbgs() << " - order: " << I << ", U = "; U.getUser()->dump());
  69   }
  70
  71   DEBUG(dbgs() << " => shuffle\n");
  72   V->sortUseList(
  73       [&Order](const Use &L, const Use &R) { return Order[&L] < Order[&R]; });
  74
  75   DEBUG({
  76     for (const Use &U : V->uses())
  77       DEBUG(dbgs() << " - order: " << Order.lookup(&U) << ", U = ";
  78             U.getUser()->dump());
  79   });
  80 }
  81
  82 void llvm::shuffleUseLists(Module &M, unsigned SeedOffset) {
  83   DEBUG(dbgs() << "*** shuffle-use-lists ***\n");
  84   std::minstd_rand0 Gen(std::minstd_rand0::default_seed + SeedOffset);
  85   DenseSet<Value *> Seen;
  86
  87   // Shuffle the use-list of each value that would be serialized to an IR file
  88   // (bitcode or assembly).
  89   auto shuffle = [&](Value *V) { shuffleValueUseLists(V, Gen, Seen); };
  90
  91   // Globals.
  92   for (GlobalVariable &G : M.globals())
  93     shuffle(&G);
  94   for (GlobalAlias &A : M.aliases())
  95     shuffle(&A);
  96   for (Function &F : M)
  97     shuffle(&F);
  98
  99   // Constants used by globals.
 100   for (GlobalVariable &G : M.globals())
 101     if (G.hasInitializer())
 102       shuffle(G.getInitializer());
 103   for (GlobalAlias &A : M.aliases())
 104     shuffle(A.getAliasee());
 105   for (Function &F : M)
 106     if (F.hasPrefixData())
 107       shuffle(F.getPrefixData());
 108
 109   // Function bodies.
 110   for (Function &F : M) {
 111     for (Argument &A : F.args())
 112       shuffle(&A);
 113     for (BasicBlock &BB : F)
 114       shuffle(&BB);
 115     for (BasicBlock &BB : F)
 116       for (Instruction &I : BB)
 117         shuffle(&I);
 118
 119     // Constants used by instructions.
 120     for (BasicBlock &BB : F)
 121       for (Instruction &I : BB)
 122         for (Value *Op : I.operands())
 123           if ((isa<Constant>(Op) && !isa<GlobalValue>(*Op)) ||
 124               isa<InlineAsm>(Op))
 125             shuffle(Op);
 126   }
 127
 128   DEBUG(dbgs() << "\n");
 129 }
 130
 131 namespace {
 132
 133 struct TempFile {
 134   std::string Filename;
 135   FileRemover Remover;
 136   bool init(const std::string &Ext);
 137   bool writeBitcode(const Module &M) const;
 138   bool writeAssembly(const Module &M) const;
 139   std::unique_ptr<Module> readBitcode(LLVMContext &Context) const;
 140   std::unique_ptr<Module> readAssembly(LLVMContext &Context) const;
 141 };
 142
 143 struct ValueMapping {
 144   DenseMap<const Value *, unsigned> IDs;
 145   std::vector<const Value *> Values;
 146
 147   /// \brief Construct a value mapping for module.
 148   ///
 149   /// Creates mapping from every value in \c M to an ID.  This mapping includes
 150   /// un-referencable values.
 151   ///
 152   /// Every \a Value that gets serialized in some way should be represented
 153   /// here.  The order needs to be deterministic, but it's unnecessary to match
 154   /// the value-ids in the bitcode writer.
 155   ///
 156   /// All constants that are referenced by other values are included in the
 157   /// mapping, but others -- which wouldn't be serialized -- are not.
 158   ValueMapping(const Module &M);
 159
 160   /// \brief Map a value.
 161   ///
 162   /// Maps a value.  If it's a constant, maps all of its operands first.
 163   void map(const Value *V);
 164   unsigned lookup(const Value *V) const { return IDs.lookup(V); }
 165 };
 166
 167 } // end namespace
 168
 169 bool TempFile::init(const std::string &Ext) {
 170   SmallVector<char, 64> Vector;
 171   DEBUG(dbgs() << " - create-temp-file\n");
 172   if (auto EC = sys::fs::createTemporaryFile("use-list-order", Ext, Vector)) {
 173     (void)EC;
 174     DEBUG(dbgs() << "error: " << EC.message() << "\n");
 175     return true;
 176   }
 177   assert(!Vector.empty());
 178
 179   Filename.assign(Vector.data(), Vector.data() + Vector.size());
 180   Remover.setFile(Filename);
 181   DEBUG(dbgs() << " - filename = " << Filename << "\n");
 182   return false;
 183 }
 184
 185 bool TempFile::writeBitcode(const Module &M) const {
 186   DEBUG(dbgs() << " - write bitcode\n");
 187   std::string ErrorInfo;
 188   raw_fd_ostream OS(Filename.c_str(), ErrorInfo, sys::fs::F_None);
 189   if (!ErrorInfo.empty()) {
 190     DEBUG(dbgs() << "error: " << ErrorInfo << "\n");
 191     return true;
 192   }
 193
 194   WriteBitcodeToFile(&M, OS);
 195   return false;
 196 }
 197
 198 bool TempFile::writeAssembly(const Module &M) const {
 199   DEBUG(dbgs() << " - write assembly\n");
 200   std::string ErrorInfo;
 201   raw_fd_ostream OS(Filename.c_str(), ErrorInfo, sys::fs::F_Text);
 202   if (!ErrorInfo.empty()) {
 203     DEBUG(dbgs() << "error: " << ErrorInfo << "\n");
 204     return true;
 205   }
 206
 207   OS << M;
 208   return false;
 209 }
 210
 211 std::unique_ptr<Module> TempFile::readBitcode(LLVMContext &Context) const {
 212   DEBUG(dbgs() << " - read bitcode\n");
 213   ErrorOr<std::unique_ptr<MemoryBuffer>> BufferOr =
 214       MemoryBuffer::getFile(Filename);
 215   if (!BufferOr) {
 216     DEBUG(dbgs() << "error: " << BufferOr.getError().message() << "\n");
 217     return nullptr;
 218   }
 219
 220   std::unique_ptr<MemoryBuffer> Buffer = std::move(BufferOr.get());
 221   ErrorOr<Module *> ModuleOr = parseBitcodeFile(Buffer.release(), Context);
 222   if (!ModuleOr) {
 223     DEBUG(dbgs() << "error: " << ModuleOr.getError().message() << "\n");
 224     return nullptr;
 225   }
 226   return std::unique_ptr<Module>(ModuleOr.get());
 227 }
 228
 229 std::unique_ptr<Module> TempFile::readAssembly(LLVMContext &Context) const {
 230   DEBUG(dbgs() << " - read assembly\n");
 231   SMDiagnostic Err;
 232   std::unique_ptr<Module> M(ParseAssemblyFile(Filename, Err, Context));
 233   if (!M.get())
 234     DEBUG(dbgs() << "error: "; Err.print("verify-use-list-order", dbgs()));
 235   return M;
 236 }
 237
 238 ValueMapping::ValueMapping(const Module &M) {
 239   // Every value should be mapped, including things like void instructions and
 240   // basic blocks that are kept out of the ValueEnumerator.
 241   //
 242   // The current mapping order makes it easier to debug the tables.  It happens
 243   // to be similar to the ID mapping when writing ValueEnumerator, but they
 244   // aren't (and needn't be) in sync.
 245
 246   // Globals.
 247   for (const GlobalVariable &G : M.globals())
 248     map(&G);
 249   for (const GlobalAlias &A : M.aliases())
 250     map(&A);
 251   for (const Function &F : M)
 252     map(&F);
 253
 254   // Constants used by globals.
 255   for (const GlobalVariable &G : M.globals())
 256     if (G.hasInitializer())
 257       map(G.getInitializer());
 258   for (const GlobalAlias &A : M.aliases())
 259     map(A.getAliasee());
 260   for (const Function &F : M)
 261     if (F.hasPrefixData())
 262       map(F.getPrefixData());
 263
 264   // Function bodies.
 265   for (const Function &F : M) {
 266     for (const Argument &A : F.args())
 267       map(&A);
 268     for (const BasicBlock &BB : F)
 269       map(&BB);
 270     for (const BasicBlock &BB : F)
 271       for (const Instruction &I : BB)
 272         map(&I);
 273
 274     // Constants used by instructions.
 275     for (const BasicBlock &BB : F)
 276       for (const Instruction &I : BB)
 277         for (const Value *Op : I.operands())
 278           if ((isa<Constant>(Op) && !isa<GlobalValue>(*Op)) ||
 279               isa<InlineAsm>(Op))
 280             map(Op);
 281   }
 282 }
 283
 284 void ValueMapping::map(const Value *V) {
 285   if (IDs.lookup(V))
 286     return;
 287
 288   if (auto *C = dyn_cast<Constant>(V))
 289     if (!isa<GlobalValue>(C))
 290       for (const Value *Op : C->operands())
 291         map(Op);
 292
 293   Values.push_back(V);
 294   IDs[V] = Values.size();
 295 }
 296
 297 #ifndef NDEBUG
 298 static void dumpMapping(const ValueMapping &VM) {
 299   dbgs() << "value-mapping (size = " << VM.Values.size() << "):\n";
 300   for (unsigned I = 0, E = VM.Values.size(); I != E; ++I) {
 301     dbgs() << " - id = " << I << ", value = ";
 302     VM.Values[I]->dump();
 303   }
 304 }
 305
 306 static void debugValue(const ValueMapping &M, unsigned I, StringRef Desc) {
 307   const Value *V = M.Values[I];
 308   dbgs() << " - " << Desc << " value = ";
 309   V->dump();
 310   for (const Use &U : V->uses()) {
 311     dbgs() << "   => use: op = " << U.getOperandNo()
 312            << ", user-id = " << M.IDs.lookup(U.getUser()) << ", user = ";
 313     U.getUser()->dump();
 314   }
 315 }
 316
 317 static void debugUserMismatch(const ValueMapping &L, const ValueMapping &R,
 318                               unsigned I) {
 319   dbgs() << " - fail: user mismatch: ID = " << I << "\n";
 320   debugValue(L, I, "LHS");
 321   debugValue(R, I, "RHS");
 322
 323   dbgs() << "\nlhs-";
 324   dumpMapping(L);
 325   dbgs() << "\nrhs-";
 326   dumpMapping(R);
 327 }
 328
 329 static void debugSizeMismatch(const ValueMapping &L, const ValueMapping &R) {
 330   dbgs() << " - fail: map size: " << L.Values.size()
 331          << " != " << R.Values.size() << "\n";
 332   dbgs() << "\nlhs-";
 333   dumpMapping(L);
 334   dbgs() << "\nrhs-";
 335   dumpMapping(R);
 336 }
 337 #endif
 338
 339 static bool matches(const ValueMapping &LM, const ValueMapping &RM) {
 340   DEBUG(dbgs() << "compare value maps\n");
 341   if (LM.Values.size() != RM.Values.size()) {
 342     DEBUG(debugSizeMismatch(LM, RM));
 343     return false;
 344   }
 345
 346   // This mapping doesn't include dangling constant users, since those don't
 347   // get serialized.  However, checking if users are constant and calling
 348   // isConstantUsed() on every one is very expensive.  Instead, just check if
 349   // the user is mapped.
 350   auto skipUnmappedUsers =
 351       [&](Value::const_use_iterator &U, Value::const_use_iterator E,
 352           const ValueMapping &M) {
 353     while (U != E && !M.lookup(U->getUser()))
 354       ++U;
 355   };
 356
 357   // Iterate through all values, and check that both mappings have the same
 358   // users.
 359   for (unsigned I = 0, E = LM.Values.size(); I != E; ++I) {
 360     const Value *L = LM.Values[I];
 361     const Value *R = RM.Values[I];
 362     auto LU = L->use_begin(), LE = L->use_end();
 363     auto RU = R->use_begin(), RE = R->use_end();
 364     skipUnmappedUsers(LU, LE, LM);
 365     skipUnmappedUsers(RU, RE, RM);
 366
 367     while (LU != LE) {
 368       if (RU == RE) {
 369         DEBUG(debugUserMismatch(LM, RM, I));
 370         return false;
 371       }
 372       if (LM.lookup(LU->getUser()) != RM.lookup(RU->getUser())) {
 373         DEBUG(debugUserMismatch(LM, RM, I));
 374         return false;
 375       }
 376       if (LU->getOperandNo() != RU->getOperandNo()) {
 377         DEBUG(debugUserMismatch(LM, RM, I));
 378         return false;
 379       }
 380       skipUnmappedUsers(++LU, LE, LM);
 381       skipUnmappedUsers(++RU, RE, RM);
 382     }
 383     if (RU != RE) {
 384       DEBUG(debugUserMismatch(LM, RM, I));
 385       return false;
 386     }
 387   }
 388
 389   return true;
 390 }
 391
 392 bool llvm::verifyBitcodeUseListOrder(const Module &M) {
 393   DEBUG(dbgs() << "*** verify-use-list-order: bitcode ***\n");
 394   TempFile F;
 395   if (F.init("bc"))
 396     return false;
 397
 398   if (F.writeBitcode(M))
 399     return false;
 400
 401   LLVMContext Context;
 402   std::unique_ptr<Module> OtherM = F.readBitcode(Context);
 403   if (!OtherM)
 404     return false;
 405
 406   return matches(ValueMapping(M), ValueMapping(*OtherM));
 407 }
 408
 409 bool llvm::verifyAssemblyUseListOrder(const Module &M) {
 410   DEBUG(dbgs() << "*** verify-use-list-order: assembly ***\n");
 411   TempFile F;
 412   if (F.init("ll"))
 413     return false;
 414
 415   if (F.writeAssembly(M))
 416     return false;
 417
 418   LLVMContext Context;
 419   std::unique_ptr<Module> OtherM = F.readAssembly(Context);
 420   if (!OtherM)
 421     return false;
 422
 423   return matches(ValueMapping(M), ValueMapping(*OtherM));
 424 }