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 } // namespace
 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   MachineBranchPredicate MBP;
 128
 129   if (TII->AnalyzeBranchPredicate(MBB, MBP, true))
 130     return false;
 131
 132   // Is the predicate comparing an integer to zero?
 133   if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
 134         (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
 135          MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
 136     return false;
 137
 138   // If we cannot erase the test instruction itself, then making the null check
 139   // implicit does not buy us much.
 140   if (!MBP.SingleUseCondition)
 141     return false;
 142
 143   MachineBasicBlock *NotNullSucc, *NullSucc;
 144
 145   if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
 146     NotNullSucc = MBP.TrueDest;
 147     NullSucc = MBP.FalseDest;
 148   } else {
 149     NotNullSucc = MBP.FalseDest;
 150     NullSucc = MBP.TrueDest;
 151   }
 152
 153   // We handle the simplest case for now.  We can potentially do better by using
 154   // the machine dominator tree.
 155   if (NotNullSucc->pred_size() != 1)
 156     return false;
 157
 158   // Starting with a code fragment like:
 159   //
 160   //   test %RAX, %RAX
 161   //   jne LblNotNull
 162   //
 163   //  LblNull:
 164   //   callq throw_NullPointerException
 165   //
 166   //  LblNotNull:
 167   //   Def = Load (%RAX + <offset>)
 168   //   ...
 169   //
 170   //
 171   // we want to end up with
 172   //
 173   //   Def = TrappingLoad (%RAX + <offset>), LblNull
 174   //   jmp LblNotNull ;; explicit or fallthrough
 175   //
 176   //  LblNotNull:
 177   //   ...
 178   //
 179   //  LblNull:
 180   //   callq throw_NullPointerException
 181   //
 182
 183   unsigned PointerReg = MBP.LHS.getReg();
 184   MachineInstr *MemOp = &*NotNullSucc->begin();
 185   unsigned BaseReg, Offset;
 186   if (TII->getMemOpBaseRegImmOfs(MemOp, BaseReg, Offset, TRI))
 187     if (MemOp->mayLoad() && !MemOp->isPredicable() && BaseReg == PointerReg &&
 188         Offset < PageSize && MemOp->getDesc().getNumDefs() == 1) {
 189       NullCheckList.emplace_back(MemOp, MBP.ConditionDef, &MBB, NotNullSucc,
 190                                  NullSucc);
 191       return true;
 192     }
 193
 194   return false;
 195 }
 196
 197 /// Wrap a machine load instruction, LoadMI, into a FAULTING_LOAD_OP machine
 198 /// instruction.  The FAULTING_LOAD_OP instruction does the same load as LoadMI
 199 /// (defining the same register), and branches to HandlerLabel if the load
 200 /// faults.  The FAULTING_LOAD_OP instruction is inserted at the end of MBB.
 201 MachineInstr *ImplicitNullChecks::insertFaultingLoad(MachineInstr *LoadMI,
 202                                                      MachineBasicBlock *MBB,
 203                                                      MCSymbol *HandlerLabel) {
 204   DebugLoc DL;
 205   unsigned NumDefs = LoadMI->getDesc().getNumDefs();
 206   assert(NumDefs == 1 && "other cases unhandled!");
 207   (void)NumDefs;
 208
 209   unsigned DefReg = LoadMI->defs().begin()->getReg();
 210   assert(std::distance(LoadMI->defs().begin(), LoadMI->defs().end()) == 1 &&
 211          "expected exactly one def!");
 212
 213   auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_LOAD_OP), DefReg)
 214                  .addSym(HandlerLabel)
 215                  .addImm(LoadMI->getOpcode());
 216
 217   for (auto &MO : LoadMI->uses())
 218     MIB.addOperand(MO);
 219
 220   MIB.setMemRefs(LoadMI->memoperands_begin(), LoadMI->memoperands_end());
 221
 222   return MIB;
 223 }
 224
 225 /// Rewrite the null checks in NullCheckList into implicit null checks.
 226 void ImplicitNullChecks::rewriteNullChecks(
 227     ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
 228   DebugLoc DL;
 229
 230   for (auto &NC : NullCheckList) {
 231     MCSymbol *HandlerLabel = MMI->getContext().createTempSymbol();
 232
 233     // Remove the conditional branch dependent on the null check.
 234     unsigned BranchesRemoved = TII->RemoveBranch(*NC.CheckBlock);
 235     (void)BranchesRemoved;
 236     assert(BranchesRemoved > 0 && "expected at least one branch!");
 237
 238     // Insert a faulting load where the conditional branch was originally.  We
 239     // check earlier ensures that this bit of code motion is legal.  We do not
 240     // touch the successors list for any basic block since we haven't changed
 241     // control flow, we've just made it implicit.
 242     insertFaultingLoad(NC.MemOperation, NC.CheckBlock, HandlerLabel);
 243     NC.MemOperation->removeFromParent();
 244     NC.CheckOperation->eraseFromParent();
 245
 246     // Insert an *unconditional* branch to not-null successor.
 247     TII->InsertBranch(*NC.CheckBlock, NC.NotNullSucc, nullptr, /*Cond=*/None,
 248                       DL);
 249
 250     // Emit the HandlerLabel as an EH_LABEL.
 251     BuildMI(*NC.NullSucc, NC.NullSucc->begin(), DL,
 252             TII->get(TargetOpcode::EH_LABEL)).addSym(HandlerLabel);
 253   }
 254 }
 255
 256 char ImplicitNullChecks::ID = 0;
 257 char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID;
 258 INITIALIZE_PASS_BEGIN(ImplicitNullChecks, "implicit-null-checks",
 259                       "Implicit null checks", false, false)
 260 INITIALIZE_PASS_END(ImplicitNullChecks, "implicit-null-checks",
 261                     "Implicit null checks", false, false)