1 //===- ImplicitNullChecks.cpp - Fold null checks into memory accesses -----===//
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 pass turns explicit null checks of the form
10 //
11 // test %r10, %r10
12 // je throw_npe
13 // movl (%r10), %esi
14 // ...
15 //
16 // to
17 //
18 // faulting_load_op("movl (%r10), %esi", throw_npe)
19 // ...
20 //
21 // With the help of a runtime that understands the .fault_maps section,
22 // faulting_load_op branches to throw_npe if executing movl (%r10), %esi incurs
23 // a page fault.
24 // Store and LoadStore are also supported.
25 //
26 //===----------------------------------------------------------------------===//
27
28 #include "llvm/ADT/ArrayRef.h"
29 #include "llvm/ADT/None.h"
30 #include "llvm/ADT/Optional.h"
31 #include "llvm/ADT/STLExtras.h"
32 #include "llvm/ADT/SmallVector.h"
33 #include "llvm/ADT/Statistic.h"
34 #include "llvm/Analysis/AliasAnalysis.h"
35 #include "llvm/Analysis/MemoryLocation.h"
36 #include "llvm/CodeGen/FaultMaps.h"
37 #include "llvm/CodeGen/MachineBasicBlock.h"
38 #include "llvm/CodeGen/MachineFunction.h"
39 #include "llvm/CodeGen/MachineFunctionPass.h"
40 #include "llvm/CodeGen/MachineInstr.h"
41 #include "llvm/CodeGen/MachineInstrBuilder.h"
42 #include "llvm/CodeGen/MachineMemOperand.h"
43 #include "llvm/CodeGen/MachineOperand.h"
44 #include "llvm/CodeGen/MachineRegisterInfo.h"
45 #include "llvm/CodeGen/PseudoSourceValue.h"
46 #include "llvm/CodeGen/TargetInstrInfo.h"
47 #include "llvm/CodeGen/TargetOpcodes.h"
48 #include "llvm/CodeGen/TargetRegisterInfo.h"
49 #include "llvm/CodeGen/TargetSubtargetInfo.h"
50 #include "llvm/IR/BasicBlock.h"
51 #include "llvm/IR/DebugLoc.h"
52 #include "llvm/IR/LLVMContext.h"
53 #include "llvm/InitializePasses.h"
54 #include "llvm/MC/MCInstrDesc.h"
55 #include "llvm/MC/MCRegisterInfo.h"
56 #include "llvm/Pass.h"
57 #include "llvm/Support/CommandLine.h"
58 #include <cassert>
59 #include <cstdint>
60 #include <iterator>
61
62 using namespace llvm;
63
64 static cl::opt<int> PageSize("imp-null-check-page-size",
65 cl::desc("The page size of the target in bytes"),
66 cl::init(4096), cl::Hidden);
67
68 static cl::opt<unsigned> MaxInstsToConsider(
69 "imp-null-max-insts-to-consider",
70 cl::desc("The max number of instructions to consider hoisting loads over "
71 "(the algorithm is quadratic over this number)"),
72 cl::Hidden, cl::init(8));
73
74 #define DEBUG_TYPE "implicit-null-checks"
75
76 STATISTIC(NumImplicitNullChecks,
77 "Number of explicit null checks made implicit");
78
79 namespace {
80
81 class ImplicitNullChecks : public MachineFunctionPass {
82 /// Return true if \c computeDependence can process \p MI.
83 static bool canHandle(const MachineInstr *MI);
84
85 /// Helper function for \c computeDependence. Return true if \p A
86 /// and \p B do not have any dependences between them, and can be
87 /// re-ordered without changing program semantics.
88 bool canReorder(const MachineInstr *A, const MachineInstr *B);
89
90 /// A data type for representing the result computed by \c
91 /// computeDependence. States whether it is okay to reorder the
92 /// instruction passed to \c computeDependence with at most one
93 /// dependency.
94 struct DependenceResult {
95 /// Can we actually re-order \p MI with \p Insts (see \c
96 /// computeDependence).
97 bool CanReorder;
98
99 /// If non-None, then an instruction in \p Insts that also must be
100 /// hoisted.
101 Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence;
102
DependenceResult__anonba0fc7a50111::ImplicitNullChecks::DependenceResult103 /*implicit*/ DependenceResult(
104 bool CanReorder,
105 Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence)
106 : CanReorder(CanReorder), PotentialDependence(PotentialDependence) {
107 assert((!PotentialDependence || CanReorder) &&
108 "!CanReorder && PotentialDependence.hasValue() not allowed!");
109 }
110 };
111
112 /// Compute a result for the following question: can \p MI be
113 /// re-ordered from after \p Insts to before it.
114 ///
115 /// \c canHandle should return true for all instructions in \p
116 /// Insts.
117 DependenceResult computeDependence(const MachineInstr *MI,
118 ArrayRef<MachineInstr *> Block);
119
120 /// Represents one null check that can be made implicit.
121 class NullCheck {
122 // The memory operation the null check can be folded into.
123 MachineInstr *MemOperation;
124
125 // The instruction actually doing the null check (Ptr != 0).
126 MachineInstr *CheckOperation;
127
128 // The block the check resides in.
129 MachineBasicBlock *CheckBlock;
130
131 // The block branched to if the pointer is non-null.
132 MachineBasicBlock *NotNullSucc;
133
134 // The block branched to if the pointer is null.
135 MachineBasicBlock *NullSucc;
136
137 // If this is non-null, then MemOperation has a dependency on this
138 // instruction; and it needs to be hoisted to execute before MemOperation.
139 MachineInstr *OnlyDependency;
140
141 public:
NullCheck(MachineInstr * memOperation,MachineInstr * checkOperation,MachineBasicBlock * checkBlock,MachineBasicBlock * notNullSucc,MachineBasicBlock * nullSucc,MachineInstr * onlyDependency)142 explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation,
143 MachineBasicBlock *checkBlock,
144 MachineBasicBlock *notNullSucc,
145 MachineBasicBlock *nullSucc,
146 MachineInstr *onlyDependency)
147 : MemOperation(memOperation), CheckOperation(checkOperation),
148 CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc),
149 OnlyDependency(onlyDependency) {}
150
getMemOperation() const151 MachineInstr *getMemOperation() const { return MemOperation; }
152
getCheckOperation() const153 MachineInstr *getCheckOperation() const { return CheckOperation; }
154
getCheckBlock() const155 MachineBasicBlock *getCheckBlock() const { return CheckBlock; }
156
getNotNullSucc() const157 MachineBasicBlock *getNotNullSucc() const { return NotNullSucc; }
158
getNullSucc() const159 MachineBasicBlock *getNullSucc() const { return NullSucc; }
160
getOnlyDependency() const161 MachineInstr *getOnlyDependency() const { return OnlyDependency; }
162 };
163
164 const TargetInstrInfo *TII = nullptr;
165 const TargetRegisterInfo *TRI = nullptr;
166 AliasAnalysis *AA = nullptr;
167 MachineFrameInfo *MFI = nullptr;
168
169 bool analyzeBlockForNullChecks(MachineBasicBlock &MBB,
170 SmallVectorImpl<NullCheck> &NullCheckList);
171 MachineInstr *insertFaultingInstr(MachineInstr *MI, MachineBasicBlock *MBB,
172 MachineBasicBlock *HandlerMBB);
173 void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList);
174
175 enum AliasResult {
176 AR_NoAlias,
177 AR_MayAlias,
178 AR_WillAliasEverything
179 };
180
181 /// Returns AR_NoAlias if \p MI memory operation does not alias with
182 /// \p PrevMI, AR_MayAlias if they may alias and AR_WillAliasEverything if
183 /// they may alias and any further memory operation may alias with \p PrevMI.
184 AliasResult areMemoryOpsAliased(const MachineInstr &MI,
185 const MachineInstr *PrevMI) const;
186
187 enum SuitabilityResult {
188 SR_Suitable,
189 SR_Unsuitable,
190 SR_Impossible
191 };
192
193 /// Return SR_Suitable if \p MI a memory operation that can be used to
194 /// implicitly null check the value in \p PointerReg, SR_Unsuitable if
195 /// \p MI cannot be used to null check and SR_Impossible if there is
196 /// no sense to continue lookup due to any other instruction will not be able
197 /// to be used. \p PrevInsts is the set of instruction seen since
198 /// the explicit null check on \p PointerReg.
199 SuitabilityResult isSuitableMemoryOp(const MachineInstr &MI,
200 unsigned PointerReg,
201 ArrayRef<MachineInstr *> PrevInsts);
202
203 /// Return true if \p FaultingMI can be hoisted from after the
204 /// instructions in \p InstsSeenSoFar to before them. Set \p Dependence to a
205 /// non-null value if we also need to (and legally can) hoist a depedency.
206 bool canHoistInst(MachineInstr *FaultingMI, unsigned PointerReg,
207 ArrayRef<MachineInstr *> InstsSeenSoFar,
208 MachineBasicBlock *NullSucc, MachineInstr *&Dependence);
209
210 public:
211 static char ID;
212
ImplicitNullChecks()213 ImplicitNullChecks() : MachineFunctionPass(ID) {
214 initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry());
215 }
216
217 bool runOnMachineFunction(MachineFunction &MF) override;
218
getAnalysisUsage(AnalysisUsage & AU) const219 void getAnalysisUsage(AnalysisUsage &AU) const override {
220 AU.addRequired<AAResultsWrapperPass>();
221 MachineFunctionPass::getAnalysisUsage(AU);
222 }
223
getRequiredProperties() const224 MachineFunctionProperties getRequiredProperties() const override {
225 return MachineFunctionProperties().set(
226 MachineFunctionProperties::Property::NoVRegs);
227 }
228 };
229
230 } // end anonymous namespace
231
canHandle(const MachineInstr * MI)232 bool ImplicitNullChecks::canHandle(const MachineInstr *MI) {
233 if (MI->isCall() || MI->mayRaiseFPException() ||
234 MI->hasUnmodeledSideEffects())
235 return false;
236 auto IsRegMask = [](const MachineOperand &MO) { return MO.isRegMask(); };
237 (void)IsRegMask;
238
239 assert(!llvm::any_of(MI->operands(), IsRegMask) &&
240 "Calls were filtered out above!");
241
242 auto IsUnordered = [](MachineMemOperand *MMO) { return MMO->isUnordered(); };
243 return llvm::all_of(MI->memoperands(), IsUnordered);
244 }
245
246 ImplicitNullChecks::DependenceResult
computeDependence(const MachineInstr * MI,ArrayRef<MachineInstr * > Block)247 ImplicitNullChecks::computeDependence(const MachineInstr *MI,
248 ArrayRef<MachineInstr *> Block) {
249 assert(llvm::all_of(Block, canHandle) && "Check this first!");
250 assert(!is_contained(Block, MI) && "Block must be exclusive of MI!");
251
252 Optional<ArrayRef<MachineInstr *>::iterator> Dep;
253
254 for (auto I = Block.begin(), E = Block.end(); I != E; ++I) {
255 if (canReorder(*I, MI))
256 continue;
257
258 if (Dep == None) {
259 // Found one possible dependency, keep track of it.
260 Dep = I;
261 } else {
262 // We found two dependencies, so bail out.
263 return {false, None};
264 }
265 }
266
267 return {true, Dep};
268 }
269
canReorder(const MachineInstr * A,const MachineInstr * B)270 bool ImplicitNullChecks::canReorder(const MachineInstr *A,
271 const MachineInstr *B) {
272 assert(canHandle(A) && canHandle(B) && "Precondition!");
273
274 // canHandle makes sure that we _can_ correctly analyze the dependencies
275 // between A and B here -- for instance, we should not be dealing with heap
276 // load-store dependencies here.
277
278 for (auto MOA : A->operands()) {
279 if (!(MOA.isReg() && MOA.getReg()))
280 continue;
281
282 Register RegA = MOA.getReg();
283 for (auto MOB : B->operands()) {
284 if (!(MOB.isReg() && MOB.getReg()))
285 continue;
286
287 Register RegB = MOB.getReg();
288
289 if (TRI->regsOverlap(RegA, RegB) && (MOA.isDef() || MOB.isDef()))
290 return false;
291 }
292 }
293
294 return true;
295 }
296
runOnMachineFunction(MachineFunction & MF)297 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
298 TII = MF.getSubtarget().getInstrInfo();
299 TRI = MF.getRegInfo().getTargetRegisterInfo();
300 MFI = &MF.getFrameInfo();
301 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
302
303 SmallVector<NullCheck, 16> NullCheckList;
304
305 for (auto &MBB : MF)
306 analyzeBlockForNullChecks(MBB, NullCheckList);
307
308 if (!NullCheckList.empty())
309 rewriteNullChecks(NullCheckList);
310
311 return !NullCheckList.empty();
312 }
313
314 // Return true if any register aliasing \p Reg is live-in into \p MBB.
AnyAliasLiveIn(const TargetRegisterInfo * TRI,MachineBasicBlock * MBB,unsigned Reg)315 static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI,
316 MachineBasicBlock *MBB, unsigned Reg) {
317 for (MCRegAliasIterator AR(Reg, TRI, /*IncludeSelf*/ true); AR.isValid();
318 ++AR)
319 if (MBB->isLiveIn(*AR))
320 return true;
321 return false;
322 }
323
324 ImplicitNullChecks::AliasResult
areMemoryOpsAliased(const MachineInstr & MI,const MachineInstr * PrevMI) const325 ImplicitNullChecks::areMemoryOpsAliased(const MachineInstr &MI,
326 const MachineInstr *PrevMI) const {
327 // If it is not memory access, skip the check.
328 if (!(PrevMI->mayStore() || PrevMI->mayLoad()))
329 return AR_NoAlias;
330 // Load-Load may alias
331 if (!(MI.mayStore() || PrevMI->mayStore()))
332 return AR_NoAlias;
333 // We lost info, conservatively alias. If it was store then no sense to
334 // continue because we won't be able to check against it further.
335 if (MI.memoperands_empty())
336 return MI.mayStore() ? AR_WillAliasEverything : AR_MayAlias;
337 if (PrevMI->memoperands_empty())
338 return PrevMI->mayStore() ? AR_WillAliasEverything : AR_MayAlias;
339
340 for (MachineMemOperand *MMO1 : MI.memoperands()) {
341 // MMO1 should have a value due it comes from operation we'd like to use
342 // as implicit null check.
343 assert(MMO1->getValue() && "MMO1 should have a Value!");
344 for (MachineMemOperand *MMO2 : PrevMI->memoperands()) {
345 if (const PseudoSourceValue *PSV = MMO2->getPseudoValue()) {
346 if (PSV->mayAlias(MFI))
347 return AR_MayAlias;
348 continue;
349 }
350 llvm::AliasResult AAResult =
351 AA->alias(MemoryLocation(MMO1->getValue(), LocationSize::unknown(),
352 MMO1->getAAInfo()),
353 MemoryLocation(MMO2->getValue(), LocationSize::unknown(),
354 MMO2->getAAInfo()));
355 if (AAResult != NoAlias)
356 return AR_MayAlias;
357 }
358 }
359 return AR_NoAlias;
360 }
361
362 ImplicitNullChecks::SuitabilityResult
isSuitableMemoryOp(const MachineInstr & MI,unsigned PointerReg,ArrayRef<MachineInstr * > PrevInsts)363 ImplicitNullChecks::isSuitableMemoryOp(const MachineInstr &MI,
364 unsigned PointerReg,
365 ArrayRef<MachineInstr *> PrevInsts) {
366 int64_t Offset;
367 const MachineOperand *BaseOp;
368
369 if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, TRI) ||
370 !BaseOp->isReg() || BaseOp->getReg() != PointerReg)
371 return SR_Unsuitable;
372
373 // We want the mem access to be issued at a sane offset from PointerReg,
374 // so that if PointerReg is null then the access reliably page faults.
375 if (!(MI.mayLoadOrStore() && !MI.isPredicable() &&
376 -PageSize < Offset && Offset < PageSize))
377 return SR_Unsuitable;
378
379 // Finally, check whether the current memory access aliases with previous one.
380 for (auto *PrevMI : PrevInsts) {
381 AliasResult AR = areMemoryOpsAliased(MI, PrevMI);
382 if (AR == AR_WillAliasEverything)
383 return SR_Impossible;
384 if (AR == AR_MayAlias)
385 return SR_Unsuitable;
386 }
387 return SR_Suitable;
388 }
389
canHoistInst(MachineInstr * FaultingMI,unsigned PointerReg,ArrayRef<MachineInstr * > InstsSeenSoFar,MachineBasicBlock * NullSucc,MachineInstr * & Dependence)390 bool ImplicitNullChecks::canHoistInst(MachineInstr *FaultingMI,
391 unsigned PointerReg,
392 ArrayRef<MachineInstr *> InstsSeenSoFar,
393 MachineBasicBlock *NullSucc,
394 MachineInstr *&Dependence) {
395 auto DepResult = computeDependence(FaultingMI, InstsSeenSoFar);
396 if (!DepResult.CanReorder)
397 return false;
398
399 if (!DepResult.PotentialDependence) {
400 Dependence = nullptr;
401 return true;
402 }
403
404 auto DependenceItr = *DepResult.PotentialDependence;
405 auto *DependenceMI = *DependenceItr;
406
407 // We don't want to reason about speculating loads. Note -- at this point
408 // we should have already filtered out all of the other non-speculatable
409 // things, like calls and stores.
410 // We also do not want to hoist stores because it might change the memory
411 // while the FaultingMI may result in faulting.
412 assert(canHandle(DependenceMI) && "Should never have reached here!");
413 if (DependenceMI->mayLoadOrStore())
414 return false;
415
416 for (auto &DependenceMO : DependenceMI->operands()) {
417 if (!(DependenceMO.isReg() && DependenceMO.getReg()))
418 continue;
419
420 // Make sure that we won't clobber any live ins to the sibling block by
421 // hoisting Dependency. For instance, we can't hoist INST to before the
422 // null check (even if it safe, and does not violate any dependencies in
423 // the non_null_block) if %rdx is live in to _null_block.
424 //
425 // test %rcx, %rcx
426 // je _null_block
427 // _non_null_block:
428 // %rdx = INST
429 // ...
430 //
431 // This restriction does not apply to the faulting load inst because in
432 // case the pointer loaded from is in the null page, the load will not
433 // semantically execute, and affect machine state. That is, if the load
434 // was loading into %rax and it faults, the value of %rax should stay the
435 // same as it would have been had the load not have executed and we'd have
436 // branched to NullSucc directly.
437 if (AnyAliasLiveIn(TRI, NullSucc, DependenceMO.getReg()))
438 return false;
439
440 // The Dependency can't be re-defining the base register -- then we won't
441 // get the memory operation on the address we want. This is already
442 // checked in \c IsSuitableMemoryOp.
443 assert(!(DependenceMO.isDef() &&
444 TRI->regsOverlap(DependenceMO.getReg(), PointerReg)) &&
445 "Should have been checked before!");
446 }
447
448 auto DepDepResult =
449 computeDependence(DependenceMI, {InstsSeenSoFar.begin(), DependenceItr});
450
451 if (!DepDepResult.CanReorder || DepDepResult.PotentialDependence)
452 return false;
453
454 Dependence = DependenceMI;
455 return true;
456 }
457
458 /// Analyze MBB to check if its terminating branch can be turned into an
459 /// implicit null check. If yes, append a description of the said null check to
460 /// NullCheckList and return true, else return false.
analyzeBlockForNullChecks(MachineBasicBlock & MBB,SmallVectorImpl<NullCheck> & NullCheckList)461 bool ImplicitNullChecks::analyzeBlockForNullChecks(
462 MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
463 using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
464
465 MDNode *BranchMD = nullptr;
466 if (auto *BB = MBB.getBasicBlock())
467 BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit);
468
469 if (!BranchMD)
470 return false;
471
472 MachineBranchPredicate MBP;
473
474 if (TII->analyzeBranchPredicate(MBB, MBP, true))
475 return false;
476
477 // Is the predicate comparing an integer to zero?
478 if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
479 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
480 MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
481 return false;
482
483 // If we cannot erase the test instruction itself, then making the null check
484 // implicit does not buy us much.
485 if (!MBP.SingleUseCondition)
486 return false;
487
488 MachineBasicBlock *NotNullSucc, *NullSucc;
489
490 if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
491 NotNullSucc = MBP.TrueDest;
492 NullSucc = MBP.FalseDest;
493 } else {
494 NotNullSucc = MBP.FalseDest;
495 NullSucc = MBP.TrueDest;
496 }
497
498 // We handle the simplest case for now. We can potentially do better by using
499 // the machine dominator tree.
500 if (NotNullSucc->pred_size() != 1)
501 return false;
502
503 // To prevent the invalid transformation of the following code:
504 //
505 // mov %rax, %rcx
506 // test %rax, %rax
507 // %rax = ...
508 // je throw_npe
509 // mov(%rcx), %r9
510 // mov(%rax), %r10
511 //
512 // into:
513 //
514 // mov %rax, %rcx
515 // %rax = ....
516 // faulting_load_op("movl (%rax), %r10", throw_npe)
517 // mov(%rcx), %r9
518 //
519 // we must ensure that there are no instructions between the 'test' and
520 // conditional jump that modify %rax.
521 const Register PointerReg = MBP.LHS.getReg();
522
523 assert(MBP.ConditionDef->getParent() == &MBB && "Should be in basic block");
524
525 for (auto I = MBB.rbegin(); MBP.ConditionDef != &*I; ++I)
526 if (I->modifiesRegister(PointerReg, TRI))
527 return false;
528
529 // Starting with a code fragment like:
530 //
531 // test %rax, %rax
532 // jne LblNotNull
533 //
534 // LblNull:
535 // callq throw_NullPointerException
536 //
537 // LblNotNull:
538 // Inst0
539 // Inst1
540 // ...
541 // Def = Load (%rax + <offset>)
542 // ...
543 //
544 //
545 // we want to end up with
546 //
547 // Def = FaultingLoad (%rax + <offset>), LblNull
548 // jmp LblNotNull ;; explicit or fallthrough
549 //
550 // LblNotNull:
551 // Inst0
552 // Inst1
553 // ...
554 //
555 // LblNull:
556 // callq throw_NullPointerException
557 //
558 //
559 // To see why this is legal, consider the two possibilities:
560 //
561 // 1. %rax is null: since we constrain <offset> to be less than PageSize, the
562 // load instruction dereferences the null page, causing a segmentation
563 // fault.
564 //
565 // 2. %rax is not null: in this case we know that the load cannot fault, as
566 // otherwise the load would've faulted in the original program too and the
567 // original program would've been undefined.
568 //
569 // This reasoning cannot be extended to justify hoisting through arbitrary
570 // control flow. For instance, in the example below (in pseudo-C)
571 //
572 // if (ptr == null) { throw_npe(); unreachable; }
573 // if (some_cond) { return 42; }
574 // v = ptr->field; // LD
575 // ...
576 //
577 // we cannot (without code duplication) use the load marked "LD" to null check
578 // ptr -- clause (2) above does not apply in this case. In the above program
579 // the safety of ptr->field can be dependent on some_cond; and, for instance,
580 // ptr could be some non-null invalid reference that never gets loaded from
581 // because some_cond is always true.
582
583 SmallVector<MachineInstr *, 8> InstsSeenSoFar;
584
585 for (auto &MI : *NotNullSucc) {
586 if (!canHandle(&MI) || InstsSeenSoFar.size() >= MaxInstsToConsider)
587 return false;
588
589 MachineInstr *Dependence;
590 SuitabilityResult SR = isSuitableMemoryOp(MI, PointerReg, InstsSeenSoFar);
591 if (SR == SR_Impossible)
592 return false;
593 if (SR == SR_Suitable &&
594 canHoistInst(&MI, PointerReg, InstsSeenSoFar, NullSucc, Dependence)) {
595 NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc,
596 NullSucc, Dependence);
597 return true;
598 }
599
600 // If MI re-defines the PointerReg then we cannot move further.
601 if (llvm::any_of(MI.operands(), [&](MachineOperand &MO) {
602 return MO.isReg() && MO.getReg() && MO.isDef() &&
603 TRI->regsOverlap(MO.getReg(), PointerReg);
604 }))
605 return false;
606 InstsSeenSoFar.push_back(&MI);
607 }
608
609 return false;
610 }
611
612 /// Wrap a machine instruction, MI, into a FAULTING machine instruction.
613 /// The FAULTING instruction does the same load/store as MI
614 /// (defining the same register), and branches to HandlerMBB if the mem access
615 /// faults. The FAULTING instruction is inserted at the end of MBB.
insertFaultingInstr(MachineInstr * MI,MachineBasicBlock * MBB,MachineBasicBlock * HandlerMBB)616 MachineInstr *ImplicitNullChecks::insertFaultingInstr(
617 MachineInstr *MI, MachineBasicBlock *MBB, MachineBasicBlock *HandlerMBB) {
618 const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for
619 // all targets.
620
621 DebugLoc DL;
622 unsigned NumDefs = MI->getDesc().getNumDefs();
623 assert(NumDefs <= 1 && "other cases unhandled!");
624
625 unsigned DefReg = NoRegister;
626 if (NumDefs != 0) {
627 DefReg = MI->getOperand(0).getReg();
628 assert(NumDefs == 1 && "expected exactly one def!");
629 }
630
631 FaultMaps::FaultKind FK;
632 if (MI->mayLoad())
633 FK =
634 MI->mayStore() ? FaultMaps::FaultingLoadStore : FaultMaps::FaultingLoad;
635 else
636 FK = FaultMaps::FaultingStore;
637
638 auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_OP), DefReg)
639 .addImm(FK)
640 .addMBB(HandlerMBB)
641 .addImm(MI->getOpcode());
642
643 for (auto &MO : MI->uses()) {
644 if (MO.isReg()) {
645 MachineOperand NewMO = MO;
646 if (MO.isUse()) {
647 NewMO.setIsKill(false);
648 } else {
649 assert(MO.isDef() && "Expected def or use");
650 NewMO.setIsDead(false);
651 }
652 MIB.add(NewMO);
653 } else {
654 MIB.add(MO);
655 }
656 }
657
658 MIB.setMemRefs(MI->memoperands());
659
660 return MIB;
661 }
662
663 /// Rewrite the null checks in NullCheckList into implicit null checks.
rewriteNullChecks(ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList)664 void ImplicitNullChecks::rewriteNullChecks(
665 ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
666 DebugLoc DL;
667
668 for (auto &NC : NullCheckList) {
669 // Remove the conditional branch dependent on the null check.
670 unsigned BranchesRemoved = TII->removeBranch(*NC.getCheckBlock());
671 (void)BranchesRemoved;
672 assert(BranchesRemoved > 0 && "expected at least one branch!");
673
674 if (auto *DepMI = NC.getOnlyDependency()) {
675 DepMI->removeFromParent();
676 NC.getCheckBlock()->insert(NC.getCheckBlock()->end(), DepMI);
677 }
678
679 // Insert a faulting instruction where the conditional branch was
680 // originally. We check earlier ensures that this bit of code motion
681 // is legal. We do not touch the successors list for any basic block
682 // since we haven't changed control flow, we've just made it implicit.
683 MachineInstr *FaultingInstr = insertFaultingInstr(
684 NC.getMemOperation(), NC.getCheckBlock(), NC.getNullSucc());
685 // Now the values defined by MemOperation, if any, are live-in of
686 // the block of MemOperation.
687 // The original operation may define implicit-defs alongside
688 // the value.
689 MachineBasicBlock *MBB = NC.getMemOperation()->getParent();
690 for (const MachineOperand &MO : FaultingInstr->operands()) {
691 if (!MO.isReg() || !MO.isDef())
692 continue;
693 Register Reg = MO.getReg();
694 if (!Reg || MBB->isLiveIn(Reg))
695 continue;
696 MBB->addLiveIn(Reg);
697 }
698
699 if (auto *DepMI = NC.getOnlyDependency()) {
700 for (auto &MO : DepMI->operands()) {
701 if (!MO.isReg() || !MO.getReg() || !MO.isDef() || MO.isDead())
702 continue;
703 if (!NC.getNotNullSucc()->isLiveIn(MO.getReg()))
704 NC.getNotNullSucc()->addLiveIn(MO.getReg());
705 }
706 }
707
708 NC.getMemOperation()->eraseFromParent();
709 NC.getCheckOperation()->eraseFromParent();
710
711 // Insert an *unconditional* branch to not-null successor.
712 TII->insertBranch(*NC.getCheckBlock(), NC.getNotNullSucc(), nullptr,
713 /*Cond=*/None, DL);
714
715 NumImplicitNullChecks++;
716 }
717 }
718
719 char ImplicitNullChecks::ID = 0;
720
721 char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID;
722
723 INITIALIZE_PASS_BEGIN(ImplicitNullChecks, DEBUG_TYPE,
724 "Implicit null checks", false, false)
725 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
726 INITIALIZE_PASS_END(ImplicitNullChecks, DEBUG_TYPE,
727 "Implicit null checks", false, false)
728