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 47 using namespace llvm; 48 49 static 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 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 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 102 public: 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. 117 class HazardDetector { 118 DenseSet<unsigned> RegDefs; 119 DenseSet<unsigned> RegUses; 120 const TargetRegisterInfo &TRI; 121 bool hasSeenClobber; 122 123 public: 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 152 void 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 180 bool 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 205 bool 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. 224 bool 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. 349 MachineInstr *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. 379 void 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 411 char ImplicitNullChecks::ID = 0; 412 char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID; 413 INITIALIZE_PASS_BEGIN(ImplicitNullChecks, "implicit-null-checks", 414 "Implicit null checks", false, false) 415 INITIALIZE_PASS_END(ImplicitNullChecks, "implicit-null-checks", 416 "Implicit null checks", false, false) 417