SafepointIRVerifier.cpp Source File (original) (raw)

51#define DEBUG_TYPE "safepoint-ir-verifier"

53using namespace llvm;

61namespace {

69class CFGDeadness {

74public:

77 auto &PU = PredIt.getUse();

79 }

83 bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {

84 assert(!isDeadBlock(InBB) && "block must be live");

86 bool Listed = false;

87 for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {

88 if (InBB == *PredIt) {

89 if (!isDeadEdge(&getEdge(PredIt)))

90 return true;

91 Listed = true;

92 }

93 }

94 (void)Listed;

95 assert(Listed && "basic block is not found among incoming blocks");

96 return false;

97 }

100 bool isDeadBlock(const BasicBlock *BB) const {

101 return DeadBlocks.count(BB);

102 }

103

104 bool isDeadEdge(const Use *U) const {

106 "edge must be operand of terminator");

108 "edge must refer to basic block");

110 "isDeadEdge() must be applied to edge from live block");

111 return DeadEdges.count(U);

112 }

113

114 bool hasLiveIncomingEdges(const BasicBlock *BB) const {

115

116 for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {

117 auto &PU = PredIt.getUse();

118 const Use &U = PU.getUser()->getOperandUse(PU.getOperandNo());

119 if (!isDeadBlock(*PredIt) && !isDeadEdge(&U))

120 return true;

121 }

122 return false;

123 }

124

125 void processFunction(const Function &F, const DominatorTree &DT) {

126 this->DT = &DT;

127

128

129 for (const BasicBlock &BB : F)

130 if (!DT.isReachableFromEntry(&BB))

131 DeadBlocks.insert(&BB);

132

133

134 ReversePostOrderTraversal<const Function *> RPOT(&F);

135 for (const BasicBlock *BB : RPOT) {

137 assert(TI && "blocks must be well formed");

138

139

140

143 continue;

144

145

147 continue;

148

151 continue;

152

154 }

155 }

156

157protected:

158 void addDeadBlock(const BasicBlock *BB) {

160

162 while (!NewDead.empty()) {

164 if (isDeadBlock(D))

165 continue;

166

167

168 SmallVector<BasicBlock *, 8> Dom;

169 DT->getDescendants(const_cast<BasicBlock*>(D), Dom);

170

171

172

173 DeadBlocks.insert_range(Dom);

174

175

176 for (BasicBlock *B : Dom)

178 if (!isDeadBlock(S) && !hasLiveIncomingEdges(S))

180 }

181 }

182

183 void addDeadEdge(const Use &DeadEdge) {

184 if (!DeadEdges.insert(&DeadEdge))

185 return;

186

188 if (hasLiveIncomingEdges(BB))

189 return;

190

191 addDeadBlock(BB);

192 }

193};

194}

195

197 const CFGDeadness &CD);

198

202 CFGDeadness CD;

203 CD.processFunction(F, DT);

206}

207

208namespace {

209

210struct SafepointIRVerifier : public FunctionPass {

211 static char ID;

214 }

215

217 auto &DT = getAnalysis().getDomTree();

218 CFGDeadness CD;

219 CD.processFunction(F, DT);

221 return false;

222 }

223

224 void getAnalysisUsage(AnalysisUsage &AU) const override {

227 }

228

229 StringRef getPassName() const override { return "safepoint verifier"; }

230};

231}

232

234 SafepointIRVerifier pass;

235 pass.runOnFunction(F);

236}

237

238char SafepointIRVerifier::ID = 0;

239

241 return new SafepointIRVerifier();

242}

243

245 "Safepoint IR Verifier", false, false)

249

252

253

254

255 return (1 == PT->getAddressSpace());

256 return false;

257}

258

261 return true;

268 return false;

269}

270

271

272template

274 OS << "[ ";

275 while (Begin != End) {

276 OS << **Begin << " ";

277 ++Begin;

278 }

279 OS << "]";

280}

281

282

283

284

285

286

288

289namespace {

290

291struct BasicBlockState {

292

294

295

297

298

299

301

302

303

304 bool Cleared = false;

305};

306}

307

308

309

310

311

312

320

321

322

323

324

326

329 bool isExclusivelyDerivedFromNull = true;

331

332

333

334 while(!Worklist.empty()) {

336 if (!Visited.insert(V).second)

337 continue;

338

340 Worklist.push_back(CI->stripPointerCasts());

341 continue;

342 }

344 Worklist.push_back(GEP->getPointerOperand());

345 continue;

346 }

347

348

351 continue;

352 }

354

357 continue;

358 }

360

361

362 Worklist.push_back(GCRelocate->getDerivedPtr());

363 continue;

364 }

366

367 Worklist.push_back(FI->getOperand(0));

368 continue;

369 }

371

372

374 isExclusivelyDerivedFromNull = false;

375

376

377 continue;

378 }

379

380

382 }

383

384

387}

388

392

393namespace {

394class InstructionVerifier;

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452class GCPtrTracker {

454 const CFGDeadness &CD;

455 SpecificBumpPtrAllocator BSAllocator;

456 DenseMap<const BasicBlock *, BasicBlockState *> BlockMap;

457

458

459 DenseSet<const Instruction *> ValidUnrelocatedDefs;

460

461

462 DenseSet<const Value *> PoisonedDefs;

463

464public:

465 GCPtrTracker(const Function &F, const DominatorTree &DT,

466 const CFGDeadness &CD);

467

468 bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {

469 return CD.hasLiveIncomingEdge(PN, InBB);

470 }

471

472 BasicBlockState *getBasicBlockState(const BasicBlock *BB);

473 const BasicBlockState *getBasicBlockState(const BasicBlock *BB) const;

474

475 bool isValuePoisoned(const Value *V) const { return PoisonedDefs.count(V); }

476

477

478

479

480

481

482

484 InstructionVerifier &Verifier);

485

486

487 bool isMapped(const BasicBlock *BB) const { return BlockMap.contains(BB); }

488

489private:

490

491 bool instructionMayBeSkipped(const Instruction *I) const;

492

493

494

495 void recalculateBBsStates();

496

497

498

499

500

501

502

503 bool removeValidUnrelocatedDefs(const BasicBlock *BB,

504 const BasicBlockState *BBS,

506

507

508

509

510 void gatherDominatingDefs(const BasicBlock *BB, AvailableValueSet &Result,

511 const DominatorTree &DT);

512

513

514

515

516

517

518 static void transferBlock(const BasicBlock *BB, BasicBlockState &BBS,

519 bool ContributionChanged);

520

521

522 static void transferInstruction(const Instruction &I, bool &Cleared,

524};

525

526

527

528

529class InstructionVerifier {

530 bool AnyInvalidUses = false;

531

532public:

533 void verifyInstruction(const GCPtrTracker *Tracker, const Instruction &I,

535

536 bool hasAnyInvalidUses() const { return AnyInvalidUses; }

537

538private:

539 void reportInvalidUse(const Value &V, const Instruction &I);

540};

541}

542

544 const CFGDeadness &CD) : F(F), CD(CD) {

545

546

548 if (!CD.isDeadBlock(&BB)) {

549 BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState;

550 for (const auto &I : BB)

551 transferInstruction(I, BBS->Cleared, BBS->Contribution);

552 BlockMap[&BB] = BBS;

553 }

554

555

556

557 for (auto &BBI : BlockMap) {

558 gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT);

559 transferBlock(BBI.first, *BBI.second, true);

560 }

561

562

563

564

565 recalculateBBsStates();

566}

567

568BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) {

569 return BlockMap.lookup(BB);

570}

571

572const BasicBlockState *GCPtrTracker::getBasicBlockState(

573 const BasicBlock *BB) const {

574 return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB);

575}

576

577bool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const {

578

579

580 return ValidUnrelocatedDefs.count(I) || PoisonedDefs.count(I);

581}

582

583void GCPtrTracker::verifyFunction(GCPtrTracker &&Tracker,

584 InstructionVerifier &Verifier) {

585

586

587 ReversePostOrderTraversal<const Function *> RPOT(&Tracker.F);

588 for (const BasicBlock *BB : RPOT) {

589 BasicBlockState *BBS = Tracker.getBasicBlockState(BB);

590 if (!BBS)

591 continue;

592

593

594

596 for (const Instruction &I : *BB) {

597 if (Tracker.instructionMayBeSkipped(&I))

598 continue;

599

600 Verifier.verifyInstruction(&Tracker, I, AvailableSet);

601

602

603

604 bool Cleared = false;

605 transferInstruction(I, Cleared, AvailableSet);

606 (void)Cleared;

607 }

608 }

609}

610

611void GCPtrTracker::recalculateBBsStates() {

612

613

616

617

618

619 while (!Worklist.empty()) {

620 const BasicBlock *BB = Worklist.pop_back_val();

621 BasicBlockState *BBS = getBasicBlockState(BB);

622 if (!BBS)

623 continue;

624

625 size_t OldInCount = BBS->AvailableIn.size();

626 for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {

628 BasicBlockState *PBBS = getBasicBlockState(PBB);

629 if (PBBS && !CD.isDeadEdge(&CFGDeadness::getEdge(PredIt)))

630 set_intersect(BBS->AvailableIn, PBBS->AvailableOut);

631 }

632

633 assert(OldInCount >= BBS->AvailableIn.size() && "invariant!");

634

635 bool InputsChanged = OldInCount != BBS->AvailableIn.size();

636 bool ContributionChanged =

637 removeValidUnrelocatedDefs(BB, BBS, BBS->Contribution);

638 if (!InputsChanged && !ContributionChanged)

639 continue;

640

641 size_t OldOutCount = BBS->AvailableOut.size();

642 transferBlock(BB, *BBS, ContributionChanged);

643 if (OldOutCount != BBS->AvailableOut.size()) {

644 assert(OldOutCount > BBS->AvailableOut.size() && "invariant!");

645 Worklist.insert_range(successors(BB));

646 }

647 }

648}

649

650bool GCPtrTracker::removeValidUnrelocatedDefs(const BasicBlock *BB,

651 const BasicBlockState *BBS,

653 assert(&BBS->Contribution == &Contribution &&

654 "Passed Contribution should be from the passed BasicBlockState!");

656 bool ContributionChanged = false;

657

658

659 for (const Instruction &I : *BB) {

660 bool ValidUnrelocatedPointerDef = false;

661 bool PoisonedPointerDef = false;

662

665

666 bool HasRelocatedInputs = false;

667 bool HasUnrelocatedInputs = false;

670 if (!isMapped(InBB) ||

671 !CD.hasLiveIncomingEdge(PN, InBB))

672 continue;

673

675

677 if (isValuePoisoned(InValue)) {

678

679 HasRelocatedInputs = true;

680 HasUnrelocatedInputs = true;

681 break;

682 }

683 if (BlockMap[InBB]->AvailableOut.count(InValue))

684 HasRelocatedInputs = true;

685 else

686 HasUnrelocatedInputs = true;

687 }

688 }

689 if (HasUnrelocatedInputs) {

690 if (HasRelocatedInputs)

691 PoisonedPointerDef = true;

692 else

693 ValidUnrelocatedPointerDef = true;

694 }

695 }

698

699

700 for (const Value *V : I.operands())

703 if (isValuePoisoned(V))

704 PoisonedPointerDef = true;

705 else

706 ValidUnrelocatedPointerDef = true;

707 break;

708 }

709 }

710 assert(!(ValidUnrelocatedPointerDef && PoisonedPointerDef) &&

711 "Value cannot be both unrelocated and poisoned!");

712 if (ValidUnrelocatedPointerDef) {

713

714

715 Contribution.erase(&I);

716 PoisonedDefs.erase(&I);

717 ValidUnrelocatedDefs.insert(&I);

719 << " from Contribution of " << BB->getName() << "\n");

720 ContributionChanged = true;

721 } else if (PoisonedPointerDef) {

722

723

724 Contribution.erase(&I);

726 LLVM_DEBUG(dbgs() << "Removing poisoned " << I << " from Contribution of "

727 << BB->getName() << "\n");

728 ContributionChanged = true;

729 } else {

730 bool Cleared = false;

731 transferInstruction(I, Cleared, AvailableSet);

732 (void)Cleared;

733 }

734 }

735 return ContributionChanged;

736}

737

738void GCPtrTracker::gatherDominatingDefs(const BasicBlock *BB,

740 const DominatorTree &DT) {

742

743 assert(DTN && "Unreachable blocks are ignored");

746 auto BBS = getBasicBlockState(DTN->getBlock());

747 assert(BBS && "immediate dominator cannot be dead for a live block");

748 const auto &Defs = BBS->Contribution;

749 Result.insert_range(Defs);

750

751

752

753

754 if (BBS->Cleared)

755 return;

756 }

757

761}

762

763void GCPtrTracker::transferBlock(const BasicBlock *BB, BasicBlockState &BBS,

764 bool ContributionChanged) {

767

768 if (BBS.Cleared) {

769

770 if (ContributionChanged)

771 AvailableOut = BBS.Contribution;

772 } else {

773

774

777 AvailableOut = std::move(Temp);

778 }

779

782 dbgs() << " to ";

784 dbgs() << "\n";);

785}

786

787void GCPtrTracker::transferInstruction(const Instruction &I, bool &Cleared,

790 Cleared = true;

794}

795

796void InstructionVerifier::verifyInstruction(

797 const GCPtrTracker *Tracker, const Instruction &I,

803 const BasicBlockState *InBBS = Tracker->getBasicBlockState(InBB);

804 if (!InBBS ||

805 !Tracker->hasLiveIncomingEdge(PN, InBB))

806 continue;

807

809

811 !InBBS->AvailableOut.count(InValue))

812 reportInvalidUse(*InValue, *PN);

813 }

816 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);

819

820

821

822 auto hasValidUnrelocatedUse = [&AvailableSet, Tracker, baseTyLHS, baseTyRHS,

824

825

826

827

828

829

830

832 return false;

833

834

835

836

837

842 return false;

843

844

845

846

847

848 if ((Tracker->isValuePoisoned(LHS) && baseTyRHS != ExclusivelyNull) ||

850 return false;

851

852

853

854

855

856

857

858

859

860 return true;

861 };

862 if (!hasValidUnrelocatedUse()) {

863

864

866 reportInvalidUse(*LHS, I);

868 reportInvalidUse(*RHS, I);

869 }

870 } else {

871 for (const Value *V : I.operands())

874 reportInvalidUse(*V, I);

875 }

876}

877

878void InstructionVerifier::reportInvalidUse(const Value &V,

879 const Instruction &I) {

880 errs() << "Illegal use of unrelocated value found!\n";

881 errs() << "Def: " << V << "\n";

882 errs() << "Use: " << I << "\n";

884 abort();

885 AnyInvalidUses = true;

886}

887

889 const CFGDeadness &CD) {

890 LLVM_DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName()

891 << "\n");

893 dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n";

894

895 GCPtrTracker Tracker(F, DT, CD);

896

897

898

899

900 InstructionVerifier Verifier;

901 GCPtrTracker::verifyFunction(std::move(Tracker), Verifier);

902

903 if (PrintOnly && !Verifier.hasAnyInvalidUses()) {

904 dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName()

905 << "\n";

906 }

907}

for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file defines the BumpPtrAllocator interface.

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

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

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

This file defines the DenseSet and SmallDenseSet classes.

static bool runOnFunction(Function &F, bool PostInlining)

@ Available

We know the block is fully available. This is a fixpoint.

modulo schedule Modulo Schedule test pass

static bool processFunction(Function &F, NVPTXTargetMachine &TM)

ppc ctr loops PowerPC CTR Loops Verify

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.

const SmallVectorImpl< MachineOperand > & Cond

static cl::opt< bool > PrintOnly("safepoint-ir-verifier-print-only", cl::init(false))

This option is used for writing test cases.

verify safepoint Safepoint IR static false bool isGCPointerType(Type *T)

Definition SafepointIRVerifier.cpp:250

static bool isNotExclusivelyConstantDerived(const Value *V)

Definition SafepointIRVerifier.cpp:389

static enum BaseType getBaseType(const Value *Val)

Return the baseType for Val which states whether Val is exclusively derived from constant/null,...

Definition SafepointIRVerifier.cpp:325

static bool containsGCPtrType(Type *Ty)

Definition SafepointIRVerifier.cpp:259

DenseSet< const Value * > AvailableValueSet

The verifier algorithm is phrased in terms of availability.

Definition SafepointIRVerifier.cpp:287

static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End)

Definition SafepointIRVerifier.cpp:273

verify safepoint Safepoint IR Verifier

Definition SafepointIRVerifier.cpp:248

BaseType

A given derived pointer can have multiple base pointers through phi/selects.

Definition SafepointIRVerifier.cpp:313

@ ExclusivelySomeConstant

Definition SafepointIRVerifier.cpp:316

@ NonConstant

Definition SafepointIRVerifier.cpp:314

@ ExclusivelyNull

Definition SafepointIRVerifier.cpp:315

This file defines generic set operations that may be used on set's of different types,...

This file implements a set that has insertion order iteration characteristics.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

LLVM_ABI AnalysisUsage & addRequiredID(const void *ID)

void setPreservesAll()

Set by analyses that do not transform their input at all.

LLVM Basic Block Representation.

const Function * getParent() const

Return the enclosing method, or null if none.

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

bool isConditional() const

BasicBlock * getSuccessor(unsigned i) const

Value * getCondition() const

static LLVM_ABI Constant * getNullValue(Type *Ty)

Constructor to create a '0' constant of arbitrary type.

ValueT lookup(const_arg_type_t< KeyT > Val) const

lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...

bool contains(const_arg_type_t< KeyT > Val) const

Return true if the specified key is in the map, false otherwise.

Implements a dense probed hash-table based set.

DomTreeNodeBase * getIDom() const

Analysis pass which computes a DominatorTree.

Legacy analysis pass which computes a DominatorTree.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

FunctionPass class - This class is used to implement most global optimizations.

iterator_range< arg_iterator > args()

op_range incoming_values()

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

Value * getIncomingValue(unsigned i) const

Return incoming value number x.

unsigned getNumIncomingValues() const

Return the number of incoming edges.

static LLVM_ABI PassRegistry * getPassRegistry()

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

Use & getUse() const

getUse - Return the operand Use in the predecessor's terminator of the successor.

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.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition SafepointIRVerifier.cpp:199

A vector that has set insertion semantics.

void push_back(const T &Elt)

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

Class to represent struct types.

The instances of the Type class are immutable: once they are created, they are never changed.

A Use represents the edge between a Value definition and its users.

User * getUser() const

Returns the User that contains this Use.

const Use & getOperandUse(unsigned i) const

LLVM Value Representation.

Type * getType() const

All values are typed, get the type of this value.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

std::pair< iterator, bool > insert(const ValueT &V)

bool erase(const ValueT &V)

size_type count(const_arg_type_t< ValueT > V) const

Return 1 if the specified key is in the set, 0 otherwise.

const ParentTy * getParent() const

This class implements an extremely fast bulk output stream that can only output to a stream.

unsigned ID

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

@ BasicBlock

Various leaf nodes.

initializer< Ty > init(const Ty &Val)

NodeAddr< UseNode * > Use

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

void set_intersect(S1Ty &S1, const S2Ty &S2)

set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)

Check a function for errors, useful for use when debugging a pass.

auto successors(const MachineBasicBlock *BB)

constexpr from_range_t from_range

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

auto cast_or_null(const Y &Val)

void verifySafepointIR(Function &F)

Run the safepoint verifier over a single function. Crashes on failure.

Definition SafepointIRVerifier.cpp:233

PredIterator< const BasicBlock, Value::const_user_iterator > const_pred_iterator

DomTreeNodeBase< BasicBlock > DomTreeNode

bool any_of(R &&range, UnaryPredicate P)

Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

FunctionPass * createSafepointIRVerifierPass()

Create an instance of the safepoint verifier pass which can be added to a pass pipeline to check for ...

Definition SafepointIRVerifier.cpp:240

auto make_first_range(ContainerTy &&c)

Given a container of pairs, return a range over the first elements.

bool set_union(S1Ty &S1, const S2Ty &S2)

set_union(A, B) - Compute A := A u B, return whether A changed.

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

LLVM_ABI raw_fd_ostream & errs()

This returns a reference to a raw_ostream for standard error.

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

LLVM_ABI void initializeSafepointIRVerifierPass(PassRegistry &)