diff options
Diffstat (limited to 'contrib/llvm/lib/CodeGen/ImplicitNullChecks.cpp')
| -rw-r--r-- | contrib/llvm/lib/CodeGen/ImplicitNullChecks.cpp | 401 |
1 files changed, 210 insertions, 191 deletions
diff --git a/contrib/llvm/lib/CodeGen/ImplicitNullChecks.cpp b/contrib/llvm/lib/CodeGen/ImplicitNullChecks.cpp index 31d6bd0..9588dfb 100644 --- a/contrib/llvm/lib/CodeGen/ImplicitNullChecks.cpp +++ b/contrib/llvm/lib/CodeGen/ImplicitNullChecks.cpp @@ -51,6 +51,12 @@ static cl::opt<int> PageSize("imp-null-check-page-size", cl::desc("The page size of the target in bytes"), cl::init(4096)); +static cl::opt<unsigned> MaxInstsToConsider( + "imp-null-max-insts-to-consider", + cl::desc("The max number of instructions to consider hoisting loads over " + "(the algorithm is quadratic over this number)"), + cl::init(8)); + #define DEBUG_TYPE "implicit-null-checks" STATISTIC(NumImplicitNullChecks, @@ -59,6 +65,44 @@ STATISTIC(NumImplicitNullChecks, namespace { class ImplicitNullChecks : public MachineFunctionPass { + /// Return true if \c computeDependence can process \p MI. + static bool canHandle(const MachineInstr *MI); + + /// Helper function for \c computeDependence. Return true if \p A + /// and \p B do not have any dependences between them, and can be + /// re-ordered without changing program semantics. + bool canReorder(const MachineInstr *A, const MachineInstr *B); + + /// A data type for representing the result computed by \c + /// computeDependence. States whether it is okay to reorder the + /// instruction passed to \c computeDependence with at most one + /// depednency. + struct DependenceResult { + /// Can we actually re-order \p MI with \p Insts (see \c + /// computeDependence). + bool CanReorder; + + /// If non-None, then an instruction in \p Insts that also must be + /// hoisted. + Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence; + + /*implicit*/ DependenceResult( + bool CanReorder, + Optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence) + : CanReorder(CanReorder), PotentialDependence(PotentialDependence) { + assert((!PotentialDependence || CanReorder) && + "!CanReorder && PotentialDependence.hasValue() not allowed!"); + } + }; + + /// Compute a result for the following question: can \p MI be + /// re-ordered from after \p Insts to before it. + /// + /// \c canHandle should return true for all instructions in \p + /// Insts. + DependenceResult computeDependence(const MachineInstr *MI, + ArrayRef<MachineInstr *> Insts); + /// Represents one null check that can be made implicit. class NullCheck { // The memory operation the null check can be folded into. @@ -114,6 +158,19 @@ class ImplicitNullChecks : public MachineFunctionPass { MachineBasicBlock *HandlerMBB); void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList); + /// Is \p MI a memory operation that can be used to implicitly null check the + /// value in \p PointerReg? \p PrevInsts is the set of instruction seen since + /// the explicit null check on \p PointerReg. + bool isSuitableMemoryOp(MachineInstr &MI, unsigned PointerReg, + ArrayRef<MachineInstr *> PrevInsts); + + /// Return true if \p FaultingMI can be hoisted from after the the + /// instructions in \p InstsSeenSoFar to before them. Set \p Dependence to a + /// non-null value if we also need to (and legally can) hoist a depedency. + bool canHoistLoadInst(MachineInstr *FaultingMI, unsigned PointerReg, + ArrayRef<MachineInstr *> InstsSeenSoFar, + MachineBasicBlock *NullSucc, MachineInstr *&Dependence); + public: static char ID; @@ -129,160 +186,70 @@ public: MachineFunctionProperties getRequiredProperties() const override { return MachineFunctionProperties().set( - MachineFunctionProperties::Property::AllVRegsAllocated); + MachineFunctionProperties::Property::NoVRegs); } }; -/// \brief Detect re-ordering hazards and dependencies. -/// -/// This class keeps track of defs and uses, and can be queried if a given -/// machine instruction can be re-ordered from after the machine instructions -/// seen so far to before them. -class HazardDetector { - static MachineInstr *getUnknownMI() { - return DenseMapInfo<MachineInstr *>::getTombstoneKey(); - } - - // Maps physical registers to the instruction defining them. If there has - // been more than one def of an specific register, that register is mapped to - // getUnknownMI(). - DenseMap<unsigned, MachineInstr *> RegDefs; - DenseSet<unsigned> RegUses; - const TargetRegisterInfo &TRI; - bool hasSeenClobber; - AliasAnalysis &AA; - -public: - explicit HazardDetector(const TargetRegisterInfo &TRI, AliasAnalysis &AA) - : TRI(TRI), hasSeenClobber(false), AA(AA) {} +} - /// \brief Make a note of \p MI for later queries to isSafeToHoist. - /// - /// May clobber this HazardDetector instance. \see isClobbered. - void rememberInstruction(MachineInstr *MI); +bool ImplicitNullChecks::canHandle(const MachineInstr *MI) { + if (MI->isCall() || MI->mayStore() || MI->hasUnmodeledSideEffects()) + return false; + auto IsRegMask = [](const MachineOperand &MO) { return MO.isRegMask(); }; + (void)IsRegMask; - /// \brief Return true if it is safe to hoist \p MI from after all the - /// instructions seen so far (via rememberInstruction) to before it. If \p MI - /// has one and only one transitive dependency, set \p Dependency to that - /// instruction. If there are more dependencies, return false. - bool isSafeToHoist(MachineInstr *MI, MachineInstr *&Dependency); + assert(!llvm::any_of(MI->operands(), IsRegMask) && + "Calls were filtered out above!"); - /// \brief Return true if this instance of HazardDetector has been clobbered - /// (i.e. has no more useful information). - /// - /// A HazardDetecter is clobbered when it sees a construct it cannot - /// understand, and it would have to return a conservative answer for all - /// future queries. Having a separate clobbered state lets the client code - /// bail early, without making queries about all of the future instructions - /// (which would have returned the most conservative answer anyway). - /// - /// Calling rememberInstruction or isSafeToHoist on a clobbered HazardDetector - /// is an error. - bool isClobbered() { return hasSeenClobber; } -}; + auto IsUnordered = [](MachineMemOperand *MMO) { return MMO->isUnordered(); }; + return llvm::all_of(MI->memoperands(), IsUnordered); } +ImplicitNullChecks::DependenceResult +ImplicitNullChecks::computeDependence(const MachineInstr *MI, + ArrayRef<MachineInstr *> Block) { + assert(llvm::all_of(Block, canHandle) && "Check this first!"); + assert(!llvm::is_contained(Block, MI) && "Block must be exclusive of MI!"); -void HazardDetector::rememberInstruction(MachineInstr *MI) { - assert(!isClobbered() && - "Don't add instructions to a clobbered hazard detector"); + Optional<ArrayRef<MachineInstr *>::iterator> Dep; - if (MI->mayStore() || MI->hasUnmodeledSideEffects()) { - hasSeenClobber = true; - return; - } + for (auto I = Block.begin(), E = Block.end(); I != E; ++I) { + if (canReorder(*I, MI)) + continue; - for (auto *MMO : MI->memoperands()) { - // Right now we don't want to worry about LLVM's memory model. - if (!MMO->isUnordered()) { - hasSeenClobber = true; - return; + if (Dep == None) { + // Found one possible dependency, keep track of it. + Dep = I; + } else { + // We found two dependencies, so bail out. + return {false, None}; } } - for (auto &MO : MI->operands()) { - if (!MO.isReg() || !MO.getReg()) - continue; - - if (MO.isDef()) { - auto It = RegDefs.find(MO.getReg()); - if (It == RegDefs.end()) - RegDefs.insert({MO.getReg(), MI}); - else { - assert(It->second && "Found null MI?"); - It->second = getUnknownMI(); - } - } else - RegUses.insert(MO.getReg()); - } + return {true, Dep}; } -bool HazardDetector::isSafeToHoist(MachineInstr *MI, - MachineInstr *&Dependency) { - assert(!isClobbered() && "isSafeToHoist cannot do anything useful!"); - Dependency = nullptr; +bool ImplicitNullChecks::canReorder(const MachineInstr *A, + const MachineInstr *B) { + assert(canHandle(A) && canHandle(B) && "Precondition!"); - // Right now we don't want to worry about LLVM's memory model. This can be - // made more precise later. - for (auto *MMO : MI->memoperands()) - if (!MMO->isUnordered()) - return false; + // canHandle makes sure that we _can_ correctly analyze the dependencies + // between A and B here -- for instance, we should not be dealing with heap + // load-store dependencies here. - for (auto &MO : MI->operands()) { - if (MO.isReg() && MO.getReg()) { - for (auto &RegDef : RegDefs) { - unsigned Reg = RegDef.first; - MachineInstr *MI = RegDef.second; - if (!TRI.regsOverlap(Reg, MO.getReg())) - continue; + for (auto MOA : A->operands()) { + if (!(MOA.isReg() && MOA.getReg())) + continue; - // We found a write-after-write or read-after-write, see if the - // instruction causing this dependency can be hoisted too. - - if (MI == getUnknownMI()) - // We don't have precise dependency information. - return false; - - if (Dependency) { - if (Dependency == MI) - continue; - // We already have one dependency, and we can track only one. - return false; - } - - // Now check if MI is actually a dependency that can be hoisted. - - // We don't want to track transitive dependencies. We already know that - // MI is the only instruction that defines Reg, but we need to be sure - // that it does not use any registers that have been defined (trivially - // checked below by ensuring that there are no register uses), and that - // it is the only def for every register it defines (otherwise we could - // violate a write after write hazard). - auto IsMIOperandSafe = [&](MachineOperand &MO) { - if (!MO.isReg() || !MO.getReg()) - return true; - if (MO.isUse()) - return false; - assert((!MO.isDef() || RegDefs.count(MO.getReg())) && - "All defs must be tracked in RegDefs by now!"); - return !MO.isDef() || RegDefs.find(MO.getReg())->second == MI; - }; - - if (!all_of(MI->operands(), IsMIOperandSafe)) - return false; - - // Now check for speculation safety: - bool SawStore = true; - if (!MI->isSafeToMove(&AA, SawStore) || MI->mayLoad()) - return false; - - Dependency = MI; - } + unsigned RegA = MOA.getReg(); + for (auto MOB : B->operands()) { + if (!(MOB.isReg() && MOB.getReg())) + continue; - if (MO.isDef()) - for (unsigned Reg : RegUses) - if (TRI.regsOverlap(Reg, MO.getReg())) - return false; // We found a write-after-read + unsigned RegB = MOB.getReg(); + + if (TRI->regsOverlap(RegA, RegB)) + return false; } } @@ -316,6 +283,96 @@ static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI, return false; } +bool ImplicitNullChecks::isSuitableMemoryOp( + MachineInstr &MI, unsigned PointerReg, ArrayRef<MachineInstr *> PrevInsts) { + int64_t Offset; + unsigned BaseReg; + + if (!TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI) || + BaseReg != PointerReg) + return false; + + // We want the load to be issued at a sane offset from PointerReg, so that + // if PointerReg is null then the load reliably page faults. + if (!(MI.mayLoad() && !MI.isPredicable() && Offset < PageSize)) + return false; + + // Finally, we need to make sure that the load instruction actually is + // loading from PointerReg, and there isn't some re-definition of PointerReg + // between the compare and the load. + for (auto *PrevMI : PrevInsts) + for (auto &PrevMO : PrevMI->operands()) + if (PrevMO.isReg() && PrevMO.getReg() && + TRI->regsOverlap(PrevMO.getReg(), PointerReg)) + return false; + + return true; +} + +bool ImplicitNullChecks::canHoistLoadInst( + MachineInstr *FaultingMI, unsigned PointerReg, + ArrayRef<MachineInstr *> InstsSeenSoFar, MachineBasicBlock *NullSucc, + MachineInstr *&Dependence) { + auto DepResult = computeDependence(FaultingMI, InstsSeenSoFar); + if (!DepResult.CanReorder) + return false; + + if (!DepResult.PotentialDependence) { + Dependence = nullptr; + return true; + } + + auto DependenceItr = *DepResult.PotentialDependence; + auto *DependenceMI = *DependenceItr; + + // We don't want to reason about speculating loads. Note -- at this point + // we should have already filtered out all of the other non-speculatable + // things, like calls and stores. + assert(canHandle(DependenceMI) && "Should never have reached here!"); + if (DependenceMI->mayLoad()) + return false; + + for (auto &DependenceMO : DependenceMI->operands()) { + if (!(DependenceMO.isReg() && DependenceMO.getReg())) + continue; + + // Make sure that we won't clobber any live ins to the sibling block by + // hoisting Dependency. For instance, we can't hoist INST to before the + // null check (even if it safe, and does not violate any dependencies in + // the non_null_block) if %rdx is live in to _null_block. + // + // test %rcx, %rcx + // je _null_block + // _non_null_block: + // %rdx<def> = INST + // ... + // + // This restriction does not apply to the faulting load inst because in + // case the pointer loaded from is in the null page, the load will not + // semantically execute, and affect machine state. That is, if the load + // was loading into %rax and it faults, the value of %rax should stay the + // same as it would have been had the load not have executed and we'd have + // branched to NullSucc directly. + if (AnyAliasLiveIn(TRI, NullSucc, DependenceMO.getReg())) + return false; + + // The Dependency can't be re-defining the base register -- then we won't + // get the memory operation on the address we want. This is already + // checked in \c IsSuitableMemoryOp. + assert(!TRI->regsOverlap(DependenceMO.getReg(), PointerReg) && + "Should have been checked before!"); + } + + auto DepDepResult = + computeDependence(DependenceMI, {InstsSeenSoFar.begin(), DependenceItr}); + + if (!DepDepResult.CanReorder || DepDepResult.PotentialDependence) + return false; + + Dependence = DependenceMI; + return true; +} + /// Analyze MBB to check if its terminating branch can be turned into an /// implicit null check. If yes, append a description of the said null check to /// NullCheckList and return true, else return false. @@ -415,63 +472,24 @@ bool ImplicitNullChecks::analyzeBlockForNullChecks( // ptr could be some non-null invalid reference that never gets loaded from // because some_cond is always true. - unsigned PointerReg = MBP.LHS.getReg(); - - HazardDetector HD(*TRI, *AA); - - for (auto MII = NotNullSucc->begin(), MIE = NotNullSucc->end(); MII != MIE; - ++MII) { - MachineInstr &MI = *MII; - unsigned BaseReg; - int64_t Offset; - MachineInstr *Dependency = nullptr; - if (TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI)) - if (MI.mayLoad() && !MI.isPredicable() && BaseReg == PointerReg && - Offset < PageSize && MI.getDesc().getNumDefs() <= 1 && - HD.isSafeToHoist(&MI, Dependency)) { - - auto DependencyOperandIsOk = [&](MachineOperand &MO) { - assert(!(MO.isReg() && MO.isUse()) && - "No transitive dependendencies please!"); - if (!MO.isReg() || !MO.getReg() || !MO.isDef()) - return true; - - // Make sure that we won't clobber any live ins to the sibling block - // by hoisting Dependency. For instance, we can't hoist INST to - // before the null check (even if it safe, and does not violate any - // dependencies in the non_null_block) if %rdx is live in to - // _null_block. - // - // test %rcx, %rcx - // je _null_block - // _non_null_block: - // %rdx<def> = INST - // ... - if (AnyAliasLiveIn(TRI, NullSucc, MO.getReg())) - return false; - - // Make sure Dependency isn't re-defining the base register. Then we - // won't get the memory operation on the address we want. - if (TRI->regsOverlap(MO.getReg(), BaseReg)) - return false; - - return true; - }; - - bool DependencyOperandsAreOk = - !Dependency || - all_of(Dependency->operands(), DependencyOperandIsOk); - - if (DependencyOperandsAreOk) { - NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc, - NullSucc, Dependency); - return true; - } - } + const unsigned PointerReg = MBP.LHS.getReg(); - HD.rememberInstruction(&MI); - if (HD.isClobbered()) + SmallVector<MachineInstr *, 8> InstsSeenSoFar; + + for (auto &MI : *NotNullSucc) { + if (!canHandle(&MI) || InstsSeenSoFar.size() >= MaxInstsToConsider) return false; + + MachineInstr *Dependence; + if (isSuitableMemoryOp(MI, PointerReg, InstsSeenSoFar) && + canHoistLoadInst(&MI, PointerReg, InstsSeenSoFar, NullSucc, + Dependence)) { + NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc, + NullSucc, Dependence); + return true; + } + + InstsSeenSoFar.push_back(&MI); } return false; @@ -518,7 +536,7 @@ void ImplicitNullChecks::rewriteNullChecks( for (auto &NC : NullCheckList) { // Remove the conditional branch dependent on the null check. - unsigned BranchesRemoved = TII->RemoveBranch(*NC.getCheckBlock()); + unsigned BranchesRemoved = TII->removeBranch(*NC.getCheckBlock()); (void)BranchesRemoved; assert(BranchesRemoved > 0 && "expected at least one branch!"); @@ -560,13 +578,14 @@ void ImplicitNullChecks::rewriteNullChecks( NC.getCheckOperation()->eraseFromParent(); // Insert an *unconditional* branch to not-null successor. - TII->InsertBranch(*NC.getCheckBlock(), NC.getNotNullSucc(), nullptr, + TII->insertBranch(*NC.getCheckBlock(), NC.getNotNullSucc(), nullptr, /*Cond=*/None, DL); NumImplicitNullChecks++; } } + char ImplicitNullChecks::ID = 0; char &llvm::ImplicitNullChecksID = ImplicitNullChecks::ID; INITIALIZE_PASS_BEGIN(ImplicitNullChecks, "implicit-null-checks", |
