311b51818bfc750bb8132d6d971630b5934cd818
[oota-llvm.git] / 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 }