VPlanVerifier.cpp Source File (original) (raw)

25#define DEBUG_TYPE "loop-vectorize"

27using namespace llvm;

30namespace {

31class VPlanVerifier {

34 bool VerifyLate;

41 bool verifyPhiRecipes(const VPBasicBlock *VPBB);

46 bool verifyEVLRecipe(const VPInstruction &EVL) const;

49 bool verifyLastActiveLaneRecipe(const VPInstruction &LastActiveLane) const;

51 bool verifyVPBasicBlock(const VPBasicBlock *VPBB);

69public:

71 bool VerifyLate)

72 : VPDT(VPDT), TypeInfo(TypeInfo), VerifyLate(VerifyLate) {}

75};

76}

78bool VPlanVerifier::verifyPhiRecipes(const VPBasicBlock *VPBB) {

79 auto RecipeI = VPBB->begin();

80 auto End = VPBB->end();

81 unsigned NumActiveLaneMaskPhiRecipes = 0;

83 while (RecipeI != End && RecipeI->isPhi()) {

85 NumActiveLaneMaskPhiRecipes++;

87 if (IsHeaderVPBB &&

89 errs() << "Found non-header PHI recipe in header VPBB";

90#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

91 errs() << ": ";

92 RecipeI->dump();

93#endif

94 return false;

95 }

98 errs() << "Found header PHI recipe in non-header VPBB";

99#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

100 errs() << ": ";

101 RecipeI->dump();

102#endif

103 return false;

104 }

105

106

107

110 errs() << "Phi-like recipe with different number of operands and "

111 "predecessors.\n";

112

113

114 return false;

115 }

116 }

117

118 RecipeI++;

119 }

120

121 if (!VerifyLate && NumActiveLaneMaskPhiRecipes > 1) {

122 errs() << "There should be no more than one VPActiveLaneMaskPHIRecipe";

123 return false;

124 }

125

126 while (RecipeI != End) {

128 errs() << "Found phi-like recipe after non-phi recipe";

129

130#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

131 errs() << ": ";

132 RecipeI->dump();

133 errs() << "after\n";

134 std::prev(RecipeI)->dump();

135#endif

136 return false;

137 }

138 RecipeI++;

139 }

140 return true;

141}

142

143bool VPlanVerifier::verifyEVLRecipe(const VPInstruction &EVL) const {

145 errs() << "verifyEVLRecipe should only be called on "

146 "VPInstruction::ExplicitVectorLength\n";

147 return false;

148 }

149 auto VerifyEVLUse = [&](const VPRecipeBase &R,

150 const unsigned ExpectedIdx) -> bool {

152 unsigned UseCount = count(Ops, &EVL);

153 if (UseCount != 1 || Ops[ExpectedIdx] != &EVL) {

154 errs() << "EVL is used as non-last operand in EVL-based recipe\n";

155 return false;

156 }

157 return true;

158 };

159 return all_of(EVL.users(), [this, &VerifyEVLUse](VPUser *U) {

160 return TypeSwitch<const VPUser *, bool>(U)

161 .Case([&](const VPWidenIntrinsicRecipe *S) {

162 return VerifyEVLUse(*S, S->getNumOperands() - 1);

163 })

164 .Case<VPWidenStoreEVLRecipe, VPReductionEVLRecipe,

165 VPWidenIntOrFpInductionRecipe, VPWidenPointerInductionRecipe>(

166 [&](const VPRecipeBase *S) { return VerifyEVLUse(*S, 2); })

167 .Case([&](auto *R) {

168 if (R->getNumOperands() != 3) {

169 errs() << "Unrolling with EVL tail folding not yet supported\n";

170 return false;

171 }

172 return VerifyEVLUse(*R, 2);

173 })

174 .Case<VPWidenLoadEVLRecipe, VPVectorEndPointerRecipe,

175 VPInterleaveEVLRecipe>(

176 [&](const VPRecipeBase *R) { return VerifyEVLUse(*R, 1); })

177 .Case(

178 [&](const VPInstructionWithType *S) { return VerifyEVLUse(*S, 0); })

179 .Case([&](const VPInstruction *I) {

180 if (I->getOpcode() == Instruction::PHI ||

181 I->getOpcode() == Instruction::ICmp ||

182 I->getOpcode() == Instruction::Sub)

183 return VerifyEVLUse(*I, 1);

184 switch (I->getOpcode()) {

185 case Instruction::Add:

186 break;

187 case Instruction::UIToFP:

188 case Instruction::Trunc:

189 case Instruction::ZExt:

190 case Instruction::Mul:

191 case Instruction::FMul:

193

194

195 if (!VerifyLate) {

196 errs() << "EVL used by unexpected VPInstruction\n";

197 return false;

198 }

199 break;

200 default:

201 errs() << "EVL used by unexpected VPInstruction\n";

202 return false;

203 }

204

205

207 I->getNumUsers() != 1 &&

208 (I->getNumUsers() != 2 ||

211 errs() << "EVL is used in VPInstruction with multiple users\n";

212 return false;

213 }

215 errs() << "Result of VPInstruction::Add with EVL operand is "

216 "not used by VPEVLBasedIVPHIRecipe\n";

217 return false;

218 }

219 return true;

220 })

221 .Default([&](const VPUser *U) {

222 errs() << "EVL has unexpected user\n";

223 return false;

224 });

225 });

226}

227

228bool VPlanVerifier::verifyLastActiveLaneRecipe(

229 const VPInstruction &LastActiveLane) const {

231 "must be called with VPInstruction::LastActiveLane");

232

234 errs() << "LastActiveLane must have at least one operand\n";

235 return false;

236 }

237

239

240

241

242 for (VPValue *Op : LastActiveLane.operands()) {

244 continue;

245

246

247 auto BroadcastOrEVL =

251 continue;

252

253 errs() << "LastActiveLane operand ";

254#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

255 VPSlotTracker Tracker(&Plan);

256 Op->printAsOperand(errs(), Tracker);

257#endif

258 errs() << " must be prefix mask (a header mask or an "

259 "EVL-derived mask currently)\n";

260 return false;

261 }

262

263 return true;

264}

265

266bool VPlanVerifier::verifyVPBasicBlock(const VPBasicBlock *VPBB) {

267 if (!verifyPhiRecipes(VPBB))

268 return false;

269

270

271 DenseMap<const VPRecipeBase *, unsigned> RecipeNumbering;

272 unsigned Cnt = 0;

273 for (const VPRecipeBase &R : *VPBB)

274 RecipeNumbering[&R] = Cnt++;

275

276 for (const VPRecipeBase &R : *VPBB) {

278 errs() << "VPIRInstructions ";

279#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

280 R.dump();

281 errs() << " ";

282#endif

283 errs() << "not in a VPIRBasicBlock!\n";

284 return false;

285 }

286 for (const VPValue *V : R.definedValues()) {

287

288

289

291 errs() << "Failed to infer scalar type!\n";

292 return false;

293 }

294

295 for (const VPUser *U : V->users()) {

298 UI->getNumOperands() != UI->getParent()->getNumPredecessors()) {

299 errs() << "Phi-like recipe with different number of operands and "

300 "predecessors.\n";

301 return false;

302 }

303

305 for (const auto &[IncomingVPV, IncomingVPBB] :

306 Phi->incoming_values_and_blocks()) {

307 if (IncomingVPV != V)

308 continue;

309

310 if (VPDT.dominates(VPBB, IncomingVPBB))

311 continue;

312

313 errs() << "Incoming def does not dominate incoming block!\n";

314#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

315 VPSlotTracker Tracker(VPBB->getPlan());

316 IncomingVPV->getDefiningRecipe()->print(errs(), " ", Tracker);

317 errs() << "\n does not dominate " << IncomingVPBB->getName()

318 << " for\n";

319 UI->print(errs(), " ", Tracker);

320#endif

321 return false;

322 }

323 continue;

324 }

325

327 continue;

328

329

330

331 if (UI->getParent() == VPBB) {

332 if (RecipeNumbering[UI] >= RecipeNumbering[&R])

333 continue;

334 } else {

335 if (VPDT.dominates(VPBB, UI->getParent()))

336 continue;

337 }

338

339 errs() << "Use before def!\n";

340#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

341 VPSlotTracker Tracker(VPBB->getPlan());

342 UI->print(errs(), " ", Tracker);

343 errs() << "\n before\n";

344 R.print(errs(), " ", Tracker);

345 errs() << "\n";

346#endif

347 return false;

348 }

349 }

351 switch (VPI->getOpcode()) {

353 if (!verifyEVLRecipe(*VPI)) {

354 errs() << "EVL VPValue is not used correctly\n";

355 return false;

356 }

357 break;

359 if (!verifyLastActiveLaneRecipe(*VPI))

360 return false;

361 break;

362 default:

363 break;

364 }

365 }

366 }

367

369 if (!IRBB)

370 return true;

371

372 if (!WrappedIRBBs.insert(IRBB->getIRBasicBlock()).second) {

373 errs() << "Same IR basic block used by multiple wrapper blocks!\n";

374 return false;

375 }

376

377 return true;

378}

379

380

381

384 for (const auto *Block : VPBlockVec) {

386 return true;

387 }

388 return false;

389}

390

391bool VPlanVerifier::verifyBlock(const VPBlockBase *VPB) {

393

396 (VPBB && VPBB->getParent() && VPBB->isExiting() &&

397 !VPBB->getParent()->isReplicator())) {

398 if (!VPBB || !VPBB->getTerminator()) {

399 errs() << "Block has multiple successors but doesn't "

400 "have a proper branch recipe!\n";

401 return false;

402 }

403 } else {

404 if (VPBB && VPBB->getTerminator()) {

405 errs() << "Unexpected branch recipe!\n";

406 return false;

407 }

408 }

409 }

410

411

413

414

416 errs() << "Multiple instances of the same successor.\n";

417 return false;

418 }

419

420 for (const VPBlockBase *Succ : Successors) {

421

422 const auto &SuccPreds = Succ->getPredecessors();

424 errs() << "Missing predecessor link.\n";

425 return false;

426 }

427 }

428

429

431

432

433

435 errs() << "Multiple instances of the same predecessor.\n";

436 return false;

437 }

438

439 for (const VPBlockBase *Pred : Predecessors) {

440

441 if (Pred->getParent() != VPB->getParent()) {

442 errs() << "Predecessor is not in the same region.\n";

443 return false;

444 }

445

446

447 const auto &PredSuccs = Pred->getSuccessors();

449 errs() << "Missing successor link.\n";

450 return false;

451 }

452 }

453 return !VPBB || verifyVPBasicBlock(VPBB);

454}

455

456bool VPlanVerifier::verifyBlocksInRegion(const VPRegionBlock *Region) {

458

459 if (VPB->getParent() != Region) {

460 errs() << "VPBlockBase has wrong parent\n";

461 return false;

462 }

463

464 if (!verifyBlock(VPB))

465 return false;

466 }

467 return true;

468}

469

470bool VPlanVerifier::verifyRegion(const VPRegionBlock *Region) {

471 const VPBlockBase *Entry = Region->getEntry();

472 const VPBlockBase *Exiting = Region->getExiting();

473

474

475 if (Entry->hasPredecessors()) {

476 errs() << "region entry block has predecessors\n";

477 return false;

478 }

480 errs() << "region exiting block has successors\n";

481 return false;

482 }

483

484 return verifyBlocksInRegion(Region);

485}

486

487bool VPlanVerifier::verifyRegionRec(const VPRegionBlock *Region) {

488

489 return verifyRegion(Region) &&

491 [this](const VPBlockBase *VPB) {

492 const auto *SubRegion = dyn_cast(VPB);

493 return !SubRegion || verifyRegionRec(SubRegion);

494 });

495}

496

497bool VPlanVerifier::verify(const VPlan &Plan) {

499 [this](const VPBlockBase *VPB) { return !verifyBlock(VPB); }))

500 return false;

501

503

504 if (!TopRegion)

505 return true;

506

507 if (!verifyRegionRec(TopRegion))

508 return false;

509

511 errs() << "VPlan Top Region should have no parent.\n";

512 return false;

513 }

514

516 if (!Entry) {

517 errs() << "VPlan entry block is not a VPBasicBlock\n";

518 return false;

519 }

520

522 errs() << "VPlan vector loop header does not start with a "

523 "VPCanonicalIVPHIRecipe\n";

524 return false;

525 }

526

528 if (!Exiting) {

529 errs() << "VPlan exiting block is not a VPBasicBlock\n";

530 return false;

531 }

532

533 if (Exiting->empty()) {

534 errs() << "VPlan vector loop exiting block must end with BranchOnCount or "

535 "BranchOnCond VPInstruction but is empty\n";

536 return false;

537 }

538

541 errs() << "VPlan vector loop exit must end with BranchOnCount or "

542 "BranchOnCond VPInstruction\n";

543 return false;

544 }

545

546 return true;

547}

548

552 VPlanVerifier Verifier(VPDT, TypeInfo, VerifyLate);

553 return Verifier.verify(Plan);

554}

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

const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]

verify safepoint Safepoint IR Verifier

This file defines the SmallPtrSet class.

This file implements the TypeSwitch template, which mimics a switch() statement whose cases are type ...

This file implements dominator tree analysis for a single level of a VPlan's H-CFG.

This file contains the declarations of different VPlan-related auxiliary helpers.

static bool hasDuplicates(const SmallVectorImpl< VPBlockBase * > &VPBlockVec)

Utility function that checks whether VPBlockVec has duplicate VPBlockBases.

Definition VPlanVerifier.cpp:382

This file declares the class VPlanVerifier, which contains utility functions to check the consistency...

This file contains the declarations of the Vectorization Plan base classes:

bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const

dominates - Returns true iff A dominates B.

Implements a dense probed hash-table based set with some number of buckets stored inline.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

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

VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.

iterator begin()

Recipe iterator methods.

VPBlockBase is the building block of the Hierarchical Control-Flow Graph.

VPRegionBlock * getParent()

size_t getNumSuccessors() const

size_t getNumPredecessors() const

const VPBlocksTy & getPredecessors() const

const VPBlocksTy & getSuccessors() const

static bool isHeader(const VPBlockBase *VPB, const VPDominatorTree &VPDT)

Returns true if VPB is a loop header, based on regions or VPDT in their absence.

Template specialization of the standard LLVM dominator tree utility for VPBlockBases.

This is a concrete Recipe that models a single VPlan-level instruction.

unsigned getOpcode() const

VPBasicBlock * getParent()

VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...

const VPBlockBase * getEntry() const

const VPBlockBase * getExiting() const

An analysis for type-inference for VPValues.

Type * inferScalarType(const VPValue *V)

Infer the type of V. Returns the scalar type of V.

unsigned getNumOperands() const

VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...

VPBasicBlock * getEntry()

LLVM_ABI_FOR_TEST VPRegionBlock * getVectorLoopRegion()

Returns the VPRegionBlock of the vector loop.

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

bool match(Val *V, const Pattern &P)

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)

MatchFunctor< Val, Pattern > match_fn(const Pattern &P)

A match functor that can be used as a UnaryPredicate in functional algorithms like all_of.

match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)

Combine two pattern matchers matching L || R.

VPInstruction_match< VPInstruction::StepVector > m_StepVector()

VPInstruction_match< VPInstruction::BranchOnCount > m_BranchOnCount()

VPInstruction_match< VPInstruction::Broadcast, Op0_t > m_Broadcast(const Op0_t &Op0)

class_match< VPValue > m_VPValue()

Match an arbitrary VPValue and ignore it.

VPInstruction_match< VPInstruction::ExplicitVectorLength, Op0_t > m_EVL(const Op0_t &Op0)

VPInstruction_match< VPInstruction::BranchOnCond > m_BranchOnCond()

NodeAddr< PhiNode * > Phi

bool isHeaderMask(const VPValue *V, const VPlan &Plan)

Return true if V is a header mask in Plan.

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.

LLVM_ABI_FOR_TEST bool verifyVPlanIsValid(const VPlan &Plan, bool VerifyLate=false)

Verify invariants for general VPlans.

Definition VPlanVerifier.cpp:549

decltype(auto) dyn_cast(const From &Val)

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

iterator_range< df_iterator< VPBlockShallowTraversalWrapper< VPBlockBase * > > > vp_depth_first_shallow(VPBlockBase *G)

Returns an iterator range to traverse the graph starting at G in depth-first order.

bool any_of(R &&range, UnaryPredicate P)

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

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

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.

auto count(R &&Range, const E &Element)

Wrapper function around std::count to count the number of times an element Element occurs in the give...

DWARFExpression::Operation Op

decltype(auto) cast(const From &Val)

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

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

Returns true if Element is found in Range.