Line data Source code
1 : //===- ImplicitNullChecks.cpp - Fold null checks into memory accesses -----===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This pass turns explicit null checks of the form
11 : //
12 : // test %r10, %r10
13 : // je throw_npe
14 : // movl (%r10), %esi
15 : // ...
16 : //
17 : // to
18 : //
19 : // faulting_load_op("movl (%r10), %esi", throw_npe)
20 : // ...
21 : //
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
24 : // a page fault.
25 : // Store and LoadStore are also supported.
26 : //
27 : //===----------------------------------------------------------------------===//
28 :
29 : #include "llvm/ADT/ArrayRef.h"
30 : #include "llvm/ADT/None.h"
31 : #include "llvm/ADT/Optional.h"
32 : #include "llvm/ADT/STLExtras.h"
33 : #include "llvm/ADT/SmallVector.h"
34 : #include "llvm/ADT/Statistic.h"
35 : #include "llvm/Analysis/AliasAnalysis.h"
36 : #include "llvm/Analysis/MemoryLocation.h"
37 : #include "llvm/CodeGen/FaultMaps.h"
38 : #include "llvm/CodeGen/MachineBasicBlock.h"
39 : #include "llvm/CodeGen/MachineFunction.h"
40 : #include "llvm/CodeGen/MachineFunctionPass.h"
41 : #include "llvm/CodeGen/MachineInstr.h"
42 : #include "llvm/CodeGen/MachineInstrBuilder.h"
43 : #include "llvm/CodeGen/MachineMemOperand.h"
44 : #include "llvm/CodeGen/MachineOperand.h"
45 : #include "llvm/CodeGen/MachineRegisterInfo.h"
46 : #include "llvm/CodeGen/PseudoSourceValue.h"
47 : #include "llvm/CodeGen/TargetInstrInfo.h"
48 : #include "llvm/CodeGen/TargetOpcodes.h"
49 : #include "llvm/CodeGen/TargetRegisterInfo.h"
50 : #include "llvm/CodeGen/TargetSubtargetInfo.h"
51 : #include "llvm/IR/BasicBlock.h"
52 : #include "llvm/IR/DebugLoc.h"
53 : #include "llvm/IR/LLVMContext.h"
54 : #include "llvm/MC/MCInstrDesc.h"
55 : #include "llvm/MC/MCRegisterInfo.h"
56 : #include "llvm/Pass.h"
57 : #include "llvm/Support/CommandLine.h"
58 : #include <cassert>
59 : #include <cstdint>
60 : #include <iterator>
61 :
62 : using namespace llvm;
63 :
64 : static cl::opt<int> PageSize("imp-null-check-page-size",
65 : cl::desc("The page size of the target in bytes"),
66 : cl::init(4096), cl::Hidden);
67 :
68 : static cl::opt<unsigned> MaxInstsToConsider(
69 : "imp-null-max-insts-to-consider",
70 : cl::desc("The max number of instructions to consider hoisting loads over "
71 : "(the algorithm is quadratic over this number)"),
72 : cl::Hidden, cl::init(8));
73 :
74 : #define DEBUG_TYPE "implicit-null-checks"
75 :
76 : STATISTIC(NumImplicitNullChecks,
77 : "Number of explicit null checks made implicit");
78 :
79 : namespace {
80 :
81 : class ImplicitNullChecks : public MachineFunctionPass {
82 : /// Return true if \c computeDependence can process \p MI.
83 : static bool canHandle(const MachineInstr *MI);
84 :
85 : /// Helper function for \c computeDependence. Return true if \p A
86 : /// and \p B do not have any dependences between them, and can be
87 : /// re-ordered without changing program semantics.
88 : bool canReorder(const MachineInstr *A, const MachineInstr *B);
89 :
90 : /// A data type for representing the result computed by \c
91 : /// computeDependence. States whether it is okay to reorder the
92 : /// instruction passed to \c computeDependence with at most one
93 : /// dependency.
94 : struct DependenceResult {
95 : /// Can we actually re-order \p MI with \p Insts (see \c
96 : /// computeDependence).
97 : bool CanReorder;
98 :
99 : /// If non-None, then an instruction in \p Insts that also must be
100 : /// hoisted.
101 : Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence;
102 :
103 : /*implicit*/ DependenceResult(
104 : bool CanReorder,
105 : Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence)
106 53 : : CanReorder(CanReorder), PotentialDependence(PotentialDependence) {
107 : assert((!PotentialDependence || CanReorder) &&
108 : "!CanReorder && PotentialDependence.hasValue() not allowed!");
109 : }
110 : };
111 :
112 : /// Compute a result for the following question: can \p MI be
113 : /// re-ordered from after \p Insts to before it.
114 : ///
115 : /// \c canHandle should return true for all instructions in \p
116 : /// Insts.
117 : DependenceResult computeDependence(const MachineInstr *MI,
118 : ArrayRef<MachineInstr *> Block);
119 :
120 : /// Represents one null check that can be made implicit.
121 : class NullCheck {
122 : // The memory operation the null check can be folded into.
123 : MachineInstr *MemOperation;
124 :
125 : // The instruction actually doing the null check (Ptr != 0).
126 : MachineInstr *CheckOperation;
127 :
128 : // The block the check resides in.
129 : MachineBasicBlock *CheckBlock;
130 :
131 : // The block branched to if the pointer is non-null.
132 : MachineBasicBlock *NotNullSucc;
133 :
134 : // The block branched to if the pointer is null.
135 : MachineBasicBlock *NullSucc;
136 :
137 : // If this is non-null, then MemOperation has a dependency on this
138 : // instruction; and it needs to be hoisted to execute before MemOperation.
139 : MachineInstr *OnlyDependency;
140 :
141 : public:
142 : explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation,
143 : MachineBasicBlock *checkBlock,
144 : MachineBasicBlock *notNullSucc,
145 : MachineBasicBlock *nullSucc,
146 : MachineInstr *onlyDependency)
147 37 : : MemOperation(memOperation), CheckOperation(checkOperation),
148 : CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc),
149 37 : OnlyDependency(onlyDependency) {}
150 :
151 0 : MachineInstr *getMemOperation() const { return MemOperation; }
152 :
153 0 : MachineInstr *getCheckOperation() const { return CheckOperation; }
154 :
155 0 : MachineBasicBlock *getCheckBlock() const { return CheckBlock; }
156 :
157 0 : MachineBasicBlock *getNotNullSucc() const { return NotNullSucc; }
158 :
159 0 : MachineBasicBlock *getNullSucc() const { return NullSucc; }
160 :
161 0 : MachineInstr *getOnlyDependency() const { return OnlyDependency; }
162 : };
163 :
164 : const TargetInstrInfo *TII = nullptr;
165 : const TargetRegisterInfo *TRI = nullptr;
166 : AliasAnalysis *AA = nullptr;
167 : MachineFrameInfo *MFI = nullptr;
168 :
169 : bool analyzeBlockForNullChecks(MachineBasicBlock &MBB,
170 : SmallVectorImpl<NullCheck> &NullCheckList);
171 : MachineInstr *insertFaultingInstr(MachineInstr *MI, MachineBasicBlock *MBB,
172 : MachineBasicBlock *HandlerMBB);
173 : void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList);
174 :
175 : enum AliasResult {
176 : AR_NoAlias,
177 : AR_MayAlias,
178 : AR_WillAliasEverything
179 : };
180 :
181 : /// Returns AR_NoAlias if \p MI memory operation does not alias with
182 : /// \p PrevMI, AR_MayAlias if they may alias and AR_WillAliasEverything if
183 : /// they may alias and any further memory operation may alias with \p PrevMI.
184 : AliasResult areMemoryOpsAliased(MachineInstr &MI, MachineInstr *PrevMI);
185 :
186 : enum SuitabilityResult {
187 : SR_Suitable,
188 : SR_Unsuitable,
189 : SR_Impossible
190 : };
191 :
192 : /// Return SR_Suitable if \p MI a memory operation that can be used to
193 : /// implicitly null check the value in \p PointerReg, SR_Unsuitable if
194 : /// \p MI cannot be used to null check and SR_Impossible if there is
195 : /// no sense to continue lookup due to any other instruction will not be able
196 : /// to be used. \p PrevInsts is the set of instruction seen since
197 : /// the explicit null check on \p PointerReg.
198 : SuitabilityResult isSuitableMemoryOp(MachineInstr &MI, unsigned PointerReg,
199 : ArrayRef<MachineInstr *> PrevInsts);
200 :
201 : /// Return true if \p FaultingMI can be hoisted from after the
202 : /// instructions in \p InstsSeenSoFar to before them. Set \p Dependence to a
203 : /// non-null value if we also need to (and legally can) hoist a depedency.
204 : bool canHoistInst(MachineInstr *FaultingMI, unsigned PointerReg,
205 : ArrayRef<MachineInstr *> InstsSeenSoFar,
206 : MachineBasicBlock *NullSucc, MachineInstr *&Dependence);
207 :
208 : public:
209 : static char ID;
210 :
211 7 : ImplicitNullChecks() : MachineFunctionPass(ID) {
212 7 : initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry());
213 7 : }
214 :
215 : bool runOnMachineFunction(MachineFunction &MF) override;
216 :
217 7 : void getAnalysisUsage(AnalysisUsage &AU) const override {
218 : AU.addRequired<AAResultsWrapperPass>();
219 7 : MachineFunctionPass::getAnalysisUsage(AU);
220 7 : }
221 :
222 7 : MachineFunctionProperties getRequiredProperties() const override {
223 7 : return MachineFunctionProperties().set(
224 7 : MachineFunctionProperties::Property::NoVRegs);
225 : }
226 : };
227 :
228 : } // end anonymous namespace
229 :
230 112 : bool ImplicitNullChecks::canHandle(const MachineInstr *MI) {
231 112 : if (MI->isCall() || MI->hasUnmodeledSideEffects())
232 8 : return false;
233 : auto IsRegMask = [](const MachineOperand &MO) { return MO.isRegMask(); };
234 : (void)IsRegMask;
235 :
236 : assert(!llvm::any_of(MI->operands(), IsRegMask) &&
237 : "Calls were filtered out above!");
238 :
239 : auto IsUnordered = [](MachineMemOperand *MMO) { return MMO->isUnordered(); };
240 104 : return llvm::all_of(MI->memoperands(), IsUnordered);
241 : }
242 :
243 : ImplicitNullChecks::DependenceResult
244 53 : ImplicitNullChecks::computeDependence(const MachineInstr *MI,
245 : ArrayRef<MachineInstr *> Block) {
246 : assert(llvm::all_of(Block, canHandle) && "Check this first!");
247 : assert(!is_contained(Block, MI) && "Block must be exclusive of MI!");
248 :
249 : Optional<ArrayRef<MachineInstr *>::iterator> Dep;
250 :
251 83 : for (auto I = Block.begin(), E = Block.end(); I != E; ++I) {
252 33 : if (canReorder(*I, MI))
253 : continue;
254 :
255 19 : if (Dep == None) {
256 : // Found one possible dependency, keep track of it.
257 : Dep = I;
258 : } else {
259 : // We found two dependencies, so bail out.
260 : return {false, None};
261 : }
262 : }
263 :
264 : return {true, Dep};
265 : }
266 :
267 0 : bool ImplicitNullChecks::canReorder(const MachineInstr *A,
268 : const MachineInstr *B) {
269 : assert(canHandle(A) && canHandle(B) && "Precondition!");
270 :
271 : // canHandle makes sure that we _can_ correctly analyze the dependencies
272 : // between A and B here -- for instance, we should not be dealing with heap
273 : // load-store dependencies here.
274 :
275 0 : for (auto MOA : A->operands()) {
276 0 : if (!(MOA.isReg() && MOA.getReg()))
277 0 : continue;
278 :
279 : unsigned RegA = MOA.getReg();
280 0 : for (auto MOB : B->operands()) {
281 0 : if (!(MOB.isReg() && MOB.getReg()))
282 0 : continue;
283 :
284 : unsigned RegB = MOB.getReg();
285 :
286 0 : if (TRI->regsOverlap(RegA, RegB) && (MOA.isDef() || MOB.isDef()))
287 0 : return false;
288 : }
289 : }
290 :
291 0 : return true;
292 : }
293 :
294 55 : bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
295 55 : TII = MF.getSubtarget().getInstrInfo();
296 55 : TRI = MF.getRegInfo().getTargetRegisterInfo();
297 55 : MFI = &MF.getFrameInfo();
298 55 : AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
299 :
300 55 : SmallVector<NullCheck, 16> NullCheckList;
301 :
302 251 : for (auto &MBB : MF)
303 196 : analyzeBlockForNullChecks(MBB, NullCheckList);
304 :
305 55 : if (!NullCheckList.empty())
306 36 : rewriteNullChecks(NullCheckList);
307 :
308 55 : return !NullCheckList.empty();
309 : }
310 :
311 : // Return true if any register aliasing \p Reg is live-in into \p MBB.
312 21 : static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI,
313 : MachineBasicBlock *MBB, unsigned Reg) {
314 193 : for (MCRegAliasIterator AR(Reg, TRI, /*IncludeSelf*/ true); AR.isValid();
315 172 : ++AR)
316 348 : if (MBB->isLiveIn(*AR))
317 2 : return true;
318 19 : return false;
319 : }
320 :
321 : ImplicitNullChecks::AliasResult
322 0 : ImplicitNullChecks::areMemoryOpsAliased(MachineInstr &MI,
323 : MachineInstr *PrevMI) {
324 : // If it is not memory access, skip the check.
325 0 : if (!(PrevMI->mayStore() || PrevMI->mayLoad()))
326 0 : return AR_NoAlias;
327 : // Load-Load may alias
328 0 : if (!(MI.mayStore() || PrevMI->mayStore()))
329 0 : return AR_NoAlias;
330 : // We lost info, conservatively alias. If it was store then no sense to
331 : // continue because we won't be able to check against it further.
332 0 : if (MI.memoperands_empty())
333 0 : return MI.mayStore() ? AR_WillAliasEverything : AR_MayAlias;
334 0 : if (PrevMI->memoperands_empty())
335 0 : return PrevMI->mayStore() ? AR_WillAliasEverything : AR_MayAlias;
336 :
337 0 : for (MachineMemOperand *MMO1 : MI.memoperands()) {
338 : // MMO1 should have a value due it comes from operation we'd like to use
339 : // as implicit null check.
340 : assert(MMO1->getValue() && "MMO1 should have a Value!");
341 0 : for (MachineMemOperand *MMO2 : PrevMI->memoperands()) {
342 0 : if (const PseudoSourceValue *PSV = MMO2->getPseudoValue()) {
343 0 : if (PSV->mayAlias(MFI))
344 0 : return AR_MayAlias;
345 0 : continue;
346 : }
347 : llvm::AliasResult AAResult =
348 0 : AA->alias(MemoryLocation(MMO1->getValue(), LocationSize::unknown(),
349 : MMO1->getAAInfo()),
350 0 : MemoryLocation(MMO2->getValue(), LocationSize::unknown(),
351 : MMO2->getAAInfo()));
352 0 : if (AAResult != NoAlias)
353 0 : return AR_MayAlias;
354 : }
355 : }
356 : return AR_NoAlias;
357 : }
358 :
359 : ImplicitNullChecks::SuitabilityResult
360 103 : ImplicitNullChecks::isSuitableMemoryOp(MachineInstr &MI, unsigned PointerReg,
361 : ArrayRef<MachineInstr *> PrevInsts) {
362 : int64_t Offset;
363 : unsigned BaseReg;
364 :
365 103 : if (!TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI) ||
366 66 : BaseReg != PointerReg)
367 : return SR_Unsuitable;
368 :
369 : // We want the mem access to be issued at a sane offset from PointerReg,
370 : // so that if PointerReg is null then the access reliably page faults.
371 100 : if (!((MI.mayLoad() || MI.mayStore()) && !MI.isPredicable() &&
372 50 : -PageSize < Offset && Offset < PageSize))
373 0 : return SR_Unsuitable;
374 :
375 : // Finally, check whether the current memory access aliases with previous one.
376 81 : for (auto *PrevMI : PrevInsts) {
377 35 : AliasResult AR = areMemoryOpsAliased(MI, PrevMI);
378 35 : if (AR == AR_WillAliasEverything)
379 : return SR_Impossible;
380 33 : if (AR == AR_MayAlias)
381 : return SR_Unsuitable;
382 : }
383 : return SR_Suitable;
384 : }
385 :
386 0 : bool ImplicitNullChecks::canHoistInst(MachineInstr *FaultingMI,
387 : unsigned PointerReg,
388 : ArrayRef<MachineInstr *> InstsSeenSoFar,
389 : MachineBasicBlock *NullSucc,
390 : MachineInstr *&Dependence) {
391 0 : auto DepResult = computeDependence(FaultingMI, InstsSeenSoFar);
392 0 : if (!DepResult.CanReorder)
393 0 : return false;
394 :
395 0 : if (!DepResult.PotentialDependence) {
396 0 : Dependence = nullptr;
397 0 : return true;
398 : }
399 :
400 0 : auto DependenceItr = *DepResult.PotentialDependence;
401 0 : auto *DependenceMI = *DependenceItr;
402 :
403 : // We don't want to reason about speculating loads. Note -- at this point
404 : // we should have already filtered out all of the other non-speculatable
405 : // things, like calls and stores.
406 : // We also do not want to hoist stores because it might change the memory
407 : // while the FaultingMI may result in faulting.
408 : assert(canHandle(DependenceMI) && "Should never have reached here!");
409 0 : if (DependenceMI->mayLoadOrStore())
410 0 : return false;
411 :
412 0 : for (auto &DependenceMO : DependenceMI->operands()) {
413 0 : if (!(DependenceMO.isReg() && DependenceMO.getReg()))
414 0 : continue;
415 :
416 : // Make sure that we won't clobber any live ins to the sibling block by
417 : // hoisting Dependency. For instance, we can't hoist INST to before the
418 : // null check (even if it safe, and does not violate any dependencies in
419 : // the non_null_block) if %rdx is live in to _null_block.
420 : //
421 : // test %rcx, %rcx
422 : // je _null_block
423 : // _non_null_block:
424 : // %rdx = INST
425 : // ...
426 : //
427 : // This restriction does not apply to the faulting load inst because in
428 : // case the pointer loaded from is in the null page, the load will not
429 : // semantically execute, and affect machine state. That is, if the load
430 : // was loading into %rax and it faults, the value of %rax should stay the
431 : // same as it would have been had the load not have executed and we'd have
432 : // branched to NullSucc directly.
433 0 : if (AnyAliasLiveIn(TRI, NullSucc, DependenceMO.getReg()))
434 0 : return false;
435 :
436 : // The Dependency can't be re-defining the base register -- then we won't
437 : // get the memory operation on the address we want. This is already
438 : // checked in \c IsSuitableMemoryOp.
439 : assert(!(DependenceMO.isDef() &&
440 : TRI->regsOverlap(DependenceMO.getReg(), PointerReg)) &&
441 : "Should have been checked before!");
442 : }
443 :
444 : auto DepDepResult =
445 0 : computeDependence(DependenceMI, {InstsSeenSoFar.begin(), DependenceItr});
446 :
447 0 : if (!DepDepResult.CanReorder || DepDepResult.PotentialDependence)
448 0 : return false;
449 :
450 0 : Dependence = DependenceMI;
451 0 : return true;
452 : }
453 :
454 : /// Analyze MBB to check if its terminating branch can be turned into an
455 : /// implicit null check. If yes, append a description of the said null check to
456 : /// NullCheckList and return true, else return false.
457 196 : bool ImplicitNullChecks::analyzeBlockForNullChecks(
458 : MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
459 : using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
460 :
461 : MDNode *BranchMD = nullptr;
462 196 : if (auto *BB = MBB.getBasicBlock())
463 195 : BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit);
464 :
465 57 : if (!BranchMD)
466 139 : return false;
467 :
468 : MachineBranchPredicate MBP;
469 :
470 57 : if (TII->analyzeBranchPredicate(MBB, MBP, true))
471 : return false;
472 :
473 : // Is the predicate comparing an integer to zero?
474 57 : if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
475 57 : (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
476 : MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
477 : return false;
478 :
479 : // If we cannot erase the test instruction itself, then making the null check
480 : // implicit does not buy us much.
481 57 : if (!MBP.SingleUseCondition)
482 : return false;
483 :
484 : MachineBasicBlock *NotNullSucc, *NullSucc;
485 :
486 57 : if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
487 22 : NotNullSucc = MBP.TrueDest;
488 22 : NullSucc = MBP.FalseDest;
489 : } else {
490 35 : NotNullSucc = MBP.FalseDest;
491 35 : NullSucc = MBP.TrueDest;
492 : }
493 :
494 : // We handle the simplest case for now. We can potentially do better by using
495 : // the machine dominator tree.
496 114 : if (NotNullSucc->pred_size() != 1)
497 : return false;
498 :
499 : // To prevent the invalid transformation of the following code:
500 : //
501 : // mov %rax, %rcx
502 : // test %rax, %rax
503 : // %rax = ...
504 : // je throw_npe
505 : // mov(%rcx), %r9
506 : // mov(%rax), %r10
507 : //
508 : // into:
509 : //
510 : // mov %rax, %rcx
511 : // %rax = ....
512 : // faulting_load_op("movl (%rax), %r10", throw_npe)
513 : // mov(%rcx), %r9
514 : //
515 : // we must ensure that there are no instructions between the 'test' and
516 : // conditional jump that modify %rax.
517 57 : const unsigned PointerReg = MBP.LHS.getReg();
518 :
519 : assert(MBP.ConditionDef->getParent() == &MBB && "Should be in basic block");
520 :
521 114 : for (auto I = MBB.rbegin(); MBP.ConditionDef != &*I; ++I)
522 58 : if (I->modifiesRegister(PointerReg, TRI))
523 : return false;
524 :
525 : // Starting with a code fragment like:
526 : //
527 : // test %rax, %rax
528 : // jne LblNotNull
529 : //
530 : // LblNull:
531 : // callq throw_NullPointerException
532 : //
533 : // LblNotNull:
534 : // Inst0
535 : // Inst1
536 : // ...
537 : // Def = Load (%rax + <offset>)
538 : // ...
539 : //
540 : //
541 : // we want to end up with
542 : //
543 : // Def = FaultingLoad (%rax + <offset>), LblNull
544 : // jmp LblNotNull ;; explicit or fallthrough
545 : //
546 : // LblNotNull:
547 : // Inst0
548 : // Inst1
549 : // ...
550 : //
551 : // LblNull:
552 : // callq throw_NullPointerException
553 : //
554 : //
555 : // To see why this is legal, consider the two possibilities:
556 : //
557 : // 1. %rax is null: since we constrain <offset> to be less than PageSize, the
558 : // load instruction dereferences the null page, causing a segmentation
559 : // fault.
560 : //
561 : // 2. %rax is not null: in this case we know that the load cannot fault, as
562 : // otherwise the load would've faulted in the original program too and the
563 : // original program would've been undefined.
564 : //
565 : // This reasoning cannot be extended to justify hoisting through arbitrary
566 : // control flow. For instance, in the example below (in pseudo-C)
567 : //
568 : // if (ptr == null) { throw_npe(); unreachable; }
569 : // if (some_cond) { return 42; }
570 : // v = ptr->field; // LD
571 : // ...
572 : //
573 : // we cannot (without code duplication) use the load marked "LD" to null check
574 : // ptr -- clause (2) above does not apply in this case. In the above program
575 : // the safety of ptr->field can be dependent on some_cond; and, for instance,
576 : // ptr could be some non-null invalid reference that never gets loaded from
577 : // because some_cond is always true.
578 :
579 : SmallVector<MachineInstr *, 8> InstsSeenSoFar;
580 :
581 115 : for (auto &MI : *NotNullSucc) {
582 112 : if (!canHandle(&MI) || InstsSeenSoFar.size() >= MaxInstsToConsider)
583 53 : return false;
584 :
585 : MachineInstr *Dependence;
586 103 : SuitabilityResult SR = isSuitableMemoryOp(MI, PointerReg, InstsSeenSoFar);
587 103 : if (SR == SR_Impossible)
588 : return false;
589 147 : if (SR == SR_Suitable &&
590 156 : canHoistInst(&MI, PointerReg, InstsSeenSoFar, NullSucc, Dependence)) {
591 37 : NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc,
592 : NullSucc, Dependence);
593 37 : return true;
594 : }
595 :
596 : // If MI re-defines the PointerReg then we cannot move further.
597 64 : if (llvm::any_of(MI.operands(), [&](MachineOperand &MO) {
598 : return MO.isReg() && MO.getReg() && MO.isDef() &&
599 : TRI->regsOverlap(MO.getReg(), PointerReg);
600 : }))
601 : return false;
602 59 : InstsSeenSoFar.push_back(&MI);
603 : }
604 :
605 : return false;
606 : }
607 :
608 : /// Wrap a machine instruction, MI, into a FAULTING machine instruction.
609 : /// The FAULTING instruction does the same load/store as MI
610 : /// (defining the same register), and branches to HandlerMBB if the mem access
611 : /// faults. The FAULTING instruction is inserted at the end of MBB.
612 0 : MachineInstr *ImplicitNullChecks::insertFaultingInstr(
613 : MachineInstr *MI, MachineBasicBlock *MBB, MachineBasicBlock *HandlerMBB) {
614 : const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for
615 : // all targets.
616 :
617 0 : DebugLoc DL;
618 0 : unsigned NumDefs = MI->getDesc().getNumDefs();
619 : assert(NumDefs <= 1 && "other cases unhandled!");
620 :
621 : unsigned DefReg = NoRegister;
622 0 : if (NumDefs != 0) {
623 0 : DefReg = MI->getOperand(0).getReg();
624 : assert(NumDefs == 1 && "expected exactly one def!");
625 : }
626 :
627 : FaultMaps::FaultKind FK;
628 0 : if (MI->mayLoad())
629 : FK =
630 0 : MI->mayStore() ? FaultMaps::FaultingLoadStore : FaultMaps::FaultingLoad;
631 : else
632 : FK = FaultMaps::FaultingStore;
633 :
634 0 : auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_OP), DefReg)
635 0 : .addImm(FK)
636 : .addMBB(HandlerMBB)
637 0 : .addImm(MI->getOpcode());
638 :
639 0 : for (auto &MO : MI->uses()) {
640 0 : if (MO.isReg()) {
641 0 : MachineOperand NewMO = MO;
642 0 : if (MO.isUse()) {
643 : NewMO.setIsKill(false);
644 : } else {
645 : assert(MO.isDef() && "Expected def or use");
646 : NewMO.setIsDead(false);
647 : }
648 : MIB.add(NewMO);
649 : } else {
650 : MIB.add(MO);
651 : }
652 : }
653 :
654 0 : MIB.setMemRefs(MI->memoperands());
655 :
656 0 : return MIB;
657 : }
658 :
659 : /// Rewrite the null checks in NullCheckList into implicit null checks.
660 36 : void ImplicitNullChecks::rewriteNullChecks(
661 : ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
662 36 : DebugLoc DL;
663 :
664 73 : for (auto &NC : NullCheckList) {
665 : // Remove the conditional branch dependent on the null check.
666 37 : unsigned BranchesRemoved = TII->removeBranch(*NC.getCheckBlock());
667 : (void)BranchesRemoved;
668 : assert(BranchesRemoved > 0 && "expected at least one branch!");
669 :
670 37 : if (auto *DepMI = NC.getOnlyDependency()) {
671 5 : DepMI->removeFromParent();
672 5 : NC.getCheckBlock()->insert(NC.getCheckBlock()->end(), DepMI);
673 : }
674 :
675 : // Insert a faulting instruction where the conditional branch was
676 : // originally. We check earlier ensures that this bit of code motion
677 : // is legal. We do not touch the successors list for any basic block
678 : // since we haven't changed control flow, we've just made it implicit.
679 37 : MachineInstr *FaultingInstr = insertFaultingInstr(
680 : NC.getMemOperation(), NC.getCheckBlock(), NC.getNullSucc());
681 : // Now the values defined by MemOperation, if any, are live-in of
682 : // the block of MemOperation.
683 : // The original operation may define implicit-defs alongside
684 : // the value.
685 37 : MachineBasicBlock *MBB = NC.getMemOperation()->getParent();
686 403 : for (const MachineOperand &MO : FaultingInstr->operands()) {
687 366 : if (!MO.isReg() || !MO.isDef())
688 : continue;
689 52 : unsigned Reg = MO.getReg();
690 52 : if (!Reg || MBB->isLiveIn(Reg))
691 15 : continue;
692 : MBB->addLiveIn(Reg);
693 : }
694 :
695 37 : if (auto *DepMI = NC.getOnlyDependency()) {
696 21 : for (auto &MO : DepMI->operands()) {
697 16 : if (!MO.isReg() || !MO.getReg() || !MO.isDef())
698 : continue;
699 8 : if (!NC.getNotNullSucc()->isLiveIn(MO.getReg()))
700 3 : NC.getNotNullSucc()->addLiveIn(MO.getReg());
701 : }
702 : }
703 :
704 37 : NC.getMemOperation()->eraseFromParent();
705 37 : NC.getCheckOperation()->eraseFromParent();
706 :
707 : // Insert an *unconditional* branch to not-null successor.
708 37 : TII->insertBranch(*NC.getCheckBlock(), NC.getNotNullSucc(), nullptr,
709 37 : /*Cond=*/None, DL);
710 :
711 : NumImplicitNullChecks++;
712 : }
713 36 : }
714 :
715 : char ImplicitNullChecks::ID = 0;
716 :
717 : char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID;
718 :
719 31780 : INITIALIZE_PASS_BEGIN(ImplicitNullChecks, DEBUG_TYPE,
720 : "Implicit null checks", false, false)
721 31780 : INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
722 85154 : INITIALIZE_PASS_END(ImplicitNullChecks, DEBUG_TYPE,
723 : "Implicit null checks", false, false)
|
