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)
269