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/Analysis/AliasAnalysis.h" 32 #include "llvm/CodeGen/Passes.h" 33 #include "llvm/CodeGen/MachineFunction.h" 34 #include "llvm/CodeGen/MachineMemOperand.h" 35 #include "llvm/CodeGen/MachineOperand.h" 36 #include "llvm/CodeGen/MachineFunctionPass.h" 37 #include "llvm/CodeGen/MachineInstrBuilder.h" 38 #include "llvm/CodeGen/MachineRegisterInfo.h" 39 #include "llvm/CodeGen/MachineModuleInfo.h" 40 #include "llvm/IR/BasicBlock.h" 41 #include "llvm/IR/Instruction.h" 42 #include "llvm/IR/LLVMContext.h" 43 #include "llvm/Support/CommandLine.h" 44 #include "llvm/Support/Debug.h" 45 #include "llvm/Target/TargetSubtargetInfo.h" 46 #include "llvm/Target/TargetInstrInfo.h" 47 48 using namespace llvm; 49 50 static cl::opt<int> PageSize("imp-null-check-page-size", 51 cl::desc("The page size of the target in bytes"), 52 cl::init(4096)); 53 54 #define DEBUG_TYPE "implicit-null-checks" 55 56 STATISTIC(NumImplicitNullChecks, 57 "Number of explicit null checks made implicit"); 58 59 namespace { 60 61 class ImplicitNullChecks : public MachineFunctionPass { 62 /// Represents one null check that can be made implicit. 63 class 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 // If this is non-null, then MemOperation has a dependency on on this 80 // instruction; and it needs to be hoisted to execute before MemOperation. 81 MachineInstr *OnlyDependency; 82 83 public: 84 explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation, 85 MachineBasicBlock *checkBlock, 86 MachineBasicBlock *notNullSucc, 87 MachineBasicBlock *nullSucc, 88 MachineInstr *onlyDependency) 89 : MemOperation(memOperation), CheckOperation(checkOperation), 90 CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc), 91 OnlyDependency(onlyDependency) {} 92 93 MachineInstr *getMemOperation() const { return MemOperation; } 94 95 MachineInstr *getCheckOperation() const { return CheckOperation; } 96 97 MachineBasicBlock *getCheckBlock() const { return CheckBlock; } 98 99 MachineBasicBlock *getNotNullSucc() const { return NotNullSucc; } 100 101 MachineBasicBlock *getNullSucc() const { return NullSucc; } 102 103 MachineInstr *getOnlyDependency() const { return OnlyDependency; } 104 }; 105 106 const TargetInstrInfo *TII = nullptr; 107 const TargetRegisterInfo *TRI = nullptr; 108 AliasAnalysis *AA = nullptr; 109 MachineModuleInfo *MMI = nullptr; 110 111 bool analyzeBlockForNullChecks(MachineBasicBlock &MBB, 112 SmallVectorImpl<NullCheck> &NullCheckList); 113 MachineInstr *insertFaultingLoad(MachineInstr *LoadMI, MachineBasicBlock *MBB, 114 MachineBasicBlock *HandlerMBB); 115 void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList); 116 117 public: 118 static char ID; 119 120 ImplicitNullChecks() : MachineFunctionPass(ID) { 121 initializeImplicitNullChecksPass(*PassRegistry::getPassRegistry()); 122 } 123 124 bool runOnMachineFunction(MachineFunction &MF) override; 125 void getAnalysisUsage(AnalysisUsage &AU) const override { 126 AU.addRequired<AAResultsWrapperPass>(); 127 MachineFunctionPass::getAnalysisUsage(AU); 128 } 129 130 MachineFunctionProperties getRequiredProperties() const override { 131 return MachineFunctionProperties().set( 132 MachineFunctionProperties::Property::AllVRegsAllocated); 133 } 134 }; 135 136 /// \brief Detect re-ordering hazards and dependencies. 137 /// 138 /// This class keeps track of defs and uses, and can be queried if a given 139 /// machine instruction can be re-ordered from after the machine instructions 140 /// seen so far to before them. 141 class HazardDetector { 142 static MachineInstr *getUnknownMI() { 143 return DenseMapInfo<MachineInstr *>::getTombstoneKey(); 144 } 145 146 // Maps physical registers to the instruction defining them. If there has 147 // been more than one def of an specific register, that register is mapped to 148 // getUnknownMI(). 149 DenseMap<unsigned, MachineInstr *> RegDefs; 150 DenseSet<unsigned> RegUses; 151 const TargetRegisterInfo &TRI; 152 bool hasSeenClobber; 153 AliasAnalysis &AA; 154 155 public: 156 explicit HazardDetector(const TargetRegisterInfo &TRI, AliasAnalysis &AA) 157 : TRI(TRI), hasSeenClobber(false), AA(AA) {} 158 159 /// \brief Make a note of \p MI for later queries to isSafeToHoist. 160 /// 161 /// May clobber this HazardDetector instance. \see isClobbered. 162 void rememberInstruction(MachineInstr *MI); 163 164 /// \brief Return true if it is safe to hoist \p MI from after all the 165 /// instructions seen so far (via rememberInstruction) to before it. If \p MI 166 /// has one and only one transitive dependency, set \p Dependency to that 167 /// instruction. If there are more dependencies, return false. 168 bool isSafeToHoist(MachineInstr *MI, MachineInstr *&Dependency); 169 170 /// \brief Return true if this instance of HazardDetector has been clobbered 171 /// (i.e. has no more useful information). 172 /// 173 /// A HazardDetecter is clobbered when it sees a construct it cannot 174 /// understand, and it would have to return a conservative answer for all 175 /// future queries. Having a separate clobbered state lets the client code 176 /// bail early, without making queries about all of the future instructions 177 /// (which would have returned the most conservative answer anyway). 178 /// 179 /// Calling rememberInstruction or isSafeToHoist on a clobbered HazardDetector 180 /// is an error. 181 bool isClobbered() { return hasSeenClobber; } 182 }; 183 } 184 185 186 void HazardDetector::rememberInstruction(MachineInstr *MI) { 187 assert(!isClobbered() && 188 "Don't add instructions to a clobbered hazard detector"); 189 190 if (MI->mayStore() || MI->hasUnmodeledSideEffects()) { 191 hasSeenClobber = true; 192 return; 193 } 194 195 for (auto *MMO : MI->memoperands()) { 196 // Right now we don't want to worry about LLVM's memory model. 197 if (!MMO->isUnordered()) { 198 hasSeenClobber = true; 199 return; 200 } 201 } 202 203 for (auto &MO : MI->operands()) { 204 if (!MO.isReg() || !MO.getReg()) 205 continue; 206 207 if (MO.isDef()) { 208 auto It = RegDefs.find(MO.getReg()); 209 if (It == RegDefs.end()) 210 RegDefs.insert({MO.getReg(), MI}); 211 else { 212 assert(It->second && "Found null MI?"); 213 It->second = getUnknownMI(); 214 } 215 } else 216 RegUses.insert(MO.getReg()); 217 } 218 } 219 220 bool HazardDetector::isSafeToHoist(MachineInstr *MI, 221 MachineInstr *&Dependency) { 222 assert(!isClobbered() && "isSafeToHoist cannot do anything useful!"); 223 Dependency = nullptr; 224 225 // Right now we don't want to worry about LLVM's memory model. This can be 226 // made more precise later. 227 for (auto *MMO : MI->memoperands()) 228 if (!MMO->isUnordered()) 229 return false; 230 231 for (auto &MO : MI->operands()) { 232 if (MO.isReg() && MO.getReg()) { 233 for (auto &RegDef : RegDefs) { 234 unsigned Reg = RegDef.first; 235 MachineInstr *MI = RegDef.second; 236 if (!TRI.regsOverlap(Reg, MO.getReg())) 237 continue; 238 239 // We found a write-after-write or read-after-write, see if the 240 // instruction causing this dependency can be hoisted too. 241 242 if (MI == getUnknownMI()) 243 // We don't have precise dependency information. 244 return false; 245 246 if (Dependency) { 247 if (Dependency == MI) 248 continue; 249 // We already have one dependency, and we can track only one. 250 return false; 251 } 252 253 // Now check if MI is actually a dependency that can be hoisted. 254 255 // We don't want to track transitive dependencies. We already know that 256 // MI is the only instruction that defines Reg, but we need to be sure 257 // that it does not use any registers that have been defined (trivially 258 // checked below by ensuring that there are no register uses), and that 259 // it is the only def for every register it defines (otherwise we could 260 // violate a write after write hazard). 261 auto IsMIOperandSafe = [&](MachineOperand &MO) { 262 if (!MO.isReg() || !MO.getReg()) 263 return true; 264 if (MO.isUse()) 265 return false; 266 assert((!MO.isDef() || RegDefs.count(MO.getReg())) && 267 "All defs must be tracked in RegDefs by now!"); 268 return !MO.isDef() || RegDefs.find(MO.getReg())->second == MI; 269 }; 270 271 if (!all_of(MI->operands(), IsMIOperandSafe)) 272 return false; 273 274 // Now check for speculation safety: 275 bool SawStore = true; 276 if (!MI->isSafeToMove(&AA, SawStore) || MI->mayLoad()) 277 return false; 278 279 Dependency = MI; 280 } 281 282 if (MO.isDef()) 283 for (unsigned Reg : RegUses) 284 if (TRI.regsOverlap(Reg, MO.getReg())) 285 return false; // We found a write-after-read 286 } 287 } 288 289 return true; 290 } 291 292 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) { 293 TII = MF.getSubtarget().getInstrInfo(); 294 TRI = MF.getRegInfo().getTargetRegisterInfo(); 295 MMI = &MF.getMMI(); 296 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 297 298 SmallVector<NullCheck, 16> NullCheckList; 299 300 for (auto &MBB : MF) 301 analyzeBlockForNullChecks(MBB, NullCheckList); 302 303 if (!NullCheckList.empty()) 304 rewriteNullChecks(NullCheckList); 305 306 return !NullCheckList.empty(); 307 } 308 309 // Return true if any register aliasing \p Reg is live-in into \p MBB. 310 static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI, 311 MachineBasicBlock *MBB, unsigned Reg) { 312 for (MCRegAliasIterator AR(Reg, TRI, /*IncludeSelf*/ true); AR.isValid(); 313 ++AR) 314 if (MBB->isLiveIn(*AR)) 315 return true; 316 return false; 317 } 318 319 /// Analyze MBB to check if its terminating branch can be turned into an 320 /// implicit null check. If yes, append a description of the said null check to 321 /// NullCheckList and return true, else return false. 322 bool ImplicitNullChecks::analyzeBlockForNullChecks( 323 MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) { 324 typedef TargetInstrInfo::MachineBranchPredicate MachineBranchPredicate; 325 326 MDNode *BranchMD = nullptr; 327 if (auto *BB = MBB.getBasicBlock()) 328 BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit); 329 330 if (!BranchMD) 331 return false; 332 333 MachineBranchPredicate MBP; 334 335 if (TII->analyzeBranchPredicate(MBB, MBP, true)) 336 return false; 337 338 // Is the predicate comparing an integer to zero? 339 if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 && 340 (MBP.Predicate == MachineBranchPredicate::PRED_NE || 341 MBP.Predicate == MachineBranchPredicate::PRED_EQ))) 342 return false; 343 344 // If we cannot erase the test instruction itself, then making the null check 345 // implicit does not buy us much. 346 if (!MBP.SingleUseCondition) 347 return false; 348 349 MachineBasicBlock *NotNullSucc, *NullSucc; 350 351 if (MBP.Predicate == MachineBranchPredicate::PRED_NE) { 352 NotNullSucc = MBP.TrueDest; 353 NullSucc = MBP.FalseDest; 354 } else { 355 NotNullSucc = MBP.FalseDest; 356 NullSucc = MBP.TrueDest; 357 } 358 359 // We handle the simplest case for now. We can potentially do better by using 360 // the machine dominator tree. 361 if (NotNullSucc->pred_size() != 1) 362 return false; 363 364 // Starting with a code fragment like: 365 // 366 // test %RAX, %RAX 367 // jne LblNotNull 368 // 369 // LblNull: 370 // callq throw_NullPointerException 371 // 372 // LblNotNull: 373 // Inst0 374 // Inst1 375 // ... 376 // Def = Load (%RAX + <offset>) 377 // ... 378 // 379 // 380 // we want to end up with 381 // 382 // Def = FaultingLoad (%RAX + <offset>), LblNull 383 // jmp LblNotNull ;; explicit or fallthrough 384 // 385 // LblNotNull: 386 // Inst0 387 // Inst1 388 // ... 389 // 390 // LblNull: 391 // callq throw_NullPointerException 392 // 393 // 394 // To see why this is legal, consider the two possibilities: 395 // 396 // 1. %RAX is null: since we constrain <offset> to be less than PageSize, the 397 // load instruction dereferences the null page, causing a segmentation 398 // fault. 399 // 400 // 2. %RAX is not null: in this case we know that the load cannot fault, as 401 // otherwise the load would've faulted in the original program too and the 402 // original program would've been undefined. 403 // 404 // This reasoning cannot be extended to justify hoisting through arbitrary 405 // control flow. For instance, in the example below (in pseudo-C) 406 // 407 // if (ptr == null) { throw_npe(); unreachable; } 408 // if (some_cond) { return 42; } 409 // v = ptr->field; // LD 410 // ... 411 // 412 // we cannot (without code duplication) use the load marked "LD" to null check 413 // ptr -- clause (2) above does not apply in this case. In the above program 414 // the safety of ptr->field can be dependent on some_cond; and, for instance, 415 // ptr could be some non-null invalid reference that never gets loaded from 416 // because some_cond is always true. 417 418 unsigned PointerReg = MBP.LHS.getReg(); 419 420 HazardDetector HD(*TRI, *AA); 421 422 for (auto MII = NotNullSucc->begin(), MIE = NotNullSucc->end(); MII != MIE; 423 ++MII) { 424 MachineInstr &MI = *MII; 425 unsigned BaseReg; 426 int64_t Offset; 427 MachineInstr *Dependency = nullptr; 428 if (TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI)) 429 if (MI.mayLoad() && !MI.isPredicable() && BaseReg == PointerReg && 430 Offset < PageSize && MI.getDesc().getNumDefs() <= 1 && 431 HD.isSafeToHoist(&MI, Dependency)) { 432 433 auto DependencyOperandIsOk = [&](MachineOperand &MO) { 434 assert(!(MO.isReg() && MO.isUse()) && 435 "No transitive dependendencies please!"); 436 if (!MO.isReg() || !MO.getReg() || !MO.isDef()) 437 return true; 438 439 // Make sure that we won't clobber any live ins to the sibling block 440 // by hoisting Dependency. For instance, we can't hoist INST to 441 // before the null check (even if it safe, and does not violate any 442 // dependencies in the non_null_block) if %rdx is live in to 443 // _null_block. 444 // 445 // test %rcx, %rcx 446 // je _null_block 447 // _non_null_block: 448 // %rdx<def> = INST 449 // ... 450 if (AnyAliasLiveIn(TRI, NullSucc, MO.getReg())) 451 return false; 452 453 // Make sure Dependency isn't re-defining the base register. Then we 454 // won't get the memory operation on the address we want. 455 if (TRI->regsOverlap(MO.getReg(), BaseReg)) 456 return false; 457 458 return true; 459 }; 460 461 bool DependencyOperandsAreOk = 462 !Dependency || 463 all_of(Dependency->operands(), DependencyOperandIsOk); 464 465 if (DependencyOperandsAreOk) { 466 NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc, 467 NullSucc, Dependency); 468 return true; 469 } 470 } 471 472 HD.rememberInstruction(&MI); 473 if (HD.isClobbered()) 474 return false; 475 } 476 477 return false; 478 } 479 480 /// Wrap a machine load instruction, LoadMI, into a FAULTING_LOAD_OP machine 481 /// instruction. The FAULTING_LOAD_OP instruction does the same load as LoadMI 482 /// (defining the same register), and branches to HandlerMBB if the load 483 /// faults. The FAULTING_LOAD_OP instruction is inserted at the end of MBB. 484 MachineInstr * 485 ImplicitNullChecks::insertFaultingLoad(MachineInstr *LoadMI, 486 MachineBasicBlock *MBB, 487 MachineBasicBlock *HandlerMBB) { 488 const unsigned NoRegister = 0; // Guaranteed to be the NoRegister value for 489 // all targets. 490 491 DebugLoc DL; 492 unsigned NumDefs = LoadMI->getDesc().getNumDefs(); 493 assert(NumDefs <= 1 && "other cases unhandled!"); 494 495 unsigned DefReg = NoRegister; 496 if (NumDefs != 0) { 497 DefReg = LoadMI->defs().begin()->getReg(); 498 assert(std::distance(LoadMI->defs().begin(), LoadMI->defs().end()) == 1 && 499 "expected exactly one def!"); 500 } 501 502 auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_LOAD_OP), DefReg) 503 .addMBB(HandlerMBB) 504 .addImm(LoadMI->getOpcode()); 505 506 for (auto &MO : LoadMI->uses()) 507 MIB.addOperand(MO); 508 509 MIB.setMemRefs(LoadMI->memoperands_begin(), LoadMI->memoperands_end()); 510 511 return MIB; 512 } 513 514 /// Rewrite the null checks in NullCheckList into implicit null checks. 515 void ImplicitNullChecks::rewriteNullChecks( 516 ArrayRef<ImplicitNullChecks::NullCheck> NullCheckList) { 517 DebugLoc DL; 518 519 for (auto &NC : NullCheckList) { 520 // Remove the conditional branch dependent on the null check. 521 unsigned BranchesRemoved = TII->RemoveBranch(*NC.getCheckBlock()); 522 (void)BranchesRemoved; 523 assert(BranchesRemoved > 0 && "expected at least one branch!"); 524 525 if (auto *DepMI = NC.getOnlyDependency()) { 526 DepMI->removeFromParent(); 527 NC.getCheckBlock()->insert(NC.getCheckBlock()->end(), DepMI); 528 } 529 530 // Insert a faulting load where the conditional branch was originally. We 531 // check earlier ensures that this bit of code motion is legal. We do not 532 // touch the successors list for any basic block since we haven't changed 533 // control flow, we've just made it implicit. 534 MachineInstr *FaultingLoad = insertFaultingLoad( 535 NC.getMemOperation(), NC.getCheckBlock(), NC.getNullSucc()); 536 // Now the values defined by MemOperation, if any, are live-in of 537 // the block of MemOperation. 538 // The original load operation may define implicit-defs alongside 539 // the loaded value. 540 MachineBasicBlock *MBB = NC.getMemOperation()->getParent(); 541 for (const MachineOperand &MO : FaultingLoad->operands()) { 542 if (!MO.isReg() || !MO.isDef()) 543 continue; 544 unsigned Reg = MO.getReg(); 545 if (!Reg || MBB->isLiveIn(Reg)) 546 continue; 547 MBB->addLiveIn(Reg); 548 } 549 550 if (auto *DepMI = NC.getOnlyDependency()) { 551 for (auto &MO : DepMI->operands()) { 552 if (!MO.isReg() || !MO.getReg() || !MO.isDef()) 553 continue; 554 if (!NC.getNotNullSucc()->isLiveIn(MO.getReg())) 555 NC.getNotNullSucc()->addLiveIn(MO.getReg()); 556 } 557 } 558 559 NC.getMemOperation()->eraseFromParent(); 560 NC.getCheckOperation()->eraseFromParent(); 561 562 // Insert an *unconditional* branch to not-null successor. 563 TII->InsertBranch(*NC.getCheckBlock(), NC.getNotNullSucc(), nullptr, 564 /*Cond=*/None, DL); 565 566 NumImplicitNullChecks++; 567 } 568 } 569 570 char ImplicitNullChecks::ID = 0; 571 char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID; 572 INITIALIZE_PASS_BEGIN(ImplicitNullChecks, "implicit-null-checks", 573 "Implicit null checks", false, false) 574 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 575 INITIALIZE_PASS_END(ImplicitNullChecks, "implicit-null-checks", 576 "Implicit null checks", false, false) 577