Coverage Report

Created: 2019-07-24 05:18

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