diff --git a/llvm/lib/CodeGen/ImplicitNullChecks.cpp b/llvm/lib/CodeGen/ImplicitNullChecks.cpp --- a/llvm/lib/CodeGen/ImplicitNullChecks.cpp +++ b/llvm/lib/CodeGen/ImplicitNullChecks.cpp @@ -79,43 +79,15 @@ namespace { class ImplicitNullChecks : public MachineFunctionPass { - /// Return true if \c computeDependence can process \p MI. + /// Return true if this satisfies basic checks that MI does not clobber the + /// faulting instruction.. static bool canHandle(const MachineInstr *MI); - /// Helper function for \c computeDependence. Return true if \p A + /// 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 - /// dependency. - 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::iterator> PotentialDependence; - - /*implicit*/ DependenceResult( - bool CanReorder, - Optional::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 Block); /// Represents one null check that can be made implicit. class NullCheck { @@ -134,19 +106,20 @@ // The block branched to if the pointer is null. MachineBasicBlock *NullSucc; - // If this is non-null, then MemOperation has a dependency on this - // instruction; and it needs to be hoisted to execute before MemOperation. - MachineInstr *OnlyDependency; + // If this is non-empty, then MemOperation has a dependency on these + // instruction; and they need to be hoisted to execute before MemOperation. + SmallVector SafeDependenceList; public: explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation, MachineBasicBlock *checkBlock, MachineBasicBlock *notNullSucc, MachineBasicBlock *nullSucc, - MachineInstr *onlyDependency) + SmallVectorImpl &safeDependenceList) : MemOperation(memOperation), CheckOperation(checkOperation), CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc), - OnlyDependency(onlyDependency) {} + SafeDependenceList(safeDependenceList.begin(), + safeDependenceList.end()) {} MachineInstr *getMemOperation() const { return MemOperation; } @@ -158,7 +131,11 @@ MachineBasicBlock *getNullSucc() const { return NullSucc; } - MachineInstr *getOnlyDependency() const { return OnlyDependency; } + // This is a backward-list, so we will need to iterate in reverse and place + // it in correct MBB when hoisting entire chunk. + const SmallVectorImpl &getSafeDependenceList() const { + return SafeDependenceList; + } }; // We can have multiple starting addresses for faulting pages, i.e. page zero @@ -222,9 +199,8 @@ /// Return true if \p FaultingMI can be hoisted from after 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 canHoistInst(MachineInstr *FaultingMI, - ArrayRef InstsSeenSoFar, - MachineBasicBlock *NullSucc, MachineInstr *&Dependence); + bool canHoistInst(MachineInstr *FaultingMI, MachineBasicBlock *NullSucc, + SmallVectorImpl &DependenceList); public: static char ID; @@ -262,30 +238,6 @@ return llvm::all_of(MI->memoperands(), IsUnordered); } -ImplicitNullChecks::DependenceResult -ImplicitNullChecks::computeDependence(const MachineInstr *MI, - ArrayRef Block) { - assert(llvm::all_of(Block, canHandle) && "Check this first!"); - assert(!is_contained(Block, MI) && "Block must be exclusive of MI!"); - - Optional::iterator> Dep; - - for (auto I = Block.begin(), E = Block.end(); I != E; ++I) { - if (canReorder(*I, MI)) - continue; - - if (Dep == None) { - // Found one possible dependency, keep track of it. - Dep = I; - } else { - // We found two dependencies, so bail out. - return {false, None}; - } - } - - return {true, Dep}; -} - bool ImplicitNullChecks::canReorder(const MachineInstr *A, const MachineInstr *B) { assert(canHandle(A) && canHandle(B) && "Precondition!"); @@ -498,41 +450,90 @@ return false; } -bool ImplicitNullChecks::canHoistInst(MachineInstr *FaultingMI, - ArrayRef 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; +bool ImplicitNullChecks::canHoistInst( + MachineInstr *FaultingMI, MachineBasicBlock *NullSucc, + SmallVectorImpl &DependenceList) { + + // Dependence state while processing the instructions in the FaultingMI's + // basic block. We start with unknown and at any point we should have either + // no dependence or a safe dependence. They are mutually exclusive, i.e. we + // cannot go from DS_None to DS_Safe and vice-versa. + // While handling both cases are possible, the algorithm below becomes + // exponential (since we need to check that *each dependency* can be reordered + // over + // all instructions that were independent of the FaultingMI). + enum DependenceState { DS_Unknown, DS_None, DS_Safe }; + + DependenceState CurrDepState = DS_Unknown; + + SmallDenseSet TrackedRegisterUses; + // Explicit uses are recorded. + auto RecordExplicitUses = [&TrackedRegisterUses](MachineInstr *MI) { + for (auto &MO : MI->uses()) { + if (MO.isReg() && MO.isUse()) + TrackedRegisterUses.insert(MO.getReg()); + } + }; - // 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. - // We also do not want to hoist stores because it might change the memory - // while the FaultingMI may result in faulting. - assert(canHandle(DependenceMI) && "Should never have reached here!"); - if (DependenceMI->mayLoadOrStore()) - return false; + // We perform dependence analysis by a backward traversal starting from + // faultingMI + // until the start of the basic block and record the dependencies in the + // DependenceList. We do not care about dependencies past + // the basic block, since we are hoisting the faultingMI and the + // DependenceList into the nullcheck basic block. + // We first record the uses in faultingMI. + RecordExplicitUses(FaultingMI); + // A backward traversal looking for register defs of the recorded uses works, + // because when we see a def through backward traversal, it is effectively the + // "correct def" which corresponds to the recorded use. + for (auto It = std::next(MachineBasicBlock::reverse_iterator(FaultingMI)); + It != FaultingMI->getParent()->rend(); ++It) { + MachineInstr *CurrMI = &*It; + // No read-after-write, write-afer-write, write-after-read dependencies. + if (canReorder(CurrMI, FaultingMI)) { + // We cannot move from a safe-dependency state to a no-dependency, since + // that will require checking that we can reorder CurrMI over all the + // dependencies recorded in DependenceList as well. + if (CurrDepState == DS_Safe) + return false; + CurrDepState = DS_None; + continue; + } - if (canDependenceHoistingClobberLiveIns(DependenceMI, NullSucc)) - return false; + if (CurrMI->mayLoadOrStore()) + return false; - auto DepDepResult = - computeDependence(DependenceMI, {InstsSeenSoFar.begin(), DependenceItr}); + // We cannot move from non-dependency to a safe dependency. + // This effectively means we either have all instructions that are + // independent of faulting MI (i.e. DS_None) or all instructions that + // safely depend on faulting MI (either directly or transitively and we are + // at DS_Safe state). + if (CurrDepState == DS_None) + return false; - if (!DepDepResult.CanReorder || DepDepResult.PotentialDependence) - return false; + if (canDependenceHoistingClobberLiveIns(CurrMI, NullSucc)) + return false; - Dependence = DependenceMI; + // At this point, we cannot just simply hoist the FaultingMI. This means + // unless it is an MI which defines the uses already recorded, we have to + // bail out. + if (!llvm::any_of(CurrMI->operands(), + [&TrackedRegisterUses](const MachineOperand &MO) { + return MO.isReg() && MO.isDef() && + (TrackedRegisterUses.count(MO.getReg()) || + TrackedRegisterUses.count(MO.getSubReg())); + })) + return false; + // TODO: We need to handle cases where CurrMI defines a subReg of one of + // the registers in trackedRegisterUses. + // esi = .. + // faulting mi mv32rm = .., rsi, .. + + assert(canHandle(CurrMI) && "Should never have reached here!"); + DependenceList.push_back(CurrMI); + RecordExplicitUses(CurrMI); + CurrDepState = DS_Safe; + } return true; } @@ -664,6 +665,8 @@ SmallVector InstsSeenSoFar; DenseSet InstrPreservesZeroReg; + SmallVector DependenceList; + for (auto &MI : *NotNullSucc) { if (!canHandle(&MI) || InstsSeenSoFar.size() >= MaxInstsToConsider) return false; @@ -673,10 +676,10 @@ InstrPreservesZeroReg); if (SR == SR_Impossible) return false; - if (SR == SR_Suitable && - canHoistInst(&MI, InstsSeenSoFar, NullSucc, Dependence)) { + + if (SR == SR_Suitable && canHoistInst(&MI, NullSucc, DependenceList)) { NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc, - NullSucc, Dependence); + NullSucc, DependenceList); return true; } @@ -754,7 +757,9 @@ (void)BranchesRemoved; assert(BranchesRemoved > 0 && "expected at least one branch!"); - if (auto *DepMI = NC.getOnlyDependency()) { + const SmallVectorImpl &DepList = NC.getSafeDependenceList(); + // We need to iterate in reverse to place dependencies in correct order. + for (auto *DepMI : reverse(DepList)) { DepMI->removeFromParent(); NC.getCheckBlock()->insert(NC.getCheckBlock()->end(), DepMI); } @@ -779,7 +784,7 @@ MBB->addLiveIn(Reg); } - if (auto *DepMI = NC.getOnlyDependency()) { + for (auto *DepMI : DepList) { for (auto &MO : DepMI->operands()) { if (!MO.isReg() || !MO.getReg() || !MO.isDef() || MO.isDead()) continue; diff --git a/llvm/test/CodeGen/X86/implicit-null-check.ll b/llvm/test/CodeGen/X86/implicit-null-check.ll --- a/llvm/test/CodeGen/X86/implicit-null-check.ll +++ b/llvm/test/CodeGen/X86/implicit-null-check.ll @@ -647,6 +647,7 @@ %t = load i64, i64* %x.loc ret i64 %t } + !startaddress_faulting_pages = !{!1, !2} !0 = !{} !1 = !{i64 0} diff --git a/llvm/test/CodeGen/X86/implicit-null-checks.mir b/llvm/test/CodeGen/X86/implicit-null-checks.mir --- a/llvm/test/CodeGen/X86/implicit-null-checks.mir +++ b/llvm/test/CodeGen/X86/implicit-null-checks.mir @@ -434,6 +434,24 @@ ret i32 200 } + define i32 @load_from_non_zero_faulting_page_dep2(i32* %ptr, i32 %val) { + entry: + %ptr_is_null = icmp eq i32* %ptr, null + br i1 %ptr_is_null, label %is_null, label %not_null, !make.implicit !0 + + is_null: + ret i32 42 + + not_null: + br i1 undef, label %ret_100, label %ret_200 + + ret_100: + ret i32 100 + + ret_200: + ret i32 200 + } + attributes #0 = { "target-features"="+bmi,+bmi2" } !startaddress_faulting_pages = !{!1, !2} @@ -536,8 +554,10 @@ - { reg: '$rdi' } - { reg: '$esi' } # CHECK: bb.0.entry: -# CHECK: TEST64rr $rdi, $rdi, implicit-def $eflags -# CHECK-NEXT: JCC_1 %bb.3, 4, implicit $eflags +# CHECK: $eax = MOV32ri 2200000 +# CHECK: $eax = ADD32ri killed $eax, 100, implicit-def dead $eflags +# CHECK: $eax = FAULTING_OP 1, %bb.3, 444, $eax, $rdi, 1, $noreg, 0, $noreg, implicit-def $eflags +# CHECK: JMP_1 %bb.1 body: | bb.0.entry: @@ -984,9 +1004,10 @@ name: inc_store_with_two_dep # CHECK-LABEL: inc_store_with_two_dep # CHECK: bb.0.entry: -# CHECK: TEST64rr $rdi, $rdi, implicit-def $eflags -# CHECK-NEXT: JCC_1 %bb.2, 4, implicit killed $eflags -# CHECK: bb.1.not_null +# CHECK: $esi = ADD32rr killed $esi, killed $esi, implicit-def dead $eflags +# CHECK: $esi = ADD32ri killed $esi, 15, implicit-def dead $eflags +# CHECK: $noreg = FAULTING_OP 3, %bb.2, 1716, $rdi, 1, $noreg, 16, $noreg, $esi +# CHECK: JMP_1 %bb.1 alignment: 16 tracksRegLiveness: true @@ -1499,3 +1520,43 @@ bb.4.ret_100: $eax = MOV32ri 100 RETQ $eax + +--- +name: load_from_non_zero_faulting_page_dep2 +# This is a positive test where we have 2 dependencies on the +# memory op. + +# CHECK-LABEL: name: load_from_non_zero_faulting_page_dep2 +# CHECK: bb.0.entry: +# CHECK: renamable $rdx = MOV64ri 35184372088832 +# CHECK: renamable $eax = MOV32rr renamable $eax, implicit killed $rax, implicit-def $rax +# CHECK: $ecx = FAULTING_OP 1, %bb.3, 1724, renamable $rdx, 8, renamable $rax, 4, $noreg +liveins: + - { reg: '$rax' } + - { reg: '$rbx' } + +body: | + bb.0.entry: + liveins: $rax, $rbx + TEST64rr renamable $rax, renamable $rax, implicit-def $eflags + JCC_1 %bb.3, 4, implicit $eflags + + bb.1.not_null: + liveins: $rax, $rbx + renamable $rdx = MOV64ri 35184372088832 + renamable $eax = MOV32rr renamable $eax, implicit killed $rax, implicit-def $rax + renamable $ecx = MOV32rm renamable $rdx, 8, renamable $rax, 4, $noreg + CMP32ri killed renamable $ecx, 1195, implicit-def $eflags + JCC_1 %bb.4, 4, implicit $eflags + + bb.2.ret_200: + $eax = MOV32ri 200 + RETQ $eax + + bb.3.is_null: + $eax = MOV32ri 42 + RETQ $eax + + bb.4.ret_100: + $eax = MOV32ri 100 + RETQ $eax