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/DenseSet.h"
29 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/CodeGen/Passes.h"
32 #include "llvm/CodeGen/MachineFunction.h"
33 #include "llvm/CodeGen/MachineMemOperand.h"
34 #include "llvm/CodeGen/MachineOperand.h"
35 #include "llvm/CodeGen/MachineFunctionPass.h"
36 #include "llvm/CodeGen/MachineInstrBuilder.h"
37 #include "llvm/CodeGen/MachineRegisterInfo.h"
38 #include "llvm/CodeGen/MachineModuleInfo.h"
39 #include "llvm/IR/BasicBlock.h"
40 #include "llvm/IR/Instruction.h"
41 #include "llvm/Support/CommandLine.h"
42 #include "llvm/Support/Debug.h"
43 #include "llvm/Target/TargetSubtargetInfo.h"
44 #include "llvm/Target/TargetInstrInfo.h"
48 static cl::opt<unsigned> PageSize("imp-null-check-page-size",
49 cl::desc("The page size of the target in "
53 #define DEBUG_TYPE "implicit-null-checks"
55 STATISTIC(NumImplicitNullChecks,
56 "Number of explicit null checks made implicit");
60 class ImplicitNullChecks : public MachineFunctionPass {
61 /// Represents one null check that can be made implicit.
63 // The memory operation the null check can be folded into.
64 MachineInstr *MemOperation;
66 // The instruction actually doing the null check (Ptr != 0).
67 MachineInstr *CheckOperation;
69 // The block the check resides in.
70 MachineBasicBlock *CheckBlock;
72 // The block branched to if the pointer is non-null.
73 MachineBasicBlock *NotNullSucc;
75 // The block branched to if the pointer is null.
76 MachineBasicBlock *NullSucc;
79 : MemOperation(), CheckOperation(), CheckBlock(), NotNullSucc(),
82 explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation,
83 MachineBasicBlock *checkBlock,
84 MachineBasicBlock *notNullSucc,
85 MachineBasicBlock *nullSucc)
86 : MemOperation(memOperation), CheckOperation(checkOperation),
87 CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc) {
91 const TargetInstrInfo *TII = nullptr;
92 const TargetRegisterInfo *TRI = nullptr;
93 MachineModuleInfo *MMI = nullptr;
95 bool analyzeBlockForNullChecks(MachineBasicBlock &MBB,
96 SmallVectorImpl<NullCheck> &NullCheckList);
97 MachineInstr *insertFaultingLoad(MachineInstr *LoadMI, MachineBasicBlock *MBB,
98 MCSymbol *HandlerLabel);
99 void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList);
104 ImplicitNullChecks() : MachineFunctionPass(ID) {
105 initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry());
108 bool runOnMachineFunction(MachineFunction &MF) override;
112 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
113 TII = MF.getSubtarget().getInstrInfo();
114 TRI = MF.getRegInfo().getTargetRegisterInfo();
117 SmallVector<NullCheck, 16> NullCheckList;
120 analyzeBlockForNullChecks(MBB, NullCheckList);
122 if (!NullCheckList.empty())
123 rewriteNullChecks(NullCheckList);
125 return !NullCheckList.empty();
128 /// Analyze MBB to check if its terminating branch can be turned into an
129 /// implicit null check. If yes, append a description of the said null check to
130 /// NullCheckList and return true, else return false.
131 bool ImplicitNullChecks::analyzeBlockForNullChecks(
132 MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
133 typedef TargetInstrInfo::MachineBranchPredicate MachineBranchPredicate;
137 ? MBB.getBasicBlock()->getTerminator()->getMetadata("make.implicit")
142 MachineBranchPredicate MBP;
144 if (TII->AnalyzeBranchPredicate(MBB, MBP, true))
147 // Is the predicate comparing an integer to zero?
148 if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
149 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
150 MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
153 // If we cannot erase the test instruction itself, then making the null check
154 // implicit does not buy us much.
155 if (!MBP.SingleUseCondition)
158 MachineBasicBlock *NotNullSucc, *NullSucc;
160 if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
161 NotNullSucc = MBP.TrueDest;
162 NullSucc = MBP.FalseDest;
164 NotNullSucc = MBP.FalseDest;
165 NullSucc = MBP.TrueDest;
168 // We handle the simplest case for now. We can potentially do better by using
169 // the machine dominator tree.
170 if (NotNullSucc->pred_size() != 1)
173 // Starting with a code fragment like:
179 // callq throw_NullPointerException
185 // Def = Load (%RAX + <offset>)
189 // we want to end up with
191 // Def = TrappingLoad (%RAX + <offset>), LblNull
192 // jmp LblNotNull ;; explicit or fallthrough
200 // callq throw_NullPointerException
203 unsigned PointerReg = MBP.LHS.getReg();
205 // As we scan NotNullSucc for a suitable load instruction, we keep track of
206 // the registers defined and used by the instructions we scan past. This bit
207 // of information lets us decide if it is legal to hoist the load instruction
208 // we find (if we do find such an instruction) to before NotNullSucc.
209 DenseSet<unsigned> RegDefs, RegUses;
211 // Returns true if it is safe to reorder MI to before NotNullSucc.
212 auto IsSafeToHoist = [&](MachineInstr *MI) {
213 // Right now we don't want to worry about LLVM's memory model. This can be
214 // made more precise later.
215 for (auto *MMO : MI->memoperands())
216 if (!MMO->isUnordered())
219 for (auto &MO : MI->operands()) {
220 if (MO.isReg() && MO.getReg()) {
221 for (unsigned Reg : RegDefs)
222 if (TRI->regsOverlap(Reg, MO.getReg()))
223 return false; // We found a write-after-write or read-after-write
226 for (unsigned Reg : RegUses)
227 if (TRI->regsOverlap(Reg, MO.getReg()))
228 return false; // We found a write-after-read
235 for (auto MII = NotNullSucc->begin(), MIE = NotNullSucc->end(); MII != MIE;
237 MachineInstr *MI = &*MII;
238 unsigned BaseReg, Offset;
239 if (TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI))
240 if (MI->mayLoad() && !MI->isPredicable() && BaseReg == PointerReg &&
241 Offset < PageSize && MI->getDesc().getNumDefs() <= 1 &&
243 NullCheckList.emplace_back(MI, MBP.ConditionDef, &MBB, NotNullSucc,
248 // MI did not match our criteria for conversion to a trapping load. Check
249 // if we can continue looking.
251 if (MI->mayStore() || MI->hasUnmodeledSideEffects())
254 for (auto *MMO : MI->memoperands())
255 // Right now we don't want to worry about LLVM's memory model.
256 if (!MMO->isUnordered())
259 // It _may_ be okay to reorder a later load instruction across MI. Make a
260 // note of its operands so that we can make the legality check if we find a
261 // suitable load instruction:
263 for (auto &MO : MI->operands()) {
264 if (!MO.isReg() || !MO.getReg())
268 RegDefs.insert(MO.getReg());
270 RegUses.insert(MO.getReg());
277 /// Wrap a machine load instruction, LoadMI, into a FAULTING_LOAD_OP machine
278 /// instruction. The FAULTING_LOAD_OP instruction does the same load as LoadMI
279 /// (defining the same register), and branches to HandlerLabel if the load
280 /// faults. The FAULTING_LOAD_OP instruction is inserted at the end of MBB.
281 MachineInstr *ImplicitNullChecks::insertFaultingLoad(MachineInstr *LoadMI,
282 MachineBasicBlock *MBB,
283 MCSymbol *HandlerLabel) {
284 const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for
288 unsigned NumDefs = LoadMI->getDesc().getNumDefs();
289 assert(NumDefs <= 1 && "other cases unhandled!");
291 unsigned DefReg = NoRegister;
293 DefReg = LoadMI->defs().begin()->getReg();
294 assert(std::distance(LoadMI->defs().begin(), LoadMI->defs().end()) == 1 &&
295 "expected exactly one def!");
298 auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_LOAD_OP), DefReg)
299 .addSym(HandlerLabel)
300 .addImm(LoadMI->getOpcode());
302 for (auto &MO : LoadMI->uses())
305 MIB.setMemRefs(LoadMI->memoperands_begin(), LoadMI->memoperands_end());
310 /// Rewrite the null checks in NullCheckList into implicit null checks.
311 void ImplicitNullChecks::rewriteNullChecks(
312 ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
315 for (auto &NC : NullCheckList) {
316 MCSymbol *HandlerLabel = MMI->getContext().createTempSymbol();
318 // Remove the conditional branch dependent on the null check.
319 unsigned BranchesRemoved = TII->RemoveBranch(*NC.CheckBlock);
320 (void)BranchesRemoved;
321 assert(BranchesRemoved > 0 && "expected at least one branch!");
323 // Insert a faulting load where the conditional branch was originally. We
324 // check earlier ensures that this bit of code motion is legal. We do not
325 // touch the successors list for any basic block since we haven't changed
326 // control flow, we've just made it implicit.
327 insertFaultingLoad(NC.MemOperation, NC.CheckBlock, HandlerLabel);
328 NC.MemOperation->eraseFromParent();
329 NC.CheckOperation->eraseFromParent();
331 // Insert an *unconditional* branch to not-null successor.
332 TII->InsertBranch(*NC.CheckBlock, NC.NotNullSucc, nullptr, /*Cond=*/None,
335 // Emit the HandlerLabel as an EH_LABEL.
336 BuildMI(*NC.NullSucc, NC.NullSucc->begin(), DL,
337 TII->get(TargetOpcode::EH_LABEL)).addSym(HandlerLabel);
339 NumImplicitNullChecks++;
343 char ImplicitNullChecks::ID = 0;
344 char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID;
345 INITIALIZE_PASS_BEGIN(ImplicitNullChecks, "implicit-null-checks",
346 "Implicit null checks", false, false)
347 INITIALIZE_PASS_END(ImplicitNullChecks, "implicit-null-checks",
348 "Implicit null checks", false, false)