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