/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Transforms/Scalar/GuardWidening.cpp
Line | Count | Source (jump to first uncovered line) |
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 "llvm/ADT/DenseMap.h" |
44 | | #include "llvm/ADT/DepthFirstIterator.h" |
45 | | #include "llvm/Analysis/LoopInfo.h" |
46 | | #include "llvm/Analysis/PostDominators.h" |
47 | | #include "llvm/Analysis/ValueTracking.h" |
48 | | #include "llvm/IR/ConstantRange.h" |
49 | | #include "llvm/IR/Dominators.h" |
50 | | #include "llvm/IR/IntrinsicInst.h" |
51 | | #include "llvm/IR/PatternMatch.h" |
52 | | #include "llvm/Pass.h" |
53 | | #include "llvm/Support/Debug.h" |
54 | | #include "llvm/Support/KnownBits.h" |
55 | | #include "llvm/Transforms/Scalar.h" |
56 | | |
57 | | using namespace llvm; |
58 | | |
59 | | #define DEBUG_TYPE "guard-widening" |
60 | | |
61 | | namespace { |
62 | | |
63 | | class GuardWideningImpl { |
64 | | DominatorTree &DT; |
65 | | PostDominatorTree &PDT; |
66 | | LoopInfo &LI; |
67 | | |
68 | | /// The set of guards whose conditions have been widened into dominating |
69 | | /// guards. |
70 | | SmallVector<IntrinsicInst *, 16> EliminatedGuards; |
71 | | |
72 | | /// The set of guards which have been widened to include conditions to other |
73 | | /// guards. |
74 | | DenseSet<IntrinsicInst *> WidenedGuards; |
75 | | |
76 | | /// Try to eliminate guard \p Guard by widening it into an earlier dominating |
77 | | /// guard. \p DFSI is the DFS iterator on the dominator tree that is |
78 | | /// currently visiting the block containing \p Guard, and \p GuardsPerBlock |
79 | | /// maps BasicBlocks to the set of guards seen in that block. |
80 | | bool eliminateGuardViaWidening( |
81 | | IntrinsicInst *Guard, const df_iterator<DomTreeNode *> &DFSI, |
82 | | const DenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 8>> & |
83 | | GuardsPerBlock); |
84 | | |
85 | | /// Used to keep track of which widening potential is more effective. |
86 | | enum WideningScore { |
87 | | /// Don't widen. |
88 | | WS_IllegalOrNegative, |
89 | | |
90 | | /// Widening is performance neutral as far as the cycles spent in check |
91 | | /// conditions goes (but can still help, e.g., code layout, having less |
92 | | /// deopt state). |
93 | | WS_Neutral, |
94 | | |
95 | | /// Widening is profitable. |
96 | | WS_Positive, |
97 | | |
98 | | /// Widening is very profitable. Not significantly different from \c |
99 | | /// WS_Positive, except by the order. |
100 | | WS_VeryPositive |
101 | | }; |
102 | | |
103 | | static StringRef scoreTypeToString(WideningScore WS); |
104 | | |
105 | | /// Compute the score for widening the condition in \p DominatedGuard |
106 | | /// (contained in \p DominatedGuardLoop) into \p DominatingGuard (contained in |
107 | | /// \p DominatingGuardLoop). |
108 | | WideningScore computeWideningScore(IntrinsicInst *DominatedGuard, |
109 | | Loop *DominatedGuardLoop, |
110 | | IntrinsicInst *DominatingGuard, |
111 | | Loop *DominatingGuardLoop); |
112 | | |
113 | | /// Helper to check if \p V can be hoisted to \p InsertPos. |
114 | 78 | bool isAvailableAt(Value *V, Instruction *InsertPos) { |
115 | 78 | SmallPtrSet<Instruction *, 8> Visited; |
116 | 78 | return isAvailableAt(V, InsertPos, Visited); |
117 | 78 | } |
118 | | |
119 | | bool isAvailableAt(Value *V, Instruction *InsertPos, |
120 | | SmallPtrSetImpl<Instruction *> &Visited); |
121 | | |
122 | | /// Helper to hoist \p V to \p InsertPos. Guaranteed to succeed if \c |
123 | | /// isAvailableAt returned true. |
124 | | void makeAvailableAt(Value *V, Instruction *InsertPos); |
125 | | |
126 | | /// Common helper used by \c widenGuard and \c isWideningCondProfitable. Try |
127 | | /// to generate an expression computing the logical AND of \p Cond0 and \p |
128 | | /// Cond1. Return true if the expression computing the AND is only as |
129 | | /// expensive as computing one of the two. If \p InsertPt is true then |
130 | | /// actually generate the resulting expression, make it available at \p |
131 | | /// InsertPt and return it in \p Result (else no change to the IR is made). |
132 | | bool widenCondCommon(Value *Cond0, Value *Cond1, Instruction *InsertPt, |
133 | | Value *&Result); |
134 | | |
135 | | /// Represents a range check of the form \c Base + \c Offset u< \c Length, |
136 | | /// with the constraint that \c Length is not negative. \c CheckInst is the |
137 | | /// pre-existing instruction in the IR that computes the result of this range |
138 | | /// check. |
139 | | class RangeCheck { |
140 | | Value *Base; |
141 | | ConstantInt *Offset; |
142 | | Value *Length; |
143 | | ICmpInst *CheckInst; |
144 | | |
145 | | public: |
146 | | explicit RangeCheck(Value *Base, ConstantInt *Offset, Value *Length, |
147 | | ICmpInst *CheckInst) |
148 | 199 | : Base(Base), Offset(Offset), Length(Length), CheckInst(CheckInst) {} |
149 | | |
150 | 162 | void setBase(Value *NewBase) { Base = NewBase; } |
151 | 162 | void setOffset(ConstantInt *NewOffset) { Offset = NewOffset; } |
152 | | |
153 | 1.04k | Value *getBase() const { return Base; } |
154 | 486 | ConstantInt *getOffset() const { return Offset; } |
155 | 414 | const APInt &getOffsetValue() const { return getOffset()->getValue(); } |
156 | 637 | Value *getLength() const { return Length; }; |
157 | 64 | ICmpInst *getCheckInst() const { return CheckInst; } |
158 | | |
159 | 0 | void print(raw_ostream &OS, bool PrintTypes = false) { |
160 | 0 | OS << "Base: "; |
161 | 0 | Base->printAsOperand(OS, PrintTypes); |
162 | 0 | OS << " Offset: "; |
163 | 0 | Offset->printAsOperand(OS, PrintTypes); |
164 | 0 | OS << " Length: "; |
165 | 0 | Length->printAsOperand(OS, PrintTypes); |
166 | 0 | } |
167 | | |
168 | 0 | LLVM_DUMP_METHOD void dump() { |
169 | 0 | print(dbgs()); |
170 | 0 | dbgs() << "\n"; |
171 | 0 | } |
172 | | }; |
173 | | |
174 | | /// Parse \p CheckCond into a conjunction (logical-and) of range checks; and |
175 | | /// append them to \p Checks. Returns true on success, may clobber \c Checks |
176 | | /// on failure. |
177 | 304 | bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks) { |
178 | 304 | SmallPtrSet<Value *, 8> Visited; |
179 | 304 | return parseRangeChecks(CheckCond, Checks, Visited); |
180 | 304 | } |
181 | | |
182 | | bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks, |
183 | | SmallPtrSetImpl<Value *> &Visited); |
184 | | |
185 | | /// Combine the checks in \p Checks into a smaller set of checks and append |
186 | | /// them into \p CombinedChecks. Return true on success (i.e. all of checks |
187 | | /// in \p Checks were combined into \p CombinedChecks). Clobbers \p Checks |
188 | | /// and \p CombinedChecks on success and on failure. |
189 | | bool combineRangeChecks(SmallVectorImpl<RangeCheck> &Checks, |
190 | | SmallVectorImpl<RangeCheck> &CombinedChecks); |
191 | | |
192 | | /// Can we compute the logical AND of \p Cond0 and \p Cond1 for the price of |
193 | | /// computing only one of the two expressions? |
194 | 74 | bool isWideningCondProfitable(Value *Cond0, Value *Cond1) { |
195 | 74 | Value *ResultUnused; |
196 | 74 | return widenCondCommon(Cond0, Cond1, /*InsertPt=*/nullptr, ResultUnused); |
197 | 74 | } |
198 | | |
199 | | /// Widen \p ToWiden to fail if \p NewCondition is false (in addition to |
200 | | /// whatever it is already checking). |
201 | 44 | void widenGuard(IntrinsicInst *ToWiden, Value *NewCondition) { |
202 | 44 | Value *Result; |
203 | 44 | widenCondCommon(ToWiden->getArgOperand(0), NewCondition, ToWiden, Result); |
204 | 44 | ToWiden->setArgOperand(0, Result); |
205 | 44 | } |
206 | | |
207 | | public: |
208 | | explicit GuardWideningImpl(DominatorTree &DT, PostDominatorTree &PDT, |
209 | | LoopInfo &LI) |
210 | 38 | : DT(DT), PDT(PDT), LI(LI) {} |
211 | | |
212 | | /// The entry point for this pass. |
213 | | bool run(); |
214 | | }; |
215 | | |
216 | | struct GuardWideningLegacyPass : public FunctionPass { |
217 | | static char ID; |
218 | | GuardWideningPass Impl; |
219 | | |
220 | 2 | GuardWideningLegacyPass() : FunctionPass(ID) { |
221 | 2 | initializeGuardWideningLegacyPassPass(*PassRegistry::getPassRegistry()); |
222 | 2 | } |
223 | | |
224 | 23 | bool runOnFunction(Function &F) override { |
225 | 23 | if (skipFunction(F)) |
226 | 0 | return false; |
227 | 23 | return GuardWideningImpl( |
228 | 23 | getAnalysis<DominatorTreeWrapperPass>().getDomTree(), |
229 | 23 | getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree(), |
230 | 23 | getAnalysis<LoopInfoWrapperPass>().getLoopInfo()).run(); |
231 | 23 | } |
232 | | |
233 | 2 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
234 | 2 | AU.setPreservesCFG(); |
235 | 2 | AU.addRequired<DominatorTreeWrapperPass>(); |
236 | 2 | AU.addRequired<PostDominatorTreeWrapperPass>(); |
237 | 2 | AU.addRequired<LoopInfoWrapperPass>(); |
238 | 2 | } |
239 | | }; |
240 | | |
241 | | } |
242 | | |
243 | 38 | bool GuardWideningImpl::run() { |
244 | 38 | using namespace llvm::PatternMatch; |
245 | 38 | |
246 | 38 | DenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 8>> GuardsInBlock; |
247 | 38 | bool Changed = false; |
248 | 38 | |
249 | 38 | for (auto DFI = df_begin(DT.getRootNode()), DFE = df_end(DT.getRootNode()); |
250 | 132 | DFI != DFE132 ; ++DFI94 ) { |
251 | 94 | auto *BB = (*DFI)->getBlock(); |
252 | 94 | auto &CurrentList = GuardsInBlock[BB]; |
253 | 94 | |
254 | 94 | for (auto &I : *BB) |
255 | 365 | if (365 match(&I, m_Intrinsic<Intrinsic::experimental_guard>())365 ) |
256 | 96 | CurrentList.push_back(cast<IntrinsicInst>(&I)); |
257 | 94 | |
258 | 94 | for (auto *II : CurrentList) |
259 | 96 | Changed |= eliminateGuardViaWidening(II, DFI, GuardsInBlock); |
260 | 94 | } |
261 | 38 | |
262 | 38 | for (auto *II : EliminatedGuards) |
263 | 44 | if (44 !WidenedGuards.count(II)44 ) |
264 | 44 | II->eraseFromParent(); |
265 | 38 | |
266 | 38 | return Changed; |
267 | 38 | } |
268 | | |
269 | | bool GuardWideningImpl::eliminateGuardViaWidening( |
270 | | IntrinsicInst *GuardInst, const df_iterator<DomTreeNode *> &DFSI, |
271 | | const DenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 8>> & |
272 | 96 | GuardsInBlock) { |
273 | 96 | IntrinsicInst *BestSoFar = nullptr; |
274 | 96 | auto BestScoreSoFar = WS_IllegalOrNegative; |
275 | 96 | auto *GuardInstLoop = LI.getLoopFor(GuardInst->getParent()); |
276 | 96 | |
277 | 96 | // In the set of dominating guards, find the one we can merge GuardInst with |
278 | 96 | // for the most profit. |
279 | 238 | for (unsigned i = 0, e = DFSI.getPathLength(); i != e238 ; ++i142 ) { |
280 | 142 | auto *CurBB = DFSI.getPath(i)->getBlock(); |
281 | 142 | auto *CurLoop = LI.getLoopFor(CurBB); |
282 | 142 | assert(GuardsInBlock.count(CurBB) && "Must have been populated by now!"); |
283 | 142 | const auto &GuardsInCurBB = GuardsInBlock.find(CurBB)->second; |
284 | 142 | |
285 | 142 | auto I = GuardsInCurBB.begin(); |
286 | 142 | auto E = GuardsInCurBB.end(); |
287 | 142 | |
288 | | #ifndef NDEBUG |
289 | | { |
290 | | unsigned Index = 0; |
291 | | for (auto &I : *CurBB) { |
292 | | if (Index == GuardsInCurBB.size()) |
293 | | break; |
294 | | if (GuardsInCurBB[Index] == &I) |
295 | | Index++; |
296 | | } |
297 | | assert(Index == GuardsInCurBB.size() && |
298 | | "Guards expected to be in order!"); |
299 | | } |
300 | | #endif |
301 | | |
302 | 142 | assert((i == (e - 1)) == (GuardInst->getParent() == CurBB) && "Bad DFS?"); |
303 | 142 | |
304 | 142 | if (i == (e - 1)142 ) { |
305 | 96 | // Corner case: make sure we're only looking at guards strictly dominating |
306 | 96 | // GuardInst when visiting GuardInst->getParent(). |
307 | 96 | auto NewEnd = std::find(I, E, GuardInst); |
308 | 96 | assert(NewEnd != E && "GuardInst not in its own block?"); |
309 | 96 | E = NewEnd; |
310 | 96 | } |
311 | 142 | |
312 | 86 | for (auto *Candidate : make_range(I, E)) { |
313 | 86 | auto Score = |
314 | 86 | computeWideningScore(GuardInst, GuardInstLoop, Candidate, CurLoop); |
315 | 86 | DEBUG(dbgs() << "Score between " << *GuardInst->getArgOperand(0) |
316 | 86 | << " and " << *Candidate->getArgOperand(0) << " is " |
317 | 86 | << scoreTypeToString(Score) << "\n"); |
318 | 86 | if (Score > BestScoreSoFar86 ) { |
319 | 44 | BestScoreSoFar = Score; |
320 | 44 | BestSoFar = Candidate; |
321 | 44 | } |
322 | 86 | } |
323 | 142 | } |
324 | 96 | |
325 | 96 | if (BestScoreSoFar == WS_IllegalOrNegative96 ) { |
326 | 52 | DEBUG(dbgs() << "Did not eliminate guard " << *GuardInst << "\n"); |
327 | 52 | return false; |
328 | 52 | } |
329 | 44 | |
330 | 96 | assert(BestSoFar != GuardInst && "Should have never visited same guard!"); |
331 | 44 | assert(DT.dominates(BestSoFar, GuardInst) && "Should be!"); |
332 | 44 | |
333 | 44 | DEBUG(dbgs() << "Widening " << *GuardInst << " into " << *BestSoFar |
334 | 96 | << " with score " << scoreTypeToString(BestScoreSoFar) << "\n"); |
335 | 96 | widenGuard(BestSoFar, GuardInst->getArgOperand(0)); |
336 | 96 | GuardInst->setArgOperand(0, ConstantInt::getTrue(GuardInst->getContext())); |
337 | 96 | EliminatedGuards.push_back(GuardInst); |
338 | 96 | WidenedGuards.insert(BestSoFar); |
339 | 96 | return true; |
340 | 96 | } |
341 | | |
342 | | GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore( |
343 | | IntrinsicInst *DominatedGuard, Loop *DominatedGuardLoop, |
344 | 86 | IntrinsicInst *DominatingGuard, Loop *DominatingGuardLoop) { |
345 | 86 | bool HoistingOutOfLoop = false; |
346 | 86 | |
347 | 86 | if (DominatingGuardLoop != DominatedGuardLoop86 ) { |
348 | 16 | if (DominatingGuardLoop && |
349 | 8 | !DominatingGuardLoop->contains(DominatedGuardLoop)) |
350 | 8 | return WS_IllegalOrNegative; |
351 | 8 | |
352 | 8 | HoistingOutOfLoop = true; |
353 | 8 | } |
354 | 86 | |
355 | 78 | if (78 !isAvailableAt(DominatedGuard->getArgOperand(0), DominatingGuard)78 ) |
356 | 4 | return WS_IllegalOrNegative; |
357 | 74 | |
358 | 74 | bool HoistingOutOfIf = |
359 | 74 | !PDT.dominates(DominatedGuard->getParent(), DominatingGuard->getParent()); |
360 | 74 | |
361 | 74 | if (isWideningCondProfitable(DominatedGuard->getArgOperand(0), |
362 | 74 | DominatingGuard->getArgOperand(0))) |
363 | 18 | return HoistingOutOfLoop ? 18 WS_VeryPositive0 : WS_Positive18 ; |
364 | 56 | |
365 | 56 | if (56 HoistingOutOfLoop56 ) |
366 | 8 | return WS_Positive; |
367 | 48 | |
368 | 48 | return HoistingOutOfIf ? 48 WS_IllegalOrNegative4 : WS_Neutral44 ; |
369 | 86 | } |
370 | | |
371 | | bool GuardWideningImpl::isAvailableAt(Value *V, Instruction *Loc, |
372 | 452 | SmallPtrSetImpl<Instruction *> &Visited) { |
373 | 452 | auto *Inst = dyn_cast<Instruction>(V); |
374 | 452 | if (!Inst || 452 DT.dominates(Inst, Loc)332 || Visited.count(Inst)256 ) |
375 | 260 | return true; |
376 | 192 | |
377 | 192 | if (192 !isSafeToSpeculativelyExecute(Inst, Loc, &DT) || |
378 | 190 | Inst->mayReadFromMemory()) |
379 | 4 | return false; |
380 | 188 | |
381 | 188 | Visited.insert(Inst); |
382 | 188 | |
383 | 188 | // We only want to go _up_ the dominance chain when recursing. |
384 | 188 | assert(!isa<PHINode>(Loc) && |
385 | 188 | "PHIs should return false for isSafeToSpeculativelyExecute"); |
386 | 188 | assert(DT.isReachableFromEntry(Inst->getParent()) && |
387 | 188 | "We did a DFS from the block entry!"); |
388 | 188 | return all_of(Inst->operands(), |
389 | 374 | [&](Value *Op) { return isAvailableAt(Op, Loc, Visited); }); |
390 | 452 | } |
391 | | |
392 | 322 | void GuardWideningImpl::makeAvailableAt(Value *V, Instruction *Loc) { |
393 | 322 | auto *Inst = dyn_cast<Instruction>(V); |
394 | 322 | if (!Inst || 322 DT.dominates(Inst, Loc)249 ) |
395 | 202 | return; |
396 | 120 | |
397 | 322 | assert(isSafeToSpeculativelyExecute(Inst, Loc, &DT) && |
398 | 120 | !Inst->mayReadFromMemory() && "Should've checked with isAvailableAt!"); |
399 | 120 | |
400 | 120 | for (Value *Op : Inst->operands()) |
401 | 238 | makeAvailableAt(Op, Loc); |
402 | 322 | |
403 | 322 | Inst->moveBefore(Loc); |
404 | 322 | } |
405 | | |
406 | | bool GuardWideningImpl::widenCondCommon(Value *Cond0, Value *Cond1, |
407 | 118 | Instruction *InsertPt, Value *&Result) { |
408 | 118 | using namespace llvm::PatternMatch; |
409 | 118 | |
410 | 118 | { |
411 | 118 | // L >u C0 && L >u C1 -> L >u max(C0, C1) |
412 | 118 | ConstantInt *RHS0, *RHS1; |
413 | 118 | Value *LHS; |
414 | 118 | ICmpInst::Predicate Pred0, Pred1; |
415 | 118 | if (match(Cond0, m_ICmp(Pred0, m_Value(LHS), m_ConstantInt(RHS0))) && |
416 | 118 | match(Cond1, m_ICmp(Pred1, m_Specific(LHS), m_ConstantInt(RHS1)))26 ) { |
417 | 10 | |
418 | 10 | ConstantRange CR0 = |
419 | 10 | ConstantRange::makeExactICmpRegion(Pred0, RHS0->getValue()); |
420 | 10 | ConstantRange CR1 = |
421 | 10 | ConstantRange::makeExactICmpRegion(Pred1, RHS1->getValue()); |
422 | 10 | |
423 | 10 | // SubsetIntersect is a subset of the actual mathematical intersection of |
424 | 10 | // CR0 and CR1, while SupersetIntersect is a superset of the actual |
425 | 10 | // mathematical intersection. If these two ConstantRanges are equal, then |
426 | 10 | // we know we were able to represent the actual mathematical intersection |
427 | 10 | // of CR0 and CR1, and can use the same to generate an icmp instruction. |
428 | 10 | // |
429 | 10 | // Given what we're doing here and the semantics of guards, it would |
430 | 10 | // actually be correct to just use SubsetIntersect, but that may be too |
431 | 10 | // aggressive in cases we care about. |
432 | 10 | auto SubsetIntersect = CR0.inverse().unionWith(CR1.inverse()).inverse(); |
433 | 10 | auto SupersetIntersect = CR0.intersectWith(CR1); |
434 | 10 | |
435 | 10 | APInt NewRHSAP; |
436 | 10 | CmpInst::Predicate Pred; |
437 | 10 | if (SubsetIntersect == SupersetIntersect && |
438 | 10 | SubsetIntersect.getEquivalentICmp(Pred, NewRHSAP)10 ) { |
439 | 8 | if (InsertPt8 ) { |
440 | 4 | ConstantInt *NewRHS = ConstantInt::get(Cond0->getContext(), NewRHSAP); |
441 | 4 | Result = new ICmpInst(InsertPt, Pred, LHS, NewRHS, "wide.chk"); |
442 | 4 | } |
443 | 8 | return true; |
444 | 8 | } |
445 | 110 | } |
446 | 110 | } |
447 | 110 | |
448 | 110 | { |
449 | 110 | SmallVector<GuardWideningImpl::RangeCheck, 4> Checks, CombinedChecks; |
450 | 110 | if (parseRangeChecks(Cond0, Checks) && 110 parseRangeChecks(Cond1, Checks)88 && |
451 | 110 | combineRangeChecks(Checks, CombinedChecks)58 ) { |
452 | 28 | if (InsertPt28 ) { |
453 | 14 | Result = nullptr; |
454 | 32 | for (auto &RC : CombinedChecks) { |
455 | 32 | makeAvailableAt(RC.getCheckInst(), InsertPt); |
456 | 32 | if (Result) |
457 | 18 | Result = BinaryOperator::CreateAnd(RC.getCheckInst(), Result, "", |
458 | 18 | InsertPt); |
459 | 32 | else |
460 | 14 | Result = RC.getCheckInst(); |
461 | 32 | } |
462 | 14 | |
463 | 14 | Result->setName("wide.chk"); |
464 | 14 | } |
465 | 28 | return true; |
466 | 28 | } |
467 | 82 | } |
468 | 82 | |
469 | 82 | // Base case -- just logical-and the two conditions together. |
470 | 82 | |
471 | 82 | if (82 InsertPt82 ) { |
472 | 26 | makeAvailableAt(Cond0, InsertPt); |
473 | 26 | makeAvailableAt(Cond1, InsertPt); |
474 | 26 | |
475 | 26 | Result = BinaryOperator::CreateAnd(Cond0, Cond1, "wide.chk", InsertPt); |
476 | 26 | } |
477 | 118 | |
478 | 118 | // We were not able to compute Cond0 AND Cond1 for the price of one. |
479 | 118 | return false; |
480 | 118 | } |
481 | | |
482 | | bool GuardWideningImpl::parseRangeChecks( |
483 | | Value *CheckCond, SmallVectorImpl<GuardWideningImpl::RangeCheck> &Checks, |
484 | 304 | SmallPtrSetImpl<Value *> &Visited) { |
485 | 304 | if (!Visited.insert(CheckCond).second) |
486 | 0 | return true; |
487 | 304 | |
488 | 304 | using namespace llvm::PatternMatch; |
489 | 304 | |
490 | 304 | { |
491 | 304 | Value *AndLHS, *AndRHS; |
492 | 304 | if (match(CheckCond, m_And(m_Value(AndLHS), m_Value(AndRHS)))) |
493 | 53 | return parseRangeChecks(AndLHS, Checks) && |
494 | 53 | parseRangeChecks(AndRHS, Checks); |
495 | 251 | } |
496 | 251 | |
497 | 251 | auto *IC = dyn_cast<ICmpInst>(CheckCond); |
498 | 251 | if (!IC || 251 !IC->getOperand(0)->getType()->isIntegerTy()201 || |
499 | 201 | (IC->getPredicate() != ICmpInst::ICMP_ULT && |
500 | 2 | IC->getPredicate() != ICmpInst::ICMP_UGT)) |
501 | 52 | return false; |
502 | 199 | |
503 | 199 | Value *CmpLHS = IC->getOperand(0), *CmpRHS = IC->getOperand(1); |
504 | 199 | if (IC->getPredicate() == ICmpInst::ICMP_UGT) |
505 | 0 | std::swap(CmpLHS, CmpRHS); |
506 | 199 | |
507 | 199 | auto &DL = IC->getModule()->getDataLayout(); |
508 | 199 | |
509 | 199 | GuardWideningImpl::RangeCheck Check( |
510 | 199 | CmpLHS, cast<ConstantInt>(ConstantInt::getNullValue(CmpRHS->getType())), |
511 | 199 | CmpRHS, IC); |
512 | 199 | |
513 | 199 | if (!isKnownNonNegative(Check.getLength(), DL)) |
514 | 0 | return false; |
515 | 199 | |
516 | 199 | // What we have in \c Check now is a correct interpretation of \p CheckCond. |
517 | 199 | // Try to see if we can move some constant offsets into the \c Offset field. |
518 | 199 | |
519 | 199 | bool Changed; |
520 | 199 | auto &Ctx = CheckCond->getContext(); |
521 | 199 | |
522 | 361 | do { |
523 | 361 | Value *OpLHS; |
524 | 361 | ConstantInt *OpRHS; |
525 | 361 | Changed = false; |
526 | 361 | |
527 | | #ifndef NDEBUG |
528 | | auto *BaseInst = dyn_cast<Instruction>(Check.getBase()); |
529 | | assert((!BaseInst || DT.isReachableFromEntry(BaseInst->getParent())) && |
530 | | "Unreachable instruction?"); |
531 | | #endif |
532 | | |
533 | 361 | if (match(Check.getBase(), m_Add(m_Value(OpLHS), m_ConstantInt(OpRHS)))361 ) { |
534 | 140 | Check.setBase(OpLHS); |
535 | 140 | APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue(); |
536 | 140 | Check.setOffset(ConstantInt::get(Ctx, NewOffset)); |
537 | 140 | Changed = true; |
538 | 361 | } else if (221 match(Check.getBase(), |
539 | 221 | m_Or(m_Value(OpLHS), m_ConstantInt(OpRHS)))) { |
540 | 22 | KnownBits Known = computeKnownBits(OpLHS, DL); |
541 | 22 | if ((OpRHS->getValue() & Known.Zero) == OpRHS->getValue()22 ) { |
542 | 22 | Check.setBase(OpLHS); |
543 | 22 | APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue(); |
544 | 22 | Check.setOffset(ConstantInt::get(Ctx, NewOffset)); |
545 | 22 | Changed = true; |
546 | 22 | } |
547 | 221 | } |
548 | 361 | } while (Changed); |
549 | 304 | |
550 | 304 | Checks.push_back(Check); |
551 | 304 | return true; |
552 | 304 | } |
553 | | |
554 | | bool GuardWideningImpl::combineRangeChecks( |
555 | | SmallVectorImpl<GuardWideningImpl::RangeCheck> &Checks, |
556 | 58 | SmallVectorImpl<GuardWideningImpl::RangeCheck> &RangeChecksOut) { |
557 | 58 | unsigned OldCount = Checks.size(); |
558 | 128 | while (!Checks.empty()128 ) { |
559 | 74 | // Pick all of the range checks with a specific base and length, and try to |
560 | 74 | // merge them. |
561 | 74 | Value *CurrentBase = Checks.front().getBase(); |
562 | 74 | Value *CurrentLength = Checks.front().getLength(); |
563 | 74 | |
564 | 74 | SmallVector<GuardWideningImpl::RangeCheck, 3> CurrentChecks; |
565 | 74 | |
566 | 384 | auto IsCurrentCheck = [&](GuardWideningImpl::RangeCheck &RC) { |
567 | 364 | return RC.getBase() == CurrentBase && RC.getLength() == CurrentLength; |
568 | 384 | }; |
569 | 74 | |
570 | 74 | copy_if(Checks, std::back_inserter(CurrentChecks), IsCurrentCheck); |
571 | 74 | Checks.erase(remove_if(Checks, IsCurrentCheck), Checks.end()); |
572 | 74 | |
573 | 74 | assert(CurrentChecks.size() != 0 && "We know we have at least one!"); |
574 | 74 | |
575 | 74 | if (CurrentChecks.size() < 374 ) { |
576 | 38 | RangeChecksOut.insert(RangeChecksOut.end(), CurrentChecks.begin(), |
577 | 38 | CurrentChecks.end()); |
578 | 38 | continue; |
579 | 38 | } |
580 | 36 | |
581 | 36 | // CurrentChecks.size() will typically be 3 here, but so far there has been |
582 | 36 | // no need to hard-code that fact. |
583 | 36 | |
584 | 36 | std::sort(CurrentChecks.begin(), CurrentChecks.end(), |
585 | 36 | [&](const GuardWideningImpl::RangeCheck &LHS, |
586 | 94 | const GuardWideningImpl::RangeCheck &RHS) { |
587 | 94 | return LHS.getOffsetValue().slt(RHS.getOffsetValue()); |
588 | 94 | }); |
589 | 36 | |
590 | 36 | // Note: std::sort should not invalidate the ChecksStart iterator. |
591 | 36 | |
592 | 36 | ConstantInt *MinOffset = CurrentChecks.front().getOffset(), |
593 | 36 | *MaxOffset = CurrentChecks.back().getOffset(); |
594 | 36 | |
595 | 36 | unsigned BitWidth = MaxOffset->getValue().getBitWidth(); |
596 | 36 | if ((MaxOffset->getValue() - MinOffset->getValue()) |
597 | 36 | .ugt(APInt::getSignedMinValue(BitWidth))) |
598 | 4 | return false; |
599 | 32 | |
600 | 32 | APInt MaxDiff = MaxOffset->getValue() - MinOffset->getValue(); |
601 | 32 | const APInt &HighOffset = MaxOffset->getValue(); |
602 | 64 | auto OffsetOK = [&](const GuardWideningImpl::RangeCheck &RC) { |
603 | 64 | return (HighOffset - RC.getOffsetValue()).ult(MaxDiff); |
604 | 64 | }; |
605 | 32 | |
606 | 32 | if (MaxDiff.isMinValue() || |
607 | 32 | !std::all_of(std::next(CurrentChecks.begin()), CurrentChecks.end(), |
608 | 32 | OffsetOK)) |
609 | 0 | return false; |
610 | 32 | |
611 | 32 | // We have a series of f+1 checks as: |
612 | 32 | // |
613 | 32 | // I+k_0 u< L ... Chk_0 |
614 | 32 | // I+k_1 u< L ... Chk_1 |
615 | 32 | // ... |
616 | 32 | // I+k_f u< L ... Chk_f |
617 | 32 | // |
618 | 32 | // with forall i in [0,f]: k_f-k_i u< k_f-k_0 ... Precond_0 |
619 | 32 | // k_f-k_0 u< INT_MIN+k_f ... Precond_1 |
620 | 32 | // k_f != k_0 ... Precond_2 |
621 | 32 | // |
622 | 32 | // Claim: |
623 | 32 | // Chk_0 AND Chk_f implies all the other checks |
624 | 32 | // |
625 | 32 | // Informal proof sketch: |
626 | 32 | // |
627 | 32 | // We will show that the integer range [I+k_0,I+k_f] does not unsigned-wrap |
628 | 32 | // (i.e. going from I+k_0 to I+k_f does not cross the -1,0 boundary) and |
629 | 32 | // thus I+k_f is the greatest unsigned value in that range. |
630 | 32 | // |
631 | 32 | // This combined with Ckh_(f+1) shows that everything in that range is u< L. |
632 | 32 | // Via Precond_0 we know that all of the indices in Chk_0 through Chk_(f+1) |
633 | 32 | // lie in [I+k_0,I+k_f], this proving our claim. |
634 | 32 | // |
635 | 32 | // To see that [I+k_0,I+k_f] is not a wrapping range, note that there are |
636 | 32 | // two possibilities: I+k_0 u< I+k_f or I+k_0 >u I+k_f (they can't be equal |
637 | 32 | // since k_0 != k_f). In the former case, [I+k_0,I+k_f] is not a wrapping |
638 | 32 | // range by definition, and the latter case is impossible: |
639 | 32 | // |
640 | 32 | // 0-----I+k_f---I+k_0----L---INT_MAX,INT_MIN------------------(-1) |
641 | 32 | // xxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx |
642 | 32 | // |
643 | 32 | // For Chk_0 to succeed, we'd have to have k_f-k_0 (the range highlighted |
644 | 32 | // with 'x' above) to be at least >u INT_MIN. |
645 | 32 | |
646 | 32 | RangeChecksOut.emplace_back(CurrentChecks.front()); |
647 | 32 | RangeChecksOut.emplace_back(CurrentChecks.back()); |
648 | 32 | } |
649 | 58 | |
650 | 54 | assert(RangeChecksOut.size() <= OldCount && "We pessimized!"); |
651 | 54 | return RangeChecksOut.size() != OldCount; |
652 | 58 | } |
653 | | |
654 | | PreservedAnalyses GuardWideningPass::run(Function &F, |
655 | 15 | FunctionAnalysisManager &AM) { |
656 | 15 | auto &DT = AM.getResult<DominatorTreeAnalysis>(F); |
657 | 15 | auto &LI = AM.getResult<LoopAnalysis>(F); |
658 | 15 | auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F); |
659 | 15 | if (!GuardWideningImpl(DT, PDT, LI).run()) |
660 | 5 | return PreservedAnalyses::all(); |
661 | 10 | |
662 | 10 | PreservedAnalyses PA; |
663 | 10 | PA.preserveSet<CFGAnalyses>(); |
664 | 10 | return PA; |
665 | 10 | } |
666 | | |
667 | | #ifndef NDEBUG |
668 | | StringRef GuardWideningImpl::scoreTypeToString(WideningScore WS) { |
669 | | switch (WS) { |
670 | | case WS_IllegalOrNegative: |
671 | | return "IllegalOrNegative"; |
672 | | case WS_Neutral: |
673 | | return "Neutral"; |
674 | | case WS_Positive: |
675 | | return "Positive"; |
676 | | case WS_VeryPositive: |
677 | | return "VeryPositive"; |
678 | | } |
679 | | |
680 | | llvm_unreachable("Fully covered switch above!"); |
681 | | } |
682 | | #endif |
683 | | |
684 | | char GuardWideningLegacyPass::ID = 0; |
685 | | |
686 | 24.6k | INITIALIZE_PASS_BEGIN24.6k (GuardWideningLegacyPass, "guard-widening", "Widen guards",
|
687 | 24.6k | false, false) |
688 | 24.6k | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
689 | 24.6k | INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) |
690 | 24.6k | INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) |
691 | 24.6k | INITIALIZE_PASS_END(GuardWideningLegacyPass, "guard-widening", "Widen guards", |
692 | | false, false) |
693 | | |
694 | 0 | FunctionPass *llvm::createGuardWideningPass() { |
695 | 0 | return new GuardWideningLegacyPass(); |
696 | 0 | } |