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/Support/CommandLine.h"
  42 #include "llvm/Support/Debug.h"
  43 #include "llvm/Target/TargetSubtargetInfo.h"
  44 #include "llvm/Target/TargetInstrInfo.h"
  45
  46 using namespace llvm;
  47
  48 static cl::opt<unsigned> PageSize("imp-null-check-page-size",
  49                                   cl::desc("The page size of the target in "
  50                                            "bytes"),
  51                                   cl::init(4096));
  52
  53 #define DEBUG_TYPE "implicit-null-checks"
  54
  55 STATISTIC(NumImplicitNullChecks,
  56           "Number of explicit null checks made implicit");
  57
  58 namespace {
  59
  60 class ImplicitNullChecks : public MachineFunctionPass {
  61   /// Represents one null check that can be made implicit.
  62   struct NullCheck {
  63     // The memory operation the null check can be folded into.
  64     MachineInstr *MemOperation;
  65
  66     // The instruction actually doing the null check (Ptr != 0).
  67     MachineInstr *CheckOperation;
  68
  69     // The block the check resides in.
  70     MachineBasicBlock *CheckBlock;
  71
  72     // The block branched to if the pointer is non-null.
  73     MachineBasicBlock *NotNullSucc;
  74
  75     // The block branched to if the pointer is null.
  76     MachineBasicBlock *NullSucc;
  77
  78     NullCheck()
  79         : MemOperation(), CheckOperation(), CheckBlock(), NotNullSucc(),
  80           NullSucc() {}
  81
  82     explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation,
  83                        MachineBasicBlock *checkBlock,
  84                        MachineBasicBlock *notNullSucc,
  85                        MachineBasicBlock *nullSucc)
  86         : MemOperation(memOperation), CheckOperation(checkOperation),
  87           CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc) {
  88     }
  89   };
  90
  91   const TargetInstrInfo *TII = nullptr;
  92   const TargetRegisterInfo *TRI = nullptr;
  93   MachineModuleInfo *MMI = nullptr;
  94
  95   bool analyzeBlockForNullChecks(MachineBasicBlock &MBB,
  96                                  SmallVectorImpl<NullCheck> &NullCheckList);
  97   MachineInstr *insertFaultingLoad(MachineInstr *LoadMI, MachineBasicBlock *MBB,
  98                                    MCSymbol *HandlerLabel);
  99   void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList);
 100
 101 public:
 102   static char ID;
 103
 104   ImplicitNullChecks() : MachineFunctionPass(ID) {
 105     initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry());
 106   }
 107
 108   bool runOnMachineFunction(MachineFunction &MF) override;
 109 };
 110 }
 111
 112 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
 113   TII = MF.getSubtarget().getInstrInfo();
 114   TRI = MF.getRegInfo().getTargetRegisterInfo();
 115   MMI = &MF.getMMI();
 116
 117   SmallVector<NullCheck, 16> NullCheckList;
 118
 119   for (auto &MBB : MF)
 120     analyzeBlockForNullChecks(MBB, NullCheckList);
 121
 122   if (!NullCheckList.empty())
 123     rewriteNullChecks(NullCheckList);
 124
 125   return !NullCheckList.empty();
 126 }
 127
 128 /// Analyze MBB to check if its terminating branch can be turned into an
 129 /// implicit null check.  If yes, append a description of the said null check to
 130 /// NullCheckList and return true, else return false.
 131 bool ImplicitNullChecks::analyzeBlockForNullChecks(
 132     MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
 133   typedef TargetInstrInfo::MachineBranchPredicate MachineBranchPredicate;
 134
 135   MDNode *BranchMD =
 136       MBB.getBasicBlock()
 137           ? MBB.getBasicBlock()->getTerminator()->getMetadata("make.implicit")
 138           : nullptr;
 139   if (!BranchMD)
 140     return false;
 141
 142   MachineBranchPredicate MBP;
 143
 144   if (TII->AnalyzeBranchPredicate(MBB, MBP, true))
 145     return false;
 146
 147   // Is the predicate comparing an integer to zero?
 148   if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
 149         (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
 150          MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
 151     return false;
 152
 153   // If we cannot erase the test instruction itself, then making the null check
 154   // implicit does not buy us much.
 155   if (!MBP.SingleUseCondition)
 156     return false;
 157
 158   MachineBasicBlock *NotNullSucc, *NullSucc;
 159
 160   if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
 161     NotNullSucc = MBP.TrueDest;
 162     NullSucc = MBP.FalseDest;
 163   } else {
 164     NotNullSucc = MBP.FalseDest;
 165     NullSucc = MBP.TrueDest;
 166   }
 167
 168   // We handle the simplest case for now.  We can potentially do better by using
 169   // the machine dominator tree.
 170   if (NotNullSucc->pred_size() != 1)
 171     return false;
 172
 173   // Starting with a code fragment like:
 174   //
 175   //   test %RAX, %RAX
 176   //   jne LblNotNull
 177   //
 178   //  LblNull:
 179   //   callq throw_NullPointerException
 180   //
 181   //  LblNotNull:
 182   //   Inst0
 183   //   Inst1
 184   //   ...
 185   //   Def = Load (%RAX + <offset>)
 186   //   ...
 187   //
 188   //
 189   // we want to end up with
 190   //
 191   //   Def = TrappingLoad (%RAX + <offset>), LblNull
 192   //   jmp LblNotNull ;; explicit or fallthrough
 193   //
 194   //  LblNotNull:
 195   //   Inst0
 196   //   Inst1
 197   //   ...
 198   //
 199   //  LblNull:
 200   //   callq throw_NullPointerException
 201   //
 202
 203   unsigned PointerReg = MBP.LHS.getReg();
 204
 205   // As we scan NotNullSucc for a suitable load instruction, we keep track of
 206   // the registers defined and used by the instructions we scan past.  This bit
 207   // of information lets us decide if it is legal to hoist the load instruction
 208   // we find (if we do find such an instruction) to before NotNullSucc.
 209   DenseSet<unsigned> RegDefs, RegUses;
 210
 211   // Returns true if it is safe to reorder MI to before NotNullSucc.
 212   auto IsSafeToHoist = [&](MachineInstr *MI) {
 213     // Right now we don't want to worry about LLVM's memory model.  This can be
 214     // made more precise later.
 215     for (auto *MMO : MI->memoperands())
 216       if (!MMO->isUnordered())
 217         return false;
 218
 219     for (auto &MO : MI->operands()) {
 220       if (MO.isReg() && MO.getReg()) {
 221         for (unsigned Reg : RegDefs)
 222           if (TRI->regsOverlap(Reg, MO.getReg()))
 223             return false;  // We found a write-after-write or read-after-write
 224
 225         if (MO.isDef())
 226           for (unsigned Reg : RegUses)
 227             if (TRI->regsOverlap(Reg, MO.getReg()))
 228               return false;  // We found a write-after-read
 229       }
 230     }
 231
 232     return true;
 233   };
 234
 235   for (auto MII = NotNullSucc->begin(), MIE = NotNullSucc->end(); MII != MIE;
 236        ++MII) {
 237     MachineInstr *MI = &*MII;
 238     unsigned BaseReg, Offset;
 239     if (TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI))
 240       if (MI->mayLoad() && !MI->isPredicable() && BaseReg == PointerReg &&
 241           Offset < PageSize && MI->getDesc().getNumDefs() <= 1 &&
 242           IsSafeToHoist(MI)) {
 243         NullCheckList.emplace_back(MI, MBP.ConditionDef, &MBB, NotNullSucc,
 244                                    NullSucc);
 245         return true;
 246       }
 247
 248     // MI did not match our criteria for conversion to a trapping load.  Check
 249     // if we can continue looking.
 250
 251     if (MI->mayStore() || MI->hasUnmodeledSideEffects())
 252       return false;
 253
 254     for (auto *MMO : MI->memoperands())
 255       // Right now we don't want to worry about LLVM's memory model.
 256       if (!MMO->isUnordered())
 257         return false;
 258
 259     // It _may_ be okay to reorder a later load instruction across MI.  Make a
 260     // note of its operands so that we can make the legality check if we find a
 261     // suitable load instruction:
 262
 263     for (auto &MO : MI->operands()) {
 264       if (!MO.isReg() || !MO.getReg())
 265         continue;
 266
 267       if (MO.isDef())
 268         RegDefs.insert(MO.getReg());
 269       else
 270         RegUses.insert(MO.getReg());
 271     }
 272   }
 273
 274   return false;
 275 }
 276
 277 /// Wrap a machine load instruction, LoadMI, into a FAULTING_LOAD_OP machine
 278 /// instruction.  The FAULTING_LOAD_OP instruction does the same load as LoadMI
 279 /// (defining the same register), and branches to HandlerLabel if the load
 280 /// faults.  The FAULTING_LOAD_OP instruction is inserted at the end of MBB.
 281 MachineInstr *ImplicitNullChecks::insertFaultingLoad(MachineInstr *LoadMI,
 282                                                      MachineBasicBlock *MBB,
 283                                                      MCSymbol *HandlerLabel) {
 284   const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for
 285                                  // all targets.
 286
 287   DebugLoc DL;
 288   unsigned NumDefs = LoadMI->getDesc().getNumDefs();
 289   assert(NumDefs <= 1 && "other cases unhandled!");
 290
 291   unsigned DefReg = NoRegister;
 292   if (NumDefs != 0) {
 293     DefReg = LoadMI->defs().begin()->getReg();
 294     assert(std::distance(LoadMI->defs().begin(), LoadMI->defs().end()) == 1 &&
 295            "expected exactly one def!");
 296   }
 297
 298   auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_LOAD_OP), DefReg)
 299                  .addSym(HandlerLabel)
 300                  .addImm(LoadMI->getOpcode());
 301
 302   for (auto &MO : LoadMI->uses())
 303     MIB.addOperand(MO);
 304
 305   MIB.setMemRefs(LoadMI->memoperands_begin(), LoadMI->memoperands_end());
 306
 307   return MIB;
 308 }
 309
 310 /// Rewrite the null checks in NullCheckList into implicit null checks.
 311 void ImplicitNullChecks::rewriteNullChecks(
 312     ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
 313   DebugLoc DL;
 314
 315   for (auto &NC : NullCheckList) {
 316     MCSymbol *HandlerLabel = MMI->getContext().createTempSymbol();
 317
 318     // Remove the conditional branch dependent on the null check.
 319     unsigned BranchesRemoved = TII->RemoveBranch(*NC.CheckBlock);
 320     (void)BranchesRemoved;
 321     assert(BranchesRemoved > 0 && "expected at least one branch!");
 322
 323     // Insert a faulting load where the conditional branch was originally.  We
 324     // check earlier ensures that this bit of code motion is legal.  We do not
 325     // touch the successors list for any basic block since we haven't changed
 326     // control flow, we've just made it implicit.
 327     insertFaultingLoad(NC.MemOperation, NC.CheckBlock, HandlerLabel);
 328     NC.MemOperation->eraseFromParent();
 329     NC.CheckOperation->eraseFromParent();
 330
 331     // Insert an *unconditional* branch to not-null successor.
 332     TII->InsertBranch(*NC.CheckBlock, NC.NotNullSucc, nullptr, /*Cond=*/None,
 333                       DL);
 334
 335     // Emit the HandlerLabel as an EH_LABEL.
 336     BuildMI(*NC.NullSucc, NC.NullSucc->begin(), DL,
 337             TII->get(TargetOpcode::EH_LABEL)).addSym(HandlerLabel);
 338
 339     NumImplicitNullChecks++;
 340   }
 341 }
 342
 343 char ImplicitNullChecks::ID = 0;
 344 char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID;
 345 INITIALIZE_PASS_BEGIN(ImplicitNullChecks, "implicit-null-checks",
 346                       "Implicit null checks", false, false)
 347 INITIALIZE_PASS_END(ImplicitNullChecks, "implicit-null-checks",
 348                     "Implicit null checks", false, false)