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;
127 MachineBranchPredicate MBP;
129 if (TII->AnalyzeBranchPredicate(MBB, MBP, true))
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)))
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)
143 MachineBasicBlock *NotNullSucc, *NullSucc;
145 if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
146 NotNullSucc = MBP.TrueDest;
147 NullSucc = MBP.FalseDest;
149 NotNullSucc = MBP.FalseDest;
150 NullSucc = MBP.TrueDest;
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)
158 // Starting with a code fragment like:
164 // callq throw_NullPointerException
167 // Def = Load (%RAX + <offset>)
171 // we want to end up with
173 // Def = TrappingLoad (%RAX + <offset>), LblNull
174 // jmp LblNotNull ;; explicit or fallthrough
180 // callq throw_NullPointerException
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,
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) {
205 unsigned NumDefs = LoadMI->getDesc().getNumDefs();
206 assert(NumDefs == 1 && "other cases unhandled!");
209 unsigned DefReg = LoadMI->defs().begin()->getReg();
210 assert(std::distance(LoadMI->defs().begin(), LoadMI->defs().end()) == 1 &&
211 "expected exactly one def!");
213 auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_LOAD_OP), DefReg)
214 .addSym(HandlerLabel)
215 .addImm(LoadMI->getOpcode());
217 for (auto &MO : LoadMI->uses())
220 MIB.setMemRefs(LoadMI->memoperands_begin(), LoadMI->memoperands_end());
225 /// Rewrite the null checks in NullCheckList into implicit null checks.
226 void ImplicitNullChecks::rewriteNullChecks(
227 ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
230 for (auto &NC : NullCheckList) {
231 MCSymbol *HandlerLabel = MMI->getContext().createTempSymbol();
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!");
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();
246 // Insert an *unconditional* branch to not-null successor.
247 TII->InsertBranch(*NC.CheckBlock, NC.NotNullSucc, nullptr, /*Cond=*/None,
250 // Emit the HandlerLabel as an EH_LABEL.
251 BuildMI(*NC.NullSucc, NC.NullSucc->begin(), DL,
252 TII->get(TargetOpcode::EH_LABEL)).addSym(HandlerLabel);
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)