LLVM  11.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 
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/InitializePasses.h"
54 #include "llvm/MC/MCInstrDesc.h"
55 #include "llvm/MC/MCRegisterInfo.h"
56 #include "llvm/Pass.h"
58 #include <cassert>
59 #include <cstdint>
60 #include <iterator>
61 
62 using namespace llvm;
63 
64 static cl::opt<int> PageSize("imp-null-check-page-size",
65  cl::desc("The page size of the target in bytes"),
66  cl::init(4096), cl::Hidden);
67 
69  "imp-null-max-insts-to-consider",
70  cl::desc("The max number of instructions to consider hoisting loads over "
71  "(the algorithm is quadratic over this number)"),
72  cl::Hidden, cl::init(8));
73 
74 #define DEBUG_TYPE "implicit-null-checks"
75 
76 STATISTIC(NumImplicitNullChecks,
77  "Number of explicit null checks made implicit");
78 
79 namespace {
80 
81 class ImplicitNullChecks : public MachineFunctionPass {
82  /// Return true if \c computeDependence can process \p MI.
83  static bool canHandle(const MachineInstr *MI);
84 
85  /// Helper function for \c computeDependence. Return true if \p A
86  /// and \p B do not have any dependences between them, and can be
87  /// re-ordered without changing program semantics.
88  bool canReorder(const MachineInstr *A, const MachineInstr *B);
89 
90  /// A data type for representing the result computed by \c
91  /// computeDependence. States whether it is okay to reorder the
92  /// instruction passed to \c computeDependence with at most one
93  /// dependency.
94  struct DependenceResult {
95  /// Can we actually re-order \p MI with \p Insts (see \c
96  /// computeDependence).
97  bool CanReorder;
98 
99  /// If non-None, then an instruction in \p Insts that also must be
100  /// hoisted.
101  Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence;
102 
103  /*implicit*/ DependenceResult(
104  bool CanReorder,
105  Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence)
106  : CanReorder(CanReorder), PotentialDependence(PotentialDependence) {
107  assert((!PotentialDependence || CanReorder) &&
108  "!CanReorder && PotentialDependence.hasValue() not allowed!");
109  }
110  };
111 
112  /// Compute a result for the following question: can \p MI be
113  /// re-ordered from after \p Insts to before it.
114  ///
115  /// \c canHandle should return true for all instructions in \p
116  /// Insts.
117  DependenceResult computeDependence(const MachineInstr *MI,
119 
120  /// Represents one null check that can be made implicit.
121  class NullCheck {
122  // The memory operation the null check can be folded into.
123  MachineInstr *MemOperation;
124 
125  // The instruction actually doing the null check (Ptr != 0).
126  MachineInstr *CheckOperation;
127 
128  // The block the check resides in.
129  MachineBasicBlock *CheckBlock;
130 
131  // The block branched to if the pointer is non-null.
132  MachineBasicBlock *NotNullSucc;
133 
134  // The block branched to if the pointer is null.
135  MachineBasicBlock *NullSucc;
136 
137  // If this is non-null, then MemOperation has a dependency on this
138  // instruction; and it needs to be hoisted to execute before MemOperation.
139  MachineInstr *OnlyDependency;
140 
141  public:
142  explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation,
143  MachineBasicBlock *checkBlock,
144  MachineBasicBlock *notNullSucc,
145  MachineBasicBlock *nullSucc,
146  MachineInstr *onlyDependency)
147  : MemOperation(memOperation), CheckOperation(checkOperation),
148  CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc),
149  OnlyDependency(onlyDependency) {}
150 
151  MachineInstr *getMemOperation() const { return MemOperation; }
152 
153  MachineInstr *getCheckOperation() const { return CheckOperation; }
154 
155  MachineBasicBlock *getCheckBlock() const { return CheckBlock; }
156 
157  MachineBasicBlock *getNotNullSucc() const { return NotNullSucc; }
158 
159  MachineBasicBlock *getNullSucc() const { return NullSucc; }
160 
161  MachineInstr *getOnlyDependency() const { return OnlyDependency; }
162  };
163 
164  const TargetInstrInfo *TII = nullptr;
165  const TargetRegisterInfo *TRI = nullptr;
166  AliasAnalysis *AA = nullptr;
167  MachineFrameInfo *MFI = nullptr;
168 
169  bool analyzeBlockForNullChecks(MachineBasicBlock &MBB,
170  SmallVectorImpl<NullCheck> &NullCheckList);
171  MachineInstr *insertFaultingInstr(MachineInstr *MI, MachineBasicBlock *MBB,
172  MachineBasicBlock *HandlerMBB);
173  void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList);
174 
175  enum AliasResult {
176  AR_NoAlias,
177  AR_MayAlias,
178  AR_WillAliasEverything
179  };
180 
181  /// Returns AR_NoAlias if \p MI memory operation does not alias with
182  /// \p PrevMI, AR_MayAlias if they may alias and AR_WillAliasEverything if
183  /// they may alias and any further memory operation may alias with \p PrevMI.
184  AliasResult areMemoryOpsAliased(const MachineInstr &MI,
185  const MachineInstr *PrevMI) const;
186 
187  enum SuitabilityResult {
188  SR_Suitable,
189  SR_Unsuitable,
190  SR_Impossible
191  };
192 
193  /// Return SR_Suitable if \p MI a memory operation that can be used to
194  /// implicitly null check the value in \p PointerReg, SR_Unsuitable if
195  /// \p MI cannot be used to null check and SR_Impossible if there is
196  /// no sense to continue lookup due to any other instruction will not be able
197  /// to be used. \p PrevInsts is the set of instruction seen since
198  /// the explicit null check on \p PointerReg.
199  SuitabilityResult isSuitableMemoryOp(const MachineInstr &MI,
200  unsigned PointerReg,
201  ArrayRef<MachineInstr *> PrevInsts);
202 
203  /// Return true if \p FaultingMI can be hoisted from after the
204  /// instructions in \p InstsSeenSoFar to before them. Set \p Dependence to a
205  /// non-null value if we also need to (and legally can) hoist a depedency.
206  bool canHoistInst(MachineInstr *FaultingMI, unsigned PointerReg,
207  ArrayRef<MachineInstr *> InstsSeenSoFar,
209 
210 public:
211  static char ID;
212 
213  ImplicitNullChecks() : MachineFunctionPass(ID) {
215  }
216 
217  bool runOnMachineFunction(MachineFunction &MF) override;
218 
219  void getAnalysisUsage(AnalysisUsage &AU) const override {
222  }
223 
224  MachineFunctionProperties getRequiredProperties() const override {
227  }
228 };
229 
230 } // end anonymous namespace
231 
232 bool ImplicitNullChecks::canHandle(const MachineInstr *MI) {
233  if (MI->isCall() || MI->mayRaiseFPException() ||
235  return false;
236  auto IsRegMask = [](const MachineOperand &MO) { return MO.isRegMask(); };
237  (void)IsRegMask;
238 
239  assert(!llvm::any_of(MI->operands(), IsRegMask) &&
240  "Calls were filtered out above!");
241 
242  auto IsUnordered = [](MachineMemOperand *MMO) { return MMO->isUnordered(); };
243  return llvm::all_of(MI->memoperands(), IsUnordered);
244 }
245 
246 ImplicitNullChecks::DependenceResult
247 ImplicitNullChecks::computeDependence(const MachineInstr *MI,
248  ArrayRef<MachineInstr *> Block) {
249  assert(llvm::all_of(Block, canHandle) && "Check this first!");
250  assert(!is_contained(Block, MI) && "Block must be exclusive of MI!");
251 
253 
254  for (auto I = Block.begin(), E = Block.end(); I != E; ++I) {
255  if (canReorder(*I, MI))
256  continue;
257 
258  if (Dep == None) {
259  // Found one possible dependency, keep track of it.
260  Dep = I;
261  } else {
262  // We found two dependencies, so bail out.
263  return {false, None};
264  }
265  }
266 
267  return {true, Dep};
268 }
269 
270 bool ImplicitNullChecks::canReorder(const MachineInstr *A,
271  const MachineInstr *B) {
272  assert(canHandle(A) && canHandle(B) && "Precondition!");
273 
274  // canHandle makes sure that we _can_ correctly analyze the dependencies
275  // between A and B here -- for instance, we should not be dealing with heap
276  // load-store dependencies here.
277 
278  for (auto MOA : A->operands()) {
279  if (!(MOA.isReg() && MOA.getReg()))
280  continue;
281 
282  Register RegA = MOA.getReg();
283  for (auto MOB : B->operands()) {
284  if (!(MOB.isReg() && MOB.getReg()))
285  continue;
286 
287  Register RegB = MOB.getReg();
288 
289  if (TRI->regsOverlap(RegA, RegB) && (MOA.isDef() || MOB.isDef()))
290  return false;
291  }
292  }
293 
294  return true;
295 }
296 
297 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
298  TII = MF.getSubtarget().getInstrInfo();
299  TRI = MF.getRegInfo().getTargetRegisterInfo();
300  MFI = &MF.getFrameInfo();
301  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
302 
303  SmallVector<NullCheck, 16> NullCheckList;
304 
305  for (auto &MBB : MF)
306  analyzeBlockForNullChecks(MBB, NullCheckList);
307 
308  if (!NullCheckList.empty())
309  rewriteNullChecks(NullCheckList);
310 
311  return !NullCheckList.empty();
312 }
313 
314 // Return true if any register aliasing \p Reg is live-in into \p MBB.
315 static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI,
316  MachineBasicBlock *MBB, unsigned Reg) {
317  for (MCRegAliasIterator AR(Reg, TRI, /*IncludeSelf*/ true); AR.isValid();
318  ++AR)
319  if (MBB->isLiveIn(*AR))
320  return true;
321  return false;
322 }
323 
324 ImplicitNullChecks::AliasResult
325 ImplicitNullChecks::areMemoryOpsAliased(const MachineInstr &MI,
326  const MachineInstr *PrevMI) const {
327  // If it is not memory access, skip the check.
328  if (!(PrevMI->mayStore() || PrevMI->mayLoad()))
329  return AR_NoAlias;
330  // Load-Load may alias
331  if (!(MI.mayStore() || PrevMI->mayStore()))
332  return AR_NoAlias;
333  // We lost info, conservatively alias. If it was store then no sense to
334  // continue because we won't be able to check against it further.
335  if (MI.memoperands_empty())
336  return MI.mayStore() ? AR_WillAliasEverything : AR_MayAlias;
337  if (PrevMI->memoperands_empty())
338  return PrevMI->mayStore() ? AR_WillAliasEverything : AR_MayAlias;
339 
340  for (MachineMemOperand *MMO1 : MI.memoperands()) {
341  // MMO1 should have a value due it comes from operation we'd like to use
342  // as implicit null check.
343  assert(MMO1->getValue() && "MMO1 should have a Value!");
344  for (MachineMemOperand *MMO2 : PrevMI->memoperands()) {
345  if (const PseudoSourceValue *PSV = MMO2->getPseudoValue()) {
346  if (PSV->mayAlias(MFI))
347  return AR_MayAlias;
348  continue;
349  }
350  llvm::AliasResult AAResult =
351  AA->alias(MemoryLocation(MMO1->getValue(), LocationSize::unknown(),
352  MMO1->getAAInfo()),
353  MemoryLocation(MMO2->getValue(), LocationSize::unknown(),
354  MMO2->getAAInfo()));
355  if (AAResult != NoAlias)
356  return AR_MayAlias;
357  }
358  }
359  return AR_NoAlias;
360 }
361 
362 ImplicitNullChecks::SuitabilityResult
363 ImplicitNullChecks::isSuitableMemoryOp(const MachineInstr &MI,
364  unsigned PointerReg,
365  ArrayRef<MachineInstr *> PrevInsts) {
366  int64_t Offset;
367  bool OffsetIsScalable;
368  const MachineOperand *BaseOp;
369 
370 
371  if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable, TRI) ||
372  !BaseOp->isReg() || BaseOp->getReg() != PointerReg)
373  return SR_Unsuitable;
374 
375  // FIXME: This algorithm assumes instructions have fixed-size offsets.
376  if (OffsetIsScalable)
377  return SR_Unsuitable;
378 
379  // We want the mem access to be issued at a sane offset from PointerReg,
380  // so that if PointerReg is null then the access reliably page faults.
381  if (!(MI.mayLoadOrStore() && !MI.isPredicable() &&
382  -PageSize < Offset && Offset < PageSize))
383  return SR_Unsuitable;
384 
385  // Finally, check whether the current memory access aliases with previous one.
386  for (auto *PrevMI : PrevInsts) {
387  AliasResult AR = areMemoryOpsAliased(MI, PrevMI);
388  if (AR == AR_WillAliasEverything)
389  return SR_Impossible;
390  if (AR == AR_MayAlias)
391  return SR_Unsuitable;
392  }
393  return SR_Suitable;
394 }
395 
396 bool ImplicitNullChecks::canHoistInst(MachineInstr *FaultingMI,
397  unsigned PointerReg,
398  ArrayRef<MachineInstr *> InstsSeenSoFar,
399  MachineBasicBlock *NullSucc,
401  auto DepResult = computeDependence(FaultingMI, InstsSeenSoFar);
402  if (!DepResult.CanReorder)
403  return false;
404 
405  if (!DepResult.PotentialDependence) {
406  Dependence = nullptr;
407  return true;
408  }
409 
410  auto DependenceItr = *DepResult.PotentialDependence;
411  auto *DependenceMI = *DependenceItr;
412 
413  // We don't want to reason about speculating loads. Note -- at this point
414  // we should have already filtered out all of the other non-speculatable
415  // things, like calls and stores.
416  // We also do not want to hoist stores because it might change the memory
417  // while the FaultingMI may result in faulting.
418  assert(canHandle(DependenceMI) && "Should never have reached here!");
419  if (DependenceMI->mayLoadOrStore())
420  return false;
421 
422  for (auto &DependenceMO : DependenceMI->operands()) {
423  if (!(DependenceMO.isReg() && DependenceMO.getReg()))
424  continue;
425 
426  // Make sure that we won't clobber any live ins to the sibling block by
427  // hoisting Dependency. For instance, we can't hoist INST to before the
428  // null check (even if it safe, and does not violate any dependencies in
429  // the non_null_block) if %rdx is live in to _null_block.
430  //
431  // test %rcx, %rcx
432  // je _null_block
433  // _non_null_block:
434  // %rdx = INST
435  // ...
436  //
437  // This restriction does not apply to the faulting load inst because in
438  // case the pointer loaded from is in the null page, the load will not
439  // semantically execute, and affect machine state. That is, if the load
440  // was loading into %rax and it faults, the value of %rax should stay the
441  // same as it would have been had the load not have executed and we'd have
442  // branched to NullSucc directly.
443  if (AnyAliasLiveIn(TRI, NullSucc, DependenceMO.getReg()))
444  return false;
445 
446  // The Dependency can't be re-defining the base register -- then we won't
447  // get the memory operation on the address we want. This is already
448  // checked in \c IsSuitableMemoryOp.
449  assert(!(DependenceMO.isDef() &&
450  TRI->regsOverlap(DependenceMO.getReg(), PointerReg)) &&
451  "Should have been checked before!");
452  }
453 
454  auto DepDepResult =
455  computeDependence(DependenceMI, {InstsSeenSoFar.begin(), DependenceItr});
456 
457  if (!DepDepResult.CanReorder || DepDepResult.PotentialDependence)
458  return false;
459 
460  Dependence = DependenceMI;
461  return true;
462 }
463 
464 /// Analyze MBB to check if its terminating branch can be turned into an
465 /// implicit null check. If yes, append a description of the said null check to
466 /// NullCheckList and return true, else return false.
467 bool ImplicitNullChecks::analyzeBlockForNullChecks(
469  using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
470 
471  MDNode *BranchMD = nullptr;
472  if (auto *BB = MBB.getBasicBlock())
473  BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit);
474 
475  if (!BranchMD)
476  return false;
477 
478  MachineBranchPredicate MBP;
479 
480  if (TII->analyzeBranchPredicate(MBB, MBP, true))
481  return false;
482 
483  // Is the predicate comparing an integer to zero?
484  if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
485  (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
486  MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
487  return false;
488 
489  // If we cannot erase the test instruction itself, then making the null check
490  // implicit does not buy us much.
491  if (!MBP.SingleUseCondition)
492  return false;
493 
494  MachineBasicBlock *NotNullSucc, *NullSucc;
495 
496  if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
497  NotNullSucc = MBP.TrueDest;
498  NullSucc = MBP.FalseDest;
499  } else {
500  NotNullSucc = MBP.FalseDest;
501  NullSucc = MBP.TrueDest;
502  }
503 
504  // We handle the simplest case for now. We can potentially do better by using
505  // the machine dominator tree.
506  if (NotNullSucc->pred_size() != 1)
507  return false;
508 
509  // To prevent the invalid transformation of the following code:
510  //
511  // mov %rax, %rcx
512  // test %rax, %rax
513  // %rax = ...
514  // je throw_npe
515  // mov(%rcx), %r9
516  // mov(%rax), %r10
517  //
518  // into:
519  //
520  // mov %rax, %rcx
521  // %rax = ....
522  // faulting_load_op("movl (%rax), %r10", throw_npe)
523  // mov(%rcx), %r9
524  //
525  // we must ensure that there are no instructions between the 'test' and
526  // conditional jump that modify %rax.
527  const Register PointerReg = MBP.LHS.getReg();
528 
529  assert(MBP.ConditionDef->getParent() == &MBB && "Should be in basic block");
530 
531  for (auto I = MBB.rbegin(); MBP.ConditionDef != &*I; ++I)
532  if (I->modifiesRegister(PointerReg, TRI))
533  return false;
534 
535  // Starting with a code fragment like:
536  //
537  // test %rax, %rax
538  // jne LblNotNull
539  //
540  // LblNull:
541  // callq throw_NullPointerException
542  //
543  // LblNotNull:
544  // Inst0
545  // Inst1
546  // ...
547  // Def = Load (%rax + <offset>)
548  // ...
549  //
550  //
551  // we want to end up with
552  //
553  // Def = FaultingLoad (%rax + <offset>), LblNull
554  // jmp LblNotNull ;; explicit or fallthrough
555  //
556  // LblNotNull:
557  // Inst0
558  // Inst1
559  // ...
560  //
561  // LblNull:
562  // callq throw_NullPointerException
563  //
564  //
565  // To see why this is legal, consider the two possibilities:
566  //
567  // 1. %rax is null: since we constrain <offset> to be less than PageSize, the
568  // load instruction dereferences the null page, causing a segmentation
569  // fault.
570  //
571  // 2. %rax is not null: in this case we know that the load cannot fault, as
572  // otherwise the load would've faulted in the original program too and the
573  // original program would've been undefined.
574  //
575  // This reasoning cannot be extended to justify hoisting through arbitrary
576  // control flow. For instance, in the example below (in pseudo-C)
577  //
578  // if (ptr == null) { throw_npe(); unreachable; }
579  // if (some_cond) { return 42; }
580  // v = ptr->field; // LD
581  // ...
582  //
583  // we cannot (without code duplication) use the load marked "LD" to null check
584  // ptr -- clause (2) above does not apply in this case. In the above program
585  // the safety of ptr->field can be dependent on some_cond; and, for instance,
586  // ptr could be some non-null invalid reference that never gets loaded from
587  // because some_cond is always true.
588 
589  SmallVector<MachineInstr *, 8> InstsSeenSoFar;
590 
591  for (auto &MI : *NotNullSucc) {
592  if (!canHandle(&MI) || InstsSeenSoFar.size() >= MaxInstsToConsider)
593  return false;
594 
595  MachineInstr *Dependence;
596  SuitabilityResult SR = isSuitableMemoryOp(MI, PointerReg, InstsSeenSoFar);
597  if (SR == SR_Impossible)
598  return false;
599  if (SR == SR_Suitable &&
600  canHoistInst(&MI, PointerReg, InstsSeenSoFar, NullSucc, Dependence)) {
601  NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc,
602  NullSucc, Dependence);
603  return true;
604  }
605 
606  // If MI re-defines the PointerReg then we cannot move further.
607  if (llvm::any_of(MI.operands(), [&](MachineOperand &MO) {
608  return MO.isReg() && MO.getReg() && MO.isDef() &&
609  TRI->regsOverlap(MO.getReg(), PointerReg);
610  }))
611  return false;
612  InstsSeenSoFar.push_back(&MI);
613  }
614 
615  return false;
616 }
617 
618 /// Wrap a machine instruction, MI, into a FAULTING machine instruction.
619 /// The FAULTING instruction does the same load/store as MI
620 /// (defining the same register), and branches to HandlerMBB if the mem access
621 /// faults. The FAULTING instruction is inserted at the end of MBB.
622 MachineInstr *ImplicitNullChecks::insertFaultingInstr(
623  MachineInstr *MI, MachineBasicBlock *MBB, MachineBasicBlock *HandlerMBB) {
624  const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for
625  // all targets.
626 
627  DebugLoc DL;
628  unsigned NumDefs = MI->getDesc().getNumDefs();
629  assert(NumDefs <= 1 && "other cases unhandled!");
630 
631  unsigned DefReg = NoRegister;
632  if (NumDefs != 0) {
633  DefReg = MI->getOperand(0).getReg();
634  assert(NumDefs == 1 && "expected exactly one def!");
635  }
636 
638  if (MI->mayLoad())
639  FK =
641  else
643 
644  auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_OP), DefReg)
645  .addImm(FK)
646  .addMBB(HandlerMBB)
647  .addImm(MI->getOpcode());
648 
649  for (auto &MO : MI->uses()) {
650  if (MO.isReg()) {
651  MachineOperand NewMO = MO;
652  if (MO.isUse()) {
653  NewMO.setIsKill(false);
654  } else {
655  assert(MO.isDef() && "Expected def or use");
656  NewMO.setIsDead(false);
657  }
658  MIB.add(NewMO);
659  } else {
660  MIB.add(MO);
661  }
662  }
663 
664  MIB.setMemRefs(MI->memoperands());
665 
666  return MIB;
667 }
668 
669 /// Rewrite the null checks in NullCheckList into implicit null checks.
670 void ImplicitNullChecks::rewriteNullChecks(
672  DebugLoc DL;
673 
674  for (auto &NC : NullCheckList) {
675  // Remove the conditional branch dependent on the null check.
676  unsigned BranchesRemoved = TII->removeBranch(*NC.getCheckBlock());
677  (void)BranchesRemoved;
678  assert(BranchesRemoved > 0 && "expected at least one branch!");
679 
680  if (auto *DepMI = NC.getOnlyDependency()) {
681  DepMI->removeFromParent();
682  NC.getCheckBlock()->insert(NC.getCheckBlock()->end(), DepMI);
683  }
684 
685  // Insert a faulting instruction where the conditional branch was
686  // originally. We check earlier ensures that this bit of code motion
687  // is legal. We do not touch the successors list for any basic block
688  // since we haven't changed control flow, we've just made it implicit.
689  MachineInstr *FaultingInstr = insertFaultingInstr(
690  NC.getMemOperation(), NC.getCheckBlock(), NC.getNullSucc());
691  // Now the values defined by MemOperation, if any, are live-in of
692  // the block of MemOperation.
693  // The original operation may define implicit-defs alongside
694  // the value.
695  MachineBasicBlock *MBB = NC.getMemOperation()->getParent();
696  for (const MachineOperand &MO : FaultingInstr->operands()) {
697  if (!MO.isReg() || !MO.isDef())
698  continue;
699  Register Reg = MO.getReg();
700  if (!Reg || MBB->isLiveIn(Reg))
701  continue;
702  MBB->addLiveIn(Reg);
703  }
704 
705  if (auto *DepMI = NC.getOnlyDependency()) {
706  for (auto &MO : DepMI->operands()) {
707  if (!MO.isReg() || !MO.getReg() || !MO.isDef() || MO.isDead())
708  continue;
709  if (!NC.getNotNullSucc()->isLiveIn(MO.getReg()))
710  NC.getNotNullSucc()->addLiveIn(MO.getReg());
711  }
712  }
713 
714  NC.getMemOperation()->eraseFromParent();
715  NC.getCheckOperation()->eraseFromParent();
716 
717  // Insert an *unconditional* branch to not-null successor.
718  TII->insertBranch(*NC.getCheckBlock(), NC.getNotNullSucc(), nullptr,
719  /*Cond=*/None, DL);
720 
721  NumImplicitNullChecks++;
722  }
723 }
724 
725 char ImplicitNullChecks::ID = 0;
726 
728 
729 INITIALIZE_PASS_BEGIN(ImplicitNullChecks, DEBUG_TYPE,
730  "Implicit null checks", false, false)
732 INITIALIZE_PASS_END(ImplicitNullChecks, DEBUG_TYPE,
733  "Implicit null checks", false, false)
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:687
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:760
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:603
iterator begin() const
Definition: ArrayRef.h:144
static constexpr LocationSize unknown()
unsigned Reg
bool isPredicable(QueryType Type=AllInBundle) const
Return true if this instruction has a predicate operand that controls execution.
Definition: MachineInstr.h:822
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 mayLoadOrStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read or modify memory.
Definition: MachineInstr.h:965
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:1491
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
A debug info location.
Definition: DebugLoc.h:33
Metadata node.
Definition: Metadata.h:870
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:559
virtual unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const
Remove the branching code at the end of the specific MBB.
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
Represents a predicate at the MachineFunction level.
MachineBasicBlock & MBB
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
AnalysisUsage & addRequired()
A description of a memory reference used in the backend.
bool getMemOperandWithOffset(const MachineInstr &MI, const MachineOperand *&BaseOp, int64_t &Offset, bool &OffsetIsScalable, const TargetRegisterInfo *TRI) const
Get the base operand and byte offset of an instruction that reads/writes memory.
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:43
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:456
bool regsOverlap(Register regA, Register regB) const
Returns true if the two registers are equal or alias each other.
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:453
bool mayRaiseFPException() const
Return true if this instruction could possibly raise a floating-point exception.
Definition: MachineInstr.h:975
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:955
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:434
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:627
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:1498
void initializeImplicitNullChecksPass(PassRegistry &)
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
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.
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:883
iterator end() const
Definition: ArrayRef.h:145
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:235
#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:62
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
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...
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:62
static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI, MachineBasicBlock *MBB, unsigned Reg)
#define I(x, y, z)
Definition: MD5.cpp:59
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:942
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:657
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
Register getReg() const
getReg - Returns the register number.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
Dependence - This class represents a dependence between two memory memory references in a function...
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:466
Properties which a MachineFunction may have at a given point in time.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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:1549