|
121
|
1 //===- GlobalMerge.cpp - Internal globals merging -------------------------===//
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 // The LLVM Compiler Infrastructure
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 // This file is distributed under the University of Illinois Open Source
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 // License. See LICENSE.TXT for details.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8 //===----------------------------------------------------------------------===//
|
|
121
|
9 //
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10 // This pass merges globals with internal linkage into one. This way all the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11 // globals which were merged into a biggest one can be addressed using offsets
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
12 // from the same base pointer (no need for separate base pointer for each of the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13 // global). Such a transformation can significantly reduce the register pressure
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14 // when many globals are involved.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
15 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
16 // For example, consider the code which touches several global variables at
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
17 // once:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
18 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
19 // static int foo[N], bar[N], baz[N];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
20 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
21 // for (i = 0; i < N; ++i) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
22 // foo[i] = bar[i] * baz[i];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
23 // }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
24 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
25 // On ARM the addresses of 3 arrays should be kept in the registers, thus
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
26 // this code has quite large register pressure (loop body):
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
27 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
28 // ldr r1, [r5], #4
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
29 // ldr r2, [r6], #4
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
30 // mul r1, r2, r1
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
31 // str r1, [r0], #4
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
32 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
33 // Pass converts the code to something like:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
34 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35 // static struct {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
36 // int foo[N];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
37 // int bar[N];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
38 // int baz[N];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
39 // } merged;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
40 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
41 // for (i = 0; i < N; ++i) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
42 // merged.foo[i] = merged.bar[i] * merged.baz[i];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
43 // }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
44 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
45 // and in ARM code this becomes:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
46 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
47 // ldr r0, [r5, #40]
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
48 // ldr r1, [r5, #80]
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
49 // mul r0, r1, r0
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
50 // str r0, [r5], #4
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
51 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
52 // note that we saved 2 registers here almostly "for free".
|
|
95
|
53 //
|
|
|
54 // However, merging globals can have tradeoffs:
|
|
|
55 // - it confuses debuggers, tools, and users
|
|
|
56 // - it makes linker optimizations less useful (order files, LOHs, ...)
|
|
|
57 // - it forces usage of indexed addressing (which isn't necessarily "free")
|
|
|
58 // - it can increase register pressure when the uses are disparate enough.
|
|
|
59 //
|
|
|
60 // We use heuristics to discover the best global grouping we can (cf cl::opts).
|
|
121
|
61 //
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
62 // ===---------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
63
|
|
121
|
64 #include "llvm/ADT/BitVector.h"
|
|
95
|
65 #include "llvm/ADT/DenseMap.h"
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
66 #include "llvm/ADT/SmallPtrSet.h"
|
|
121
|
67 #include "llvm/ADT/SmallVector.h"
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
68 #include "llvm/ADT/Statistic.h"
|
|
121
|
69 #include "llvm/ADT/StringRef.h"
|
|
|
70 #include "llvm/ADT/Triple.h"
|
|
|
71 #include "llvm/ADT/Twine.h"
|
|
83
|
72 #include "llvm/CodeGen/Passes.h"
|
|
134
|
73 #include "llvm/CodeGen/TargetLoweringObjectFile.h"
|
|
121
|
74 #include "llvm/IR/BasicBlock.h"
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
75 #include "llvm/IR/Constants.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
76 #include "llvm/IR/DataLayout.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
77 #include "llvm/IR/DerivedTypes.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
78 #include "llvm/IR/Function.h"
|
|
121
|
79 #include "llvm/IR/GlobalAlias.h"
|
|
|
80 #include "llvm/IR/GlobalValue.h"
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
81 #include "llvm/IR/GlobalVariable.h"
|
|
121
|
82 #include "llvm/IR/Instruction.h"
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
83 #include "llvm/IR/Module.h"
|
|
121
|
84 #include "llvm/IR/Type.h"
|
|
|
85 #include "llvm/IR/Use.h"
|
|
|
86 #include "llvm/IR/User.h"
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
87 #include "llvm/Pass.h"
|
|
121
|
88 #include "llvm/Support/Casting.h"
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
89 #include "llvm/Support/CommandLine.h"
|
|
95
|
90 #include "llvm/Support/Debug.h"
|
|
|
91 #include "llvm/Support/raw_ostream.h"
|
|
121
|
92 #include "llvm/Target/TargetMachine.h"
|
|
95
|
93 #include <algorithm>
|
|
121
|
94 #include <cassert>
|
|
134
|
95 #include <cstddef>
|
|
121
|
96 #include <cstdint>
|
|
|
97 #include <string>
|
|
|
98 #include <vector>
|
|
|
99
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
100 using namespace llvm;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
101
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
102 #define DEBUG_TYPE "global-merge"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
103
|
|
95
|
104 // FIXME: This is only useful as a last-resort way to disable the pass.
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
105 static cl::opt<bool>
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
106 EnableGlobalMerge("enable-global-merge", cl::Hidden,
|
|
95
|
107 cl::desc("Enable the global merge pass"),
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
108 cl::init(true));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
109
|
|
120
|
110 static cl::opt<unsigned>
|
|
|
111 GlobalMergeMaxOffset("global-merge-max-offset", cl::Hidden,
|
|
|
112 cl::desc("Set maximum offset for global merge pass"),
|
|
|
113 cl::init(0));
|
|
|
114
|
|
95
|
115 static cl::opt<bool> GlobalMergeGroupByUse(
|
|
|
116 "global-merge-group-by-use", cl::Hidden,
|
|
|
117 cl::desc("Improve global merge pass to look at uses"), cl::init(true));
|
|
|
118
|
|
|
119 static cl::opt<bool> GlobalMergeIgnoreSingleUse(
|
|
|
120 "global-merge-ignore-single-use", cl::Hidden,
|
|
|
121 cl::desc("Improve global merge pass to ignore globals only used alone"),
|
|
|
122 cl::init(true));
|
|
|
123
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
124 static cl::opt<bool>
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
125 EnableGlobalMergeOnConst("global-merge-on-const", cl::Hidden,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
126 cl::desc("Enable global merge pass on constants"),
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
127 cl::init(false));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
128
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
129 // FIXME: this could be a transitional option, and we probably need to remove
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
130 // it if only we are sure this optimization could always benefit all targets.
|
|
95
|
131 static cl::opt<cl::boolOrDefault>
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
132 EnableGlobalMergeOnExternal("global-merge-on-external", cl::Hidden,
|
|
95
|
133 cl::desc("Enable global merge pass on external linkage"));
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
134
|
|
95
|
135 STATISTIC(NumMerged, "Number of globals merged");
|
|
121
|
136
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
137 namespace {
|
|
121
|
138
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
139 class GlobalMerge : public FunctionPass {
|
|
121
|
140 const TargetMachine *TM = nullptr;
|
|
|
141
|
|
95
|
142 // FIXME: Infer the maximum possible offset depending on the actual users
|
|
|
143 // (these max offsets are different for the users inside Thumb or ARM
|
|
|
144 // functions), see the code that passes in the offset in the ARM backend
|
|
|
145 // for more information.
|
|
|
146 unsigned MaxOffset;
|
|
|
147
|
|
|
148 /// Whether we should try to optimize for size only.
|
|
|
149 /// Currently, this applies a dead simple heuristic: only consider globals
|
|
|
150 /// used in minsize functions for merging.
|
|
|
151 /// FIXME: This could learn about optsize, and be used in the cost model.
|
|
121
|
152 bool OnlyOptimizeForSize = false;
|
|
95
|
153
|
|
|
154 /// Whether we should merge global variables that have external linkage.
|
|
121
|
155 bool MergeExternalGlobals = false;
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
156
|
|
120
|
157 bool IsMachO;
|
|
|
158
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
159 bool doMerge(SmallVectorImpl<GlobalVariable*> &Globals,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
160 Module &M, bool isConst, unsigned AddrSpace) const;
|
|
121
|
161
|
|
95
|
162 /// \brief Merge everything in \p Globals for which the corresponding bit
|
|
|
163 /// in \p GlobalSet is set.
|
|
|
164 bool doMerge(const SmallVectorImpl<GlobalVariable *> &Globals,
|
|
|
165 const BitVector &GlobalSet, Module &M, bool isConst,
|
|
|
166 unsigned AddrSpace) const;
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
167
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
168 /// \brief Check if the given variable has been identified as must keep
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
169 /// \pre setMustKeepGlobalVariables must have been called on the Module that
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
170 /// contains GV
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
171 bool isMustKeepGlobalVariable(const GlobalVariable *GV) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
172 return MustKeepGlobalVariables.count(GV);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
173 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
174
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
175 /// Collect every variables marked as "used" or used in a landing pad
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
176 /// instruction for this Module.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
177 void setMustKeepGlobalVariables(Module &M);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
178
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
179 /// Collect every variables marked as "used"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
180 void collectUsedGlobalVariables(Module &M);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
181
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
182 /// Keep track of the GlobalVariable that must not be merged away
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
183 SmallPtrSet<const GlobalVariable *, 16> MustKeepGlobalVariables;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
184
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
185 public:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
186 static char ID; // Pass identification, replacement for typeid.
|
|
121
|
187
|
|
120
|
188 explicit GlobalMerge()
|
|
121
|
189 : FunctionPass(ID), MaxOffset(GlobalMergeMaxOffset) {
|
|
120
|
190 initializeGlobalMergePass(*PassRegistry::getPassRegistry());
|
|
|
191 }
|
|
|
192
|
|
|
193 explicit GlobalMerge(const TargetMachine *TM, unsigned MaximalOffset,
|
|
|
194 bool OnlyOptimizeForSize, bool MergeExternalGlobals)
|
|
95
|
195 : FunctionPass(ID), TM(TM), MaxOffset(MaximalOffset),
|
|
|
196 OnlyOptimizeForSize(OnlyOptimizeForSize),
|
|
|
197 MergeExternalGlobals(MergeExternalGlobals) {
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
198 initializeGlobalMergePass(*PassRegistry::getPassRegistry());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
199 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
200
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
201 bool doInitialization(Module &M) override;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
202 bool runOnFunction(Function &F) override;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
203 bool doFinalization(Module &M) override;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
204
|
|
120
|
205 StringRef getPassName() const override { return "Merge internal globals"; }
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
206
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
207 void getAnalysisUsage(AnalysisUsage &AU) const override {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
208 AU.setPreservesCFG();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
209 FunctionPass::getAnalysisUsage(AU);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
210 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
211 };
|
|
121
|
212
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
213 } // end anonymous namespace
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
214
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
215 char GlobalMerge::ID = 0;
|
|
121
|
216
|
|
|
217 INITIALIZE_PASS(GlobalMerge, DEBUG_TYPE, "Merge global variables", false, false)
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
218
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
219 bool GlobalMerge::doMerge(SmallVectorImpl<GlobalVariable*> &Globals,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
220 Module &M, bool isConst, unsigned AddrSpace) const {
|
|
95
|
221 auto &DL = M.getDataLayout();
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
222 // FIXME: Find better heuristics
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
223 std::stable_sort(Globals.begin(), Globals.end(),
|
|
95
|
224 [&DL](const GlobalVariable *GV1, const GlobalVariable *GV2) {
|
|
|
225 return DL.getTypeAllocSize(GV1->getValueType()) <
|
|
|
226 DL.getTypeAllocSize(GV2->getValueType());
|
|
|
227 });
|
|
|
228
|
|
|
229 // If we want to just blindly group all globals together, do so.
|
|
|
230 if (!GlobalMergeGroupByUse) {
|
|
|
231 BitVector AllGlobals(Globals.size());
|
|
|
232 AllGlobals.set();
|
|
|
233 return doMerge(Globals, AllGlobals, M, isConst, AddrSpace);
|
|
|
234 }
|
|
|
235
|
|
|
236 // If we want to be smarter, look at all uses of each global, to try to
|
|
|
237 // discover all sets of globals used together, and how many times each of
|
|
|
238 // these sets occurred.
|
|
|
239 //
|
|
|
240 // Keep this reasonably efficient, by having an append-only list of all sets
|
|
|
241 // discovered so far (UsedGlobalSet), and mapping each "together-ness" unit of
|
|
|
242 // code (currently, a Function) to the set of globals seen so far that are
|
|
|
243 // used together in that unit (GlobalUsesByFunction).
|
|
|
244 //
|
|
|
245 // When we look at the Nth global, we now that any new set is either:
|
|
|
246 // - the singleton set {N}, containing this global only, or
|
|
|
247 // - the union of {N} and a previously-discovered set, containing some
|
|
|
248 // combination of the previous N-1 globals.
|
|
|
249 // Using that knowledge, when looking at the Nth global, we can keep:
|
|
|
250 // - a reference to the singleton set {N} (CurGVOnlySetIdx)
|
|
|
251 // - a list mapping each previous set to its union with {N} (EncounteredUGS),
|
|
|
252 // if it actually occurs.
|
|
|
253
|
|
|
254 // We keep track of the sets of globals used together "close enough".
|
|
|
255 struct UsedGlobalSet {
|
|
|
256 BitVector Globals;
|
|
121
|
257 unsigned UsageCount = 1;
|
|
|
258
|
|
|
259 UsedGlobalSet(size_t Size) : Globals(Size) {}
|
|
95
|
260 };
|
|
|
261
|
|
|
262 // Each set is unique in UsedGlobalSets.
|
|
|
263 std::vector<UsedGlobalSet> UsedGlobalSets;
|
|
|
264
|
|
|
265 // Avoid repeating the create-global-set pattern.
|
|
|
266 auto CreateGlobalSet = [&]() -> UsedGlobalSet & {
|
|
|
267 UsedGlobalSets.emplace_back(Globals.size());
|
|
|
268 return UsedGlobalSets.back();
|
|
|
269 };
|
|
|
270
|
|
|
271 // The first set is the empty set.
|
|
|
272 CreateGlobalSet().UsageCount = 0;
|
|
|
273
|
|
|
274 // We define "close enough" to be "in the same function".
|
|
|
275 // FIXME: Grouping uses by function is way too aggressive, so we should have
|
|
|
276 // a better metric for distance between uses.
|
|
|
277 // The obvious alternative would be to group by BasicBlock, but that's in
|
|
|
278 // turn too conservative..
|
|
|
279 // Anything in between wouldn't be trivial to compute, so just stick with
|
|
|
280 // per-function grouping.
|
|
|
281
|
|
|
282 // The value type is an index into UsedGlobalSets.
|
|
|
283 // The default (0) conveniently points to the empty set.
|
|
|
284 DenseMap<Function *, size_t /*UsedGlobalSetIdx*/> GlobalUsesByFunction;
|
|
|
285
|
|
|
286 // Now, look at each merge-eligible global in turn.
|
|
|
287
|
|
|
288 // Keep track of the sets we already encountered to which we added the
|
|
|
289 // current global.
|
|
|
290 // Each element matches the same-index element in UsedGlobalSets.
|
|
|
291 // This lets us efficiently tell whether a set has already been expanded to
|
|
|
292 // include the current global.
|
|
|
293 std::vector<size_t> EncounteredUGS;
|
|
|
294
|
|
|
295 for (size_t GI = 0, GE = Globals.size(); GI != GE; ++GI) {
|
|
|
296 GlobalVariable *GV = Globals[GI];
|
|
|
297
|
|
|
298 // Reset the encountered sets for this global...
|
|
|
299 std::fill(EncounteredUGS.begin(), EncounteredUGS.end(), 0);
|
|
|
300 // ...and grow it in case we created new sets for the previous global.
|
|
|
301 EncounteredUGS.resize(UsedGlobalSets.size());
|
|
|
302
|
|
|
303 // We might need to create a set that only consists of the current global.
|
|
|
304 // Keep track of its index into UsedGlobalSets.
|
|
|
305 size_t CurGVOnlySetIdx = 0;
|
|
|
306
|
|
|
307 // For each global, look at all its Uses.
|
|
|
308 for (auto &U : GV->uses()) {
|
|
|
309 // This Use might be a ConstantExpr. We're interested in Instruction
|
|
|
310 // users, so look through ConstantExpr...
|
|
|
311 Use *UI, *UE;
|
|
|
312 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U.getUser())) {
|
|
|
313 if (CE->use_empty())
|
|
|
314 continue;
|
|
|
315 UI = &*CE->use_begin();
|
|
|
316 UE = nullptr;
|
|
|
317 } else if (isa<Instruction>(U.getUser())) {
|
|
|
318 UI = &U;
|
|
|
319 UE = UI->getNext();
|
|
|
320 } else {
|
|
|
321 continue;
|
|
|
322 }
|
|
|
323
|
|
|
324 // ...to iterate on all the instruction users of the global.
|
|
|
325 // Note that we iterate on Uses and not on Users to be able to getNext().
|
|
|
326 for (; UI != UE; UI = UI->getNext()) {
|
|
|
327 Instruction *I = dyn_cast<Instruction>(UI->getUser());
|
|
|
328 if (!I)
|
|
|
329 continue;
|
|
|
330
|
|
|
331 Function *ParentFn = I->getParent()->getParent();
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
332
|
|
95
|
333 // If we're only optimizing for size, ignore non-minsize functions.
|
|
|
334 if (OnlyOptimizeForSize && !ParentFn->optForMinSize())
|
|
|
335 continue;
|
|
|
336
|
|
|
337 size_t UGSIdx = GlobalUsesByFunction[ParentFn];
|
|
|
338
|
|
|
339 // If this is the first global the basic block uses, map it to the set
|
|
|
340 // consisting of this global only.
|
|
|
341 if (!UGSIdx) {
|
|
|
342 // If that set doesn't exist yet, create it.
|
|
|
343 if (!CurGVOnlySetIdx) {
|
|
|
344 CurGVOnlySetIdx = UsedGlobalSets.size();
|
|
|
345 CreateGlobalSet().Globals.set(GI);
|
|
|
346 } else {
|
|
|
347 ++UsedGlobalSets[CurGVOnlySetIdx].UsageCount;
|
|
|
348 }
|
|
|
349
|
|
|
350 GlobalUsesByFunction[ParentFn] = CurGVOnlySetIdx;
|
|
|
351 continue;
|
|
|
352 }
|
|
|
353
|
|
|
354 // If we already encountered this BB, just increment the counter.
|
|
|
355 if (UsedGlobalSets[UGSIdx].Globals.test(GI)) {
|
|
|
356 ++UsedGlobalSets[UGSIdx].UsageCount;
|
|
|
357 continue;
|
|
|
358 }
|
|
|
359
|
|
|
360 // If not, the previous set wasn't actually used in this function.
|
|
|
361 --UsedGlobalSets[UGSIdx].UsageCount;
|
|
|
362
|
|
|
363 // If we already expanded the previous set to include this global, just
|
|
|
364 // reuse that expanded set.
|
|
|
365 if (size_t ExpandedIdx = EncounteredUGS[UGSIdx]) {
|
|
|
366 ++UsedGlobalSets[ExpandedIdx].UsageCount;
|
|
|
367 GlobalUsesByFunction[ParentFn] = ExpandedIdx;
|
|
|
368 continue;
|
|
|
369 }
|
|
|
370
|
|
|
371 // If not, create a new set consisting of the union of the previous set
|
|
|
372 // and this global. Mark it as encountered, so we can reuse it later.
|
|
|
373 GlobalUsesByFunction[ParentFn] = EncounteredUGS[UGSIdx] =
|
|
|
374 UsedGlobalSets.size();
|
|
|
375
|
|
|
376 UsedGlobalSet &NewUGS = CreateGlobalSet();
|
|
|
377 NewUGS.Globals.set(GI);
|
|
|
378 NewUGS.Globals |= UsedGlobalSets[UGSIdx].Globals;
|
|
|
379 }
|
|
|
380 }
|
|
|
381 }
|
|
|
382
|
|
|
383 // Now we found a bunch of sets of globals used together. We accumulated
|
|
|
384 // the number of times we encountered the sets (i.e., the number of blocks
|
|
|
385 // that use that exact set of globals).
|
|
|
386 //
|
|
|
387 // Multiply that by the size of the set to give us a crude profitability
|
|
|
388 // metric.
|
|
134
|
389 std::stable_sort(UsedGlobalSets.begin(), UsedGlobalSets.end(),
|
|
95
|
390 [](const UsedGlobalSet &UGS1, const UsedGlobalSet &UGS2) {
|
|
|
391 return UGS1.Globals.count() * UGS1.UsageCount <
|
|
|
392 UGS2.Globals.count() * UGS2.UsageCount;
|
|
|
393 });
|
|
|
394
|
|
|
395 // We can choose to merge all globals together, but ignore globals never used
|
|
|
396 // with another global. This catches the obviously non-profitable cases of
|
|
|
397 // having a single global, but is aggressive enough for any other case.
|
|
|
398 if (GlobalMergeIgnoreSingleUse) {
|
|
|
399 BitVector AllGlobals(Globals.size());
|
|
|
400 for (size_t i = 0, e = UsedGlobalSets.size(); i != e; ++i) {
|
|
|
401 const UsedGlobalSet &UGS = UsedGlobalSets[e - i - 1];
|
|
|
402 if (UGS.UsageCount == 0)
|
|
|
403 continue;
|
|
|
404 if (UGS.Globals.count() > 1)
|
|
|
405 AllGlobals |= UGS.Globals;
|
|
|
406 }
|
|
|
407 return doMerge(Globals, AllGlobals, M, isConst, AddrSpace);
|
|
|
408 }
|
|
|
409
|
|
|
410 // Starting from the sets with the best (=biggest) profitability, find a
|
|
|
411 // good combination.
|
|
|
412 // The ideal (and expensive) solution can only be found by trying all
|
|
|
413 // combinations, looking for the one with the best profitability.
|
|
|
414 // Don't be smart about it, and just pick the first compatible combination,
|
|
|
415 // starting with the sets with the best profitability.
|
|
|
416 BitVector PickedGlobals(Globals.size());
|
|
|
417 bool Changed = false;
|
|
|
418
|
|
|
419 for (size_t i = 0, e = UsedGlobalSets.size(); i != e; ++i) {
|
|
|
420 const UsedGlobalSet &UGS = UsedGlobalSets[e - i - 1];
|
|
|
421 if (UGS.UsageCount == 0)
|
|
|
422 continue;
|
|
|
423 if (PickedGlobals.anyCommon(UGS.Globals))
|
|
|
424 continue;
|
|
|
425 PickedGlobals |= UGS.Globals;
|
|
|
426 // If the set only contains one global, there's no point in merging.
|
|
|
427 // Ignore the global for inclusion in other sets though, so keep it in
|
|
|
428 // PickedGlobals.
|
|
|
429 if (UGS.Globals.count() < 2)
|
|
|
430 continue;
|
|
|
431 Changed |= doMerge(Globals, UGS.Globals, M, isConst, AddrSpace);
|
|
|
432 }
|
|
|
433
|
|
|
434 return Changed;
|
|
|
435 }
|
|
|
436
|
|
|
437 bool GlobalMerge::doMerge(const SmallVectorImpl<GlobalVariable *> &Globals,
|
|
|
438 const BitVector &GlobalSet, Module &M, bool isConst,
|
|
|
439 unsigned AddrSpace) const {
|
|
|
440 assert(Globals.size() > 1);
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
441
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
442 Type *Int32Ty = Type::getInt32Ty(M.getContext());
|
|
95
|
443 auto &DL = M.getDataLayout();
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
444
|
|
95
|
445 DEBUG(dbgs() << " Trying to merge set, starts with #"
|
|
|
446 << GlobalSet.find_first() << "\n");
|
|
|
447
|
|
|
448 ssize_t i = GlobalSet.find_first();
|
|
|
449 while (i != -1) {
|
|
|
450 ssize_t j = 0;
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
451 uint64_t MergedSize = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
452 std::vector<Type*> Tys;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
453 std::vector<Constant*> Inits;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
454
|
|
120
|
455 bool HasExternal = false;
|
|
|
456 StringRef FirstExternalName;
|
|
95
|
457 for (j = i; j != -1; j = GlobalSet.find_next(j)) {
|
|
|
458 Type *Ty = Globals[j]->getValueType();
|
|
|
459 MergedSize += DL.getTypeAllocSize(Ty);
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
460 if (MergedSize > MaxOffset) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
461 break;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
462 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
463 Tys.push_back(Ty);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
464 Inits.push_back(Globals[j]->getInitializer());
|
|
120
|
465
|
|
|
466 if (Globals[j]->hasExternalLinkage() && !HasExternal) {
|
|
|
467 HasExternal = true;
|
|
|
468 FirstExternalName = Globals[j]->getName();
|
|
|
469 }
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
470 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
471
|
|
120
|
472 // If merged variables doesn't have external linkage, we needn't to expose
|
|
|
473 // the symbol after merging.
|
|
|
474 GlobalValue::LinkageTypes Linkage = HasExternal
|
|
|
475 ? GlobalValue::ExternalLinkage
|
|
|
476 : GlobalValue::InternalLinkage;
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
477 StructType *MergedTy = StructType::get(M.getContext(), Tys);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
478 Constant *MergedInit = ConstantStruct::get(MergedTy, Inits);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
479
|
|
120
|
480 // On Darwin external linkage needs to be preserved, otherwise
|
|
|
481 // dsymutil cannot preserve the debug info for the merged
|
|
|
482 // variables. If they have external linkage, use the symbol name
|
|
|
483 // of the first variable merged as the suffix of global symbol
|
|
|
484 // name. This avoids a link-time naming conflict for the
|
|
|
485 // _MergedGlobals symbols.
|
|
|
486 Twine MergedName =
|
|
|
487 (IsMachO && HasExternal)
|
|
|
488 ? "_MergedGlobals_" + FirstExternalName
|
|
|
489 : "_MergedGlobals";
|
|
|
490 auto MergedLinkage = IsMachO ? Linkage : GlobalValue::PrivateLinkage;
|
|
|
491 auto *MergedGV = new GlobalVariable(
|
|
|
492 M, MergedTy, isConst, MergedLinkage, MergedInit, MergedName, nullptr,
|
|
|
493 GlobalVariable::NotThreadLocal, AddrSpace);
|
|
|
494
|
|
|
495 const StructLayout *MergedLayout = DL.getStructLayout(MergedTy);
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
496
|
|
95
|
497 for (ssize_t k = i, idx = 0; k != j; k = GlobalSet.find_next(k), ++idx) {
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
498 GlobalValue::LinkageTypes Linkage = Globals[k]->getLinkage();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
499 std::string Name = Globals[k]->getName();
|
|
134
|
500 GlobalValue::DLLStorageClassTypes DLLStorage =
|
|
|
501 Globals[k]->getDLLStorageClass();
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
502
|
|
120
|
503 // Copy metadata while adjusting any debug info metadata by the original
|
|
|
504 // global's offset within the merged global.
|
|
|
505 MergedGV->copyMetadata(Globals[k], MergedLayout->getElementOffset(idx));
|
|
|
506
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
507 Constant *Idx[2] = {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
508 ConstantInt::get(Int32Ty, 0),
|
|
95
|
509 ConstantInt::get(Int32Ty, idx),
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
510 };
|
|
95
|
511 Constant *GEP =
|
|
|
512 ConstantExpr::getInBoundsGetElementPtr(MergedTy, MergedGV, Idx);
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
513 Globals[k]->replaceAllUsesWith(GEP);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
514 Globals[k]->eraseFromParent();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
515
|
|
95
|
516 // When the linkage is not internal we must emit an alias for the original
|
|
|
517 // variable name as it may be accessed from another object. On non-Mach-O
|
|
|
518 // we can also emit an alias for internal linkage as it's safe to do so.
|
|
|
519 // It's not safe on Mach-O as the alias (and thus the portion of the
|
|
|
520 // MergedGlobals variable) may be dead stripped at link time.
|
|
120
|
521 if (Linkage != GlobalValue::InternalLinkage || !IsMachO) {
|
|
134
|
522 GlobalAlias *GA =
|
|
|
523 GlobalAlias::create(Tys[idx], AddrSpace, Linkage, Name, GEP, &M);
|
|
|
524 GA->setDLLStorageClass(DLLStorage);
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
525 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
526
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
527 NumMerged++;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
528 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
529 i = j;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
530 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
531
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
532 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
533 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
534
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
535 void GlobalMerge::collectUsedGlobalVariables(Module &M) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
536 // Extract global variables from llvm.used array
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
537 const GlobalVariable *GV = M.getGlobalVariable("llvm.used");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
538 if (!GV || !GV->hasInitializer()) return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
539
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
540 // Should be an array of 'i8*'.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
541 const ConstantArray *InitList = cast<ConstantArray>(GV->getInitializer());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
542
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
543 for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
544 if (const GlobalVariable *G =
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
545 dyn_cast<GlobalVariable>(InitList->getOperand(i)->stripPointerCasts()))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
546 MustKeepGlobalVariables.insert(G);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
547 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
548
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
549 void GlobalMerge::setMustKeepGlobalVariables(Module &M) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
550 collectUsedGlobalVariables(M);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
551
|
|
120
|
552 for (Function &F : M) {
|
|
|
553 for (BasicBlock &BB : F) {
|
|
|
554 Instruction *Pad = BB.getFirstNonPHI();
|
|
|
555 if (!Pad->isEHPad())
|
|
|
556 continue;
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
557
|
|
120
|
558 // Keep globals used by landingpads and catchpads.
|
|
|
559 for (const Use &U : Pad->operands()) {
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
560 if (const GlobalVariable *GV =
|
|
120
|
561 dyn_cast<GlobalVariable>(U->stripPointerCasts()))
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
562 MustKeepGlobalVariables.insert(GV);
|
|
120
|
563 }
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
564 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
565 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
566 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
567
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
568 bool GlobalMerge::doInitialization(Module &M) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
569 if (!EnableGlobalMerge)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
570 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
571
|
|
120
|
572 IsMachO = Triple(M.getTargetTriple()).isOSBinFormatMachO();
|
|
|
573
|
|
95
|
574 auto &DL = M.getDataLayout();
|
|
121
|
575 DenseMap<unsigned, SmallVector<GlobalVariable *, 16>> Globals, ConstGlobals,
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
576 BSSGlobals;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
577 bool Changed = false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
578 setMustKeepGlobalVariables(M);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
579
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
580 // Grab all non-const globals.
|
|
95
|
581 for (auto &GV : M.globals()) {
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
582 // Merge is safe for "normal" internal or external globals only
|
|
121
|
583 if (GV.isDeclaration() || GV.isThreadLocal() ||
|
|
|
584 GV.hasSection() || GV.hasImplicitSection())
|
|
|
585 continue;
|
|
|
586
|
|
|
587 // It's not safe to merge globals that may be preempted
|
|
|
588 if (TM && !TM->shouldAssumeDSOLocal(M, &GV))
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
589 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
590
|
|
95
|
591 if (!(MergeExternalGlobals && GV.hasExternalLinkage()) &&
|
|
|
592 !GV.hasInternalLinkage())
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
593 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
594
|
|
95
|
595 PointerType *PT = dyn_cast<PointerType>(GV.getType());
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
596 assert(PT && "Global variable is not a pointer!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
597
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
598 unsigned AddressSpace = PT->getAddressSpace();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
599
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
600 // Ignore fancy-aligned globals for now.
|
|
95
|
601 unsigned Alignment = DL.getPreferredAlignment(&GV);
|
|
|
602 Type *Ty = GV.getValueType();
|
|
|
603 if (Alignment > DL.getABITypeAlignment(Ty))
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
604 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
605
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
606 // Ignore all 'special' globals.
|
|
95
|
607 if (GV.getName().startswith("llvm.") ||
|
|
|
608 GV.getName().startswith(".llvm."))
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
609 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
610
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
611 // Ignore all "required" globals:
|
|
95
|
612 if (isMustKeepGlobalVariable(&GV))
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
613 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
614
|
|
95
|
615 if (DL.getTypeAllocSize(Ty) < MaxOffset) {
|
|
120
|
616 if (TM &&
|
|
|
617 TargetLoweringObjectFile::getKindForGlobal(&GV, *TM).isBSSLocal())
|
|
95
|
618 BSSGlobals[AddressSpace].push_back(&GV);
|
|
|
619 else if (GV.isConstant())
|
|
|
620 ConstGlobals[AddressSpace].push_back(&GV);
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
621 else
|
|
95
|
622 Globals[AddressSpace].push_back(&GV);
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
623 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
624 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
625
|
|
95
|
626 for (auto &P : Globals)
|
|
|
627 if (P.second.size() > 1)
|
|
|
628 Changed |= doMerge(P.second, M, false, P.first);
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
629
|
|
95
|
630 for (auto &P : BSSGlobals)
|
|
|
631 if (P.second.size() > 1)
|
|
|
632 Changed |= doMerge(P.second, M, false, P.first);
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
633
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
634 if (EnableGlobalMergeOnConst)
|
|
95
|
635 for (auto &P : ConstGlobals)
|
|
|
636 if (P.second.size() > 1)
|
|
|
637 Changed |= doMerge(P.second, M, true, P.first);
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
638
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
639 return Changed;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
640 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
641
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
642 bool GlobalMerge::runOnFunction(Function &F) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
643 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
644 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
645
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
646 bool GlobalMerge::doFinalization(Module &M) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
647 MustKeepGlobalVariables.clear();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
648 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
649 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
650
|
|
95
|
651 Pass *llvm::createGlobalMergePass(const TargetMachine *TM, unsigned Offset,
|
|
|
652 bool OnlyOptimizeForSize,
|
|
|
653 bool MergeExternalByDefault) {
|
|
|
654 bool MergeExternal = (EnableGlobalMergeOnExternal == cl::BOU_UNSET) ?
|
|
|
655 MergeExternalByDefault : (EnableGlobalMergeOnExternal == cl::BOU_TRUE);
|
|
|
656 return new GlobalMerge(TM, Offset, OnlyOptimizeForSize, MergeExternal);
|
77
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
657 }
|
