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     DEBUG(dbgs() << "error: " << EC.message() << "\n");
 174     return true;
 175   }
 176   assert(!Vector.empty());
 177
 178   Filename.assign(Vector.data(), Vector.data() + Vector.size());
 179   Remover.setFile(Filename);
 180   DEBUG(dbgs() << " - filename = " << Filename << "\n");
 181   return false;
 182 }
 183
 184 bool TempFile::writeBitcode(const Module &M) const {
 185   DEBUG(dbgs() << " - write bitcode\n");
 186   std::string ErrorInfo;
 187   raw_fd_ostream OS(Filename.c_str(), ErrorInfo, sys::fs::F_None);
 188   if (!ErrorInfo.empty()) {
 189     DEBUG(dbgs() << "error: " << ErrorInfo << "\n");
 190     return true;
 191   }
 192
 193   WriteBitcodeToFile(&M, OS);
 194   return false;
 195 }
 196
 197 bool TempFile::writeAssembly(const Module &M) const {
 198   DEBUG(dbgs() << " - write assembly\n");
 199   std::string ErrorInfo;
 200   raw_fd_ostream OS(Filename.c_str(), ErrorInfo, sys::fs::F_Text);
 201   if (!ErrorInfo.empty()) {
 202     DEBUG(dbgs() << "error: " << ErrorInfo << "\n");
 203     return true;
 204   }
 205
 206   OS << M;
 207   return false;
 208 }
 209
 210 std::unique_ptr<Module> TempFile::readBitcode(LLVMContext &Context) const {
 211   DEBUG(dbgs() << " - read bitcode\n");
 212   ErrorOr<std::unique_ptr<MemoryBuffer>> BufferOr =
 213       MemoryBuffer::getFile(Filename);
 214   if (!BufferOr) {
 215     DEBUG(dbgs() << "error: " << BufferOr.getError().message() << "\n");
 216     return nullptr;
 217   }
 218
 219   std::unique_ptr<MemoryBuffer> Buffer = std::move(BufferOr.get());
 220   ErrorOr<Module *> ModuleOr = parseBitcodeFile(Buffer.release(), Context);
 221   if (!ModuleOr) {
 222     DEBUG(dbgs() << "error: " << ModuleOr.getError().message() << "\n");
 223     return nullptr;
 224   }
 225   return std::unique_ptr<Module>(ModuleOr.get());
 226 }
 227
 228 std::unique_ptr<Module> TempFile::readAssembly(LLVMContext &Context) const {
 229   DEBUG(dbgs() << " - read assembly\n");
 230   SMDiagnostic Err;
 231   std::unique_ptr<Module> M(ParseAssemblyFile(Filename, Err, Context));
 232   if (!M.get())
 233     DEBUG(dbgs() << "error: "; Err.print("verify-use-list-order", dbgs()));
 234   return M;
 235 }
 236
 237 ValueMapping::ValueMapping(const Module &M) {
 238   // Every value should be mapped, including things like void instructions and
 239   // basic blocks that are kept out of the ValueEnumerator.
 240   //
 241   // The current mapping order makes it easier to debug the tables.  It happens
 242   // to be similar to the ID mapping when writing ValueEnumerator, but they
 243   // aren't (and needn't be) in sync.
 244
 245   // Globals.
 246   for (const GlobalVariable &G : M.globals())
 247     map(&G);
 248   for (const GlobalAlias &A : M.aliases())
 249     map(&A);
 250   for (const Function &F : M)
 251     map(&F);
 252
 253   // Constants used by globals.
 254   for (const GlobalVariable &G : M.globals())
 255     if (G.hasInitializer())
 256       map(G.getInitializer());
 257   for (const GlobalAlias &A : M.aliases())
 258     map(A.getAliasee());
 259   for (const Function &F : M)
 260     if (F.hasPrefixData())
 261       map(F.getPrefixData());
 262
 263   // Function bodies.
 264   for (const Function &F : M) {
 265     for (const Argument &A : F.args())
 266       map(&A);
 267     for (const BasicBlock &BB : F)
 268       map(&BB);
 269     for (const BasicBlock &BB : F)
 270       for (const Instruction &I : BB)
 271         map(&I);
 272
 273     // Constants used by instructions.
 274     for (const BasicBlock &BB : F)
 275       for (const Instruction &I : BB)
 276         for (const Value *Op : I.operands())
 277           if ((isa<Constant>(Op) && !isa<GlobalValue>(*Op)) ||
 278               isa<InlineAsm>(Op))
 279             map(Op);
 280   }
 281 }
 282
 283 void ValueMapping::map(const Value *V) {
 284   if (IDs.lookup(V))
 285     return;
 286
 287   if (auto *C = dyn_cast<Constant>(V))
 288     if (!isa<GlobalValue>(C))
 289       for (const Value *Op : C->operands())
 290         map(Op);
 291
 292   Values.push_back(V);
 293   IDs[V] = Values.size();
 294 }
 295
 296 #ifndef NDEBUG
 297 static void dumpMapping(const ValueMapping &VM) {
 298   dbgs() << "value-mapping (size = " << VM.Values.size() << "):\n";
 299   for (unsigned I = 0, E = VM.Values.size(); I != E; ++I) {
 300     dbgs() << " - id = " << I << ", value = ";
 301     VM.Values[I]->dump();
 302   }
 303 }
 304
 305 static void debugValue(const ValueMapping &M, unsigned I, StringRef Desc) {
 306   const Value *V = M.Values[I];
 307   dbgs() << " - " << Desc << " value = ";
 308   V->dump();
 309   for (const Use &U : V->uses()) {
 310     dbgs() << "   => use: op = " << U.getOperandNo()
 311            << ", user-id = " << M.IDs.lookup(U.getUser()) << ", user = ";
 312     U.getUser()->dump();
 313   }
 314 }
 315
 316 static void debugUserMismatch(const ValueMapping &L, const ValueMapping &R,
 317                               unsigned I) {
 318   dbgs() << " - fail: user mismatch: ID = " << I << "\n";
 319   debugValue(L, I, "LHS");
 320   debugValue(R, I, "RHS");
 321
 322   dbgs() << "\nlhs-";
 323   dumpMapping(L);
 324   dbgs() << "\nrhs-";
 325   dumpMapping(R);
 326 }
 327
 328 static void debugSizeMismatch(const ValueMapping &L, const ValueMapping &R) {
 329   dbgs() << " - fail: map size: " << L.Values.size()
 330          << " != " << R.Values.size() << "\n";
 331   dbgs() << "\nlhs-";
 332   dumpMapping(L);
 333   dbgs() << "\nrhs-";
 334   dumpMapping(R);
 335 }
 336 #endif
 337
 338 static bool matches(const ValueMapping &LM, const ValueMapping &RM) {
 339   DEBUG(dbgs() << "compare value maps\n");
 340   if (LM.Values.size() != RM.Values.size()) {
 341     DEBUG(debugSizeMismatch(LM, RM));
 342     return false;
 343   }
 344
 345   // This mapping doesn't include dangling constant users, since those don't
 346   // get serialized.  However, checking if users are constant and calling
 347   // isConstantUsed() on every one is very expensive.  Instead, just check if
 348   // the user is mapped.
 349   auto skipUnmappedUsers =
 350       [&](Value::const_use_iterator &U, Value::const_use_iterator E,
 351           const ValueMapping &M) {
 352     while (U != E && !M.lookup(U->getUser()))
 353       ++U;
 354   };
 355
 356   // Iterate through all values, and check that both mappings have the same
 357   // users.
 358   for (unsigned I = 0, E = LM.Values.size(); I != E; ++I) {
 359     const Value *L = LM.Values[I];
 360     const Value *R = RM.Values[I];
 361     auto LU = L->use_begin(), LE = L->use_end();
 362     auto RU = R->use_begin(), RE = R->use_end();
 363     skipUnmappedUsers(LU, LE, LM);
 364     skipUnmappedUsers(RU, RE, RM);
 365
 366     while (LU != LE) {
 367       if (RU == RE) {
 368         DEBUG(debugUserMismatch(LM, RM, I));
 369         return false;
 370       }
 371       if (LM.lookup(LU->getUser()) != RM.lookup(RU->getUser())) {
 372         DEBUG(debugUserMismatch(LM, RM, I));
 373         return false;
 374       }
 375       if (LU->getOperandNo() != RU->getOperandNo()) {
 376         DEBUG(debugUserMismatch(LM, RM, I));
 377         return false;
 378       }
 379       skipUnmappedUsers(++LU, LE, LM);
 380       skipUnmappedUsers(++RU, RE, RM);
 381     }
 382     if (RU != RE) {
 383       DEBUG(debugUserMismatch(LM, RM, I));
 384       return false;
 385     }
 386   }
 387
 388   return true;
 389 }
 390
 391 bool llvm::verifyBitcodeUseListOrder(const Module &M) {
 392   DEBUG(dbgs() << "*** verify-use-list-order: bitcode ***\n");
 393   TempFile F;
 394   if (F.init("bc"))
 395     return false;
 396
 397   if (F.writeBitcode(M))
 398     return false;
 399
 400   LLVMContext Context;
 401   std::unique_ptr<Module> OtherM = F.readBitcode(Context);
 402   if (!OtherM)
 403     return false;
 404
 405   return matches(ValueMapping(M), ValueMapping(*OtherM));
 406 }
 407
 408 bool llvm::verifyAssemblyUseListOrder(const Module &M) {
 409   DEBUG(dbgs() << "*** verify-use-list-order: assembly ***\n");
 410   TempFile F;
 411   if (F.init("ll"))
 412     return false;
 413
 414   if (F.writeAssembly(M))
 415     return false;
 416
 417   LLVMContext Context;
 418   std::unique_ptr<Module> OtherM = F.readAssembly(Context);
 419   if (!OtherM)
 420     return false;
 421
 422   return matches(ValueMapping(M), ValueMapping(*OtherM));
 423 }