File: | lib/Transforms/Scalar/GuardWidening.cpp |
Warning: | line 480, column 9 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- GuardWidening.cpp - ---- Guard widening ----------------------------===// | |||
2 | // | |||
3 | // The LLVM Compiler Infrastructure | |||
4 | // | |||
5 | // This file is distributed under the University of Illinois Open Source | |||
6 | // License. See LICENSE.TXT for details. | |||
7 | // | |||
8 | //===----------------------------------------------------------------------===// | |||
9 | // | |||
10 | // This file implements the guard widening pass. The semantics of the | |||
11 | // @llvm.experimental.guard intrinsic lets LLVM transform it so that it fails | |||
12 | // more often that it did before the transform. This optimization is called | |||
13 | // "widening" and can be used hoist and common runtime checks in situations like | |||
14 | // these: | |||
15 | // | |||
16 | // %cmp0 = 7 u< Length | |||
17 | // call @llvm.experimental.guard(i1 %cmp0) [ "deopt"(...) ] | |||
18 | // call @unknown_side_effects() | |||
19 | // %cmp1 = 9 u< Length | |||
20 | // call @llvm.experimental.guard(i1 %cmp1) [ "deopt"(...) ] | |||
21 | // ... | |||
22 | // | |||
23 | // => | |||
24 | // | |||
25 | // %cmp0 = 9 u< Length | |||
26 | // call @llvm.experimental.guard(i1 %cmp0) [ "deopt"(...) ] | |||
27 | // call @unknown_side_effects() | |||
28 | // ... | |||
29 | // | |||
30 | // If %cmp0 is false, @llvm.experimental.guard will "deoptimize" back to a | |||
31 | // generic implementation of the same function, which will have the correct | |||
32 | // semantics from that point onward. It is always _legal_ to deoptimize (so | |||
33 | // replacing %cmp0 with false is "correct"), though it may not always be | |||
34 | // profitable to do so. | |||
35 | // | |||
36 | // NB! This pass is a work in progress. It hasn't been tuned to be "production | |||
37 | // ready" yet. It is known to have quadriatic running time and will not scale | |||
38 | // to large numbers of guards | |||
39 | // | |||
40 | //===----------------------------------------------------------------------===// | |||
41 | ||||
42 | #include "llvm/Transforms/Scalar/GuardWidening.h" | |||
43 | #include <functional> | |||
44 | #include "llvm/ADT/DenseMap.h" | |||
45 | #include "llvm/ADT/DepthFirstIterator.h" | |||
46 | #include "llvm/Analysis/LoopInfo.h" | |||
47 | #include "llvm/Analysis/LoopPass.h" | |||
48 | #include "llvm/Analysis/PostDominators.h" | |||
49 | #include "llvm/Analysis/ValueTracking.h" | |||
50 | #include "llvm/IR/ConstantRange.h" | |||
51 | #include "llvm/IR/Dominators.h" | |||
52 | #include "llvm/IR/IntrinsicInst.h" | |||
53 | #include "llvm/IR/PatternMatch.h" | |||
54 | #include "llvm/Pass.h" | |||
55 | #include "llvm/Support/Debug.h" | |||
56 | #include "llvm/Support/KnownBits.h" | |||
57 | #include "llvm/Transforms/Scalar.h" | |||
58 | #include "llvm/Transforms/Utils/LoopUtils.h" | |||
59 | ||||
60 | using namespace llvm; | |||
61 | ||||
62 | #define DEBUG_TYPE"guard-widening" "guard-widening" | |||
63 | ||||
64 | namespace { | |||
65 | ||||
66 | class GuardWideningImpl { | |||
67 | DominatorTree &DT; | |||
68 | PostDominatorTree *PDT; | |||
69 | LoopInfo &LI; | |||
70 | ||||
71 | /// Together, these describe the region of interest. This might be all of | |||
72 | /// the blocks within a function, or only a given loop's blocks and preheader. | |||
73 | DomTreeNode *Root; | |||
74 | std::function<bool(BasicBlock*)> BlockFilter; | |||
75 | ||||
76 | /// The set of guards whose conditions have been widened into dominating | |||
77 | /// guards. | |||
78 | SmallVector<IntrinsicInst *, 16> EliminatedGuards; | |||
79 | ||||
80 | /// The set of guards which have been widened to include conditions to other | |||
81 | /// guards. | |||
82 | DenseSet<IntrinsicInst *> WidenedGuards; | |||
83 | ||||
84 | /// Try to eliminate guard \p Guard by widening it into an earlier dominating | |||
85 | /// guard. \p DFSI is the DFS iterator on the dominator tree that is | |||
86 | /// currently visiting the block containing \p Guard, and \p GuardsPerBlock | |||
87 | /// maps BasicBlocks to the set of guards seen in that block. | |||
88 | bool eliminateGuardViaWidening( | |||
89 | IntrinsicInst *Guard, const df_iterator<DomTreeNode *> &DFSI, | |||
90 | const DenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 8>> & | |||
91 | GuardsPerBlock); | |||
92 | ||||
93 | /// Used to keep track of which widening potential is more effective. | |||
94 | enum WideningScore { | |||
95 | /// Don't widen. | |||
96 | WS_IllegalOrNegative, | |||
97 | ||||
98 | /// Widening is performance neutral as far as the cycles spent in check | |||
99 | /// conditions goes (but can still help, e.g., code layout, having less | |||
100 | /// deopt state). | |||
101 | WS_Neutral, | |||
102 | ||||
103 | /// Widening is profitable. | |||
104 | WS_Positive, | |||
105 | ||||
106 | /// Widening is very profitable. Not significantly different from \c | |||
107 | /// WS_Positive, except by the order. | |||
108 | WS_VeryPositive | |||
109 | }; | |||
110 | ||||
111 | static StringRef scoreTypeToString(WideningScore WS); | |||
112 | ||||
113 | /// Compute the score for widening the condition in \p DominatedGuard | |||
114 | /// (contained in \p DominatedGuardLoop) into \p DominatingGuard (contained in | |||
115 | /// \p DominatingGuardLoop). | |||
116 | WideningScore computeWideningScore(IntrinsicInst *DominatedGuard, | |||
117 | Loop *DominatedGuardLoop, | |||
118 | IntrinsicInst *DominatingGuard, | |||
119 | Loop *DominatingGuardLoop); | |||
120 | ||||
121 | /// Helper to check if \p V can be hoisted to \p InsertPos. | |||
122 | bool isAvailableAt(Value *V, Instruction *InsertPos) { | |||
123 | SmallPtrSet<Instruction *, 8> Visited; | |||
124 | return isAvailableAt(V, InsertPos, Visited); | |||
125 | } | |||
126 | ||||
127 | bool isAvailableAt(Value *V, Instruction *InsertPos, | |||
128 | SmallPtrSetImpl<Instruction *> &Visited); | |||
129 | ||||
130 | /// Helper to hoist \p V to \p InsertPos. Guaranteed to succeed if \c | |||
131 | /// isAvailableAt returned true. | |||
132 | void makeAvailableAt(Value *V, Instruction *InsertPos); | |||
133 | ||||
134 | /// Common helper used by \c widenGuard and \c isWideningCondProfitable. Try | |||
135 | /// to generate an expression computing the logical AND of \p Cond0 and \p | |||
136 | /// Cond1. Return true if the expression computing the AND is only as | |||
137 | /// expensive as computing one of the two. If \p InsertPt is true then | |||
138 | /// actually generate the resulting expression, make it available at \p | |||
139 | /// InsertPt and return it in \p Result (else no change to the IR is made). | |||
140 | bool widenCondCommon(Value *Cond0, Value *Cond1, Instruction *InsertPt, | |||
141 | Value *&Result); | |||
142 | ||||
143 | /// Represents a range check of the form \c Base + \c Offset u< \c Length, | |||
144 | /// with the constraint that \c Length is not negative. \c CheckInst is the | |||
145 | /// pre-existing instruction in the IR that computes the result of this range | |||
146 | /// check. | |||
147 | class RangeCheck { | |||
148 | Value *Base; | |||
149 | ConstantInt *Offset; | |||
150 | Value *Length; | |||
151 | ICmpInst *CheckInst; | |||
152 | ||||
153 | public: | |||
154 | explicit RangeCheck(Value *Base, ConstantInt *Offset, Value *Length, | |||
155 | ICmpInst *CheckInst) | |||
156 | : Base(Base), Offset(Offset), Length(Length), CheckInst(CheckInst) {} | |||
157 | ||||
158 | void setBase(Value *NewBase) { Base = NewBase; } | |||
159 | void setOffset(ConstantInt *NewOffset) { Offset = NewOffset; } | |||
160 | ||||
161 | Value *getBase() const { return Base; } | |||
162 | ConstantInt *getOffset() const { return Offset; } | |||
163 | const APInt &getOffsetValue() const { return getOffset()->getValue(); } | |||
164 | Value *getLength() const { return Length; }; | |||
165 | ICmpInst *getCheckInst() const { return CheckInst; } | |||
166 | ||||
167 | void print(raw_ostream &OS, bool PrintTypes = false) { | |||
168 | OS << "Base: "; | |||
169 | Base->printAsOperand(OS, PrintTypes); | |||
170 | OS << " Offset: "; | |||
171 | Offset->printAsOperand(OS, PrintTypes); | |||
172 | OS << " Length: "; | |||
173 | Length->printAsOperand(OS, PrintTypes); | |||
174 | } | |||
175 | ||||
176 | LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void dump() { | |||
177 | print(dbgs()); | |||
178 | dbgs() << "\n"; | |||
179 | } | |||
180 | }; | |||
181 | ||||
182 | /// Parse \p CheckCond into a conjunction (logical-and) of range checks; and | |||
183 | /// append them to \p Checks. Returns true on success, may clobber \c Checks | |||
184 | /// on failure. | |||
185 | bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks) { | |||
186 | SmallPtrSet<Value *, 8> Visited; | |||
187 | return parseRangeChecks(CheckCond, Checks, Visited); | |||
188 | } | |||
189 | ||||
190 | bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks, | |||
191 | SmallPtrSetImpl<Value *> &Visited); | |||
192 | ||||
193 | /// Combine the checks in \p Checks into a smaller set of checks and append | |||
194 | /// them into \p CombinedChecks. Return true on success (i.e. all of checks | |||
195 | /// in \p Checks were combined into \p CombinedChecks). Clobbers \p Checks | |||
196 | /// and \p CombinedChecks on success and on failure. | |||
197 | bool combineRangeChecks(SmallVectorImpl<RangeCheck> &Checks, | |||
198 | SmallVectorImpl<RangeCheck> &CombinedChecks); | |||
199 | ||||
200 | /// Can we compute the logical AND of \p Cond0 and \p Cond1 for the price of | |||
201 | /// computing only one of the two expressions? | |||
202 | bool isWideningCondProfitable(Value *Cond0, Value *Cond1) { | |||
203 | Value *ResultUnused; | |||
204 | return widenCondCommon(Cond0, Cond1, /*InsertPt=*/nullptr, ResultUnused); | |||
205 | } | |||
206 | ||||
207 | /// Widen \p ToWiden to fail if \p NewCondition is false (in addition to | |||
208 | /// whatever it is already checking). | |||
209 | void widenGuard(IntrinsicInst *ToWiden, Value *NewCondition) { | |||
210 | Value *Result; | |||
211 | widenCondCommon(ToWiden->getArgOperand(0), NewCondition, ToWiden, Result); | |||
212 | ToWiden->setArgOperand(0, Result); | |||
213 | } | |||
214 | ||||
215 | public: | |||
216 | ||||
217 | explicit GuardWideningImpl(DominatorTree &DT, PostDominatorTree *PDT, | |||
218 | LoopInfo &LI, DomTreeNode *Root, | |||
219 | std::function<bool(BasicBlock*)> BlockFilter) | |||
220 | : DT(DT), PDT(PDT), LI(LI), Root(Root), BlockFilter(BlockFilter) {} | |||
221 | ||||
222 | /// The entry point for this pass. | |||
223 | bool run(); | |||
224 | }; | |||
225 | } | |||
226 | ||||
227 | bool GuardWideningImpl::run() { | |||
228 | using namespace llvm::PatternMatch; | |||
229 | ||||
230 | DenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 8>> GuardsInBlock; | |||
231 | bool Changed = false; | |||
232 | ||||
233 | for (auto DFI = df_begin(Root), DFE = df_end(Root); | |||
234 | DFI != DFE; ++DFI) { | |||
235 | auto *BB = (*DFI)->getBlock(); | |||
236 | if (!BlockFilter(BB)) | |||
237 | continue; | |||
238 | ||||
239 | auto &CurrentList = GuardsInBlock[BB]; | |||
240 | ||||
241 | for (auto &I : *BB) | |||
242 | if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>())) | |||
243 | CurrentList.push_back(cast<IntrinsicInst>(&I)); | |||
244 | ||||
245 | for (auto *II : CurrentList) | |||
246 | Changed |= eliminateGuardViaWidening(II, DFI, GuardsInBlock); | |||
247 | } | |||
248 | ||||
249 | assert(EliminatedGuards.empty() || Changed)(static_cast <bool> (EliminatedGuards.empty() || Changed ) ? void (0) : __assert_fail ("EliminatedGuards.empty() || Changed" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 249, __extension__ __PRETTY_FUNCTION__)); | |||
250 | for (auto *II : EliminatedGuards) | |||
251 | if (!WidenedGuards.count(II)) | |||
252 | II->eraseFromParent(); | |||
253 | ||||
254 | return Changed; | |||
255 | } | |||
256 | ||||
257 | bool GuardWideningImpl::eliminateGuardViaWidening( | |||
258 | IntrinsicInst *GuardInst, const df_iterator<DomTreeNode *> &DFSI, | |||
259 | const DenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 8>> & | |||
260 | GuardsInBlock) { | |||
261 | IntrinsicInst *BestSoFar = nullptr; | |||
262 | auto BestScoreSoFar = WS_IllegalOrNegative; | |||
263 | auto *GuardInstLoop = LI.getLoopFor(GuardInst->getParent()); | |||
264 | ||||
265 | // In the set of dominating guards, find the one we can merge GuardInst with | |||
266 | // for the most profit. | |||
267 | for (unsigned i = 0, e = DFSI.getPathLength(); i != e; ++i) { | |||
268 | auto *CurBB = DFSI.getPath(i)->getBlock(); | |||
269 | if (!BlockFilter(CurBB)) | |||
270 | break; | |||
271 | auto *CurLoop = LI.getLoopFor(CurBB); | |||
272 | assert(GuardsInBlock.count(CurBB) && "Must have been populated by now!")(static_cast <bool> (GuardsInBlock.count(CurBB) && "Must have been populated by now!") ? void (0) : __assert_fail ("GuardsInBlock.count(CurBB) && \"Must have been populated by now!\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 272, __extension__ __PRETTY_FUNCTION__)); | |||
273 | const auto &GuardsInCurBB = GuardsInBlock.find(CurBB)->second; | |||
274 | ||||
275 | auto I = GuardsInCurBB.begin(); | |||
276 | auto E = GuardsInCurBB.end(); | |||
277 | ||||
278 | #ifndef NDEBUG | |||
279 | { | |||
280 | unsigned Index = 0; | |||
281 | for (auto &I : *CurBB) { | |||
282 | if (Index == GuardsInCurBB.size()) | |||
283 | break; | |||
284 | if (GuardsInCurBB[Index] == &I) | |||
285 | Index++; | |||
286 | } | |||
287 | assert(Index == GuardsInCurBB.size() &&(static_cast <bool> (Index == GuardsInCurBB.size() && "Guards expected to be in order!") ? void (0) : __assert_fail ("Index == GuardsInCurBB.size() && \"Guards expected to be in order!\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 288, __extension__ __PRETTY_FUNCTION__)) | |||
288 | "Guards expected to be in order!")(static_cast <bool> (Index == GuardsInCurBB.size() && "Guards expected to be in order!") ? void (0) : __assert_fail ("Index == GuardsInCurBB.size() && \"Guards expected to be in order!\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 288, __extension__ __PRETTY_FUNCTION__)); | |||
289 | } | |||
290 | #endif | |||
291 | ||||
292 | assert((i == (e - 1)) == (GuardInst->getParent() == CurBB) && "Bad DFS?")(static_cast <bool> ((i == (e - 1)) == (GuardInst->getParent () == CurBB) && "Bad DFS?") ? void (0) : __assert_fail ("(i == (e - 1)) == (GuardInst->getParent() == CurBB) && \"Bad DFS?\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 292, __extension__ __PRETTY_FUNCTION__)); | |||
293 | ||||
294 | if (i == (e - 1)) { | |||
295 | // Corner case: make sure we're only looking at guards strictly dominating | |||
296 | // GuardInst when visiting GuardInst->getParent(). | |||
297 | auto NewEnd = std::find(I, E, GuardInst); | |||
298 | assert(NewEnd != E && "GuardInst not in its own block?")(static_cast <bool> (NewEnd != E && "GuardInst not in its own block?" ) ? void (0) : __assert_fail ("NewEnd != E && \"GuardInst not in its own block?\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 298, __extension__ __PRETTY_FUNCTION__)); | |||
299 | E = NewEnd; | |||
300 | } | |||
301 | ||||
302 | for (auto *Candidate : make_range(I, E)) { | |||
303 | auto Score = | |||
304 | computeWideningScore(GuardInst, GuardInstLoop, Candidate, CurLoop); | |||
305 | LLVM_DEBUG(dbgs() << "Score between " << *GuardInst->getArgOperand(0)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("guard-widening")) { dbgs() << "Score between " << *GuardInst->getArgOperand(0) << " and " << *Candidate ->getArgOperand(0) << " is " << scoreTypeToString (Score) << "\n"; } } while (false) | |||
306 | << " and " << *Candidate->getArgOperand(0) << " is "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("guard-widening")) { dbgs() << "Score between " << *GuardInst->getArgOperand(0) << " and " << *Candidate ->getArgOperand(0) << " is " << scoreTypeToString (Score) << "\n"; } } while (false) | |||
307 | << scoreTypeToString(Score) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("guard-widening")) { dbgs() << "Score between " << *GuardInst->getArgOperand(0) << " and " << *Candidate ->getArgOperand(0) << " is " << scoreTypeToString (Score) << "\n"; } } while (false); | |||
308 | if (Score > BestScoreSoFar) { | |||
309 | BestScoreSoFar = Score; | |||
310 | BestSoFar = Candidate; | |||
311 | } | |||
312 | } | |||
313 | } | |||
314 | ||||
315 | if (BestScoreSoFar == WS_IllegalOrNegative) { | |||
316 | LLVM_DEBUG(dbgs() << "Did not eliminate guard " << *GuardInst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("guard-widening")) { dbgs() << "Did not eliminate guard " << *GuardInst << "\n"; } } while (false); | |||
317 | return false; | |||
318 | } | |||
319 | ||||
320 | assert(BestSoFar != GuardInst && "Should have never visited same guard!")(static_cast <bool> (BestSoFar != GuardInst && "Should have never visited same guard!" ) ? void (0) : __assert_fail ("BestSoFar != GuardInst && \"Should have never visited same guard!\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 320, __extension__ __PRETTY_FUNCTION__)); | |||
321 | assert(DT.dominates(BestSoFar, GuardInst) && "Should be!")(static_cast <bool> (DT.dominates(BestSoFar, GuardInst) && "Should be!") ? void (0) : __assert_fail ("DT.dominates(BestSoFar, GuardInst) && \"Should be!\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 321, __extension__ __PRETTY_FUNCTION__)); | |||
322 | ||||
323 | LLVM_DEBUG(dbgs() << "Widening " << *GuardInst << " into " << *BestSoFardo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("guard-widening")) { dbgs() << "Widening " << *GuardInst << " into " << *BestSoFar << " with score " << scoreTypeToString(BestScoreSoFar) << "\n"; } } while (false) | |||
324 | << " with score " << scoreTypeToString(BestScoreSoFar)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("guard-widening")) { dbgs() << "Widening " << *GuardInst << " into " << *BestSoFar << " with score " << scoreTypeToString(BestScoreSoFar) << "\n"; } } while (false) | |||
325 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("guard-widening")) { dbgs() << "Widening " << *GuardInst << " into " << *BestSoFar << " with score " << scoreTypeToString(BestScoreSoFar) << "\n"; } } while (false); | |||
326 | widenGuard(BestSoFar, GuardInst->getArgOperand(0)); | |||
327 | GuardInst->setArgOperand(0, ConstantInt::getTrue(GuardInst->getContext())); | |||
328 | EliminatedGuards.push_back(GuardInst); | |||
329 | WidenedGuards.insert(BestSoFar); | |||
330 | return true; | |||
331 | } | |||
332 | ||||
333 | GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore( | |||
334 | IntrinsicInst *DominatedGuard, Loop *DominatedGuardLoop, | |||
335 | IntrinsicInst *DominatingGuard, Loop *DominatingGuardLoop) { | |||
336 | bool HoistingOutOfLoop = false; | |||
337 | ||||
338 | if (DominatingGuardLoop != DominatedGuardLoop) { | |||
339 | // Be conservative and don't widen into a sibling loop. TODO: If the | |||
340 | // sibling is colder, we should consider allowing this. | |||
341 | if (DominatingGuardLoop && | |||
342 | !DominatingGuardLoop->contains(DominatedGuardLoop)) | |||
343 | return WS_IllegalOrNegative; | |||
344 | ||||
345 | HoistingOutOfLoop = true; | |||
346 | } | |||
347 | ||||
348 | if (!isAvailableAt(DominatedGuard->getArgOperand(0), DominatingGuard)) | |||
349 | return WS_IllegalOrNegative; | |||
350 | ||||
351 | // If the guard was conditional executed, it may never be reached | |||
352 | // dynamically. There are two potential downsides to hoisting it out of the | |||
353 | // conditionally executed region: 1) we may spuriously deopt without need and | |||
354 | // 2) we have the extra cost of computing the guard condition in the common | |||
355 | // case. At the moment, we really only consider the second in our heuristic | |||
356 | // here. TODO: evaluate cost model for spurious deopt | |||
357 | // NOTE: As written, this also lets us hoist right over another guard which | |||
358 | // is essentially just another spelling for control flow. | |||
359 | if (isWideningCondProfitable(DominatedGuard->getArgOperand(0), | |||
360 | DominatingGuard->getArgOperand(0))) | |||
361 | return HoistingOutOfLoop ? WS_VeryPositive : WS_Positive; | |||
362 | ||||
363 | if (HoistingOutOfLoop) | |||
364 | return WS_Positive; | |||
365 | ||||
366 | // Returns true if we might be hoisting above explicit control flow. Note | |||
367 | // that this completely ignores implicit control flow (guards, calls which | |||
368 | // throw, etc...). That choice appears arbitrary. | |||
369 | auto MaybeHoistingOutOfIf = [&]() { | |||
370 | auto *DominatingBlock = DominatingGuard->getParent(); | |||
371 | auto *DominatedBlock = DominatedGuard->getParent(); | |||
372 | ||||
373 | // Same Block? | |||
374 | if (DominatedBlock == DominatingBlock) | |||
375 | return false; | |||
376 | // Obvious successor (common loop header/preheader case) | |||
377 | if (DominatedBlock == DominatingBlock->getUniqueSuccessor()) | |||
378 | return false; | |||
379 | // TODO: diamond, triangle cases | |||
380 | if (!PDT) return true; | |||
381 | return !PDT->dominates(DominatedGuard->getParent(), | |||
382 | DominatingGuard->getParent()); | |||
383 | }; | |||
384 | ||||
385 | return MaybeHoistingOutOfIf() ? WS_IllegalOrNegative : WS_Neutral; | |||
386 | } | |||
387 | ||||
388 | bool GuardWideningImpl::isAvailableAt(Value *V, Instruction *Loc, | |||
389 | SmallPtrSetImpl<Instruction *> &Visited) { | |||
390 | auto *Inst = dyn_cast<Instruction>(V); | |||
391 | if (!Inst || DT.dominates(Inst, Loc) || Visited.count(Inst)) | |||
392 | return true; | |||
393 | ||||
394 | if (!isSafeToSpeculativelyExecute(Inst, Loc, &DT) || | |||
395 | Inst->mayReadFromMemory()) | |||
396 | return false; | |||
397 | ||||
398 | Visited.insert(Inst); | |||
399 | ||||
400 | // We only want to go _up_ the dominance chain when recursing. | |||
401 | assert(!isa<PHINode>(Loc) &&(static_cast <bool> (!isa<PHINode>(Loc) && "PHIs should return false for isSafeToSpeculativelyExecute") ? void (0) : __assert_fail ("!isa<PHINode>(Loc) && \"PHIs should return false for isSafeToSpeculativelyExecute\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 402, __extension__ __PRETTY_FUNCTION__)) | |||
402 | "PHIs should return false for isSafeToSpeculativelyExecute")(static_cast <bool> (!isa<PHINode>(Loc) && "PHIs should return false for isSafeToSpeculativelyExecute") ? void (0) : __assert_fail ("!isa<PHINode>(Loc) && \"PHIs should return false for isSafeToSpeculativelyExecute\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 402, __extension__ __PRETTY_FUNCTION__)); | |||
403 | assert(DT.isReachableFromEntry(Inst->getParent()) &&(static_cast <bool> (DT.isReachableFromEntry(Inst->getParent ()) && "We did a DFS from the block entry!") ? void ( 0) : __assert_fail ("DT.isReachableFromEntry(Inst->getParent()) && \"We did a DFS from the block entry!\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 404, __extension__ __PRETTY_FUNCTION__)) | |||
404 | "We did a DFS from the block entry!")(static_cast <bool> (DT.isReachableFromEntry(Inst->getParent ()) && "We did a DFS from the block entry!") ? void ( 0) : __assert_fail ("DT.isReachableFromEntry(Inst->getParent()) && \"We did a DFS from the block entry!\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 404, __extension__ __PRETTY_FUNCTION__)); | |||
405 | return all_of(Inst->operands(), | |||
406 | [&](Value *Op) { return isAvailableAt(Op, Loc, Visited); }); | |||
407 | } | |||
408 | ||||
409 | void GuardWideningImpl::makeAvailableAt(Value *V, Instruction *Loc) { | |||
410 | auto *Inst = dyn_cast<Instruction>(V); | |||
411 | if (!Inst || DT.dominates(Inst, Loc)) | |||
412 | return; | |||
413 | ||||
414 | assert(isSafeToSpeculativelyExecute(Inst, Loc, &DT) &&(static_cast <bool> (isSafeToSpeculativelyExecute(Inst, Loc, &DT) && !Inst->mayReadFromMemory() && "Should've checked with isAvailableAt!") ? void (0) : __assert_fail ("isSafeToSpeculativelyExecute(Inst, Loc, &DT) && !Inst->mayReadFromMemory() && \"Should've checked with isAvailableAt!\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 415, __extension__ __PRETTY_FUNCTION__)) | |||
415 | !Inst->mayReadFromMemory() && "Should've checked with isAvailableAt!")(static_cast <bool> (isSafeToSpeculativelyExecute(Inst, Loc, &DT) && !Inst->mayReadFromMemory() && "Should've checked with isAvailableAt!") ? void (0) : __assert_fail ("isSafeToSpeculativelyExecute(Inst, Loc, &DT) && !Inst->mayReadFromMemory() && \"Should've checked with isAvailableAt!\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 415, __extension__ __PRETTY_FUNCTION__)); | |||
416 | ||||
417 | for (Value *Op : Inst->operands()) | |||
418 | makeAvailableAt(Op, Loc); | |||
419 | ||||
420 | Inst->moveBefore(Loc); | |||
421 | } | |||
422 | ||||
423 | bool GuardWideningImpl::widenCondCommon(Value *Cond0, Value *Cond1, | |||
424 | Instruction *InsertPt, Value *&Result) { | |||
425 | using namespace llvm::PatternMatch; | |||
426 | ||||
427 | { | |||
428 | // L >u C0 && L >u C1 -> L >u max(C0, C1) | |||
429 | ConstantInt *RHS0, *RHS1; | |||
430 | Value *LHS; | |||
431 | ICmpInst::Predicate Pred0, Pred1; | |||
432 | if (match(Cond0, m_ICmp(Pred0, m_Value(LHS), m_ConstantInt(RHS0))) && | |||
433 | match(Cond1, m_ICmp(Pred1, m_Specific(LHS), m_ConstantInt(RHS1)))) { | |||
434 | ||||
435 | ConstantRange CR0 = | |||
436 | ConstantRange::makeExactICmpRegion(Pred0, RHS0->getValue()); | |||
437 | ConstantRange CR1 = | |||
438 | ConstantRange::makeExactICmpRegion(Pred1, RHS1->getValue()); | |||
439 | ||||
440 | // SubsetIntersect is a subset of the actual mathematical intersection of | |||
441 | // CR0 and CR1, while SupersetIntersect is a superset of the actual | |||
442 | // mathematical intersection. If these two ConstantRanges are equal, then | |||
443 | // we know we were able to represent the actual mathematical intersection | |||
444 | // of CR0 and CR1, and can use the same to generate an icmp instruction. | |||
445 | // | |||
446 | // Given what we're doing here and the semantics of guards, it would | |||
447 | // actually be correct to just use SubsetIntersect, but that may be too | |||
448 | // aggressive in cases we care about. | |||
449 | auto SubsetIntersect = CR0.inverse().unionWith(CR1.inverse()).inverse(); | |||
450 | auto SupersetIntersect = CR0.intersectWith(CR1); | |||
451 | ||||
452 | APInt NewRHSAP; | |||
453 | CmpInst::Predicate Pred; | |||
454 | if (SubsetIntersect == SupersetIntersect && | |||
455 | SubsetIntersect.getEquivalentICmp(Pred, NewRHSAP)) { | |||
456 | if (InsertPt) { | |||
457 | ConstantInt *NewRHS = ConstantInt::get(Cond0->getContext(), NewRHSAP); | |||
458 | Result = new ICmpInst(InsertPt, Pred, LHS, NewRHS, "wide.chk"); | |||
459 | } | |||
460 | return true; | |||
461 | } | |||
462 | } | |||
463 | } | |||
464 | ||||
465 | { | |||
466 | SmallVector<GuardWideningImpl::RangeCheck, 4> Checks, CombinedChecks; | |||
467 | if (parseRangeChecks(Cond0, Checks) && parseRangeChecks(Cond1, Checks) && | |||
468 | combineRangeChecks(Checks, CombinedChecks)) { | |||
469 | if (InsertPt) { | |||
470 | Result = nullptr; | |||
471 | for (auto &RC : CombinedChecks) { | |||
472 | makeAvailableAt(RC.getCheckInst(), InsertPt); | |||
473 | if (Result) | |||
474 | Result = BinaryOperator::CreateAnd(RC.getCheckInst(), Result, "", | |||
475 | InsertPt); | |||
476 | else | |||
477 | Result = RC.getCheckInst(); | |||
478 | } | |||
479 | ||||
480 | Result->setName("wide.chk"); | |||
| ||||
481 | } | |||
482 | return true; | |||
483 | } | |||
484 | } | |||
485 | ||||
486 | // Base case -- just logical-and the two conditions together. | |||
487 | ||||
488 | if (InsertPt) { | |||
489 | makeAvailableAt(Cond0, InsertPt); | |||
490 | makeAvailableAt(Cond1, InsertPt); | |||
491 | ||||
492 | Result = BinaryOperator::CreateAnd(Cond0, Cond1, "wide.chk", InsertPt); | |||
493 | } | |||
494 | ||||
495 | // We were not able to compute Cond0 AND Cond1 for the price of one. | |||
496 | return false; | |||
497 | } | |||
498 | ||||
499 | bool GuardWideningImpl::parseRangeChecks( | |||
500 | Value *CheckCond, SmallVectorImpl<GuardWideningImpl::RangeCheck> &Checks, | |||
501 | SmallPtrSetImpl<Value *> &Visited) { | |||
502 | if (!Visited.insert(CheckCond).second) | |||
503 | return true; | |||
504 | ||||
505 | using namespace llvm::PatternMatch; | |||
506 | ||||
507 | { | |||
508 | Value *AndLHS, *AndRHS; | |||
509 | if (match(CheckCond, m_And(m_Value(AndLHS), m_Value(AndRHS)))) | |||
510 | return parseRangeChecks(AndLHS, Checks) && | |||
511 | parseRangeChecks(AndRHS, Checks); | |||
512 | } | |||
513 | ||||
514 | auto *IC = dyn_cast<ICmpInst>(CheckCond); | |||
515 | if (!IC || !IC->getOperand(0)->getType()->isIntegerTy() || | |||
516 | (IC->getPredicate() != ICmpInst::ICMP_ULT && | |||
517 | IC->getPredicate() != ICmpInst::ICMP_UGT)) | |||
518 | return false; | |||
519 | ||||
520 | Value *CmpLHS = IC->getOperand(0), *CmpRHS = IC->getOperand(1); | |||
521 | if (IC->getPredicate() == ICmpInst::ICMP_UGT) | |||
522 | std::swap(CmpLHS, CmpRHS); | |||
523 | ||||
524 | auto &DL = IC->getModule()->getDataLayout(); | |||
525 | ||||
526 | GuardWideningImpl::RangeCheck Check( | |||
527 | CmpLHS, cast<ConstantInt>(ConstantInt::getNullValue(CmpRHS->getType())), | |||
528 | CmpRHS, IC); | |||
529 | ||||
530 | if (!isKnownNonNegative(Check.getLength(), DL)) | |||
531 | return false; | |||
532 | ||||
533 | // What we have in \c Check now is a correct interpretation of \p CheckCond. | |||
534 | // Try to see if we can move some constant offsets into the \c Offset field. | |||
535 | ||||
536 | bool Changed; | |||
537 | auto &Ctx = CheckCond->getContext(); | |||
538 | ||||
539 | do { | |||
540 | Value *OpLHS; | |||
541 | ConstantInt *OpRHS; | |||
542 | Changed = false; | |||
543 | ||||
544 | #ifndef NDEBUG | |||
545 | auto *BaseInst = dyn_cast<Instruction>(Check.getBase()); | |||
546 | assert((!BaseInst || DT.isReachableFromEntry(BaseInst->getParent())) &&(static_cast <bool> ((!BaseInst || DT.isReachableFromEntry (BaseInst->getParent())) && "Unreachable instruction?" ) ? void (0) : __assert_fail ("(!BaseInst || DT.isReachableFromEntry(BaseInst->getParent())) && \"Unreachable instruction?\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 547, __extension__ __PRETTY_FUNCTION__)) | |||
547 | "Unreachable instruction?")(static_cast <bool> ((!BaseInst || DT.isReachableFromEntry (BaseInst->getParent())) && "Unreachable instruction?" ) ? void (0) : __assert_fail ("(!BaseInst || DT.isReachableFromEntry(BaseInst->getParent())) && \"Unreachable instruction?\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 547, __extension__ __PRETTY_FUNCTION__)); | |||
548 | #endif | |||
549 | ||||
550 | if (match(Check.getBase(), m_Add(m_Value(OpLHS), m_ConstantInt(OpRHS)))) { | |||
551 | Check.setBase(OpLHS); | |||
552 | APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue(); | |||
553 | Check.setOffset(ConstantInt::get(Ctx, NewOffset)); | |||
554 | Changed = true; | |||
555 | } else if (match(Check.getBase(), | |||
556 | m_Or(m_Value(OpLHS), m_ConstantInt(OpRHS)))) { | |||
557 | KnownBits Known = computeKnownBits(OpLHS, DL); | |||
558 | if ((OpRHS->getValue() & Known.Zero) == OpRHS->getValue()) { | |||
559 | Check.setBase(OpLHS); | |||
560 | APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue(); | |||
561 | Check.setOffset(ConstantInt::get(Ctx, NewOffset)); | |||
562 | Changed = true; | |||
563 | } | |||
564 | } | |||
565 | } while (Changed); | |||
566 | ||||
567 | Checks.push_back(Check); | |||
568 | return true; | |||
569 | } | |||
570 | ||||
571 | bool GuardWideningImpl::combineRangeChecks( | |||
572 | SmallVectorImpl<GuardWideningImpl::RangeCheck> &Checks, | |||
573 | SmallVectorImpl<GuardWideningImpl::RangeCheck> &RangeChecksOut) { | |||
574 | unsigned OldCount = Checks.size(); | |||
575 | while (!Checks.empty()) { | |||
576 | // Pick all of the range checks with a specific base and length, and try to | |||
577 | // merge them. | |||
578 | Value *CurrentBase = Checks.front().getBase(); | |||
579 | Value *CurrentLength = Checks.front().getLength(); | |||
580 | ||||
581 | SmallVector<GuardWideningImpl::RangeCheck, 3> CurrentChecks; | |||
582 | ||||
583 | auto IsCurrentCheck = [&](GuardWideningImpl::RangeCheck &RC) { | |||
584 | return RC.getBase() == CurrentBase && RC.getLength() == CurrentLength; | |||
585 | }; | |||
586 | ||||
587 | copy_if(Checks, std::back_inserter(CurrentChecks), IsCurrentCheck); | |||
588 | Checks.erase(remove_if(Checks, IsCurrentCheck), Checks.end()); | |||
589 | ||||
590 | assert(CurrentChecks.size() != 0 && "We know we have at least one!")(static_cast <bool> (CurrentChecks.size() != 0 && "We know we have at least one!") ? void (0) : __assert_fail ( "CurrentChecks.size() != 0 && \"We know we have at least one!\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 590, __extension__ __PRETTY_FUNCTION__)); | |||
591 | ||||
592 | if (CurrentChecks.size() < 3) { | |||
593 | RangeChecksOut.insert(RangeChecksOut.end(), CurrentChecks.begin(), | |||
594 | CurrentChecks.end()); | |||
595 | continue; | |||
596 | } | |||
597 | ||||
598 | // CurrentChecks.size() will typically be 3 here, but so far there has been | |||
599 | // no need to hard-code that fact. | |||
600 | ||||
601 | llvm::sort(CurrentChecks.begin(), CurrentChecks.end(), | |||
602 | [&](const GuardWideningImpl::RangeCheck &LHS, | |||
603 | const GuardWideningImpl::RangeCheck &RHS) { | |||
604 | return LHS.getOffsetValue().slt(RHS.getOffsetValue()); | |||
605 | }); | |||
606 | ||||
607 | // Note: std::sort should not invalidate the ChecksStart iterator. | |||
608 | ||||
609 | ConstantInt *MinOffset = CurrentChecks.front().getOffset(), | |||
610 | *MaxOffset = CurrentChecks.back().getOffset(); | |||
611 | ||||
612 | unsigned BitWidth = MaxOffset->getValue().getBitWidth(); | |||
613 | if ((MaxOffset->getValue() - MinOffset->getValue()) | |||
614 | .ugt(APInt::getSignedMinValue(BitWidth))) | |||
615 | return false; | |||
616 | ||||
617 | APInt MaxDiff = MaxOffset->getValue() - MinOffset->getValue(); | |||
618 | const APInt &HighOffset = MaxOffset->getValue(); | |||
619 | auto OffsetOK = [&](const GuardWideningImpl::RangeCheck &RC) { | |||
620 | return (HighOffset - RC.getOffsetValue()).ult(MaxDiff); | |||
621 | }; | |||
622 | ||||
623 | if (MaxDiff.isMinValue() || | |||
624 | !std::all_of(std::next(CurrentChecks.begin()), CurrentChecks.end(), | |||
625 | OffsetOK)) | |||
626 | return false; | |||
627 | ||||
628 | // We have a series of f+1 checks as: | |||
629 | // | |||
630 | // I+k_0 u< L ... Chk_0 | |||
631 | // I+k_1 u< L ... Chk_1 | |||
632 | // ... | |||
633 | // I+k_f u< L ... Chk_f | |||
634 | // | |||
635 | // with forall i in [0,f]: k_f-k_i u< k_f-k_0 ... Precond_0 | |||
636 | // k_f-k_0 u< INT_MIN+k_f ... Precond_1 | |||
637 | // k_f != k_0 ... Precond_2 | |||
638 | // | |||
639 | // Claim: | |||
640 | // Chk_0 AND Chk_f implies all the other checks | |||
641 | // | |||
642 | // Informal proof sketch: | |||
643 | // | |||
644 | // We will show that the integer range [I+k_0,I+k_f] does not unsigned-wrap | |||
645 | // (i.e. going from I+k_0 to I+k_f does not cross the -1,0 boundary) and | |||
646 | // thus I+k_f is the greatest unsigned value in that range. | |||
647 | // | |||
648 | // This combined with Ckh_(f+1) shows that everything in that range is u< L. | |||
649 | // Via Precond_0 we know that all of the indices in Chk_0 through Chk_(f+1) | |||
650 | // lie in [I+k_0,I+k_f], this proving our claim. | |||
651 | // | |||
652 | // To see that [I+k_0,I+k_f] is not a wrapping range, note that there are | |||
653 | // two possibilities: I+k_0 u< I+k_f or I+k_0 >u I+k_f (they can't be equal | |||
654 | // since k_0 != k_f). In the former case, [I+k_0,I+k_f] is not a wrapping | |||
655 | // range by definition, and the latter case is impossible: | |||
656 | // | |||
657 | // 0-----I+k_f---I+k_0----L---INT_MAX,INT_MIN------------------(-1) | |||
658 | // xxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx | |||
659 | // | |||
660 | // For Chk_0 to succeed, we'd have to have k_f-k_0 (the range highlighted | |||
661 | // with 'x' above) to be at least >u INT_MIN. | |||
662 | ||||
663 | RangeChecksOut.emplace_back(CurrentChecks.front()); | |||
664 | RangeChecksOut.emplace_back(CurrentChecks.back()); | |||
665 | } | |||
666 | ||||
667 | assert(RangeChecksOut.size() <= OldCount && "We pessimized!")(static_cast <bool> (RangeChecksOut.size() <= OldCount && "We pessimized!") ? void (0) : __assert_fail ("RangeChecksOut.size() <= OldCount && \"We pessimized!\"" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 667, __extension__ __PRETTY_FUNCTION__)); | |||
668 | return RangeChecksOut.size() != OldCount; | |||
669 | } | |||
670 | ||||
671 | #ifndef NDEBUG | |||
672 | StringRef GuardWideningImpl::scoreTypeToString(WideningScore WS) { | |||
673 | switch (WS) { | |||
674 | case WS_IllegalOrNegative: | |||
675 | return "IllegalOrNegative"; | |||
676 | case WS_Neutral: | |||
677 | return "Neutral"; | |||
678 | case WS_Positive: | |||
679 | return "Positive"; | |||
680 | case WS_VeryPositive: | |||
681 | return "VeryPositive"; | |||
682 | } | |||
683 | ||||
684 | llvm_unreachable("Fully covered switch above!")::llvm::llvm_unreachable_internal("Fully covered switch above!" , "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/Scalar/GuardWidening.cpp" , 684); | |||
685 | } | |||
686 | #endif | |||
687 | ||||
688 | PreservedAnalyses GuardWideningPass::run(Function &F, | |||
689 | FunctionAnalysisManager &AM) { | |||
690 | auto &DT = AM.getResult<DominatorTreeAnalysis>(F); | |||
691 | auto &LI = AM.getResult<LoopAnalysis>(F); | |||
692 | auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F); | |||
693 | if (!GuardWideningImpl(DT, &PDT, LI, DT.getRootNode(), | |||
694 | [](BasicBlock*) { return true; } ).run()) | |||
695 | return PreservedAnalyses::all(); | |||
696 | ||||
697 | PreservedAnalyses PA; | |||
698 | PA.preserveSet<CFGAnalyses>(); | |||
699 | return PA; | |||
700 | } | |||
701 | ||||
702 | namespace { | |||
703 | struct GuardWideningLegacyPass : public FunctionPass { | |||
704 | static char ID; | |||
705 | ||||
706 | GuardWideningLegacyPass() : FunctionPass(ID) { | |||
707 | initializeGuardWideningLegacyPassPass(*PassRegistry::getPassRegistry()); | |||
708 | } | |||
709 | ||||
710 | bool runOnFunction(Function &F) override { | |||
711 | if (skipFunction(F)) | |||
712 | return false; | |||
713 | auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); | |||
714 | auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); | |||
715 | auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree(); | |||
716 | return GuardWideningImpl(DT, &PDT, LI, DT.getRootNode(), | |||
717 | [](BasicBlock*) { return true; } ).run(); | |||
718 | } | |||
719 | ||||
720 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
721 | AU.setPreservesCFG(); | |||
722 | AU.addRequired<DominatorTreeWrapperPass>(); | |||
723 | AU.addRequired<PostDominatorTreeWrapperPass>(); | |||
724 | AU.addRequired<LoopInfoWrapperPass>(); | |||
725 | } | |||
726 | }; | |||
727 | ||||
728 | /// Same as above, but restricted to a single loop at a time. Can be | |||
729 | /// scheduled with other loop passes w/o breaking out of LPM | |||
730 | struct LoopGuardWideningLegacyPass : public LoopPass { | |||
731 | static char ID; | |||
732 | ||||
733 | LoopGuardWideningLegacyPass() : LoopPass(ID) { | |||
734 | initializeLoopGuardWideningLegacyPassPass(*PassRegistry::getPassRegistry()); | |||
735 | } | |||
736 | ||||
737 | bool runOnLoop(Loop *L, LPPassManager &LPM) override { | |||
738 | if (skipLoop(L)) | |||
| ||||
739 | return false; | |||
740 | auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); | |||
741 | auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); | |||
742 | auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>(); | |||
743 | auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr; | |||
744 | BasicBlock *RootBB = L->getLoopPredecessor(); | |||
745 | if (!RootBB) | |||
746 | RootBB = L->getHeader(); | |||
747 | auto BlockFilter = [&](BasicBlock *BB) { | |||
748 | return BB == RootBB || L->contains(BB); | |||
749 | }; | |||
750 | return GuardWideningImpl(DT, PDT, LI, | |||
751 | DT.getNode(RootBB), BlockFilter).run(); | |||
752 | } | |||
753 | ||||
754 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
755 | AU.setPreservesCFG(); | |||
756 | getLoopAnalysisUsage(AU); | |||
757 | AU.addPreserved<PostDominatorTreeWrapperPass>(); | |||
758 | } | |||
759 | }; | |||
760 | } | |||
761 | ||||
762 | char GuardWideningLegacyPass::ID = 0; | |||
763 | char LoopGuardWideningLegacyPass::ID = 0; | |||
764 | ||||
765 | INITIALIZE_PASS_BEGIN(GuardWideningLegacyPass, "guard-widening", "Widen guards",static void *initializeGuardWideningLegacyPassPassOnce(PassRegistry &Registry) { | |||
766 | false, false)static void *initializeGuardWideningLegacyPassPassOnce(PassRegistry &Registry) { | |||
767 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry); | |||
768 | INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)initializePostDominatorTreeWrapperPassPass(Registry); | |||
769 | INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)initializeLoopInfoWrapperPassPass(Registry); | |||
770 | INITIALIZE_PASS_END(GuardWideningLegacyPass, "guard-widening", "Widen guards",PassInfo *PI = new PassInfo( "Widen guards", "guard-widening" , &GuardWideningLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <GuardWideningLegacyPass>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeGuardWideningLegacyPassPassFlag ; void llvm::initializeGuardWideningLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeGuardWideningLegacyPassPassFlag , initializeGuardWideningLegacyPassPassOnce, std::ref(Registry )); } | |||
771 | false, false)PassInfo *PI = new PassInfo( "Widen guards", "guard-widening" , &GuardWideningLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <GuardWideningLegacyPass>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeGuardWideningLegacyPassPassFlag ; void llvm::initializeGuardWideningLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeGuardWideningLegacyPassPassFlag , initializeGuardWideningLegacyPassPassOnce, std::ref(Registry )); } | |||
772 | ||||
773 | INITIALIZE_PASS_BEGIN(LoopGuardWideningLegacyPass, "loop-guard-widening",static void *initializeLoopGuardWideningLegacyPassPassOnce(PassRegistry &Registry) { | |||
774 | "Widen guards (within a single loop, as a loop pass)",static void *initializeLoopGuardWideningLegacyPassPassOnce(PassRegistry &Registry) { | |||
775 | false, false)static void *initializeLoopGuardWideningLegacyPassPassOnce(PassRegistry &Registry) { | |||
776 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry); | |||
777 | INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)initializePostDominatorTreeWrapperPassPass(Registry); | |||
778 | INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)initializeLoopInfoWrapperPassPass(Registry); | |||
779 | INITIALIZE_PASS_END(LoopGuardWideningLegacyPass, "loop-guard-widening",PassInfo *PI = new PassInfo( "Widen guards (within a single loop, as a loop pass)" , "loop-guard-widening", &LoopGuardWideningLegacyPass::ID , PassInfo::NormalCtor_t(callDefaultCtor<LoopGuardWideningLegacyPass >), false, false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeLoopGuardWideningLegacyPassPassFlag ; void llvm::initializeLoopGuardWideningLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeLoopGuardWideningLegacyPassPassFlag , initializeLoopGuardWideningLegacyPassPassOnce, std::ref(Registry )); } | |||
780 | "Widen guards (within a single loop, as a loop pass)",PassInfo *PI = new PassInfo( "Widen guards (within a single loop, as a loop pass)" , "loop-guard-widening", &LoopGuardWideningLegacyPass::ID , PassInfo::NormalCtor_t(callDefaultCtor<LoopGuardWideningLegacyPass >), false, false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeLoopGuardWideningLegacyPassPassFlag ; void llvm::initializeLoopGuardWideningLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeLoopGuardWideningLegacyPassPassFlag , initializeLoopGuardWideningLegacyPassPassOnce, std::ref(Registry )); } | |||
781 | false, false)PassInfo *PI = new PassInfo( "Widen guards (within a single loop, as a loop pass)" , "loop-guard-widening", &LoopGuardWideningLegacyPass::ID , PassInfo::NormalCtor_t(callDefaultCtor<LoopGuardWideningLegacyPass >), false, false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeLoopGuardWideningLegacyPassPassFlag ; void llvm::initializeLoopGuardWideningLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeLoopGuardWideningLegacyPassPassFlag , initializeLoopGuardWideningLegacyPassPassOnce, std::ref(Registry )); } | |||
782 | ||||
783 | FunctionPass *llvm::createGuardWideningPass() { | |||
784 | return new GuardWideningLegacyPass(); | |||
785 | } | |||
786 | ||||
787 | Pass *llvm::createLoopGuardWideningPass() { | |||
788 | return new LoopGuardWideningLegacyPass(); | |||
789 | } |