1 //===-- ImplicitNullChecks.cpp - Fold null checks into memory accesses ----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass turns explicit null checks of the form
19 // faulting_load_op("movl (%r10), %esi", throw_npe)
22 // With the help of a runtime that understands the .fault_maps section,
23 // faulting_load_op branches to throw_npe if executing movl (%r10), %esi incurs
25 // Store and LoadStore are also supported.
27 //===----------------------------------------------------------------------===//
29 #include "llvm/ADT/DenseSet.h"
30 #include "llvm/ADT/SmallVector.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/Analysis/AliasAnalysis.h"
33 #include "llvm/CodeGen/FaultMaps.h"
34 #include "llvm/CodeGen/Passes.h"
35 #include "llvm/CodeGen/MachineFunction.h"
36 #include "llvm/CodeGen/MachineMemOperand.h"
37 #include "llvm/CodeGen/MachineOperand.h"
38 #include "llvm/CodeGen/MachineFunctionPass.h"
39 #include "llvm/CodeGen/MachineInstrBuilder.h"
40 #include "llvm/CodeGen/MachineRegisterInfo.h"
41 #include "llvm/CodeGen/MachineModuleInfo.h"
42 #include "llvm/IR/BasicBlock.h"
43 #include "llvm/IR/Instruction.h"
44 #include "llvm/IR/LLVMContext.h"
45 #include "llvm/Support/CommandLine.h"
46 #include "llvm/Support/Debug.h"
47 #include "llvm/Target/TargetSubtargetInfo.h"
48 #include "llvm/Target/TargetInstrInfo.h"
52 static cl::opt<int> PageSize("imp-null-check-page-size",
53 cl::desc("The page size of the target in bytes"),
56 static cl::opt<unsigned> MaxInstsToConsider(
57 "imp-null-max-insts-to-consider",
58 cl::desc("The max number of instructions to consider hoisting loads over "
59 "(the algorithm is quadratic over this number)"),
62 #define DEBUG_TYPE "implicit-null-checks"
64 STATISTIC(NumImplicitNullChecks,
65 "Number of explicit null checks made implicit");
69 class ImplicitNullChecks : public MachineFunctionPass {
70 /// Return true if \c computeDependence can process \p MI.
71 static bool canHandle(const MachineInstr *MI);
73 /// Helper function for \c computeDependence. Return true if \p A
74 /// and \p B do not have any dependences between them, and can be
75 /// re-ordered without changing program semantics.
76 bool canReorder(const MachineInstr *A, const MachineInstr *B);
78 /// A data type for representing the result computed by \c
79 /// computeDependence. States whether it is okay to reorder the
80 /// instruction passed to \c computeDependence with at most one
82 struct DependenceResult {
83 /// Can we actually re-order \p MI with \p Insts (see \c
84 /// computeDependence).
87 /// If non-None, then an instruction in \p Insts that also must be
89 Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence;
91 /*implicit*/ DependenceResult(
93 Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence)
94 : CanReorder(CanReorder), PotentialDependence(PotentialDependence) {
95 assert((!PotentialDependence || CanReorder) &&
96 "!CanReorder && PotentialDependence.hasValue() not allowed!");
100 /// Compute a result for the following question: can \p MI be
101 /// re-ordered from after \p Insts to before it.
103 /// \c canHandle should return true for all instructions in \p
105 DependenceResult computeDependence(const MachineInstr *MI,
106 ArrayRef<MachineInstr *> Insts);
108 /// Represents one null check that can be made implicit.
110 // The memory operation the null check can be folded into.
111 MachineInstr *MemOperation;
113 // The instruction actually doing the null check (Ptr != 0).
114 MachineInstr *CheckOperation;
116 // The block the check resides in.
117 MachineBasicBlock *CheckBlock;
119 // The block branched to if the pointer is non-null.
120 MachineBasicBlock *NotNullSucc;
122 // The block branched to if the pointer is null.
123 MachineBasicBlock *NullSucc;
125 // If this is non-null, then MemOperation has a dependency on on this
126 // instruction; and it needs to be hoisted to execute before MemOperation.
127 MachineInstr *OnlyDependency;
130 explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation,
131 MachineBasicBlock *checkBlock,
132 MachineBasicBlock *notNullSucc,
133 MachineBasicBlock *nullSucc,
134 MachineInstr *onlyDependency)
135 : MemOperation(memOperation), CheckOperation(checkOperation),
136 CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc),
137 OnlyDependency(onlyDependency) {}
139 MachineInstr *getMemOperation() const { return MemOperation; }
141 MachineInstr *getCheckOperation() const { return CheckOperation; }
143 MachineBasicBlock *getCheckBlock() const { return CheckBlock; }
145 MachineBasicBlock *getNotNullSucc() const { return NotNullSucc; }
147 MachineBasicBlock *getNullSucc() const { return NullSucc; }
149 MachineInstr *getOnlyDependency() const { return OnlyDependency; }
152 const TargetInstrInfo *TII = nullptr;
153 const TargetRegisterInfo *TRI = nullptr;
154 AliasAnalysis *AA = nullptr;
155 MachineModuleInfo *MMI = nullptr;
156 MachineFrameInfo *MFI = nullptr;
158 bool analyzeBlockForNullChecks(MachineBasicBlock &MBB,
159 SmallVectorImpl<NullCheck> &NullCheckList);
160 MachineInstr *insertFaultingInstr(MachineInstr *MI, MachineBasicBlock *MBB,
161 MachineBasicBlock *HandlerMBB);
162 void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList);
167 AR_WillAliasEverything
169 /// Returns AR_NoAlias if \p MI memory operation does not alias with
170 /// \p PrevMI, AR_MayAlias if they may alias and AR_WillAliasEverything if
171 /// they may alias and any further memory operation may alias with \p PrevMI.
172 AliasResult areMemoryOpsAliased(MachineInstr &MI, MachineInstr *PrevMI);
174 enum SuitabilityResult {
179 /// Return SR_Suitable if \p MI a memory operation that can be used to
180 /// implicitly null check the value in \p PointerReg, SR_Unsuitable if
181 /// \p MI cannot be used to null check and SR_Impossible if there is
182 /// no sense to continue lookup due to any other instruction will not be able
183 /// to be used. \p PrevInsts is the set of instruction seen since
184 /// the explicit null check on \p PointerReg.
185 SuitabilityResult isSuitableMemoryOp(MachineInstr &MI, unsigned PointerReg,
186 ArrayRef<MachineInstr *> PrevInsts);
188 /// Return true if \p FaultingMI can be hoisted from after the the
189 /// instructions in \p InstsSeenSoFar to before them. Set \p Dependence to a
190 /// non-null value if we also need to (and legally can) hoist a depedency.
191 bool canHoistInst(MachineInstr *FaultingMI, unsigned PointerReg,
192 ArrayRef<MachineInstr *> InstsSeenSoFar,
193 MachineBasicBlock *NullSucc, MachineInstr *&Dependence);
198 ImplicitNullChecks() : MachineFunctionPass(ID) {
199 initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry());
202 bool runOnMachineFunction(MachineFunction &MF) override;
203 void getAnalysisUsage(AnalysisUsage &AU) const override {
204 AU.addRequired<AAResultsWrapperPass>();
205 MachineFunctionPass::getAnalysisUsage(AU);
208 MachineFunctionProperties getRequiredProperties() const override {
209 return MachineFunctionProperties().set(
210 MachineFunctionProperties::Property::NoVRegs);
216 bool ImplicitNullChecks::canHandle(const MachineInstr *MI) {
217 if (MI->isCall() || MI->hasUnmodeledSideEffects())
219 auto IsRegMask = [](const MachineOperand &MO) { return MO.isRegMask(); };
222 assert(!llvm::any_of(MI->operands(), IsRegMask) &&
223 "Calls were filtered out above!");
225 auto IsUnordered = [](MachineMemOperand *MMO) { return MMO->isUnordered(); };
226 return llvm::all_of(MI->memoperands(), IsUnordered);
229 ImplicitNullChecks::DependenceResult
230 ImplicitNullChecks::computeDependence(const MachineInstr *MI,
231 ArrayRef<MachineInstr *> Block) {
232 assert(llvm::all_of(Block, canHandle) && "Check this first!");
233 assert(!llvm::is_contained(Block, MI) && "Block must be exclusive of MI!");
235 Optional<ArrayRef<MachineInstr *>::iterator> Dep;
237 for (auto I = Block.begin(), E = Block.end(); I != E; ++I) {
238 if (canReorder(*I, MI))
242 // Found one possible dependency, keep track of it.
245 // We found two dependencies, so bail out.
246 return {false, None};
253 bool ImplicitNullChecks::canReorder(const MachineInstr *A,
254 const MachineInstr *B) {
255 assert(canHandle(A) && canHandle(B) && "Precondition!");
257 // canHandle makes sure that we _can_ correctly analyze the dependencies
258 // between A and B here -- for instance, we should not be dealing with heap
259 // load-store dependencies here.
261 for (auto MOA : A->operands()) {
262 if (!(MOA.isReg() && MOA.getReg()))
265 unsigned RegA = MOA.getReg();
266 for (auto MOB : B->operands()) {
267 if (!(MOB.isReg() && MOB.getReg()))
270 unsigned RegB = MOB.getReg();
272 if (TRI->regsOverlap(RegA, RegB) && (MOA.isDef() || MOB.isDef()))
280 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
281 TII = MF.getSubtarget().getInstrInfo();
282 TRI = MF.getRegInfo().getTargetRegisterInfo();
284 MFI = &MF.getFrameInfo();
285 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
287 SmallVector<NullCheck, 16> NullCheckList;
290 analyzeBlockForNullChecks(MBB, NullCheckList);
292 if (!NullCheckList.empty())
293 rewriteNullChecks(NullCheckList);
295 return !NullCheckList.empty();
298 // Return true if any register aliasing \p Reg is live-in into \p MBB.
299 static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI,
300 MachineBasicBlock *MBB, unsigned Reg) {
301 for (MCRegAliasIterator AR(Reg, TRI, /*IncludeSelf*/ true); AR.isValid();
303 if (MBB->isLiveIn(*AR))
308 ImplicitNullChecks::AliasResult
309 ImplicitNullChecks::areMemoryOpsAliased(MachineInstr &MI,
310 MachineInstr *PrevMI) {
311 // If it is not memory access, skip the check.
312 if (!(PrevMI->mayStore() || PrevMI->mayLoad()))
314 // Load-Load may alias
315 if (!(MI.mayStore() || PrevMI->mayStore()))
317 // We lost info, conservatively alias. If it was store then no sense to
318 // continue because we won't be able to check against it further.
319 if (MI.memoperands_empty())
320 return MI.mayStore() ? AR_WillAliasEverything : AR_MayAlias;
321 if (PrevMI->memoperands_empty())
322 return PrevMI->mayStore() ? AR_WillAliasEverything : AR_MayAlias;
324 for (MachineMemOperand *MMO1 : MI.memoperands()) {
325 // MMO1 should have a value due it comes from operation we'd like to use
326 // as implicit null check.
327 assert(MMO1->getValue() && "MMO1 should have a Value!");
328 for (MachineMemOperand *MMO2 : PrevMI->memoperands()) {
329 if (const PseudoSourceValue *PSV = MMO2->getPseudoValue()) {
330 if (PSV->mayAlias(MFI))
334 llvm::AliasResult AAResult = AA->alias(
335 MemoryLocation(MMO1->getValue(), MemoryLocation::UnknownSize,
337 MemoryLocation(MMO2->getValue(), MemoryLocation::UnknownSize,
339 if (AAResult != NoAlias)
346 ImplicitNullChecks::SuitabilityResult
347 ImplicitNullChecks::isSuitableMemoryOp(MachineInstr &MI, unsigned PointerReg,
348 ArrayRef<MachineInstr *> PrevInsts) {
352 if (!TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI) ||
353 BaseReg != PointerReg)
354 return SR_Unsuitable;
356 // We want the mem access to be issued at a sane offset from PointerReg,
357 // so that if PointerReg is null then the access reliably page faults.
358 if (!((MI.mayLoad() || MI.mayStore()) && !MI.isPredicable() &&
360 return SR_Unsuitable;
362 // Finally, we need to make sure that the access instruction actually is
363 // accessing from PointerReg, and there isn't some re-definition of PointerReg
364 // between the compare and the memory access.
365 // If PointerReg has been redefined before then there is no sense to continue
366 // lookup due to this condition will fail for any further instruction.
367 SuitabilityResult Suitable = SR_Suitable;
368 for (auto *PrevMI : PrevInsts)
369 for (auto &PrevMO : PrevMI->operands()) {
370 if (PrevMO.isReg() && PrevMO.getReg() && PrevMO.isDef() &&
371 TRI->regsOverlap(PrevMO.getReg(), PointerReg))
372 return SR_Impossible;
374 // Check whether the current memory access aliases with previous one.
375 // If we already found that it aliases then no need to continue.
376 // But we continue base pointer check as it can result in SR_Impossible.
377 if (Suitable == SR_Suitable) {
378 AliasResult AR = areMemoryOpsAliased(MI, PrevMI);
379 if (AR == AR_WillAliasEverything)
380 return SR_Impossible;
381 if (AR == AR_MayAlias)
382 Suitable = SR_Unsuitable;
388 bool ImplicitNullChecks::canHoistInst(MachineInstr *FaultingMI,
390 ArrayRef<MachineInstr *> InstsSeenSoFar,
391 MachineBasicBlock *NullSucc,
392 MachineInstr *&Dependence) {
393 auto DepResult = computeDependence(FaultingMI, InstsSeenSoFar);
394 if (!DepResult.CanReorder)
397 if (!DepResult.PotentialDependence) {
398 Dependence = nullptr;
402 auto DependenceItr = *DepResult.PotentialDependence;
403 auto *DependenceMI = *DependenceItr;
405 // We don't want to reason about speculating loads. Note -- at this point
406 // we should have already filtered out all of the other non-speculatable
407 // things, like calls and stores.
408 assert(canHandle(DependenceMI) && "Should never have reached here!");
409 if (DependenceMI->mayLoad())
412 for (auto &DependenceMO : DependenceMI->operands()) {
413 if (!(DependenceMO.isReg() && DependenceMO.getReg()))
416 // Make sure that we won't clobber any live ins to the sibling block by
417 // hoisting Dependency. For instance, we can't hoist INST to before the
418 // null check (even if it safe, and does not violate any dependencies in
419 // the non_null_block) if %rdx is live in to _null_block.
427 // This restriction does not apply to the faulting load inst because in
428 // case the pointer loaded from is in the null page, the load will not
429 // semantically execute, and affect machine state. That is, if the load
430 // was loading into %rax and it faults, the value of %rax should stay the
431 // same as it would have been had the load not have executed and we'd have
432 // branched to NullSucc directly.
433 if (AnyAliasLiveIn(TRI, NullSucc, DependenceMO.getReg()))
436 // The Dependency can't be re-defining the base register -- then we won't
437 // get the memory operation on the address we want. This is already
438 // checked in \c IsSuitableMemoryOp.
439 assert(!(DependenceMO.isDef() &&
440 TRI->regsOverlap(DependenceMO.getReg(), PointerReg)) &&
441 "Should have been checked before!");
445 computeDependence(DependenceMI, {InstsSeenSoFar.begin(), DependenceItr});
447 if (!DepDepResult.CanReorder || DepDepResult.PotentialDependence)
450 Dependence = DependenceMI;
454 /// Analyze MBB to check if its terminating branch can be turned into an
455 /// implicit null check. If yes, append a description of the said null check to
456 /// NullCheckList and return true, else return false.
457 bool ImplicitNullChecks::analyzeBlockForNullChecks(
458 MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
459 typedef TargetInstrInfo::MachineBranchPredicate MachineBranchPredicate;
461 MDNode *BranchMD = nullptr;
462 if (auto *BB = MBB.getBasicBlock())
463 BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit);
468 MachineBranchPredicate MBP;
470 if (TII->analyzeBranchPredicate(MBB, MBP, true))
473 // Is the predicate comparing an integer to zero?
474 if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
475 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
476 MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
479 // If we cannot erase the test instruction itself, then making the null check
480 // implicit does not buy us much.
481 if (!MBP.SingleUseCondition)
484 MachineBasicBlock *NotNullSucc, *NullSucc;
486 if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
487 NotNullSucc = MBP.TrueDest;
488 NullSucc = MBP.FalseDest;
490 NotNullSucc = MBP.FalseDest;
491 NullSucc = MBP.TrueDest;
494 // We handle the simplest case for now. We can potentially do better by using
495 // the machine dominator tree.
496 if (NotNullSucc->pred_size() != 1)
499 // Starting with a code fragment like:
505 // callq throw_NullPointerException
511 // Def = Load (%RAX + <offset>)
515 // we want to end up with
517 // Def = FaultingLoad (%RAX + <offset>), LblNull
518 // jmp LblNotNull ;; explicit or fallthrough
526 // callq throw_NullPointerException
529 // To see why this is legal, consider the two possibilities:
531 // 1. %RAX is null: since we constrain <offset> to be less than PageSize, the
532 // load instruction dereferences the null page, causing a segmentation
535 // 2. %RAX is not null: in this case we know that the load cannot fault, as
536 // otherwise the load would've faulted in the original program too and the
537 // original program would've been undefined.
539 // This reasoning cannot be extended to justify hoisting through arbitrary
540 // control flow. For instance, in the example below (in pseudo-C)
542 // if (ptr == null) { throw_npe(); unreachable; }
543 // if (some_cond) { return 42; }
544 // v = ptr->field; // LD
547 // we cannot (without code duplication) use the load marked "LD" to null check
548 // ptr -- clause (2) above does not apply in this case. In the above program
549 // the safety of ptr->field can be dependent on some_cond; and, for instance,
550 // ptr could be some non-null invalid reference that never gets loaded from
551 // because some_cond is always true.
553 const unsigned PointerReg = MBP.LHS.getReg();
555 SmallVector<MachineInstr *, 8> InstsSeenSoFar;
557 for (auto &MI : *NotNullSucc) {
558 if (!canHandle(&MI) || InstsSeenSoFar.size() >= MaxInstsToConsider)
561 MachineInstr *Dependence;
562 SuitabilityResult SR = isSuitableMemoryOp(MI, PointerReg, InstsSeenSoFar);
563 if (SR == SR_Impossible)
565 if (SR == SR_Suitable &&
566 canHoistInst(&MI, PointerReg, InstsSeenSoFar, NullSucc, Dependence)) {
567 NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc,
568 NullSucc, Dependence);
572 InstsSeenSoFar.push_back(&MI);
578 /// Wrap a machine instruction, MI, into a FAULTING machine instruction.
579 /// The FAULTING instruction does the same load/store as MI
580 /// (defining the same register), and branches to HandlerMBB if the mem access
581 /// faults. The FAULTING instruction is inserted at the end of MBB.
582 MachineInstr *ImplicitNullChecks::insertFaultingInstr(
583 MachineInstr *MI, MachineBasicBlock *MBB, MachineBasicBlock *HandlerMBB) {
584 const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for
588 unsigned NumDefs = MI->getDesc().getNumDefs();
589 assert(NumDefs <= 1 && "other cases unhandled!");
591 unsigned DefReg = NoRegister;
593 DefReg = MI->defs().begin()->getReg();
594 assert(std::distance(MI->defs().begin(), MI->defs().end()) == 1 &&
595 "expected exactly one def!");
598 FaultMaps::FaultKind FK;
601 MI->mayStore() ? FaultMaps::FaultingLoadStore : FaultMaps::FaultingLoad;
603 FK = FaultMaps::FaultingStore;
605 auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_OP), DefReg)
608 .addImm(MI->getOpcode());
610 for (auto &MO : MI->uses()) {
612 MachineOperand NewMO = MO;
614 NewMO.setIsKill(false);
616 assert(MO.isDef() && "Expected def or use");
617 NewMO.setIsDead(false);
625 MIB.setMemRefs(MI->memoperands_begin(), MI->memoperands_end());
630 /// Rewrite the null checks in NullCheckList into implicit null checks.
631 void ImplicitNullChecks::rewriteNullChecks(
632 ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
635 for (auto &NC : NullCheckList) {
636 // Remove the conditional branch dependent on the null check.
637 unsigned BranchesRemoved = TII->removeBranch(*NC.getCheckBlock());
638 (void)BranchesRemoved;
639 assert(BranchesRemoved > 0 && "expected at least one branch!");
641 if (auto *DepMI = NC.getOnlyDependency()) {
642 DepMI->removeFromParent();
643 NC.getCheckBlock()->insert(NC.getCheckBlock()->end(), DepMI);
646 // Insert a faulting instruction where the conditional branch was
647 // originally. We check earlier ensures that this bit of code motion
648 // is legal. We do not touch the successors list for any basic block
649 // since we haven't changed control flow, we've just made it implicit.
650 MachineInstr *FaultingInstr = insertFaultingInstr(
651 NC.getMemOperation(), NC.getCheckBlock(), NC.getNullSucc());
652 // Now the values defined by MemOperation, if any, are live-in of
653 // the block of MemOperation.
654 // The original operation may define implicit-defs alongside
656 MachineBasicBlock *MBB = NC.getMemOperation()->getParent();
657 for (const MachineOperand &MO : FaultingInstr->operands()) {
658 if (!MO.isReg() || !MO.isDef())
660 unsigned Reg = MO.getReg();
661 if (!Reg || MBB->isLiveIn(Reg))
666 if (auto *DepMI = NC.getOnlyDependency()) {
667 for (auto &MO : DepMI->operands()) {
668 if (!MO.isReg() || !MO.getReg() || !MO.isDef())
670 if (!NC.getNotNullSucc()->isLiveIn(MO.getReg()))
671 NC.getNotNullSucc()->addLiveIn(MO.getReg());
675 NC.getMemOperation()->eraseFromParent();
676 NC.getCheckOperation()->eraseFromParent();
678 // Insert an *unconditional* branch to not-null successor.
679 TII->insertBranch(*NC.getCheckBlock(), NC.getNotNullSucc(), nullptr,
682 NumImplicitNullChecks++;
687 char ImplicitNullChecks::ID = 0;
688 char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID;
689 INITIALIZE_PASS_BEGIN(ImplicitNullChecks, DEBUG_TYPE,
690 "Implicit null checks", false, false)
691 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
692 INITIALIZE_PASS_END(ImplicitNullChecks, DEBUG_TYPE,
693 "Implicit null checks", false, false)