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