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