Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===//
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 file implements a trivial dead store elimination that only considers
10
// basic-block local redundant stores.
11
//
12
// FIXME: This should eventually be extended to be a post-dominator tree
13
// traversal.  Doing so would be pretty trivial.
14
//
15
//===----------------------------------------------------------------------===//
16
17
#include "llvm/Transforms/Scalar/DeadStoreElimination.h"
18
#include "llvm/ADT/APInt.h"
19
#include "llvm/ADT/DenseMap.h"
20
#include "llvm/ADT/SetVector.h"
21
#include "llvm/ADT/SmallPtrSet.h"
22
#include "llvm/ADT/SmallVector.h"
23
#include "llvm/ADT/Statistic.h"
24
#include "llvm/ADT/StringRef.h"
25
#include "llvm/Analysis/AliasAnalysis.h"
26
#include "llvm/Analysis/CaptureTracking.h"
27
#include "llvm/Analysis/GlobalsModRef.h"
28
#include "llvm/Analysis/MemoryBuiltins.h"
29
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
30
#include "llvm/Analysis/MemoryLocation.h"
31
#include "llvm/Analysis/OrderedBasicBlock.h"
32
#include "llvm/Analysis/TargetLibraryInfo.h"
33
#include "llvm/Analysis/ValueTracking.h"
34
#include "llvm/IR/Argument.h"
35
#include "llvm/IR/BasicBlock.h"
36
#include "llvm/IR/CallSite.h"
37
#include "llvm/IR/Constant.h"
38
#include "llvm/IR/Constants.h"
39
#include "llvm/IR/DataLayout.h"
40
#include "llvm/IR/Dominators.h"
41
#include "llvm/IR/Function.h"
42
#include "llvm/IR/InstrTypes.h"
43
#include "llvm/IR/Instruction.h"
44
#include "llvm/IR/Instructions.h"
45
#include "llvm/IR/IntrinsicInst.h"
46
#include "llvm/IR/Intrinsics.h"
47
#include "llvm/IR/LLVMContext.h"
48
#include "llvm/IR/Module.h"
49
#include "llvm/IR/PassManager.h"
50
#include "llvm/IR/Value.h"
51
#include "llvm/Pass.h"
52
#include "llvm/Support/Casting.h"
53
#include "llvm/Support/CommandLine.h"
54
#include "llvm/Support/Debug.h"
55
#include "llvm/Support/ErrorHandling.h"
56
#include "llvm/Support/MathExtras.h"
57
#include "llvm/Support/raw_ostream.h"
58
#include "llvm/Transforms/Scalar.h"
59
#include "llvm/Transforms/Utils/Local.h"
60
#include <algorithm>
61
#include <cassert>
62
#include <cstddef>
63
#include <cstdint>
64
#include <iterator>
65
#include <map>
66
#include <utility>
67
68
using namespace llvm;
69
70
#define DEBUG_TYPE "dse"
71
72
STATISTIC(NumRedundantStores, "Number of redundant stores deleted");
73
STATISTIC(NumFastStores, "Number of stores deleted");
74
STATISTIC(NumFastOther, "Number of other instrs removed");
75
STATISTIC(NumCompletePartials, "Number of stores dead by later partials");
76
STATISTIC(NumModifiedStores, "Number of stores modified");
77
78
static cl::opt<bool>
79
EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking",
80
  cl::init(true), cl::Hidden,
81
  cl::desc("Enable partial-overwrite tracking in DSE"));
82
83
static cl::opt<bool>
84
EnablePartialStoreMerging("enable-dse-partial-store-merging",
85
  cl::init(true), cl::Hidden,
86
  cl::desc("Enable partial store merging in DSE"));
87
88
//===----------------------------------------------------------------------===//
89
// Helper functions
90
//===----------------------------------------------------------------------===//
91
using OverlapIntervalsTy = std::map<int64_t, int64_t>;
92
using InstOverlapIntervalsTy = DenseMap<Instruction *, OverlapIntervalsTy>;
93
94
/// Delete this instruction.  Before we do, go through and zero out all the
95
/// operands of this instruction.  If any of them become dead, delete them and
96
/// the computation tree that feeds them.
97
/// If ValueSet is non-null, remove any deleted instructions from it as well.
98
static void
99
deleteDeadInstruction(Instruction *I, BasicBlock::iterator *BBI,
100
                      MemoryDependenceResults &MD, const TargetLibraryInfo &TLI,
101
                      InstOverlapIntervalsTy &IOL, OrderedBasicBlock &OBB,
102
8.39k
                      SmallSetVector<const Value *, 16> *ValueSet = nullptr) {
103
8.39k
  SmallVector<Instruction*, 32> NowDeadInsts;
104
8.39k
105
8.39k
  NowDeadInsts.push_back(I);
106
8.39k
  --NumFastOther;
107
8.39k
108
8.39k
  // Keeping the iterator straight is a pain, so we let this routine tell the
109
8.39k
  // caller what the next instruction is after we're done mucking about.
110
8.39k
  BasicBlock::iterator NewIter = *BBI;
111
8.39k
112
8.39k
  // Before we touch this instruction, remove it from memdep!
113
10.5k
  do {
114
10.5k
    Instruction *DeadInst = NowDeadInsts.pop_back_val();
115
10.5k
    ++NumFastOther;
116
10.5k
117
10.5k
    // Try to preserve debug information attached to the dead instruction.
118
10.5k
    salvageDebugInfo(*DeadInst);
119
10.5k
120
10.5k
    // This instruction is dead, zap it, in stages.  Start by removing it from
121
10.5k
    // MemDep, which needs to know the operands and needs it to be in the
122
10.5k
    // function.
123
10.5k
    MD.removeInstruction(DeadInst);
124
10.5k
125
33.2k
    for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; 
++op22.7k
) {
126
22.7k
      Value *Op = DeadInst->getOperand(op);
127
22.7k
      DeadInst->setOperand(op, nullptr);
128
22.7k
129
22.7k
      // If this operand just became dead, add it to the NowDeadInsts list.
130
22.7k
      if (!Op->use_empty()) 
continue20.0k
;
131
2.64k
132
2.64k
      if (Instruction *OpI = dyn_cast<Instruction>(Op))
133
2.13k
        if (isInstructionTriviallyDead(OpI, &TLI))
134
2.13k
          NowDeadInsts.push_back(OpI);
135
2.64k
    }
136
10.5k
137
10.5k
    if (ValueSet) 
ValueSet->remove(DeadInst)360
;
138
10.5k
    IOL.erase(DeadInst);
139
10.5k
    OBB.eraseInstruction(DeadInst);
140
10.5k
141
10.5k
    if (NewIter == DeadInst->getIterator())
142
475
      NewIter = DeadInst->eraseFromParent();
143
10.0k
    else
144
10.0k
      DeadInst->eraseFromParent();
145
10.5k
  } while (!NowDeadInsts.empty());
146
8.39k
  *BBI = NewIter;
147
8.39k
}
148
149
/// Does this instruction write some memory?  This only returns true for things
150
/// that we can analyze with other helpers below.
151
static bool hasAnalyzableMemoryWrite(Instruction *I,
152
16.6M
                                     const TargetLibraryInfo &TLI) {
153
16.6M
  if (isa<StoreInst>(I))
154
1.45M
    return true;
155
15.2M
  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
156
413k
    switch (II->getIntrinsicID()) {
157
413k
    default:
158
192k
      return false;
159
413k
    case Intrinsic::memset:
160
221k
    case Intrinsic::memmove:
161
221k
    case Intrinsic::memcpy:
162
221k
    case Intrinsic::memcpy_element_unordered_atomic:
163
221k
    case Intrinsic::memmove_element_unordered_atomic:
164
221k
    case Intrinsic::memset_element_unordered_atomic:
165
221k
    case Intrinsic::init_trampoline:
166
221k
    case Intrinsic::lifetime_end:
167
221k
      return true;
168
14.8M
    }
169
14.8M
  }
170
14.8M
  if (auto CS = CallSite(I)) {
171
1.95M
    if (Function *F = CS.getCalledFunction()) {
172
1.84M
      StringRef FnName = F->getName();
173
1.84M
      if (TLI.has(LibFunc_strcpy) && 
FnName == TLI.getName(LibFunc_strcpy)1.45M
)
174
338
        return true;
175
1.84M
      if (TLI.has(LibFunc_strncpy) && 
FnName == TLI.getName(LibFunc_strncpy)1.45M
)
176
80
        return true;
177
1.84M
      if (TLI.has(LibFunc_strcat) && 
FnName == TLI.getName(LibFunc_strcat)1.45M
)
178
47
        return true;
179
1.84M
      if (TLI.has(LibFunc_strncat) && 
FnName == TLI.getName(LibFunc_strncat)1.45M
)
180
2
        return true;
181
14.8M
    }
182
1.95M
  }
183
14.8M
  return false;
184
14.8M
}
185
186
/// Return a Location stored to by the specified instruction. If isRemovable
187
/// returns true, this function and getLocForRead completely describe the memory
188
/// operations for this instruction.
189
864k
static MemoryLocation getLocForWrite(Instruction *Inst) {
190
864k
191
864k
  if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
192
747k
    return MemoryLocation::get(SI);
193
117k
194
117k
  if (auto *MI = dyn_cast<AnyMemIntrinsic>(Inst)) {
195
65.6k
    // memcpy/memmove/memset.
196
65.6k
    MemoryLocation Loc = MemoryLocation::getForDest(MI);
197
65.6k
    return Loc;
198
65.6k
  }
199
51.5k
200
51.5k
  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
201
51.1k
    switch (II->getIntrinsicID()) {
202
51.1k
    default:
203
0
      return MemoryLocation(); // Unhandled intrinsic.
204
51.1k
    case Intrinsic::init_trampoline:
205
2
      return MemoryLocation(II->getArgOperand(0));
206
51.1k
    case Intrinsic::lifetime_end: {
207
51.1k
      uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue();
208
51.1k
      return MemoryLocation(II->getArgOperand(1), Len);
209
383
    }
210
383
    }
211
383
  }
212
383
  if (auto CS = CallSite(Inst))
213
383
    // All the supported TLI functions so far happen to have dest as their
214
383
    // first argument.
215
383
    return MemoryLocation(CS.getArgument(0));
216
0
  return MemoryLocation();
217
0
}
218
219
/// Return the location read by the specified "hasAnalyzableMemoryWrite"
220
/// instruction if any.
221
static MemoryLocation getLocForRead(Instruction *Inst,
222
106k
                                    const TargetLibraryInfo &TLI) {
223
106k
  assert(hasAnalyzableMemoryWrite(Inst, TLI) && "Unknown instruction case");
224
106k
225
106k
  // The only instructions that both read and write are the mem transfer
226
106k
  // instructions (memcpy/memmove).
227
106k
  if (auto *MTI = dyn_cast<AnyMemTransferInst>(Inst))
228
9.05k
    return MemoryLocation::getForSource(MTI);
229
97.0k
  return MemoryLocation();
230
97.0k
}
231
232
/// If the value of this instruction and the memory it writes to is unused, may
233
/// we delete this instruction?
234
590k
static bool isRemovable(Instruction *I) {
235
590k
  // Don't remove volatile/atomic stores.
236
590k
  if (StoreInst *SI = dyn_cast<StoreInst>(I))
237
526k
    return SI->isUnordered();
238
63.7k
239
63.7k
  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
240
63.5k
    switch (II->getIntrinsicID()) {
241
63.5k
    
default: 0
llvm_unreachable0
("doesn't pass 'hasAnalyzableMemoryWrite' predicate");
242
63.5k
    case Intrinsic::lifetime_end:
243
31.4k
      // Never remove dead lifetime_end's, e.g. because it is followed by a
244
31.4k
      // free.
245
31.4k
      return false;
246
63.5k
    case Intrinsic::init_trampoline:
247
2
      // Always safe to remove init_trampoline.
248
2
      return true;
249
63.5k
    case Intrinsic::memset:
250
32.0k
    case Intrinsic::memmove:
251
32.0k
    case Intrinsic::memcpy:
252
32.0k
      // Don't remove volatile memory intrinsics.
253
32.0k
      return !cast<MemIntrinsic>(II)->isVolatile();
254
32.0k
    case Intrinsic::memcpy_element_unordered_atomic:
255
109
    case Intrinsic::memmove_element_unordered_atomic:
256
109
    case Intrinsic::memset_element_unordered_atomic:
257
109
      return true;
258
154
    }
259
154
  }
260
154
261
154
  // note: only get here for calls with analyzable writes - i.e. libcalls
262
154
  if (auto CS = CallSite(I))
263
154
    return CS.getInstruction()->use_empty();
264
0
265
0
  return false;
266
0
}
267
268
/// Returns true if the end of this instruction can be safely shortened in
269
/// length.
270
3.20k
static bool isShortenableAtTheEnd(Instruction *I) {
271
3.20k
  // Don't shorten stores for now
272
3.20k
  if (isa<StoreInst>(I))
273
36
    return false;
274
3.17k
275
3.17k
  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
276
3.17k
    switch (II->getIntrinsicID()) {
277
3.17k
      
default: return false0
;
278
3.17k
      case Intrinsic::memset:
279
3.17k
      case Intrinsic::memcpy:
280
3.17k
      case Intrinsic::memcpy_element_unordered_atomic:
281
3.17k
      case Intrinsic::memset_element_unordered_atomic:
282
3.17k
        // Do shorten memory intrinsics.
283
3.17k
        // FIXME: Add memmove if it's also safe to transform.
284
3.17k
        return true;
285
0
    }
286
0
  }
287
0
288
0
  // Don't shorten libcalls calls for now.
289
0
290
0
  return false;
291
0
}
292
293
/// Returns true if the beginning of this instruction can be safely shortened
294
/// in length.
295
3.14k
static bool isShortenableAtTheBeginning(Instruction *I) {
296
3.14k
  // FIXME: Handle only memset for now. Supporting memcpy/memmove should be
297
3.14k
  // easily done by offsetting the source address.
298
3.14k
  return isa<AnyMemSetInst>(I);
299
3.14k
}
300
301
/// Return the pointer that is being written to.
302
140k
static Value *getStoredPointerOperand(Instruction *I) {
303
140k
  //TODO: factor this to reuse getLocForWrite
304
140k
  MemoryLocation Loc = getLocForWrite(I);
305
140k
  assert(Loc.Ptr &&
306
140k
         "unable to find pointer written for analyzable instruction?");
307
140k
  // TODO: most APIs don't expect const Value *
308
140k
  return const_cast<Value*>(Loc.Ptr);
309
140k
}
310
311
static uint64_t getPointerSize(const Value *V, const DataLayout &DL,
312
                               const TargetLibraryInfo &TLI,
313
211k
                               const Function *F) {
314
211k
  uint64_t Size;
315
211k
  ObjectSizeOpts Opts;
316
211k
  Opts.NullIsUnknownSize = NullPointerIsDefined(F);
317
211k
318
211k
  if (getObjectSize(V, Size, DL, &TLI, Opts))
319
189k
    return Size;
320
21.8k
  return MemoryLocation::UnknownSize;
321
21.8k
}
322
323
namespace {
324
325
enum OverwriteResult {
326
  OW_Begin,
327
  OW_Complete,
328
  OW_End,
329
  OW_PartialEarlierWithFullLater,
330
  OW_Unknown
331
};
332
333
} // end anonymous namespace
334
335
/// Return 'OW_Complete' if a store to the 'Later' location completely
336
/// overwrites a store to the 'Earlier' location, 'OW_End' if the end of the
337
/// 'Earlier' location is completely overwritten by 'Later', 'OW_Begin' if the
338
/// beginning of the 'Earlier' location is overwritten by 'Later'.
339
/// 'OW_PartialEarlierWithFullLater' means that an earlier (big) store was
340
/// overwritten by a latter (smaller) store which doesn't write outside the big
341
/// store's memory locations. Returns 'OW_Unknown' if nothing can be determined.
342
static OverwriteResult isOverwrite(const MemoryLocation &Later,
343
                                   const MemoryLocation &Earlier,
344
                                   const DataLayout &DL,
345
                                   const TargetLibraryInfo &TLI,
346
                                   int64_t &EarlierOff, int64_t &LaterOff,
347
                                   Instruction *DepWrite,
348
                                   InstOverlapIntervalsTy &IOL,
349
                                   AliasAnalysis &AA,
350
96.6k
                                   const Function *F) {
351
96.6k
  // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
352
96.6k
  // get imprecise values here, though (except for unknown sizes).
353
96.6k
  if (!Later.Size.isPrecise() || 
!Earlier.Size.isPrecise()96.4k
)
354
976
    return OW_Unknown;
355
95.6k
356
95.6k
  const uint64_t LaterSize = Later.Size.getValue();
357
95.6k
  const uint64_t EarlierSize = Earlier.Size.getValue();
358
95.6k
359
95.6k
  const Value *P1 = Earlier.Ptr->stripPointerCasts();
360
95.6k
  const Value *P2 = Later.Ptr->stripPointerCasts();
361
95.6k
362
95.6k
  // If the start pointers are the same, we just have to compare sizes to see if
363
95.6k
  // the later store was larger than the earlier store.
364
95.6k
  if (P1 == P2 || 
AA.isMustAlias(P1, P2)85.9k
) {
365
9.90k
    // Make sure that the Later size is >= the Earlier size.
366
9.90k
    if (LaterSize >= EarlierSize)
367
6.68k
      return OW_Complete;
368
89.0k
  }
369
89.0k
370
89.0k
  // Check to see if the later store is to the entire object (either a global,
371
89.0k
  // an alloca, or a byval/inalloca argument).  If so, then it clearly
372
89.0k
  // overwrites any other store to the same object.
373
89.0k
  const Value *UO1 = GetUnderlyingObject(P1, DL),
374
89.0k
              *UO2 = GetUnderlyingObject(P2, DL);
375
89.0k
376
89.0k
  // If we can't resolve the same pointers to the same object, then we can't
377
89.0k
  // analyze them at all.
378
89.0k
  if (UO1 != UO2)
379
61.2k
    return OW_Unknown;
380
27.7k
381
27.7k
  // If the "Later" store is to a recognizable object, get its size.
382
27.7k
  uint64_t ObjectSize = getPointerSize(UO2, DL, TLI, F);
383
27.7k
  if (ObjectSize != MemoryLocation::UnknownSize)
384
6.21k
    if (ObjectSize == LaterSize && 
ObjectSize >= EarlierSize448
)
385
448
      return OW_Complete;
386
27.3k
387
27.3k
  // Okay, we have stores to two completely different pointers.  Try to
388
27.3k
  // decompose the pointer into a "base + constant_offset" form.  If the base
389
27.3k
  // pointers are equal, then we can reason about the two stores.
390
27.3k
  EarlierOff = 0;
391
27.3k
  LaterOff = 0;
392
27.3k
  const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, DL);
393
27.3k
  const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, DL);
394
27.3k
395
27.3k
  // If the base pointers still differ, we have two completely different stores.
396
27.3k
  if (BP1 != BP2)
397
17.9k
    return OW_Unknown;
398
9.33k
399
9.33k
  // The later store completely overlaps the earlier store if:
400
9.33k
  //
401
9.33k
  // 1. Both start at the same offset and the later one's size is greater than
402
9.33k
  //    or equal to the earlier one's, or
403
9.33k
  //
404
9.33k
  //      |--earlier--|
405
9.33k
  //      |--   later   --|
406
9.33k
  //
407
9.33k
  // 2. The earlier store has an offset greater than the later offset, but which
408
9.33k
  //    still lies completely within the later store.
409
9.33k
  //
410
9.33k
  //        |--earlier--|
411
9.33k
  //    |-----  later  ------|
412
9.33k
  //
413
9.33k
  // We have to be careful here as *Off is signed while *.Size is unsigned.
414
9.33k
  if (EarlierOff >= LaterOff &&
415
9.33k
      
LaterSize >= EarlierSize3.45k
&&
416
9.33k
      
uint64_t(EarlierOff - LaterOff) + EarlierSize <= LaterSize54
)
417
21
    return OW_Complete;
418
9.31k
419
9.31k
  // We may now overlap, although the overlap is not complete. There might also
420
9.31k
  // be other incomplete overlaps, and together, they might cover the complete
421
9.31k
  // earlier write.
422
9.31k
  // Note: The correctness of this logic depends on the fact that this function
423
9.31k
  // is not even called providing DepWrite when there are any intervening reads.
424
9.31k
  if (EnablePartialOverwriteTracking &&
425
9.31k
      LaterOff < int64_t(EarlierOff + EarlierSize) &&
426
9.31k
      
int64_t(LaterOff + LaterSize) >= EarlierOff7.80k
) {
427
7.61k
428
7.61k
    // Insert our part of the overlap into the map.
429
7.61k
    auto &IM = IOL[DepWrite];
430
7.61k
    LLVM_DEBUG(dbgs() << "DSE: Partial overwrite: Earlier [" << EarlierOff
431
7.61k
                      << ", " << int64_t(EarlierOff + EarlierSize)
432
7.61k
                      << ") Later [" << LaterOff << ", "
433
7.61k
                      << int64_t(LaterOff + LaterSize) << ")\n");
434
7.61k
435
7.61k
    // Make sure that we only insert non-overlapping intervals and combine
436
7.61k
    // adjacent intervals. The intervals are stored in the map with the ending
437
7.61k
    // offset as the key (in the half-open sense) and the starting offset as
438
7.61k
    // the value.
439
7.61k
    int64_t LaterIntStart = LaterOff, LaterIntEnd = LaterOff + LaterSize;
440
7.61k
441
7.61k
    // Find any intervals ending at, or after, LaterIntStart which start
442
7.61k
    // before LaterIntEnd.
443
7.61k
    auto ILI = IM.lower_bound(LaterIntStart);
444
7.61k
    if (ILI != IM.end() && 
ILI->second <= LaterIntEnd3.54k
) {
445
2.31k
      // This existing interval is overlapped with the current store somewhere
446
2.31k
      // in [LaterIntStart, LaterIntEnd]. Merge them by erasing the existing
447
2.31k
      // intervals and adjusting our start and end.
448
2.31k
      LaterIntStart = std::min(LaterIntStart, ILI->second);
449
2.31k
      LaterIntEnd = std::max(LaterIntEnd, ILI->first);
450
2.31k
      ILI = IM.erase(ILI);
451
2.31k
452
2.31k
      // Continue erasing and adjusting our end in case other previous
453
2.31k
      // intervals are also overlapped with the current store.
454
2.31k
      //
455
2.31k
      // |--- ealier 1 ---|  |--- ealier 2 ---|
456
2.31k
      //     |------- later---------|
457
2.31k
      //
458
2.40k
      while (ILI != IM.end() && 
ILI->second <= LaterIntEnd1.22k
) {
459
86
        assert(ILI->second > LaterIntStart && "Unexpected interval");
460
86
        LaterIntEnd = std::max(LaterIntEnd, ILI->first);
461
86
        ILI = IM.erase(ILI);
462
86
      }
463
2.31k
    }
464
7.61k
465
7.61k
    IM[LaterIntEnd] = LaterIntStart;
466
7.61k
467
7.61k
    ILI = IM.begin();
468
7.61k
    if (ILI->second <= EarlierOff &&
469
7.61k
        
ILI->first >= int64_t(EarlierOff + EarlierSize)5.50k
) {
470
280
      LLVM_DEBUG(dbgs() << "DSE: Full overwrite from partials: Earlier ["
471
280
                        << EarlierOff << ", "
472
280
                        << int64_t(EarlierOff + EarlierSize)
473
280
                        << ") Composite Later [" << ILI->second << ", "
474
280
                        << ILI->first << ")\n");
475
280
      ++NumCompletePartials;
476
280
      return OW_Complete;
477
280
    }
478
9.03k
  }
479
9.03k
480
9.03k
  // Check for an earlier store which writes to all the memory locations that
481
9.03k
  // the later store writes to.
482
9.03k
  if (EnablePartialStoreMerging && 
LaterOff >= EarlierOff8.99k
&&
483
9.03k
      
int64_t(EarlierOff + EarlierSize) > LaterOff8.78k
&&
484
9.03k
      
uint64_t(LaterOff - EarlierOff) + LaterSize <= EarlierSize7.28k
) {
485
7.28k
    LLVM_DEBUG(dbgs() << "DSE: Partial overwrite an earlier load ["
486
7.28k
                      << EarlierOff << ", "
487
7.28k
                      << int64_t(EarlierOff + EarlierSize)
488
7.28k
                      << ") by a later store [" << LaterOff << ", "
489
7.28k
                      << int64_t(LaterOff + LaterSize) << ")\n");
490
7.28k
    // TODO: Maybe come up with a better name?
491
7.28k
    return OW_PartialEarlierWithFullLater;
492
7.28k
  }
493
1.75k
494
1.75k
  // Another interesting case is if the later store overwrites the end of the
495
1.75k
  // earlier store.
496
1.75k
  //
497
1.75k
  //      |--earlier--|
498
1.75k
  //                |--   later   --|
499
1.75k
  //
500
1.75k
  // In this case we may want to trim the size of earlier to avoid generating
501
1.75k
  // writes to addresses which will definitely be overwritten later
502
1.75k
  if (!EnablePartialOverwriteTracking &&
503
1.75k
      
(0
LaterOff > EarlierOff0
&&
LaterOff < int64_t(EarlierOff + EarlierSize)0
&&
504
0
       int64_t(LaterOff + LaterSize) >= int64_t(EarlierOff + EarlierSize)))
505
0
    return OW_End;
506
1.75k
507
1.75k
  // Finally, we also need to check if the later store overwrites the beginning
508
1.75k
  // of the earlier store.
509
1.75k
  //
510
1.75k
  //                |--earlier--|
511
1.75k
  //      |--   later   --|
512
1.75k
  //
513
1.75k
  // In this case we may want to move the destination address and trim the size
514
1.75k
  // of earlier to avoid generating writes to addresses which will definitely
515
1.75k
  // be overwritten later.
516
1.75k
  if (!EnablePartialOverwriteTracking &&
517
1.75k
      
(0
LaterOff <= EarlierOff0
&&
int64_t(LaterOff + LaterSize) > EarlierOff0
)) {
518
0
    assert(int64_t(LaterOff + LaterSize) < int64_t(EarlierOff + EarlierSize) &&
519
0
           "Expect to be handled as OW_Complete");
520
0
    return OW_Begin;
521
0
  }
522
1.75k
  // Otherwise, they don't completely overlap.
523
1.75k
  return OW_Unknown;
524
1.75k
}
525
526
/// If 'Inst' might be a self read (i.e. a noop copy of a
527
/// memory region into an identical pointer) then it doesn't actually make its
528
/// input dead in the traditional sense.  Consider this case:
529
///
530
///   memmove(A <- B)
531
///   memmove(A <- A)
532
///
533
/// In this case, the second store to A does not make the first store to A dead.
534
/// The usual situation isn't an explicit A<-A store like this (which can be
535
/// trivially removed) but a case where two pointers may alias.
536
///
537
/// This function detects when it is unsafe to remove a dependent instruction
538
/// because the DSE inducing instruction may be a self-read.
539
static bool isPossibleSelfRead(Instruction *Inst,
540
                               const MemoryLocation &InstStoreLoc,
541
                               Instruction *DepWrite,
542
                               const TargetLibraryInfo &TLI,
543
101k
                               AliasAnalysis &AA) {
544
101k
  // Self reads can only happen for instructions that read memory.  Get the
545
101k
  // location read.
546
101k
  MemoryLocation InstReadLoc = getLocForRead(Inst, TLI);
547
101k
  if (!InstReadLoc.Ptr)
548
94.5k
    return false; // Not a reading instruction.
549
6.90k
550
6.90k
  // If the read and written loc obviously don't alias, it isn't a read.
551
6.90k
  if (AA.isNoAlias(InstReadLoc, InstStoreLoc))
552
2.14k
    return false;
553
4.75k
554
4.75k
  if (isa<AnyMemCpyInst>(Inst)) {
555
4.73k
    // LLVM's memcpy overlap semantics are not fully fleshed out (see PR11763)
556
4.73k
    // but in practice memcpy(A <- B) either means that A and B are disjoint or
557
4.73k
    // are equal (i.e. there are not partial overlaps).  Given that, if we have:
558
4.73k
    //
559
4.73k
    //   memcpy/memmove(A <- B)  // DepWrite
560
4.73k
    //   memcpy(A <- B)  // Inst
561
4.73k
    //
562
4.73k
    // with Inst reading/writing a >= size than DepWrite, we can reason as
563
4.73k
    // follows:
564
4.73k
    //
565
4.73k
    //   - If A == B then both the copies are no-ops, so the DepWrite can be
566
4.73k
    //     removed.
567
4.73k
    //   - If A != B then A and B are disjoint locations in Inst.  Since
568
4.73k
    //     Inst.size >= DepWrite.size A and B are disjoint in DepWrite too.
569
4.73k
    //     Therefore DepWrite can be removed.
570
4.73k
    MemoryLocation DepReadLoc = getLocForRead(DepWrite, TLI);
571
4.73k
572
4.73k
    if (DepReadLoc.Ptr && 
AA.isMustAlias(InstReadLoc.Ptr, DepReadLoc.Ptr)2.15k
)
573
16
      return false;
574
4.73k
  }
575
4.73k
576
4.73k
  // If DepWrite doesn't read memory or if we can't prove it is a must alias,
577
4.73k
  // then it can't be considered dead.
578
4.73k
  return true;
579
4.73k
}
580
581
/// Returns true if the memory which is accessed by the second instruction is not
582
/// modified between the first and the second instruction.
583
/// Precondition: Second instruction must be dominated by the first
584
/// instruction.
585
static bool memoryIsNotModifiedBetween(Instruction *FirstI,
586
                                       Instruction *SecondI,
587
1.12k
                                       AliasAnalysis *AA) {
588
1.12k
  SmallVector<BasicBlock *, 16> WorkList;
589
1.12k
  SmallPtrSet<BasicBlock *, 8> Visited;
590
1.12k
  BasicBlock::iterator FirstBBI(FirstI);
591
1.12k
  ++FirstBBI;
592
1.12k
  BasicBlock::iterator SecondBBI(SecondI);
593
1.12k
  BasicBlock *FirstBB = FirstI->getParent();
594
1.12k
  BasicBlock *SecondBB = SecondI->getParent();
595
1.12k
  MemoryLocation MemLoc = MemoryLocation::get(SecondI);
596
1.12k
597
1.12k
  // Start checking the store-block.
598
1.12k
  WorkList.push_back(SecondBB);
599
1.12k
  bool isFirstBlock = true;
600
1.12k
601
1.12k
  // Check all blocks going backward until we reach the load-block.
602
3.22k
  while (!WorkList.empty()) {
603
2.92k
    BasicBlock *B = WorkList.pop_back_val();
604
2.92k
605
2.92k
    // Ignore instructions before LI if this is the FirstBB.
606
2.92k
    BasicBlock::iterator BI = (B == FirstBB ? 
FirstBBI828
:
B->begin()2.10k
);
607
2.92k
608
2.92k
    BasicBlock::iterator EI;
609
2.92k
    if (isFirstBlock) {
610
1.12k
      // Ignore instructions after SI if this is the first visit of SecondBB.
611
1.12k
      assert(B == SecondBB && "first block is not the store block");
612
1.12k
      EI = SecondBBI;
613
1.12k
      isFirstBlock = false;
614
1.79k
    } else {
615
1.79k
      // It's not SecondBB or (in case of a loop) the second visit of SecondBB.
616
1.79k
      // In this case we also have to look at instructions after SI.
617
1.79k
      EI = B->end();
618
1.79k
    }
619
16.2k
    for (; BI != EI; 
++BI13.3k
) {
620
14.1k
      Instruction *I = &*BI;
621
14.1k
      if (I->mayWriteToMemory() && 
I != SecondI2.72k
)
622
2.71k
        if (isModSet(AA->getModRefInfo(I, MemLoc)))
623
835
          return false;
624
14.1k
    }
625
2.92k
    
if (2.09k
B != FirstBB2.09k
) {
626
1.70k
      assert(B != &FirstBB->getParent()->getEntryBlock() &&
627
1.70k
          "Should not hit the entry block because SI must be dominated by LI");
628
4.62k
      for (auto PredI = pred_begin(B), PE = pred_end(B); PredI != PE; 
++PredI2.92k
) {
629
2.92k
        if (!Visited.insert(*PredI).second)
630
180
          continue;
631
2.74k
        WorkList.push_back(*PredI);
632
2.74k
      }
633
1.70k
    }
634
2.09k
  }
635
1.12k
  
return true294
;
636
1.12k
}
637
638
/// Find all blocks that will unconditionally lead to the block BB and append
639
/// them to F.
640
static void findUnconditionalPreds(SmallVectorImpl<BasicBlock *> &Blocks,
641
13.3k
                                   BasicBlock *BB, DominatorTree *DT) {
642
30.6k
  for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; 
++I17.3k
) {
643
17.3k
    BasicBlock *Pred = *I;
644
17.3k
    if (Pred == BB) 
continue24
;
645
17.2k
    Instruction *PredTI = Pred->getTerminator();
646
17.2k
    if (PredTI->getNumSuccessors() != 1)
647
15.0k
      continue;
648
2.22k
649
2.22k
    if (DT->isReachableFromEntry(Pred))
650
2.22k
      Blocks.push_back(Pred);
651
2.22k
  }
652
13.3k
}
653
654
/// Handle frees of entire structures whose dependency is a store
655
/// to a field of that structure.
656
static bool handleFree(CallInst *F, AliasAnalysis *AA,
657
                       MemoryDependenceResults *MD, DominatorTree *DT,
658
                       const TargetLibraryInfo *TLI,
659
40.0k
                       InstOverlapIntervalsTy &IOL, OrderedBasicBlock &OBB) {
660
40.0k
  bool MadeChange = false;
661
40.0k
662
40.0k
  MemoryLocation Loc = MemoryLocation(F->getOperand(0));
663
40.0k
  SmallVector<BasicBlock *, 16> Blocks;
664
40.0k
  Blocks.push_back(F->getParent());
665
40.0k
  const DataLayout &DL = F->getModule()->getDataLayout();
666
40.0k
667
82.2k
  while (!Blocks.empty()) {
668
42.2k
    BasicBlock *BB = Blocks.pop_back_val();
669
42.2k
    Instruction *InstPt = BB->getTerminator();
670
42.2k
    if (BB == F->getParent()) 
InstPt = F40.0k
;
671
42.2k
672
42.2k
    MemDepResult Dep =
673
42.2k
        MD->getPointerDependencyFrom(Loc, false, InstPt->getIterator(), BB);
674
42.4k
    while (Dep.isDef() || 
Dep.isClobber()27.9k
) {
675
26.7k
      Instruction *Dependency = Dep.getInst();
676
26.7k
      if (!hasAnalyzableMemoryWrite(Dependency, *TLI) ||
677
26.7k
          
!isRemovable(Dependency)7.38k
)
678
19.4k
        break;
679
7.34k
680
7.34k
      Value *DepPointer =
681
7.34k
          GetUnderlyingObject(getStoredPointerOperand(Dependency), DL);
682
7.34k
683
7.34k
      // Check for aliasing.
684
7.34k
      if (!AA->isMustAlias(F->getArgOperand(0), DepPointer))
685
7.16k
        break;
686
183
687
183
      LLVM_DEBUG(
688
183
          dbgs() << "DSE: Dead Store to soon to be freed memory:\n  DEAD: "
689
183
                 << *Dependency << '\n');
690
183
691
183
      // DCE instructions only used to calculate that store.
692
183
      BasicBlock::iterator BBI(Dependency);
693
183
      deleteDeadInstruction(Dependency, &BBI, *MD, *TLI, IOL, OBB);
694
183
      ++NumFastStores;
695
183
      MadeChange = true;
696
183
697
183
      // Inst's old Dependency is now deleted. Compute the next dependency,
698
183
      // which may also be dead, as in
699
183
      //    s[0] = 0;
700
183
      //    s[1] = 0; // This has just been deleted.
701
183
      //    free(s);
702
183
      Dep = MD->getPointerDependencyFrom(Loc, false, BBI, BB);
703
183
    }
704
42.2k
705
42.2k
    if (Dep.isNonLocal())
706
13.3k
      findUnconditionalPreds(Blocks, BB, DT);
707
42.2k
  }
708
40.0k
709
40.0k
  return MadeChange;
710
40.0k
}
711
712
/// Check to see if the specified location may alias any of the stack objects in
713
/// the DeadStackObjects set. If so, they become live because the location is
714
/// being loaded.
715
static void removeAccessedObjects(const MemoryLocation &LoadedLoc,
716
                                  SmallSetVector<const Value *, 16> &DeadStackObjects,
717
                                  const DataLayout &DL, AliasAnalysis *AA,
718
                                  const TargetLibraryInfo *TLI,
719
58.0k
                                  const Function *F) {
720
58.0k
  const Value *UnderlyingPointer = GetUnderlyingObject(LoadedLoc.Ptr, DL);
721
58.0k
722
58.0k
  // A constant can't be in the dead pointer set.
723
58.0k
  if (isa<Constant>(UnderlyingPointer))
724
13.7k
    return;
725
44.3k
726
44.3k
  // If the kill pointer can be easily reduced to an alloca, don't bother doing
727
44.3k
  // extraneous AA queries.
728
44.3k
  if (isa<AllocaInst>(UnderlyingPointer) || 
isa<Argument>(UnderlyingPointer)44.0k
) {
729
41.3k
    DeadStackObjects.remove(UnderlyingPointer);
730
41.3k
    return;
731
41.3k
  }
732
3.06k
733
3.06k
  // Remove objects that could alias LoadedLoc.
734
3.06k
  DeadStackObjects.remove_if([&](const Value *I) {
735
394
    // See if the loaded location could alias the stack location.
736
394
    MemoryLocation StackLoc(I, getPointerSize(I, DL, *TLI, F));
737
394
    return !AA->isNoAlias(StackLoc, LoadedLoc);
738
394
  });
739
3.06k
}
740
741
/// Remove dead stores to stack-allocated locations in the function end block.
742
/// Ex:
743
/// %A = alloca i32
744
/// ...
745
/// store i32 1, i32* %A
746
/// ret void
747
static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA,
748
                           MemoryDependenceResults *MD,
749
                           const TargetLibraryInfo *TLI,
750
                           InstOverlapIntervalsTy &IOL,
751
522k
                           OrderedBasicBlock &OBB) {
752
522k
  bool MadeChange = false;
753
522k
754
522k
  // Keep track of all of the stack objects that are dead at the end of the
755
522k
  // function.
756
522k
  SmallSetVector<const Value*, 16> DeadStackObjects;
757
522k
758
522k
  // Find all of the alloca'd pointers in the entry block.
759
522k
  BasicBlock &Entry = BB.getParent()->front();
760
3.60M
  for (Instruction &I : Entry) {
761
3.60M
    if (isa<AllocaInst>(&I))
762
195k
      DeadStackObjects.insert(&I);
763
3.40M
764
3.40M
    // Okay, so these are dead heap objects, but if the pointer never escapes
765
3.40M
    // then it's leaked by this function anyways.
766
3.40M
    else if (isAllocLikeFn(&I, TLI) && 
!PointerMayBeCaptured(&I, true, true)6.55k
)
767
117
      DeadStackObjects.insert(&I);
768
3.60M
  }
769
522k
770
522k
  // Treat byval or inalloca arguments the same, stores to them are dead at the
771
522k
  // end of the function.
772
522k
  for (Argument &AI : BB.getParent()->args())
773
1.07M
    if (AI.hasByValOrInAllocaAttr())
774
580
      DeadStackObjects.insert(&AI);
775
522k
776
522k
  const DataLayout &DL = BB.getModule()->getDataLayout();
777
522k
778
522k
  // Scan the basic block backwards
779
1.53M
  for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
780
1.29M
    --BBI;
781
1.29M
782
1.29M
    // If we find a store, check to see if it points into a dead stack value.
783
1.29M
    if (hasAnalyzableMemoryWrite(&*BBI, *TLI) && 
isRemovable(&*BBI)168k
) {
784
133k
      // See through pointer-to-pointer bitcasts
785
133k
      SmallVector<const Value *, 4> Pointers;
786
133k
      GetUnderlyingObjects(getStoredPointerOperand(&*BBI), Pointers, DL);
787
133k
788
133k
      // Stores to stack values are valid candidates for removal.
789
133k
      bool AllDead = true;
790
133k
      for (const Value *Pointer : Pointers)
791
133k
        if (!DeadStackObjects.count(Pointer)) {
792
133k
          AllDead = false;
793
133k
          break;
794
133k
        }
795
133k
796
133k
      if (AllDead) {
797
75
        Instruction *Dead = &*BBI;
798
75
799
75
        LLVM_DEBUG(dbgs() << "DSE: Dead Store at End of Block:\n  DEAD: "
800
75
                          << *Dead << "\n  Objects: ";
801
75
                   for (SmallVectorImpl<const Value *>::iterator I =
802
75
                            Pointers.begin(),
803
75
                        E = Pointers.end();
804
75
                        I != E; ++I) {
805
75
                     dbgs() << **I;
806
75
                     if (std::next(I) != E)
807
75
                       dbgs() << ", ";
808
75
                   } dbgs()
809
75
                   << '\n');
810
75
811
75
        // DCE instructions only used to calculate that store.
812
75
        deleteDeadInstruction(Dead, &BBI, *MD, *TLI, IOL, OBB,
813
75
                              &DeadStackObjects);
814
75
        ++NumFastStores;
815
75
        MadeChange = true;
816
75
        continue;
817
75
      }
818
1.29M
    }
819
1.29M
820
1.29M
    // Remove any dead non-memory-mutating instructions.
821
1.29M
    if (isInstructionTriviallyDead(&*BBI, TLI)) {
822
216
      LLVM_DEBUG(dbgs() << "DSE: Removing trivially dead instruction:\n  DEAD: "
823
216
                        << *&*BBI << '\n');
824
216
      deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, IOL, OBB,
825
216
                            &DeadStackObjects);
826
216
      ++NumFastOther;
827
216
      MadeChange = true;
828
216
      continue;
829
216
    }
830
1.29M
831
1.29M
    if (isa<AllocaInst>(BBI)) {
832
2
      // Remove allocas from the list of dead stack objects; there can't be
833
2
      // any references before the definition.
834
2
      DeadStackObjects.remove(&*BBI);
835
2
      continue;
836
2
    }
837
1.29M
838
1.29M
    if (auto *Call = dyn_cast<CallBase>(&*BBI)) {
839
239k
      // Remove allocation function calls from the list of dead stack objects;
840
239k
      // there can't be any references before the definition.
841
239k
      if (isAllocLikeFn(&*BBI, TLI))
842
1.94k
        DeadStackObjects.remove(&*BBI);
843
239k
844
239k
      // If this call does not access memory, it can't be loading any of our
845
239k
      // pointers.
846
239k
      if (AA->doesNotAccessMemory(Call))
847
6.72k
        continue;
848
232k
849
232k
      // If the call might load from any of our allocas, then any store above
850
232k
      // the call is live.
851
232k
      DeadStackObjects.remove_if([&](const Value *I) {
852
183k
        // See if the call site touches the value.
853
183k
        return isRefSet(AA->getModRefInfo(
854
183k
            Call, I, getPointerSize(I, DL, *TLI, BB.getParent())));
855
183k
      });
856
232k
857
232k
      // If all of the allocas were clobbered by the call then we're not going
858
232k
      // to find anything else to process.
859
232k
      if (DeadStackObjects.empty())
860
215k
        break;
861
16.9k
862
16.9k
      continue;
863
16.9k
    }
864
1.05M
865
1.05M
    // We can remove the dead stores, irrespective of the fence and its ordering
866
1.05M
    // (release/acquire/seq_cst). Fences only constraints the ordering of
867
1.05M
    // already visible stores, it does not make a store visible to other
868
1.05M
    // threads. So, skipping over a fence does not change a store from being
869
1.05M
    // dead.
870
1.05M
    if (isa<FenceInst>(*BBI))
871
143
      continue;
872
1.05M
873
1.05M
    MemoryLocation LoadedLoc;
874
1.05M
875
1.05M
    // If we encounter a use of the pointer, it is no longer considered dead
876
1.05M
    if (LoadInst *L = dyn_cast<LoadInst>(BBI)) {
877
58.8k
      if (!L->isUnordered()) // Be conservative with atomic/volatile load
878
723
        break;
879
58.0k
      LoadedLoc = MemoryLocation::get(L);
880
996k
    } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
881
3
      LoadedLoc = MemoryLocation::get(V);
882
996k
    } else if (!BBI->mayReadFromMemory()) {
883
991k
      // Instruction doesn't read memory.  Note that stores that weren't removed
884
991k
      // above will hit this case.
885
991k
      continue;
886
991k
    } else {
887
5.25k
      // Unknown inst; assume it clobbers everything.
888
5.25k
      break;
889
5.25k
    }
890
58.0k
891
58.0k
    // Remove any allocas from the DeadPointer set that are loaded, as this
892
58.0k
    // makes any stores above the access live.
893
58.0k
    removeAccessedObjects(LoadedLoc, DeadStackObjects, DL, AA, TLI, BB.getParent());
894
58.0k
895
58.0k
    // If all of the allocas were clobbered by the access then we're not going
896
58.0k
    // to find anything else to process.
897
58.0k
    if (DeadStackObjects.empty())
898
56.7k
      break;
899
58.0k
  }
900
522k
901
522k
  return MadeChange;
902
522k
}
903
904
static bool tryToShorten(Instruction *EarlierWrite, int64_t &EarlierOffset,
905
                         int64_t &EarlierSize, int64_t LaterOffset,
906
2.69k
                         int64_t LaterSize, bool IsOverwriteEnd) {
907
2.69k
  // TODO: base this on the target vector size so that if the earlier
908
2.69k
  // store was too small to get vector writes anyway then its likely
909
2.69k
  // a good idea to shorten it
910
2.69k
  // Power of 2 vector writes are probably always a bad idea to optimize
911
2.69k
  // as any store/memset/memcpy is likely using vector instructions so
912
2.69k
  // shortening it to not vector size is likely to be slower
913
2.69k
  auto *EarlierIntrinsic = cast<AnyMemIntrinsic>(EarlierWrite);
914
2.69k
  unsigned EarlierWriteAlign = EarlierIntrinsic->getDestAlignment();
915
2.69k
  if (!IsOverwriteEnd)
916
1.41k
    LaterOffset = int64_t(LaterOffset + LaterSize);
917
2.69k
918
2.69k
  if (!(isPowerOf2_64(LaterOffset) && 
EarlierWriteAlign <= LaterOffset432
) &&
919
2.69k
      
!(2.45k
(EarlierWriteAlign != 0)2.45k
&&
LaterOffset % EarlierWriteAlign == 02.45k
))
920
2.34k
    return false;
921
352
922
352
  int64_t NewLength = IsOverwriteEnd
923
352
                          ? 
LaterOffset - EarlierOffset98
924
352
                          : 
EarlierSize - (LaterOffset - EarlierOffset)254
;
925
352
926
352
  if (auto *AMI = dyn_cast<AtomicMemIntrinsic>(EarlierWrite)) {
927
17
    // When shortening an atomic memory intrinsic, the newly shortened
928
17
    // length must remain an integer multiple of the element size.
929
17
    const uint32_t ElementSize = AMI->getElementSizeInBytes();
930
17
    if (0 != NewLength % ElementSize)
931
0
      return false;
932
352
  }
933
352
934
352
  LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  OW "
935
352
                    << (IsOverwriteEnd ? "END" : "BEGIN") << ": "
936
352
                    << *EarlierWrite << "\n  KILLER (offset " << LaterOffset
937
352
                    << ", " << EarlierSize << ")\n");
938
352
939
352
  Value *EarlierWriteLength = EarlierIntrinsic->getLength();
940
352
  Value *TrimmedLength =
941
352
      ConstantInt::get(EarlierWriteLength->getType(), NewLength);
942
352
  EarlierIntrinsic->setLength(TrimmedLength);
943
352
944
352
  EarlierSize = NewLength;
945
352
  if (!IsOverwriteEnd) {
946
254
    int64_t OffsetMoved = (LaterOffset - EarlierOffset);
947
254
    Value *Indices[1] = {
948
254
        ConstantInt::get(EarlierWriteLength->getType(), OffsetMoved)};
949
254
    GetElementPtrInst *NewDestGEP = GetElementPtrInst::CreateInBounds(
950
254
        EarlierIntrinsic->getRawDest()->getType()->getPointerElementType(),
951
254
        EarlierIntrinsic->getRawDest(), Indices, "", EarlierWrite);
952
254
    NewDestGEP->setDebugLoc(EarlierIntrinsic->getDebugLoc());
953
254
    EarlierIntrinsic->setDest(NewDestGEP);
954
254
    EarlierOffset = EarlierOffset + OffsetMoved;
955
254
  }
956
352
  return true;
957
352
}
958
959
static bool tryToShortenEnd(Instruction *EarlierWrite,
960
                            OverlapIntervalsTy &IntervalMap,
961
3.20k
                            int64_t &EarlierStart, int64_t &EarlierSize) {
962
3.20k
  if (IntervalMap.empty() || !isShortenableAtTheEnd(EarlierWrite))
963
36
    return false;
964
3.17k
965
3.17k
  OverlapIntervalsTy::iterator OII = --IntervalMap.end();
966
3.17k
  int64_t LaterStart = OII->second;
967
3.17k
  int64_t LaterSize = OII->first - LaterStart;
968
3.17k
969
3.17k
  if (LaterStart > EarlierStart && 
LaterStart < EarlierStart + EarlierSize1.56k
&&
970
3.17k
      
LaterStart + LaterSize >= EarlierStart + EarlierSize1.56k
) {
971
1.28k
    if (tryToShorten(EarlierWrite, EarlierStart, EarlierSize, LaterStart,
972
1.28k
                     LaterSize, true)) {
973
98
      IntervalMap.erase(OII);
974
98
      return true;
975
98
    }
976
3.07k
  }
977
3.07k
  return false;
978
3.07k
}
979
980
static bool tryToShortenBegin(Instruction *EarlierWrite,
981
                              OverlapIntervalsTy &IntervalMap,
982
3.14k
                              int64_t &EarlierStart, int64_t &EarlierSize) {
983
3.14k
  if (IntervalMap.empty() || !isShortenableAtTheBeginning(EarlierWrite))
984
1.53k
    return false;
985
1.61k
986
1.61k
  OverlapIntervalsTy::iterator OII = IntervalMap.begin();
987
1.61k
  int64_t LaterStart = OII->second;
988
1.61k
  int64_t LaterSize = OII->first - LaterStart;
989
1.61k
990
1.61k
  if (LaterStart <= EarlierStart && 
LaterStart + LaterSize > EarlierStart1.41k
) {
991
1.41k
    assert(LaterStart + LaterSize < EarlierStart + EarlierSize &&
992
1.41k
           "Should have been handled as OW_Complete");
993
1.41k
    if (tryToShorten(EarlierWrite, EarlierStart, EarlierSize, LaterStart,
994
1.41k
                     LaterSize, false)) {
995
254
      IntervalMap.erase(OII);
996
254
      return true;
997
254
    }
998
1.36k
  }
999
1.36k
  return false;
1000
1.36k
}
1001
1002
static bool removePartiallyOverlappedStores(AliasAnalysis *AA,
1003
                                            const DataLayout &DL,
1004
2.75M
                                            InstOverlapIntervalsTy &IOL) {
1005
2.75M
  bool Changed = false;
1006
2.75M
  for (auto OI : IOL) {
1007
3.20k
    Instruction *EarlierWrite = OI.first;
1008
3.20k
    MemoryLocation Loc = getLocForWrite(EarlierWrite);
1009
3.20k
    assert(isRemovable(EarlierWrite) && "Expect only removable instruction");
1010
3.20k
1011
3.20k
    const Value *Ptr = Loc.Ptr->stripPointerCasts();
1012
3.20k
    int64_t EarlierStart = 0;
1013
3.20k
    int64_t EarlierSize = int64_t(Loc.Size.getValue());
1014
3.20k
    GetPointerBaseWithConstantOffset(Ptr, EarlierStart, DL);
1015
3.20k
    OverlapIntervalsTy &IntervalMap = OI.second;
1016
3.20k
    Changed |=
1017
3.20k
        tryToShortenEnd(EarlierWrite, IntervalMap, EarlierStart, EarlierSize);
1018
3.20k
    if (IntervalMap.empty())
1019
59
      continue;
1020
3.14k
    Changed |=
1021
3.14k
        tryToShortenBegin(EarlierWrite, IntervalMap, EarlierStart, EarlierSize);
1022
3.14k
  }
1023
2.75M
  return Changed;
1024
2.75M
}
1025
1026
static bool eliminateNoopStore(Instruction *Inst, BasicBlock::iterator &BBI,
1027
                               AliasAnalysis *AA, MemoryDependenceResults *MD,
1028
                               const DataLayout &DL,
1029
                               const TargetLibraryInfo *TLI,
1030
                               InstOverlapIntervalsTy &IOL,
1031
1.39M
                               OrderedBasicBlock &OBB) {
1032
1.39M
  // Must be a store instruction.
1033
1.39M
  StoreInst *SI = dyn_cast<StoreInst>(Inst);
1034
1.39M
  if (!SI)
1035
157k
    return false;
1036
1.24M
1037
1.24M
  // If we're storing the same value back to a pointer that we just loaded from,
1038
1.24M
  // then the store can be removed.
1039
1.24M
  if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
1040
200k
    if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
1041
200k
        
isRemovable(SI)858
&&
memoryIsNotModifiedBetween(DepLoad, SI, AA)840
) {
1042
72
1043
72
      LLVM_DEBUG(
1044
72
          dbgs() << "DSE: Remove Store Of Load from same pointer:\n  LOAD: "
1045
72
                 << *DepLoad << "\n  STORE: " << *SI << '\n');
1046
72
1047
72
      deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, OBB);
1048
72
      ++NumRedundantStores;
1049
72
      return true;
1050
72
    }
1051
1.24M
  }
1052
1.24M
1053
1.24M
  // Remove null stores into the calloc'ed objects
1054
1.24M
  Constant *StoredConstant = dyn_cast<Constant>(SI->getValueOperand());
1055
1.24M
  if (StoredConstant && 
StoredConstant->isNullValue()550k
&&
isRemovable(SI)310k
) {
1056
299k
    Instruction *UnderlyingPointer =
1057
299k
        dyn_cast<Instruction>(GetUnderlyingObject(SI->getPointerOperand(), DL));
1058
299k
1059
299k
    if (UnderlyingPointer && 
isCallocLikeFn(UnderlyingPointer, TLI)159k
&&
1060
299k
        
memoryIsNotModifiedBetween(UnderlyingPointer, SI, AA)101
) {
1061
35
      LLVM_DEBUG(
1062
35
          dbgs() << "DSE: Remove null store to the calloc'ed object:\n  DEAD: "
1063
35
                 << *Inst << "\n  OBJECT: " << *UnderlyingPointer << '\n');
1064
35
1065
35
      deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, OBB);
1066
35
      ++NumRedundantStores;
1067
35
      return true;
1068
35
    }
1069
1.24M
  }
1070
1.24M
  return false;
1071
1.24M
}
1072
1073
static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
1074
                                MemoryDependenceResults *MD, DominatorTree *DT,
1075
2.75M
                                const TargetLibraryInfo *TLI) {
1076
2.75M
  const DataLayout &DL = BB.getModule()->getDataLayout();
1077
2.75M
  bool MadeChange = false;
1078
2.75M
1079
2.75M
  OrderedBasicBlock OBB(&BB);
1080
2.75M
  Instruction *LastThrowing = nullptr;
1081
2.75M
1082
2.75M
  // A map of interval maps representing partially-overwritten value parts.
1083
2.75M
  InstOverlapIntervalsTy IOL;
1084
2.75M
1085
2.75M
  // Do a top-down walk on the BB.
1086
17.5M
  for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
1087
14.7M
    // Handle 'free' calls specially.
1088
14.7M
    if (CallInst *F = isFreeCall(&*BBI, TLI)) {
1089
40.0k
      MadeChange |= handleFree(F, AA, MD, DT, TLI, IOL, OBB);
1090
40.0k
      // Increment BBI after handleFree has potentially deleted instructions.
1091
40.0k
      // This ensures we maintain a valid iterator.
1092
40.0k
      ++BBI;
1093
40.0k
      continue;
1094
40.0k
    }
1095
14.7M
1096
14.7M
    Instruction *Inst = &*BBI++;
1097
14.7M
1098
14.7M
    if (Inst->mayThrow()) {
1099
62.9k
      LastThrowing = Inst;
1100
62.9k
      continue;
1101
62.9k
    }
1102
14.6M
1103
14.6M
    // Check to see if Inst writes to memory.  If not, continue.
1104
14.6M
    if (!hasAnalyzableMemoryWrite(Inst, *TLI))
1105
13.2M
      continue;
1106
1.39M
1107
1.39M
    // eliminateNoopStore will update in iterator, if necessary.
1108
1.39M
    if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL, OBB)) {
1109
107
      MadeChange = true;
1110
107
      continue;
1111
107
    }
1112
1.39M
1113
1.39M
    // If we find something that writes memory, get its memory dependence.
1114
1.39M
    MemDepResult InstDep = MD->getDependency(Inst, &OBB);
1115
1.39M
1116
1.39M
    // Ignore any store where we can't find a local dependence.
1117
1.39M
    // FIXME: cross-block DSE would be fun. :)
1118
1.39M
    if (!InstDep.isDef() && 
!InstDep.isClobber()1.07M
)
1119
782k
      continue;
1120
616k
1121
616k
    // Figure out what location is being stored to.
1122
616k
    MemoryLocation Loc = getLocForWrite(Inst);
1123
616k
1124
616k
    // If we didn't get a useful location, fail.
1125
616k
    if (!Loc.Ptr)
1126
0
      continue;
1127
616k
1128
616k
    // Loop until we find a store we can eliminate or a load that
1129
616k
    // invalidates the analysis. Without an upper bound on the number of
1130
616k
    // instructions examined, this analysis can become very time-consuming.
1131
616k
    // However, the potential gain diminishes as we process more instructions
1132
616k
    // without eliminating any of them. Therefore, we limit the number of
1133
616k
    // instructions we look at.
1134
616k
    auto Limit = MD->getDefaultBlockScanLimit();
1135
701k
    while (InstDep.isDef() || 
InstDep.isClobber()351k
) {
1136
680k
      // Get the memory clobbered by the instruction we depend on.  MemDep will
1137
680k
      // skip any instructions that 'Loc' clearly doesn't interact with.  If we
1138
680k
      // end up depending on a may- or must-aliased load, then we can't optimize
1139
680k
      // away the store and we bail out.  However, if we depend on something
1140
680k
      // that overwrites the memory location we *can* potentially optimize it.
1141
680k
      //
1142
680k
      // Find out what memory location the dependent instruction stores.
1143
680k
      Instruction *DepWrite = InstDep.getInst();
1144
680k
      if (!hasAnalyzableMemoryWrite(DepWrite, *TLI))
1145
576k
        break;
1146
104k
      MemoryLocation DepLoc = getLocForWrite(DepWrite);
1147
104k
      // If we didn't get a useful location, or if it isn't a size, bail out.
1148
104k
      if (!DepLoc.Ptr)
1149
0
        break;
1150
104k
1151
104k
      // Make sure we don't look past a call which might throw. This is an
1152
104k
      // issue because MemoryDependenceAnalysis works in the wrong direction:
1153
104k
      // it finds instructions which dominate the current instruction, rather than
1154
104k
      // instructions which are post-dominated by the current instruction.
1155
104k
      //
1156
104k
      // If the underlying object is a non-escaping memory allocation, any store
1157
104k
      // to it is dead along the unwind edge. Otherwise, we need to preserve
1158
104k
      // the store.
1159
104k
      if (LastThrowing && 
OBB.dominates(DepWrite, LastThrowing)5.08k
) {
1160
1.02k
        const Value* Underlying = GetUnderlyingObject(DepLoc.Ptr, DL);
1161
1.02k
        bool IsStoreDeadOnUnwind = isa<AllocaInst>(Underlying);
1162
1.02k
        if (!IsStoreDeadOnUnwind) {
1163
814
            // We're looking for a call to an allocation function
1164
814
            // where the allocation doesn't escape before the last
1165
814
            // throwing instruction; PointerMayBeCaptured
1166
814
            // reasonably fast approximation.
1167
814
            IsStoreDeadOnUnwind = isAllocLikeFn(Underlying, TLI) &&
1168
814
                
!PointerMayBeCaptured(Underlying, false, true)10
;
1169
814
        }
1170
1.02k
        if (!IsStoreDeadOnUnwind)
1171
805
          break;
1172
103k
      }
1173
103k
1174
103k
      // If we find a write that is a) removable (i.e., non-volatile), b) is
1175
103k
      // completely obliterated by the store to 'Loc', and c) which we know that
1176
103k
      // 'Inst' doesn't load from, then we can remove it.
1177
103k
      // Also try to merge two stores if a later one only touches memory written
1178
103k
      // to by the earlier one.
1179
103k
      if (isRemovable(DepWrite) &&
1180
103k
          
!isPossibleSelfRead(Inst, Loc, DepWrite, *TLI, *AA)101k
) {
1181
96.6k
        int64_t InstWriteOffset, DepWriteOffset;
1182
96.6k
        OverwriteResult OR = isOverwrite(Loc, DepLoc, DL, *TLI, DepWriteOffset,
1183
96.6k
                                         InstWriteOffset, DepWrite, IOL, *AA,
1184
96.6k
                                         BB.getParent());
1185
96.6k
        if (OR == OW_Complete) {
1186
7.43k
          LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *DepWrite
1187
7.43k
                            << "\n  KILLER: " << *Inst << '\n');
1188
7.43k
1189
7.43k
          // Delete the store and now-dead instructions that feed it.
1190
7.43k
          deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, OBB);
1191
7.43k
          ++NumFastStores;
1192
7.43k
          MadeChange = true;
1193
7.43k
1194
7.43k
          // We erased DepWrite; start over.
1195
7.43k
          InstDep = MD->getDependency(Inst, &OBB);
1196
7.43k
          continue;
1197
89.2k
        } else if ((OR == OW_End && 
isShortenableAtTheEnd(DepWrite)0
) ||
1198
89.2k
                   ((OR == OW_Begin &&
1199
89.2k
                     
isShortenableAtTheBeginning(DepWrite)0
))) {
1200
0
          assert(!EnablePartialOverwriteTracking && "Do not expect to perform "
1201
0
                                                    "when partial-overwrite "
1202
0
                                                    "tracking is enabled");
1203
0
          // The overwrite result is known, so these must be known, too.
1204
0
          int64_t EarlierSize = DepLoc.Size.getValue();
1205
0
          int64_t LaterSize = Loc.Size.getValue();
1206
0
          bool IsOverwriteEnd = (OR == OW_End);
1207
0
          MadeChange |= tryToShorten(DepWrite, DepWriteOffset, EarlierSize,
1208
0
                                    InstWriteOffset, LaterSize, IsOverwriteEnd);
1209
89.2k
        } else if (EnablePartialStoreMerging &&
1210
89.2k
                   
OR == OW_PartialEarlierWithFullLater89.1k
) {
1211
7.28k
          auto *Earlier = dyn_cast<StoreInst>(DepWrite);
1212
7.28k
          auto *Later = dyn_cast<StoreInst>(Inst);
1213
7.28k
          if (Earlier && 
isa<ConstantInt>(Earlier->getValueOperand())228
&&
1214
7.28k
              DL.typeSizeEqualsStoreSize(
1215
207
                  Earlier->getValueOperand()->getType()) &&
1216
7.28k
              
Later205
&&
isa<ConstantInt>(Later->getValueOperand())205
&&
1217
7.28k
              DL.typeSizeEqualsStoreSize(
1218
190
                  Later->getValueOperand()->getType()) &&
1219
7.28k
              
memoryIsNotModifiedBetween(Earlier, Later, AA)188
) {
1220
187
            // If the store we find is:
1221
187
            //   a) partially overwritten by the store to 'Loc'
1222
187
            //   b) the later store is fully contained in the earlier one and
1223
187
            //   c) they both have a constant value
1224
187
            //   d) none of the two stores need padding
1225
187
            // Merge the two stores, replacing the earlier store's value with a
1226
187
            // merge of both values.
1227
187
            // TODO: Deal with other constant types (vectors, etc), and probably
1228
187
            // some mem intrinsics (if needed)
1229
187
1230
187
            APInt EarlierValue =
1231
187
                cast<ConstantInt>(Earlier->getValueOperand())->getValue();
1232
187
            APInt LaterValue =
1233
187
                cast<ConstantInt>(Later->getValueOperand())->getValue();
1234
187
            unsigned LaterBits = LaterValue.getBitWidth();
1235
187
            assert(EarlierValue.getBitWidth() > LaterValue.getBitWidth());
1236
187
            LaterValue = LaterValue.zext(EarlierValue.getBitWidth());
1237
187
1238
187
            // Offset of the smaller store inside the larger store
1239
187
            unsigned BitOffsetDiff = (InstWriteOffset - DepWriteOffset) * 8;
1240
187
            unsigned LShiftAmount =
1241
187
                DL.isBigEndian()
1242
187
                    ? 
EarlierValue.getBitWidth() - BitOffsetDiff - LaterBits18
1243
187
                    : 
BitOffsetDiff169
;
1244
187
            APInt Mask =
1245
187
                APInt::getBitsSet(EarlierValue.getBitWidth(), LShiftAmount,
1246
187
                                  LShiftAmount + LaterBits);
1247
187
            // Clear the bits we'll be replacing, then OR with the smaller
1248
187
            // store, shifted appropriately.
1249
187
            APInt Merged =
1250
187
                (EarlierValue & ~Mask) | (LaterValue << LShiftAmount);
1251
187
            LLVM_DEBUG(dbgs() << "DSE: Merge Stores:\n  Earlier: " << *DepWrite
1252
187
                              << "\n  Later: " << *Inst
1253
187
                              << "\n  Merged Value: " << Merged << '\n');
1254
187
1255
187
            auto *SI = new StoreInst(
1256
187
                ConstantInt::get(Earlier->getValueOperand()->getType(), Merged),
1257
187
                Earlier->getPointerOperand(), false, Earlier->getAlignment(),
1258
187
                Earlier->getOrdering(), Earlier->getSyncScopeID(), DepWrite);
1259
187
1260
187
            unsigned MDToKeep[] = {LLVMContext::MD_dbg, LLVMContext::MD_tbaa,
1261
187
                                   LLVMContext::MD_alias_scope,
1262
187
                                   LLVMContext::MD_noalias,
1263
187
                                   LLVMContext::MD_nontemporal};
1264
187
            SI->copyMetadata(*DepWrite, MDToKeep);
1265
187
            ++NumModifiedStores;
1266
187
1267
187
            // Remove earlier, wider, store
1268
187
            OBB.replaceInstruction(DepWrite, SI);
1269
187
1270
187
            // Delete the old stores and now-dead instructions that feed them.
1271
187
            deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL, OBB);
1272
187
            deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, OBB);
1273
187
            MadeChange = true;
1274
187
1275
187
            // We erased DepWrite and Inst (Loc); start over.
1276
187
            break;
1277
187
          }
1278
95.7k
        }
1279
96.6k
      }
1280
95.7k
1281
95.7k
      // If this is a may-aliased store that is clobbering the store value, we
1282
95.7k
      // can keep searching past it for another must-aliased pointer that stores
1283
95.7k
      // to the same location.  For example, in:
1284
95.7k
      //   store -> P
1285
95.7k
      //   store -> Q
1286
95.7k
      //   store -> P
1287
95.7k
      // we can remove the first store to P even though we don't know if P and Q
1288
95.7k
      // alias.
1289
95.7k
      if (DepWrite == &BB.front()) 
break4.26k
;
1290
91.4k
1291
91.4k
      // Can't look past this instruction if it might read 'Loc'.
1292
91.4k
      if (isRefSet(AA->getModRefInfo(DepWrite, Loc)))
1293
13.4k
        break;
1294
78.0k
1295
78.0k
      InstDep = MD->getPointerDependencyFrom(Loc, /*isLoad=*/ false,
1296
78.0k
                                             DepWrite->getIterator(), &BB,
1297
78.0k
                                             /*QueryInst=*/ nullptr, &Limit);
1298
78.0k
    }
1299
616k
  }
1300
2.75M
1301
2.75M
  if (EnablePartialOverwriteTracking)
1302
2.75M
    MadeChange |= removePartiallyOverlappedStores(AA, DL, IOL);
1303
2.75M
1304
2.75M
  // If this block ends in a return, unwind, or unreachable, all allocas are
1305
2.75M
  // dead at its end, which means stores to them are also dead.
1306
2.75M
  if (BB.getTerminator()->getNumSuccessors() == 0)
1307
522k
    MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, OBB);
1308
2.75M
1309
2.75M
  return MadeChange;
1310
2.75M
}
1311
1312
static bool eliminateDeadStores(Function &F, AliasAnalysis *AA,
1313
                                MemoryDependenceResults *MD, DominatorTree *DT,
1314
467k
                                const TargetLibraryInfo *TLI) {
1315
467k
  bool MadeChange = false;
1316
467k
  for (BasicBlock &BB : F)
1317
2.75M
    // Only check non-dead blocks.  Dead blocks may have strange pointer
1318
2.75M
    // cycles that will confuse alias analysis.
1319
2.75M
    if (DT->isReachableFromEntry(&BB))
1320
2.75M
      MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI);
1321
467k
1322
467k
  return MadeChange;
1323
467k
}
1324
1325
//===----------------------------------------------------------------------===//
1326
// DSE Pass
1327
//===----------------------------------------------------------------------===//
1328
1.23k
PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
1329
1.23k
  AliasAnalysis *AA = &AM.getResult<AAManager>(F);
1330
1.23k
  DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F);
1331
1.23k
  MemoryDependenceResults *MD = &AM.getResult<MemoryDependenceAnalysis>(F);
1332
1.23k
  const TargetLibraryInfo *TLI = &AM.getResult<TargetLibraryAnalysis>(F);
1333
1.23k
1334
1.23k
  if (!eliminateDeadStores(F, AA, MD, DT, TLI))
1335
1.16k
    return PreservedAnalyses::all();
1336
76
1337
76
  PreservedAnalyses PA;
1338
76
  PA.preserveSet<CFGAnalyses>();
1339
76
  PA.preserve<GlobalsAA>();
1340
76
  PA.preserve<MemoryDependenceAnalysis>();
1341
76
  return PA;
1342
76
}
1343
1344
namespace {
1345
1346
/// A legacy pass for the legacy pass manager that wraps \c DSEPass.
1347
class DSELegacyPass : public FunctionPass {
1348
public:
1349
  static char ID; // Pass identification, replacement for typeid
1350
1351
13.4k
  DSELegacyPass() : FunctionPass(ID) {
1352
13.4k
    initializeDSELegacyPassPass(*PassRegistry::getPassRegistry());
1353
13.4k
  }
1354
1355
466k
  bool runOnFunction(Function &F) override {
1356
466k
    if (skipFunction(F))
1357
44
      return false;
1358
466k
1359
466k
    DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1360
466k
    AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
1361
466k
    MemoryDependenceResults *MD =
1362
466k
        &getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
1363
466k
    const TargetLibraryInfo *TLI =
1364
466k
        &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1365
466k
1366
466k
    return eliminateDeadStores(F, AA, MD, DT, TLI);
1367
466k
  }
1368
1369
13.4k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
1370
13.4k
    AU.setPreservesCFG();
1371
13.4k
    AU.addRequired<DominatorTreeWrapperPass>();
1372
13.4k
    AU.addRequired<AAResultsWrapperPass>();
1373
13.4k
    AU.addRequired<MemoryDependenceWrapperPass>();
1374
13.4k
    AU.addRequired<TargetLibraryInfoWrapperPass>();
1375
13.4k
    AU.addPreserved<DominatorTreeWrapperPass>();
1376
13.4k
    AU.addPreserved<GlobalsAAWrapperPass>();
1377
13.4k
    AU.addPreserved<MemoryDependenceWrapperPass>();
1378
13.4k
  }
1379
};
1380
1381
} // end anonymous namespace
1382
1383
char DSELegacyPass::ID = 0;
1384
1385
48.9k
INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false,
1386
48.9k
                      false)
1387
48.9k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1388
48.9k
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
1389
48.9k
INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
1390
48.9k
INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
1391
48.9k
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
1392
48.9k
INITIALIZE_PASS_END(DSELegacyPass, "dse", "Dead Store Elimination", false,
1393
                    false)
1394
1395
13.4k
FunctionPass *llvm::createDeadStoreEliminationPass() {
1396
13.4k
  return new DSELegacyPass();
1397
13.4k
}