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