63#define DEBUG_TYPE "implicit-null-checks"
66 "Number of explicit null checks made implicit");
70class ImplicitNullChecksImpl {
83 struct DependenceResult {
90 std::optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence;
95 : CanReorder(CanReorder), PotentialDependence(PotentialDependence) {
96 assert((!PotentialDependence || CanReorder) &&
97 "!CanReorder && PotentialDependence.hasValue() not allowed!");
106 DependenceResult computeDependence(
const MachineInstr *
MI,
112 MachineInstr *MemOperation;
115 MachineInstr *CheckOperation;
118 MachineBasicBlock *CheckBlock;
121 MachineBasicBlock *NotNullSucc;
124 MachineBasicBlock *NullSucc;
128 MachineInstr *OnlyDependency;
131 explicit NullCheck(MachineInstr *memOperation, MachineInstr *checkOperation,
132 MachineBasicBlock *checkBlock,
133 MachineBasicBlock *notNullSucc,
134 MachineBasicBlock *nullSucc,
135 MachineInstr *onlyDependency)
136 : MemOperation(memOperation), CheckOperation(checkOperation),
137 CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc),
138 OnlyDependency(onlyDependency) {}
140 MachineInstr *getMemOperation()
const {
return MemOperation; }
142 MachineInstr *getCheckOperation()
const {
return CheckOperation; }
144 MachineBasicBlock *getCheckBlock()
const {
return CheckBlock; }
146 MachineBasicBlock *getNotNullSucc()
const {
return NotNullSucc; }
148 MachineBasicBlock *getNullSucc()
const {
return NullSucc; }
150 MachineInstr *getOnlyDependency()
const {
return OnlyDependency; }
153 const CodeGenOptions &Opts;
154 const TargetInstrInfo *TII =
nullptr;
155 const TargetRegisterInfo *TRI =
nullptr;
157 MachineFrameInfo *MFI =
nullptr;
159 bool analyzeBlockForNullChecks(MachineBasicBlock &
MBB,
160 SmallVectorImpl<NullCheck> &NullCheckList);
161 MachineInstr *insertFaultingInstr(MachineInstr *
MI, MachineBasicBlock *
MBB,
162 MachineBasicBlock *HandlerMBB);
168 AR_WillAliasEverything
174 AliasResult areMemoryOpsAliased(
const MachineInstr &
MI,
175 const MachineInstr *PrevMI)
const;
177 enum SuitabilityResult {
189 SuitabilityResult isSuitableMemoryOp(
const MachineInstr &
MI,
196 bool canDependenceHoistingClobberLiveIns(MachineInstr *DependenceMI,
197 MachineBasicBlock *NullSucc);
202 bool canHoistInst(MachineInstr *FaultingMI,
204 MachineBasicBlock *NullSucc, MachineInstr *&Dependence);
209 TRI(MF.getRegInfo().getTargetRegisterInfo()), AA(AA),
210 MFI(&MF.getFrameInfo()) {}
219 ImplicitNullChecksLegacy() : MachineFunctionPass(ID) {}
224 auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
225 return ImplicitNullChecksImpl(MF, AA).run(MF);
228 void getAnalysisUsage(AnalysisUsage &AU)
const override {
233 MachineFunctionProperties getRequiredProperties()
const override {
234 return MachineFunctionProperties().setNoVRegs();
241 if (
MI->isCall() ||
MI->mayRaiseFPException() ||
242 MI->hasUnmodeledSideEffects())
244 auto IsRegMask = [](
const MachineOperand &MO) {
return MO.isRegMask(); };
248 "Calls were filtered out above!");
250 auto IsUnordered = [](MachineMemOperand *MMO) {
return MMO->isUnordered(); };
254ImplicitNullChecksImpl::DependenceResult
255ImplicitNullChecksImpl::computeDependence(
const MachineInstr *
MI,
260 std::optional<ArrayRef<MachineInstr *>::iterator> Dep;
263 if (canReorder(*
I,
MI))
266 if (Dep == std::nullopt) {
271 return {
false, std::nullopt};
278bool ImplicitNullChecksImpl::canReorder(
const MachineInstr *
A,
279 const MachineInstr *
B) {
280 assert(canHandle(
A) && canHandle(
B) &&
"Precondition!");
286 for (
const auto &MOA :
A->operands()) {
287 if (!(MOA.isReg() && MOA.getReg()))
291 for (
const auto &MOB :
B->operands()) {
292 if (!(MOB.isReg() && MOB.getReg()))
297 if (
TRI->regsOverlap(RegA, RegB) && (MOA.isDef() || MOB.isDef()))
310 analyzeBlockForNullChecks(
MBB, NullCheckList);
312 if (!NullCheckList.
empty())
313 rewriteNullChecks(NullCheckList);
315 return !NullCheckList.
empty();
323 if (
MBB->isLiveIn(*AR))
328ImplicitNullChecksImpl::AliasResult
329ImplicitNullChecksImpl::areMemoryOpsAliased(
const MachineInstr &
MI,
330 const MachineInstr *PrevMI)
const {
339 if (
MI.memoperands_empty())
340 return MI.mayStore() ? AR_WillAliasEverything : AR_MayAlias;
342 return PrevMI->
mayStore() ? AR_WillAliasEverything : AR_MayAlias;
344 for (MachineMemOperand *MMO1 :
MI.memoperands()) {
347 assert(MMO1->getValue() &&
"MMO1 should have a Value!");
348 for (MachineMemOperand *MMO2 : PrevMI->
memoperands()) {
349 if (
const PseudoSourceValue *PSV = MMO2->getPseudoValue()) {
350 if (PSV->mayAlias(MFI))
363ImplicitNullChecksImpl::SuitabilityResult
364ImplicitNullChecksImpl::isSuitableMemoryOp(
const MachineInstr &
MI,
369 if (
MI.getDesc().getNumDefs() > 1)
370 return SR_Unsuitable;
372 if (!
MI.mayLoadOrStore() ||
MI.isPredicable())
373 return SR_Unsuitable;
374 auto AM =
TII->getAddrModeFromMemoryOp(
MI);
375 if (!AM || AM->Form != ExtAddrMode::Formula::Basic)
376 return SR_Unsuitable;
379 int64_t Displacement =
AddrMode.Displacement;
383 if (BaseReg != PointerReg && ScaledReg != PointerReg)
384 return SR_Unsuitable;
386 unsigned PointerRegSizeInBits =
TRI->getRegSizeInBits(PointerReg,
MRI);
390 TRI->getRegSizeInBits(BaseReg,
MRI) != PointerRegSizeInBits) ||
392 TRI->getRegSizeInBits(ScaledReg,
MRI) != PointerRegSizeInBits))
393 return SR_Unsuitable;
397 auto CalculateDisplacementFromAddrMode = [&](
Register RegUsedInAddr,
398 int64_t Multiplier) {
404 assert(Multiplier &&
"expected to be non-zero!");
405 MachineInstr *ModifyingMI =
nullptr;
407 It !=
MI.getParent()->
rend(); It++) {
408 const MachineInstr *CurrMI = &*It;
410 ModifyingMI =
const_cast<MachineInstr *
>(CurrMI);
419 if (!
TII->getConstValDefinedInReg(*ModifyingMI, RegUsedInAddr, ImmVal))
426 assert(MultiplierC.isStrictlyPositive() &&
427 "expected to be a positive value!");
431 APInt Product = ImmValC.smul_ov(MultiplierC, IsOverflow);
434 APInt DisplacementC(64, Displacement,
true );
435 DisplacementC = Product.
sadd_ov(DisplacementC, IsOverflow);
440 if (DisplacementC.getActiveBits() > 64)
442 Displacement = DisplacementC.getSExtValue();
448 bool BaseRegIsConstVal =
false, ScaledRegIsConstVal =
false;
449 if (CalculateDisplacementFromAddrMode(BaseReg, 1))
450 BaseRegIsConstVal =
true;
451 if (CalculateDisplacementFromAddrMode(ScaledReg,
AddrMode.Scale))
452 ScaledRegIsConstVal =
true;
459 if ((BaseReg && BaseReg != PointerReg && !BaseRegIsConstVal) ||
460 (ScaledReg && ScaledReg != PointerReg && !ScaledRegIsConstVal))
461 return SR_Unsuitable;
465 if (!(-Opts.imp_null_check_page_size < Displacement &&
466 Displacement < Opts.imp_null_check_page_size))
467 return SR_Unsuitable;
470 for (
auto *PrevMI : PrevInsts) {
471 AliasResult AR = areMemoryOpsAliased(
MI, PrevMI);
472 if (AR == AR_WillAliasEverything)
473 return SR_Impossible;
474 if (AR == AR_MayAlias)
475 return SR_Unsuitable;
480bool ImplicitNullChecksImpl::canDependenceHoistingClobberLiveIns(
481 MachineInstr *DependenceMI, MachineBasicBlock *NullSucc) {
482 for (
const auto &DependenceMO : DependenceMI->
operands()) {
483 if (!(DependenceMO.isReg() && DependenceMO.getReg()))
512bool ImplicitNullChecksImpl::canHoistInst(
514 MachineBasicBlock *NullSucc, MachineInstr *&Dependence) {
515 auto DepResult = computeDependence(FaultingMI, InstsSeenSoFar);
516 if (!DepResult.CanReorder)
519 if (!DepResult.PotentialDependence) {
520 Dependence =
nullptr;
524 auto DependenceItr = *DepResult.PotentialDependence;
525 auto *DependenceMI = *DependenceItr;
532 assert(canHandle(DependenceMI) &&
"Should never have reached here!");
536 if (canDependenceHoistingClobberLiveIns(DependenceMI, NullSucc))
540 computeDependence(DependenceMI, {InstsSeenSoFar.
begin(), DependenceItr});
542 if (!DepDepResult.CanReorder || DepDepResult.PotentialDependence)
545 Dependence = DependenceMI;
552bool ImplicitNullChecksImpl::analyzeBlockForNullChecks(
553 MachineBasicBlock &
MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
554 using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
556 MDNode *BranchMD =
nullptr;
558 BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit);
563 MachineBranchPredicate MBP;
565 if (
TII->analyzeBranchPredicate(
MBB, MBP,
true))
569 if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
570 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
571 MBP.Predicate == MachineBranchPredicate::PRED_EQ)))
576 if (MBP.ConditionDef && !MBP.SingleUseCondition)
579 MachineBasicBlock *NotNullSucc, *NullSucc;
581 if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {
582 NotNullSucc = MBP.TrueDest;
583 NullSucc = MBP.FalseDest;
585 NotNullSucc = MBP.FalseDest;
586 NullSucc = MBP.TrueDest;
594 const Register PointerReg = MBP.LHS.getReg();
596 if (MBP.ConditionDef) {
615 assert(MBP.ConditionDef->getParent() == &
MBB &&
616 "Should be in basic block");
618 for (
auto I =
MBB.
rbegin(); MBP.ConditionDef != &*
I; ++
I)
619 if (
I->modifiesRegister(PointerReg,
TRI))
676 SmallVector<MachineInstr *, 8> InstsSeenSoFar;
684 for (MachineInstr &
MI :
686 if (!canHandle(&
MI) ||
687 InstsSeenSoFar.
size() >= Opts.imp_null_max_insts_to_consider)
690 MachineInstr *Dependence;
691 SuitabilityResult SR = isSuitableMemoryOp(
MI, PointerReg, InstsSeenSoFar);
692 if (SR == SR_Impossible)
694 if (SR == SR_Suitable &&
695 canHoistInst(&
MI, InstsSeenSoFar, NullSucc, Dependence)) {
697 NullSucc, Dependence);
703 if (!
TII->preservesZeroValueInReg(&
MI, PointerReg))
715MachineInstr *ImplicitNullChecksImpl::insertFaultingInstr(
716 MachineInstr *
MI, MachineBasicBlock *
MBB, MachineBasicBlock *HandlerMBB) {
717 unsigned NumDefs =
MI->getDesc().getNumDefs();
718 assert(NumDefs <= 1 &&
"other cases unhandled!");
722 DefReg =
MI->getOperand(0).getReg();
723 assert(NumDefs == 1 &&
"expected exactly one def!");
734 TII->get(TargetOpcode::FAULTING_OP), DefReg)
739 for (
auto &MO :
MI->uses()) {
741 MachineOperand NewMO = MO;
745 assert(MO.isDef() &&
"Expected def or use");
760void ImplicitNullChecksImpl::rewriteNullChecks(
764 for (
const auto &
NC : NullCheckList) {
767 (void)BranchesRemoved;
768 assert(BranchesRemoved > 0 &&
"expected at least one branch!");
770 if (
auto *DepMI =
NC.getOnlyDependency()) {
771 DepMI->removeFromParent();
772 NC.getCheckBlock()->insert(
NC.getCheckBlock()->end(), DepMI);
779 MachineInstr *FaultingInstr = insertFaultingInstr(
780 NC.getMemOperation(),
NC.getCheckBlock(),
NC.getNullSucc());
786 for (
const MachineOperand &MO : FaultingInstr->
all_defs()) {
793 if (
auto *DepMI =
NC.getOnlyDependency()) {
794 for (
auto &MO : DepMI->all_defs()) {
795 if (!MO.getReg() || MO.isDead())
797 if (!
NC.getNotNullSucc()->isLiveIn(MO.getReg()))
798 NC.getNotNullSucc()->addLiveIn(MO.getReg());
802 NC.getMemOperation()->eraseFromParent();
803 if (
auto *CheckOp =
NC.getCheckOperation())
804 CheckOp->eraseFromParent();
811 NumImplicitNullChecks++;
815char ImplicitNullChecksLegacy::ID = 0;
820 "Implicit null checks",
false,
false)
832 bool Changed = ImplicitNullChecksImpl(MF, &
AA).run(MF);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
const HexagonInstrInfo * TII
static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI, MachineBasicBlock *MBB, Register Reg)
Register const TargetRegisterInfo * TRI
Promote Memory to Register
This file provides utility analysis objects describing memory locations.
FunctionAnalysisManager FAM
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
MachineRegisterInfo & MRI
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
uint16_t RegSizeInBits(const MCRegisterInfo &MRI, MCRegister RegNo)
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are no-alias.
LLVM_ABI APInt sadd_ov(const APInt &RHS, bool &Overflow) const
AnalysisUsage & addRequired()
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const override
Insert branch code into the end of the specified MachineBasicBlock.
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
MCRegAliasIterator enumerates all registers aliasing Reg.
An RAII based helper class to modify MachineFunctionProperties when running pass.
unsigned pred_size() const
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
reverse_iterator rbegin()
MachineInstrBundleIterator< const MachineInstr, true > const_reverse_iterator
LLVM_ABI bool isLiveIn(MCRegister Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineInstrBuilder & setMemRefs(ArrayRef< MachineMemOperand * > MMOs) const
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
Representation of each machine instruction.
bool mayLoadOrStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read or modify memory.
filtered_mop_range all_defs()
Returns an iterator range over all operands that are (explicit or implicit) register defs.
bool memoperands_empty() const
Return true if we don't have any memory operands which described the memory access done by this instr...
bool modifiesRegister(Register Reg, const TargetRegisterInfo *TRI) const
Return true if the MachineInstr modifies (fully define or partially define) the specified register.
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
ArrayRef< MachineMemOperand * > memoperands() const
Access to memory operands of the instruction.
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
void setIsDead(bool Val=true)
void setIsKill(bool Val=true)
const MachineFunction & getMF() const
static MemoryLocation getAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location after Ptr, while remaining within the underlying objec...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Wrapper class representing virtual and physical registers.
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Abstract Attribute helper functions.
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
std::reverse_iterator< iterator > rend() const
BaseReg
Stack frame base register. Bit 0 of FREInfo.Info.
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
LLVM_ABI char & ImplicitNullChecksID
ImplicitNullChecks - This pass folds null pointer checks into nearby memory operations.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
auto instructionsWithoutDebug(IterT It, IterT End, bool SkipPseudoOp=true)
Construct a range iterator which begins at It and moves forwards until End is reached,...
ArrayRef(const T &OneElt) -> ArrayRef< T >
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
AAResults AliasAnalysis
Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)