ImplicitNullChecks.cpp Source File (original) (raw)

56#include

57#include

58#include

60using namespace llvm;

63 cl::desc("The page size of the target in bytes"),

67 "imp-null-max-insts-to-consider",

68 cl::desc("The max number of instructions to consider hoisting loads over "

69 "(the algorithm is quadratic over this number)"),

72#define DEBUG_TYPE "implicit-null-checks"

75 "Number of explicit null checks made implicit");

77namespace {

92 struct DependenceResult {

95 bool CanReorder;

99 std::optional<ArrayRef<MachineInstr *>::iterator> PotentialDependence;

100

101 DependenceResult(

102 bool CanReorder,

104 : CanReorder(CanReorder), PotentialDependence(PotentialDependence) {

105 assert((!PotentialDependence || CanReorder) &&

106 "!CanReorder && PotentialDependence.hasValue() not allowed!");

107 }

108 };

109

110

111

112

113

114

115 DependenceResult computeDependence(const MachineInstr *MI,

117

118

119 class NullCheck {

120

122

123

125

126

128

129

131

132

134

135

136

138

139 public:

145 : MemOperation(memOperation), CheckOperation(checkOperation),

146 CheckBlock(checkBlock), NotNullSucc(notNullSucc), NullSucc(nullSucc),

147 OnlyDependency(onlyDependency) {}

148

149 MachineInstr *getMemOperation() const { return MemOperation; }

150

151 MachineInstr *getCheckOperation() const { return CheckOperation; }

152

154

155 MachineBasicBlock *getNotNullSucc() const { return NotNullSucc; }

156

158

159 MachineInstr *getOnlyDependency() const { return OnlyDependency; }

160 };

161

166

172

174 AR_NoAlias,

175 AR_MayAlias,

176 AR_WillAliasEverything

177 };

178

179

180

181

184

185 enum SuitabilityResult {

186 SR_Suitable,

187 SR_Unsuitable,

188 SR_Impossible

189 };

190

191

192

193

194

195

196

197 SuitabilityResult isSuitableMemoryOp(const MachineInstr &MI,

198 unsigned PointerReg,

200

201

202

203

204 bool canDependenceHoistingClobberLiveIns(MachineInstr *DependenceMI,

206

207

208

209

213

214public:

215 static char ID;

216

219 }

220

222

226 }

227

230 MachineFunctionProperties::Property::NoVRegs);

231 }

232};

233

234}

235

236bool ImplicitNullChecks::canHandle(const MachineInstr *MI) {

237 if (MI->isCall() || MI->mayRaiseFPException() ||

238 MI->hasUnmodeledSideEffects())

239 return false;

240 auto IsRegMask = [](const MachineOperand &MO) { return MO.isRegMask(); };

241 (void)IsRegMask;

242

244 "Calls were filtered out above!");

245

246 auto IsUnordered = [](MachineMemOperand *MMO) { return MMO->isUnordered(); };

248}

249

250ImplicitNullChecks::DependenceResult

251ImplicitNullChecks::computeDependence(const MachineInstr *MI,

255

256 std::optional<ArrayRef<MachineInstr *>::iterator> Dep;

257

258 for (auto I = Block.begin(), E = Block.end(); I != E; ++I) {

259 if (canReorder(*I, MI))

260 continue;

261

262 if (Dep == std::nullopt) {

263

264 Dep = I;

265 } else {

266

267 return {false, std::nullopt};

268 }

269 }

270

271 return {true, Dep};

272}

273

274bool ImplicitNullChecks::canReorder(const MachineInstr *A,

276 assert(canHandle(A) && canHandle(B) && "Precondition!");

277

278

279

280

281

282 for (const auto &MOA : A->operands()) {

283 if (!(MOA.isReg() && MOA.getReg()))

284 continue;

285

286 Register RegA = MOA.getReg();

287 for (const auto &MOB : B->operands()) {

288 if (!(MOB.isReg() && MOB.getReg()))

289 continue;

290

291 Register RegB = MOB.getReg();

292

293 if (TRI->regsOverlap(RegA, RegB) && (MOA.isDef() || MOB.isDef()))

294 return false;

295 }

296 }

297

298 return true;

299}

300

301bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {

305 AA = &getAnalysis().getAAResults();

306

308

309 for (auto &MBB : MF)

310 analyzeBlockForNullChecks(MBB, NullCheckList);

311

312 if (!NullCheckList.empty())

313 rewriteNullChecks(NullCheckList);

314

315 return !NullCheckList.empty();

316}

317

318

322 ++AR)

324 return true;

325 return false;

326}

327

328ImplicitNullChecks::AliasResult

329ImplicitNullChecks::areMemoryOpsAliased(const MachineInstr &MI,

331

333 return AR_NoAlias;

334

335 if (!(MI.mayStore() || PrevMI->mayStore()))

336 return AR_NoAlias;

337

338

339 if (MI.memoperands_empty())

340 return MI.mayStore() ? AR_WillAliasEverything : AR_MayAlias;

342 return PrevMI->mayStore() ? AR_WillAliasEverything : AR_MayAlias;

343

345

346

347 assert(MMO1->getValue() && "MMO1 should have a Value!");

350 if (PSV->mayAlias(MFI))

351 return AR_MayAlias;

352 continue;

353 }

357 return AR_MayAlias;

358 }

359 }

360 return AR_NoAlias;

361}

362

363ImplicitNullChecks::SuitabilityResult

364ImplicitNullChecks::isSuitableMemoryOp(const MachineInstr &MI,

365 unsigned PointerReg,

367

368

369 if (MI.getDesc().getNumDefs() > 1)

370 return SR_Unsuitable;

371

372 if (.mayLoadOrStore() || MI.isPredicable())

373 return SR_Unsuitable;

374 auto AM = TII->getAddrModeFromMemoryOp(MI, TRI);

375 if (!AM || AM->Form != ExtAddrMode::Formula::Basic)

376 return SR_Unsuitable;

379 int64_t Displacement = AddrMode.Displacement;

380

381

382

383 if (BaseReg != PointerReg && ScaledReg != PointerReg)

384 return SR_Unsuitable;

386 unsigned PointerRegSizeInBits = TRI->getRegSizeInBits(PointerReg, MRI);

387

388

389 if ((BaseReg &&

390 TRI->getRegSizeInBits(BaseReg, MRI) != PointerRegSizeInBits) ||

391 (ScaledReg &&

392 TRI->getRegSizeInBits(ScaledReg, MRI) != PointerRegSizeInBits))

393 return SR_Unsuitable;

394

395

396

397 auto CalculateDisplacementFromAddrMode = [&](Register RegUsedInAddr,

398 int64_t Multiplier) {

399

400

401

402 if (!RegUsedInAddr)

403 return false;

404 assert(Multiplier && "expected to be non-zero!");

407 It != MI.getParent()->rend(); It++) {

410 ModifyingMI = const_cast<MachineInstr *>(CurrMI);

411 break;

412 }

413 }

414 if (!ModifyingMI)

415 return false;

416

417

418 int64_t ImmVal;

419 if ( TII ->getConstValDefinedInReg(*ModifyingMI, RegUsedInAddr, ImmVal))

420 return false;

421

422

423 int32_t RegSizeInBits = TRI->getRegSizeInBits(RegUsedInAddr, MRI);

424 APInt ImmValC(RegSizeInBits, ImmVal, true );

425 APInt MultiplierC(RegSizeInBits, Multiplier);

426 assert(MultiplierC.isStrictlyPositive() &&

427 "expected to be a positive value!");

428 bool IsOverflow;

429

430

431 APInt Product = ImmValC.smul_ov(MultiplierC, IsOverflow);

432 if (IsOverflow)

433 return false;

434 APInt DisplacementC(64, Displacement, true );

435 DisplacementC = Product.sadd_ov(DisplacementC, IsOverflow);

436 if (IsOverflow)

437 return false;

438

439

440 if (DisplacementC.getActiveBits() > 64)

441 return false;

443 return true;

444 };

445

446

447

448 bool BaseRegIsConstVal = false, ScaledRegIsConstVal = false;

449 if (CalculateDisplacementFromAddrMode(BaseReg, 1))

450 BaseRegIsConstVal = true;

451 if (CalculateDisplacementFromAddrMode(ScaledReg, AddrMode.Scale))

452 ScaledRegIsConstVal = true;

453

454

455

456

457

458

459 if ((BaseReg && BaseReg != PointerReg && !BaseRegIsConstVal) ||

460 (ScaledReg && ScaledReg != PointerReg && !ScaledRegIsConstVal))

461 return SR_Unsuitable;

462

463

464

466 return SR_Unsuitable;

467

468

469 for (auto *PrevMI : PrevInsts) {

470 AliasResult AR = areMemoryOpsAliased(MI, PrevMI);

471 if (AR == AR_WillAliasEverything)

472 return SR_Impossible;

473 if (AR == AR_MayAlias)

474 return SR_Unsuitable;

475 }

476 return SR_Suitable;

477}

478

479bool ImplicitNullChecks::canDependenceHoistingClobberLiveIns(

481 for (const auto &DependenceMO : DependenceMI->operands()) {

482 if (!(DependenceMO.isReg() && DependenceMO.getReg()))

483 continue;

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

503 return true;

504

505 }

506

507

508 return false;

509}

510

511bool ImplicitNullChecks::canHoistInst(MachineInstr *FaultingMI,

515 auto DepResult = computeDependence(FaultingMI, InstsSeenSoFar);

516 if (!DepResult.CanReorder)

517 return false;

518

519 if (!DepResult.PotentialDependence) {

521 return true;

522 }

523

524 auto DependenceItr = *DepResult.PotentialDependence;

525 auto *DependenceMI = *DependenceItr;

526

527

528

529

530

531

532 assert(canHandle(DependenceMI) && "Should never have reached here!");

534 return false;

535

536 if (canDependenceHoistingClobberLiveIns(DependenceMI, NullSucc))

537 return false;

538

539 auto DepDepResult =

540 computeDependence(DependenceMI, {InstsSeenSoFar.begin(), DependenceItr});

541

542 if (!DepDepResult.CanReorder || DepDepResult.PotentialDependence)

543 return false;

544

546 return true;

547}

548

549

550

551

552bool ImplicitNullChecks::analyzeBlockForNullChecks(

555

556 MDNode *BranchMD = nullptr;

558 BranchMD = BB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit);

559

560 if (!BranchMD)

561 return false;

562

563 MachineBranchPredicate MBP;

564

565 if (TII->analyzeBranchPredicate(MBB, MBP, true))

566 return false;

567

568

569 if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&

570 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||

571 MBP.Predicate == MachineBranchPredicate::PRED_EQ)))

572 return false;

573

574

575

576 if (MBP.ConditionDef && !MBP.SingleUseCondition)

577 return false;

578

580

581 if (MBP.Predicate == MachineBranchPredicate::PRED_NE) {

582 NotNullSucc = MBP.TrueDest;

583 NullSucc = MBP.FalseDest;

584 } else {

585 NotNullSucc = MBP.FalseDest;

586 NullSucc = MBP.TrueDest;

587 }

588

589

590

591 if (NotNullSucc->pred_size() != 1)

592 return false;

593

594 const Register PointerReg = MBP.LHS.getReg();

595

596 if (MBP.ConditionDef) {

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615 assert(MBP.ConditionDef->getParent() == &MBB &&

616 "Should be in basic block");

617

618 for (auto I = MBB.rbegin(); MBP.ConditionDef != &*I; ++I)

619 if (I->modifiesRegister(PointerReg, TRI))

620 return false;

621 }

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646

647

648

649

650

651

652

653

654

655

656

657

658

659

660

661

662

663

664

665

666

667

668

669

670

671

672

673

674

675

677

678 for (auto &MI : *NotNullSucc) {

680 return false;

681

683 SuitabilityResult SR = isSuitableMemoryOp(MI, PointerReg, InstsSeenSoFar);

684 if (SR == SR_Impossible)

685 return false;

686 if (SR == SR_Suitable &&

687 canHoistInst(&MI, InstsSeenSoFar, NullSucc, Dependence)) {

688 NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc,

690 return true;

691 }

692

693

694

695 if ( TII ->preservesZeroValueInReg(&MI, PointerReg, TRI))

696 return false;

698 }

699

700 return false;

701}

702

703

704

705

706

707MachineInstr *ImplicitNullChecks::insertFaultingInstr(

709 const unsigned NoRegister = 0;

710

711

713 unsigned NumDefs = MI->getDesc().getNumDefs();

714 assert(NumDefs <= 1 && "other cases unhandled!");

715

716 unsigned DefReg = NoRegister;

717 if (NumDefs != 0) {

718 DefReg = MI->getOperand(0).getReg();

719 assert(NumDefs == 1 && "expected exactly one def!");

720 }

721

723 if (MI->mayLoad())

724 FK =

726 else

728

729 auto MIB = BuildMI(MBB, DL, TII->get(TargetOpcode::FAULTING_OP), DefReg)

733

734 for (auto &MO : MI->uses()) {

735 if (MO.isReg()) {

737 if (MO.isUse()) {

739 } else {

740 assert(MO.isDef() && "Expected def or use");

742 }

743 MIB.add(NewMO);

744 } else {

745 MIB.add(MO);

746 }

747 }

748

749 MIB.setMemRefs(MI->memoperands());

750

751 return MIB;

752}

753

754

755void ImplicitNullChecks::rewriteNullChecks(

758

759 for (const auto &NC : NullCheckList) {

760

761 unsigned BranchesRemoved = TII->removeBranch(*NC.getCheckBlock());

762 (void)BranchesRemoved;

763 assert(BranchesRemoved > 0 && "expected at least one branch!");

764

765 if (auto *DepMI = NC.getOnlyDependency()) {

766 DepMI->removeFromParent();

767 NC.getCheckBlock()->insert(NC.getCheckBlock()->end(), DepMI);

768 }

769

770

771

772

773

774 MachineInstr *FaultingInstr = insertFaultingInstr(

775 NC.getMemOperation(), NC.getCheckBlock(), NC.getNullSucc());

776

777

778

779

784 continue;

786 }

787

788 if (auto *DepMI = NC.getOnlyDependency()) {

789 for (auto &MO : DepMI->all_defs()) {

790 if (!MO.getReg() || MO.isDead())

791 continue;

792 if (.getNotNullSucc()->isLiveIn(MO.getReg()))

793 NC.getNotNullSucc()->addLiveIn(MO.getReg());

794 }

795 }

796

797 NC.getMemOperation()->eraseFromParent();

798 if (auto *CheckOp = NC.getCheckOperation())

799 CheckOp->eraseFromParent();

800

801

802

804 {}, DL);

805

806 NumImplicitNullChecks++;

807 }

808}

809

810char ImplicitNullChecks::ID = 0;

811

813

815 "Implicit null checks", false, false)

unsigned const MachineRegisterInfo * MRI

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

const HexagonInstrInfo * TII

static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI, MachineBasicBlock *MBB, unsigned Reg)

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 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))

unsigned const TargetRegisterInfo * TRI

This file provides utility analysis objects describing memory locations.

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

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)

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.

Class for arbitrary precision integers.

APInt sadd_ov(const APInt &RHS, bool &Overflow) const

APInt smul_ov(const APInt &RHS, bool &Overflow) const

int64_t getSExtValue() const

Get sign extended value.

The possible results of an alias query.

Represent the analysis usage information of a pass.

AnalysisUsage & addRequired()

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

Dependence - This class represents a dependence between two memory memory references in a function.

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.

MCRegAliasIterator enumerates all registers aliasing Reg.

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.

reverse_iterator rbegin()

bool isLiveIn(MCRegister Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const

Return true if the specified register is in the live in set.

The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.

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.

virtual bool runOnMachineFunction(MachineFunction &MF)=0

runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...

virtual MachineFunctionProperties getRequiredProperties() const

Properties which a MachineFunction may have at a given point in time.

MachineFunctionProperties & set(Property P)

const TargetSubtargetInfo & getSubtarget() const

getSubtarget - Return the subtarget for which this machine code is being compiled.

MachineFrameInfo & getFrameInfo()

getFrameInfo - Return the frame info object for the current function.

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

const MachineInstrBuilder & addImm(int64_t Val) const

Add a new immediate operand.

const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const

MachineBasicBlock iterator that automatically skips over MIs that are inside bundles (i....

Representation of each machine instruction.

bool mayLoadOrStore(QueryType Type=AnyInBundle) const

Return true if this instruction could possibly read or modify memory.

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.

iterator_range< mop_iterator > operands()

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.

iterator_range< filtered_mop_iterator > all_defs()

Returns an iterator range over all operands that are (explicit or implicit) register defs.

A description of a memory reference used in the backend.

MachineOperand class - Representation of each machine instruction operand.

void setIsDead(bool Val=true)

void setIsKill(bool Val=true)

MachineRegisterInfo - Keep track of information for virtual and physical registers,...

const TargetRegisterInfo * getTargetRegisterInfo() 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...

static PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

Special value supplied for machine level alias analysis.

Wrapper class representing virtual and physical registers.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

TargetInstrInfo - Interface to description of machine instruction set.

TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...

virtual const TargetInstrInfo * getInstrInfo() const

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

Reg

All possible values of the reg field in the ModR/M byte.

initializer< Ty > init(const Ty &Val)

reverse_iterator rend(StringRef path LLVM_LIFETIME_BOUND)

Get reverse end iterator over path.

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.

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.

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

void initializeImplicitNullChecksPass(PassRegistry &)

Represents a predicate at the MachineFunction level.