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//
26//===----------------------------------------------------------------------===//
27
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"
46
47using namespace llvm;
48
49static cl::opt<unsigned> PageSize("imp-null-check-page-size",
50                                  cl::desc("The page size of the target in "
51                                           "bytes"),
52                                  cl::init(4096));
53
54#define DEBUG_TYPE "implicit-null-checks"
55
56STATISTIC(NumImplicitNullChecks,
57          "Number of explicit null checks made implicit");
58
59namespace {
60
61class ImplicitNullChecks : public MachineFunctionPass {
62  /// Represents one null check that can be made implicit.
63  struct NullCheck {
64    // The memory operation the null check can be folded into.
65    MachineInstr *MemOperation;
66
67    // The instruction actually doing the null check (Ptr != 0).
68    MachineInstr *CheckOperation;
69
70    // The block the check resides in.
71    MachineBasicBlock *CheckBlock;
72
73    // The block branched to if the pointer is non-null.
74    MachineBasicBlock *NotNullSucc;
75
76    // The block branched to if the pointer is null.
77    MachineBasicBlock *NullSucc;
78
79    NullCheck()
80        : MemOperation(), CheckOperation(), CheckBlock(), NotNullSucc(),
81          NullSucc() {}
82
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) {
89    }
90  };
91
92  const TargetInstrInfo *TII = nullptr;
93  const TargetRegisterInfo *TRI = nullptr;
94  MachineModuleInfo *MMI = nullptr;
95
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);
101
102public:
103  static char ID;
104
105  ImplicitNullChecks() : MachineFunctionPass(ID) {
106    initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry());
107  }
108
109  bool runOnMachineFunction(MachineFunction &MF) override;
110};
111
112/// \brief Detect re-ordering hazards and dependencies.
113///
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.
117class HazardDetector {
118  DenseSet<unsigned> RegDefs;
119  DenseSet<unsigned> RegUses;
120  const TargetRegisterInfo &TRI;
121  bool hasSeenClobber;
122
123public:
124  explicit HazardDetector(const TargetRegisterInfo &TRI) :
125    TRI(TRI), hasSeenClobber(false) {}
126
127  /// \brief Make a note of \p MI for later queries to isSafeToHoist.
128  ///
129  /// May clobber this HazardDetector instance.  \see isClobbered.
130  void rememberInstruction(MachineInstr *MI);
131
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);
135
136  /// \brief Return true if this instance of HazardDetector has been clobbered
137  /// (i.e. has no more useful information).
138  ///
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).
144  ///
145  /// Calling rememberInstruction or isSafeToHoist on a clobbered HazardDetector
146  /// is an error.
147  bool isClobbered() { return hasSeenClobber; }
148};
149}
150
151
152void HazardDetector::rememberInstruction(MachineInstr *MI) {
153  assert(!isClobbered() &&
154         "Don't add instructions to a clobbered hazard detector");
155
156  if (MI->mayStore() || MI->hasUnmodeledSideEffects()) {
157    hasSeenClobber = true;
158    return;
159  }
160
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;
165      return;
166    }
167  }
168
169  for (auto &MO : MI->operands()) {
170    if (!MO.isReg() || !MO.getReg())
171      continue;
172
173    if (MO.isDef())
174      RegDefs.insert(MO.getReg());
175    else
176      RegUses.insert(MO.getReg());
177  }
178}
179
180bool HazardDetector::isSafeToHoist(MachineInstr *MI) {
181  assert(!isClobbered() && "isSafeToHoist cannot do anything useful!");
182
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())
187      return false;
188
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
194
195      if (MO.isDef())
196        for (unsigned Reg : RegUses)
197          if (TRI.regsOverlap(Reg, MO.getReg()))
198            return false;  // We found a write-after-read
199    }
200  }
201
202  return true;
203}
204
205bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
206  TII = MF.getSubtarget().getInstrInfo();
207  TRI = MF.getRegInfo().getTargetRegisterInfo();
208  MMI = &MF.getMMI();
209
210  SmallVector<NullCheck, 16> NullCheckList;
211
212  for (auto &MBB : MF)
213    analyzeBlockForNullChecks(MBB, NullCheckList);
214
215  if (!NullCheckList.empty())
216    rewriteNullChecks(NullCheckList);
217
218  return !NullCheckList.empty();
219}
220
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.
224bool ImplicitNullChecks::analyzeBlockForNullChecks(
225    MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
226  typedef TargetInstrInfo::MachineBranchPredicate MachineBranchPredicate;
227
228  MDNode *BranchMD = nullptr;
229  if (auto *BB = MBB.getBasicBlock())
230    BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit);
231
232  if (!BranchMD)
233    return false;
234
235  MachineBranchPredicate MBP;
236
237  if (TII->AnalyzeBranchPredicate(MBB, MBP, true))
238    return false;
239
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)))
244    return false;
245
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)
249    return false;
250
251  MachineBasicBlock *NotNullSucc, *NullSucc;
252
253  if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
254    NotNullSucc = MBP.TrueDest;
255    NullSucc = MBP.FalseDest;
256  } else {
257    NotNullSucc = MBP.FalseDest;
258    NullSucc = MBP.TrueDest;
259  }
260
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)
264    return false;
265
266  // Starting with a code fragment like:
267  //
268  //   test %RAX, %RAX
269  //   jne LblNotNull
270  //
271  //  LblNull:
272  //   callq throw_NullPointerException
273  //
274  //  LblNotNull:
275  //   Inst0
276  //   Inst1
277  //   ...
278  //   Def = Load (%RAX + <offset>)
279  //   ...
280  //
281  //
282  // we want to end up with
283  //
284  //   Def = FaultingLoad (%RAX + <offset>), LblNull
285  //   jmp LblNotNull ;; explicit or fallthrough
286  //
287  //  LblNotNull:
288  //   Inst0
289  //   Inst1
290  //   ...
291  //
292  //  LblNull:
293  //   callq throw_NullPointerException
294  //
295  //
296  // To see why this is legal, consider the two possibilities:
297  //
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
300  //     fault.
301  //
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.
305  //
306  // This reasoning cannot be extended to justify hoisting through arbitrary
307  // control flow.  For instance, in the example below (in pseudo-C)
308  //
309  //    if (ptr == null) { throw_npe(); unreachable; }
310  //    if (some_cond) { return 42; }
311  //    v = ptr->field;  // LD
312  //    ...
313  //
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.
319
320  unsigned PointerReg = MBP.LHS.getReg();
321
322  HazardDetector HD(*TRI);
323
324  for (auto MII = NotNullSucc->begin(), MIE = NotNullSucc->end(); MII != MIE;
325       ++MII) {
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,
333                                   NullSucc);
334        return true;
335      }
336
337    HD.rememberInstruction(MI);
338    if (HD.isClobbered())
339      return false;
340  }
341
342  return false;
343}
344
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.
349MachineInstr *ImplicitNullChecks::insertFaultingLoad(MachineInstr *LoadMI,
350                                                     MachineBasicBlock *MBB,
351                                                     MCSymbol *HandlerLabel) {
352  const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for
353                                 // all targets.
354
355  DebugLoc DL;
356  unsigned NumDefs = LoadMI->getDesc().getNumDefs();
357  assert(NumDefs <= 1 && "other cases unhandled!");
358
359  unsigned DefReg = NoRegister;
360  if (NumDefs != 0) {
361    DefReg = LoadMI->defs().begin()->getReg();
362    assert(std::distance(LoadMI->defs().begin(), LoadMI->defs().end()) == 1 &&
363           "expected exactly one def!");
364  }
365
366  auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_LOAD_OP), DefReg)
367                 .addSym(HandlerLabel)
368                 .addImm(LoadMI->getOpcode());
369
370  for (auto &MO : LoadMI->uses())
371    MIB.addOperand(MO);
372
373  MIB.setMemRefs(LoadMI->memoperands_begin(), LoadMI->memoperands_end());
374
375  return MIB;
376}
377
378/// Rewrite the null checks in NullCheckList into implicit null checks.
379void ImplicitNullChecks::rewriteNullChecks(
380    ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) {
381  DebugLoc DL;
382
383  for (auto &NC : NullCheckList) {
384    MCSymbol *HandlerLabel = MMI->getContext().createTempSymbol();
385
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!");
390
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();
398
399    // Insert an *unconditional* branch to not-null successor.
400    TII->InsertBranch(*NC.CheckBlock, NC.NotNullSucc, nullptr, /*Cond=*/None,
401                      DL);
402
403    // Emit the HandlerLabel as an EH_LABEL.
404    BuildMI(*NC.NullSucc, NC.NullSucc->begin(), DL,
405            TII->get(TargetOpcode::EH_LABEL)).addSym(HandlerLabel);
406
407    NumImplicitNullChecks++;
408  }
409}
410
411char ImplicitNullChecks::ID = 0;
412char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID;
413INITIALIZE_PASS_BEGIN(ImplicitNullChecks, "implicit-null-checks",
414                      "Implicit null checks", false, false)
415INITIALIZE_PASS_END(ImplicitNullChecks, "implicit-null-checks",
416                    "Implicit null checks", false, false)
417