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