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