1327952Sdim//===- ImplicitNullChecks.cpp - Fold null checks into memory accesses -----===// 2284677Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6284677Sdim// 7284677Sdim//===----------------------------------------------------------------------===// 8284677Sdim// 9284677Sdim// This pass turns explicit null checks of the form 10284677Sdim// 11284677Sdim// test %r10, %r10 12284677Sdim// je throw_npe 13284677Sdim// movl (%r10), %esi 14284677Sdim// ... 15284677Sdim// 16284677Sdim// to 17284677Sdim// 18284677Sdim// faulting_load_op("movl (%r10), %esi", throw_npe) 19284677Sdim// ... 20284677Sdim// 21284677Sdim// With the help of a runtime that understands the .fault_maps section, 22284677Sdim// faulting_load_op branches to throw_npe if executing movl (%r10), %esi incurs 23284677Sdim// a page fault. 24321369Sdim// Store and LoadStore are also supported. 25284677Sdim// 26284677Sdim//===----------------------------------------------------------------------===// 27284677Sdim 28327952Sdim#include "llvm/ADT/ArrayRef.h" 29327952Sdim#include "llvm/ADT/None.h" 30327952Sdim#include "llvm/ADT/Optional.h" 31327952Sdim#include "llvm/ADT/STLExtras.h" 32284677Sdim#include "llvm/ADT/SmallVector.h" 33286684Sdim#include "llvm/ADT/Statistic.h" 34309124Sdim#include "llvm/Analysis/AliasAnalysis.h" 35327952Sdim#include "llvm/Analysis/MemoryLocation.h" 36321369Sdim#include "llvm/CodeGen/FaultMaps.h" 37327952Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 38284677Sdim#include "llvm/CodeGen/MachineFunction.h" 39321369Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 40327952Sdim#include "llvm/CodeGen/MachineInstr.h" 41321369Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 42286684Sdim#include "llvm/CodeGen/MachineMemOperand.h" 43284677Sdim#include "llvm/CodeGen/MachineOperand.h" 44284677Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 45327952Sdim#include "llvm/CodeGen/PseudoSourceValue.h" 46327952Sdim#include "llvm/CodeGen/TargetInstrInfo.h" 47327952Sdim#include "llvm/CodeGen/TargetOpcodes.h" 48327952Sdim#include "llvm/CodeGen/TargetRegisterInfo.h" 49327952Sdim#include "llvm/CodeGen/TargetSubtargetInfo.h" 50284677Sdim#include "llvm/IR/BasicBlock.h" 51327952Sdim#include "llvm/IR/DebugLoc.h" 52296417Sdim#include "llvm/IR/LLVMContext.h" 53360784Sdim#include "llvm/InitializePasses.h" 54327952Sdim#include "llvm/MC/MCInstrDesc.h" 55327952Sdim#include "llvm/MC/MCRegisterInfo.h" 56327952Sdim#include "llvm/Pass.h" 57284677Sdim#include "llvm/Support/CommandLine.h" 58327952Sdim#include <cassert> 59327952Sdim#include <cstdint> 60327952Sdim#include <iterator> 61284677Sdim 62284677Sdimusing namespace llvm; 63284677Sdim 64309124Sdimstatic cl::opt<int> PageSize("imp-null-check-page-size", 65309124Sdim cl::desc("The page size of the target in bytes"), 66327952Sdim cl::init(4096), cl::Hidden); 67284677Sdim 68314564Sdimstatic cl::opt<unsigned> MaxInstsToConsider( 69314564Sdim "imp-null-max-insts-to-consider", 70314564Sdim cl::desc("The max number of instructions to consider hoisting loads over " 71314564Sdim "(the algorithm is quadratic over this number)"), 72327952Sdim cl::Hidden, cl::init(8)); 73314564Sdim 74286684Sdim#define DEBUG_TYPE "implicit-null-checks" 75286684Sdim 76286684SdimSTATISTIC(NumImplicitNullChecks, 77286684Sdim "Number of explicit null checks made implicit"); 78286684Sdim 79284677Sdimnamespace { 80284677Sdim 81284677Sdimclass ImplicitNullChecks : public MachineFunctionPass { 82314564Sdim /// Return true if \c computeDependence can process \p MI. 83314564Sdim static bool canHandle(const MachineInstr *MI); 84314564Sdim 85314564Sdim /// Helper function for \c computeDependence. Return true if \p A 86314564Sdim /// and \p B do not have any dependences between them, and can be 87314564Sdim /// re-ordered without changing program semantics. 88314564Sdim bool canReorder(const MachineInstr *A, const MachineInstr *B); 89314564Sdim 90314564Sdim /// A data type for representing the result computed by \c 91314564Sdim /// computeDependence. States whether it is okay to reorder the 92314564Sdim /// instruction passed to \c computeDependence with at most one 93344779Sdim /// dependency. 94314564Sdim struct DependenceResult { 95314564Sdim /// Can we actually re-order \p MI with \p Insts (see \c 96314564Sdim /// computeDependence). 97314564Sdim bool CanReorder; 98314564Sdim 99314564Sdim /// If non-None, then an instruction in \p Insts that also must be 100314564Sdim /// hoisted. 101314564Sdim Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence; 102314564Sdim 103314564Sdim /*implicit*/ DependenceResult( 104314564Sdim bool CanReorder, 105314564Sdim Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence) 106314564Sdim : CanReorder(CanReorder), PotentialDependence(PotentialDependence) { 107314564Sdim assert((!PotentialDependence || CanReorder) && 108314564Sdim "!CanReorder && PotentialDependence.hasValue() not allowed!"); 109314564Sdim } 110314564Sdim }; 111314564Sdim 112314564Sdim /// Compute a result for the following question: can \p MI be 113314564Sdim /// re-ordered from after \p Insts to before it. 114314564Sdim /// 115314564Sdim /// \c canHandle should return true for all instructions in \p 116314564Sdim /// Insts. 117314564Sdim DependenceResult computeDependence(const MachineInstr *MI, 118341825Sdim ArrayRef<MachineInstr *> Block); 119314564Sdim 120284677Sdim /// Represents one null check that can be made implicit. 121309124Sdim class NullCheck { 122284677Sdim // The memory operation the null check can be folded into. 123284677Sdim MachineInstr *MemOperation; 124284677Sdim 125284677Sdim // The instruction actually doing the null check (Ptr != 0). 126284677Sdim MachineInstr *CheckOperation; 127284677Sdim 128284677Sdim // The block the check resides in. 129284677Sdim MachineBasicBlock *CheckBlock; 130284677Sdim 131284677Sdim // The block branched to if the pointer is non-null. 132284677Sdim MachineBasicBlock *NotNullSucc; 133284677Sdim 134284677Sdim // The block branched to if the pointer is null. 135284677Sdim MachineBasicBlock *NullSucc; 136284677Sdim 137341825Sdim // If this is non-null, then MemOperation has a dependency on this 138309124Sdim // instruction; and it needs to be hoisted to execute before MemOperation. 139309124Sdim MachineInstr *OnlyDependency; 140284677Sdim 141309124Sdim public: 142284677Sdim explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation, 143284677Sdim MachineBasicBlock *checkBlock, 144284677Sdim MachineBasicBlock *notNullSucc, 145309124Sdim MachineBasicBlock *nullSucc, 146309124Sdim MachineInstr *onlyDependency) 147284677Sdim : MemOperation(memOperation), CheckOperation(checkOperation), 148309124Sdim CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc), 149309124Sdim OnlyDependency(onlyDependency) {} 150309124Sdim 151309124Sdim MachineInstr *getMemOperation() const { return MemOperation; } 152309124Sdim 153309124Sdim MachineInstr *getCheckOperation() const { return CheckOperation; } 154309124Sdim 155309124Sdim MachineBasicBlock *getCheckBlock() const { return CheckBlock; } 156309124Sdim 157309124Sdim MachineBasicBlock *getNotNullSucc() const { return NotNullSucc; } 158309124Sdim 159309124Sdim MachineBasicBlock *getNullSucc() const { return NullSucc; } 160309124Sdim 161309124Sdim MachineInstr *getOnlyDependency() const { return OnlyDependency; } 162284677Sdim }; 163284677Sdim 164284677Sdim const TargetInstrInfo *TII = nullptr; 165284677Sdim const TargetRegisterInfo *TRI = nullptr; 166309124Sdim AliasAnalysis *AA = nullptr; 167321369Sdim MachineFrameInfo *MFI = nullptr; 168284677Sdim 169284677Sdim bool analyzeBlockForNullChecks(MachineBasicBlock &MBB, 170284677Sdim SmallVectorImpl<NullCheck> &NullCheckList); 171321369Sdim MachineInstr *insertFaultingInstr(MachineInstr *MI, MachineBasicBlock *MBB, 172321369Sdim MachineBasicBlock *HandlerMBB); 173284677Sdim void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList); 174284677Sdim 175321369Sdim enum AliasResult { 176321369Sdim AR_NoAlias, 177321369Sdim AR_MayAlias, 178321369Sdim AR_WillAliasEverything 179321369Sdim }; 180327952Sdim 181321369Sdim /// Returns AR_NoAlias if \p MI memory operation does not alias with 182321369Sdim /// \p PrevMI, AR_MayAlias if they may alias and AR_WillAliasEverything if 183321369Sdim /// they may alias and any further memory operation may alias with \p PrevMI. 184353358Sdim AliasResult areMemoryOpsAliased(const MachineInstr &MI, 185353358Sdim const MachineInstr *PrevMI) const; 186321369Sdim 187321369Sdim enum SuitabilityResult { 188321369Sdim SR_Suitable, 189321369Sdim SR_Unsuitable, 190321369Sdim SR_Impossible 191321369Sdim }; 192327952Sdim 193321369Sdim /// Return SR_Suitable if \p MI a memory operation that can be used to 194321369Sdim /// implicitly null check the value in \p PointerReg, SR_Unsuitable if 195321369Sdim /// \p MI cannot be used to null check and SR_Impossible if there is 196321369Sdim /// no sense to continue lookup due to any other instruction will not be able 197321369Sdim /// to be used. \p PrevInsts is the set of instruction seen since 198314564Sdim /// the explicit null check on \p PointerReg. 199353358Sdim SuitabilityResult isSuitableMemoryOp(const MachineInstr &MI, 200353358Sdim unsigned PointerReg, 201321369Sdim ArrayRef<MachineInstr *> PrevInsts); 202314564Sdim 203341825Sdim /// Return true if \p FaultingMI can be hoisted from after the 204314564Sdim /// instructions in \p InstsSeenSoFar to before them. Set \p Dependence to a 205314564Sdim /// non-null value if we also need to (and legally can) hoist a depedency. 206321369Sdim bool canHoistInst(MachineInstr *FaultingMI, unsigned PointerReg, 207321369Sdim ArrayRef<MachineInstr *> InstsSeenSoFar, 208321369Sdim MachineBasicBlock *NullSucc, MachineInstr *&Dependence); 209314564Sdim 210284677Sdimpublic: 211284677Sdim static char ID; 212284677Sdim 213284677Sdim ImplicitNullChecks() : MachineFunctionPass(ID) { 214284677Sdim initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry()); 215284677Sdim } 216284677Sdim 217284677Sdim bool runOnMachineFunction(MachineFunction &MF) override; 218327952Sdim 219309124Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 220309124Sdim AU.addRequired<AAResultsWrapperPass>(); 221309124Sdim MachineFunctionPass::getAnalysisUsage(AU); 222309124Sdim } 223309124Sdim 224309124Sdim MachineFunctionProperties getRequiredProperties() const override { 225309124Sdim return MachineFunctionProperties().set( 226314564Sdim MachineFunctionProperties::Property::NoVRegs); 227309124Sdim } 228284677Sdim}; 229296417Sdim 230327952Sdim} // end anonymous namespace 231309124Sdim 232314564Sdimbool ImplicitNullChecks::canHandle(const MachineInstr *MI) { 233353358Sdim if (MI->isCall() || MI->mayRaiseFPException() || 234353358Sdim MI->hasUnmodeledSideEffects()) 235314564Sdim return false; 236314564Sdim auto IsRegMask = [](const MachineOperand &MO) { return MO.isRegMask(); }; 237314564Sdim (void)IsRegMask; 238296417Sdim 239314564Sdim assert(!llvm::any_of(MI->operands(), IsRegMask) && 240314564Sdim "Calls were filtered out above!"); 241296417Sdim 242314564Sdim auto IsUnordered = [](MachineMemOperand *MMO) { return MMO->isUnordered(); }; 243314564Sdim return llvm::all_of(MI->memoperands(), IsUnordered); 244285181Sdim} 245284677Sdim 246314564SdimImplicitNullChecks::DependenceResult 247314564SdimImplicitNullChecks::computeDependence(const MachineInstr *MI, 248314564Sdim ArrayRef<MachineInstr *> Block) { 249314564Sdim assert(llvm::all_of(Block, canHandle) && "Check this first!"); 250327952Sdim assert(!is_contained(Block, MI) && "Block must be exclusive of MI!"); 251296417Sdim 252314564Sdim Optional<ArrayRef<MachineInstr *>::iterator> Dep; 253296417Sdim 254314564Sdim for (auto I = Block.begin(), E = Block.end(); I != E; ++I) { 255314564Sdim if (canReorder(*I, MI)) 256314564Sdim continue; 257296417Sdim 258314564Sdim if (Dep == None) { 259314564Sdim // Found one possible dependency, keep track of it. 260314564Sdim Dep = I; 261314564Sdim } else { 262314564Sdim // We found two dependencies, so bail out. 263314564Sdim return {false, None}; 264296417Sdim } 265296417Sdim } 266296417Sdim 267314564Sdim return {true, Dep}; 268296417Sdim} 269296417Sdim 270314564Sdimbool ImplicitNullChecks::canReorder(const MachineInstr *A, 271314564Sdim const MachineInstr *B) { 272314564Sdim assert(canHandle(A) && canHandle(B) && "Precondition!"); 273296417Sdim 274314564Sdim // canHandle makes sure that we _can_ correctly analyze the dependencies 275314564Sdim // between A and B here -- for instance, we should not be dealing with heap 276314564Sdim // load-store dependencies here. 277296417Sdim 278314564Sdim for (auto MOA : A->operands()) { 279314564Sdim if (!(MOA.isReg() && MOA.getReg())) 280314564Sdim continue; 281296417Sdim 282360784Sdim Register RegA = MOA.getReg(); 283314564Sdim for (auto MOB : B->operands()) { 284314564Sdim if (!(MOB.isReg() && MOB.getReg())) 285314564Sdim continue; 286309124Sdim 287360784Sdim Register RegB = MOB.getReg(); 288309124Sdim 289321369Sdim if (TRI->regsOverlap(RegA, RegB) && (MOA.isDef() || MOB.isDef())) 290314564Sdim return false; 291296417Sdim } 292296417Sdim } 293296417Sdim 294296417Sdim return true; 295296417Sdim} 296296417Sdim 297284677Sdimbool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) { 298284677Sdim TII = MF.getSubtarget().getInstrInfo(); 299284677Sdim TRI = MF.getRegInfo().getTargetRegisterInfo(); 300321369Sdim MFI = &MF.getFrameInfo(); 301309124Sdim AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 302284677Sdim 303284677Sdim SmallVector<NullCheck, 16> NullCheckList; 304284677Sdim 305284677Sdim for (auto &MBB : MF) 306284677Sdim analyzeBlockForNullChecks(MBB, NullCheckList); 307284677Sdim 308284677Sdim if (!NullCheckList.empty()) 309284677Sdim rewriteNullChecks(NullCheckList); 310284677Sdim 311284677Sdim return !NullCheckList.empty(); 312284677Sdim} 313284677Sdim 314309124Sdim// Return true if any register aliasing \p Reg is live-in into \p MBB. 315309124Sdimstatic bool AnyAliasLiveIn(const TargetRegisterInfo *TRI, 316309124Sdim MachineBasicBlock *MBB, unsigned Reg) { 317309124Sdim for (MCRegAliasIterator AR(Reg, TRI, /*IncludeSelf*/ true); AR.isValid(); 318309124Sdim ++AR) 319309124Sdim if (MBB->isLiveIn(*AR)) 320309124Sdim return true; 321309124Sdim return false; 322309124Sdim} 323309124Sdim 324321369SdimImplicitNullChecks::AliasResult 325353358SdimImplicitNullChecks::areMemoryOpsAliased(const MachineInstr &MI, 326353358Sdim const MachineInstr *PrevMI) const { 327321369Sdim // If it is not memory access, skip the check. 328321369Sdim if (!(PrevMI->mayStore() || PrevMI->mayLoad())) 329321369Sdim return AR_NoAlias; 330321369Sdim // Load-Load may alias 331321369Sdim if (!(MI.mayStore() || PrevMI->mayStore())) 332321369Sdim return AR_NoAlias; 333321369Sdim // We lost info, conservatively alias. If it was store then no sense to 334321369Sdim // continue because we won't be able to check against it further. 335321369Sdim if (MI.memoperands_empty()) 336321369Sdim return MI.mayStore() ? AR_WillAliasEverything : AR_MayAlias; 337321369Sdim if (PrevMI->memoperands_empty()) 338321369Sdim return PrevMI->mayStore() ? AR_WillAliasEverything : AR_MayAlias; 339321369Sdim 340321369Sdim for (MachineMemOperand *MMO1 : MI.memoperands()) { 341321369Sdim // MMO1 should have a value due it comes from operation we'd like to use 342321369Sdim // as implicit null check. 343321369Sdim assert(MMO1->getValue() && "MMO1 should have a Value!"); 344321369Sdim for (MachineMemOperand *MMO2 : PrevMI->memoperands()) { 345321369Sdim if (const PseudoSourceValue *PSV = MMO2->getPseudoValue()) { 346321369Sdim if (PSV->mayAlias(MFI)) 347321369Sdim return AR_MayAlias; 348321369Sdim continue; 349321369Sdim } 350344779Sdim llvm::AliasResult AAResult = 351344779Sdim AA->alias(MemoryLocation(MMO1->getValue(), LocationSize::unknown(), 352344779Sdim MMO1->getAAInfo()), 353344779Sdim MemoryLocation(MMO2->getValue(), LocationSize::unknown(), 354344779Sdim MMO2->getAAInfo())); 355321369Sdim if (AAResult != NoAlias) 356321369Sdim return AR_MayAlias; 357321369Sdim } 358321369Sdim } 359321369Sdim return AR_NoAlias; 360321369Sdim} 361321369Sdim 362321369SdimImplicitNullChecks::SuitabilityResult 363353358SdimImplicitNullChecks::isSuitableMemoryOp(const MachineInstr &MI, 364353358Sdim unsigned PointerReg, 365321369Sdim ArrayRef<MachineInstr *> PrevInsts) { 366314564Sdim int64_t Offset; 367353358Sdim const MachineOperand *BaseOp; 368314564Sdim 369344779Sdim if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, TRI) || 370344779Sdim !BaseOp->isReg() || BaseOp->getReg() != PointerReg) 371321369Sdim return SR_Unsuitable; 372314564Sdim 373321369Sdim // We want the mem access to be issued at a sane offset from PointerReg, 374321369Sdim // so that if PointerReg is null then the access reliably page faults. 375360784Sdim if (!(MI.mayLoadOrStore() && !MI.isPredicable() && 376327952Sdim -PageSize < Offset && Offset < PageSize)) 377321369Sdim return SR_Unsuitable; 378314564Sdim 379321369Sdim // Finally, check whether the current memory access aliases with previous one. 380321369Sdim for (auto *PrevMI : PrevInsts) { 381321369Sdim AliasResult AR = areMemoryOpsAliased(MI, PrevMI); 382321369Sdim if (AR == AR_WillAliasEverything) 383321369Sdim return SR_Impossible; 384321369Sdim if (AR == AR_MayAlias) 385321369Sdim return SR_Unsuitable; 386321369Sdim } 387321369Sdim return SR_Suitable; 388314564Sdim} 389314564Sdim 390321369Sdimbool ImplicitNullChecks::canHoistInst(MachineInstr *FaultingMI, 391321369Sdim unsigned PointerReg, 392321369Sdim ArrayRef<MachineInstr *> InstsSeenSoFar, 393321369Sdim MachineBasicBlock *NullSucc, 394321369Sdim MachineInstr *&Dependence) { 395314564Sdim auto DepResult = computeDependence(FaultingMI, InstsSeenSoFar); 396314564Sdim if (!DepResult.CanReorder) 397314564Sdim return false; 398314564Sdim 399314564Sdim if (!DepResult.PotentialDependence) { 400314564Sdim Dependence = nullptr; 401314564Sdim return true; 402314564Sdim } 403314564Sdim 404314564Sdim auto DependenceItr = *DepResult.PotentialDependence; 405314564Sdim auto *DependenceMI = *DependenceItr; 406314564Sdim 407314564Sdim // We don't want to reason about speculating loads. Note -- at this point 408314564Sdim // we should have already filtered out all of the other non-speculatable 409314564Sdim // things, like calls and stores. 410327952Sdim // We also do not want to hoist stores because it might change the memory 411327952Sdim // while the FaultingMI may result in faulting. 412314564Sdim assert(canHandle(DependenceMI) && "Should never have reached here!"); 413327952Sdim if (DependenceMI->mayLoadOrStore()) 414314564Sdim return false; 415314564Sdim 416314564Sdim for (auto &DependenceMO : DependenceMI->operands()) { 417314564Sdim if (!(DependenceMO.isReg() && DependenceMO.getReg())) 418314564Sdim continue; 419314564Sdim 420314564Sdim // Make sure that we won't clobber any live ins to the sibling block by 421314564Sdim // hoisting Dependency. For instance, we can't hoist INST to before the 422314564Sdim // null check (even if it safe, and does not violate any dependencies in 423314564Sdim // the non_null_block) if %rdx is live in to _null_block. 424314564Sdim // 425314564Sdim // test %rcx, %rcx 426314564Sdim // je _null_block 427314564Sdim // _non_null_block: 428327952Sdim // %rdx = INST 429314564Sdim // ... 430314564Sdim // 431314564Sdim // This restriction does not apply to the faulting load inst because in 432314564Sdim // case the pointer loaded from is in the null page, the load will not 433314564Sdim // semantically execute, and affect machine state. That is, if the load 434314564Sdim // was loading into %rax and it faults, the value of %rax should stay the 435314564Sdim // same as it would have been had the load not have executed and we'd have 436314564Sdim // branched to NullSucc directly. 437314564Sdim if (AnyAliasLiveIn(TRI, NullSucc, DependenceMO.getReg())) 438314564Sdim return false; 439314564Sdim 440314564Sdim // The Dependency can't be re-defining the base register -- then we won't 441314564Sdim // get the memory operation on the address we want. This is already 442314564Sdim // checked in \c IsSuitableMemoryOp. 443321369Sdim assert(!(DependenceMO.isDef() && 444321369Sdim TRI->regsOverlap(DependenceMO.getReg(), PointerReg)) && 445314564Sdim "Should have been checked before!"); 446314564Sdim } 447314564Sdim 448314564Sdim auto DepDepResult = 449314564Sdim computeDependence(DependenceMI, {InstsSeenSoFar.begin(), DependenceItr}); 450314564Sdim 451314564Sdim if (!DepDepResult.CanReorder || DepDepResult.PotentialDependence) 452314564Sdim return false; 453314564Sdim 454314564Sdim Dependence = DependenceMI; 455314564Sdim return true; 456314564Sdim} 457314564Sdim 458284677Sdim/// Analyze MBB to check if its terminating branch can be turned into an 459284677Sdim/// implicit null check. If yes, append a description of the said null check to 460284677Sdim/// NullCheckList and return true, else return false. 461284677Sdimbool ImplicitNullChecks::analyzeBlockForNullChecks( 462284677Sdim MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) { 463327952Sdim using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate; 464284677Sdim 465296417Sdim MDNode *BranchMD = nullptr; 466296417Sdim if (auto *BB = MBB.getBasicBlock()) 467296417Sdim BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit); 468296417Sdim 469285181Sdim if (!BranchMD) 470285181Sdim return false; 471285181Sdim 472284677Sdim MachineBranchPredicate MBP; 473284677Sdim 474309124Sdim if (TII->analyzeBranchPredicate(MBB, MBP, true)) 475284677Sdim return false; 476284677Sdim 477284677Sdim // Is the predicate comparing an integer to zero? 478284677Sdim if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 && 479284677Sdim (MBP.Predicate == MachineBranchPredicate::PRED_NE || 480284677Sdim MBP.Predicate == MachineBranchPredicate::PRED_EQ))) 481284677Sdim return false; 482284677Sdim 483284677Sdim // If we cannot erase the test instruction itself, then making the null check 484284677Sdim // implicit does not buy us much. 485284677Sdim if (!MBP.SingleUseCondition) 486284677Sdim return false; 487284677Sdim 488284677Sdim MachineBasicBlock *NotNullSucc, *NullSucc; 489284677Sdim 490284677Sdim if (MBP.Predicate == MachineBranchPredicate::PRED_NE) { 491284677Sdim NotNullSucc = MBP.TrueDest; 492284677Sdim NullSucc = MBP.FalseDest; 493284677Sdim } else { 494284677Sdim NotNullSucc = MBP.FalseDest; 495284677Sdim NullSucc = MBP.TrueDest; 496284677Sdim } 497284677Sdim 498284677Sdim // We handle the simplest case for now. We can potentially do better by using 499284677Sdim // the machine dominator tree. 500284677Sdim if (NotNullSucc->pred_size() != 1) 501284677Sdim return false; 502284677Sdim 503341825Sdim // To prevent the invalid transformation of the following code: 504341825Sdim // 505341825Sdim // mov %rax, %rcx 506341825Sdim // test %rax, %rax 507341825Sdim // %rax = ... 508341825Sdim // je throw_npe 509341825Sdim // mov(%rcx), %r9 510341825Sdim // mov(%rax), %r10 511341825Sdim // 512341825Sdim // into: 513341825Sdim // 514341825Sdim // mov %rax, %rcx 515341825Sdim // %rax = .... 516341825Sdim // faulting_load_op("movl (%rax), %r10", throw_npe) 517341825Sdim // mov(%rcx), %r9 518341825Sdim // 519341825Sdim // we must ensure that there are no instructions between the 'test' and 520341825Sdim // conditional jump that modify %rax. 521360784Sdim const Register PointerReg = MBP.LHS.getReg(); 522341825Sdim 523341825Sdim assert(MBP.ConditionDef->getParent() == &MBB && "Should be in basic block"); 524341825Sdim 525341825Sdim for (auto I = MBB.rbegin(); MBP.ConditionDef != &*I; ++I) 526341825Sdim if (I->modifiesRegister(PointerReg, TRI)) 527341825Sdim return false; 528341825Sdim 529284677Sdim // Starting with a code fragment like: 530284677Sdim // 531327952Sdim // test %rax, %rax 532284677Sdim // jne LblNotNull 533284677Sdim // 534284677Sdim // LblNull: 535284677Sdim // callq throw_NullPointerException 536284677Sdim // 537284677Sdim // LblNotNull: 538286684Sdim // Inst0 539286684Sdim // Inst1 540286684Sdim // ... 541327952Sdim // Def = Load (%rax + <offset>) 542284677Sdim // ... 543284677Sdim // 544284677Sdim // 545284677Sdim // we want to end up with 546284677Sdim // 547327952Sdim // Def = FaultingLoad (%rax + <offset>), LblNull 548284677Sdim // jmp LblNotNull ;; explicit or fallthrough 549284677Sdim // 550284677Sdim // LblNotNull: 551286684Sdim // Inst0 552286684Sdim // Inst1 553284677Sdim // ... 554284677Sdim // 555284677Sdim // LblNull: 556284677Sdim // callq throw_NullPointerException 557284677Sdim // 558296417Sdim // 559296417Sdim // To see why this is legal, consider the two possibilities: 560296417Sdim // 561327952Sdim // 1. %rax is null: since we constrain <offset> to be less than PageSize, the 562296417Sdim // load instruction dereferences the null page, causing a segmentation 563296417Sdim // fault. 564296417Sdim // 565327952Sdim // 2. %rax is not null: in this case we know that the load cannot fault, as 566296417Sdim // otherwise the load would've faulted in the original program too and the 567296417Sdim // original program would've been undefined. 568296417Sdim // 569296417Sdim // This reasoning cannot be extended to justify hoisting through arbitrary 570296417Sdim // control flow. For instance, in the example below (in pseudo-C) 571296417Sdim // 572296417Sdim // if (ptr == null) { throw_npe(); unreachable; } 573296417Sdim // if (some_cond) { return 42; } 574296417Sdim // v = ptr->field; // LD 575296417Sdim // ... 576296417Sdim // 577296417Sdim // we cannot (without code duplication) use the load marked "LD" to null check 578296417Sdim // ptr -- clause (2) above does not apply in this case. In the above program 579296417Sdim // the safety of ptr->field can be dependent on some_cond; and, for instance, 580296417Sdim // ptr could be some non-null invalid reference that never gets loaded from 581296417Sdim // because some_cond is always true. 582284677Sdim 583314564Sdim SmallVector<MachineInstr *, 8> InstsSeenSoFar; 584286684Sdim 585314564Sdim for (auto &MI : *NotNullSucc) { 586314564Sdim if (!canHandle(&MI) || InstsSeenSoFar.size() >= MaxInstsToConsider) 587314564Sdim return false; 588309124Sdim 589314564Sdim MachineInstr *Dependence; 590321369Sdim SuitabilityResult SR = isSuitableMemoryOp(MI, PointerReg, InstsSeenSoFar); 591321369Sdim if (SR == SR_Impossible) 592321369Sdim return false; 593321369Sdim if (SR == SR_Suitable && 594321369Sdim canHoistInst(&MI, PointerReg, InstsSeenSoFar, NullSucc, Dependence)) { 595314564Sdim NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc, 596314564Sdim NullSucc, Dependence); 597314564Sdim return true; 598314564Sdim } 599309124Sdim 600321369Sdim // If MI re-defines the PointerReg then we cannot move further. 601327952Sdim if (llvm::any_of(MI.operands(), [&](MachineOperand &MO) { 602321369Sdim return MO.isReg() && MO.getReg() && MO.isDef() && 603321369Sdim TRI->regsOverlap(MO.getReg(), PointerReg); 604321369Sdim })) 605321369Sdim return false; 606314564Sdim InstsSeenSoFar.push_back(&MI); 607286684Sdim } 608286684Sdim 609284677Sdim return false; 610284677Sdim} 611284677Sdim 612321369Sdim/// Wrap a machine instruction, MI, into a FAULTING machine instruction. 613321369Sdim/// The FAULTING instruction does the same load/store as MI 614321369Sdim/// (defining the same register), and branches to HandlerMBB if the mem access 615321369Sdim/// faults. The FAULTING instruction is inserted at the end of MBB. 616321369SdimMachineInstr *ImplicitNullChecks::insertFaultingInstr( 617321369Sdim MachineInstr *MI, MachineBasicBlock *MBB, MachineBasicBlock *HandlerMBB) { 618296417Sdim const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for 619296417Sdim // all targets. 620296417Sdim 621284677Sdim DebugLoc DL; 622321369Sdim unsigned NumDefs = MI->getDesc().getNumDefs(); 623296417Sdim assert(NumDefs <= 1 && "other cases unhandled!"); 624284677Sdim 625296417Sdim unsigned DefReg = NoRegister; 626296417Sdim if (NumDefs != 0) { 627341825Sdim DefReg = MI->getOperand(0).getReg(); 628341825Sdim assert(NumDefs == 1 && "expected exactly one def!"); 629296417Sdim } 630284677Sdim 631321369Sdim FaultMaps::FaultKind FK; 632321369Sdim if (MI->mayLoad()) 633321369Sdim FK = 634321369Sdim MI->mayStore() ? FaultMaps::FaultingLoadStore : FaultMaps::FaultingLoad; 635321369Sdim else 636321369Sdim FK = FaultMaps::FaultingStore; 637321369Sdim 638321369Sdim auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_OP), DefReg) 639321369Sdim .addImm(FK) 640309124Sdim .addMBB(HandlerMBB) 641321369Sdim .addImm(MI->getOpcode()); 642284677Sdim 643321369Sdim for (auto &MO : MI->uses()) { 644321369Sdim if (MO.isReg()) { 645321369Sdim MachineOperand NewMO = MO; 646321369Sdim if (MO.isUse()) { 647321369Sdim NewMO.setIsKill(false); 648321369Sdim } else { 649321369Sdim assert(MO.isDef() && "Expected def or use"); 650321369Sdim NewMO.setIsDead(false); 651321369Sdim } 652321369Sdim MIB.add(NewMO); 653321369Sdim } else { 654321369Sdim MIB.add(MO); 655321369Sdim } 656321369Sdim } 657284677Sdim 658344779Sdim MIB.setMemRefs(MI->memoperands()); 659284677Sdim 660284677Sdim return MIB; 661284677Sdim} 662284677Sdim 663284677Sdim/// Rewrite the null checks in NullCheckList into implicit null checks. 664284677Sdimvoid ImplicitNullChecks::rewriteNullChecks( 665284677Sdim ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) { 666284677Sdim DebugLoc DL; 667284677Sdim 668284677Sdim for (auto &NC : NullCheckList) { 669284677Sdim // Remove the conditional branch dependent on the null check. 670314564Sdim unsigned BranchesRemoved = TII->removeBranch(*NC.getCheckBlock()); 671284677Sdim (void)BranchesRemoved; 672284677Sdim assert(BranchesRemoved > 0 && "expected at least one branch!"); 673284677Sdim 674309124Sdim if (auto *DepMI = NC.getOnlyDependency()) { 675309124Sdim DepMI->removeFromParent(); 676309124Sdim NC.getCheckBlock()->insert(NC.getCheckBlock()->end(), DepMI); 677309124Sdim } 678309124Sdim 679321369Sdim // Insert a faulting instruction where the conditional branch was 680321369Sdim // originally. We check earlier ensures that this bit of code motion 681321369Sdim // is legal. We do not touch the successors list for any basic block 682321369Sdim // since we haven't changed control flow, we've just made it implicit. 683321369Sdim MachineInstr *FaultingInstr = insertFaultingInstr( 684309124Sdim NC.getMemOperation(), NC.getCheckBlock(), NC.getNullSucc()); 685309124Sdim // Now the values defined by MemOperation, if any, are live-in of 686309124Sdim // the block of MemOperation. 687321369Sdim // The original operation may define implicit-defs alongside 688321369Sdim // the value. 689309124Sdim MachineBasicBlock *MBB = NC.getMemOperation()->getParent(); 690321369Sdim for (const MachineOperand &MO : FaultingInstr->operands()) { 691309124Sdim if (!MO.isReg() || !MO.isDef()) 692309124Sdim continue; 693360784Sdim Register Reg = MO.getReg(); 694309124Sdim if (!Reg || MBB->isLiveIn(Reg)) 695309124Sdim continue; 696309124Sdim MBB->addLiveIn(Reg); 697309124Sdim } 698284677Sdim 699309124Sdim if (auto *DepMI = NC.getOnlyDependency()) { 700309124Sdim for (auto &MO : DepMI->operands()) { 701360784Sdim if (!MO.isReg() || !MO.getReg() || !MO.isDef() || MO.isDead()) 702309124Sdim continue; 703309124Sdim if (!NC.getNotNullSucc()->isLiveIn(MO.getReg())) 704309124Sdim NC.getNotNullSucc()->addLiveIn(MO.getReg()); 705309124Sdim } 706309124Sdim } 707309124Sdim 708309124Sdim NC.getMemOperation()->eraseFromParent(); 709309124Sdim NC.getCheckOperation()->eraseFromParent(); 710309124Sdim 711284677Sdim // Insert an *unconditional* branch to not-null successor. 712314564Sdim TII->insertBranch(*NC.getCheckBlock(), NC.getNotNullSucc(), nullptr, 713309124Sdim /*Cond=*/None, DL); 714284677Sdim 715286684Sdim NumImplicitNullChecks++; 716284677Sdim } 717284677Sdim} 718284677Sdim 719327952Sdimchar ImplicitNullChecks::ID = 0; 720314564Sdim 721284677Sdimchar &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID; 722327952Sdim 723321369SdimINITIALIZE_PASS_BEGIN(ImplicitNullChecks, DEBUG_TYPE, 724284677Sdim "Implicit null checks", false, false) 725309124SdimINITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 726321369SdimINITIALIZE_PASS_END(ImplicitNullChecks, DEBUG_TYPE, 727284677Sdim "Implicit null checks", false, false) 728