1 //===-- ImplicitNullChecks.cpp - Fold null checks into memory accesses ----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass turns explicit null checks of the form
19 // faulting_load_op("movl (%r10), %esi", throw_npe)
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
26 //===----------------------------------------------------------------------===//
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"
46 static cl::opt<unsigned> PageSize("imp-null-check-page-size",
47 cl::desc("The page size of the target in "
51 #define DEBUG_TYPE "implicit-null-checks"
53 STATISTIC(NumImplicitNullChecks,
54 "Number of explicit null checks made implicit");
58 class ImplicitNullChecks : public MachineFunctionPass {
59 /// Represents one null check that can be made implicit.
61 // The memory operation the null check can be folded into.
62 MachineInstr *MemOperation;
64 // The instruction actually doing the null check (Ptr != 0).
65 MachineInstr *CheckOperation;
67 // The block the check resides in.
68 MachineBasicBlock *CheckBlock;
70 // The block branched to if the pointer is non-null.
71 MachineBasicBlock *NotNullSucc;
73 // The block branched to if the pointer is null.
74 MachineBasicBlock *NullSucc;
77 : MemOperation(), CheckOperation(), CheckBlock(), NotNullSucc(),
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) {
89 const TargetInstrInfo *TII = nullptr;
90 const TargetRegisterInfo *TRI = nullptr;
91 MachineModuleInfo *MMI = nullptr;
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);
102 ImplicitNullChecks() : MachineFunctionPass(ID) {
103 initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry());
106 bool runOnMachineFunction(MachineFunction &MF) override;
110 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
111 TII = MF.getSubtarget().getInstrInfo();
112 TRI = MF.getRegInfo().getTargetRegisterInfo();
115 SmallVector<NullCheck, 16> NullCheckList;
118 analyzeBlockForNullChecks(MBB, NullCheckList);
120 if (!NullCheckList.empty())
121 rewriteNullChecks(NullCheckList);
123 return !NullCheckList.empty();
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;
135 ? MBB.getBasicBlock()->getTerminator()->getMetadata("make.implicit")
140 MachineBranchPredicate MBP;
142 if (TII->AnalyzeBranchPredicate(MBB, MBP, true))
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)))
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)
156 MachineBasicBlock *NotNullSucc, *NullSucc;
158 if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
159 NotNullSucc = MBP.TrueDest;
160 NullSucc = MBP.FalseDest;
162 NotNullSucc = MBP.FalseDest;
163 NullSucc = MBP.TrueDest;
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)
171 // Starting with a code fragment like:
177 // callq throw_NullPointerException
180 // Def = Load (%RAX + <offset>)
184 // we want to end up with
186 // Def = TrappingLoad (%RAX + <offset>), LblNull
187 // jmp LblNotNull ;; explicit or fallthrough
193 // callq throw_NullPointerException
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,
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) {
218 unsigned NumDefs = LoadMI->getDesc().getNumDefs();
219 assert(NumDefs == 1 && "other cases unhandled!");
222 unsigned DefReg = LoadMI->defs().begin()->getReg();
223 assert(std::distance(LoadMI->defs().begin(), LoadMI->defs().end()) == 1 &&
224 "expected exactly one def!");
226 auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_LOAD_OP), DefReg)
227 .addSym(HandlerLabel)
228 .addImm(LoadMI->getOpcode());
230 for (auto &MO : LoadMI->uses())
233 MIB.setMemRefs(LoadMI->memoperands_begin(), LoadMI->memoperands_end());
238 /// Rewrite the null checks in NullCheckList into implicit null checks.
239 void ImplicitNullChecks::rewriteNullChecks(
240 ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
243 for (auto &NC : NullCheckList) {
244 MCSymbol *HandlerLabel = MMI->getContext().createTempSymbol();
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!");
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();
259 // Insert an *unconditional* branch to not-null successor.
260 TII->InsertBranch(*NC.CheckBlock, NC.NotNullSucc, nullptr, /*Cond=*/None,
263 // Emit the HandlerLabel as an EH_LABEL.
264 BuildMI(*NC.NullSucc, NC.NullSucc->begin(), DL,
265 TII->get(TargetOpcode::EH_LABEL)).addSym(HandlerLabel);
267 NumImplicitNullChecks++;
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)