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/CodeGen/Passes.h"
  32 #include "llvm/CodeGen/MachineFunction.h"
  33 #include "llvm/CodeGen/MachineMemOperand.h"
  34 #include "llvm/CodeGen/MachineOperand.h"
  35 #include "llvm/CodeGen/MachineFunctionPass.h"
  36 #include "llvm/CodeGen/MachineInstrBuilder.h"
  37 #include "llvm/CodeGen/MachineRegisterInfo.h"
  38 #include "llvm/CodeGen/MachineModuleInfo.h"
  39 #include "llvm/IR/BasicBlock.h"
  40 #include "llvm/IR/Instruction.h"
  41 #include "llvm/IR/LLVMContext.h"
  42 #include "llvm/Support/CommandLine.h"
  43 #include "llvm/Support/Debug.h"
  44 #include "llvm/Target/TargetSubtargetInfo.h"
  45 #include "llvm/Target/TargetInstrInfo.h"
  46
  47 using namespace llvm;
  48
  49 static cl::opt<unsigned> PageSize("imp-null-check-page-size",
  50                                   cl::desc("The page size of the target in "
  51                                            "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   struct 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     NullCheck()
  80         : MemOperation(), CheckOperation(), CheckBlock(), NotNullSucc(),
  81           NullSucc() {}
  82
  83     explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation,
  84                        MachineBasicBlock *checkBlock,
  85                        MachineBasicBlock *notNullSucc,
  86                        MachineBasicBlock *nullSucc)
  87         : MemOperation(memOperation), CheckOperation(checkOperation),
  88           CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc) {
  89     }
  90   };
  91
  92   const TargetInstrInfo *TII = nullptr;
  93   const TargetRegisterInfo *TRI = nullptr;
  94   MachineModuleInfo *MMI = nullptr;
  95
  96   bool analyzeBlockForNullChecks(MachineBasicBlock &MBB,
  97                                  SmallVectorImpl<NullCheck> &NullCheckList);
  98   MachineInstr *insertFaultingLoad(MachineInstr *LoadMI, MachineBasicBlock *MBB,
  99                                    MCSymbol *HandlerLabel);
 100   void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList);
 101
 102 public:
 103   static char ID;
 104
 105   ImplicitNullChecks() : MachineFunctionPass(ID) {
 106     initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry());
 107   }
 108
 109   bool runOnMachineFunction(MachineFunction &MF) override;
 110 };
 111
 112 /// \brief Detect re-ordering hazards and dependencies.
 113 ///
 114 /// This class keeps track of defs and uses, and can be queried if a given
 115 /// machine instruction can be re-ordered from after the machine instructions
 116 /// seen so far to before them.
 117 class HazardDetector {
 118   DenseSet<unsigned> RegDefs;
 119   DenseSet<unsigned> RegUses;
 120   const TargetRegisterInfo &TRI;
 121   bool hasSeenClobber;
 122
 123 public:
 124   explicit HazardDetector(const TargetRegisterInfo &TRI) :
 125     TRI(TRI), hasSeenClobber(false) {}
 126
 127   /// \brief Make a note of \p MI for later queries to isSafeToHoist.
 128   ///
 129   /// May clobber this HazardDetector instance.  \see isClobbered.
 130   void rememberInstruction(MachineInstr *MI);
 131
 132   /// \brief Return true if it is safe to hoist \p MI from after all the
 133   /// instructions seen so far (via rememberInstruction) to before it.
 134   bool isSafeToHoist(MachineInstr *MI);
 135
 136   /// \brief Return true if this instance of HazardDetector has been clobbered
 137   /// (i.e. has no more useful information).
 138   ///
 139   /// A HazardDetecter is clobbered when it sees a construct it cannot
 140   /// understand, and it would have to return a conservative answer for all
 141   /// future queries.  Having a separate clobbered state lets the client code
 142   /// bail early, without making queries about all of the future instructions
 143   /// (which would have returned the most conservative answer anyway).
 144   ///
 145   /// Calling rememberInstruction or isSafeToHoist on a clobbered HazardDetector
 146   /// is an error.
 147   bool isClobbered() { return hasSeenClobber; }
 148 };
 149 }
 150
 151
 152 void HazardDetector::rememberInstruction(MachineInstr *MI) {
 153   assert(!isClobbered() &&
 154          "Don't add instructions to a clobbered hazard detector");
 155
 156   if (MI->mayStore() || MI->hasUnmodeledSideEffects()) {
 157     hasSeenClobber = true;
 158     return;
 159   }
 160
 161   for (auto *MMO : MI->memoperands()) {
 162     // Right now we don't want to worry about LLVM's memory model.
 163     if (!MMO->isUnordered()) {
 164       hasSeenClobber = true;
 165       return;
 166     }
 167   }
 168
 169   for (auto &MO : MI->operands()) {
 170     if (!MO.isReg() || !MO.getReg())
 171       continue;
 172
 173     if (MO.isDef())
 174       RegDefs.insert(MO.getReg());
 175     else
 176       RegUses.insert(MO.getReg());
 177   }
 178 }
 179
 180 bool HazardDetector::isSafeToHoist(MachineInstr *MI) {
 181   assert(!isClobbered() && "isSafeToHoist cannot do anything useful!");
 182
 183   // Right now we don't want to worry about LLVM's memory model.  This can be
 184   // made more precise later.
 185   for (auto *MMO : MI->memoperands())
 186     if (!MMO->isUnordered())
 187       return false;
 188
 189   for (auto &MO : MI->operands()) {
 190     if (MO.isReg() && MO.getReg()) {
 191       for (unsigned Reg : RegDefs)
 192         if (TRI.regsOverlap(Reg, MO.getReg()))
 193           return false;  // We found a write-after-write or read-after-write
 194
 195       if (MO.isDef())
 196         for (unsigned Reg : RegUses)
 197           if (TRI.regsOverlap(Reg, MO.getReg()))
 198             return false;  // We found a write-after-read
 199     }
 200   }
 201
 202   return true;
 203 }
 204
 205 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
 206   TII = MF.getSubtarget().getInstrInfo();
 207   TRI = MF.getRegInfo().getTargetRegisterInfo();
 208   MMI = &MF.getMMI();
 209
 210   SmallVector<NullCheck, 16> NullCheckList;
 211
 212   for (auto &MBB : MF)
 213     analyzeBlockForNullChecks(MBB, NullCheckList);
 214
 215   if (!NullCheckList.empty())
 216     rewriteNullChecks(NullCheckList);
 217
 218   return !NullCheckList.empty();
 219 }
 220
 221 /// Analyze MBB to check if its terminating branch can be turned into an
 222 /// implicit null check.  If yes, append a description of the said null check to
 223 /// NullCheckList and return true, else return false.
 224 bool ImplicitNullChecks::analyzeBlockForNullChecks(
 225     MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
 226   typedef TargetInstrInfo::MachineBranchPredicate MachineBranchPredicate;
 227
 228   MDNode *BranchMD = nullptr;
 229   if (auto *BB = MBB.getBasicBlock())
 230     BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit);
 231
 232   if (!BranchMD)
 233     return false;
 234
 235   MachineBranchPredicate MBP;
 236
 237   if (TII->AnalyzeBranchPredicate(MBB, MBP, true))
 238     return false;
 239
 240   // Is the predicate comparing an integer to zero?
 241   if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
 242         (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
 243          MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
 244     return false;
 245
 246   // If we cannot erase the test instruction itself, then making the null check
 247   // implicit does not buy us much.
 248   if (!MBP.SingleUseCondition)
 249     return false;
 250
 251   MachineBasicBlock *NotNullSucc, *NullSucc;
 252
 253   if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
 254     NotNullSucc = MBP.TrueDest;
 255     NullSucc = MBP.FalseDest;
 256   } else {
 257     NotNullSucc = MBP.FalseDest;
 258     NullSucc = MBP.TrueDest;
 259   }
 260
 261   // We handle the simplest case for now.  We can potentially do better by using
 262   // the machine dominator tree.
 263   if (NotNullSucc->pred_size() != 1)
 264     return false;
 265
 266   // Starting with a code fragment like:
 267   //
 268   //   test %RAX, %RAX
 269   //   jne LblNotNull
 270   //
 271   //  LblNull:
 272   //   callq throw_NullPointerException
 273   //
 274   //  LblNotNull:
 275   //   Inst0
 276   //   Inst1
 277   //   ...
 278   //   Def = Load (%RAX + <offset>)
 279   //   ...
 280   //
 281   //
 282   // we want to end up with
 283   //
 284   //   Def = FaultingLoad (%RAX + <offset>), LblNull
 285   //   jmp LblNotNull ;; explicit or fallthrough
 286   //
 287   //  LblNotNull:
 288   //   Inst0
 289   //   Inst1
 290   //   ...
 291   //
 292   //  LblNull:
 293   //   callq throw_NullPointerException
 294   //
 295   //
 296   // To see why this is legal, consider the two possibilities:
 297   //
 298   //  1. %RAX is null: since we constrain <offset> to be less than PageSize, the
 299   //     load instruction dereferences the null page, causing a segmentation
 300   //     fault.
 301   //
 302   //  2. %RAX is not null: in this case we know that the load cannot fault, as
 303   //     otherwise the load would've faulted in the original program too and the
 304   //     original program would've been undefined.
 305   //
 306   // This reasoning cannot be extended to justify hoisting through arbitrary
 307   // control flow.  For instance, in the example below (in pseudo-C)
 308   //
 309   //    if (ptr == null) { throw_npe(); unreachable; }
 310   //    if (some_cond) { return 42; }
 311   //    v = ptr->field;  // LD
 312   //    ...
 313   //
 314   // we cannot (without code duplication) use the load marked "LD" to null check
 315   // ptr -- clause (2) above does not apply in this case.  In the above program
 316   // the safety of ptr->field can be dependent on some_cond; and, for instance,
 317   // ptr could be some non-null invalid reference that never gets loaded from
 318   // because some_cond is always true.
 319
 320   unsigned PointerReg = MBP.LHS.getReg();
 321
 322   HazardDetector HD(*TRI);
 323
 324   for (auto MII = NotNullSucc->begin(), MIE = NotNullSucc->end(); MII != MIE;
 325        ++MII) {
 326     MachineInstr *MI = &*MII;
 327     unsigned BaseReg, Offset;
 328     if (TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI))
 329       if (MI->mayLoad() && !MI->isPredicable() && BaseReg == PointerReg &&
 330           Offset < PageSize && MI->getDesc().getNumDefs() <= 1 &&
 331           HD.isSafeToHoist(MI)) {
 332         NullCheckList.emplace_back(MI, MBP.ConditionDef, &MBB, NotNullSucc,
 333                                    NullSucc);
 334         return true;
 335       }
 336
 337     HD.rememberInstruction(MI);
 338     if (HD.isClobbered())
 339       return false;
 340   }
 341
 342   return false;
 343 }
 344
 345 /// Wrap a machine load instruction, LoadMI, into a FAULTING_LOAD_OP machine
 346 /// instruction.  The FAULTING_LOAD_OP instruction does the same load as LoadMI
 347 /// (defining the same register), and branches to HandlerLabel if the load
 348 /// faults.  The FAULTING_LOAD_OP instruction is inserted at the end of MBB.
 349 MachineInstr *ImplicitNullChecks::insertFaultingLoad(MachineInstr *LoadMI,
 350                                                      MachineBasicBlock *MBB,
 351                                                      MCSymbol *HandlerLabel) {
 352   const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for
 353                                  // all targets.
 354
 355   DebugLoc DL;
 356   unsigned NumDefs = LoadMI->getDesc().getNumDefs();
 357   assert(NumDefs <= 1 && "other cases unhandled!");
 358
 359   unsigned DefReg = NoRegister;
 360   if (NumDefs != 0) {
 361     DefReg = LoadMI->defs().begin()->getReg();
 362     assert(std::distance(LoadMI->defs().begin(), LoadMI->defs().end()) == 1 &&
 363            "expected exactly one def!");
 364   }
 365
 366   auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_LOAD_OP), DefReg)
 367                  .addSym(HandlerLabel)
 368                  .addImm(LoadMI->getOpcode());
 369
 370   for (auto &MO : LoadMI->uses())
 371     MIB.addOperand(MO);
 372
 373   MIB.setMemRefs(LoadMI->memoperands_begin(), LoadMI->memoperands_end());
 374
 375   return MIB;
 376 }
 377
 378 /// Rewrite the null checks in NullCheckList into implicit null checks.
 379 void ImplicitNullChecks::rewriteNullChecks(
 380     ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
 381   DebugLoc DL;
 382
 383   for (auto &NC : NullCheckList) {
 384     MCSymbol *HandlerLabel = MMI->getContext().createTempSymbol();
 385
 386     // Remove the conditional branch dependent on the null check.
 387     unsigned BranchesRemoved = TII->RemoveBranch(*NC.CheckBlock);
 388     (void)BranchesRemoved;
 389     assert(BranchesRemoved > 0 && "expected at least one branch!");
 390
 391     // Insert a faulting load where the conditional branch was originally.  We
 392     // check earlier ensures that this bit of code motion is legal.  We do not
 393     // touch the successors list for any basic block since we haven't changed
 394     // control flow, we've just made it implicit.
 395     insertFaultingLoad(NC.MemOperation, NC.CheckBlock, HandlerLabel);
 396     NC.MemOperation->eraseFromParent();
 397     NC.CheckOperation->eraseFromParent();
 398
 399     // Insert an *unconditional* branch to not-null successor.
 400     TII->InsertBranch(*NC.CheckBlock, NC.NotNullSucc, nullptr, /*Cond=*/None,
 401                       DL);
 402
 403     // Emit the HandlerLabel as an EH_LABEL.
 404     BuildMI(*NC.NullSucc, NC.NullSucc->begin(), DL,
 405             TII->get(TargetOpcode::EH_LABEL)).addSym(HandlerLabel);
 406
 407     NumImplicitNullChecks++;
 408   }
 409 }
 410
 411 char ImplicitNullChecks::ID = 0;
 412 char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID;
 413 INITIALIZE_PASS_BEGIN(ImplicitNullChecks, "implicit-null-checks",
 414                       "Implicit null checks", false, false)
 415 INITIALIZE_PASS_END(ImplicitNullChecks, "implicit-null-checks",
 416                     "Implicit null checks", false, false)