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/SmallVector.h"
  29 #include "llvm/CodeGen/Passes.h"
  30 #include "llvm/CodeGen/MachineFunction.h"
  31 #include "llvm/CodeGen/MachineOperand.h"
  32 #include "llvm/CodeGen/MachineFunctionPass.h"
  33 #include "llvm/CodeGen/MachineInstrBuilder.h"
  34 #include "llvm/CodeGen/MachineRegisterInfo.h"
  35 #include "llvm/CodeGen/MachineModuleInfo.h"
  36 #include "llvm/IR/BasicBlock.h"
  37 #include "llvm/IR/Instruction.h"
  38 #include "llvm/Support/CommandLine.h"
  39 #include "llvm/Support/Debug.h"
  40 #include "llvm/Target/TargetSubtargetInfo.h"
  41 #include "llvm/Target/TargetInstrInfo.h"
  42
  43 using namespace llvm;
  44
  45 static cl::opt<unsigned> PageSize("imp-null-check-page-size",
  46                                   cl::desc("The page size of the target in "
  47                                            "bytes"),
  48                                   cl::init(4096));
  49
  50 namespace {
  51
  52 class ImplicitNullChecks : public MachineFunctionPass {
  53   /// Represents one null check that can be made implicit.
  54   struct NullCheck {
  55     // The memory operation the null check can be folded into.
  56     MachineInstr *MemOperation;
  57
  58     // The instruction actually doing the null check (Ptr != 0).
  59     MachineInstr *CheckOperation;
  60
  61     // The block the check resides in.
  62     MachineBasicBlock *CheckBlock;
  63
  64     // The block branched to if the pointer is non-null.
  65     MachineBasicBlock *NotNullSucc;
  66
  67     // The block branched to if the pointer is null.
  68     MachineBasicBlock *NullSucc;
  69
  70     NullCheck()
  71         : MemOperation(), CheckOperation(), CheckBlock(), NotNullSucc(),
  72           NullSucc() {}
  73
  74     explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation,
  75                        MachineBasicBlock *checkBlock,
  76                        MachineBasicBlock *notNullSucc,
  77                        MachineBasicBlock *nullSucc)
  78         : MemOperation(memOperation), CheckOperation(checkOperation),
  79           CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc) {
  80     }
  81   };
  82
  83   const TargetInstrInfo *TII = nullptr;
  84   const TargetRegisterInfo *TRI = nullptr;
  85   MachineModuleInfo *MMI = nullptr;
  86
  87   bool analyzeBlockForNullChecks(MachineBasicBlock &MBB,
  88                                  SmallVectorImpl<NullCheck> &NullCheckList);
  89   MachineInstr *insertFaultingLoad(MachineInstr *LoadMI, MachineBasicBlock *MBB,
  90                                    MCSymbol *HandlerLabel);
  91   void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList);
  92
  93 public:
  94   static char ID;
  95
  96   ImplicitNullChecks() : MachineFunctionPass(ID) {
  97     initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry());
  98   }
  99
 100   bool runOnMachineFunction(MachineFunction &MF) override;
 101 };
 102 }
 103
 104 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
 105   TII = MF.getSubtarget().getInstrInfo();
 106   TRI = MF.getRegInfo().getTargetRegisterInfo();
 107   MMI = &MF.getMMI();
 108
 109   SmallVector<NullCheck, 16> NullCheckList;
 110
 111   for (auto &MBB : MF)
 112     analyzeBlockForNullChecks(MBB, NullCheckList);
 113
 114   if (!NullCheckList.empty())
 115     rewriteNullChecks(NullCheckList);
 116
 117   return !NullCheckList.empty();
 118 }
 119
 120 /// Analyze MBB to check if its terminating branch can be turned into an
 121 /// implicit null check.  If yes, append a description of the said null check to
 122 /// NullCheckList and return true, else return false.
 123 bool ImplicitNullChecks::analyzeBlockForNullChecks(
 124     MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
 125   typedef TargetInstrInfo::MachineBranchPredicate MachineBranchPredicate;
 126
 127   MDNode *BranchMD =
 128       MBB.getBasicBlock()
 129           ? MBB.getBasicBlock()->getTerminator()->getMetadata("make.implicit")
 130           : nullptr;
 131   if (!BranchMD)
 132     return false;
 133
 134   MachineBranchPredicate MBP;
 135
 136   if (TII->AnalyzeBranchPredicate(MBB, MBP, true))
 137     return false;
 138
 139   // Is the predicate comparing an integer to zero?
 140   if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
 141         (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
 142          MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
 143     return false;
 144
 145   // If we cannot erase the test instruction itself, then making the null check
 146   // implicit does not buy us much.
 147   if (!MBP.SingleUseCondition)
 148     return false;
 149
 150   MachineBasicBlock *NotNullSucc, *NullSucc;
 151
 152   if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
 153     NotNullSucc = MBP.TrueDest;
 154     NullSucc = MBP.FalseDest;
 155   } else {
 156     NotNullSucc = MBP.FalseDest;
 157     NullSucc = MBP.TrueDest;
 158   }
 159
 160   // We handle the simplest case for now.  We can potentially do better by using
 161   // the machine dominator tree.
 162   if (NotNullSucc->pred_size() != 1)
 163     return false;
 164
 165   // Starting with a code fragment like:
 166   //
 167   //   test %RAX, %RAX
 168   //   jne LblNotNull
 169   //
 170   //  LblNull:
 171   //   callq throw_NullPointerException
 172   //
 173   //  LblNotNull:
 174   //   Def = Load (%RAX + <offset>)
 175   //   ...
 176   //
 177   //
 178   // we want to end up with
 179   //
 180   //   Def = TrappingLoad (%RAX + <offset>), LblNull
 181   //   jmp LblNotNull ;; explicit or fallthrough
 182   //
 183   //  LblNotNull:
 184   //   ...
 185   //
 186   //  LblNull:
 187   //   callq throw_NullPointerException
 188   //
 189
 190   unsigned PointerReg = MBP.LHS.getReg();
 191   MachineInstr *MemOp = &*NotNullSucc->begin();
 192   unsigned BaseReg, Offset;
 193   if (TII->getMemOpBaseRegImmOfs(MemOp, BaseReg, Offset, TRI))
 194     if (MemOp->mayLoad() && !MemOp->isPredicable() && BaseReg == PointerReg &&
 195         Offset < PageSize && MemOp->getDesc().getNumDefs() == 1) {
 196       NullCheckList.emplace_back(MemOp, MBP.ConditionDef, &MBB, NotNullSucc,
 197                                  NullSucc);
 198       return true;
 199     }
 200
 201   return false;
 202 }
 203
 204 /// Wrap a machine load instruction, LoadMI, into a FAULTING_LOAD_OP machine
 205 /// instruction.  The FAULTING_LOAD_OP instruction does the same load as LoadMI
 206 /// (defining the same register), and branches to HandlerLabel if the load
 207 /// faults.  The FAULTING_LOAD_OP instruction is inserted at the end of MBB.
 208 MachineInstr *ImplicitNullChecks::insertFaultingLoad(MachineInstr *LoadMI,
 209                                                      MachineBasicBlock *MBB,
 210                                                      MCSymbol *HandlerLabel) {
 211   DebugLoc DL;
 212   unsigned NumDefs = LoadMI->getDesc().getNumDefs();
 213   assert(NumDefs == 1 && "other cases unhandled!");
 214   (void)NumDefs;
 215
 216   unsigned DefReg = LoadMI->defs().begin()->getReg();
 217   assert(std::distance(LoadMI->defs().begin(), LoadMI->defs().end()) == 1 &&
 218          "expected exactly one def!");
 219
 220   auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_LOAD_OP), DefReg)
 221                  .addSym(HandlerLabel)
 222                  .addImm(LoadMI->getOpcode());
 223
 224   for (auto &MO : LoadMI->uses())
 225     MIB.addOperand(MO);
 226
 227   MIB.setMemRefs(LoadMI->memoperands_begin(), LoadMI->memoperands_end());
 228
 229   return MIB;
 230 }
 231
 232 /// Rewrite the null checks in NullCheckList into implicit null checks.
 233 void ImplicitNullChecks::rewriteNullChecks(
 234     ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
 235   DebugLoc DL;
 236
 237   for (auto &NC : NullCheckList) {
 238     MCSymbol *HandlerLabel = MMI->getContext().createTempSymbol();
 239
 240     // Remove the conditional branch dependent on the null check.
 241     unsigned BranchesRemoved = TII->RemoveBranch(*NC.CheckBlock);
 242     (void)BranchesRemoved;
 243     assert(BranchesRemoved > 0 && "expected at least one branch!");
 244
 245     // Insert a faulting load where the conditional branch was originally.  We
 246     // check earlier ensures that this bit of code motion is legal.  We do not
 247     // touch the successors list for any basic block since we haven't changed
 248     // control flow, we've just made it implicit.
 249     insertFaultingLoad(NC.MemOperation, NC.CheckBlock, HandlerLabel);
 250     NC.MemOperation->removeFromParent();
 251     NC.CheckOperation->eraseFromParent();
 252
 253     // Insert an *unconditional* branch to not-null successor.
 254     TII->InsertBranch(*NC.CheckBlock, NC.NotNullSucc, nullptr, /*Cond=*/None,
 255                       DL);
 256
 257     // Emit the HandlerLabel as an EH_LABEL.
 258     BuildMI(*NC.NullSucc, NC.NullSucc->begin(), DL,
 259             TII->get(TargetOpcode::EH_LABEL)).addSym(HandlerLabel);
 260   }
 261 }
 262
 263 char ImplicitNullChecks::ID = 0;
 264 char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID;
 265 INITIALIZE_PASS_BEGIN(ImplicitNullChecks, "implicit-null-checks",
 266                       "Implicit null checks", false, false)
 267 INITIALIZE_PASS_END(ImplicitNullChecks, "implicit-null-checks",
 268                     "Implicit null checks", false, false)