contrib/llvm/lib/CodeGen/ImplicitNullChecks.cpp

   1 //===-- ImplicitNullChecks.cpp - Fold null checks into memory accesses ----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass turns explicit null checks of the form
  11 //
  12 //   test %r10, %r10
  13 //   je throw_npe
  14 //   movl (%r10), %esi
  15 //   ...
  16 //
  17 // to
  18 //
  19 //   faulting_load_op("movl (%r10), %esi", throw_npe)
  20 //   ...
  21 //
  22 // With the help of a runtime that understands the .fault_maps section,
  23 // faulting_load_op branches to throw_npe if executing movl (%r10), %esi incurs
  24 // a page fault.
  25 // Store and LoadStore are also supported.
  26 //
  27 //===----------------------------------------------------------------------===//
  28
  29 #include "llvm/ADT/DenseSet.h"
  30 #include "llvm/ADT/SmallVector.h"
  31 #include "llvm/ADT/Statistic.h"
  32 #include "llvm/Analysis/AliasAnalysis.h"
  33 #include "llvm/CodeGen/FaultMaps.h"
  34 #include "llvm/CodeGen/Passes.h"
  35 #include "llvm/CodeGen/MachineFunction.h"
  36 #include "llvm/CodeGen/MachineMemOperand.h"
  37 #include "llvm/CodeGen/MachineOperand.h"
  38 #include "llvm/CodeGen/MachineFunctionPass.h"
  39 #include "llvm/CodeGen/MachineInstrBuilder.h"
  40 #include "llvm/CodeGen/MachineRegisterInfo.h"
  41 #include "llvm/CodeGen/MachineModuleInfo.h"
  42 #include "llvm/IR/BasicBlock.h"
  43 #include "llvm/IR/Instruction.h"
  44 #include "llvm/IR/LLVMContext.h"
  45 #include "llvm/Support/CommandLine.h"
  46 #include "llvm/Support/Debug.h"
  47 #include "llvm/Target/TargetSubtargetInfo.h"
  48 #include "llvm/Target/TargetInstrInfo.h"
  49
  50 using namespace llvm;
  51
  52 static cl::opt<int> PageSize("imp-null-check-page-size",
  53                              cl::desc("The page size of the target in bytes"),
  54                              cl::init(4096));
  55
  56 static cl::opt<unsigned> MaxInstsToConsider(
  57     "imp-null-max-insts-to-consider",
  58     cl::desc("The max number of instructions to consider hoisting loads over "
  59              "(the algorithm is quadratic over this number)"),
  60     cl::init(8));
  61
  62 #define DEBUG_TYPE "implicit-null-checks"
  63
  64 STATISTIC(NumImplicitNullChecks,
  65           "Number of explicit null checks made implicit");
  66
  67 namespace {
  68
  69 class ImplicitNullChecks : public MachineFunctionPass {
  70   /// Return true if \c computeDependence can process \p MI.
  71   static bool canHandle(const MachineInstr *MI);
  72
  73   /// Helper function for \c computeDependence.  Return true if \p A
  74   /// and \p B do not have any dependences between them, and can be
  75   /// re-ordered without changing program semantics.
  76   bool canReorder(const MachineInstr *A, const MachineInstr *B);
  77
  78   /// A data type for representing the result computed by \c
  79   /// computeDependence.  States whether it is okay to reorder the
  80   /// instruction passed to \c computeDependence with at most one
  81   /// depednency.
  82   struct DependenceResult {
  83     /// Can we actually re-order \p MI with \p Insts (see \c
  84     /// computeDependence).
  85     bool CanReorder;
  86
  87     /// If non-None, then an instruction in \p Insts that also must be
  88     /// hoisted.
  89     Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence;
  90
  91     /*implicit*/ DependenceResult(
  92         bool CanReorder,
  93         Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence)
  94         : CanReorder(CanReorder), PotentialDependence(PotentialDependence) {
  95       assert((!PotentialDependence || CanReorder) &&
  96              "!CanReorder && PotentialDependence.hasValue() not allowed!");
  97     }
  98   };
  99
 100   /// Compute a result for the following question: can \p MI be
 101   /// re-ordered from after \p Insts to before it.
 102   ///
 103   /// \c canHandle should return true for all instructions in \p
 104   /// Insts.
 105   DependenceResult computeDependence(const MachineInstr *MI,
 106                                      ArrayRef<MachineInstr *> Insts);
 107
 108   /// Represents one null check that can be made implicit.
 109   class NullCheck {
 110     // The memory operation the null check can be folded into.
 111     MachineInstr *MemOperation;
 112
 113     // The instruction actually doing the null check (Ptr != 0).
 114     MachineInstr *CheckOperation;
 115
 116     // The block the check resides in.
 117     MachineBasicBlock *CheckBlock;
 118
 119     // The block branched to if the pointer is non-null.
 120     MachineBasicBlock *NotNullSucc;
 121
 122     // The block branched to if the pointer is null.
 123     MachineBasicBlock *NullSucc;
 124
 125     // If this is non-null, then MemOperation has a dependency on on this
 126     // instruction; and it needs to be hoisted to execute before MemOperation.
 127     MachineInstr *OnlyDependency;
 128
 129   public:
 130     explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation,
 131                        MachineBasicBlock *checkBlock,
 132                        MachineBasicBlock *notNullSucc,
 133                        MachineBasicBlock *nullSucc,
 134                        MachineInstr *onlyDependency)
 135         : MemOperation(memOperation), CheckOperation(checkOperation),
 136           CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc),
 137           OnlyDependency(onlyDependency) {}
 138
 139     MachineInstr *getMemOperation() const { return MemOperation; }
 140
 141     MachineInstr *getCheckOperation() const { return CheckOperation; }
 142
 143     MachineBasicBlock *getCheckBlock() const { return CheckBlock; }
 144
 145     MachineBasicBlock *getNotNullSucc() const { return NotNullSucc; }
 146
 147     MachineBasicBlock *getNullSucc() const { return NullSucc; }
 148
 149     MachineInstr *getOnlyDependency() const { return OnlyDependency; }
 150   };
 151
 152   const TargetInstrInfo *TII = nullptr;
 153   const TargetRegisterInfo *TRI = nullptr;
 154   AliasAnalysis *AA = nullptr;
 155   MachineModuleInfo *MMI = nullptr;
 156   MachineFrameInfo *MFI = nullptr;
 157
 158   bool analyzeBlockForNullChecks(MachineBasicBlock &MBB,
 159                                  SmallVectorImpl<NullCheck> &NullCheckList);
 160   MachineInstr *insertFaultingInstr(MachineInstr *MI, MachineBasicBlock *MBB,
 161                                     MachineBasicBlock *HandlerMBB);
 162   void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList);
 163
 164   enum AliasResult {
 165     AR_NoAlias,
 166     AR_MayAlias,
 167     AR_WillAliasEverything
 168   };
 169   /// Returns AR_NoAlias if \p MI memory operation does not alias with
 170   /// \p PrevMI, AR_MayAlias if they may alias and AR_WillAliasEverything if
 171   /// they may alias and any further memory operation may alias with \p PrevMI.
 172   AliasResult areMemoryOpsAliased(MachineInstr &MI, MachineInstr *PrevMI);
 173
 174   enum SuitabilityResult {
 175     SR_Suitable,
 176     SR_Unsuitable,
 177     SR_Impossible
 178   };
 179   /// Return SR_Suitable if \p MI a memory operation that can be used to
 180   /// implicitly null check the value in \p PointerReg, SR_Unsuitable if
 181   /// \p MI cannot be used to null check and SR_Impossible if there is
 182   /// no sense to continue lookup due to any other instruction will not be able
 183   /// to be used. \p PrevInsts is the set of instruction seen since
 184   /// the explicit null check on \p PointerReg.
 185   SuitabilityResult isSuitableMemoryOp(MachineInstr &MI, unsigned PointerReg,
 186                                        ArrayRef<MachineInstr *> PrevInsts);
 187
 188   /// Return true if \p FaultingMI can be hoisted from after the the
 189   /// instructions in \p InstsSeenSoFar to before them.  Set \p Dependence to a
 190   /// non-null value if we also need to (and legally can) hoist a depedency.
 191   bool canHoistInst(MachineInstr *FaultingMI, unsigned PointerReg,
 192                     ArrayRef<MachineInstr *> InstsSeenSoFar,
 193                     MachineBasicBlock *NullSucc, MachineInstr *&Dependence);
 194
 195 public:
 196   static char ID;
 197
 198   ImplicitNullChecks() : MachineFunctionPass(ID) {
 199     initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry());
 200   }
 201
 202   bool runOnMachineFunction(MachineFunction &MF) override;
 203   void getAnalysisUsage(AnalysisUsage &AU) const override {
 204     AU.addRequired<AAResultsWrapperPass>();
 205     MachineFunctionPass::getAnalysisUsage(AU);
 206   }
 207
 208   MachineFunctionProperties getRequiredProperties() const override {
 209     return MachineFunctionProperties().set(
 210         MachineFunctionProperties::Property::NoVRegs);
 211   }
 212 };
 213
 214 }
 215
 216 bool ImplicitNullChecks::canHandle(const MachineInstr *MI) {
 217   if (MI->isCall() || MI->hasUnmodeledSideEffects())
 218     return false;
 219   auto IsRegMask = [](const MachineOperand &MO) { return MO.isRegMask(); };
 220   (void)IsRegMask;
 221
 222   assert(!llvm::any_of(MI->operands(), IsRegMask) &&
 223          "Calls were filtered out above!");
 224
 225   auto IsUnordered = [](MachineMemOperand *MMO) { return MMO->isUnordered(); };
 226   return llvm::all_of(MI->memoperands(), IsUnordered);
 227 }
 228
 229 ImplicitNullChecks::DependenceResult
 230 ImplicitNullChecks::computeDependence(const MachineInstr *MI,
 231                                       ArrayRef<MachineInstr *> Block) {
 232   assert(llvm::all_of(Block, canHandle) && "Check this first!");
 233   assert(!llvm::is_contained(Block, MI) && "Block must be exclusive of MI!");
 234
 235   Optional<ArrayRef<MachineInstr *>::iterator> Dep;
 236
 237   for (auto I = Block.begin(), E = Block.end(); I != E; ++I) {
 238     if (canReorder(*I, MI))
 239       continue;
 240
 241     if (Dep == None) {
 242       // Found one possible dependency, keep track of it.
 243       Dep = I;
 244     } else {
 245       // We found two dependencies, so bail out.
 246       return {false, None};
 247     }
 248   }
 249
 250   return {true, Dep};
 251 }
 252
 253 bool ImplicitNullChecks::canReorder(const MachineInstr *A,
 254                                     const MachineInstr *B) {
 255   assert(canHandle(A) && canHandle(B) && "Precondition!");
 256
 257   // canHandle makes sure that we _can_ correctly analyze the dependencies
 258   // between A and B here -- for instance, we should not be dealing with heap
 259   // load-store dependencies here.
 260
 261   for (auto MOA : A->operands()) {
 262     if (!(MOA.isReg() && MOA.getReg()))
 263       continue;
 264
 265     unsigned RegA = MOA.getReg();
 266     for (auto MOB : B->operands()) {
 267       if (!(MOB.isReg() && MOB.getReg()))
 268         continue;
 269
 270       unsigned RegB = MOB.getReg();
 271
 272       if (TRI->regsOverlap(RegA, RegB) && (MOA.isDef() || MOB.isDef()))
 273         return false;
 274     }
 275   }
 276
 277   return true;
 278 }
 279
 280 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
 281   TII = MF.getSubtarget().getInstrInfo();
 282   TRI = MF.getRegInfo().getTargetRegisterInfo();
 283   MMI = &MF.getMMI();
 284   MFI = &MF.getFrameInfo();
 285   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 286
 287   SmallVector<NullCheck, 16> NullCheckList;
 288
 289   for (auto &MBB : MF)
 290     analyzeBlockForNullChecks(MBB, NullCheckList);
 291
 292   if (!NullCheckList.empty())
 293     rewriteNullChecks(NullCheckList);
 294
 295   return !NullCheckList.empty();
 296 }
 297
 298 // Return true if any register aliasing \p Reg is live-in into \p MBB.
 299 static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI,
 300                            MachineBasicBlock *MBB, unsigned Reg) {
 301   for (MCRegAliasIterator AR(Reg, TRI, /*IncludeSelf*/ true); AR.isValid();
 302        ++AR)
 303     if (MBB->isLiveIn(*AR))
 304       return true;
 305   return false;
 306 }
 307
 308 ImplicitNullChecks::AliasResult
 309 ImplicitNullChecks::areMemoryOpsAliased(MachineInstr &MI,
 310                                         MachineInstr *PrevMI) {
 311   // If it is not memory access, skip the check.
 312   if (!(PrevMI->mayStore() || PrevMI->mayLoad()))
 313     return AR_NoAlias;
 314   // Load-Load may alias
 315   if (!(MI.mayStore() || PrevMI->mayStore()))
 316     return AR_NoAlias;
 317   // We lost info, conservatively alias. If it was store then no sense to
 318   // continue because we won't be able to check against it further.
 319   if (MI.memoperands_empty())
 320     return MI.mayStore() ? AR_WillAliasEverything : AR_MayAlias;
 321   if (PrevMI->memoperands_empty())
 322     return PrevMI->mayStore() ? AR_WillAliasEverything : AR_MayAlias;
 323
 324   for (MachineMemOperand *MMO1 : MI.memoperands()) {
 325     // MMO1 should have a value due it comes from operation we'd like to use
 326     // as implicit null check.
 327     assert(MMO1->getValue() && "MMO1 should have a Value!");
 328     for (MachineMemOperand *MMO2 : PrevMI->memoperands()) {
 329       if (const PseudoSourceValue *PSV = MMO2->getPseudoValue()) {
 330         if (PSV->mayAlias(MFI))
 331           return AR_MayAlias;
 332         continue;
 333       }
 334       llvm::AliasResult AAResult = AA->alias(
 335           MemoryLocation(MMO1->getValue(), MemoryLocation::UnknownSize,
 336                          MMO1->getAAInfo()),
 337           MemoryLocation(MMO2->getValue(), MemoryLocation::UnknownSize,
 338                          MMO2->getAAInfo()));
 339       if (AAResult != NoAlias)
 340         return AR_MayAlias;
 341     }
 342   }
 343   return AR_NoAlias;
 344 }
 345
 346 ImplicitNullChecks::SuitabilityResult
 347 ImplicitNullChecks::isSuitableMemoryOp(MachineInstr &MI, unsigned PointerReg,
 348                                        ArrayRef<MachineInstr *> PrevInsts) {
 349   int64_t Offset;
 350   unsigned BaseReg;
 351
 352   if (!TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI) ||
 353       BaseReg != PointerReg)
 354     return SR_Unsuitable;
 355
 356   // We want the mem access to be issued at a sane offset from PointerReg,
 357   // so that if PointerReg is null then the access reliably page faults.
 358   if (!((MI.mayLoad() || MI.mayStore()) && !MI.isPredicable() &&
 359         Offset < PageSize))
 360     return SR_Unsuitable;
 361
 362   // Finally, we need to make sure that the access instruction actually is
 363   // accessing from PointerReg, and there isn't some re-definition of PointerReg
 364   // between the compare and the memory access.
 365   // If PointerReg has been redefined before then there is no sense to continue
 366   // lookup due to this condition will fail for any further instruction.
 367   SuitabilityResult Suitable = SR_Suitable;
 368   for (auto *PrevMI : PrevInsts)
 369     for (auto &PrevMO : PrevMI->operands()) {
 370       if (PrevMO.isReg() && PrevMO.getReg() && PrevMO.isDef() &&
 371           TRI->regsOverlap(PrevMO.getReg(), PointerReg))
 372         return SR_Impossible;
 373
 374       // Check whether the current memory access aliases with previous one.
 375       // If we already found that it aliases then no need to continue.
 376       // But we continue base pointer check as it can result in SR_Impossible.
 377       if (Suitable == SR_Suitable) {
 378         AliasResult AR = areMemoryOpsAliased(MI, PrevMI);
 379         if (AR == AR_WillAliasEverything)
 380           return SR_Impossible;
 381         if (AR == AR_MayAlias)
 382           Suitable = SR_Unsuitable;
 383       }
 384     }
 385   return Suitable;
 386 }
 387
 388 bool ImplicitNullChecks::canHoistInst(MachineInstr *FaultingMI,
 389                                       unsigned PointerReg,
 390                                       ArrayRef<MachineInstr *> InstsSeenSoFar,
 391                                       MachineBasicBlock *NullSucc,
 392                                       MachineInstr *&Dependence) {
 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   assert(canHandle(DependenceMI) && "Should never have reached here!");
 409   if (DependenceMI->mayLoad())
 410     return false;
 411
 412   for (auto &DependenceMO : DependenceMI->operands()) {
 413     if (!(DependenceMO.isReg() && DependenceMO.getReg()))
 414       continue;
 415
 416     // Make sure that we won't clobber any live ins to the sibling block by
 417     // hoisting Dependency.  For instance, we can't hoist INST to before the
 418     // null check (even if it safe, and does not violate any dependencies in
 419     // the non_null_block) if %rdx is live in to _null_block.
 420     //
 421     //    test %rcx, %rcx
 422     //    je _null_block
 423     //  _non_null_block:
 424     //    %rdx<def> = INST
 425     //    ...
 426     //
 427     // This restriction does not apply to the faulting load inst because in
 428     // case the pointer loaded from is in the null page, the load will not
 429     // semantically execute, and affect machine state.  That is, if the load
 430     // was loading into %rax and it faults, the value of %rax should stay the
 431     // same as it would have been had the load not have executed and we'd have
 432     // branched to NullSucc directly.
 433     if (AnyAliasLiveIn(TRI, NullSucc, DependenceMO.getReg()))
 434       return false;
 435
 436     // The Dependency can't be re-defining the base register -- then we won't
 437     // get the memory operation on the address we want.  This is already
 438     // checked in \c IsSuitableMemoryOp.
 439     assert(!(DependenceMO.isDef() &&
 440              TRI->regsOverlap(DependenceMO.getReg(), PointerReg)) &&
 441            "Should have been checked before!");
 442   }
 443
 444   auto DepDepResult =
 445       computeDependence(DependenceMI, {InstsSeenSoFar.begin(), DependenceItr});
 446
 447   if (!DepDepResult.CanReorder || DepDepResult.PotentialDependence)
 448     return false;
 449
 450   Dependence = DependenceMI;
 451   return true;
 452 }
 453
 454 /// Analyze MBB to check if its terminating branch can be turned into an
 455 /// implicit null check.  If yes, append a description of the said null check to
 456 /// NullCheckList and return true, else return false.
 457 bool ImplicitNullChecks::analyzeBlockForNullChecks(
 458     MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
 459   typedef TargetInstrInfo::MachineBranchPredicate MachineBranchPredicate;
 460
 461   MDNode *BranchMD = nullptr;
 462   if (auto *BB = MBB.getBasicBlock())
 463     BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit);
 464
 465   if (!BranchMD)
 466     return false;
 467
 468   MachineBranchPredicate MBP;
 469
 470   if (TII->analyzeBranchPredicate(MBB, MBP, true))
 471     return false;
 472
 473   // Is the predicate comparing an integer to zero?
 474   if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
 475         (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
 476          MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
 477     return false;
 478
 479   // If we cannot erase the test instruction itself, then making the null check
 480   // implicit does not buy us much.
 481   if (!MBP.SingleUseCondition)
 482     return false;
 483
 484   MachineBasicBlock *NotNullSucc, *NullSucc;
 485
 486   if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
 487     NotNullSucc = MBP.TrueDest;
 488     NullSucc = MBP.FalseDest;
 489   } else {
 490     NotNullSucc = MBP.FalseDest;
 491     NullSucc = MBP.TrueDest;
 492   }
 493
 494   // We handle the simplest case for now.  We can potentially do better by using
 495   // the machine dominator tree.
 496   if (NotNullSucc->pred_size() != 1)
 497     return false;
 498
 499   // Starting with a code fragment like:
 500   //
 501   //   test %RAX, %RAX
 502   //   jne LblNotNull
 503   //
 504   //  LblNull:
 505   //   callq throw_NullPointerException
 506   //
 507   //  LblNotNull:
 508   //   Inst0
 509   //   Inst1
 510   //   ...
 511   //   Def = Load (%RAX + <offset>)
 512   //   ...
 513   //
 514   //
 515   // we want to end up with
 516   //
 517   //   Def = FaultingLoad (%RAX + <offset>), LblNull
 518   //   jmp LblNotNull ;; explicit or fallthrough
 519   //
 520   //  LblNotNull:
 521   //   Inst0
 522   //   Inst1
 523   //   ...
 524   //
 525   //  LblNull:
 526   //   callq throw_NullPointerException
 527   //
 528   //
 529   // To see why this is legal, consider the two possibilities:
 530   //
 531   //  1. %RAX is null: since we constrain <offset> to be less than PageSize, the
 532   //     load instruction dereferences the null page, causing a segmentation
 533   //     fault.
 534   //
 535   //  2. %RAX is not null: in this case we know that the load cannot fault, as
 536   //     otherwise the load would've faulted in the original program too and the
 537   //     original program would've been undefined.
 538   //
 539   // This reasoning cannot be extended to justify hoisting through arbitrary
 540   // control flow.  For instance, in the example below (in pseudo-C)
 541   //
 542   //    if (ptr == null) { throw_npe(); unreachable; }
 543   //    if (some_cond) { return 42; }
 544   //    v = ptr->field;  // LD
 545   //    ...
 546   //
 547   // we cannot (without code duplication) use the load marked "LD" to null check
 548   // ptr -- clause (2) above does not apply in this case.  In the above program
 549   // the safety of ptr->field can be dependent on some_cond; and, for instance,
 550   // ptr could be some non-null invalid reference that never gets loaded from
 551   // because some_cond is always true.
 552
 553   const unsigned PointerReg = MBP.LHS.getReg();
 554
 555   SmallVector<MachineInstr *, 8> InstsSeenSoFar;
 556
 557   for (auto &MI : *NotNullSucc) {
 558     if (!canHandle(&MI) || InstsSeenSoFar.size() >= MaxInstsToConsider)
 559       return false;
 560
 561     MachineInstr *Dependence;
 562     SuitabilityResult SR = isSuitableMemoryOp(MI, PointerReg, InstsSeenSoFar);
 563     if (SR == SR_Impossible)
 564       return false;
 565     if (SR == SR_Suitable &&
 566         canHoistInst(&MI, PointerReg, InstsSeenSoFar, NullSucc, Dependence)) {
 567       NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc,
 568                                  NullSucc, Dependence);
 569       return true;
 570     }
 571
 572     InstsSeenSoFar.push_back(&MI);
 573   }
 574
 575   return false;
 576 }
 577
 578 /// Wrap a machine instruction, MI, into a FAULTING machine instruction.
 579 /// The FAULTING instruction does the same load/store as MI
 580 /// (defining the same register), and branches to HandlerMBB if the mem access
 581 /// faults.  The FAULTING instruction is inserted at the end of MBB.
 582 MachineInstr *ImplicitNullChecks::insertFaultingInstr(
 583     MachineInstr *MI, MachineBasicBlock *MBB, MachineBasicBlock *HandlerMBB) {
 584   const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for
 585                                  // all targets.
 586
 587   DebugLoc DL;
 588   unsigned NumDefs = MI->getDesc().getNumDefs();
 589   assert(NumDefs <= 1 && "other cases unhandled!");
 590
 591   unsigned DefReg = NoRegister;
 592   if (NumDefs != 0) {
 593     DefReg = MI->defs().begin()->getReg();
 594     assert(std::distance(MI->defs().begin(), MI->defs().end()) == 1 &&
 595            "expected exactly one def!");
 596   }
 597
 598   FaultMaps::FaultKind FK;
 599   if (MI->mayLoad())
 600     FK =
 601         MI->mayStore() ? FaultMaps::FaultingLoadStore : FaultMaps::FaultingLoad;
 602   else
 603     FK = FaultMaps::FaultingStore;
 604
 605   auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_OP), DefReg)
 606                  .addImm(FK)
 607                  .addMBB(HandlerMBB)
 608                  .addImm(MI->getOpcode());
 609
 610   for (auto &MO : MI->uses())
 611     MIB.add(MO);
 612
 613   MIB.setMemRefs(MI->memoperands_begin(), MI->memoperands_end());
 614
 615   return MIB;
 616 }
 617
 618 /// Rewrite the null checks in NullCheckList into implicit null checks.
 619 void ImplicitNullChecks::rewriteNullChecks(
 620     ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
 621   DebugLoc DL;
 622
 623   for (auto &NC : NullCheckList) {
 624     // Remove the conditional branch dependent on the null check.
 625     unsigned BranchesRemoved = TII->removeBranch(*NC.getCheckBlock());
 626     (void)BranchesRemoved;
 627     assert(BranchesRemoved > 0 && "expected at least one branch!");
 628
 629     if (auto *DepMI = NC.getOnlyDependency()) {
 630       DepMI->removeFromParent();
 631       NC.getCheckBlock()->insert(NC.getCheckBlock()->end(), DepMI);
 632     }
 633
 634     // Insert a faulting instruction where the conditional branch was
 635     // originally. We check earlier ensures that this bit of code motion
 636     // is legal.  We do not touch the successors list for any basic block
 637     // since we haven't changed control flow, we've just made it implicit.
 638     MachineInstr *FaultingInstr = insertFaultingInstr(
 639         NC.getMemOperation(), NC.getCheckBlock(), NC.getNullSucc());
 640     // Now the values defined by MemOperation, if any, are live-in of
 641     // the block of MemOperation.
 642     // The original operation may define implicit-defs alongside
 643     // the value.
 644     MachineBasicBlock *MBB = NC.getMemOperation()->getParent();
 645     for (const MachineOperand &MO : FaultingInstr->operands()) {
 646       if (!MO.isReg() || !MO.isDef())
 647         continue;
 648       unsigned Reg = MO.getReg();
 649       if (!Reg || MBB->isLiveIn(Reg))
 650         continue;
 651       MBB->addLiveIn(Reg);
 652     }
 653
 654     if (auto *DepMI = NC.getOnlyDependency()) {
 655       for (auto &MO : DepMI->operands()) {
 656         if (!MO.isReg() || !MO.getReg() || !MO.isDef())
 657           continue;
 658         if (!NC.getNotNullSucc()->isLiveIn(MO.getReg()))
 659           NC.getNotNullSucc()->addLiveIn(MO.getReg());
 660       }
 661     }
 662
 663     NC.getMemOperation()->eraseFromParent();
 664     NC.getCheckOperation()->eraseFromParent();
 665
 666     // Insert an *unconditional* branch to not-null successor.
 667     TII->insertBranch(*NC.getCheckBlock(), NC.getNotNullSucc(), nullptr,
 668                       /*Cond=*/None, DL);
 669
 670     NumImplicitNullChecks++;
 671   }
 672 }
 673
 674
 675 char ImplicitNullChecks::ID = 0;
 676 char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID;
 677 INITIALIZE_PASS_BEGIN(ImplicitNullChecks, "implicit-null-checks",
 678                       "Implicit null checks", false, false)
 679 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 680 INITIALIZE_PASS_END(ImplicitNullChecks, "implicit-null-checks",
 681                     "Implicit null checks", false, false)