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/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"
45 static cl::opt<unsigned> PageSize("imp-null-check-page-size",
46 cl::desc("The page size of the target in "
52 class ImplicitNullChecks : public MachineFunctionPass {
53 /// Represents one null check that can be made implicit.
55 // The memory operation the null check can be folded into.
56 MachineInstr *MemOperation;
58 // The instruction actually doing the null check (Ptr != 0).
59 MachineInstr *CheckOperation;
61 // The block the check resides in.
62 MachineBasicBlock *CheckBlock;
64 // The block branched to if the pointer is non-null.
65 MachineBasicBlock *NotNullSucc;
67 // The block branched to if the pointer is null.
68 MachineBasicBlock *NullSucc;
71 : MemOperation(), CheckOperation(), CheckBlock(), NotNullSucc(),
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) {
83 const TargetInstrInfo *TII = nullptr;
84 const TargetRegisterInfo *TRI = nullptr;
85 MachineModuleInfo *MMI = nullptr;
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);
96 ImplicitNullChecks() : MachineFunctionPass(ID) {
97 initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry());
100 bool runOnMachineFunction(MachineFunction &MF) override;
104 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
105 TII = MF.getSubtarget().getInstrInfo();
106 TRI = MF.getRegInfo().getTargetRegisterInfo();
109 SmallVector<NullCheck, 16> NullCheckList;
112 analyzeBlockForNullChecks(MBB, NullCheckList);
114 if (!NullCheckList.empty())
115 rewriteNullChecks(NullCheckList);
117 return !NullCheckList.empty();
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;
129 ? MBB.getBasicBlock()->getTerminator()->getMetadata("make.implicit")
134 MachineBranchPredicate MBP;
136 if (TII->AnalyzeBranchPredicate(MBB, MBP, true))
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)))
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)
150 MachineBasicBlock *NotNullSucc, *NullSucc;
152 if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
153 NotNullSucc = MBP.TrueDest;
154 NullSucc = MBP.FalseDest;
156 NotNullSucc = MBP.FalseDest;
157 NullSucc = MBP.TrueDest;
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)
165 // Starting with a code fragment like:
171 // callq throw_NullPointerException
174 // Def = Load (%RAX + <offset>)
178 // we want to end up with
180 // Def = TrappingLoad (%RAX + <offset>), LblNull
181 // jmp LblNotNull ;; explicit or fallthrough
187 // callq throw_NullPointerException
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,
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) {
212 unsigned NumDefs = LoadMI->getDesc().getNumDefs();
213 assert(NumDefs == 1 && "other cases unhandled!");
216 unsigned DefReg = LoadMI->defs().begin()->getReg();
217 assert(std::distance(LoadMI->defs().begin(), LoadMI->defs().end()) == 1 &&
218 "expected exactly one def!");
220 auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_LOAD_OP), DefReg)
221 .addSym(HandlerLabel)
222 .addImm(LoadMI->getOpcode());
224 for (auto &MO : LoadMI->uses())
227 MIB.setMemRefs(LoadMI->memoperands_begin(), LoadMI->memoperands_end());
232 /// Rewrite the null checks in NullCheckList into implicit null checks.
233 void ImplicitNullChecks::rewriteNullChecks(
234 ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
237 for (auto &NC : NullCheckList) {
238 MCSymbol *HandlerLabel = MMI->getContext().createTempSymbol();
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!");
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();
253 // Insert an *unconditional* branch to not-null successor.
254 TII->InsertBranch(*NC.CheckBlock, NC.NotNullSucc, nullptr, /*Cond=*/None,
257 // Emit the HandlerLabel as an EH_LABEL.
258 BuildMI(*NC.NullSucc, NC.NullSucc->begin(), DL,
259 TII->get(TargetOpcode::EH_LABEL)).addSym(HandlerLabel);
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)