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 //
  26 //===----------------------------------------------------------------------===//
  27
  28 #include "llvm/ADT/DenseSet.h"
  29 #include "llvm/ADT/SmallVector.h"
  30 #include "llvm/ADT/Statistic.h"
  31 #include "llvm/Analysis/AliasAnalysis.h"
  32 #include "llvm/CodeGen/Passes.h"
  33 #include "llvm/CodeGen/MachineFunction.h"
  34 #include "llvm/CodeGen/MachineMemOperand.h"
  35 #include "llvm/CodeGen/MachineOperand.h"
  36 #include "llvm/CodeGen/MachineFunctionPass.h"
  37 #include "llvm/CodeGen/MachineInstrBuilder.h"
  38 #include "llvm/CodeGen/MachineRegisterInfo.h"
  39 #include "llvm/CodeGen/MachineModuleInfo.h"
  40 #include "llvm/IR/BasicBlock.h"
  41 #include "llvm/IR/Instruction.h"
  42 #include "llvm/IR/LLVMContext.h"
  43 #include "llvm/Support/CommandLine.h"
  44 #include "llvm/Support/Debug.h"
  45 #include "llvm/Target/TargetSubtargetInfo.h"
  46 #include "llvm/Target/TargetInstrInfo.h"
  47
  48 using namespace llvm;
  49
  50 static cl::opt<int> PageSize("imp-null-check-page-size",
  51                              cl::desc("The page size of the target in bytes"),
  52                              cl::init(4096));
  53
  54 #define DEBUG_TYPE "implicit-null-checks"
  55
  56 STATISTIC(NumImplicitNullChecks,
  57           "Number of explicit null checks made implicit");
  58
  59 namespace {
  60
  61 class ImplicitNullChecks : public MachineFunctionPass {
  62   /// Represents one null check that can be made implicit.
  63   class NullCheck {
  64     // The memory operation the null check can be folded into.
  65     MachineInstr *MemOperation;
  66
  67     // The instruction actually doing the null check (Ptr != 0).
  68     MachineInstr *CheckOperation;
  69
  70     // The block the check resides in.
  71     MachineBasicBlock *CheckBlock;
  72
  73     // The block branched to if the pointer is non-null.
  74     MachineBasicBlock *NotNullSucc;
  75
  76     // The block branched to if the pointer is null.
  77     MachineBasicBlock *NullSucc;
  78
  79     // If this is non-null, then MemOperation has a dependency on on this
  80     // instruction; and it needs to be hoisted to execute before MemOperation.
  81     MachineInstr *OnlyDependency;
  82
  83   public:
  84     explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation,
  85                        MachineBasicBlock *checkBlock,
  86                        MachineBasicBlock *notNullSucc,
  87                        MachineBasicBlock *nullSucc,
  88                        MachineInstr *onlyDependency)
  89         : MemOperation(memOperation), CheckOperation(checkOperation),
  90           CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc),
  91           OnlyDependency(onlyDependency) {}
  92
  93     MachineInstr *getMemOperation() const { return MemOperation; }
  94
  95     MachineInstr *getCheckOperation() const { return CheckOperation; }
  96
  97     MachineBasicBlock *getCheckBlock() const { return CheckBlock; }
  98
  99     MachineBasicBlock *getNotNullSucc() const { return NotNullSucc; }
 100
 101     MachineBasicBlock *getNullSucc() const { return NullSucc; }
 102
 103     MachineInstr *getOnlyDependency() const { return OnlyDependency; }
 104   };
 105
 106   const TargetInstrInfo *TII = nullptr;
 107   const TargetRegisterInfo *TRI = nullptr;
 108   AliasAnalysis *AA = nullptr;
 109   MachineModuleInfo *MMI = nullptr;
 110
 111   bool analyzeBlockForNullChecks(MachineBasicBlock &MBB,
 112                                  SmallVectorImpl<NullCheck> &NullCheckList);
 113   MachineInstr *insertFaultingLoad(MachineInstr *LoadMI, MachineBasicBlock *MBB,
 114                                    MachineBasicBlock *HandlerMBB);
 115   void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList);
 116
 117 public:
 118   static char ID;
 119
 120   ImplicitNullChecks() : MachineFunctionPass(ID) {
 121     initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry());
 122   }
 123
 124   bool runOnMachineFunction(MachineFunction &MF) override;
 125   void getAnalysisUsage(AnalysisUsage &AU) const override {
 126     AU.addRequired<AAResultsWrapperPass>();
 127     MachineFunctionPass::getAnalysisUsage(AU);
 128   }
 129
 130   MachineFunctionProperties getRequiredProperties() const override {
 131     return MachineFunctionProperties().set(
 132         MachineFunctionProperties::Property::NoVRegs);
 133   }
 134 };
 135
 136 /// \brief Detect re-ordering hazards and dependencies.
 137 ///
 138 /// This class keeps track of defs and uses, and can be queried if a given
 139 /// machine instruction can be re-ordered from after the machine instructions
 140 /// seen so far to before them.
 141 class HazardDetector {
 142   static MachineInstr *getUnknownMI() {
 143     return DenseMapInfo<MachineInstr *>::getTombstoneKey();
 144   }
 145
 146   // Maps physical registers to the instruction defining them.  If there has
 147   // been more than one def of an specific register, that register is mapped to
 148   // getUnknownMI().
 149   DenseMap<unsigned, MachineInstr *> RegDefs;
 150   DenseSet<unsigned> RegUses;
 151   const TargetRegisterInfo &TRI;
 152   bool hasSeenClobber;
 153   AliasAnalysis &AA;
 154
 155 public:
 156   explicit HazardDetector(const TargetRegisterInfo &TRI, AliasAnalysis &AA)
 157       : TRI(TRI), hasSeenClobber(false), AA(AA) {}
 158
 159   /// \brief Make a note of \p MI for later queries to isSafeToHoist.
 160   ///
 161   /// May clobber this HazardDetector instance.  \see isClobbered.
 162   void rememberInstruction(MachineInstr *MI);
 163
 164   /// \brief Return true if it is safe to hoist \p MI from after all the
 165   /// instructions seen so far (via rememberInstruction) to before it.  If \p MI
 166   /// has one and only one transitive dependency, set \p Dependency to that
 167   /// instruction.  If there are more dependencies, return false.
 168   bool isSafeToHoist(MachineInstr *MI, MachineInstr *&Dependency);
 169
 170   /// \brief Return true if this instance of HazardDetector has been clobbered
 171   /// (i.e. has no more useful information).
 172   ///
 173   /// A HazardDetecter is clobbered when it sees a construct it cannot
 174   /// understand, and it would have to return a conservative answer for all
 175   /// future queries.  Having a separate clobbered state lets the client code
 176   /// bail early, without making queries about all of the future instructions
 177   /// (which would have returned the most conservative answer anyway).
 178   ///
 179   /// Calling rememberInstruction or isSafeToHoist on a clobbered HazardDetector
 180   /// is an error.
 181   bool isClobbered() { return hasSeenClobber; }
 182 };
 183 }
 184
 185
 186 void HazardDetector::rememberInstruction(MachineInstr *MI) {
 187   assert(!isClobbered() &&
 188          "Don't add instructions to a clobbered hazard detector");
 189
 190   // There may be readonly calls that we can handle in theory, but for
 191   // now we don't bother since we don't handle callee clobbered
 192   // registers.
 193   if (MI->isCall() || MI->mayStore() || MI->hasUnmodeledSideEffects()) {
 194     hasSeenClobber = true;
 195     return;
 196   }
 197
 198   for (auto *MMO : MI->memoperands()) {
 199     // Right now we don't want to worry about LLVM's memory model.
 200     if (!MMO->isUnordered()) {
 201       hasSeenClobber = true;
 202       return;
 203     }
 204   }
 205
 206   for (auto &MO : MI->operands()) {
 207     if (!MO.isReg() || !MO.getReg())
 208       continue;
 209
 210     if (MO.isDef()) {
 211       auto It = RegDefs.find(MO.getReg());
 212       if (It == RegDefs.end())
 213         RegDefs.insert({MO.getReg(), MI});
 214       else {
 215         assert(It->second && "Found null MI?");
 216         It->second = getUnknownMI();
 217       }
 218     } else
 219       RegUses.insert(MO.getReg());
 220   }
 221 }
 222
 223 bool HazardDetector::isSafeToHoist(MachineInstr *MI,
 224                                    MachineInstr *&Dependency) {
 225   assert(!isClobbered() && "isSafeToHoist cannot do anything useful!");
 226   Dependency = nullptr;
 227
 228   // Right now we don't want to worry about LLVM's memory model.  This can be
 229   // made more precise later.
 230   for (auto *MMO : MI->memoperands())
 231     if (!MMO->isUnordered())
 232       return false;
 233
 234   for (auto &MO : MI->operands()) {
 235     if (MO.isReg() && MO.getReg()) {
 236       for (auto &RegDef : RegDefs) {
 237         unsigned Reg = RegDef.first;
 238         MachineInstr *MI = RegDef.second;
 239         if (!TRI.regsOverlap(Reg, MO.getReg()))
 240           continue;
 241
 242         // We found a write-after-write or read-after-write, see if the
 243         // instruction causing this dependency can be hoisted too.
 244
 245         if (MI == getUnknownMI())
 246           // We don't have precise dependency information.
 247           return false;
 248
 249         if (Dependency) {
 250           if (Dependency == MI)
 251             continue;
 252           // We already have one dependency, and we can track only one.
 253           return false;
 254         }
 255
 256         // Now check if MI is actually a dependency that can be hoisted.
 257
 258         // We don't want to track transitive dependencies.  We already know that
 259         // MI is the only instruction that defines Reg, but we need to be sure
 260         // that it does not use any registers that have been defined (trivially
 261         // checked below by ensuring that there are no register uses), and that
 262         // it is the only def for every register it defines (otherwise we could
 263         // violate a write after write hazard).
 264         auto IsMIOperandSafe = [&](MachineOperand &MO) {
 265           if (!MO.isReg() || !MO.getReg())
 266             return true;
 267           if (MO.isUse())
 268             return false;
 269           assert((!MO.isDef() || RegDefs.count(MO.getReg())) &&
 270                  "All defs must be tracked in RegDefs by now!");
 271           return !MO.isDef() || RegDefs.find(MO.getReg())->second == MI;
 272         };
 273
 274         if (!all_of(MI->operands(), IsMIOperandSafe))
 275           return false;
 276
 277         // Now check for speculation safety:
 278         bool SawStore = true;
 279         if (!MI->isSafeToMove(&AA, SawStore) || MI->mayLoad())
 280           return false;
 281
 282         Dependency = MI;
 283       }
 284
 285       if (MO.isDef())
 286         for (unsigned Reg : RegUses)
 287           if (TRI.regsOverlap(Reg, MO.getReg()))
 288             return false;  // We found a write-after-read
 289     }
 290   }
 291
 292   return true;
 293 }
 294
 295 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
 296   TII = MF.getSubtarget().getInstrInfo();
 297   TRI = MF.getRegInfo().getTargetRegisterInfo();
 298   MMI = &MF.getMMI();
 299   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 300
 301   SmallVector<NullCheck, 16> NullCheckList;
 302
 303   for (auto &MBB : MF)
 304     analyzeBlockForNullChecks(MBB, NullCheckList);
 305
 306   if (!NullCheckList.empty())
 307     rewriteNullChecks(NullCheckList);
 308
 309   return !NullCheckList.empty();
 310 }
 311
 312 // Return true if any register aliasing \p Reg is live-in into \p MBB.
 313 static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI,
 314                            MachineBasicBlock *MBB, unsigned Reg) {
 315   for (MCRegAliasIterator AR(Reg, TRI, /*IncludeSelf*/ true); AR.isValid();
 316        ++AR)
 317     if (MBB->isLiveIn(*AR))
 318       return true;
 319   return false;
 320 }
 321
 322 /// Analyze MBB to check if its terminating branch can be turned into an
 323 /// implicit null check.  If yes, append a description of the said null check to
 324 /// NullCheckList and return true, else return false.
 325 bool ImplicitNullChecks::analyzeBlockForNullChecks(
 326     MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
 327   typedef TargetInstrInfo::MachineBranchPredicate MachineBranchPredicate;
 328
 329   MDNode *BranchMD = nullptr;
 330   if (auto *BB = MBB.getBasicBlock())
 331     BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit);
 332
 333   if (!BranchMD)
 334     return false;
 335
 336   MachineBranchPredicate MBP;
 337
 338   if (TII->analyzeBranchPredicate(MBB, MBP, true))
 339     return false;
 340
 341   // Is the predicate comparing an integer to zero?
 342   if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
 343         (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
 344          MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
 345     return false;
 346
 347   // If we cannot erase the test instruction itself, then making the null check
 348   // implicit does not buy us much.
 349   if (!MBP.SingleUseCondition)
 350     return false;
 351
 352   MachineBasicBlock *NotNullSucc, *NullSucc;
 353
 354   if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
 355     NotNullSucc = MBP.TrueDest;
 356     NullSucc = MBP.FalseDest;
 357   } else {
 358     NotNullSucc = MBP.FalseDest;
 359     NullSucc = MBP.TrueDest;
 360   }
 361
 362   // We handle the simplest case for now.  We can potentially do better by using
 363   // the machine dominator tree.
 364   if (NotNullSucc->pred_size() != 1)
 365     return false;
 366
 367   // Starting with a code fragment like:
 368   //
 369   //   test %RAX, %RAX
 370   //   jne LblNotNull
 371   //
 372   //  LblNull:
 373   //   callq throw_NullPointerException
 374   //
 375   //  LblNotNull:
 376   //   Inst0
 377   //   Inst1
 378   //   ...
 379   //   Def = Load (%RAX + <offset>)
 380   //   ...
 381   //
 382   //
 383   // we want to end up with
 384   //
 385   //   Def = FaultingLoad (%RAX + <offset>), LblNull
 386   //   jmp LblNotNull ;; explicit or fallthrough
 387   //
 388   //  LblNotNull:
 389   //   Inst0
 390   //   Inst1
 391   //   ...
 392   //
 393   //  LblNull:
 394   //   callq throw_NullPointerException
 395   //
 396   //
 397   // To see why this is legal, consider the two possibilities:
 398   //
 399   //  1. %RAX is null: since we constrain <offset> to be less than PageSize, the
 400   //     load instruction dereferences the null page, causing a segmentation
 401   //     fault.
 402   //
 403   //  2. %RAX is not null: in this case we know that the load cannot fault, as
 404   //     otherwise the load would've faulted in the original program too and the
 405   //     original program would've been undefined.
 406   //
 407   // This reasoning cannot be extended to justify hoisting through arbitrary
 408   // control flow.  For instance, in the example below (in pseudo-C)
 409   //
 410   //    if (ptr == null) { throw_npe(); unreachable; }
 411   //    if (some_cond) { return 42; }
 412   //    v = ptr->field;  // LD
 413   //    ...
 414   //
 415   // we cannot (without code duplication) use the load marked "LD" to null check
 416   // ptr -- clause (2) above does not apply in this case.  In the above program
 417   // the safety of ptr->field can be dependent on some_cond; and, for instance,
 418   // ptr could be some non-null invalid reference that never gets loaded from
 419   // because some_cond is always true.
 420
 421   unsigned PointerReg = MBP.LHS.getReg();
 422
 423   HazardDetector HD(*TRI, *AA);
 424
 425   for (auto MII = NotNullSucc->begin(), MIE = NotNullSucc->end(); MII != MIE;
 426        ++MII) {
 427     MachineInstr &MI = *MII;
 428     unsigned BaseReg;
 429     int64_t Offset;
 430     MachineInstr *Dependency = nullptr;
 431     if (TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI))
 432       if (MI.mayLoad() && !MI.isPredicable() && BaseReg == PointerReg &&
 433           Offset < PageSize && MI.getDesc().getNumDefs() <= 1 &&
 434           HD.isSafeToHoist(&MI, Dependency)) {
 435
 436         auto DependencyOperandIsOk = [&](MachineOperand &MO) {
 437           assert(!(MO.isReg() && MO.isUse()) &&
 438                  "No transitive dependendencies please!");
 439           if (!MO.isReg() || !MO.getReg() || !MO.isDef())
 440             return true;
 441
 442           // Make sure that we won't clobber any live ins to the sibling block
 443           // by hoisting Dependency.  For instance, we can't hoist INST to
 444           // before the null check (even if it safe, and does not violate any
 445           // dependencies in the non_null_block) if %rdx is live in to
 446           // _null_block.
 447           //
 448           //    test %rcx, %rcx
 449           //    je _null_block
 450           //  _non_null_block:
 451           //    %rdx<def> = INST
 452           //    ...
 453           if (AnyAliasLiveIn(TRI, NullSucc, MO.getReg()))
 454             return false;
 455
 456           // Make sure Dependency isn't re-defining the base register.  Then we
 457           // won't get the memory operation on the address we want.
 458           if (TRI->regsOverlap(MO.getReg(), BaseReg))
 459             return false;
 460
 461           return true;
 462         };
 463
 464         bool DependencyOperandsAreOk =
 465             !Dependency ||
 466             all_of(Dependency->operands(), DependencyOperandIsOk);
 467
 468         if (DependencyOperandsAreOk) {
 469           NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc,
 470                                      NullSucc, Dependency);
 471           return true;
 472         }
 473       }
 474
 475     HD.rememberInstruction(&MI);
 476     if (HD.isClobbered())
 477       return false;
 478   }
 479
 480   return false;
 481 }
 482
 483 /// Wrap a machine load instruction, LoadMI, into a FAULTING_LOAD_OP machine
 484 /// instruction.  The FAULTING_LOAD_OP instruction does the same load as LoadMI
 485 /// (defining the same register), and branches to HandlerMBB if the load
 486 /// faults.  The FAULTING_LOAD_OP instruction is inserted at the end of MBB.
 487 MachineInstr *
 488 ImplicitNullChecks::insertFaultingLoad(MachineInstr *LoadMI,
 489                                        MachineBasicBlock *MBB,
 490                                        MachineBasicBlock *HandlerMBB) {
 491   const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for
 492                                  // all targets.
 493
 494   DebugLoc DL;
 495   unsigned NumDefs = LoadMI->getDesc().getNumDefs();
 496   assert(NumDefs <= 1 && "other cases unhandled!");
 497
 498   unsigned DefReg = NoRegister;
 499   if (NumDefs != 0) {
 500     DefReg = LoadMI->defs().begin()->getReg();
 501     assert(std::distance(LoadMI->defs().begin(), LoadMI->defs().end()) == 1 &&
 502            "expected exactly one def!");
 503   }
 504
 505   auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_LOAD_OP), DefReg)
 506                  .addMBB(HandlerMBB)
 507                  .addImm(LoadMI->getOpcode());
 508
 509   for (auto &MO : LoadMI->uses())
 510     MIB.addOperand(MO);
 511
 512   MIB.setMemRefs(LoadMI->memoperands_begin(), LoadMI->memoperands_end());
 513
 514   return MIB;
 515 }
 516
 517 /// Rewrite the null checks in NullCheckList into implicit null checks.
 518 void ImplicitNullChecks::rewriteNullChecks(
 519     ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
 520   DebugLoc DL;
 521
 522   for (auto &NC : NullCheckList) {
 523     // Remove the conditional branch dependent on the null check.
 524     unsigned BranchesRemoved = TII->removeBranch(*NC.getCheckBlock());
 525     (void)BranchesRemoved;
 526     assert(BranchesRemoved > 0 && "expected at least one branch!");
 527
 528     if (auto *DepMI = NC.getOnlyDependency()) {
 529       DepMI->removeFromParent();
 530       NC.getCheckBlock()->insert(NC.getCheckBlock()->end(), DepMI);
 531     }
 532
 533     // Insert a faulting load where the conditional branch was originally.  We
 534     // check earlier ensures that this bit of code motion is legal.  We do not
 535     // touch the successors list for any basic block since we haven't changed
 536     // control flow, we've just made it implicit.
 537     MachineInstr *FaultingLoad = insertFaultingLoad(
 538         NC.getMemOperation(), NC.getCheckBlock(), NC.getNullSucc());
 539     // Now the values defined by MemOperation, if any, are live-in of
 540     // the block of MemOperation.
 541     // The original load operation may define implicit-defs alongside
 542     // the loaded value.
 543     MachineBasicBlock *MBB = NC.getMemOperation()->getParent();
 544     for (const MachineOperand &MO : FaultingLoad->operands()) {
 545       if (!MO.isReg() || !MO.isDef())
 546         continue;
 547       unsigned Reg = MO.getReg();
 548       if (!Reg || MBB->isLiveIn(Reg))
 549         continue;
 550       MBB->addLiveIn(Reg);
 551     }
 552
 553     if (auto *DepMI = NC.getOnlyDependency()) {
 554       for (auto &MO : DepMI->operands()) {
 555         if (!MO.isReg() || !MO.getReg() || !MO.isDef())
 556           continue;
 557         if (!NC.getNotNullSucc()->isLiveIn(MO.getReg()))
 558           NC.getNotNullSucc()->addLiveIn(MO.getReg());
 559       }
 560     }
 561
 562     NC.getMemOperation()->eraseFromParent();
 563     NC.getCheckOperation()->eraseFromParent();
 564
 565     // Insert an *unconditional* branch to not-null successor.
 566     TII->insertBranch(*NC.getCheckBlock(), NC.getNotNullSucc(), nullptr,
 567                       /*Cond=*/None, DL);
 568
 569     NumImplicitNullChecks++;
 570   }
 571 }
 572
 573 char ImplicitNullChecks::ID = 0;
 574 char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID;
 575 INITIALIZE_PASS_BEGIN(ImplicitNullChecks, "implicit-null-checks",
 576                       "Implicit null checks", false, false)
 577 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 578 INITIALIZE_PASS_END(ImplicitNullChecks, "implicit-null-checks",
 579                     "Implicit null checks", false, false)