VPlan.cpp Source File (original) (raw)

46#include

47#include

49using namespace llvm;

52namespace llvm {

54}

58 "vplan-print-in-dot-format", cl::Hidden,

59 cl::desc("Use dot format instead of plain text when dumping VPlans"));

61#define DEBUG_TYPE "loop-vectorize"

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

65 const VPInstruction *Instr = dyn_cast(&V);

67 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);

69 return OS;

70}

71#endif

75 switch (LaneKind) {

81 return Builder.getInt32(Lane);

82 }

84}

87 : SubclassID(SC), UnderlyingVal(UV), Def(Def) {

89 Def->addDefinedValue(this);

90}

93 assert(Users.empty() && "trying to delete a VPValue with remaining users");

95 Def->removeDefinedValue(this);

96}

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

100 if (const VPRecipeBase *R = dyn_cast_or_null(Def))

102 else

104}

105

107 const VPRecipeBase *Instr = dyn_cast_or_null(this->Def);

109 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);

111 dbgs() << "\n";

112}

113

115 const VPRecipeBase *Instr = dyn_cast_or_null(this);

117 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);

119 dbgs() << "\n";

120}

121#endif

122

124 return cast_or_null(Def);

125}

126

128 return cast_or_null(Def);

129}

130

131

132

134 T *Next = Start;

135 T *Current = Start;

136 while ((Next = Next->getParent()))

137 Current = Next;

138

140 WorkList.insert(Current);

141

142 for (unsigned i = 0; i < WorkList.size(); i++) {

143 T *Current = WorkList[i];

144 if (Current->getNumPredecessors() == 0)

145 return Current;

146 auto &Predecessors = Current->getPredecessors();

147 WorkList.insert(Predecessors.begin(), Predecessors.end());

148 }

149

150 llvm_unreachable("VPlan without any entry node without predecessors");

151}

152

154

156

157

162 return cast(Block);

163}

164

169 return cast(Block);

170}

171

173 assert(ParentPlan->getEntry() == this && "Can only set plan on its entry.");

174 Plan = ParentPlan;

175}

176

177

182 return cast(Block);

183}

184

189 return cast(Block);

190}

191

193 if (!Successors.empty() || !Parent)

194 return this;

196 "Block w/o successors not the exiting block of its parent.");

198}

199

201 if (!Predecessors.empty() || !Parent)

202 return this;

204 "Block w/o predecessors not the entry of its parent.");

206}

207

210 while (It != end() && It->isPhi())

211 It++;

212 return It;

213}

214

219 Loop *CurrentParentLoop, Type *CanonicalIVTy)

220 : TTI(TTI), VF(VF), CFG(DT), LI(LI), Builder(Builder), ILV(ILV), Plan(Plan),

221 CurrentParentLoop(CurrentParentLoop), LVer(nullptr),

222 TypeAnalysis(CanonicalIVTy) {}

223

225 if (Def->isLiveIn())

226 return Def->getLiveInIRValue();

227

230

234 }

235

238 if (!VecPart->getType()->isVectorTy()) {

239 assert(Lane.isFirstLane() && "cannot get lane > 0 for scalar");

240 return VecPart;

241 }

242

245

246 return Extract;

247}

248

250 if (NeedsScalar) {

255 "Trying to access a single scalar per part but has multiple scalars "

256 "per part.");

258 }

259

260

263

264 auto GetBroadcastInstrs = [this, Def](Value *V) {

265 bool SafeToHoist = Def->isDefinedOutsideLoopRegions();

267 return V;

268

270 if (SafeToHoist) {

273 if (LoopVectorPreHeader)

275 }

276

277

278

280

281 return Shuf;

282 };

283

285 assert(Def->isLiveIn() && "expected a live-in");

286 Value *IRV = Def->getLiveInIRValue();

287 Value *B = GetBroadcastInstrs(IRV);

289 return B;

290 }

291

293

294

296 set(Def, ScalarValue);

297 return ScalarValue;

298 }

299

301

303

305

306

309 "unexpected recipe found to be invariant");

310 IsUniform = true;

311 LastLane = 0;

312 }

313

314 auto *LastInst = cast(get(Def, LastLane));

315

316

317

319 auto NewIP = isa(LastInst)

320 ? LastInst->getParent()->getFirstNonPHIIt()

323

324

325

326

327

328

329

330 Value *VectorValue = nullptr;

331 if (IsUniform) {

332 VectorValue = GetBroadcastInstrs(ScalarValue);

333 set(Def, VectorValue);

334 } else {

335

338 set(Def, Undef);

341 VectorValue = get(Def);

342 }

344 return VectorValue;

345}

346

348 VPRegionBlock *LoopRegion = R->getParent()->getEnclosingLoopRegion();

350}

351

354

355

356 if (LVer && isa<LoadInst, StoreInst>(Orig))

358}

359

361

363 return;

364

365 if (Instruction *ToI = dyn_cast(To)) {

368 }

369}

370

373

374

375 if (DIL &&

380

382 auto NewDIL =

384 if (NewDIL)

386 else

387 LLVM_DEBUG(dbgs() << "Failed to create new discriminator: "

388 << DIL->getFilename() << " Line: " << DIL->getLine());

389 } else

391}

392

396 Value *VectorValue = get(Def);

399 set(Def, VectorValue);

400}

401

404

405

410

411 return NewBB;

412}

413

416

417 for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {

421

422 assert(PredBB && "Predecessor basic-block not found building successor.");

423 auto *PredBBTerminator = PredBB->getTerminator();

425

426 auto *TermBr = dyn_cast(PredBBTerminator);

427 if (isa(PredBBTerminator)) {

428 assert(PredVPSuccessors.size() == 1 &&

429 "Predecessor ending w/o branch must have single successor.");

430 DebugLoc DL = PredBBTerminator->getDebugLoc();

433 Br->setDebugLoc(DL);

434 } else if (TermBr && !TermBr->isConditional()) {

435 TermBr->setSuccessor(0, NewBB);

436 } else {

437

438

439 unsigned idx = PredVPSuccessors.front() == this ? 0 : 1;

440 assert((TermBr && (!TermBr->getSuccessor(idx) ||

441 (isa(this) &&

442 TermBr->getSuccessor(idx) == NewBB))) &&

443 "Trying to reset an existing successor block.");

444 TermBr->setSuccessor(idx, NewBB);

445 }

447 }

448}

449

451 assert(getHierarchicalSuccessors().size() <= 2 &&

452 "VPIRBasicBlock can have at most two successors at the moment!");

456 executeRecipes(State, IRBB);

457

458

459 if (getSingleSuccessor() && isa(IRBB->getTerminator())) {

462 IRBB->getTerminator()->eraseFromParent();

463 } else {

465 (getNumSuccessors() == 0 || isa(IRBB->getTerminator())) &&

466 "other blocks must be terminated by a branch");

467 }

468

469 connectToPredecessors(State->CFG);

470}

471

473 auto *NewBlock = getPlan()->createEmptyVPIRBasicBlock(IRBB);

476 return NewBlock;

477}

478

480 bool Replica = bool(State->Lane);

482

483 auto IsReplicateRegion = [](VPBlockBase *BB) {

484 auto *R = dyn_cast_or_null(BB);

485 return R && R->isReplicator();

486 };

487

488

489 if ((Replica && this == getParent()->getEntry()) ||

490 IsReplicateRegion(getSingleHierarchicalPredecessor())) {

491

492

493

495 } else {

496 NewBB = createEmptyBasicBlock(State->CFG);

497

499

501

502

506

509 connectToPredecessors(State->CFG);

510 }

511

512

513 executeRecipes(State, NewBB);

514}

515

517 auto *NewBlock = getPlan()->createVPBasicBlock(getName());

520 return NewBlock;

521}

522

525 << " in BB:" << BB->getName() << '\n');

526

528

531

533}

534

536 assert((SplitAt == end() || SplitAt->getParent() == this) &&

537 "can only split at a position in the same block");

538

540

541 auto *SplitBlock = getPlan()->createVPBasicBlock(getName() + ".split");

543

544

548

550}

551

552

553

555 if (P && P->isReplicator()) {

556 P = P->getParent();

557

558

559 assert(( || !cast(P)->isReplicator()) &&

560 "unexpected nested replicate regions");

561 }

562 return P;

563}

564

567}

568

571}

572

574 if (VPBB->empty()) {

577 "block with multiple successors doesn't have a recipe as terminator");

578 return false;

579 }

580

582 bool IsCondBranch = isa(R) ||

586

589 assert(IsCondBranch && "block with multiple successors not terminated by "

590 "conditional branch recipe");

591

592 return true;

593 }

594

597 "block with 0 or 1 successors terminated by conditional branch recipe");

598 return false;

599}

600

603 return &back();

604 return nullptr;

605}

606

609 return &back();

610 return nullptr;

611}

612

615}

616

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

619 if (getSuccessors().empty()) {

620 O << Indent << "No successors\n";

621 } else {

622 O << Indent << "Successor(s): ";

623 ListSeparator LS;

624 for (auto *Succ : getSuccessors())

625 O << LS << Succ->getName();

626 O << '\n';

627 }

628}

629

632 O << Indent << getName() << ":\n";

633

634 auto RecipeIndent = Indent + " ";

637 O << '\n';

638 }

639

640 printSuccessors(O, Indent);

641}

642#endif

643

645

646

647

648

649

650

654 bool InRegion = Entry->getParent();

655

658 Old2NewVPBlocks[BB] = NewBB;

659 if (InRegion && BB->getNumSuccessors() == 0) {

660 assert(!Exiting && "Multiple exiting blocks?");

661 Exiting = BB;

662 }

663 }

664 assert((!InRegion || Exiting) && "regions must have a single exiting block");

665

666

668 VPBlockBase *NewBB = Old2NewVPBlocks[BB];

671 NewPreds.push_back(Old2NewVPBlocks[Pred]);

672 }

676 NewSuccs.push_back(Old2NewVPBlocks[Succ]);

677 }

679 }

680

681#if !defined(NDEBUG)

682

683

684 for (const auto &[OldBB, NewBB] :

687 for (const auto &[OldPred, NewPred] :

688 zip(OldBB->getPredecessors(), NewBB->getPredecessors()))

689 assert(NewPred == Old2NewVPBlocks[OldPred] && "Different predecessors");

690

691 for (const auto &[OldSucc, NewSucc] :

692 zip(OldBB->successors(), NewBB->successors()))

693 assert(NewSucc == Old2NewVPBlocks[OldSucc] && "Different successors");

694 }

695#endif

696

697 return std::make_pair(Old2NewVPBlocks[Entry],

698 Exiting ? Old2NewVPBlocks[Exiting] : nullptr);

699}

700

702 const auto &[NewEntry, NewExiting] = cloneFrom(getEntry());

703 auto *NewRegion = getPlan()->createVPRegionBlock(NewEntry, NewExiting,

704 getName(), isReplicator());

706 Block->setParent(NewRegion);

707 return NewRegion;

708}

709

712 RPOT(Entry);

713

714 if (!isReplicator()) {

715

720

721

722

723 if (ParentLoop)

725 else

727

728

731 Block->execute(State);

732 }

733

735 return;

736 }

737

738 assert(!State->Lane && "Replicating a Region with non-null instance.");

739

740

741 assert(!State->VF.isScalable() && "VF is assumed to be non scalable.");

746

749 Block->execute(State);

750 }

751 }

752

753

754 State->Lane.reset();

755}

756

760 Cost += R.cost(VF, Ctx);

762}

763

765 if (!isReplicator()) {

773 LLVM_DEBUG(dbgs() << "Cost of " << BackedgeCost << " for VF " << VF

774 << ": vector loop backedge\n");

775 Cost += BackedgeCost;

777 }

778

779

780

781

782

785

786

787

788

790 VPBasicBlock *Then = cast(getEntry()->getSuccessors()[0]);

792

793

794

797

798 return ThenCost;

799}

800

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

804 O << Indent << (isReplicator() ? " " : " ") << getName() << ": {";

805 auto NewIndent = Indent + " ";

807 O << '\n';

808 BlockBase->print(O, NewIndent, SlotTracker);

809 }

810 O << Indent << "}\n";

811

812 printSuccessors(O, Indent);

813}

814#endif

815

817 setEntry(createVPIRBasicBlock(L->getLoopPreheader()));

818 ScalarHeader = createVPIRBasicBlock(L->getHeader());

819}

820

823

824 for (auto *VPB : CreatedBlocks) {

825 if (auto *VPBB = dyn_cast(VPB)) {

826

827

829 for (auto *Def : R.definedValues())

830 Def->replaceAllUsesWith(&DummyValue);

831

832 for (unsigned I = 0, E = R.getNumOperands(); I != E; I++)

833 R.setOperand(I, &DummyValue);

834 }

835 }

836 delete VPB;

837 }

838 for (VPValue *VPV : VPLiveInsToFree)

839 delete VPV;

840 if (BackedgeTakenCount)

841 delete BackedgeTakenCount;

842}

843

846 bool RequiresScalarEpilogueCheck,

847 bool TailFolded, Loop *TheLoop) {

848 auto Plan = std::make_unique(TheLoop);

850

851

852

853

854

855

856

859

860

861

862

864 assert(!isa(BackedgeTakenCountSCEV) &&

865 "Invalid loop count");

868 InductionTy, TheLoop);

869 Plan->TripCount =

871

872

873

878 HeaderVPBB, LatchVPBB, "vector loop", false );

879

883

886 if (!RequiresScalarEpilogueCheck) {

889 }

890

891

892

893

894

895

896

897

898

901

904

906

907

908

909

912 TailFolded

917 ScalarLatchTerm->getDebugLoc(), "cmp.n");

919 ScalarLatchTerm->getDebugLoc());

921}

922

926

927 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {

929 auto *TCMO = Builder.CreateSub(TripCountV, ConstantInt::get(TCTy, 1),

930 "trip.count.minus.1");

931 BackedgeTakenCount->setUnderlyingValue(TCMO);

932 }

933

934 VectorTripCount.setUnderlyingValue(VectorTripCountV);

935

937

938 assert((!getVectorLoopRegion() || VFxUF.getNumUsers()) &&

939 "VFxUF expected to always have users");

940 unsigned UF = getUF();

941 if (VF.getNumUsers()) {

943 VF.setUnderlyingValue(RuntimeVF);

944 VFxUF.setUnderlyingValue(

945 UF > 1 ? Builder.CreateMul(RuntimeVF, ConstantInt::get(TCTy, UF))

946 : RuntimeVF);

947 } else {

949 }

950}

951

952

953

954

956

959

960

962 cast(VectorPreHeader->getTerminator())->setSuccessor(0, nullptr);

965

966 LLVM_DEBUG(dbgs() << "Executing best plan with VF=" << State->VF

967 << ", UF=" << getUF() << '\n');

968 setName("Final VPlan");

970

971

972

973

980

981

982

985

987 Entry);

988

989

991 Block->execute(State);

992

994

995 auto *LoopRegion = getVectorLoopRegion();

996 if (!LoopRegion)

997 return;

998

1001

1002

1003

1004 VPBasicBlock *Header = LoopRegion->getEntryBasicBlock();

1006

1007 if (isa(&R))

1008 continue;

1009

1010 if (isa(&R)) {

1012 if (isa(&R)) {

1013 Phi = cast(State->get(R.getVPSingleValue()));

1014 } else {

1015 auto *WidenPhi = cast(&R);

1017 "recipe generating only scalars should have been replaced");

1018 auto *GEP = cast(State->get(WidenPhi));

1019 Phi = cast(GEP->getPointerOperand());

1020 }

1021

1022 Phi->setIncomingBlock(1, VectorLatchBB);

1023

1024

1025

1026 Instruction *Inc = cast(Phi->getIncomingValue(1));

1028

1029

1030 if (auto *IV = dyn_cast(&R))

1031 Inc->setOperand(0, State->get(IV->getLastUnrolledPartOperand()));

1032 continue;

1033 }

1034

1035 auto *PhiR = cast(&R);

1036 bool NeedsScalar = isa(PhiR) ||

1037 (isa(PhiR) &&

1038 cast(PhiR)->isInLoop());

1039 Value *Phi = State->get(PhiR, NeedsScalar);

1040 Value *Val = State->get(PhiR->getBackedgeValue(), NeedsScalar);

1041 cast(Phi)->addIncoming(Val, VectorLatchBB);

1042 }

1043}

1044

1046

1047

1048 return getVectorLoopRegion()->cost(VF, Ctx);

1049}

1050

1052

1054 if (auto *R = dyn_cast(B))

1055 return R->isReplicator() ? nullptr : R;

1056 return nullptr;

1057}

1058

1061 if (auto *R = dyn_cast(B))

1062 return R->isReplicator() ? nullptr : R;

1063 return nullptr;

1064}

1065

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

1069

1070 if (VF.getNumUsers() > 0) {

1071 O << "\nLive-in ";

1073 O << " = VF";

1074 }

1075

1076 if (VFxUF.getNumUsers() > 0) {

1077 O << "\nLive-in ";

1079 O << " = VF * UF";

1080 }

1081

1082 if (VectorTripCount.getNumUsers() > 0) {

1083 O << "\nLive-in ";

1084 VectorTripCount.printAsOperand(O, SlotTracker);

1085 O << " = vector-trip-count";

1086 }

1087

1088 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {

1089 O << "\nLive-in ";

1090 BackedgeTakenCount->printAsOperand(O, SlotTracker);

1091 O << " = backedge-taken count";

1092 }

1093

1094 O << "\n";

1095 if (TripCount->isLiveIn())

1096 O << "Live-in ";

1097 TripCount->printAsOperand(O, SlotTracker);

1098 O << " = original trip-count";

1099 O << "\n";

1100}

1101

1105

1106 O << "VPlan '" << getName() << "' {";

1107

1108 printLiveIns(O);

1109

1111 RPOT(getEntry());

1113 O << '\n';

1115 }

1116

1117 O << "}\n";

1118}

1119

1121 std::string Out;

1123 RSO << Name << " for ";

1124 if (!VFs.empty()) {

1125 RSO << "VF={" << VFs[0];

1127 RSO << "," << VF;

1128 RSO << "},";

1129 }

1130

1131 if (UFs.empty()) {

1132 RSO << "UF>=1";

1133 } else {

1134 RSO << "UF={" << UFs[0];

1136 RSO << "," << UF;

1137 RSO << "}";

1138 }

1139

1140 return Out;

1141}

1142

1147}

1148

1151#endif

1152

1155

1156

1157

1159 OldDeepRPOT(Entry);

1161 NewDeepRPOT(NewEntry);

1162

1163

1164 for (const auto &[OldBB, NewBB] :

1165 zip(VPBlockUtils::blocksOnly(OldDeepRPOT),

1166 VPBlockUtils::blocksOnly(NewDeepRPOT))) {

1167 assert(OldBB->getRecipeList().size() == NewBB->getRecipeList().size() &&

1168 "blocks must have the same number of recipes");

1169 for (const auto &[OldR, NewR] : zip(*OldBB, *NewBB)) {

1170 assert(OldR.getNumOperands() == NewR.getNumOperands() &&

1171 "recipes must have the same number of operands");

1172 assert(OldR.getNumDefinedValues() == NewR.getNumDefinedValues() &&

1173 "recipes must define the same number of operands");

1174 for (const auto &[OldV, NewV] :

1175 zip(OldR.definedValues(), NewR.definedValues()))

1176 Old2NewVPValues[OldV] = NewV;

1177 }

1178 }

1179

1180

1182 VPBlockUtils::blocksOnly(NewDeepRPOT)) {

1184 for (unsigned I = 0, E = NewR.getNumOperands(); I != E; ++I) {

1185 VPValue *NewOp = Old2NewVPValues.lookup(NewR.getOperand(I));

1186 NewR.setOperand(I, NewOp);

1187 }

1188 }

1189}

1190

1192 unsigned NumBlocksBeforeCloning = CreatedBlocks.size();

1193

1194 const auto &[NewEntry, __] = cloneFrom(Entry);

1195

1196 BasicBlock *ScalarHeaderIRBB = getScalarHeader()->getIRBasicBlock();

1199 auto *VPIRBB = dyn_cast(VPB);

1200 return VPIRBB && VPIRBB->getIRBasicBlock() == ScalarHeaderIRBB;

1201 }));

1202

1203 auto *NewPlan = new VPlan(cast(NewEntry), NewScalarHeader);

1205 for (VPValue *OldLiveIn : VPLiveInsToFree) {

1206 Old2NewVPValues[OldLiveIn] =

1207 NewPlan->getOrAddLiveIn(OldLiveIn->getLiveInIRValue());

1208 }

1209 Old2NewVPValues[&VectorTripCount] = &NewPlan->VectorTripCount;

1210 Old2NewVPValues[&VF] = &NewPlan->VF;

1211 Old2NewVPValues[&VFxUF] = &NewPlan->VFxUF;

1212 if (BackedgeTakenCount) {

1213 NewPlan->BackedgeTakenCount = new VPValue();

1214 Old2NewVPValues[BackedgeTakenCount] = NewPlan->BackedgeTakenCount;

1215 }

1216 assert(TripCount && "trip count must be set");

1217 if (TripCount->isLiveIn())

1218 Old2NewVPValues[TripCount] =

1219 NewPlan->getOrAddLiveIn(TripCount->getLiveInIRValue());

1220

1221

1222

1223 remapOperands(Entry, NewEntry, Old2NewVPValues);

1224

1225

1226 NewPlan->VFs = VFs;

1227 NewPlan->UFs = UFs;

1228

1229 NewPlan->Name = Name;

1231 "TripCount must have been added to Old2NewVPValues");

1232 NewPlan->TripCount = Old2NewVPValues[TripCount];

1233

1234

1235

1236 unsigned NumBlocksAfterCloning = CreatedBlocks.size();

1237 for (unsigned I :

1238 seq(NumBlocksBeforeCloning, NumBlocksAfterCloning))

1239 NewPlan->CreatedBlocks.push_back(this->CreatedBlocks[I]);

1240 CreatedBlocks.truncate(NumBlocksBeforeCloning);

1241

1242 return NewPlan;

1243}

1244

1247 CreatedBlocks.push_back(VPIRBB);

1248 return VPIRBB;

1249}

1250

1252 auto *VPIRBB = createEmptyVPIRBasicBlock(IRBB);

1256 return VPIRBB;

1257}

1258

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

1260

1262 return (isa(Block) ? "cluster_N" : "N") +

1264}

1265

1267 const std::string &Name = Block->getName();

1268 if ( Name .empty())

1269 return Name;

1270 return "VPB" + Twine(getOrCreateBID(Block));

1271}

1272

1275 bumpIndent(0);

1276 OS << "digraph VPlan {\n";

1277 OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";

1280

1281 {

1282

1283 std::string Str;

1288 for (auto Line : Lines)

1290 }

1291

1292 OS << "\"]\n";

1293 OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";

1294 OS << "edge [fontname=Courier, fontsize=30]\n";

1295 OS << "compound=true\n";

1296

1298 dumpBlock(Block);

1299

1300 OS << "}\n";

1301}

1302

1308 else

1310}

1311

1313 bool Hidden, const Twine &Label) {

1314

1315

1318 OS << Indent << getUID(Tail) << " -> " << getUID(Head);

1319 OS << " [ label=\"" << Label << '\"';

1321 OS << " ltail=" << getUID(From);

1322 if (Head != To)

1323 OS << " lhead=" << getUID(To);

1324 if (Hidden)

1325 OS << "; splines=none";

1326 OS << "]\n";

1327}

1328

1330 auto &Successors = Block->getSuccessors();

1331 if (Successors.size() == 1)

1332 drawEdge(Block, Successors.front(), false, "");

1333 else if (Successors.size() == 2) {

1334 drawEdge(Block, Successors.front(), false, "T");

1335 drawEdge(Block, Successors.back(), false, "F");

1336 } else {

1337 unsigned SuccessorNumber = 0;

1338 for (auto *Successor : Successors)

1340 }

1341}

1342

1344

1345

1346 OS << Indent << getUID(BasicBlock) << " [label =\n";

1347 bumpIndent(1);

1348 std::string Str;

1350

1352

1353

1354

1357

1360 };

1361

1362

1364 EmitLine(Line, " +\n");

1365 EmitLine(Lines.back(), "\n");

1366

1367 bumpIndent(-1);

1368 OS << Indent << "]\n";

1369

1371}

1372

1374 OS << Indent << "subgraph " << getUID(Region) << " {\n";

1375 bumpIndent(1);

1376 OS << Indent << "fontname=Courier\n"

1377 << Indent << "label=\""

1380

1383 dumpBlock(Block);

1384 bumpIndent(-1);

1385 OS << Indent << "}\n";

1387}

1388

1390 if (auto *Inst = dyn_cast(V)) {

1391 if (!Inst->getType()->isVoidTy()) {

1392 Inst->printAsOperand(O, false);

1393 O << " = ";

1394 }

1395 O << Inst->getOpcodeName() << " ";

1396 unsigned E = Inst->getNumOperands();

1397 if (E > 0) {

1398 Inst->getOperand(0)->printAsOperand(O, false);

1399 for (unsigned I = 1; I < E; ++I)

1400 Inst->getOperand(I)->printAsOperand(O << ", ", false);

1401 }

1402 } else

1403 V->printAsOperand(O, false);

1404}

1405

1406#endif

1407

1408

1409

1414}

1415

1418}

1420 replaceUsesWithIf(New, [](VPUser &, unsigned) { return true; });

1421}

1422

1426

1427

1428

1429 if (this == New)

1430 return;

1431

1432 for (unsigned J = 0; J < getNumUsers();) {

1434 bool RemovedUser = false;

1437 continue;

1438

1439 RemovedUser = true;

1441 }

1442

1443

1444

1445 if (!RemovedUser)

1446 J++;

1447 }

1448}

1449

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

1453}

1454

1458 });

1459}

1460#endif

1461

1463 Old2NewTy &Old2New,

1468 visitBlock(Base, Old2New, IAI);

1469 }

1470}

1471

1472void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,

1476 if (isa(&VPI))

1477 continue;

1478 assert(isa(&VPI) && "Can only handle VPInstructions");

1479 auto *VPInst = cast(&VPI);

1480

1481 auto *Inst = dyn_cast_or_null(VPInst->getUnderlyingValue());

1482 if (!Inst)

1483 continue;

1485 if (!IG)

1486 continue;

1487

1488 auto NewIGIter = Old2New.find(IG);

1489 if (NewIGIter == Old2New.end())

1491 IG->getFactor(), IG->isReverse(), IG->getAlign());

1492

1493 if (Inst == IG->getInsertPos())

1494 Old2New[IG]->setInsertPos(VPInst);

1495

1496 InterleaveGroupMap[VPInst] = Old2New[IG];

1497 InterleaveGroupMap[VPInst]->insertMember(

1498 VPInst, IG->getIndex(Inst),

1499 Align(IG->isReverse() ? (-1) * int(IG->getFactor())

1500 : IG->getFactor()));

1501 }

1503 visitRegion(Region, Old2New, IAI);

1504 else

1506}

1507

1512}

1513

1514void VPSlotTracker::assignName(const VPValue *V) {

1515 assert(!VPValue2Name.contains(V) && "VPValue already has a name!");

1516 auto *UV = V->getUnderlyingValue();

1517 auto *VPI = dyn_cast_or_null(V->getDefiningRecipe());

1518 if (!UV && !(VPI && !VPI->getName().empty())) {

1519 VPValue2Name[V] = (Twine("vp<%") + Twine(NextSlot) + ">").str();

1520 NextSlot++;

1521 return;

1522 }

1523

1524

1525

1526 std::string Name;

1527 if (UV) {

1529 UV->printAsOperand(S, false);

1530 } else

1531 Name = VPI->getName();

1532

1533 assert( Name .empty() && "Name cannot be empty.");

1535 std::string BaseName = (Twine(Prefix) + Name + Twine(">")).str();

1536

1537

1538 const auto &[A, _] = VPValue2Name.insert({V, BaseName});

1539

1540

1541 if (V->isLiveIn() && isa<ConstantInt, ConstantFP>(UV))

1542 return;

1543

1544

1545

1546 const auto &[C, UseInserted] = BaseName2Version.insert({BaseName, 0});

1547 if (!UseInserted) {

1548 C->second++;

1549 A->second = (BaseName + Twine(".") + Twine(C->second)).str();

1550 }

1551}

1552

1553void VPSlotTracker::assignNames(const VPlan &Plan) {

1555 assignName(&Plan.VF);

1557 assignName(&Plan.VFxUF);

1558 assignName(&Plan.VectorTripCount);

1559 if (Plan.BackedgeTakenCount)

1560 assignName(Plan.BackedgeTakenCount);

1562 assignName(LI);

1563

1567 VPBlockUtils::blocksOnly(RPOT))

1568 assignNames(VPBB);

1569}

1570

1571void VPSlotTracker::assignNames(const VPBasicBlock *VPBB) {

1573 for (VPValue *Def : Recipe.definedValues())

1574 assignName(Def);

1575}

1576

1578 std::string Name = VPValue2Name.lookup(V);

1579 if ( Name .empty())

1580 return Name;

1581

1582

1583

1584

1585

1586

1587

1588

1589 const VPRecipeBase *DefR = V->getDefiningRecipe();

1590 (void)DefR;

1592 "VPValue defined by a recipe in a VPlan?");

1593

1594

1595 if (auto *UV = V->getUnderlyingValue()) {

1596 std::string Name;

1598 UV->printAsOperand(S, false);

1599 return (Twine("ir<") + Name + ">").str();

1600 }

1601

1602 return "";

1603}

1604

1607 assert( Range .isEmpty() && "Trying to test an empty VF range.");

1608 bool PredicateAtRangeStart = Predicate(Range.Start);

1609

1611 if (Predicate(TmpVF) != PredicateAtRangeStart) {

1612 Range.End = TmpVF;

1613 break;

1614 }

1615

1616 return PredicateAtRangeStart;

1617}

1618

1619

1620

1621

1622

1623

1626 auto MaxVFTimes2 = MaxVF * 2;

1628 VFRange SubRange = {VF, MaxVFTimes2};

1629 auto Plan = buildVPlan(SubRange);

1631

1632

1634 VPlans.push_back(std::move(Plan));

1635 VF = SubRange.End;

1636 }

1637}

1638

1642 1 &&

1643 "Multiple VPlans for VF.");

1644

1647 return *Plan.get();

1648 }

1650}

1651

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

1654 if (VPlans.empty()) {

1655 O << "LV: No VPlans built.\n";

1656 return;

1657 }

1658 for (const auto &Plan : VPlans)

1661 else

1663}

1664#endif

1665

1668 if (!V->isLiveIn())

1669 return {};

1670

1672}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static const Function * getParent(const Value *V)

BlockVerifier::State From

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

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

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

dxil pretty DXIL Metadata Pretty Printer

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

static void dumpEdges(CFGMST< Edge, BBInfo > &MST, GCOVFunction &GF)

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

iv Induction Variable Users

This file provides a LoopVectorizationPlanner class.

cl::opt< unsigned > ForceTargetInstructionCost("force-target-instruction-cost", cl::init(0), cl::Hidden, cl::desc("A flag that overrides the target's expected cost for " "an instruction to a single constant value. Mostly " "useful for getting consistent testing."))

ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))

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

static StringRef getName(Value *V)

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

This file defines the SmallVector class.

This file provides utility VPlan to VPlan transformations.

static T * getPlanEntry(T *Start)

static T * getEnclosingLoopRegionForRegion(T *P)

Return the enclosing loop region for region P.

static bool isDefinedInsideLoopRegions(const VPValue *VPV)

Returns true if there is a vector loop region and VPV is defined in a loop region.

cl::opt< unsigned > ForceTargetInstructionCost

static bool hasConditionalTerminator(const VPBasicBlock *VPBB)

static void remapOperands(VPBlockBase *Entry, VPBlockBase *NewEntry, DenseMap< VPValue *, VPValue * > &Old2NewVPValues)

static std::pair< VPBlockBase *, VPBlockBase * > cloneFrom(VPBlockBase *Entry)

static cl::opt< bool > PrintVPlansInDotFormat("vplan-print-in-dot-format", cl::Hidden, cl::desc("Use dot format instead of plain text when dumping VPlans"))

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

static bool IsCondBranch(unsigned BrOpc)

static const uint32_t IV[8]

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

void print(raw_ostream &OS, AssemblyAnnotationWriter *AAW=nullptr, bool ShouldPreserveUseListOrder=false, bool IsForDebug=false) const

Print the basic block to an output stream with an optional AssemblyAnnotationWriter.

static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)

Creates a new BasicBlock.

const BasicBlock * getSingleSuccessor() const

Return the successor of this block if it has a single successor.

const Function * getParent() const

Return the enclosing method, or null if none.

InstListType::iterator iterator

Instruction iterators...

LLVMContext & getContext() const

Get the context in which this basic block lives.

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

static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)

static ConstantInt * getTrue(LLVMContext &Context)

std::optional< const DILocation * > cloneByMultiplyingDuplicationFactor(unsigned DF) const

Returns a new DILocation with duplication factor DF * current duplication factor encoded in the discr...

This class represents an Operation in the Expression.

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.

static constexpr UpdateKind Delete

static constexpr UpdateKind Insert

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

constexpr bool isScalar() const

Exactly one element.

bool shouldEmitDebugInfoForProfiling() const

Returns true if we should emit debug info for profiling.

void applyUpdates(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

void flush()

Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.

Common base class shared among various IRBuilders.

Value * CreateInsertElement(Type *VecTy, Value *NewElt, Value *Idx, const Twine &Name="")

Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")

UnreachableInst * CreateUnreachable()

Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")

Return a vector value that contains.

IntegerType * getInt32Ty()

Fetch the type representing a 32-bit integer.

BasicBlock * GetInsertBlock() const

void SetCurrentDebugLocation(DebugLoc L)

Set location information used by debugging information.

InsertPoint saveIP() const

Returns the current insert point.

ConstantInt * getInt32(uint32_t C)

Get a constant 32-bit value.

Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)

BranchInst * CreateBr(BasicBlock *Dest)

Create an unconditional 'br label X' instruction.

void restoreIP(InsertPoint IP)

Sets the current insert point to a previously-saved location.

void SetInsertPoint(BasicBlock *TheBB)

This specifies that created instructions should be appended to the end of the specified block.

Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

InnerLoopVectorizer vectorizes loops which contain only one basic block to a specified vectorization ...

static InstructionCost getInvalid(CostType Val=0)

InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

void moveBefore(Instruction *MovePos)

Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...

The group of interleaved loads/stores sharing the same stride and close to each other.

Drive the analysis of interleaved memory accesses in the loop.

InterleaveGroup< Instruction > * getInterleaveGroup(const Instruction *Instr) const

Get the interleave group that Instr belongs to.

BlockT * getLoopLatch() const

If there is a single latch block for this loop, return it.

BlockT * getUniqueLatchExitBlock() const

Return the unique exit block for the latch, or null if there are multiple different exit blocks or th...

void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)

This method is used by other analyses to update loop information.

void addChildLoop(LoopT *NewChild)

Add the specified loop to be a child of this loop.

void addTopLevelLoop(LoopT *New)

This adds the specified loop to the collection of top-level loops.

LoopT * AllocateLoop(ArgsTy &&...Args)

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

VPlan & getPlanFor(ElementCount VF) const

Return the VPlan for VF.

void buildVPlans(ElementCount MinVF, ElementCount MaxVF)

Build VPlans for power-of-2 VF's between MinVF and MaxVF inclusive, according to the information gath...

static bool getDecisionAndClampRange(const std::function< bool(ElementCount)> &Predicate, VFRange &Range)

Test a Predicate on a Range of VF's.

void printPlans(raw_ostream &O)

void annotateInstWithNoAlias(Instruction *VersionedInst, const Instruction *OrigInst)

Add the noalias annotations to VersionedInst.

Represents a single loop in the control flow graph.

void eraseFromParent()

This method unlinks 'this' from the containing function and deletes it.

static PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...

ScalarEvolution * getSE() const

Returns the ScalarEvolution analysis used.

const SCEV * getSymbolicMaxBackedgeTakenCount()

Get the (predicated) symbolic max backedge count for the analyzed loop.

BlockT * getEntry() const

Get the entry BasicBlock of the Region.

This class represents an analyzed expression in the program.

Type * getType() const

Return the LLVM type of this SCEV expression.

The main scalar evolution driver.

const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)

A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...

size_type size() const

Determine the number of elements in the SetVector.

bool insert(const value_type &X)

Insert a new element into the SetVector.

This class provides computation of slot numbers for LLVM Assembly writing.

A SetVector that performs no allocations if smaller than a certain size.

void push_back(const T &Elt)

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

StringRef - Represent a constant reference to a string, i.e.

std::pair< StringRef, StringRef > split(char Separator) const

Split into two substrings around the first occurrence of a separator character.

StringRef rtrim(char Char) const

Return string with consecutive Char characters starting from the right removed.

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

static OperandValueInfo getOperandInfo(const Value *V)

Collect properties of V used in cost analysis, e.g. OP_PowerOf2.

InstructionCost getCFInstrCost(unsigned Opcode, TTI::TargetCostKind CostKind=TTI::TCK_SizeAndLatency, const Instruction *I=nullptr) const

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

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

static IntegerType * getInt1Ty(LLVMContext &C)

LLVMContext & getContext() const

Return the LLVMContext in which this type was uniqued.

This function has undefined behavior.

void setOperand(unsigned i, Value *Val)

Value * getOperand(unsigned i) const

unsigned getNumOperands() const

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

void appendRecipe(VPRecipeBase *Recipe)

Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe.

RecipeListTy::iterator iterator

Instruction iterators...

void connectToPredecessors(VPTransformState::CFGState &CFG)

Connect the VPBBs predecessors' in the VPlan CFG to the IR basic block generated for this VPBB.

void execute(VPTransformState *State) override

The method which generates the output IR instructions that correspond to this VPBasicBlock,...

iterator begin()

Recipe iterator methods.

VPBasicBlock * clone() override

Clone the current block and it's recipes, without updating the operands of the cloned recipes.

InstructionCost cost(ElementCount VF, VPCostContext &Ctx) override

Return the cost of this VPBasicBlock.

iterator getFirstNonPhi()

Return the position of the first non-phi node recipe in the block.

VPRegionBlock * getEnclosingLoopRegion()

VPBasicBlock * splitAt(iterator SplitAt)

Split current block at SplitAt by inserting a new block between the current block and its successors ...

void executeRecipes(VPTransformState *State, BasicBlock *BB)

Execute the recipes in the IR basic block BB.

void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override

Print this VPBsicBlock to O, prefixing all lines with Indent.

bool isExiting() const

Returns true if the block is exiting it's parent region.

VPRecipeBase * getTerminator()

If the block has multiple successors, return the branch recipe terminating the block.

const VPRecipeBase & back() const

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

void setSuccessors(ArrayRef< VPBlockBase * > NewSuccs)

Set each VPBasicBlock in NewSuccss as successor of this VPBlockBase.

VPRegionBlock * getParent()

const VPBasicBlock * getExitingBasicBlock() const

void setName(const Twine &newName)

size_t getNumSuccessors() const

iterator_range< VPBlockBase ** > successors()

void printSuccessors(raw_ostream &O, const Twine &Indent) const

Print the successors of this block to O, prefixing all lines with Indent.

void setPredecessors(ArrayRef< VPBlockBase * > NewPreds)

Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.

VPBlockBase * getEnclosingBlockWithPredecessors()

const VPBlocksTy & getPredecessors() const

void setPlan(VPlan *ParentPlan)

Sets the pointer of the plan containing the block.

const VPBlocksTy & getHierarchicalSuccessors()

VPBlockBase * getEnclosingBlockWithSuccessors()

An Enclosing Block of a block B is any block containing B, including B itself.

const VPBasicBlock * getEntryBasicBlock() const

Helper for GraphTraits specialization that traverses through VPRegionBlocks.

static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)

Insert disconnected VPBlockBase NewBlock after BlockPtr.

static void connectBlocks(VPBlockBase *From, VPBlockBase *To, unsigned PredIdx=-1u, unsigned SuccIdx=-1u)

Connect VPBlockBases From and To bi-directionally.

VPlan-based builder utility analogous to IRBuilder.

This class augments a recipe with a set of VPValues defined by the recipe.

void dump() const

Dump the VPDef to stderr (for debugging).

virtual void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const =0

Each concrete VPDef prints itself.

Recipe to expand a SCEV expression.

A special type of VPBasicBlock that wraps an existing IR basic block.

void execute(VPTransformState *State) override

The method which generates the output IR instructions that correspond to this VPBasicBlock,...

VPIRBasicBlock * clone() override

Clone the current block and it's recipes, without updating the operands of the cloned recipes.

A recipe to wrap on original IR instruction not to be modified during execution, execept for PHIs.

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

VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI)

In what follows, the term "input IR" refers to code that is fed into the vectorizer whereas the term ...

Value * getAsRuntimeExpr(IRBuilderBase &Builder, const ElementCount &VF) const

Returns an expression describing the lane index that can be used at runtime.

static VPLane getFirstLane()

@ ScalableLast

For ScalableLast, Lane is the offset from the start of the last N-element subvector in a scalable vec...

@ First

For First, Lane is the index into the first N elements of a fixed-vector <N x > or a scalable v...

VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.

VPBasicBlock * getParent()

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

VPRegionBlock * clone() override

Clone all blocks in the single-entry single-exit region of the block and their recipes without updati...

const VPBlockBase * getEntry() const

bool isReplicator() const

An indicator whether this region is to generate multiple replicated instances of output IR correspond...

InstructionCost cost(ElementCount VF, VPCostContext &Ctx) override

Return the cost of the block.

void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override

Print this VPRegionBlock to O (recursively), prefixing all lines with Indent.

void execute(VPTransformState *State) override

The method which generates the output IR instructions that correspond to this VPRegionBlock,...

const VPBlockBase * getExiting() const

VPBasicBlock * getPreheaderVPBB()

Returns the pre-header VPBasicBlock of the loop region.

A recipe for handling phi nodes of integer and floating-point inductions, producing their scalar valu...

This class can be used to assign names to VPValues.

std::string getOrCreateName(const VPValue *V) const

Returns the name assigned to V, if there is one, otherwise try to construct one from the underlying v...

This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...

void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const

Print the operands to O.

bool isDefinedOutsideLoopRegions() const

Returns true if the VPValue is defined outside any loop region.

VPRecipeBase * getDefiningRecipe()

Returns the recipe defining this VPValue or nullptr if it is not defined by a recipe,...

void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const

void dump() const

Dump the value to stderr (for debugging).

VPValue(const unsigned char SC, Value *UV=nullptr, VPDef *Def=nullptr)

void print(raw_ostream &OS, VPSlotTracker &Tracker) const

void replaceAllUsesWith(VPValue *New)

unsigned getNumUsers() const

void replaceUsesWithIf(VPValue *New, llvm::function_ref< bool(VPUser &U, unsigned Idx)> ShouldReplace)

Go through the uses list for this VPValue and make each use point to New if the callback ShouldReplac...

VPDef * Def

Pointer to the VPDef that defines this VPValue.

A recipe for handling phi nodes of integer and floating-point inductions, producing their vector valu...

VPlanPrinter prints a given VPlan to a given output stream.

LLVM_DUMP_METHOD void dump()

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

void printDOT(raw_ostream &O) const

Print this VPlan in DOT format to O.

std::string getName() const

Return a string with the name of the plan and the applicable VFs and UFs.

void prepareToExecute(Value *TripCount, Value *VectorTripCount, VPTransformState &State)

Prepare the plan for execution, setting up the required live-in values.

VPBasicBlock * getEntry()

VPRegionBlock * createVPRegionBlock(VPBlockBase *Entry, VPBlockBase *Exiting, const std::string &Name="", bool IsReplicator=false)

Create a new VPRegionBlock with Entry, Exiting and Name.

VPValue & getVectorTripCount()

The vector trip count.

VPValue * getTripCount() const

The trip count of the original loop.

static VPlanPtr createInitialVPlan(Type *InductionTy, PredicatedScalarEvolution &PSE, bool RequiresScalarEpilogueCheck, bool TailFolded, Loop *TheLoop)

Create initial VPlan, having an "entry" VPBasicBlock (wrapping original scalar pre-header) which cont...

VPIRBasicBlock * createEmptyVPIRBasicBlock(BasicBlock *IRBB)

Create a VPIRBasicBlock wrapping IRBB, but do not create VPIRInstructions wrapping the instructions i...

bool hasVF(ElementCount VF)

VPRegionBlock * getVectorLoopRegion()

Returns the VPRegionBlock of the vector loop.

InstructionCost cost(ElementCount VF, VPCostContext &Ctx)

Return the cost of this plan.

VPBasicBlock * createVPBasicBlock(const Twine &Name, VPRecipeBase *Recipe=nullptr)

Create a new VPBasicBlock with Name and containing Recipe if present.

VPIRBasicBlock * createVPIRBasicBlock(BasicBlock *IRBB)

Create a VPIRBasicBlock from IRBB containing VPIRInstructions for all instructions in IRBB,...

VPValue * getOrAddLiveIn(Value *V)

Gets the live-in VPValue for V or adds a new live-in (if none exists yet) for V.

LLVM_DUMP_METHOD void dump() const

Dump the plan to stderr (for debugging).

void execute(VPTransformState *State)

Generate the IR code for this VPlan.

void print(raw_ostream &O) const

Print this VPlan to O.

VPIRBasicBlock * getScalarHeader() const

Return the VPIRBasicBlock wrapping the header of the scalar loop.

void printLiveIns(raw_ostream &O) const

Print the live-ins of this VPlan to O.

VPBasicBlock * getVectorPreheader()

Returns the preheader of the vector loop region, if one exists, or null otherwise.

VPlan * duplicate()

Clone the current VPlan, update all VPValues of the new VPlan and cloned recipes to refer to the clon...

LLVM Value Representation.

Type * getType() const

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

StringRef getName() const

Return a constant reference to the value's name.

static VectorType * get(Type *ElementType, ElementCount EC)

This static method is the primary way to construct an VectorType.

static constexpr bool isKnownLT(const FixedOrScalableQuantity &LHS, const FixedOrScalableQuantity &RHS)

constexpr bool isScalable() const

Returns whether the quantity is scaled by a runtime quantity (vscale).

constexpr ScalarTy getKnownMinValue() const

Returns the minimum value this quantity can represent.

An efficient, type-erasing, non-owning reference to a callable.

self_iterator getIterator()

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

A raw_ostream that writes to an std::string.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

@ Tail

Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...

@ C

The default llvm calling convention, compatible with C.

std::string EscapeString(const std::string &Label)

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

BinaryVPInstruction_match< Op0_t, Op1_t, VPInstruction::BranchOnCount > m_BranchOnCount(const Op0_t &Op0, const Op1_t &Op1)

UnaryVPInstruction_match< Op0_t, VPInstruction::BranchOnCond > m_BranchOnCond(const Op0_t &Op0)

class_match< VPValue > m_VPValue()

Match an arbitrary VPValue and ignore it.

bool isUniformAfterVectorization(const VPValue *VPV)

Returns true if VPV is uniform after vectorization.

VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, ScalarEvolution &SE)

Get or create a VPValue that corresponds to the expansion of Expr.

bool onlyFirstLaneUsed(const VPValue *Def)

Returns true if only the first lane of Def is used.

This is an optimization pass for GlobalISel generic memory operations.

auto drop_begin(T &&RangeOrContainer, size_t N=1)

Return a range covering RangeOrContainer with the first N elements excluded.

void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)

detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)

zip iterator for two or more iteratable types.

auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)

Get the size of a range.

auto successors(const MachineBasicBlock *BB)

Value * getRuntimeVF(IRBuilderBase &B, Type *Ty, ElementCount VF)

Return the runtime value for VF.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

void interleaveComma(const Container &c, StreamT &os, UnaryFunctor each_fn)

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

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.

Instruction * propagateMetadata(Instruction *I, ArrayRef< Value * > VL)

Specifically, let Kinds = [MD_tbaa, MD_alias_scope, MD_noalias, MD_fpmath, MD_nontemporal,...

Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)

cl::opt< bool > EnableFSDiscriminator

cl::opt< bool > EnableVPlanNativePath("enable-vplan-native-path", cl::Hidden, cl::desc("Enable VPlan-native vectorization path with " "support for outer loop vectorization."))

std::unique_ptr< VPlan > VPlanPtr

raw_ostream & dbgs()

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

bool isa(const From &Val)

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

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

auto count_if(R &&Range, UnaryPredicate P)

Wrapper function around std::count_if to count the number of times an element satisfying a given pred...

Value * createStepForVF(IRBuilderBase &B, Type *Ty, ElementCount VF, int64_t Step)

Return a value for Step multiplied by VF.

BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)

Split the specified block at the specified instruction.

auto find_if(R &&Range, UnaryPredicate P)

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

unsigned getReciprocalPredBlockProb()

A helper function that returns the reciprocal of the block probability of predicated blocks.

This struct is a compact representation of a valid (non-zero power of two) alignment.

A range of powers-of-2 vectorization factors with fixed start and adjustable end.

Struct to hold various analysis needed for cost computations.

TargetTransformInfo::OperandValueInfo getOperandInfo(VPValue *V) const

Returns the OperandInfo for V, if it is a live-in.

TargetTransformInfo::TargetCostKind CostKind

const TargetTransformInfo & TTI

Hold state information used when constructing the CFG of the output IR, traversing the VPBasicBlocks ...

BasicBlock * PrevBB

The previous IR BasicBlock created or used.

SmallDenseMap< VPBasicBlock *, BasicBlock * > VPBB2IRBB

A mapping of each VPBasicBlock to the corresponding BasicBlock.

VPBasicBlock * PrevVPBB

The previous VPBasicBlock visited. Initially set to null.

BasicBlock * ExitBB

The last IR BasicBlock in the output IR.

BasicBlock * getPreheaderBBFor(VPRecipeBase *R)

Returns the BasicBlock* mapped to the pre-header of the loop region containing R.

DomTreeUpdater DTU

Updater for the DominatorTree.

DenseMap< VPValue *, Value * > VPV2Vector

DenseMap< VPValue *, SmallVector< Value *, 4 > > VPV2Scalars

VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...

bool hasScalarValue(VPValue *Def, VPLane Lane)

bool hasVectorValue(VPValue *Def)

LoopInfo * LI

Hold a pointer to LoopInfo to register new basic blocks in the loop.

struct llvm::VPTransformState::DataState Data

void addMetadata(Value *To, Instruction *From)

Add metadata from one instruction to another.

void packScalarIntoVectorValue(VPValue *Def, const VPLane &Lane)

Construct the vector value of a scalarized value V one lane at a time.

Value * get(VPValue *Def, bool IsScalar=false)

Get the generated vector Value for a given VPValue Def if IsScalar is false, otherwise return the gen...

struct llvm::VPTransformState::CFGState CFG

LoopVersioning * LVer

LoopVersioning.

void addNewMetadata(Instruction *To, const Instruction *Orig)

Add additional metadata to To that was not present on Orig.

std::optional< VPLane > Lane

Hold the index to generate specific scalar instructions.

VPTransformState(const TargetTransformInfo *TTI, ElementCount VF, unsigned UF, LoopInfo *LI, DominatorTree *DT, IRBuilderBase &Builder, InnerLoopVectorizer *ILV, VPlan *Plan, Loop *CurrentParentLoop, Type *CanonicalIVTy)

IRBuilderBase & Builder

Hold a reference to the IRBuilder used to generate output IR code.

VPlan * Plan

Pointer to the VPlan code is generated for.

ElementCount VF

The chosen Vectorization Factor of the loop being vectorized.

void setDebugLocFrom(DebugLoc DL)

Set the debug location in the builder using the debug location DL.

Loop * CurrentParentLoop

The parent loop object for the current scope, or nullptr.

void set(VPValue *Def, Value *V, bool IsScalar=false)

Set the generated vector Value for a given VPValue, if IsScalar is false.

void print(raw_ostream &O) const

static void optimize(VPlan &Plan)

Apply VPlan-to-VPlan optimizations to Plan, including induction recipe optimizations,...