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/DenseSet.h"
  18 #include "llvm/IR/Module.h"
  19 #include "llvm/Support/CommandLine.h"
  20 #include "llvm/Support/Debug.h"
  21
  22 #include <random>
  23 #include <vector>
  24
  25 #define DEBUG_TYPE "use-list-order"
  26
  27 using namespace llvm;
  28
  29 static cl::opt<bool> PreserveBitcodeUseListOrder(
  30     "preserve-bc-use-list-order",
  31     cl::desc("Experimental support to preserve bitcode use-list order."),
  32     cl::init(false), cl::Hidden);
  33
  34 static cl::opt<bool> PreserveAssemblyUseListOrder(
  35     "preserve-ll-use-list-order",
  36     cl::desc("Experimental support to preserve assembly use-list order."),
  37     cl::init(false), cl::Hidden);
  38
  39 bool llvm::shouldPreserveBitcodeUseListOrder() {
  40   return PreserveBitcodeUseListOrder;
  41 }
  42
  43 bool llvm::shouldPreserveAssemblyUseListOrder() {
  44   return PreserveAssemblyUseListOrder;
  45 }
  46
  47 static void shuffleValueUseLists(Value *V, std::minstd_rand0 &Gen,
  48                                  DenseSet<Value *> &Seen) {
  49   if (!Seen.insert(V).second)
  50     return;
  51
  52   if (auto *C = dyn_cast<Constant>(V))
  53     if (!isa<GlobalValue>(C))
  54       for (Value *Op : C->operands())
  55         shuffleValueUseLists(Op, Gen, Seen);
  56
  57   if (V->use_empty() || std::next(V->use_begin()) == V->use_end())
  58     // Nothing to shuffle for 0 or 1 users.
  59     return;
  60
  61   // Generate random numbers between 10 and 99, which will line up nicely in
  62   // debug output.  We're not worried about collisons here.
  63   DEBUG(dbgs() << "V = "; V->dump());
  64   std::uniform_int_distribution<short> Dist(10, 99);
  65   SmallDenseMap<const Use *, short, 16> Order;
  66   for (const Use &U : V->uses()) {
  67     auto I = Dist(Gen);
  68     Order[&U] = I;
  69     DEBUG(dbgs() << " - order: " << I << ", U = "; U.getUser()->dump());
  70   }
  71
  72   DEBUG(dbgs() << " => shuffle\n");
  73   V->sortUseList(
  74       [&Order](const Use &L, const Use &R) { return Order[&L] < Order[&R]; });
  75
  76   DEBUG({
  77     for (const Use &U : V->uses())
  78       DEBUG(dbgs() << " - order: " << Order.lookup(&U) << ", U = ";
  79             U.getUser()->dump());
  80   });
  81 }
  82
  83 void llvm::shuffleUseLists(Module &M, unsigned SeedOffset) {
  84   DEBUG(dbgs() << "*** shuffle-use-lists ***\n");
  85   std::minstd_rand0 Gen(std::minstd_rand0::default_seed + SeedOffset);
  86   DenseSet<Value *> Seen;
  87
  88   // Shuffle the use-list of each value that would be serialized to an IR file
  89   // (bitcode or assembly).
  90   auto shuffle = [&](Value *V) { shuffleValueUseLists(V, Gen, Seen); };
  91
  92   // Globals.
  93   for (GlobalVariable &G : M.globals())
  94     shuffle(&G);
  95   for (GlobalAlias &A : M.aliases())
  96     shuffle(&A);
  97   for (Function &F : M)
  98     shuffle(&F);
  99
 100   // Constants used by globals.
 101   for (GlobalVariable &G : M.globals())
 102     if (G.hasInitializer())
 103       shuffle(G.getInitializer());
 104   for (GlobalAlias &A : M.aliases())
 105     shuffle(A.getAliasee());
 106   for (Function &F : M)
 107     if (F.hasPrefixData())
 108       shuffle(F.getPrefixData());
 109
 110   // Function bodies.
 111   for (Function &F : M) {
 112     for (Argument &A : F.args())
 113       shuffle(&A);
 114     for (BasicBlock &BB : F)
 115       shuffle(&BB);
 116     for (BasicBlock &BB : F)
 117       for (Instruction &I : BB)
 118         shuffle(&I);
 119
 120     // Constants used by instructions.
 121     for (BasicBlock &BB : F)
 122       for (Instruction &I : BB)
 123         for (Value *Op : I.operands())
 124           if ((isa<Constant>(Op) && !isa<GlobalValue>(*Op)) ||
 125               isa<InlineAsm>(Op))
 126             shuffle(Op);
 127   }
 128
 129   DEBUG(dbgs() << "\n");
 130 }