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/IR/LLVMContext.h"
42 #include "llvm/Support/CommandLine.h"
43 #include "llvm/Support/Debug.h"
44 #include "llvm/Target/TargetSubtargetInfo.h"
45 #include "llvm/Target/TargetInstrInfo.h"
49 static cl::opt<unsigned> PageSize("imp-null-check-page-size",
50 cl::desc("The page size of the target in "
54 #define DEBUG_TYPE "implicit-null-checks"
56 STATISTIC(NumImplicitNullChecks,
57 "Number of explicit null checks made implicit");
61 class ImplicitNullChecks : public MachineFunctionPass {
62 /// Represents one null check that can be made implicit.
64 // The memory operation the null check can be folded into.
65 MachineInstr *MemOperation;
67 // The instruction actually doing the null check (Ptr != 0).
68 MachineInstr *CheckOperation;
70 // The block the check resides in.
71 MachineBasicBlock *CheckBlock;
73 // The block branched to if the pointer is non-null.
74 MachineBasicBlock *NotNullSucc;
76 // The block branched to if the pointer is null.
77 MachineBasicBlock *NullSucc;
80 : MemOperation(), CheckOperation(), CheckBlock(), NotNullSucc(),
83 explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation,
84 MachineBasicBlock *checkBlock,
85 MachineBasicBlock *notNullSucc,
86 MachineBasicBlock *nullSucc)
87 : MemOperation(memOperation), CheckOperation(checkOperation),
88 CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc) {
92 const TargetInstrInfo *TII = nullptr;
93 const TargetRegisterInfo *TRI = nullptr;
94 MachineModuleInfo *MMI = nullptr;
96 bool analyzeBlockForNullChecks(MachineBasicBlock &MBB,
97 SmallVectorImpl<NullCheck> &NullCheckList);
98 MachineInstr *insertFaultingLoad(MachineInstr *LoadMI, MachineBasicBlock *MBB,
99 MCSymbol *HandlerLabel);
100 void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList);
105 ImplicitNullChecks() : MachineFunctionPass(ID) {
106 initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry());
109 bool runOnMachineFunction(MachineFunction &MF) override;
112 /// \brief Detect re-ordering hazards and dependencies.
114 /// This class keeps track of defs and uses, and can be queried if a given
115 /// machine instruction can be re-ordered from after the machine instructions
116 /// seen so far to before them.
117 class HazardDetector {
118 DenseSet<unsigned> RegDefs;
119 DenseSet<unsigned> RegUses;
120 const TargetRegisterInfo &TRI;
124 explicit HazardDetector(const TargetRegisterInfo &TRI) :
125 TRI(TRI), hasSeenClobber(false) {}
127 /// \brief Make a note of \p MI for later queries to isSafeToHoist.
129 /// May clobber this HazardDetector instance. \see isClobbered.
130 void rememberInstruction(MachineInstr *MI);
132 /// \brief Return true if it is safe to hoist \p MI from after all the
133 /// instructions seen so far (via rememberInstruction) to before it.
134 bool isSafeToHoist(MachineInstr *MI);
136 /// \brief Return true if this instance of HazardDetector has been clobbered
137 /// (i.e. has no more useful information).
139 /// A HazardDetecter is clobbered when it sees a construct it cannot
140 /// understand, and it would have to return a conservative answer for all
141 /// future queries. Having a separate clobbered state lets the client code
142 /// bail early, without making queries about all of the future instructions
143 /// (which would have returned the most conservative answer anyway).
145 /// Calling rememberInstruction or isSafeToHoist on a clobbered HazardDetector
147 bool isClobbered() { return hasSeenClobber; }
152 void HazardDetector::rememberInstruction(MachineInstr *MI) {
153 assert(!isClobbered() &&
154 "Don't add instructions to a clobbered hazard detector");
156 if (MI->mayStore() || MI->hasUnmodeledSideEffects()) {
157 hasSeenClobber = true;
161 for (auto *MMO : MI->memoperands()) {
162 // Right now we don't want to worry about LLVM's memory model.
163 if (!MMO->isUnordered()) {
164 hasSeenClobber = true;
169 for (auto &MO : MI->operands()) {
170 if (!MO.isReg() || !MO.getReg())
174 RegDefs.insert(MO.getReg());
176 RegUses.insert(MO.getReg());
180 bool HazardDetector::isSafeToHoist(MachineInstr *MI) {
181 assert(!isClobbered() && "isSafeToHoist cannot do anything useful!");
183 // Right now we don't want to worry about LLVM's memory model. This can be
184 // made more precise later.
185 for (auto *MMO : MI->memoperands())
186 if (!MMO->isUnordered())
189 for (auto &MO : MI->operands()) {
190 if (MO.isReg() && MO.getReg()) {
191 for (unsigned Reg : RegDefs)
192 if (TRI.regsOverlap(Reg, MO.getReg()))
193 return false; // We found a write-after-write or read-after-write
196 for (unsigned Reg : RegUses)
197 if (TRI.regsOverlap(Reg, MO.getReg()))
198 return false; // We found a write-after-read
205 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
206 TII = MF.getSubtarget().getInstrInfo();
207 TRI = MF.getRegInfo().getTargetRegisterInfo();
210 SmallVector<NullCheck, 16> NullCheckList;
213 analyzeBlockForNullChecks(MBB, NullCheckList);
215 if (!NullCheckList.empty())
216 rewriteNullChecks(NullCheckList);
218 return !NullCheckList.empty();
221 /// Analyze MBB to check if its terminating branch can be turned into an
222 /// implicit null check. If yes, append a description of the said null check to
223 /// NullCheckList and return true, else return false.
224 bool ImplicitNullChecks::analyzeBlockForNullChecks(
225 MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
226 typedef TargetInstrInfo::MachineBranchPredicate MachineBranchPredicate;
228 MDNode *BranchMD = nullptr;
229 if (auto *BB = MBB.getBasicBlock())
230 BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit);
235 MachineBranchPredicate MBP;
237 if (TII->AnalyzeBranchPredicate(MBB, MBP, true))
240 // Is the predicate comparing an integer to zero?
241 if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
242 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
243 MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
246 // If we cannot erase the test instruction itself, then making the null check
247 // implicit does not buy us much.
248 if (!MBP.SingleUseCondition)
251 MachineBasicBlock *NotNullSucc, *NullSucc;
253 if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
254 NotNullSucc = MBP.TrueDest;
255 NullSucc = MBP.FalseDest;
257 NotNullSucc = MBP.FalseDest;
258 NullSucc = MBP.TrueDest;
261 // We handle the simplest case for now. We can potentially do better by using
262 // the machine dominator tree.
263 if (NotNullSucc->pred_size() != 1)
266 // Starting with a code fragment like:
272 // callq throw_NullPointerException
278 // Def = Load (%RAX + <offset>)
282 // we want to end up with
284 // Def = FaultingLoad (%RAX + <offset>), LblNull
285 // jmp LblNotNull ;; explicit or fallthrough
293 // callq throw_NullPointerException
296 // To see why this is legal, consider the two possibilities:
298 // 1. %RAX is null: since we constrain <offset> to be less than PageSize, the
299 // load instruction dereferences the null page, causing a segmentation
302 // 2. %RAX is not null: in this case we know that the load cannot fault, as
303 // otherwise the load would've faulted in the original program too and the
304 // original program would've been undefined.
306 // This reasoning cannot be extended to justify hoisting through arbitrary
307 // control flow. For instance, in the example below (in pseudo-C)
309 // if (ptr == null) { throw_npe(); unreachable; }
310 // if (some_cond) { return 42; }
311 // v = ptr->field; // LD
314 // we cannot (without code duplication) use the load marked "LD" to null check
315 // ptr -- clause (2) above does not apply in this case. In the above program
316 // the safety of ptr->field can be dependent on some_cond; and, for instance,
317 // ptr could be some non-null invalid reference that never gets loaded from
318 // because some_cond is always true.
320 unsigned PointerReg = MBP.LHS.getReg();
322 HazardDetector HD(*TRI);
324 for (auto MII = NotNullSucc->begin(), MIE = NotNullSucc->end(); MII != MIE;
326 MachineInstr *MI = &*MII;
327 unsigned BaseReg, Offset;
328 if (TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI))
329 if (MI->mayLoad() && !MI->isPredicable() && BaseReg == PointerReg &&
330 Offset < PageSize && MI->getDesc().getNumDefs() <= 1 &&
331 HD.isSafeToHoist(MI)) {
332 NullCheckList.emplace_back(MI, MBP.ConditionDef, &MBB, NotNullSucc,
337 HD.rememberInstruction(MI);
338 if (HD.isClobbered())
345 /// Wrap a machine load instruction, LoadMI, into a FAULTING_LOAD_OP machine
346 /// instruction. The FAULTING_LOAD_OP instruction does the same load as LoadMI
347 /// (defining the same register), and branches to HandlerLabel if the load
348 /// faults. The FAULTING_LOAD_OP instruction is inserted at the end of MBB.
349 MachineInstr *ImplicitNullChecks::insertFaultingLoad(MachineInstr *LoadMI,
350 MachineBasicBlock *MBB,
351 MCSymbol *HandlerLabel) {
352 const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for
356 unsigned NumDefs = LoadMI->getDesc().getNumDefs();
357 assert(NumDefs <= 1 && "other cases unhandled!");
359 unsigned DefReg = NoRegister;
361 DefReg = LoadMI->defs().begin()->getReg();
362 assert(std::distance(LoadMI->defs().begin(), LoadMI->defs().end()) == 1 &&
363 "expected exactly one def!");
366 auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_LOAD_OP), DefReg)
367 .addSym(HandlerLabel)
368 .addImm(LoadMI->getOpcode());
370 for (auto &MO : LoadMI->uses())
373 MIB.setMemRefs(LoadMI->memoperands_begin(), LoadMI->memoperands_end());
378 /// Rewrite the null checks in NullCheckList into implicit null checks.
379 void ImplicitNullChecks::rewriteNullChecks(
380 ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
383 for (auto &NC : NullCheckList) {
384 MCSymbol *HandlerLabel = MMI->getContext().createTempSymbol();
386 // Remove the conditional branch dependent on the null check.
387 unsigned BranchesRemoved = TII->RemoveBranch(*NC.CheckBlock);
388 (void)BranchesRemoved;
389 assert(BranchesRemoved > 0 && "expected at least one branch!");
391 // Insert a faulting load where the conditional branch was originally. We
392 // check earlier ensures that this bit of code motion is legal. We do not
393 // touch the successors list for any basic block since we haven't changed
394 // control flow, we've just made it implicit.
395 insertFaultingLoad(NC.MemOperation, NC.CheckBlock, HandlerLabel);
396 NC.MemOperation->eraseFromParent();
397 NC.CheckOperation->eraseFromParent();
399 // Insert an *unconditional* branch to not-null successor.
400 TII->InsertBranch(*NC.CheckBlock, NC.NotNullSucc, nullptr, /*Cond=*/None,
403 // Emit the HandlerLabel as an EH_LABEL.
404 BuildMI(*NC.NullSucc, NC.NullSucc->begin(), DL,
405 TII->get(TargetOpcode::EH_LABEL)).addSym(HandlerLabel);
407 NumImplicitNullChecks++;
411 char ImplicitNullChecks::ID = 0;
412 char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID;
413 INITIALIZE_PASS_BEGIN(ImplicitNullChecks, "implicit-null-checks",
414 "Implicit null checks", false, false)
415 INITIALIZE_PASS_END(ImplicitNullChecks, "implicit-null-checks",
416 "Implicit null checks", false, false)