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 //
  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::AllVRegsAllocated);
 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   if (MI->mayStore() || MI->hasUnmodeledSideEffects()) {
 191     hasSeenClobber = true;
 192     return;
 193   }
 194
 195   for (auto *MMO : MI->memoperands()) {
 196     // Right now we don't want to worry about LLVM's memory model.
 197     if (!MMO->isUnordered()) {
 198       hasSeenClobber = true;
 199       return;
 200     }
 201   }
 202
 203   for (auto &MO : MI->operands()) {
 204     if (!MO.isReg() || !MO.getReg())
 205       continue;
 206
 207     if (MO.isDef()) {
 208       auto It = RegDefs.find(MO.getReg());
 209       if (It == RegDefs.end())
 210         RegDefs.insert({MO.getReg(), MI});
 211       else {
 212         assert(It->second && "Found null MI?");
 213         It->second = getUnknownMI();
 214       }
 215     } else
 216       RegUses.insert(MO.getReg());
 217   }
 218 }
 219
 220 bool HazardDetector::isSafeToHoist(MachineInstr *MI,
 221                                    MachineInstr *&Dependency) {
 222   assert(!isClobbered() && "isSafeToHoist cannot do anything useful!");
 223   Dependency = nullptr;
 224
 225   // Right now we don't want to worry about LLVM's memory model.  This can be
 226   // made more precise later.
 227   for (auto *MMO : MI->memoperands())
 228     if (!MMO->isUnordered())
 229       return false;
 230
 231   for (auto &MO : MI->operands()) {
 232     if (MO.isReg() && MO.getReg()) {
 233       for (auto &RegDef : RegDefs) {
 234         unsigned Reg = RegDef.first;
 235         MachineInstr *MI = RegDef.second;
 236         if (!TRI.regsOverlap(Reg, MO.getReg()))
 237           continue;
 238
 239         // We found a write-after-write or read-after-write, see if the
 240         // instruction causing this dependency can be hoisted too.
 241
 242         if (MI == getUnknownMI())
 243           // We don't have precise dependency information.
 244           return false;
 245
 246         if (Dependency) {
 247           if (Dependency == MI)
 248             continue;
 249           // We already have one dependency, and we can track only one.
 250           return false;
 251         }
 252
 253         // Now check if MI is actually a dependency that can be hoisted.
 254
 255         // We don't want to track transitive dependencies.  We already know that
 256         // MI is the only instruction that defines Reg, but we need to be sure
 257         // that it does not use any registers that have been defined (trivially
 258         // checked below by ensuring that there are no register uses), and that
 259         // it is the only def for every register it defines (otherwise we could
 260         // violate a write after write hazard).
 261         auto IsMIOperandSafe = [&](MachineOperand &MO) {
 262           if (!MO.isReg() || !MO.getReg())
 263             return true;
 264           if (MO.isUse())
 265             return false;
 266           assert((!MO.isDef() || RegDefs.count(MO.getReg())) &&
 267                  "All defs must be tracked in RegDefs by now!");
 268           return !MO.isDef() || RegDefs.find(MO.getReg())->second == MI;
 269         };
 270
 271         if (!all_of(MI->operands(), IsMIOperandSafe))
 272           return false;
 273
 274         // Now check for speculation safety:
 275         bool SawStore = true;
 276         if (!MI->isSafeToMove(&AA, SawStore) || MI->mayLoad())
 277           return false;
 278
 279         Dependency = MI;
 280       }
 281
 282       if (MO.isDef())
 283         for (unsigned Reg : RegUses)
 284           if (TRI.regsOverlap(Reg, MO.getReg()))
 285             return false;  // We found a write-after-read
 286     }
 287   }
 288
 289   return true;
 290 }
 291
 292 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
 293   TII = MF.getSubtarget().getInstrInfo();
 294   TRI = MF.getRegInfo().getTargetRegisterInfo();
 295   MMI = &MF.getMMI();
 296   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 297
 298   SmallVector<NullCheck, 16> NullCheckList;
 299
 300   for (auto &MBB : MF)
 301     analyzeBlockForNullChecks(MBB, NullCheckList);
 302
 303   if (!NullCheckList.empty())
 304     rewriteNullChecks(NullCheckList);
 305
 306   return !NullCheckList.empty();
 307 }
 308
 309 // Return true if any register aliasing \p Reg is live-in into \p MBB.
 310 static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI,
 311                            MachineBasicBlock *MBB, unsigned Reg) {
 312   for (MCRegAliasIterator AR(Reg, TRI, /*IncludeSelf*/ true); AR.isValid();
 313        ++AR)
 314     if (MBB->isLiveIn(*AR))
 315       return true;
 316   return false;
 317 }
 318
 319 /// Analyze MBB to check if its terminating branch can be turned into an
 320 /// implicit null check.  If yes, append a description of the said null check to
 321 /// NullCheckList and return true, else return false.
 322 bool ImplicitNullChecks::analyzeBlockForNullChecks(
 323     MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
 324   typedef TargetInstrInfo::MachineBranchPredicate MachineBranchPredicate;
 325
 326   MDNode *BranchMD = nullptr;
 327   if (auto *BB = MBB.getBasicBlock())
 328     BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit);
 329
 330   if (!BranchMD)
 331     return false;
 332
 333   MachineBranchPredicate MBP;
 334
 335   if (TII->analyzeBranchPredicate(MBB, MBP, true))
 336     return false;
 337
 338   // Is the predicate comparing an integer to zero?
 339   if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
 340         (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
 341          MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
 342     return false;
 343
 344   // If we cannot erase the test instruction itself, then making the null check
 345   // implicit does not buy us much.
 346   if (!MBP.SingleUseCondition)
 347     return false;
 348
 349   MachineBasicBlock *NotNullSucc, *NullSucc;
 350
 351   if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
 352     NotNullSucc = MBP.TrueDest;
 353     NullSucc = MBP.FalseDest;
 354   } else {
 355     NotNullSucc = MBP.FalseDest;
 356     NullSucc = MBP.TrueDest;
 357   }
 358
 359   // We handle the simplest case for now.  We can potentially do better by using
 360   // the machine dominator tree.
 361   if (NotNullSucc->pred_size() != 1)
 362     return false;
 363
 364   // Starting with a code fragment like:
 365   //
 366   //   test %RAX, %RAX
 367   //   jne LblNotNull
 368   //
 369   //  LblNull:
 370   //   callq throw_NullPointerException
 371   //
 372   //  LblNotNull:
 373   //   Inst0
 374   //   Inst1
 375   //   ...
 376   //   Def = Load (%RAX + <offset>)
 377   //   ...
 378   //
 379   //
 380   // we want to end up with
 381   //
 382   //   Def = FaultingLoad (%RAX + <offset>), LblNull
 383   //   jmp LblNotNull ;; explicit or fallthrough
 384   //
 385   //  LblNotNull:
 386   //   Inst0
 387   //   Inst1
 388   //   ...
 389   //
 390   //  LblNull:
 391   //   callq throw_NullPointerException
 392   //
 393   //
 394   // To see why this is legal, consider the two possibilities:
 395   //
 396   //  1. %RAX is null: since we constrain <offset> to be less than PageSize, the
 397   //     load instruction dereferences the null page, causing a segmentation
 398   //     fault.
 399   //
 400   //  2. %RAX is not null: in this case we know that the load cannot fault, as
 401   //     otherwise the load would've faulted in the original program too and the
 402   //     original program would've been undefined.
 403   //
 404   // This reasoning cannot be extended to justify hoisting through arbitrary
 405   // control flow.  For instance, in the example below (in pseudo-C)
 406   //
 407   //    if (ptr == null) { throw_npe(); unreachable; }
 408   //    if (some_cond) { return 42; }
 409   //    v = ptr->field;  // LD
 410   //    ...
 411   //
 412   // we cannot (without code duplication) use the load marked "LD" to null check
 413   // ptr -- clause (2) above does not apply in this case.  In the above program
 414   // the safety of ptr->field can be dependent on some_cond; and, for instance,
 415   // ptr could be some non-null invalid reference that never gets loaded from
 416   // because some_cond is always true.
 417
 418   unsigned PointerReg = MBP.LHS.getReg();
 419
 420   HazardDetector HD(*TRI, *AA);
 421
 422   for (auto MII = NotNullSucc->begin(), MIE = NotNullSucc->end(); MII != MIE;
 423        ++MII) {
 424     MachineInstr &MI = *MII;
 425     unsigned BaseReg;
 426     int64_t Offset;
 427     MachineInstr *Dependency = nullptr;
 428     if (TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI))
 429       if (MI.mayLoad() && !MI.isPredicable() && BaseReg == PointerReg &&
 430           Offset < PageSize && MI.getDesc().getNumDefs() <= 1 &&
 431           HD.isSafeToHoist(&MI, Dependency)) {
 432
 433         auto DependencyOperandIsOk = [&](MachineOperand &MO) {
 434           assert(!(MO.isReg() && MO.isUse()) &&
 435                  "No transitive dependendencies please!");
 436           if (!MO.isReg() || !MO.getReg() || !MO.isDef())
 437             return true;
 438
 439           // Make sure that we won't clobber any live ins to the sibling block
 440           // by hoisting Dependency.  For instance, we can't hoist INST to
 441           // before the null check (even if it safe, and does not violate any
 442           // dependencies in the non_null_block) if %rdx is live in to
 443           // _null_block.
 444           //
 445           //    test %rcx, %rcx
 446           //    je _null_block
 447           //  _non_null_block:
 448           //    %rdx<def> = INST
 449           //    ...
 450           if (AnyAliasLiveIn(TRI, NullSucc, MO.getReg()))
 451             return false;
 452
 453           // Make sure Dependency isn't re-defining the base register.  Then we
 454           // won't get the memory operation on the address we want.
 455           if (TRI->regsOverlap(MO.getReg(), BaseReg))
 456             return false;
 457
 458           return true;
 459         };
 460
 461         bool DependencyOperandsAreOk =
 462             !Dependency ||
 463             all_of(Dependency->operands(), DependencyOperandIsOk);
 464
 465         if (DependencyOperandsAreOk) {
 466           NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc,
 467                                      NullSucc, Dependency);
 468           return true;
 469         }
 470       }
 471
 472     HD.rememberInstruction(&MI);
 473     if (HD.isClobbered())
 474       return false;
 475   }
 476
 477   return false;
 478 }
 479
 480 /// Wrap a machine load instruction, LoadMI, into a FAULTING_LOAD_OP machine
 481 /// instruction.  The FAULTING_LOAD_OP instruction does the same load as LoadMI
 482 /// (defining the same register), and branches to HandlerMBB if the load
 483 /// faults.  The FAULTING_LOAD_OP instruction is inserted at the end of MBB.
 484 MachineInstr *
 485 ImplicitNullChecks::insertFaultingLoad(MachineInstr *LoadMI,
 486                                        MachineBasicBlock *MBB,
 487                                        MachineBasicBlock *HandlerMBB) {
 488   const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for
 489                                  // all targets.
 490
 491   DebugLoc DL;
 492   unsigned NumDefs = LoadMI->getDesc().getNumDefs();
 493   assert(NumDefs <= 1 && "other cases unhandled!");
 494
 495   unsigned DefReg = NoRegister;
 496   if (NumDefs != 0) {
 497     DefReg = LoadMI->defs().begin()->getReg();
 498     assert(std::distance(LoadMI->defs().begin(), LoadMI->defs().end()) == 1 &&
 499            "expected exactly one def!");
 500   }
 501
 502   auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_LOAD_OP), DefReg)
 503                  .addMBB(HandlerMBB)
 504                  .addImm(LoadMI->getOpcode());
 505
 506   for (auto &MO : LoadMI->uses())
 507     MIB.addOperand(MO);
 508
 509   MIB.setMemRefs(LoadMI->memoperands_begin(), LoadMI->memoperands_end());
 510
 511   return MIB;
 512 }
 513
 514 /// Rewrite the null checks in NullCheckList into implicit null checks.
 515 void ImplicitNullChecks::rewriteNullChecks(
 516     ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
 517   DebugLoc DL;
 518
 519   for (auto &NC : NullCheckList) {
 520     // Remove the conditional branch dependent on the null check.
 521     unsigned BranchesRemoved = TII->RemoveBranch(*NC.getCheckBlock());
 522     (void)BranchesRemoved;
 523     assert(BranchesRemoved > 0 && "expected at least one branch!");
 524
 525     if (auto *DepMI = NC.getOnlyDependency()) {
 526       DepMI->removeFromParent();
 527       NC.getCheckBlock()->insert(NC.getCheckBlock()->end(), DepMI);
 528     }
 529
 530     // Insert a faulting load where the conditional branch was originally.  We
 531     // check earlier ensures that this bit of code motion is legal.  We do not
 532     // touch the successors list for any basic block since we haven't changed
 533     // control flow, we've just made it implicit.
 534     MachineInstr *FaultingLoad = insertFaultingLoad(
 535         NC.getMemOperation(), NC.getCheckBlock(), NC.getNullSucc());
 536     // Now the values defined by MemOperation, if any, are live-in of
 537     // the block of MemOperation.
 538     // The original load operation may define implicit-defs alongside
 539     // the loaded value.
 540     MachineBasicBlock *MBB = NC.getMemOperation()->getParent();
 541     for (const MachineOperand &MO : FaultingLoad->operands()) {
 542       if (!MO.isReg() || !MO.isDef())
 543         continue;
 544       unsigned Reg = MO.getReg();
 545       if (!Reg || MBB->isLiveIn(Reg))
 546         continue;
 547       MBB->addLiveIn(Reg);
 548     }
 549
 550     if (auto *DepMI = NC.getOnlyDependency()) {
 551       for (auto &MO : DepMI->operands()) {
 552         if (!MO.isReg() || !MO.getReg() || !MO.isDef())
 553           continue;
 554         if (!NC.getNotNullSucc()->isLiveIn(MO.getReg()))
 555           NC.getNotNullSucc()->addLiveIn(MO.getReg());
 556       }
 557     }
 558
 559     NC.getMemOperation()->eraseFromParent();
 560     NC.getCheckOperation()->eraseFromParent();
 561
 562     // Insert an *unconditional* branch to not-null successor.
 563     TII->InsertBranch(*NC.getCheckBlock(), NC.getNotNullSucc(), nullptr,
 564                       /*Cond=*/None, DL);
 565
 566     NumImplicitNullChecks++;
 567   }
 568 }
 569
 570 char ImplicitNullChecks::ID = 0;
 571 char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID;
 572 INITIALIZE_PASS_BEGIN(ImplicitNullChecks, "implicit-null-checks",
 573                       "Implicit null checks", false, false)
 574 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 575 INITIALIZE_PASS_END(ImplicitNullChecks, "implicit-null-checks",
 576                     "Implicit null checks", false, false)