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       dbgs() << " - order: " << Order.lookup(&U) << ", U = ";
  79       U.getUser()->dump();
  80     }
  81   });
  82 }
  83
  84 void llvm::shuffleUseLists(Module &M, unsigned SeedOffset) {
  85   DEBUG(dbgs() << "*** shuffle-use-lists ***\n");
  86   std::minstd_rand0 Gen(std::minstd_rand0::default_seed + SeedOffset);
  87   DenseSet<Value *> Seen;
  88
  89   // Shuffle the use-list of each value that would be serialized to an IR file
  90   // (bitcode or assembly).
  91   auto shuffle = [&](Value *V) { shuffleValueUseLists(V, Gen, Seen); };
  92
  93   // Globals.
  94   for (GlobalVariable &G : M.globals())
  95     shuffle(&G);
  96   for (GlobalAlias &A : M.aliases())
  97     shuffle(&A);
  98   for (Function &F : M)
  99     shuffle(&F);
 100
 101   // Constants used by globals.
 102   for (GlobalVariable &G : M.globals())
 103     if (G.hasInitializer())
 104       shuffle(G.getInitializer());
 105   for (GlobalAlias &A : M.aliases())
 106     shuffle(A.getAliasee());
 107   for (Function &F : M)
 108     if (F.hasPrefixData())
 109       shuffle(F.getPrefixData());
 110
 111   // Function bodies.
 112   for (Function &F : M) {
 113     for (Argument &A : F.args())
 114       shuffle(&A);
 115     for (BasicBlock &BB : F)
 116       shuffle(&BB);
 117     for (BasicBlock &BB : F)
 118       for (Instruction &I : BB)
 119         shuffle(&I);
 120
 121     // Constants used by instructions.
 122     for (BasicBlock &BB : F)
 123       for (Instruction &I : BB)
 124         for (Value *Op : I.operands())
 125           if ((isa<Constant>(Op) && !isa<GlobalValue>(*Op)) ||
 126               isa<InlineAsm>(Op))
 127             shuffle(Op);
 128   }
 129
 130   DEBUG(dbgs() << "\n");
 131 }