LLVM 24.0.0git
ImplicitNullChecks.cpp
Go to the documentation of this file.
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
29#include "CodeGenOptions.h"
30#include "llvm/ADT/ArrayRef.h"
31#include "llvm/ADT/STLExtras.h"
33#include "llvm/ADT/Statistic.h"
50#include "llvm/IR/BasicBlock.h"
51#include "llvm/IR/DebugLoc.h"
52#include "llvm/IR/LLVMContext.h"
54#include "llvm/MC/MCInstrDesc.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,
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(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>();
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(MI->memoperands(), IsUnordered);
252}
253
254ImplicitNullChecksImpl::DependenceResult
255ImplicitNullChecksImpl::computeDependence(const MachineInstr *MI,
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(*I, 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.
321 for (MCRegAliasIterator AR(Reg, TRI, /*IncludeSelf*/ true); AR.isValid();
322 ++AR)
323 if (MBB->isLiveIn(*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 MemoryLocation::getAfter(MMO1->getValue(), MMO1->getAAInfo()),
356 MemoryLocation::getAfter(MMO2->getValue(), 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(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(PointerReg, MRI);
387 // Bail out of the sizes of BaseReg, ScaledReg and PointerReg are not the
388 // same.
389 if ((BaseReg &&
390 TRI->getRegSizeInBits(BaseReg, MRI) != PointerRegSizeInBits) ||
391 (ScaledReg &&
392 TRI->getRegSizeInBits(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(MachineBasicBlock::const_reverse_iterator(&MI));
407 It != MI.getParent()->rend(); It++) {
408 const MachineInstr *CurrMI = &*It;
409 if (CurrMI->modifiesRegister(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(*ModifyingMI, 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(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(MultiplierC, IsOverflow);
432 if (IsOverflow)
433 return false;
434 APInt DisplacementC(64, Displacement, true /*isSigned*/);
435 DisplacementC = Product.sadd_ov(DisplacementC, 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, NullSucc, 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(FaultingMI, 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(DependenceMI, {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(LLVMContext::MD_make_implicit);
559
560 if (!BranchMD)
561 return false;
562
563 MachineBranchPredicate MBP;
564
565 if (TII->analyzeBranchPredicate(MBB, MBP, 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(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(NotNullSucc->begin(), NotNullSucc->end())) {
686 if (!canHandle(&MI) ||
687 InstsSeenSoFar.size() >= Opts.imp_null_max_insts_to_consider)
688 return false;
689
690 MachineInstr *Dependence;
691 SuitabilityResult SR = isSuitableMemoryOp(MI, PointerReg, InstsSeenSoFar);
692 if (SR == SR_Impossible)
693 return false;
694 if (SR == SR_Suitable &&
695 canHoistInst(&MI, InstsSeenSoFar, NullSucc, Dependence)) {
696 NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc,
697 NullSucc, 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, PointerReg))
704 return false;
705 InstsSeenSoFar.push_back(&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(0).getReg();
723 assert(NumDefs == 1 && "expected exactly one def!");
724 }
725
727 if (MI->mayLoad())
728 FK =
730 else
732
733 auto MIB = BuildMI(MBB, MI->getDebugLoc(),
734 TII->get(TargetOpcode::FAULTING_OP), DefReg)
735 .addImm(FK)
736 .addMBB(HandlerMBB)
737 .addImm(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(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(
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(*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(NC.getCheckBlock()->end(), 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 NC.getMemOperation(), NC.getCheckBlock(), 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(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(MO.getReg()))
798 NC.getNotNullSucc()->addLiveIn(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(*NC.getCheckBlock(), NC.getNotNullSucc(), 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)
822INITIALIZE_PASS_END(ImplicitNullChecksLegacy, DEBUG_TYPE,
823 "Implicit null checks", false, false)
824
828 MFPropsModifier _(*this, MF);
829 auto &FAM = MFAM.getResult<FunctionAnalysisManagerMachineFunctionProxy>(MF)
830 .getManager();
831 auto &AA = FAM.getResult<AAManager>(MF.getFunction());
832 bool Changed = ImplicitNullChecksImpl(MF, &AA).run(MF);
833 if (!Changed)
834 return PreservedAnalyses::all();
836}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define DEBUG_TYPE
const HexagonInstrInfo * TII
#define _
IRTranslator LLVM IR MI
static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI, MachineBasicBlock *MBB, Register Reg)
#define I(x, y, z)
Definition MD5.cpp:57
Register Reg
Register const TargetRegisterInfo * TRI
Promote Memory to Register
Definition Mem2Reg.cpp:110
This file provides utility analysis objects describing memory locations.
FunctionAnalysisManager FAM
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
MachineRegisterInfo & MRI
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
uint16_t RegSizeInBits(const MCRegisterInfo &MRI, MCRegister RegNo)
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are no-alias.
LLVM_ABI APInt sadd_ov(const APInt &RHS, bool &Overflow) const
Definition APInt.cpp:1966
AnalysisUsage & addRequired()
const_pointer iterator
Definition ArrayRef.h:47
iterator begin() const
Definition ArrayRef.h:129
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const override
Insert branch code into the end of the specified MachineBasicBlock.
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
MCRegAliasIterator enumerates all registers aliasing Reg.
An RAII based helper class to modify MachineFunctionProperties when running pass.
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
reverse_iterator rbegin()
MachineInstrBundleIterator< const MachineInstr, true > const_reverse_iterator
LLVM_ABI bool isLiveIn(MCRegister Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineInstrBuilder & setMemRefs(ArrayRef< MachineMemOperand * > MMOs) const
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
Representation of each machine instruction.
bool mayLoadOrStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read or modify memory.
filtered_mop_range all_defs()
Returns an iterator range over all operands that are (explicit or implicit) register defs.
bool memoperands_empty() const
Return true if we don't have any memory operands which described the memory access done by this instr...
bool modifiesRegister(Register Reg, const TargetRegisterInfo *TRI) const
Return true if the MachineInstr modifies (fully define or partially define) the specified register.
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
mop_range operands()
ArrayRef< MachineMemOperand * > memoperands() const
Access to memory operands of the instruction.
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
void setIsDead(bool Val=true)
void setIsKill(bool Val=true)
const MachineFunction & getMF() const
static MemoryLocation getAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location after Ptr, while remaining within the underlying objec...
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
Wrapper class representing virtual and physical registers.
Definition Register.h:20
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Abstract Attribute helper functions.
Definition Attributor.h:166
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
std::reverse_iterator< iterator > rend() const
Definition BasicBlock.h:96
BaseReg
Stack frame base register. Bit 0 of FREInfo.Info.
Definition SFrame.h:77
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1755
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
LLVM_ABI char & ImplicitNullChecksID
ImplicitNullChecks - This pass folds null pointer checks into nearby memory operations.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1769
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
auto instructionsWithoutDebug(IterT It, IterT End, bool SkipPseudoOp=true)
Construct a range iterator which begins at It and moves forwards until End is reached,...
ArrayRef(const T &OneElt) -> ArrayRef< T >
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition STLExtras.h:1963
AAResults AliasAnalysis
Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
#define NC
Definition regutils.h:42