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
26 //===----------------------------------------------------------------------===//
28 #include "llvm/ADT/DenseSet.h"
29 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/Analysis/AliasAnalysis.h"
32 #include "llvm/CodeGen/Passes.h"
33 #include "llvm/CodeGen/MachineFunction.h"
34 #include "llvm/CodeGen/MachineMemOperand.h"
35 #include "llvm/CodeGen/MachineOperand.h"
36 #include "llvm/CodeGen/MachineFunctionPass.h"
37 #include "llvm/CodeGen/MachineInstrBuilder.h"
38 #include "llvm/CodeGen/MachineRegisterInfo.h"
39 #include "llvm/CodeGen/MachineModuleInfo.h"
40 #include "llvm/IR/BasicBlock.h"
41 #include "llvm/IR/Instruction.h"
42 #include "llvm/IR/LLVMContext.h"
43 #include "llvm/Support/CommandLine.h"
44 #include "llvm/Support/Debug.h"
45 #include "llvm/Target/TargetSubtargetInfo.h"
46 #include "llvm/Target/TargetInstrInfo.h"
50 static cl::opt<int> PageSize("imp-null-check-page-size",
51 cl::desc("The page size of the target in bytes"),
54 static cl::opt<unsigned> MaxInstsToConsider(
55 "imp-null-max-insts-to-consider",
56 cl::desc("The max number of instructions to consider hoisting loads over "
57 "(the algorithm is quadratic over this number)"),
60 #define DEBUG_TYPE "implicit-null-checks"
62 STATISTIC(NumImplicitNullChecks,
63 "Number of explicit null checks made implicit");
67 class ImplicitNullChecks : public MachineFunctionPass {
68 /// Return true if \c computeDependence can process \p MI.
69 static bool canHandle(const MachineInstr *MI);
71 /// Helper function for \c computeDependence. Return true if \p A
72 /// and \p B do not have any dependences between them, and can be
73 /// re-ordered without changing program semantics.
74 bool canReorder(const MachineInstr *A, const MachineInstr *B);
76 /// A data type for representing the result computed by \c
77 /// computeDependence. States whether it is okay to reorder the
78 /// instruction passed to \c computeDependence with at most one
80 struct DependenceResult {
81 /// Can we actually re-order \p MI with \p Insts (see \c
82 /// computeDependence).
85 /// If non-None, then an instruction in \p Insts that also must be
87 Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence;
89 /*implicit*/ DependenceResult(
91 Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence)
92 : CanReorder(CanReorder), PotentialDependence(PotentialDependence) {
93 assert((!PotentialDependence || CanReorder) &&
94 "!CanReorder && PotentialDependence.hasValue() not allowed!");
98 /// Compute a result for the following question: can \p MI be
99 /// re-ordered from after \p Insts to before it.
101 /// \c canHandle should return true for all instructions in \p
103 DependenceResult computeDependence(const MachineInstr *MI,
104 ArrayRef<MachineInstr *> Insts);
106 /// Represents one null check that can be made implicit.
108 // The memory operation the null check can be folded into.
109 MachineInstr *MemOperation;
111 // The instruction actually doing the null check (Ptr != 0).
112 MachineInstr *CheckOperation;
114 // The block the check resides in.
115 MachineBasicBlock *CheckBlock;
117 // The block branched to if the pointer is non-null.
118 MachineBasicBlock *NotNullSucc;
120 // The block branched to if the pointer is null.
121 MachineBasicBlock *NullSucc;
123 // If this is non-null, then MemOperation has a dependency on on this
124 // instruction; and it needs to be hoisted to execute before MemOperation.
125 MachineInstr *OnlyDependency;
128 explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation,
129 MachineBasicBlock *checkBlock,
130 MachineBasicBlock *notNullSucc,
131 MachineBasicBlock *nullSucc,
132 MachineInstr *onlyDependency)
133 : MemOperation(memOperation), CheckOperation(checkOperation),
134 CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc),
135 OnlyDependency(onlyDependency) {}
137 MachineInstr *getMemOperation() const { return MemOperation; }
139 MachineInstr *getCheckOperation() const { return CheckOperation; }
141 MachineBasicBlock *getCheckBlock() const { return CheckBlock; }
143 MachineBasicBlock *getNotNullSucc() const { return NotNullSucc; }
145 MachineBasicBlock *getNullSucc() const { return NullSucc; }
147 MachineInstr *getOnlyDependency() const { return OnlyDependency; }
150 const TargetInstrInfo *TII = nullptr;
151 const TargetRegisterInfo *TRI = nullptr;
152 AliasAnalysis *AA = nullptr;
153 MachineModuleInfo *MMI = nullptr;
155 bool analyzeBlockForNullChecks(MachineBasicBlock &MBB,
156 SmallVectorImpl<NullCheck> &NullCheckList);
157 MachineInstr *insertFaultingLoad(MachineInstr *LoadMI, MachineBasicBlock *MBB,
158 MachineBasicBlock *HandlerMBB);
159 void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList);
161 /// Is \p MI a memory operation that can be used to implicitly null check the
162 /// value in \p PointerReg? \p PrevInsts is the set of instruction seen since
163 /// the explicit null check on \p PointerReg.
164 bool isSuitableMemoryOp(MachineInstr &MI, unsigned PointerReg,
165 ArrayRef<MachineInstr *> PrevInsts);
167 /// Return true if \p FaultingMI can be hoisted from after the the
168 /// instructions in \p InstsSeenSoFar to before them. Set \p Dependence to a
169 /// non-null value if we also need to (and legally can) hoist a depedency.
170 bool canHoistLoadInst(MachineInstr *FaultingMI, unsigned PointerReg,
171 ArrayRef<MachineInstr *> InstsSeenSoFar,
172 MachineBasicBlock *NullSucc, MachineInstr *&Dependence);
177 ImplicitNullChecks() : MachineFunctionPass(ID) {
178 initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry());
181 bool runOnMachineFunction(MachineFunction &MF) override;
182 void getAnalysisUsage(AnalysisUsage &AU) const override {
183 AU.addRequired<AAResultsWrapperPass>();
184 MachineFunctionPass::getAnalysisUsage(AU);
187 MachineFunctionProperties getRequiredProperties() const override {
188 return MachineFunctionProperties().set(
189 MachineFunctionProperties::Property::NoVRegs);
195 bool ImplicitNullChecks::canHandle(const MachineInstr *MI) {
196 if (MI->isCall() || MI->mayStore() || MI->hasUnmodeledSideEffects())
198 auto IsRegMask = [](const MachineOperand &MO) { return MO.isRegMask(); };
201 assert(!llvm::any_of(MI->operands(), IsRegMask) &&
202 "Calls were filtered out above!");
204 auto IsUnordered = [](MachineMemOperand *MMO) { return MMO->isUnordered(); };
205 return llvm::all_of(MI->memoperands(), IsUnordered);
208 ImplicitNullChecks::DependenceResult
209 ImplicitNullChecks::computeDependence(const MachineInstr *MI,
210 ArrayRef<MachineInstr *> Block) {
211 assert(llvm::all_of(Block, canHandle) && "Check this first!");
212 assert(!llvm::is_contained(Block, MI) && "Block must be exclusive of MI!");
214 Optional<ArrayRef<MachineInstr *>::iterator> Dep;
216 for (auto I = Block.begin(), E = Block.end(); I != E; ++I) {
217 if (canReorder(*I, MI))
221 // Found one possible dependency, keep track of it.
224 // We found two dependencies, so bail out.
225 return {false, None};
232 bool ImplicitNullChecks::canReorder(const MachineInstr *A,
233 const MachineInstr *B) {
234 assert(canHandle(A) && canHandle(B) && "Precondition!");
236 // canHandle makes sure that we _can_ correctly analyze the dependencies
237 // between A and B here -- for instance, we should not be dealing with heap
238 // load-store dependencies here.
240 for (auto MOA : A->operands()) {
241 if (!(MOA.isReg() && MOA.getReg()))
244 unsigned RegA = MOA.getReg();
245 for (auto MOB : B->operands()) {
246 if (!(MOB.isReg() && MOB.getReg()))
249 unsigned RegB = MOB.getReg();
251 if (TRI->regsOverlap(RegA, RegB))
259 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
260 TII = MF.getSubtarget().getInstrInfo();
261 TRI = MF.getRegInfo().getTargetRegisterInfo();
263 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
265 SmallVector<NullCheck, 16> NullCheckList;
268 analyzeBlockForNullChecks(MBB, NullCheckList);
270 if (!NullCheckList.empty())
271 rewriteNullChecks(NullCheckList);
273 return !NullCheckList.empty();
276 // Return true if any register aliasing \p Reg is live-in into \p MBB.
277 static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI,
278 MachineBasicBlock *MBB, unsigned Reg) {
279 for (MCRegAliasIterator AR(Reg, TRI, /*IncludeSelf*/ true); AR.isValid();
281 if (MBB->isLiveIn(*AR))
286 bool ImplicitNullChecks::isSuitableMemoryOp(
287 MachineInstr &MI, unsigned PointerReg, ArrayRef<MachineInstr *> PrevInsts) {
291 if (!TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI) ||
292 BaseReg != PointerReg)
295 // We want the load to be issued at a sane offset from PointerReg, so that
296 // if PointerReg is null then the load reliably page faults.
297 if (!(MI.mayLoad() && !MI.isPredicable() && Offset < PageSize))
300 // Finally, we need to make sure that the load instruction actually is
301 // loading from PointerReg, and there isn't some re-definition of PointerReg
302 // between the compare and the load.
303 for (auto *PrevMI : PrevInsts)
304 for (auto &PrevMO : PrevMI->operands())
305 if (PrevMO.isReg() && PrevMO.getReg() &&
306 TRI->regsOverlap(PrevMO.getReg(), PointerReg))
312 bool ImplicitNullChecks::canHoistLoadInst(
313 MachineInstr *FaultingMI, unsigned PointerReg,
314 ArrayRef<MachineInstr *> InstsSeenSoFar, MachineBasicBlock *NullSucc,
315 MachineInstr *&Dependence) {
316 auto DepResult = computeDependence(FaultingMI, InstsSeenSoFar);
317 if (!DepResult.CanReorder)
320 if (!DepResult.PotentialDependence) {
321 Dependence = nullptr;
325 auto DependenceItr = *DepResult.PotentialDependence;
326 auto *DependenceMI = *DependenceItr;
328 // We don't want to reason about speculating loads. Note -- at this point
329 // we should have already filtered out all of the other non-speculatable
330 // things, like calls and stores.
331 assert(canHandle(DependenceMI) && "Should never have reached here!");
332 if (DependenceMI->mayLoad())
335 for (auto &DependenceMO : DependenceMI->operands()) {
336 if (!(DependenceMO.isReg() && DependenceMO.getReg()))
339 // Make sure that we won't clobber any live ins to the sibling block by
340 // hoisting Dependency. For instance, we can't hoist INST to before the
341 // null check (even if it safe, and does not violate any dependencies in
342 // the non_null_block) if %rdx is live in to _null_block.
350 // This restriction does not apply to the faulting load inst because in
351 // case the pointer loaded from is in the null page, the load will not
352 // semantically execute, and affect machine state. That is, if the load
353 // was loading into %rax and it faults, the value of %rax should stay the
354 // same as it would have been had the load not have executed and we'd have
355 // branched to NullSucc directly.
356 if (AnyAliasLiveIn(TRI, NullSucc, DependenceMO.getReg()))
359 // The Dependency can't be re-defining the base register -- then we won't
360 // get the memory operation on the address we want. This is already
361 // checked in \c IsSuitableMemoryOp.
362 assert(!TRI->regsOverlap(DependenceMO.getReg(), PointerReg) &&
363 "Should have been checked before!");
367 computeDependence(DependenceMI, {InstsSeenSoFar.begin(), DependenceItr});
369 if (!DepDepResult.CanReorder || DepDepResult.PotentialDependence)
372 Dependence = DependenceMI;
376 /// Analyze MBB to check if its terminating branch can be turned into an
377 /// implicit null check. If yes, append a description of the said null check to
378 /// NullCheckList and return true, else return false.
379 bool ImplicitNullChecks::analyzeBlockForNullChecks(
380 MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
381 typedef TargetInstrInfo::MachineBranchPredicate MachineBranchPredicate;
383 MDNode *BranchMD = nullptr;
384 if (auto *BB = MBB.getBasicBlock())
385 BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit);
390 MachineBranchPredicate MBP;
392 if (TII->analyzeBranchPredicate(MBB, MBP, true))
395 // Is the predicate comparing an integer to zero?
396 if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
397 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
398 MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
401 // If we cannot erase the test instruction itself, then making the null check
402 // implicit does not buy us much.
403 if (!MBP.SingleUseCondition)
406 MachineBasicBlock *NotNullSucc, *NullSucc;
408 if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
409 NotNullSucc = MBP.TrueDest;
410 NullSucc = MBP.FalseDest;
412 NotNullSucc = MBP.FalseDest;
413 NullSucc = MBP.TrueDest;
416 // We handle the simplest case for now. We can potentially do better by using
417 // the machine dominator tree.
418 if (NotNullSucc->pred_size() != 1)
421 // Starting with a code fragment like:
427 // callq throw_NullPointerException
433 // Def = Load (%RAX + <offset>)
437 // we want to end up with
439 // Def = FaultingLoad (%RAX + <offset>), LblNull
440 // jmp LblNotNull ;; explicit or fallthrough
448 // callq throw_NullPointerException
451 // To see why this is legal, consider the two possibilities:
453 // 1. %RAX is null: since we constrain <offset> to be less than PageSize, the
454 // load instruction dereferences the null page, causing a segmentation
457 // 2. %RAX is not null: in this case we know that the load cannot fault, as
458 // otherwise the load would've faulted in the original program too and the
459 // original program would've been undefined.
461 // This reasoning cannot be extended to justify hoisting through arbitrary
462 // control flow. For instance, in the example below (in pseudo-C)
464 // if (ptr == null) { throw_npe(); unreachable; }
465 // if (some_cond) { return 42; }
466 // v = ptr->field; // LD
469 // we cannot (without code duplication) use the load marked "LD" to null check
470 // ptr -- clause (2) above does not apply in this case. In the above program
471 // the safety of ptr->field can be dependent on some_cond; and, for instance,
472 // ptr could be some non-null invalid reference that never gets loaded from
473 // because some_cond is always true.
475 const unsigned PointerReg = MBP.LHS.getReg();
477 SmallVector<MachineInstr *, 8> InstsSeenSoFar;
479 for (auto &MI : *NotNullSucc) {
480 if (!canHandle(&MI) || InstsSeenSoFar.size() >= MaxInstsToConsider)
483 MachineInstr *Dependence;
484 if (isSuitableMemoryOp(MI, PointerReg, InstsSeenSoFar) &&
485 canHoistLoadInst(&MI, PointerReg, InstsSeenSoFar, NullSucc,
487 NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc,
488 NullSucc, Dependence);
492 InstsSeenSoFar.push_back(&MI);
498 /// Wrap a machine load instruction, LoadMI, into a FAULTING_LOAD_OP machine
499 /// instruction. The FAULTING_LOAD_OP instruction does the same load as LoadMI
500 /// (defining the same register), and branches to HandlerMBB if the load
501 /// faults. The FAULTING_LOAD_OP instruction is inserted at the end of MBB.
503 ImplicitNullChecks::insertFaultingLoad(MachineInstr *LoadMI,
504 MachineBasicBlock *MBB,
505 MachineBasicBlock *HandlerMBB) {
506 const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for
510 unsigned NumDefs = LoadMI->getDesc().getNumDefs();
511 assert(NumDefs <= 1 && "other cases unhandled!");
513 unsigned DefReg = NoRegister;
515 DefReg = LoadMI->defs().begin()->getReg();
516 assert(std::distance(LoadMI->defs().begin(), LoadMI->defs().end()) == 1 &&
517 "expected exactly one def!");
520 auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_LOAD_OP), DefReg)
522 .addImm(LoadMI->getOpcode());
524 for (auto &MO : LoadMI->uses())
527 MIB.setMemRefs(LoadMI->memoperands_begin(), LoadMI->memoperands_end());
532 /// Rewrite the null checks in NullCheckList into implicit null checks.
533 void ImplicitNullChecks::rewriteNullChecks(
534 ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
537 for (auto &NC : NullCheckList) {
538 // Remove the conditional branch dependent on the null check.
539 unsigned BranchesRemoved = TII->removeBranch(*NC.getCheckBlock());
540 (void)BranchesRemoved;
541 assert(BranchesRemoved > 0 && "expected at least one branch!");
543 if (auto *DepMI = NC.getOnlyDependency()) {
544 DepMI->removeFromParent();
545 NC.getCheckBlock()->insert(NC.getCheckBlock()->end(), DepMI);
548 // Insert a faulting load where the conditional branch was originally. We
549 // check earlier ensures that this bit of code motion is legal. We do not
550 // touch the successors list for any basic block since we haven't changed
551 // control flow, we've just made it implicit.
552 MachineInstr *FaultingLoad = insertFaultingLoad(
553 NC.getMemOperation(), NC.getCheckBlock(), NC.getNullSucc());
554 // Now the values defined by MemOperation, if any, are live-in of
555 // the block of MemOperation.
556 // The original load operation may define implicit-defs alongside
558 MachineBasicBlock *MBB = NC.getMemOperation()->getParent();
559 for (const MachineOperand &MO : FaultingLoad->operands()) {
560 if (!MO.isReg() || !MO.isDef())
562 unsigned Reg = MO.getReg();
563 if (!Reg || MBB->isLiveIn(Reg))
568 if (auto *DepMI = NC.getOnlyDependency()) {
569 for (auto &MO : DepMI->operands()) {
570 if (!MO.isReg() || !MO.getReg() || !MO.isDef())
572 if (!NC.getNotNullSucc()->isLiveIn(MO.getReg()))
573 NC.getNotNullSucc()->addLiveIn(MO.getReg());
577 NC.getMemOperation()->eraseFromParent();
578 NC.getCheckOperation()->eraseFromParent();
580 // Insert an *unconditional* branch to not-null successor.
581 TII->insertBranch(*NC.getCheckBlock(), NC.getNotNullSucc(), nullptr,
584 NumImplicitNullChecks++;
589 char ImplicitNullChecks::ID = 0;
590 char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID;
591 INITIALIZE_PASS_BEGIN(ImplicitNullChecks, "implicit-null-checks",
592 "Implicit null checks", false, false)
593 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
594 INITIALIZE_PASS_END(ImplicitNullChecks, "implicit-null-checks",
595 "Implicit null checks", false, false)