Coverage Report

Created: 2019-07-24 05:18

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