LLVM  9.0.0svn
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 
28 #include "llvm/ADT/ArrayRef.h"
29 #include "llvm/ADT/None.h"
30 #include "llvm/ADT/Optional.h"
31 #include "llvm/ADT/STLExtras.h"
32 #include "llvm/ADT/SmallVector.h"
33 #include "llvm/ADT/Statistic.h"
36 #include "llvm/CodeGen/FaultMaps.h"
50 #include "llvm/IR/BasicBlock.h"
51 #include "llvm/IR/DebugLoc.h"
52 #include "llvm/IR/LLVMContext.h"
53 #include "llvm/MC/MCInstrDesc.h"
54 #include "llvm/MC/MCRegisterInfo.h"
55 #include "llvm/Pass.h"
57 #include <cassert>
58 #include <cstdint>
59 #include <iterator>
60 
61 using namespace llvm;
62 
63 static cl::opt<int> PageSize("imp-null-check-page-size",
64  cl::desc("The page size of the target in bytes"),
65  cl::init(4096), cl::Hidden);
66 
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(8));
72 
73 #define DEBUG_TYPE "implicit-null-checks"
74 
75 STATISTIC(NumImplicitNullChecks,
76  "Number of explicit null checks made implicit");
77 
78 namespace {
79 
80 class ImplicitNullChecks : public MachineFunctionPass {
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-None, then an instruction in \p Insts that also must be
99  /// hoisted.
100  Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence;
101 
102  /*implicit*/ DependenceResult(
103  bool CanReorder,
104  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,
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(MachineInstr &MI, MachineInstr *PrevMI);
184 
185  enum SuitabilityResult {
186  SR_Suitable,
187  SR_Unsuitable,
188  SR_Impossible
189  };
190 
191  /// Return SR_Suitable if \p MI a memory operation that can be used to
192  /// implicitly null check the value in \p PointerReg, SR_Unsuitable if
193  /// \p MI cannot be used to null check and SR_Impossible if there is
194  /// no sense to continue lookup due to any other instruction will not be able
195  /// to be used. \p PrevInsts is the set of instruction seen since
196  /// the explicit null check on \p PointerReg.
197  SuitabilityResult isSuitableMemoryOp(MachineInstr &MI, unsigned PointerReg,
198  ArrayRef<MachineInstr *> PrevInsts);
199 
200  /// Return true if \p FaultingMI can be hoisted from after the
201  /// instructions in \p InstsSeenSoFar to before them. Set \p Dependence to a
202  /// non-null value if we also need to (and legally can) hoist a depedency.
203  bool canHoistInst(MachineInstr *FaultingMI, unsigned PointerReg,
204  ArrayRef<MachineInstr *> InstsSeenSoFar,
206 
207 public:
208  static char ID;
209 
210  ImplicitNullChecks() : MachineFunctionPass(ID) {
212  }
213 
214  bool runOnMachineFunction(MachineFunction &MF) override;
215 
216  void getAnalysisUsage(AnalysisUsage &AU) const override {
219  }
220 
221  MachineFunctionProperties getRequiredProperties() const override {
224  }
225 };
226 
227 } // end anonymous namespace
228 
229 bool ImplicitNullChecks::canHandle(const MachineInstr *MI) {
230  if (MI->isCall() || MI->hasUnmodeledSideEffects())
231  return false;
232  auto IsRegMask = [](const MachineOperand &MO) { return MO.isRegMask(); };
233  (void)IsRegMask;
234 
235  assert(!llvm::any_of(MI->operands(), IsRegMask) &&
236  "Calls were filtered out above!");
237 
238  // TODO: This should be isUnordered (see D57601) once test cases are written
239  // demonstrating that.
240  auto IsSimple = [](MachineMemOperand *MMO) {
241  return !MMO->isVolatile() && !MMO->isAtomic(); };
242  return llvm::all_of(MI->memoperands(), IsSimple);
243 }
244 
245 ImplicitNullChecks::DependenceResult
246 ImplicitNullChecks::computeDependence(const MachineInstr *MI,
247  ArrayRef<MachineInstr *> Block) {
248  assert(llvm::all_of(Block, canHandle) && "Check this first!");
249  assert(!is_contained(Block, MI) && "Block must be exclusive of MI!");
250 
252 
253  for (auto I = Block.begin(), E = Block.end(); I != E; ++I) {
254  if (canReorder(*I, MI))
255  continue;
256 
257  if (Dep == None) {
258  // Found one possible dependency, keep track of it.
259  Dep = I;
260  } else {
261  // We found two dependencies, so bail out.
262  return {false, None};
263  }
264  }
265 
266  return {true, Dep};
267 }
268 
269 bool ImplicitNullChecks::canReorder(const MachineInstr *A,
270  const MachineInstr *B) {
271  assert(canHandle(A) && canHandle(B) && "Precondition!");
272 
273  // canHandle makes sure that we _can_ correctly analyze the dependencies
274  // between A and B here -- for instance, we should not be dealing with heap
275  // load-store dependencies here.
276 
277  for (auto MOA : A->operands()) {
278  if (!(MOA.isReg() && MOA.getReg()))
279  continue;
280 
281  unsigned RegA = MOA.getReg();
282  for (auto MOB : B->operands()) {
283  if (!(MOB.isReg() && MOB.getReg()))
284  continue;
285 
286  unsigned RegB = MOB.getReg();
287 
288  if (TRI->regsOverlap(RegA, RegB) && (MOA.isDef() || MOB.isDef()))
289  return false;
290  }
291  }
292 
293  return true;
294 }
295 
296 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
297  TII = MF.getSubtarget().getInstrInfo();
298  TRI = MF.getRegInfo().getTargetRegisterInfo();
299  MFI = &MF.getFrameInfo();
300  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
301 
302  SmallVector<NullCheck, 16> NullCheckList;
303 
304  for (auto &MBB : MF)
305  analyzeBlockForNullChecks(MBB, NullCheckList);
306 
307  if (!NullCheckList.empty())
308  rewriteNullChecks(NullCheckList);
309 
310  return !NullCheckList.empty();
311 }
312 
313 // Return true if any register aliasing \p Reg is live-in into \p MBB.
314 static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI,
315  MachineBasicBlock *MBB, unsigned Reg) {
316  for (MCRegAliasIterator AR(Reg, TRI, /*IncludeSelf*/ true); AR.isValid();
317  ++AR)
318  if (MBB->isLiveIn(*AR))
319  return true;
320  return false;
321 }
322 
323 ImplicitNullChecks::AliasResult
324 ImplicitNullChecks::areMemoryOpsAliased(MachineInstr &MI,
325  MachineInstr *PrevMI) {
326  // If it is not memory access, skip the check.
327  if (!(PrevMI->mayStore() || PrevMI->mayLoad()))
328  return AR_NoAlias;
329  // Load-Load may alias
330  if (!(MI.mayStore() || PrevMI->mayStore()))
331  return AR_NoAlias;
332  // We lost info, conservatively alias. If it was store then no sense to
333  // continue because we won't be able to check against it further.
334  if (MI.memoperands_empty())
335  return MI.mayStore() ? AR_WillAliasEverything : AR_MayAlias;
336  if (PrevMI->memoperands_empty())
337  return PrevMI->mayStore() ? AR_WillAliasEverything : AR_MayAlias;
338 
339  for (MachineMemOperand *MMO1 : MI.memoperands()) {
340  // MMO1 should have a value due it comes from operation we'd like to use
341  // as implicit null check.
342  assert(MMO1->getValue() && "MMO1 should have a Value!");
343  for (MachineMemOperand *MMO2 : PrevMI->memoperands()) {
344  if (const PseudoSourceValue *PSV = MMO2->getPseudoValue()) {
345  if (PSV->mayAlias(MFI))
346  return AR_MayAlias;
347  continue;
348  }
349  llvm::AliasResult AAResult =
350  AA->alias(MemoryLocation(MMO1->getValue(), LocationSize::unknown(),
351  MMO1->getAAInfo()),
352  MemoryLocation(MMO2->getValue(), LocationSize::unknown(),
353  MMO2->getAAInfo()));
354  if (AAResult != NoAlias)
355  return AR_MayAlias;
356  }
357  }
358  return AR_NoAlias;
359 }
360 
361 ImplicitNullChecks::SuitabilityResult
362 ImplicitNullChecks::isSuitableMemoryOp(MachineInstr &MI, unsigned PointerReg,
363  ArrayRef<MachineInstr *> PrevInsts) {
364  int64_t Offset;
365  MachineOperand *BaseOp;
366 
367  if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, TRI) ||
368  !BaseOp->isReg() || BaseOp->getReg() != PointerReg)
369  return SR_Unsuitable;
370 
371  // We want the mem access to be issued at a sane offset from PointerReg,
372  // so that if PointerReg is null then the access reliably page faults.
373  if (!((MI.mayLoad() || MI.mayStore()) && !MI.isPredicable() &&
374  -PageSize < Offset && Offset < PageSize))
375  return SR_Unsuitable;
376 
377  // Finally, check whether the current memory access aliases with previous one.
378  for (auto *PrevMI : PrevInsts) {
379  AliasResult AR = areMemoryOpsAliased(MI, PrevMI);
380  if (AR == AR_WillAliasEverything)
381  return SR_Impossible;
382  if (AR == AR_MayAlias)
383  return SR_Unsuitable;
384  }
385  return SR_Suitable;
386 }
387 
388 bool ImplicitNullChecks::canHoistInst(MachineInstr *FaultingMI,
389  unsigned PointerReg,
390  ArrayRef<MachineInstr *> InstsSeenSoFar,
391  MachineBasicBlock *NullSucc,
393  auto DepResult = computeDependence(FaultingMI, InstsSeenSoFar);
394  if (!DepResult.CanReorder)
395  return false;
396 
397  if (!DepResult.PotentialDependence) {
398  Dependence = nullptr;
399  return true;
400  }
401 
402  auto DependenceItr = *DepResult.PotentialDependence;
403  auto *DependenceMI = *DependenceItr;
404 
405  // We don't want to reason about speculating loads. Note -- at this point
406  // we should have already filtered out all of the other non-speculatable
407  // things, like calls and stores.
408  // We also do not want to hoist stores because it might change the memory
409  // while the FaultingMI may result in faulting.
410  assert(canHandle(DependenceMI) && "Should never have reached here!");
411  if (DependenceMI->mayLoadOrStore())
412  return false;
413 
414  for (auto &DependenceMO : DependenceMI->operands()) {
415  if (!(DependenceMO.isReg() && DependenceMO.getReg()))
416  continue;
417 
418  // Make sure that we won't clobber any live ins to the sibling block by
419  // hoisting Dependency. For instance, we can't hoist INST to before the
420  // null check (even if it safe, and does not violate any dependencies in
421  // the non_null_block) if %rdx is live in to _null_block.
422  //
423  // test %rcx, %rcx
424  // je _null_block
425  // _non_null_block:
426  // %rdx = INST
427  // ...
428  //
429  // This restriction does not apply to the faulting load inst because in
430  // case the pointer loaded from is in the null page, the load will not
431  // semantically execute, and affect machine state. That is, if the load
432  // was loading into %rax and it faults, the value of %rax should stay the
433  // same as it would have been had the load not have executed and we'd have
434  // branched to NullSucc directly.
435  if (AnyAliasLiveIn(TRI, NullSucc, DependenceMO.getReg()))
436  return false;
437 
438  // The Dependency can't be re-defining the base register -- then we won't
439  // get the memory operation on the address we want. This is already
440  // checked in \c IsSuitableMemoryOp.
441  assert(!(DependenceMO.isDef() &&
442  TRI->regsOverlap(DependenceMO.getReg(), PointerReg)) &&
443  "Should have been checked before!");
444  }
445 
446  auto DepDepResult =
447  computeDependence(DependenceMI, {InstsSeenSoFar.begin(), DependenceItr});
448 
449  if (!DepDepResult.CanReorder || DepDepResult.PotentialDependence)
450  return false;
451 
452  Dependence = DependenceMI;
453  return true;
454 }
455 
456 /// Analyze MBB to check if its terminating branch can be turned into an
457 /// implicit null check. If yes, append a description of the said null check to
458 /// NullCheckList and return true, else return false.
459 bool ImplicitNullChecks::analyzeBlockForNullChecks(
460  MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
461  using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
462 
463  MDNode *BranchMD = nullptr;
464  if (auto *BB = MBB.getBasicBlock())
465  BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit);
466 
467  if (!BranchMD)
468  return false;
469 
470  MachineBranchPredicate MBP;
471 
472  if (TII->analyzeBranchPredicate(MBB, MBP, true))
473  return false;
474 
475  // Is the predicate comparing an integer to zero?
476  if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
477  (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
478  MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
479  return false;
480 
481  // If we cannot erase the test instruction itself, then making the null check
482  // implicit does not buy us much.
483  if (!MBP.SingleUseCondition)
484  return false;
485 
486  MachineBasicBlock *NotNullSucc, *NullSucc;
487 
488  if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
489  NotNullSucc = MBP.TrueDest;
490  NullSucc = MBP.FalseDest;
491  } else {
492  NotNullSucc = MBP.FalseDest;
493  NullSucc = MBP.TrueDest;
494  }
495 
496  // We handle the simplest case for now. We can potentially do better by using
497  // the machine dominator tree.
498  if (NotNullSucc->pred_size() != 1)
499  return false;
500 
501  // To prevent the invalid transformation of the following code:
502  //
503  // mov %rax, %rcx
504  // test %rax, %rax
505  // %rax = ...
506  // je throw_npe
507  // mov(%rcx), %r9
508  // mov(%rax), %r10
509  //
510  // into:
511  //
512  // mov %rax, %rcx
513  // %rax = ....
514  // faulting_load_op("movl (%rax), %r10", throw_npe)
515  // mov(%rcx), %r9
516  //
517  // we must ensure that there are no instructions between the 'test' and
518  // conditional jump that modify %rax.
519  const unsigned PointerReg = MBP.LHS.getReg();
520 
521  assert(MBP.ConditionDef->getParent() == &MBB && "Should be in basic block");
522 
523  for (auto I = MBB.rbegin(); MBP.ConditionDef != &*I; ++I)
524  if (I->modifiesRegister(PointerReg, TRI))
525  return false;
526 
527  // Starting with a code fragment like:
528  //
529  // test %rax, %rax
530  // jne LblNotNull
531  //
532  // LblNull:
533  // callq throw_NullPointerException
534  //
535  // LblNotNull:
536  // Inst0
537  // Inst1
538  // ...
539  // Def = Load (%rax + <offset>)
540  // ...
541  //
542  //
543  // we want to end up with
544  //
545  // Def = FaultingLoad (%rax + <offset>), LblNull
546  // jmp LblNotNull ;; explicit or fallthrough
547  //
548  // LblNotNull:
549  // Inst0
550  // Inst1
551  // ...
552  //
553  // LblNull:
554  // callq throw_NullPointerException
555  //
556  //
557  // To see why this is legal, consider the two possibilities:
558  //
559  // 1. %rax is null: since we constrain <offset> to be less than PageSize, the
560  // load instruction dereferences the null page, causing a segmentation
561  // fault.
562  //
563  // 2. %rax is not null: in this case we know that the load cannot fault, as
564  // otherwise the load would've faulted in the original program too and the
565  // original program would've been undefined.
566  //
567  // This reasoning cannot be extended to justify hoisting through arbitrary
568  // control flow. For instance, in the example below (in pseudo-C)
569  //
570  // if (ptr == null) { throw_npe(); unreachable; }
571  // if (some_cond) { return 42; }
572  // v = ptr->field; // LD
573  // ...
574  //
575  // we cannot (without code duplication) use the load marked "LD" to null check
576  // ptr -- clause (2) above does not apply in this case. In the above program
577  // the safety of ptr->field can be dependent on some_cond; and, for instance,
578  // ptr could be some non-null invalid reference that never gets loaded from
579  // because some_cond is always true.
580 
581  SmallVector<MachineInstr *, 8> InstsSeenSoFar;
582 
583  for (auto &MI : *NotNullSucc) {
584  if (!canHandle(&MI) || InstsSeenSoFar.size() >= MaxInstsToConsider)
585  return false;
586 
587  MachineInstr *Dependence;
588  SuitabilityResult SR = isSuitableMemoryOp(MI, PointerReg, InstsSeenSoFar);
589  if (SR == SR_Impossible)
590  return false;
591  if (SR == SR_Suitable &&
592  canHoistInst(&MI, PointerReg, InstsSeenSoFar, NullSucc, Dependence)) {
593  NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc,
594  NullSucc, Dependence);
595  return true;
596  }
597 
598  // If MI re-defines the PointerReg then we cannot move further.
599  if (llvm::any_of(MI.operands(), [&](MachineOperand &MO) {
600  return MO.isReg() && MO.getReg() && MO.isDef() &&
601  TRI->regsOverlap(MO.getReg(), PointerReg);
602  }))
603  return false;
604  InstsSeenSoFar.push_back(&MI);
605  }
606 
607  return false;
608 }
609 
610 /// Wrap a machine instruction, MI, into a FAULTING machine instruction.
611 /// The FAULTING instruction does the same load/store as MI
612 /// (defining the same register), and branches to HandlerMBB if the mem access
613 /// faults. The FAULTING instruction is inserted at the end of MBB.
614 MachineInstr *ImplicitNullChecks::insertFaultingInstr(
615  MachineInstr *MI, MachineBasicBlock *MBB, MachineBasicBlock *HandlerMBB) {
616  const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for
617  // all targets.
618 
619  DebugLoc DL;
620  unsigned NumDefs = MI->getDesc().getNumDefs();
621  assert(NumDefs <= 1 && "other cases unhandled!");
622 
623  unsigned DefReg = NoRegister;
624  if (NumDefs != 0) {
625  DefReg = MI->getOperand(0).getReg();
626  assert(NumDefs == 1 && "expected exactly one def!");
627  }
628 
630  if (MI->mayLoad())
631  FK =
633  else
635 
636  auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_OP), DefReg)
637  .addImm(FK)
638  .addMBB(HandlerMBB)
639  .addImm(MI->getOpcode());
640 
641  for (auto &MO : MI->uses()) {
642  if (MO.isReg()) {
643  MachineOperand NewMO = MO;
644  if (MO.isUse()) {
645  NewMO.setIsKill(false);
646  } else {
647  assert(MO.isDef() && "Expected def or use");
648  NewMO.setIsDead(false);
649  }
650  MIB.add(NewMO);
651  } else {
652  MIB.add(MO);
653  }
654  }
655 
656  MIB.setMemRefs(MI->memoperands());
657 
658  return MIB;
659 }
660 
661 /// Rewrite the null checks in NullCheckList into implicit null checks.
662 void ImplicitNullChecks::rewriteNullChecks(
664  DebugLoc DL;
665 
666  for (auto &NC : NullCheckList) {
667  // Remove the conditional branch dependent on the null check.
668  unsigned BranchesRemoved = TII->removeBranch(*NC.getCheckBlock());
669  (void)BranchesRemoved;
670  assert(BranchesRemoved > 0 && "expected at least one branch!");
671 
672  if (auto *DepMI = NC.getOnlyDependency()) {
673  DepMI->removeFromParent();
674  NC.getCheckBlock()->insert(NC.getCheckBlock()->end(), DepMI);
675  }
676 
677  // Insert a faulting instruction where the conditional branch was
678  // originally. We check earlier ensures that this bit of code motion
679  // is legal. We do not touch the successors list for any basic block
680  // since we haven't changed control flow, we've just made it implicit.
681  MachineInstr *FaultingInstr = insertFaultingInstr(
682  NC.getMemOperation(), NC.getCheckBlock(), NC.getNullSucc());
683  // Now the values defined by MemOperation, if any, are live-in of
684  // the block of MemOperation.
685  // The original operation may define implicit-defs alongside
686  // the value.
687  MachineBasicBlock *MBB = NC.getMemOperation()->getParent();
688  for (const MachineOperand &MO : FaultingInstr->operands()) {
689  if (!MO.isReg() || !MO.isDef())
690  continue;
691  unsigned Reg = MO.getReg();
692  if (!Reg || MBB->isLiveIn(Reg))
693  continue;
694  MBB->addLiveIn(Reg);
695  }
696 
697  if (auto *DepMI = NC.getOnlyDependency()) {
698  for (auto &MO : DepMI->operands()) {
699  if (!MO.isReg() || !MO.getReg() || !MO.isDef())
700  continue;
701  if (!NC.getNotNullSucc()->isLiveIn(MO.getReg()))
702  NC.getNotNullSucc()->addLiveIn(MO.getReg());
703  }
704  }
705 
706  NC.getMemOperation()->eraseFromParent();
707  NC.getCheckOperation()->eraseFromParent();
708 
709  // Insert an *unconditional* branch to not-null successor.
710  TII->insertBranch(*NC.getCheckBlock(), NC.getNotNullSucc(), nullptr,
711  /*Cond=*/None, DL);
712 
713  NumImplicitNullChecks++;
714  }
715 }
716 
717 char ImplicitNullChecks::ID = 0;
718 
720 
721 INITIALIZE_PASS_BEGIN(ImplicitNullChecks, DEBUG_TYPE,
722  "Implicit null checks", false, false)
724 INITIALIZE_PASS_END(ImplicitNullChecks, DEBUG_TYPE,
725  "Implicit null checks", false, false)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:632
This class represents lattice values for constants.
Definition: AllocatorList.h:23
iterator_range< mop_iterator > uses()
Returns a range that includes all operands that are register uses.
Definition: MachineInstr.h:491
iterator begin() const
Definition: ArrayRef.h:136
static constexpr LocationSize unknown()
unsigned getReg() const
getReg - Returns the register number.
unsigned Reg
bool isPredicable(QueryType Type=AllInBundle) const
Return true if this instruction has a predicate operand that controls execution.
Definition: MachineInstr.h:686
The two locations do not alias at all.
Definition: AliasAnalysis.h:83
virtual unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const
Insert branch code into the end of the specified MachineBasicBlock.
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:1185
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
A debug info location.
Definition: DebugLoc.h:33
Metadata node.
Definition: Metadata.h:863
void setIsDead(bool Val=true)
static cl::opt< unsigned > MaxInstsToConsider("imp-null-max-insts-to-consider", cl::desc("The max number of instructions to consider hoisting loads over " "(the algorithm is quadratic over this number)"), cl::Hidden, cl::init(8))
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:458
virtual unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const
Remove the branching code at the end of the specific MBB.
Represents a predicate at the MachineFunction level.
virtual bool getMemOperandWithOffset(MachineInstr &MI, MachineOperand *&BaseOp, int64_t &Offset, const TargetRegisterInfo *TRI) const
Get the base operand and byte offset of an instruction that reads/writes memory.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
A description of a memory reference used in the backend.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
Implicit null checks
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:408
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:405
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
#define DEBUG_TYPE
virtual const TargetInstrInfo * getInstrInfo() const
reverse_iterator rbegin()
TargetInstrInfo - Interface to description of machine instruction set.
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:77
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
Definition: MachineInstr.h:819
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:422
const TargetRegisterInfo * getTargetRegisterInfo() const
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
ArrayRef< MachineMemOperand * > memoperands() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:515
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
INITIALIZE_PASS_BEGIN(ImplicitNullChecks, DEBUG_TYPE, "Implicit null checks", false, false) INITIALIZE_PASS_END(ImplicitNullChecks
MCRegAliasIterator enumerates all registers aliasing Reg.
Represent the analysis usage information of a pass.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1192
void initializeImplicitNullChecksPass(PassRegistry &)
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
size_t size() const
Definition: SmallVector.h:52
char & ImplicitNullChecksID
ImplicitNullChecks - This pass folds null pointer checks into nearby memory operations.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
void setIsKill(bool Val=true)
Representation for a specific memory location.
bool regsOverlap(unsigned regA, unsigned regB) const
Returns true if the two registers are equal or alias each other.
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:839
iterator end() const
Definition: ArrayRef.h:137
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:225
#define NC
Definition: regutils.h:42
unsigned pred_size() const
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
Special value supplied for machine level alias analysis.
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:63
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:644
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
virtual bool analyzeBranchPredicate(MachineBasicBlock &MBB, MachineBranchPredicate &MBP, bool AllowModify=false) const
Analyze the branching code at the end of MBB and parse it into the MachineBranchPredicate structure i...
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
This file provides utility analysis objects describing memory locations.
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:44
static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI, MachineBasicBlock *MBB, unsigned Reg)
#define I(x, y, z)
Definition: MD5.cpp:58
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
static cl::opt< int > PageSize("imp-null-check-page-size", cl::desc("The page size of the target in bytes"), cl::init(4096), cl::Hidden)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
Definition: MachineInstr.h:806
bool memoperands_empty() const
Return true if we don&#39;t have any memory operands which described the memory access done by this instr...
Definition: MachineInstr.h:545
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore...
IRTranslator LLVM IR MI
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned char TargetFlags=0) const
Dependence - This class represents a dependence between two memory memory references in a function...
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:413
Properties which a MachineFunction may have at a given point in time.
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1244