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