blob: dff6d02b06e2ab247c43e93364951ac93da63282 [file] [log] [blame]
Eugene Zelenko900b6332017-08-29 22:32:07 +00001//===- ImplicitNullChecks.cpp - Fold null checks into memory accesses -----===//
Sanjoy Das69fad072015-06-15 18:44:27 +00002//
Chandler Carruth2946cd72019-01-19 08:50:56 +00003// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
Sanjoy Das69fad072015-06-15 18:44:27 +00006//
7//===----------------------------------------------------------------------===//
8//
9// This pass turns explicit null checks of the form
10//
11// test %r10, %r10
12// je throw_npe
13// movl (%r10), %esi
14// ...
15//
16// to
17//
18// faulting_load_op("movl (%r10), %esi", throw_npe)
19// ...
20//
21// With the help of a runtime that understands the .fault_maps section,
22// faulting_load_op branches to throw_npe if executing movl (%r10), %esi incurs
23// a page fault.
Serguei Katkov51c220c2017-04-12 04:41:35 +000024// Store and LoadStore are also supported.
Sanjoy Das69fad072015-06-15 18:44:27 +000025//
26//===----------------------------------------------------------------------===//
27
Eugene Zelenko900b6332017-08-29 22:32:07 +000028#include "llvm/ADT/ArrayRef.h"
29#include "llvm/ADT/None.h"
30#include "llvm/ADT/Optional.h"
31#include "llvm/ADT/STLExtras.h"
Sanjoy Das69fad072015-06-15 18:44:27 +000032#include "llvm/ADT/SmallVector.h"
Sanjoy Das8ee6a302015-07-06 23:32:10 +000033#include "llvm/ADT/Statistic.h"
Sanjoy Dase57bf682016-06-22 22:16:51 +000034#include "llvm/Analysis/AliasAnalysis.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000035#include "llvm/Analysis/MemoryLocation.h"
Sanjoy Das2f63cbc2017-02-07 19:19:49 +000036#include "llvm/CodeGen/FaultMaps.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000037#include "llvm/CodeGen/MachineBasicBlock.h"
Sanjoy Das69fad072015-06-15 18:44:27 +000038#include "llvm/CodeGen/MachineFunction.h"
Sanjoy Das69fad072015-06-15 18:44:27 +000039#include "llvm/CodeGen/MachineFunctionPass.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000040#include "llvm/CodeGen/MachineInstr.h"
Sanjoy Das69fad072015-06-15 18:44:27 +000041#include "llvm/CodeGen/MachineInstrBuilder.h"
Chandler Carruth6bda14b2017-06-06 11:49:48 +000042#include "llvm/CodeGen/MachineMemOperand.h"
Chandler Carruth6bda14b2017-06-06 11:49:48 +000043#include "llvm/CodeGen/MachineOperand.h"
44#include "llvm/CodeGen/MachineRegisterInfo.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000045#include "llvm/CodeGen/PseudoSourceValue.h"
David Blaikie3f833ed2017-11-08 01:01:31 +000046#include "llvm/CodeGen/TargetInstrInfo.h"
David Blaikieb3bde2e2017-11-17 01:07:10 +000047#include "llvm/CodeGen/TargetOpcodes.h"
48#include "llvm/CodeGen/TargetRegisterInfo.h"
49#include "llvm/CodeGen/TargetSubtargetInfo.h"
Sanjoy Das69fad072015-06-15 18:44:27 +000050#include "llvm/IR/BasicBlock.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000051#include "llvm/IR/DebugLoc.h"
Chen Li00038782015-08-04 04:41:34 +000052#include "llvm/IR/LLVMContext.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000053#include "llvm/MC/MCInstrDesc.h"
54#include "llvm/MC/MCRegisterInfo.h"
55#include "llvm/Pass.h"
Sanjoy Das69fad072015-06-15 18:44:27 +000056#include "llvm/Support/CommandLine.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000057#include <cassert>
58#include <cstdint>
59#include <iterator>
Sanjoy Das69fad072015-06-15 18:44:27 +000060
61using namespace llvm;
62
Chad Rosierc27a18f2016-03-09 16:00:35 +000063static cl::opt<int> PageSize("imp-null-check-page-size",
64 cl::desc("The page size of the target in bytes"),
Zachary Turner8065f0b2017-12-01 00:53:10 +000065 cl::init(4096), cl::Hidden);
Sanjoy Das69fad072015-06-15 18:44:27 +000066
Sanjoy Das9a129802016-12-23 00:41:21 +000067static cl::opt<unsigned> MaxInstsToConsider(
68 "imp-null-max-insts-to-consider",
69 cl::desc("The max number of instructions to consider hoisting loads over "
70 "(the algorithm is quadratic over this number)"),
Zachary Turner8065f0b2017-12-01 00:53:10 +000071 cl::Hidden, cl::init(8));
Sanjoy Das9a129802016-12-23 00:41:21 +000072
Sanjoy Das8ee6a302015-07-06 23:32:10 +000073#define DEBUG_TYPE "implicit-null-checks"
74
75STATISTIC(NumImplicitNullChecks,
76 "Number of explicit null checks made implicit");
77
Sanjoy Das69fad072015-06-15 18:44:27 +000078namespace {
79
80class ImplicitNullChecks : public MachineFunctionPass {
Sanjoy Das9a129802016-12-23 00:41:21 +000081 /// Return true if \c computeDependence can process \p MI.
82 static bool canHandle(const MachineInstr *MI);
83
84 /// Helper function for \c computeDependence. Return true if \p A
85 /// and \p B do not have any dependences between them, and can be
86 /// re-ordered without changing program semantics.
87 bool canReorder(const MachineInstr *A, const MachineInstr *B);
88
89 /// A data type for representing the result computed by \c
90 /// computeDependence. States whether it is okay to reorder the
91 /// instruction passed to \c computeDependence with at most one
Fangrui Song58963e42018-09-08 02:04:20 +000092 /// dependency.
Sanjoy Das9a129802016-12-23 00:41:21 +000093 struct DependenceResult {
94 /// Can we actually re-order \p MI with \p Insts (see \c
95 /// computeDependence).
96 bool CanReorder;
97
98 /// If non-None, then an instruction in \p Insts that also must be
99 /// hoisted.
100 Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence;
101
102 /*implicit*/ DependenceResult(
103 bool CanReorder,
104 Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence)
105 : CanReorder(CanReorder), PotentialDependence(PotentialDependence) {
106 assert((!PotentialDependence || CanReorder) &&
107 "!CanReorder && PotentialDependence.hasValue() not allowed!");
108 }
109 };
110
111 /// Compute a result for the following question: can \p MI be
112 /// re-ordered from after \p Insts to before it.
113 ///
114 /// \c canHandle should return true for all instructions in \p
115 /// Insts.
116 DependenceResult computeDependence(const MachineInstr *MI,
Fangrui Songcb0bab82018-07-16 18:51:40 +0000117 ArrayRef<MachineInstr *> Block);
Sanjoy Das9a129802016-12-23 00:41:21 +0000118
Sanjoy Das69fad072015-06-15 18:44:27 +0000119 /// Represents one null check that can be made implicit.
Sanjoy Dase173b9a2016-06-21 02:10:18 +0000120 class NullCheck {
Sanjoy Das69fad072015-06-15 18:44:27 +0000121 // The memory operation the null check can be folded into.
122 MachineInstr *MemOperation;
123
124 // The instruction actually doing the null check (Ptr != 0).
125 MachineInstr *CheckOperation;
126
127 // The block the check resides in.
128 MachineBasicBlock *CheckBlock;
129
Eric Christopher572e03a2015-06-19 01:53:21 +0000130 // The block branched to if the pointer is non-null.
Sanjoy Das69fad072015-06-15 18:44:27 +0000131 MachineBasicBlock *NotNullSucc;
132
Eric Christopher572e03a2015-06-19 01:53:21 +0000133 // The block branched to if the pointer is null.
Sanjoy Das69fad072015-06-15 18:44:27 +0000134 MachineBasicBlock *NullSucc;
135
Hiroshi Inoue0909ca12018-01-26 08:15:29 +0000136 // If this is non-null, then MemOperation has a dependency on this
Sanjoy Dase57bf682016-06-22 22:16:51 +0000137 // instruction; and it needs to be hoisted to execute before MemOperation.
138 MachineInstr *OnlyDependency;
139
Sanjoy Dase173b9a2016-06-21 02:10:18 +0000140 public:
Sanjoy Das69fad072015-06-15 18:44:27 +0000141 explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation,
142 MachineBasicBlock *checkBlock,
143 MachineBasicBlock *notNullSucc,
Sanjoy Dase57bf682016-06-22 22:16:51 +0000144 MachineBasicBlock *nullSucc,
145 MachineInstr *onlyDependency)
Sanjoy Das69fad072015-06-15 18:44:27 +0000146 : MemOperation(memOperation), CheckOperation(checkOperation),
Sanjoy Dase57bf682016-06-22 22:16:51 +0000147 CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc),
148 OnlyDependency(onlyDependency) {}
Sanjoy Dase173b9a2016-06-21 02:10:18 +0000149
150 MachineInstr *getMemOperation() const { return MemOperation; }
151
152 MachineInstr *getCheckOperation() const { return CheckOperation; }
153
154 MachineBasicBlock *getCheckBlock() const { return CheckBlock; }
155
156 MachineBasicBlock *getNotNullSucc() const { return NotNullSucc; }
157
158 MachineBasicBlock *getNullSucc() const { return NullSucc; }
Sanjoy Dase57bf682016-06-22 22:16:51 +0000159
160 MachineInstr *getOnlyDependency() const { return OnlyDependency; }
Sanjoy Das69fad072015-06-15 18:44:27 +0000161 };
162
163 const TargetInstrInfo *TII = nullptr;
164 const TargetRegisterInfo *TRI = nullptr;
Sanjoy Dase57bf682016-06-22 22:16:51 +0000165 AliasAnalysis *AA = nullptr;
Sanjoy Daseef785c2017-02-28 07:04:49 +0000166 MachineFrameInfo *MFI = nullptr;
Sanjoy Das69fad072015-06-15 18:44:27 +0000167
168 bool analyzeBlockForNullChecks(MachineBasicBlock &MBB,
169 SmallVectorImpl<NullCheck> &NullCheckList);
Sanjoy Das2f63cbc2017-02-07 19:19:49 +0000170 MachineInstr *insertFaultingInstr(MachineInstr *MI, MachineBasicBlock *MBB,
171 MachineBasicBlock *HandlerMBB);
Sanjoy Das69fad072015-06-15 18:44:27 +0000172 void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList);
173
Sanjoy Daseef785c2017-02-28 07:04:49 +0000174 enum AliasResult {
175 AR_NoAlias,
176 AR_MayAlias,
177 AR_WillAliasEverything
178 };
Eugene Zelenko900b6332017-08-29 22:32:07 +0000179
Sanjoy Daseef785c2017-02-28 07:04:49 +0000180 /// Returns AR_NoAlias if \p MI memory operation does not alias with
181 /// \p PrevMI, AR_MayAlias if they may alias and AR_WillAliasEverything if
182 /// they may alias and any further memory operation may alias with \p PrevMI.
Bjorn Pettersson238c9d6302019-04-19 09:08:38 +0000183 AliasResult areMemoryOpsAliased(const MachineInstr &MI,
184 const MachineInstr *PrevMI) const;
Sanjoy Das15e50b52017-02-01 02:49:25 +0000185
Sanjoy Daseef785c2017-02-28 07:04:49 +0000186 enum SuitabilityResult {
187 SR_Suitable,
188 SR_Unsuitable,
189 SR_Impossible
190 };
Eugene Zelenko900b6332017-08-29 22:32:07 +0000191
Sanjoy Das15e50b52017-02-01 02:49:25 +0000192 /// 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
Sanjoy Daseef785c2017-02-28 07:04:49 +0000197 /// the explicit null check on \p PointerReg.
Bjorn Pettersson238c9d6302019-04-19 09:08:38 +0000198 SuitabilityResult isSuitableMemoryOp(const MachineInstr &MI,
199 unsigned PointerReg,
Sanjoy Daseef785c2017-02-28 07:04:49 +0000200 ArrayRef<MachineInstr *> PrevInsts);
Sanjoy Das50fef432016-12-23 00:41:24 +0000201
Hiroshi Inoue8f976ba2018-01-17 12:29:38 +0000202 /// Return true if \p FaultingMI can be hoisted from after the
Sanjoy Das50fef432016-12-23 00:41:24 +0000203 /// instructions in \p InstsSeenSoFar to before them. Set \p Dependence to a
204 /// non-null value if we also need to (and legally can) hoist a depedency.
Sanjoy Das2f63cbc2017-02-07 19:19:49 +0000205 bool canHoistInst(MachineInstr *FaultingMI, unsigned PointerReg,
206 ArrayRef<MachineInstr *> InstsSeenSoFar,
207 MachineBasicBlock *NullSucc, MachineInstr *&Dependence);
Sanjoy Das50fef432016-12-23 00:41:24 +0000208
Sanjoy Das69fad072015-06-15 18:44:27 +0000209public:
210 static char ID;
211
212 ImplicitNullChecks() : MachineFunctionPass(ID) {
213 initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry());
214 }
215
216 bool runOnMachineFunction(MachineFunction &MF) override;
Eugene Zelenko900b6332017-08-29 22:32:07 +0000217
Sanjoy Dase57bf682016-06-22 22:16:51 +0000218 void getAnalysisUsage(AnalysisUsage &AU) const override {
219 AU.addRequired<AAResultsWrapperPass>();
220 MachineFunctionPass::getAnalysisUsage(AU);
221 }
Derek Schuffad154c82016-03-28 17:05:30 +0000222
223 MachineFunctionProperties getRequiredProperties() const override {
224 return MachineFunctionProperties().set(
Matthias Braun1eb47362016-08-25 01:27:13 +0000225 MachineFunctionProperties::Property::NoVRegs);
Derek Schuffad154c82016-03-28 17:05:30 +0000226 }
Sanjoy Das69fad072015-06-15 18:44:27 +0000227};
Sanjoy Dasedc394f2015-11-12 20:51:44 +0000228
Eugene Zelenko900b6332017-08-29 22:32:07 +0000229} // end anonymous namespace
Sanjoy Dasedc394f2015-11-12 20:51:44 +0000230
Sanjoy Das9a129802016-12-23 00:41:21 +0000231bool ImplicitNullChecks::canHandle(const MachineInstr *MI) {
Sanjoy Das2f63cbc2017-02-07 19:19:49 +0000232 if (MI->isCall() || MI->hasUnmodeledSideEffects())
Sanjoy Das9a129802016-12-23 00:41:21 +0000233 return false;
234 auto IsRegMask = [](const MachineOperand &MO) { return MO.isRegMask(); };
235 (void)IsRegMask;
Sanjoy Dasedc394f2015-11-12 20:51:44 +0000236
Sanjoy Das9a129802016-12-23 00:41:21 +0000237 assert(!llvm::any_of(MI->operands(), IsRegMask) &&
238 "Calls were filtered out above!");
Sanjoy Dasedc394f2015-11-12 20:51:44 +0000239
Philip Reames21a50cc2019-03-13 03:25:20 +0000240 auto IsUnordered = [](MachineMemOperand *MMO) { return MMO->isUnordered(); };
241 return llvm::all_of(MI->memoperands(), IsUnordered);
Sanjoy Das9a129802016-12-23 00:41:21 +0000242}
Sanjoy Dasedc394f2015-11-12 20:51:44 +0000243
Sanjoy Das9a129802016-12-23 00:41:21 +0000244ImplicitNullChecks::DependenceResult
245ImplicitNullChecks::computeDependence(const MachineInstr *MI,
246 ArrayRef<MachineInstr *> Block) {
247 assert(llvm::all_of(Block, canHandle) && "Check this first!");
Eugene Zelenko900b6332017-08-29 22:32:07 +0000248 assert(!is_contained(Block, MI) && "Block must be exclusive of MI!");
Sanjoy Das9a129802016-12-23 00:41:21 +0000249
250 Optional<ArrayRef<MachineInstr *>::iterator> Dep;
251
252 for (auto I = Block.begin(), E = Block.end(); I != E; ++I) {
253 if (canReorder(*I, MI))
254 continue;
255
256 if (Dep == None) {
257 // Found one possible dependency, keep track of it.
258 Dep = I;
259 } else {
260 // We found two dependencies, so bail out.
261 return {false, None};
Sanjoy Dasedc394f2015-11-12 20:51:44 +0000262 }
263 }
264
Sanjoy Das9a129802016-12-23 00:41:21 +0000265 return {true, Dep};
Sanjoy Dasedc394f2015-11-12 20:51:44 +0000266}
267
Sanjoy Das9a129802016-12-23 00:41:21 +0000268bool ImplicitNullChecks::canReorder(const MachineInstr *A,
269 const MachineInstr *B) {
270 assert(canHandle(A) && canHandle(B) && "Precondition!");
Sanjoy Dasedc394f2015-11-12 20:51:44 +0000271
Sanjoy Das9a129802016-12-23 00:41:21 +0000272 // canHandle makes sure that we _can_ correctly analyze the dependencies
273 // between A and B here -- for instance, we should not be dealing with heap
274 // load-store dependencies here.
Sanjoy Dasedc394f2015-11-12 20:51:44 +0000275
Sanjoy Das9a129802016-12-23 00:41:21 +0000276 for (auto MOA : A->operands()) {
277 if (!(MOA.isReg() && MOA.getReg()))
278 continue;
Sanjoy Dase57bf682016-06-22 22:16:51 +0000279
Sanjoy Das9a129802016-12-23 00:41:21 +0000280 unsigned RegA = MOA.getReg();
281 for (auto MOB : B->operands()) {
282 if (!(MOB.isReg() && MOB.getReg()))
283 continue;
Sanjoy Dase57bf682016-06-22 22:16:51 +0000284
Sanjoy Das9a129802016-12-23 00:41:21 +0000285 unsigned RegB = MOB.getReg();
Sanjoy Dase57bf682016-06-22 22:16:51 +0000286
Sanjoy Das08da2e22017-02-01 16:04:21 +0000287 if (TRI->regsOverlap(RegA, RegB) && (MOA.isDef() || MOB.isDef()))
Sanjoy Das9a129802016-12-23 00:41:21 +0000288 return false;
Sanjoy Dasedc394f2015-11-12 20:51:44 +0000289 }
290 }
291
292 return true;
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000293}
Sanjoy Das69fad072015-06-15 18:44:27 +0000294
295bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
296 TII = MF.getSubtarget().getInstrInfo();
297 TRI = MF.getRegInfo().getTargetRegisterInfo();
Sanjoy Daseef785c2017-02-28 07:04:49 +0000298 MFI = &MF.getFrameInfo();
Sanjoy Dase57bf682016-06-22 22:16:51 +0000299 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
Sanjoy Das69fad072015-06-15 18:44:27 +0000300
301 SmallVector<NullCheck, 16> NullCheckList;
302
303 for (auto &MBB : MF)
304 analyzeBlockForNullChecks(MBB, NullCheckList);
305
306 if (!NullCheckList.empty())
307 rewriteNullChecks(NullCheckList);
308
309 return !NullCheckList.empty();
310}
311
Sanjoy Dase57bf682016-06-22 22:16:51 +0000312// Return true if any register aliasing \p Reg is live-in into \p MBB.
313static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI,
314 MachineBasicBlock *MBB, unsigned Reg) {
315 for (MCRegAliasIterator AR(Reg, TRI, /*IncludeSelf*/ true); AR.isValid();
316 ++AR)
317 if (MBB->isLiveIn(*AR))
318 return true;
319 return false;
320}
321
Sanjoy Daseef785c2017-02-28 07:04:49 +0000322ImplicitNullChecks::AliasResult
Bjorn Pettersson238c9d6302019-04-19 09:08:38 +0000323ImplicitNullChecks::areMemoryOpsAliased(const MachineInstr &MI,
324 const MachineInstr *PrevMI) const {
Sanjoy Daseef785c2017-02-28 07:04:49 +0000325 // If it is not memory access, skip the check.
326 if (!(PrevMI->mayStore() || PrevMI->mayLoad()))
327 return AR_NoAlias;
328 // Load-Load may alias
329 if (!(MI.mayStore() || PrevMI->mayStore()))
330 return AR_NoAlias;
331 // We lost info, conservatively alias. If it was store then no sense to
332 // continue because we won't be able to check against it further.
333 if (MI.memoperands_empty())
334 return MI.mayStore() ? AR_WillAliasEverything : AR_MayAlias;
335 if (PrevMI->memoperands_empty())
336 return PrevMI->mayStore() ? AR_WillAliasEverything : AR_MayAlias;
337
338 for (MachineMemOperand *MMO1 : MI.memoperands()) {
339 // MMO1 should have a value due it comes from operation we'd like to use
340 // as implicit null check.
341 assert(MMO1->getValue() && "MMO1 should have a Value!");
342 for (MachineMemOperand *MMO2 : PrevMI->memoperands()) {
343 if (const PseudoSourceValue *PSV = MMO2->getPseudoValue()) {
344 if (PSV->mayAlias(MFI))
345 return AR_MayAlias;
346 continue;
347 }
George Burgess IV6ef80022018-10-10 21:28:44 +0000348 llvm::AliasResult AAResult =
349 AA->alias(MemoryLocation(MMO1->getValue(), LocationSize::unknown(),
350 MMO1->getAAInfo()),
351 MemoryLocation(MMO2->getValue(), LocationSize::unknown(),
352 MMO2->getAAInfo()));
Sanjoy Daseef785c2017-02-28 07:04:49 +0000353 if (AAResult != NoAlias)
354 return AR_MayAlias;
355 }
356 }
357 return AR_NoAlias;
358}
359
Sanjoy Das15e50b52017-02-01 02:49:25 +0000360ImplicitNullChecks::SuitabilityResult
Bjorn Pettersson238c9d6302019-04-19 09:08:38 +0000361ImplicitNullChecks::isSuitableMemoryOp(const MachineInstr &MI,
362 unsigned PointerReg,
Sanjoy Daseef785c2017-02-28 07:04:49 +0000363 ArrayRef<MachineInstr *> PrevInsts) {
Sanjoy Das50fef432016-12-23 00:41:24 +0000364 int64_t Offset;
Bjorn Pettersson238c9d6302019-04-19 09:08:38 +0000365 const MachineOperand *BaseOp;
Sanjoy Das50fef432016-12-23 00:41:24 +0000366
Francis Visoiu Mistrihd7eebd62018-11-28 12:00:20 +0000367 if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, TRI) ||
368 !BaseOp->isReg() || BaseOp->getReg() != PointerReg)
Sanjoy Daseef785c2017-02-28 07:04:49 +0000369 return SR_Unsuitable;
Sanjoy Das50fef432016-12-23 00:41:24 +0000370
Sanjoy Das2f63cbc2017-02-07 19:19:49 +0000371 // We want the mem access to be issued at a sane offset from PointerReg,
372 // so that if PointerReg is null then the access reliably page faults.
373 if (!((MI.mayLoad() || MI.mayStore()) && !MI.isPredicable() &&
Yichao Yua18b0b12017-10-17 11:47:36 +0000374 -PageSize < Offset && Offset < PageSize))
Sanjoy Daseef785c2017-02-28 07:04:49 +0000375 return SR_Unsuitable;
Sanjoy Das50fef432016-12-23 00:41:24 +0000376
Serguei Katkov0b0dc572017-06-21 06:38:23 +0000377 // Finally, check whether the current memory access aliases with previous one.
378 for (auto *PrevMI : PrevInsts) {
379 AliasResult AR = areMemoryOpsAliased(MI, PrevMI);
380 if (AR == AR_WillAliasEverything)
381 return SR_Impossible;
382 if (AR == AR_MayAlias)
383 return SR_Unsuitable;
384 }
385 return SR_Suitable;
Sanjoy Das50fef432016-12-23 00:41:24 +0000386}
387
Sanjoy Das2f63cbc2017-02-07 19:19:49 +0000388bool ImplicitNullChecks::canHoistInst(MachineInstr *FaultingMI,
389 unsigned PointerReg,
390 ArrayRef<MachineInstr *> InstsSeenSoFar,
391 MachineBasicBlock *NullSucc,
392 MachineInstr *&Dependence) {
Sanjoy Das50fef432016-12-23 00:41:24 +0000393 auto DepResult = computeDependence(FaultingMI, InstsSeenSoFar);
394 if (!DepResult.CanReorder)
395 return false;
396
397 if (!DepResult.PotentialDependence) {
398 Dependence = nullptr;
399 return true;
400 }
401
402 auto DependenceItr = *DepResult.PotentialDependence;
403 auto *DependenceMI = *DependenceItr;
404
405 // We don't want to reason about speculating loads. Note -- at this point
406 // we should have already filtered out all of the other non-speculatable
407 // things, like calls and stores.
Serguei Katkov6ea2e812017-08-09 05:17:02 +0000408 // We also do not want to hoist stores because it might change the memory
409 // while the FaultingMI may result in faulting.
Sanjoy Das50fef432016-12-23 00:41:24 +0000410 assert(canHandle(DependenceMI) && "Should never have reached here!");
Serguei Katkov6ea2e812017-08-09 05:17:02 +0000411 if (DependenceMI->mayLoadOrStore())
Sanjoy Das50fef432016-12-23 00:41:24 +0000412 return false;
413
414 for (auto &DependenceMO : DependenceMI->operands()) {
415 if (!(DependenceMO.isReg() && DependenceMO.getReg()))
416 continue;
417
418 // Make sure that we won't clobber any live ins to the sibling block by
419 // hoisting Dependency. For instance, we can't hoist INST to before the
420 // null check (even if it safe, and does not violate any dependencies in
421 // the non_null_block) if %rdx is live in to _null_block.
422 //
423 // test %rcx, %rcx
424 // je _null_block
425 // _non_null_block:
Francis Visoiu Mistriha8a83d12017-12-07 10:40:31 +0000426 // %rdx = INST
Sanjoy Das50fef432016-12-23 00:41:24 +0000427 // ...
428 //
429 // This restriction does not apply to the faulting load inst because in
430 // case the pointer loaded from is in the null page, the load will not
431 // semantically execute, and affect machine state. That is, if the load
432 // was loading into %rax and it faults, the value of %rax should stay the
433 // same as it would have been had the load not have executed and we'd have
434 // branched to NullSucc directly.
435 if (AnyAliasLiveIn(TRI, NullSucc, DependenceMO.getReg()))
436 return false;
437
438 // The Dependency can't be re-defining the base register -- then we won't
439 // get the memory operation on the address we want. This is already
440 // checked in \c IsSuitableMemoryOp.
Sanjoy Das08da2e22017-02-01 16:04:21 +0000441 assert(!(DependenceMO.isDef() &&
442 TRI->regsOverlap(DependenceMO.getReg(), PointerReg)) &&
Sanjoy Das50fef432016-12-23 00:41:24 +0000443 "Should have been checked before!");
444 }
445
446 auto DepDepResult =
447 computeDependence(DependenceMI, {InstsSeenSoFar.begin(), DependenceItr});
448
449 if (!DepDepResult.CanReorder || DepDepResult.PotentialDependence)
450 return false;
451
452 Dependence = DependenceMI;
453 return true;
454}
455
Sanjoy Das69fad072015-06-15 18:44:27 +0000456/// Analyze MBB to check if its terminating branch can be turned into an
457/// implicit null check. If yes, append a description of the said null check to
458/// NullCheckList and return true, else return false.
459bool ImplicitNullChecks::analyzeBlockForNullChecks(
460 MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
Eugene Zelenko900b6332017-08-29 22:32:07 +0000461 using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
Sanjoy Das69fad072015-06-15 18:44:27 +0000462
Sanjoy Dase8b81642015-11-12 20:51:49 +0000463 MDNode *BranchMD = nullptr;
464 if (auto *BB = MBB.getBasicBlock())
465 BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit);
466
Sanjoy Das9c41a932015-06-30 21:22:32 +0000467 if (!BranchMD)
468 return false;
469
Sanjoy Das69fad072015-06-15 18:44:27 +0000470 MachineBranchPredicate MBP;
471
Jacques Pienaar71c30a12016-07-15 14:41:04 +0000472 if (TII->analyzeBranchPredicate(MBB, MBP, true))
Sanjoy Das69fad072015-06-15 18:44:27 +0000473 return false;
474
475 // Is the predicate comparing an integer to zero?
476 if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
477 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
478 MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
479 return false;
480
481 // If we cannot erase the test instruction itself, then making the null check
482 // implicit does not buy us much.
483 if (!MBP.SingleUseCondition)
484 return false;
485
486 MachineBasicBlock *NotNullSucc, *NullSucc;
487
488 if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
489 NotNullSucc = MBP.TrueDest;
490 NullSucc = MBP.FalseDest;
491 } else {
492 NotNullSucc = MBP.FalseDest;
493 NullSucc = MBP.TrueDest;
494 }
495
496 // We handle the simplest case for now. We can potentially do better by using
497 // the machine dominator tree.
498 if (NotNullSucc->pred_size() != 1)
499 return false;
500
Max Kazantseve8e01142018-07-04 08:01:26 +0000501 // To prevent the invalid transformation of the following code:
502 //
503 // mov %rax, %rcx
504 // test %rax, %rax
505 // %rax = ...
506 // je throw_npe
507 // mov(%rcx), %r9
508 // mov(%rax), %r10
509 //
510 // into:
511 //
512 // mov %rax, %rcx
513 // %rax = ....
514 // faulting_load_op("movl (%rax), %r10", throw_npe)
515 // mov(%rcx), %r9
516 //
517 // we must ensure that there are no instructions between the 'test' and
518 // conditional jump that modify %rax.
519 const unsigned PointerReg = MBP.LHS.getReg();
520
521 assert(MBP.ConditionDef->getParent() == &MBB && "Should be in basic block");
522
523 for (auto I = MBB.rbegin(); MBP.ConditionDef != &*I; ++I)
524 if (I->modifiesRegister(PointerReg, TRI))
525 return false;
526
Sanjoy Das69fad072015-06-15 18:44:27 +0000527 // Starting with a code fragment like:
528 //
Francis Visoiu Mistrih9d7bb0c2017-11-28 17:15:09 +0000529 // test %rax, %rax
Sanjoy Das69fad072015-06-15 18:44:27 +0000530 // jne LblNotNull
531 //
532 // LblNull:
533 // callq throw_NullPointerException
534 //
535 // LblNotNull:
Sanjoy Dasb7718452015-07-09 20:13:25 +0000536 // Inst0
537 // Inst1
538 // ...
Francis Visoiu Mistrih9d7bb0c2017-11-28 17:15:09 +0000539 // Def = Load (%rax + <offset>)
Sanjoy Das69fad072015-06-15 18:44:27 +0000540 // ...
541 //
542 //
543 // we want to end up with
544 //
Francis Visoiu Mistrih9d7bb0c2017-11-28 17:15:09 +0000545 // Def = FaultingLoad (%rax + <offset>), LblNull
Sanjoy Das69fad072015-06-15 18:44:27 +0000546 // jmp LblNotNull ;; explicit or fallthrough
547 //
548 // LblNotNull:
Sanjoy Dasb7718452015-07-09 20:13:25 +0000549 // Inst0
550 // Inst1
Sanjoy Das69fad072015-06-15 18:44:27 +0000551 // ...
552 //
553 // LblNull:
554 // callq throw_NullPointerException
555 //
Sanjoy Dasac9c5b12015-11-13 08:14:00 +0000556 //
557 // To see why this is legal, consider the two possibilities:
558 //
Francis Visoiu Mistrih9d7bb0c2017-11-28 17:15:09 +0000559 // 1. %rax is null: since we constrain <offset> to be less than PageSize, the
Sanjoy Dasac9c5b12015-11-13 08:14:00 +0000560 // load instruction dereferences the null page, causing a segmentation
561 // fault.
562 //
Francis Visoiu Mistrih9d7bb0c2017-11-28 17:15:09 +0000563 // 2. %rax is not null: in this case we know that the load cannot fault, as
Sanjoy Dasac9c5b12015-11-13 08:14:00 +0000564 // otherwise the load would've faulted in the original program too and the
565 // original program would've been undefined.
566 //
567 // This reasoning cannot be extended to justify hoisting through arbitrary
568 // control flow. For instance, in the example below (in pseudo-C)
569 //
570 // if (ptr == null) { throw_npe(); unreachable; }
571 // if (some_cond) { return 42; }
572 // v = ptr->field; // LD
573 // ...
574 //
575 // we cannot (without code duplication) use the load marked "LD" to null check
576 // ptr -- clause (2) above does not apply in this case. In the above program
577 // the safety of ptr->field can be dependent on some_cond; and, for instance,
578 // ptr could be some non-null invalid reference that never gets loaded from
579 // because some_cond is always true.
Sanjoy Das69fad072015-06-15 18:44:27 +0000580
Sanjoy Das9a129802016-12-23 00:41:21 +0000581 SmallVector<MachineInstr *, 8> InstsSeenSoFar;
Sanjoy Dasb7718452015-07-09 20:13:25 +0000582
Sanjoy Das9a129802016-12-23 00:41:21 +0000583 for (auto &MI : *NotNullSucc) {
584 if (!canHandle(&MI) || InstsSeenSoFar.size() >= MaxInstsToConsider)
585 return false;
586
587 MachineInstr *Dependence;
Sanjoy Daseef785c2017-02-28 07:04:49 +0000588 SuitabilityResult SR = isSuitableMemoryOp(MI, PointerReg, InstsSeenSoFar);
Sanjoy Das15e50b52017-02-01 02:49:25 +0000589 if (SR == SR_Impossible)
590 return false;
Sanjoy Das2f63cbc2017-02-07 19:19:49 +0000591 if (SR == SR_Suitable &&
592 canHoistInst(&MI, PointerReg, InstsSeenSoFar, NullSucc, Dependence)) {
Sanjoy Das9a129802016-12-23 00:41:21 +0000593 NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc,
594 NullSucc, Dependence);
595 return true;
596 }
597
Serguei Katkov0b0dc572017-06-21 06:38:23 +0000598 // If MI re-defines the PointerReg then we cannot move further.
Eugene Zelenko900b6332017-08-29 22:32:07 +0000599 if (llvm::any_of(MI.operands(), [&](MachineOperand &MO) {
Serguei Katkov0b0dc572017-06-21 06:38:23 +0000600 return MO.isReg() && MO.getReg() && MO.isDef() &&
601 TRI->regsOverlap(MO.getReg(), PointerReg);
602 }))
603 return false;
Sanjoy Das9a129802016-12-23 00:41:21 +0000604 InstsSeenSoFar.push_back(&MI);
Sanjoy Dasb7718452015-07-09 20:13:25 +0000605 }
606
Sanjoy Das69fad072015-06-15 18:44:27 +0000607 return false;
608}
609
Sanjoy Das2f63cbc2017-02-07 19:19:49 +0000610/// Wrap a machine instruction, MI, into a FAULTING machine instruction.
611/// The FAULTING instruction does the same load/store as MI
612/// (defining the same register), and branches to HandlerMBB if the mem access
613/// faults. The FAULTING instruction is inserted at the end of MBB.
614MachineInstr *ImplicitNullChecks::insertFaultingInstr(
615 MachineInstr *MI, MachineBasicBlock *MBB, MachineBasicBlock *HandlerMBB) {
Sanjoy Das93d608c2015-07-20 20:31:39 +0000616 const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for
617 // all targets.
618
Sanjoy Das69fad072015-06-15 18:44:27 +0000619 DebugLoc DL;
Sanjoy Das2f63cbc2017-02-07 19:19:49 +0000620 unsigned NumDefs = MI->getDesc().getNumDefs();
Sanjoy Das93d608c2015-07-20 20:31:39 +0000621 assert(NumDefs <= 1 && "other cases unhandled!");
Sanjoy Das69fad072015-06-15 18:44:27 +0000622
Sanjoy Das93d608c2015-07-20 20:31:39 +0000623 unsigned DefReg = NoRegister;
624 if (NumDefs != 0) {
Craig Topper342273a2018-05-16 23:39:27 +0000625 DefReg = MI->getOperand(0).getReg();
Vedant Kumar5a0872c2018-05-16 23:20:42 +0000626 assert(NumDefs == 1 && "expected exactly one def!");
Sanjoy Das93d608c2015-07-20 20:31:39 +0000627 }
Sanjoy Das69fad072015-06-15 18:44:27 +0000628
Sanjoy Das2f63cbc2017-02-07 19:19:49 +0000629 FaultMaps::FaultKind FK;
630 if (MI->mayLoad())
631 FK =
632 MI->mayStore() ? FaultMaps::FaultingLoadStore : FaultMaps::FaultingLoad;
633 else
634 FK = FaultMaps::FaultingStore;
Sanjoy Das69fad072015-06-15 18:44:27 +0000635
Sanjoy Das2f63cbc2017-02-07 19:19:49 +0000636 auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_OP), DefReg)
637 .addImm(FK)
638 .addMBB(HandlerMBB)
639 .addImm(MI->getOpcode());
640
Matthias Braun605f77952017-05-31 22:23:08 +0000641 for (auto &MO : MI->uses()) {
642 if (MO.isReg()) {
643 MachineOperand NewMO = MO;
644 if (MO.isUse()) {
645 NewMO.setIsKill(false);
646 } else {
647 assert(MO.isDef() && "Expected def or use");
648 NewMO.setIsDead(false);
649 }
650 MIB.add(NewMO);
651 } else {
652 MIB.add(MO);
653 }
654 }
Sanjoy Das69fad072015-06-15 18:44:27 +0000655
Chandler Carruthc73c0302018-08-16 21:30:05 +0000656 MIB.setMemRefs(MI->memoperands());
Sanjoy Das69fad072015-06-15 18:44:27 +0000657
658 return MIB;
659}
660
661/// Rewrite the null checks in NullCheckList into implicit null checks.
662void ImplicitNullChecks::rewriteNullChecks(
663 ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
664 DebugLoc DL;
665
666 for (auto &NC : NullCheckList) {
Sanjoy Das69fad072015-06-15 18:44:27 +0000667 // Remove the conditional branch dependent on the null check.
Matt Arsenault1b9fc8e2016-09-14 20:43:16 +0000668 unsigned BranchesRemoved = TII->removeBranch(*NC.getCheckBlock());
Sanjoy Das69fad072015-06-15 18:44:27 +0000669 (void)BranchesRemoved;
670 assert(BranchesRemoved > 0 && "expected at least one branch!");
671
Sanjoy Dase57bf682016-06-22 22:16:51 +0000672 if (auto *DepMI = NC.getOnlyDependency()) {
673 DepMI->removeFromParent();
674 NC.getCheckBlock()->insert(NC.getCheckBlock()->end(), DepMI);
675 }
676
Sanjoy Das2f63cbc2017-02-07 19:19:49 +0000677 // Insert a faulting instruction where the conditional branch was
678 // originally. We check earlier ensures that this bit of code motion
679 // is legal. We do not touch the successors list for any basic block
680 // since we haven't changed control flow, we've just made it implicit.
681 MachineInstr *FaultingInstr = insertFaultingInstr(
Sanjoy Dase173b9a2016-06-21 02:10:18 +0000682 NC.getMemOperation(), NC.getCheckBlock(), NC.getNullSucc());
Quentin Colombet26dab3a2016-05-03 18:09:06 +0000683 // Now the values defined by MemOperation, if any, are live-in of
684 // the block of MemOperation.
Sanjoy Das2f63cbc2017-02-07 19:19:49 +0000685 // The original operation may define implicit-defs alongside
686 // the value.
Sanjoy Dase173b9a2016-06-21 02:10:18 +0000687 MachineBasicBlock *MBB = NC.getMemOperation()->getParent();
Sanjoy Das2f63cbc2017-02-07 19:19:49 +0000688 for (const MachineOperand &MO : FaultingInstr->operands()) {
Quentin Colombet26dab3a2016-05-03 18:09:06 +0000689 if (!MO.isReg() || !MO.isDef())
690 continue;
691 unsigned Reg = MO.getReg();
692 if (!Reg || MBB->isLiveIn(Reg))
693 continue;
694 MBB->addLiveIn(Reg);
Quentin Colombet12b69912016-04-27 23:26:40 +0000695 }
Sanjoy Dase57bf682016-06-22 22:16:51 +0000696
697 if (auto *DepMI = NC.getOnlyDependency()) {
698 for (auto &MO : DepMI->operands()) {
699 if (!MO.isReg() || !MO.getReg() || !MO.isDef())
700 continue;
701 if (!NC.getNotNullSucc()->isLiveIn(MO.getReg()))
702 NC.getNotNullSucc()->addLiveIn(MO.getReg());
703 }
704 }
705
Sanjoy Dase173b9a2016-06-21 02:10:18 +0000706 NC.getMemOperation()->eraseFromParent();
707 NC.getCheckOperation()->eraseFromParent();
Sanjoy Das69fad072015-06-15 18:44:27 +0000708
709 // Insert an *unconditional* branch to not-null successor.
Matt Arsenaulte8e0f5c2016-09-14 17:24:15 +0000710 TII->insertBranch(*NC.getCheckBlock(), NC.getNotNullSucc(), nullptr,
Sanjoy Dase173b9a2016-06-21 02:10:18 +0000711 /*Cond=*/None, DL);
Sanjoy Das69fad072015-06-15 18:44:27 +0000712
Sanjoy Das8ee6a302015-07-06 23:32:10 +0000713 NumImplicitNullChecks++;
Sanjoy Das69fad072015-06-15 18:44:27 +0000714 }
715}
716
717char ImplicitNullChecks::ID = 0;
Eugene Zelenko900b6332017-08-29 22:32:07 +0000718
Sanjoy Das69fad072015-06-15 18:44:27 +0000719char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID;
Eugene Zelenko900b6332017-08-29 22:32:07 +0000720
Matthias Braun1527baa2017-05-25 21:26:32 +0000721INITIALIZE_PASS_BEGIN(ImplicitNullChecks, DEBUG_TYPE,
Sanjoy Das69fad072015-06-15 18:44:27 +0000722 "Implicit null checks", false, false)
Sanjoy Dase57bf682016-06-22 22:16:51 +0000723INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
Matthias Braun1527baa2017-05-25 21:26:32 +0000724INITIALIZE_PASS_END(ImplicitNullChecks, DEBUG_TYPE,
Sanjoy Das69fad072015-06-15 18:44:27 +0000725 "Implicit null checks", false, false)