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