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