Go to the documentation of this file.
65 cl::desc(
"The page size of the target in bytes"),
69 "imp-null-max-insts-to-consider",
70 cl::desc(
"The max number of instructions to consider hoisting loads over "
71 "(the algorithm is quadratic over this number)"),
74 #define DEBUG_TYPE "implicit-null-checks"
77 "Number of explicit null checks made implicit");
94 struct DependenceResult {
106 : CanReorder(CanReorder), PotentialDependence(PotentialDependence) {
107 assert((!PotentialDependence || CanReorder) &&
108 "!CanReorder && PotentialDependence.hasValue() not allowed!");
147 : MemOperation(memOperation), CheckOperation(checkOperation),
148 CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc),
149 OnlyDependency(onlyDependency) {}
151 MachineInstr *getMemOperation()
const {
return MemOperation; }
153 MachineInstr *getCheckOperation()
const {
return CheckOperation; }
161 MachineInstr *getOnlyDependency()
const {
return OnlyDependency; }
178 AR_WillAliasEverything
187 enum SuitabilityResult {
206 bool canDependenceHoistingClobberLiveIns(
MachineInstr *DependenceMI,
239 if (
MI->isCall() ||
MI->mayRaiseFPException() ||
240 MI->hasUnmodeledSideEffects())
242 auto IsRegMask = [](
const MachineOperand &MO) {
return MO.isRegMask(); };
246 "Calls were filtered out above!");
252 ImplicitNullChecks::DependenceResult
261 if (canReorder(*
I,
MI))
269 return {
false,
None};
276 bool ImplicitNullChecks::canReorder(
const MachineInstr *A,
278 assert(canHandle(A) && canHandle(
B) &&
"Precondition!");
284 for (
const auto &MOA :
A->operands()) {
285 if (!(MOA.isReg() && MOA.getReg()))
289 for (
const auto &MOB :
B->operands()) {
290 if (!(MOB.isReg() && MOB.getReg()))
307 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
312 analyzeBlockForNullChecks(
MBB, NullCheckList);
314 if (!NullCheckList.empty())
315 rewriteNullChecks(NullCheckList);
317 return !NullCheckList.empty();
330 ImplicitNullChecks::AliasResult
341 if (
MI.memoperands_empty())
342 return MI.mayStore() ? AR_WillAliasEverything : AR_MayAlias;
344 return PrevMI->
mayStore() ? AR_WillAliasEverything : AR_MayAlias;
349 assert(MMO1->getValue() &&
"MMO1 should have a Value!");
352 if (PSV->mayAlias(MFI))
365 ImplicitNullChecks::SuitabilityResult
371 if (
MI.getDesc().getNumDefs() > 1)
372 return SR_Unsuitable;
374 if (!
MI.mayLoadOrStore() ||
MI.isPredicable())
375 return SR_Unsuitable;
376 auto AM =
TII->getAddrModeFromMemoryOp(
MI,
TRI);
378 return SR_Unsuitable;
381 int64_t Displacement =
AddrMode.Displacement;
385 if (BaseReg != PointerReg && ScaledReg != PointerReg)
386 return SR_Unsuitable;
395 return SR_Unsuitable;
399 auto CalculateDisplacementFromAddrMode = [&](
Register RegUsedInAddr,
400 int64_t Multiplier) {
406 assert(Multiplier &&
"expected to be non-zero!");
409 It !=
MI.getParent()->
rend(); It++) {
421 if (!
TII->getConstValDefinedInReg(*ModifyingMI, RegUsedInAddr, ImmVal))
426 APInt ImmValC(RegSizeInBits, ImmVal,
true );
427 APInt MultiplierC(RegSizeInBits, Multiplier);
428 assert(MultiplierC.isStrictlyPositive() &&
429 "expected to be a positive value!");
433 APInt Product = ImmValC.
smul_ov(MultiplierC, IsOverflow);
436 APInt DisplacementC(64, Displacement,
true );
437 DisplacementC = Product.
sadd_ov(DisplacementC, IsOverflow);
442 if (DisplacementC.getActiveBits() > 64)
450 bool BaseRegIsConstVal =
false, ScaledRegIsConstVal =
false;
451 if (CalculateDisplacementFromAddrMode(BaseReg, 1))
452 BaseRegIsConstVal =
true;
453 if (CalculateDisplacementFromAddrMode(ScaledReg,
AddrMode.Scale))
454 ScaledRegIsConstVal =
true;
461 if ((BaseReg && BaseReg != PointerReg && !BaseRegIsConstVal) ||
462 (ScaledReg && ScaledReg != PointerReg && !ScaledRegIsConstVal))
463 return SR_Unsuitable;
468 return SR_Unsuitable;
471 for (
auto *PrevMI : PrevInsts) {
473 if (AR == AR_WillAliasEverything)
474 return SR_Impossible;
475 if (AR == AR_MayAlias)
476 return SR_Unsuitable;
481 bool ImplicitNullChecks::canDependenceHoistingClobberLiveIns(
483 for (
const auto &DependenceMO : DependenceMI->
operands()) {
484 if (!(DependenceMO.isReg() && DependenceMO.getReg()))
513 bool ImplicitNullChecks::canHoistInst(
MachineInstr *FaultingMI,
517 auto DepResult = computeDependence(FaultingMI, InstsSeenSoFar);
518 if (!DepResult.CanReorder)
521 if (!DepResult.PotentialDependence) {
526 auto DependenceItr = *DepResult.PotentialDependence;
527 auto *DependenceMI = *DependenceItr;
534 assert(canHandle(DependenceMI) &&
"Should never have reached here!");
538 if (canDependenceHoistingClobberLiveIns(DependenceMI, NullSucc))
542 computeDependence(DependenceMI, {InstsSeenSoFar.
begin(), DependenceItr});
544 if (!DepDepResult.CanReorder || DepDepResult.PotentialDependence)
554 bool ImplicitNullChecks::analyzeBlockForNullChecks(
558 MDNode *BranchMD =
nullptr;
560 BranchMD =
BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit);
565 MachineBranchPredicate MBP;
567 if (
TII->analyzeBranchPredicate(
MBB, MBP,
true))
571 if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
578 if (MBP.ConditionDef && !MBP.SingleUseCondition)
584 NotNullSucc = MBP.TrueDest;
585 NullSucc = MBP.FalseDest;
587 NotNullSucc = MBP.FalseDest;
588 NullSucc = MBP.TrueDest;
596 const Register PointerReg = MBP.LHS.getReg();
598 if (MBP.ConditionDef) {
617 assert(MBP.ConditionDef->getParent() == &
MBB &&
618 "Should be in basic block");
620 for (
auto I =
MBB.
rbegin(); MBP.ConditionDef != &*
I; ++
I)
621 if (
I->modifiesRegister(PointerReg,
TRI))
680 for (
auto &
MI : *NotNullSucc) {
685 SuitabilityResult SR = isSuitableMemoryOp(
MI, PointerReg, InstsSeenSoFar);
686 if (SR == SR_Impossible)
688 if (SR == SR_Suitable &&
689 canHoistInst(&
MI, InstsSeenSoFar, NullSucc,
Dependence)) {
697 if (!
TII->preservesZeroValueInReg(&
MI, PointerReg,
TRI))
699 InstsSeenSoFar.push_back(&
MI);
711 const unsigned NoRegister = 0;
715 unsigned NumDefs =
MI->getDesc().getNumDefs();
716 assert(NumDefs <= 1 &&
"other cases unhandled!");
718 unsigned DefReg = NoRegister;
720 DefReg =
MI->getOperand(0).getReg();
721 assert(NumDefs == 1 &&
"expected exactly one def!");
731 auto MIB =
BuildMI(
MBB,
DL,
TII->get(TargetOpcode::FAULTING_OP), DefReg)
736 for (
auto &MO :
MI->uses()) {
742 assert(MO.isDef() &&
"Expected def or use");
751 MIB.setMemRefs(
MI->memoperands());
757 void ImplicitNullChecks::rewriteNullChecks(
761 for (
auto &
NC : NullCheckList) {
764 (void)BranchesRemoved;
765 assert(BranchesRemoved > 0 &&
"expected at least one branch!");
767 if (
auto *DepMI =
NC.getOnlyDependency()) {
768 DepMI->removeFromParent();
769 NC.getCheckBlock()->insert(
NC.getCheckBlock()->end(), DepMI);
777 NC.getMemOperation(),
NC.getCheckBlock(),
NC.getNullSucc());
784 if (!MO.isReg() || !MO.isDef())
792 if (
auto *DepMI =
NC.getOnlyDependency()) {
793 for (
auto &MO : DepMI->operands()) {
794 if (!MO.isReg() || !MO.getReg() || !MO.isDef() || MO.isDead())
796 if (!
NC.getNotNullSucc()->isLiveIn(MO.getReg()))
797 NC.getNotNullSucc()->addLiveIn(MO.getReg());
801 NC.getMemOperation()->eraseFromParent();
802 if (
auto *CheckOp =
NC.getCheckOperation())
803 CheckOp->eraseFromParent();
810 NumImplicitNullChecks++;
819 "Implicit null checks",
false,
false)
APInt sadd_ov(const APInt &RHS, bool &Overflow) const
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
This is an optimization pass for GlobalISel generic memory operations.
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::Hidden, cl::init(8))
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Represents a predicate at the MachineFunction level.
bool mayLoadOrStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read or modify memory.
virtual const TargetInstrInfo * getInstrInfo() const
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
void setIsKill(bool Val=true)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
int64_t getSExtValue() const
Get sign extended value.
Reg
All possible values of the reg field in the ModR/M byte.
const TargetRegisterInfo * getTargetRegisterInfo() const
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Dependence - This class represents a dependence between two memory memory references in a function.
INITIALIZE_PASS_BEGIN(ImplicitNullChecks, DEBUG_TYPE, "Implicit null checks", false, false) INITIALIZE_PASS_END(ImplicitNullChecks
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
A description of a memory reference used in the backend.
Properties which a MachineFunction may have at a given point in time.
The possible results of an alias query.
unsigned const TargetRegisterInfo * TRI
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
unsigned pred_size() const
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
TargetInstrInfo - Interface to description of machine instruction set.
static cl::opt< int > PageSize("imp-null-check-page-size", cl::desc("The page size of the target in bytes"), cl::init(4096), cl::Hidden)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Represent the analysis usage information of a pass.
const HexagonInstrInfo * TII
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
MachineOperand class - Representation of each machine instruction operand.
MachineFunctionProperties & set(Property P)
STATISTIC(NumFunctions, "Total number of functions")
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.
Special value supplied for machine level alias analysis.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
@ Implicit
Not emitted register (e.g. carry, or temporary result).
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void setIsDead(bool Val=true)
bool regsOverlap(Register RegA, Register RegB) const
Returns true if the two registers are equal or alias each other.
Representation of each machine instruction.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
initializer< Ty > init(const Ty &Val)
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
Class for arbitrary precision integers.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
reverse_iterator rbegin()
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
void initializeImplicitNullChecksPass(PassRegistry &)
unsigned const MachineRegisterInfo * MRI
Wrapper class representing virtual and physical registers.
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
bool modifiesRegister(Register Reg, const TargetRegisterInfo *TRI=nullptr) const
Return true if the MachineInstr modifies (fully define or partially define) the specified register.
unsigned getRegSizeInBits(const TargetRegisterClass &RC) const
Return the size in bits of a register from class RC.
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool memoperands_empty() const
Return true if we don't have any memory operands which described the memory access done by this instr...
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
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 wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
ArrayRef< MachineMemOperand * > memoperands() const
Access to memory operands of the instruction.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reverse_iterator rend(StringRef path)
Get reverse end iterator over path.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
char & ImplicitNullChecksID
ImplicitNullChecks - This pass folds null pointer checks into nearby memory operations.
AnalysisUsage & addRequired()
MachineBasicBlock iterator that automatically skips over MIs that are inside bundles (i....
iterator_range< mop_iterator > operands()
MCRegAliasIterator enumerates all registers aliasing Reg.
reference emplace_back(ArgTypes &&... Args)
static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI, MachineBasicBlock *MBB, unsigned Reg)