VPlan.cpp Source File (original) (raw)

49#include

50#include

52using namespace llvm;

59 "llvm.loop.vectorize.followup_vectorized";

61 "llvm.loop.vectorize.followup_epilogue";

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

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

70#define DEBUG_TYPE "loop-vectorize"

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

79#endif

83 switch (LaneKind) {

86 return Builder.CreateSub(getRuntimeVF(Builder, Builder.getInt32Ty(), VF),

89 return Builder.getInt32(Lane);

90 }

92}

97 Def->addDefinedValue(this);

98}

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

103 Def->removeDefinedValue(this);

104}

105

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

113

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

119 dbgs() << "\n";

120}

121

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

127 dbgs() << "\n";

128}

129#endif

130

134

138

139

140

143 T *Current = Start;

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

145 Current = Next;

146

148 WorkList.insert(Current);

149

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

151 T *Current = WorkList[i];

152 if (!Current->hasPredecessors())

153 return Current;

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

156 }

157

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

159}

160

162

164

165

172

179

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

182 Plan = ParentPlan;

183}

184

185

192

199

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

202 return this;

203 assert(Parent->getExiting() == this &&

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

205 return Parent->getEnclosingBlockWithSuccessors();

206}

207

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

210 return this;

211 assert(Parent->getEntry() == this &&

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

213 return Parent->getEnclosingBlockWithPredecessors();

214}

215

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

219 It++;

220 return It;

221}

222

230

232 if (Def->isLiveIn())

233 return Def->getLiveInIRValue();

234

236 return Data.VPV2Scalars[Def][Lane.mapToCacheIndex(VF)];

237

240 return Data.VPV2Scalars[Def][0];

241 }

242

243

244

247 return get(BuildVector->getOperand(Lane.getKnownLane()), true);

248 }

249

251 auto *VecPart = Data.VPV2Vector[Def];

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

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

254 return VecPart;

255 }

256

258 auto *Extract = Builder.CreateExtractElement(VecPart, LaneV);

259

260 return Extract;

261}

262

264 if (NeedsScalar) {

268 Data.VPV2Scalars[Def].size() == 1)) &&

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

270 "per part.");

272 }

273

274

276 return Data.VPV2Vector[Def];

277

278 auto GetBroadcastInstrs = [this](Value *V) {

279 if (VF.isScalar())

280 return V;

281

282 Value *Shuf = Builder.CreateVectorSplat(VF, V, "broadcast");

283 return Shuf;

284 };

285

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

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

289 Value *B = GetBroadcastInstrs(IRV);

291 return B;

292 }

293

295

296

297 if (VF.isScalar()) {

298 set(Def, ScalarValue);

299 return ScalarValue;

300 }

301

303 VPLane LastLane(IsSingleScalar ? 0 : VF.getFixedValue() - 1);

304

305

306

307

308 assert(IsSingleScalar && "must be a single-scalar at this point");

309

310

311

312 auto OldIP = Builder.saveIP();

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

317 Builder.SetInsertPoint(&*NewIP);

318 Value *VectorValue = GetBroadcastInstrs(ScalarValue);

319 set(Def, VectorValue);

320 Builder.restoreIP(OldIP);

321 return VectorValue;

322}

323

326

327

328 if (DIL &&

330 ->getParent()

331 ->shouldEmitDebugInfoForProfiling() &&

333

334 unsigned UF = Plan->getUF();

335 auto NewDIL =

337 if (NewDIL)

338 Builder.SetCurrentDebugLocation(*NewDIL);

339 else

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

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

342 } else

343 Builder.SetCurrentDebugLocation(DL);

344}

345

347 Value *WideValue,

352

353 for (unsigned I = 0, E = StructTy->getNumElements(); I != E; I++) {

354 Value *ScalarValue = Builder.CreateExtractValue(ScalarInst, I);

355 Value *VectorValue = Builder.CreateExtractValue(WideValue, I);

356 VectorValue =

357 Builder.CreateInsertElement(VectorValue, ScalarValue, LaneExpr);

358 WideValue = Builder.CreateInsertValue(WideValue, VectorValue, I);

359 }

360 } else {

361 WideValue = Builder.CreateInsertElement(WideValue, ScalarInst, LaneExpr);

362 }

363 return WideValue;

364}

365

367 auto &CFG = State.CFG;

368

369

374

375 return NewBB;

376}

377

379 auto &CFG = State.CFG;

381

382

383

384 Loop *ParentLoop = State.CurrentParentLoop;

385

386

387

389 SuccOrExitVPB = SuccOrExitVPB ? SuccOrExitVPB : this;

390 if (State.Plan->isExitBlock(SuccOrExitVPB)) {

391 ParentLoop = State.LI->getLoopFor(

393 }

394

395 if (ParentLoop && !State.LI->getLoopFor(NewBB))

397

400

402 } else {

404 }

405

406

408 VPBasicBlock *PredVPBB = PredVPBlock->getExitingBasicBlock();

410 assert(CFG.VPBB2IRBB.contains(PredVPBB) &&

411 "Predecessor basic-block not found building successor.");

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

415

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

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

420 DebugLoc DL = PredBBTerminator->getDebugLoc();

421 PredBBTerminator->eraseFromParent();

423 Br->setDebugLoc(DL);

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

425 TermBr->setSuccessor(0, NewBB);

426 } else {

427

428

429

430

431

432

433

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

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

437 (TermBr->getSuccessor(idx) == NewBB ||

438 PredVPBlock == getPlan()->getEntry())))) &&

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

440 TermBr->setSuccessor(idx, NewBB);

441 }

443 }

444}

445

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

449

451 IRBB->moveAfter(State->CFG.PrevBB);

452 State->Builder.SetInsertPoint(IRBB->getTerminator());

453 State->CFG.PrevBB = IRBB;

454 State->CFG.VPBB2IRBB[this] = IRBB;

456

457

459 auto *Br = State->Builder.CreateBr(IRBB);

460 Br->setOperand(0, nullptr);

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

462 } else {

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

466 }

467

469}

470

475 return NewBlock;

476}

477

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

480 BasicBlock *NewBB = State->CFG.PrevBB;

481

483

484 Loop *PrevParentLoop = State->CurrentParentLoop;

485 State->CurrentParentLoop = State->LI->AllocateLoop();

486

487

488

489 if (PrevParentLoop)

490 PrevParentLoop->addChildLoop(State->CurrentParentLoop);

491 else

492 State->LI->addTopLevelLoop(State->CurrentParentLoop);

493 }

494

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

497 assert((!R || R->isReplicator()) &&

498 "only replicate region blocks should remain");

499 return R;

500 };

501

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

504

505

506

507 State->CFG.VPBB2IRBB[this] = NewBB;

508 } else {

509 NewBB = createEmptyBasicBlock(*State);

510

511 State->Builder.SetInsertPoint(NewBB);

512

513 UnreachableInst *Terminator = State->Builder.CreateUnreachable();

514 State->Builder.SetInsertPoint(Terminator);

515

516 State->CFG.PrevBB = NewBB;

517 State->CFG.VPBB2IRBB[this] = NewBB;

519 }

520

521

523

524

526 State->CurrentParentLoop = State->CurrentParentLoop->getParentLoop();

527}

528

533 return NewBlock;

534}

535

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

539

540 State->CFG.PrevVPBB = this;

541

543 State->setDebugLocFrom(Recipe.getDebugLoc());

544 Recipe.execute(*State);

545 }

546

548}

549

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

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

553

554

557

558

562

564}

565

566

567

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

570 P = P->getParent();

571

572

573 assert(( || ->isReplicator()) && "unexpected nested replicate regions");

574 }

575 return P;

576}

577

581

585

587 if (VPBB->empty()) {

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

591 return false;

592 }

593

601 (void)IsSwitch;

605 "block with multiple successors not terminated by "

606 "conditional branch nor switch recipe");

607

608 return true;

609 }

610

612 assert(IsSwitch && "block with more than 2 successors not terminated by "

613 "a switch recipe");

614 return true;

615 }

616

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

620 return false;

621}

622

625 return &back();

626 return nullptr;

627}

628

631 return &back();

632 return nullptr;

633}

634

638

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

644

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

648 } else {

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

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

653 O << '\n';

654 }

655}

656

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

660

661 auto RecipeIndent = Indent + " ";

664 O << '\n';

665 }

666

668}

669#endif

670

672

673

674

675

676

677

681 bool InRegion = Entry->getParent();

682

685 Old2NewVPBlocks[BB] = NewBB;

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

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

688 Exiting = BB;

689 }

690 }

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

692

693

695 VPBlockBase *NewBB = Old2NewVPBlocks[BB];

698 NewPreds.push_back(Old2NewVPBlocks[Pred]);

699 }

703 NewSuccs.push_back(Old2NewVPBlocks[Succ]);

704 }

706 }

707

708#if !defined(NDEBUG)

709

710

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

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

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

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

717

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

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

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

721 }

722#endif

723

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

725 Exiting ? Old2NewVPBlocks[Exiting] : nullptr);

726}

727

731 VPRegionBlock *NewRegion =

733 ? Plan.createReplicateRegion(NewEntry, NewExiting, getName())

734 : Plan.createLoopRegion(getName(), NewEntry, NewExiting);

735

737 Block->setParent(NewRegion);

738 return NewRegion;

739}

740

743 "Loop regions should have been lowered to plain CFG");

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

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

746

748 Entry);

749 State->Lane = VPLane(0);

750 for (unsigned Lane = 0, VF = State->VF.getFixedValue(); Lane < VF; ++Lane) {

752

755 Block->execute(State);

756 }

757 }

758

759

760 State->Lane.reset();

761}

762

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

768}

769

774 } else {

777 "must be in the entry block of a non-replicate region");

779 "loop region has a single predecessor (preheader), its entry block "

780 "has 2 incoming blocks");

781

782

783

784 Pred = Idx == 0 ? Region->getSinglePredecessor() : Region;

785 }

786 return Pred->getExitingBasicBlock();

787}

788

797 : Ctx.TTI.getCFInstrCost(Instruction::Br, Ctx.CostKind);

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

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

800 Cost += BackedgeCost;

802 }

803

804

805

806

807

810

811

812 assert(VF.isVector() && "Can only compute vector cost at the moment.");

814 return Then->cost(VF, Ctx);

815}

816

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

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

821 auto NewIndent = Indent + " ";

823 O << '\n';

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

825 }

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

827

829}

830#endif

831

835 assert(this == getPlan()->getVectorLoopRegion() &&

836 "Canonical IV must be in the entry of the top-level loop region");

838 {CanIV->getStartValue(), CanIV->getBackedgeValue()},

839 CanIV->getDebugLoc(), "index");

841 CanIV->eraseFromParent();

842 }

843

849

852

856}

857

861

863 L->getUniqueExitBlocks(IRExitBlocks);

866}

867

870

871 for (auto *VPB : CreatedBlocks) {

873

874

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

877 Def->replaceAllUsesWith(&DummyValue);

878

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

880 R.setOperand(I, &DummyValue);

881 }

882 }

883 delete VPB;

884 }

886 delete VPV;

887 delete BackedgeTakenCount;

888}

889

893 });

895 return *Iter;

896}

897

901

902

903

904

906

907 State->CFG.PrevVPBB = nullptr;

908 State->CFG.ExitBB = State->CFG.PrevBB->getSingleSuccessor();

909

910

911

912 State->VPDT.recalculate(*this);

913

914

915 BasicBlock *VectorPreHeader = State->CFG.PrevBB;

917 State->CFG.DTU.applyUpdates(

919

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

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

924

925 BasicBlock *ScalarPh = State->CFG.ExitBB;

928

929

930

931 State->CFG.DTU.applyUpdates(

933 }

935 Entry);

936

937

939 Block->execute(State);

940

941

943

944

945

948 if (R.getNumOperands() == 1)

949 R.eraseFromParent();

950 }

951 }

952

953 Loop *OrigLoop =

954 State->LI->getLoopFor(getScalarHeader()->getIRBasicBlock());

957 for (auto *BB : Blocks)

958 State->LI->removeBlock(BB);

960 State->LI->erase(OrigLoop);

961 }

962

963 State->CFG.DTU.flush();

964

966 if (!Header)

967 return;

968

970 BasicBlock *VectorLatchBB = State->CFG.VPBB2IRBB[LatchVPBB];

971

972

973

975

977 continue;

978

980

984

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

986

987

988 Value *Val = State->get(PhiR->getOperand(1), NeedsScalar);

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

990 }

991}

992

994

995

996

998

999

1000

1005 }))

1007

1008 return Cost;

1009}

1010

1012

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

1016 return nullptr;

1017}

1018

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

1023 return nullptr;

1024}

1025

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

1029

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

1031 O << "\nLive-in ";

1033 O << " = VF";

1034 }

1035

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

1037 O << "\nLive-in ";

1039 O << " = VF * UF";

1040 }

1041

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

1043 O << "\nLive-in ";

1044 VectorTripCount.printAsOperand(O, SlotTracker);

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

1046 }

1047

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

1049 O << "\nLive-in ";

1050 BackedgeTakenCount->printAsOperand(O, SlotTracker);

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

1052 }

1053

1054 O << "\n";

1055 if (TripCount) {

1056 if (TripCount->isLiveIn())

1057 O << "Live-in ";

1058 TripCount->printAsOperand(O, SlotTracker);

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

1060 O << "\n";

1061 }

1062}

1063

1067

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

1069

1071

1075 O << '\n';

1077 }

1078

1079 O << "}\n";

1080}

1081

1083 std::string Out;

1085 RSO << Name << " for ";

1086 if (!VFs.empty()) {

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

1089 RSO << "," << VF;

1090 RSO << "},";

1091 }

1092

1093 if (UFs.empty()) {

1094 RSO << "UF>=1";

1095 } else {

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

1098 RSO << "," << UF;

1099 RSO << "}";

1100 }

1101

1102 return Out;

1103}

1104

1110

1113#endif

1114

1117

1118

1119

1121 OldDeepRPOT(Entry);

1123 NewDeepRPOT(NewEntry);

1124

1125

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

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

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

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

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

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

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

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

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

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

1138 Old2NewVPValues[OldV] = NewV;

1139 }

1140 }

1141

1142

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

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

1148 NewR.setOperand(I, NewOp);

1149 }

1150 }

1151}

1152

1154 unsigned NumBlocksBeforeCloning = CreatedBlocks.size();

1155

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

1157

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

1165 }));

1166 } else {

1168 }

1169

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

1173 Old2NewVPValues[OldLiveIn] =

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

1175 }

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

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

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

1179 if (BackedgeTakenCount) {

1180 NewPlan->BackedgeTakenCount = new VPValue();

1181 Old2NewVPValues[BackedgeTakenCount] = NewPlan->BackedgeTakenCount;

1182 }

1183 if (TripCount && TripCount->isLiveIn())

1184 Old2NewVPValues[TripCount] =

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

1186

1187

1188

1189 remapOperands(Entry, NewEntry, Old2NewVPValues);

1190

1191

1192 NewPlan->VFs = VFs;

1193 NewPlan->UFs = UFs;

1194

1195 NewPlan->Name = Name;

1196 if (TripCount) {

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

1199 NewPlan->TripCount = Old2NewVPValues[TripCount];

1200 }

1201

1202

1203

1204 unsigned NumBlocksAfterCloning = CreatedBlocks.size();

1205 for (unsigned I :

1206 seq(NumBlocksBeforeCloning, NumBlocksAfterCloning))

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

1208 CreatedBlocks.truncate(NumBlocksBeforeCloning);

1209

1210

1211 for (VPBlockBase *VPB : NewPlan->CreatedBlocks) {

1213 VPB != NewScalarHeader)

1215 }

1216

1217 return NewPlan;

1218}

1219

1222 CreatedBlocks.push_back(VPIRBB);

1223 return VPIRBB;

1224}

1225

1231 return VPIRBB;

1232}

1233

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

1235

1239}

1240

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

1243 if (!Name.empty())

1244 return Name;

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

1246}

1247

1249 Depth = 1;

1250 bumpIndent(0);

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

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

1253 if (!Plan.getName().empty())

1255

1256 {

1257

1258 std::string Str;

1260 Plan.printLiveIns(SS);

1263 for (auto Line : Lines)

1265 }

1266

1267 OS << "\"]\n";

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

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

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

1271

1273 dumpBlock(Block);

1274

1275 OS << "}\n";

1276}

1277

1283 else

1285}

1286

1288 bool Hidden, const Twine &Label) {

1289

1290

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

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

1295 if (Tail != From)

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

1297 if (Head != To)

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

1299 if (Hidden)

1300 OS << "; splines=none";

1301 OS << "]\n";

1302}

1303

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

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

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

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

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

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

1311 } else {

1312 unsigned SuccessorNumber = 0;

1313 for (auto *Successor : Successors)

1314 drawEdge(Block, Successor, false, Twine(SuccessorNumber++));

1315 }

1316}

1317

1319

1320

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

1322 bumpIndent(1);

1323 std::string Str;

1324 raw_string_ostream SS(Str);

1325

1326 BasicBlock->print(SS, "", SlotTracker);

1327

1328

1329

1331 StringRef(Str).rtrim('\n').split(Lines, "\n");

1332

1333 auto EmitLine = [&](StringRef Line, StringRef Suffix) {

1335 };

1336

1337

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

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

1341

1342 bumpIndent(-1);

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

1344

1345 dumpEdges(BasicBlock);

1346}

1347

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

1350 bumpIndent(1);

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

1352 << Indent << "label=\""

1355

1356 assert(Region->getEntry() && "Region contains no inner blocks.");

1358 dumpBlock(Block);

1359 bumpIndent(-1);

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

1361 dumpEdges(Region);

1362}

1363

1364#endif

1365

1366

1367

1370 return DefR && (!DefR->getParent()->getPlan()->getVectorLoopRegion() ||

1372}

1373

1380

1384

1385

1386

1387 if (this == New)

1388 return;

1389

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

1392 bool RemovedUser = false;

1395 continue;

1396

1397 RemovedUser = true;

1399 }

1400

1401

1402

1403 if (!RemovedUser)

1404 J++;

1405 }

1406}

1407

1409 for (unsigned Idx = 0; Idx != getNumOperands(); ++Idx) {

1412 }

1413}

1414

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

1419

1425#endif

1426

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

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

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

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

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

1433 NextSlot++;

1434 return;

1435 }

1436

1437

1438

1439 std::string Name;

1440 if (UV)

1442 else

1443 Name = VPI->getName();

1444

1445 assert(!Name.empty() && "Name cannot be empty.");

1446 StringRef Prefix = UV ? "ir<" : "vp<%";

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

1448

1449

1450 const auto &[A, _] = VPValue2Name.try_emplace(V, BaseName);

1451

1452

1454 return;

1455

1456

1457

1458 const auto &[C, UseInserted] = BaseName2Version.try_emplace(BaseName, 0);

1459 if (!UseInserted) {

1460 C->second++;

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

1462 }

1463}

1464

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

1467 assignName(&Plan.VF);

1469 assignName(&Plan.VFxUF);

1470 assignName(&Plan.VectorTripCount);

1471 if (Plan.BackedgeTakenCount)

1472 assignName(Plan.BackedgeTakenCount);

1473 for (VPValue *LI : Plan.getLiveIns())

1474 assignName(LI);

1475

1476 ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<const VPBlockBase *>>

1477 RPOT(VPBlockDeepTraversalWrapper<const VPBlockBase *>(Plan.getEntry()));

1478 for (const VPBasicBlock *VPBB :

1480 assignNames(VPBB);

1481}

1482

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

1484 for (const VPRecipeBase &Recipe : *VPBB)

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

1486 assignName(Def);

1487}

1488

1489std::string VPSlotTracker::getName(const Value *V) {

1490 std::string Name;

1491 raw_string_ostream S(Name);

1493 V->printAsOperand(S, false);

1494 return Name;

1495 }

1496

1497 if (!MST) {

1498

1499

1501

1502 if (I->getParent()) {

1503 MST = std::make_unique(I->getModule());

1504 MST->incorporateFunction(*I->getFunction());

1505 } else {

1506 MST = std::make_unique(nullptr);

1507 }

1508 }

1509 V->printAsOperand(S, false, *MST);

1510 return Name;

1511}

1512

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

1515 if (!Name.empty())

1516 return Name;

1517

1518

1519

1520

1521

1522

1523

1524

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

1526 (void)DefR;

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

1529

1530

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

1532 std::string Name;

1534 UV->printAsOperand(S, false);

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

1536 }

1537

1538 return "";

1539}

1540

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

1544 bool PredicateAtRangeStart = Predicate(Range.Start);

1545

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

1548 Range.End = TmpVF;

1549 break;

1550 }

1551

1552 return PredicateAtRangeStart;

1553}

1554

1555

1556

1557

1558

1559

1562 auto MaxVFTimes2 = MaxVF * 2;

1564 VFRange SubRange = {VF, MaxVFTimes2};

1565 if (auto Plan = tryToBuildVPlan(SubRange)) {

1567

1568

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

1571 }

1572 VF = SubRange.End;

1573 }

1574}

1575

1578 [VF](const VPlanPtr &Plan) { return Plan->hasVF(VF); }) ==

1579 1 &&

1580 "Multiple VPlans for VF.");

1581

1582 for (const VPlanPtr &Plan : VPlans) {

1583 if (Plan->hasVF(VF))

1584 return *Plan.get();

1585 }

1587}

1588

1591

1593 bool IsUnrollMetadata = false;

1594 MDNode *LoopID = L->getLoopID();

1595 if (LoopID) {

1596

1597 for (unsigned I = 1, IE = LoopID->getNumOperands(); I < IE; ++I) {

1599 if (MD) {

1601 if (!S)

1602 continue;

1603 if (S->getString().starts_with("llvm.loop.unroll.runtime.disable"))

1604 continue;

1605 IsUnrollMetadata =

1606 S->getString().starts_with("llvm.loop.unroll.disable");

1607 }

1609 }

1610 }

1611

1612 if (!IsUnrollMetadata) {

1613

1614 LLVMContext &Context = L->getHeader()->getContext();

1617 MDString::get(Context, "llvm.loop.unroll.runtime.disable"));

1621

1623 L->setLoopID(NewLoopID);

1624 }

1625}

1626

1629 bool VectorizingEpilogue, MDNode *OrigLoopID,

1630 std::optional OrigAverageTripCount,

1631 unsigned OrigLoopInvocationWeight, unsigned EstimatedVFxUF,

1632 bool DisableRuntimeUnroll) {

1633

1634

1635

1637 std::optional<MDNode *> RemainderLoopID =

1640 if (RemainderLoopID) {

1641 OrigLoop->setLoopID(*RemainderLoopID);

1642 } else {

1643 if (DisableRuntimeUnroll)

1645

1647 Hints.setAlreadyVectorized();

1648 }

1649 }

1650

1651 if (!VectorLoop)

1652 return;

1653

1657 VectorLoop->setLoopID(*VectorizedLoopID);

1658 } else {

1659

1660

1661 if (OrigLoopID)

1662 VectorLoop->setLoopID(OrigLoopID);

1663

1664 if (!VectorizingEpilogue) {

1666 Hints.setAlreadyVectorized();

1667 }

1668 }

1670 TTI.getUnrollingPreferences(VectorLoop, *PSE.getSE(), UP, ORE);

1673

1674

1675

1676

1677

1678

1679

1680

1681

1682

1683

1684

1685

1686

1687 if (!OrigAverageTripCount)

1688 return;

1689

1690 unsigned AverageVectorTripCount = *OrigAverageTripCount / EstimatedVFxUF;

1691

1692 unsigned RemainderAverageTripCount = *OrigAverageTripCount % EstimatedVFxUF;

1693

1694 if (HeaderVPBB) {

1696 OrigLoopInvocationWeight);

1697 }

1700 OrigLoopInvocationWeight);

1701 }

1702}

1703

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

1706 if (VPlans.empty()) {

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

1708 return;

1709 }

1710 for (const auto &Plan : VPlans)

1713 else

1715}

1716#endif

1717

1721 unsigned WideSize = C->getBitWidth();

1723 ? TruncatedVal.sext(WideSize)

1724 : TruncatedVal.zext(WideSize);

1725 return ExtendedVal == *C;

1726}

1727

1730 if (!V->isLiveIn())

1731 return {};

1732

1734}

1735

1738 bool AlwaysIncludeReplicatingR) {

1740 return 0;

1741

1743 "Scalarization overhead not supported for scalable vectors");

1744

1746

1747 if (!ResultTy->isVoidTy()) {

1748 for (Type *VectorTy :

1750 ScalarizationCost += TTI.getScalarizationOverhead(

1752 true,

1753 false, CostKind);

1754 }

1755 }

1756

1757

1760 for (auto *Op : Operands) {

1761 if (Op->isLiveIn() ||

1762 (!AlwaysIncludeReplicatingR &&

1766 !UniqueOperands.insert(Op).second)

1767 continue;

1769 }

1770 return ScalarizationCost +

1771 TTI.getOperandsScalarizationOverhead(Tys, CostKind);

1772}

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

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

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

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

#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

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

This file defines the LoopVectorizationLegality class.

This file provides a LoopVectorizationPlanner class.

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)

This file defines the SmallVector class.

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.

This file provides utility VPlan to VPlan transformations.

static void addRuntimeUnrollDisableMetaData(Loop *L)

Definition VPlan.cpp:1589

static T * getPlanEntry(T *Start)

Definition VPlan.cpp:141

static T * getEnclosingLoopRegionForRegion(T *P)

Return the enclosing loop region for region P.

Definition VPlan.cpp:568

const char LLVMLoopVectorizeFollowupAll[]

Definition VPlan.cpp:57

static bool isDefinedInsideLoopRegions(const VPValue *VPV)

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

Definition VPlan.cpp:1368

static bool hasConditionalTerminator(const VPBasicBlock *VPBB)

Definition VPlan.cpp:586

const char LLVMLoopVectorizeFollowupVectorized[]

Definition VPlan.cpp:58

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

Definition VPlan.cpp:1115

const char LLVMLoopVectorizeFollowupEpilogue[]

Definition VPlan.cpp:60

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

Definition VPlan.cpp:678

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)

Class for arbitrary precision integers.

static APInt getAllOnes(unsigned numBits)

Return an APInt of a specified width with all bits set.

LLVM_ABI APInt zext(unsigned width) const

Zero extend to a new width.

LLVM_ABI APInt sext(unsigned width) const

Sign extend to a new width.

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

A cache of @llvm.assume calls within a function.

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

const Function * getParent() const

Return the enclosing method, or null if none.

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

Creates a new BasicBlock.

LLVM_ABI const BasicBlock * getSingleSuccessor() const

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

InstListType::iterator iterator

Instruction iterators...

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

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

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

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 isVector() const

One or more elements.

constexpr bool isScalar() const

Exactly one element.

Common base class shared among various IRBuilders.

static InstructionCost getInvalid(CostType Val=0)

This is an important class for using LLVM in a threaded context.

A helper class to return the specified delimiter string after the first invocation of operator String...

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

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

std::vector< BlockT * > & getBlocksVector()

Return a direct, mutable handle to the blocks vector so that we can mutate it efficiently with techni...

void addChildLoop(LoopT *NewChild)

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

VPlan & getPlanFor(ElementCount VF) const

Return the VPlan for VF.

Definition VPlan.cpp:1576

void updateLoopMetadataAndProfileInfo(Loop *VectorLoop, VPBasicBlock *HeaderVPBB, const VPlan &Plan, bool VectorizingEpilogue, MDNode *OrigLoopID, std::optional< unsigned > OrigAverageTripCount, unsigned OrigLoopInvocationWeight, unsigned EstimatedVFxUF, bool DisableRuntimeUnroll)

Update loop metadata and profile info for both the scalar remainder loop and VectorLoop,...

Definition VPlan.cpp:1627

void buildVPlans(ElementCount MinVF, ElementCount MaxVF)

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

Definition VPlan.cpp:1560

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

Test a Predicate on a Range of VF's.

Definition VPlan.cpp:1541

void printPlans(raw_ostream &O)

Definition VPlan.cpp:1705

Utility class for getting and setting loop vectorizer hints in the form of loop metadata.

Represents a single loop in the control flow graph.

void setLoopID(MDNode *LoopID) const

Set the llvm.loop loop id metadata for this loop.

LLVM_ABI void replaceOperandWith(unsigned I, Metadata *New)

Replace a specific operand.

const MDOperand & getOperand(unsigned I) const

static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)

unsigned getNumOperands() const

Return number of MDNode operands.

static LLVM_ABI MDString * get(LLVMContext &Context, StringRef Str)

BlockT * getEntry() const

Get the entry BasicBlock of the Region.

size_type size() const

Determine the number of elements in the SetVector.

void insert_range(Range &&R)

bool insert(const value_type &X)

Insert a new element into the SetVector.

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

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.

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.

std::pair< iterator, bool > try_emplace(StringRef Key, ArgsTy &&...Args)

Emplace a new element for the specified key into the map if the key isn't already in the map.

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 LLVM_ABI OperandValueInfo getOperandInfo(const Value *V)

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

PartialReductionExtendKind

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.

LLVM_ABI unsigned getScalarSizeInBits() const LLVM_READONLY

If this is a vector type, return the getPrimitiveSizeInBits value for the element type.

bool isVoidTy() const

Return true if this is 'void'.

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 execute(VPTransformState *State) override

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

Definition VPlan.cpp:478

iterator begin()

Recipe iterator methods.

VPBasicBlock * clone() override

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

Definition VPlan.cpp:529

InstructionCost cost(ElementCount VF, VPCostContext &Ctx) override

Return the cost of this VPBasicBlock.

Definition VPlan.cpp:763

const VPBasicBlock * getCFGPredecessor(unsigned Idx) const

Returns the predecessor block at index Idx with the predecessors as per the corresponding plain CFG.

Definition VPlan.cpp:770

iterator getFirstNonPhi()

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

Definition VPlan.cpp:216

void connectToPredecessors(VPTransformState &State)

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

Definition VPlan.cpp:378

VPRegionBlock * getEnclosingLoopRegion()

Definition VPlan.cpp:578

VPBasicBlock * splitAt(iterator SplitAt)

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

Definition VPlan.cpp:550

RecipeListTy Recipes

The VPRecipes held in the order of output instructions to generate.

void executeRecipes(VPTransformState *State, BasicBlock *BB)

Execute the recipes in the IR basic block BB.

Definition VPlan.cpp:536

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

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

Definition VPlan.cpp:657

bool isExiting() const

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

Definition VPlan.cpp:635

VPRecipeBase * getTerminator()

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

Definition VPlan.cpp:623

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

Definition VPlan.cpp:186

void setName(const Twine &newName)

size_t getNumSuccessors() const

iterator_range< VPBlockBase ** > successors()

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

Print plain-text dump of this VPBlockBase to O, prefixing all lines with Indent.

bool hasPredecessors() const

Returns true if this block has any predecessors.

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

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

Definition VPlan.cpp:645

size_t getNumPredecessors() const

void setPredecessors(ArrayRef< VPBlockBase * > NewPreds)

Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.

VPBlockBase * getEnclosingBlockWithPredecessors()

Definition VPlan.cpp:208

const VPBlocksTy & getPredecessors() const

virtual VPBlockBase * clone()=0

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

VPlan * getPlan()

Definition VPlan.cpp:161

void setPlan(VPlan *ParentPlan)

Sets the pointer of the plan containing the block.

Definition VPlan.cpp:180

const std::string & getName() const

VPBlockBase * getSinglePredecessor() const

const VPBlocksTy & getHierarchicalSuccessors()

VPBlockBase(const unsigned char SC, const std::string &N)

VPBlockBase * getEnclosingBlockWithSuccessors()

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

Definition VPlan.cpp:200

const VPBasicBlock * getEntryBasicBlock() const

Definition VPlan.cpp:166

VPBlockBase * getSingleHierarchicalPredecessor()

VPBlockBase * getSingleSuccessor() const

const VPBlocksTy & getSuccessors() const

static auto blocksOnly(const T &Range)

Return an iterator range over Range which only includes BlockTy blocks.

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

Insert disconnected VPBlockBase NewBlock after BlockPtr.

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

Returns true if VPB is a loop latch, using isHeader().

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.

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

Connect VPBlockBases From and To bi-directionally.

static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)

Disconnect VPBlockBases From and To bi-directionally.

VPlan-based builder utility analogous to IRBuilder.

VPPhi * createScalarPhi(ArrayRef< VPValue * > IncomingValues, DebugLoc DL, const Twine &Name="")

LLVM_ABI_FOR_TEST void dump() const

Dump the VPDef to stderr (for debugging).

Definition VPlan.cpp:122

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

Each concrete VPDef prints itself.

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

Definition VPlan.cpp:446

BasicBlock * getIRBasicBlock() const

VPIRBasicBlock * clone() override

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

Definition VPlan.cpp:471

static LLVM_ABI_FOR_TEST VPIRInstruction * create(Instruction &I)

Create a new VPIRPhi for \I , if it is a PHINode, otherwise create a VPIRInstruction.

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.

Definition VPlan.cpp:81

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.

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

Print the recipe, delegating to printRecipe().

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

Definition VPlan.cpp:728

const VPBlockBase * getEntry() const

void dissolveToCFGLoop()

Remove the current region from its VPlan, connecting its predecessor to its entry,...

Definition VPlan.cpp:832

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.

Definition VPlan.cpp:789

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

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

Definition VPlan.cpp:818

void execute(VPTransformState *State) override

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

Definition VPlan.cpp:741

const VPBlockBase * getExiting() const

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

Definition VPlan.cpp:1513

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

void replaceUsesOfWith(VPValue *From, VPValue *To)

Replaces all uses of From in the VPUser with To.

Definition VPlan.cpp:1408

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

Print the operands to O.

Definition VPlan.cpp:1420

void setOperand(unsigned I, VPValue *New)

unsigned getNumOperands() const

VPValue * getOperand(unsigned N) const

This is the base class of the VPlan Def/Use graph, used for modeling the data flow into,...

bool isDefinedOutsideLoopRegions() const

Returns true if the VPValue is defined outside any loop.

Definition VPlan.cpp:1374

VPRecipeBase * getDefiningRecipe()

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

Definition VPlan.cpp:131

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

Definition VPlan.cpp:1416

Value * UnderlyingVal

Hold the underlying Value, if any, attached to this VPValue.

void dump() const

Dump the value to stderr (for debugging).

Definition VPlan.cpp:114

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

Definition VPlan.cpp:94

virtual ~VPValue()

Definition VPlan.cpp:100

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

Definition VPlan.cpp:107

void replaceAllUsesWith(VPValue *New)

Definition VPlan.cpp:1377

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

Definition VPlan.cpp:1381

VPDef * Def

Pointer to the VPDef that defines this VPValue.

LLVM_DUMP_METHOD void dump()

Definition VPlan.cpp:1248

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

LLVM_ABI_FOR_TEST void printDOT(raw_ostream &O) const

Print this VPlan in DOT format to O.

Definition VPlan.cpp:1106

friend class VPSlotTracker

std::string getName() const

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

Definition VPlan.cpp:1082

VPBasicBlock * getEntry()

void setName(const Twine &newName)

VPIRBasicBlock * getExitBlock(BasicBlock *IRBB) const

Return the VPIRBasicBlock corresponding to IRBB.

Definition VPlan.cpp:890

LLVM_ABI_FOR_TEST ~VPlan()

Definition VPlan.cpp:868

bool isExitBlock(VPBlockBase *VPBB)

Returns true if VPBB is an exit block.

Definition VPlan.cpp:898

friend class VPlanPrinter

VPIRBasicBlock * createEmptyVPIRBasicBlock(BasicBlock *IRBB)

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

Definition VPlan.cpp:1220

ArrayRef< VPIRBasicBlock * > getExitBlocks() const

Return an ArrayRef containing VPIRBasicBlocks wrapping the exit blocks of the original scalar loop.

LLVM_ABI_FOR_TEST VPRegionBlock * getVectorLoopRegion()

Returns the VPRegionBlock of the vector loop.

Definition VPlan.cpp:1011

InstructionCost cost(ElementCount VF, VPCostContext &Ctx)

Return the cost of this plan.

Definition VPlan.cpp:993

void setEntry(VPBasicBlock *VPBB)

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

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

LLVM_ABI_FOR_TEST VPIRBasicBlock * createVPIRBasicBlock(BasicBlock *IRBB)

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

Definition VPlan.cpp:1226

LLVM_DUMP_METHOD void dump() const

Dump the plan to stderr (for debugging).

Definition VPlan.cpp:1112

VPBasicBlock * getScalarPreheader() const

Return the VPBasicBlock for the preheader of the scalar loop.

void execute(VPTransformState *State)

Generate the IR code for this VPlan.

Definition VPlan.cpp:905

ArrayRef< VPValue * > getLiveIns() const

Return the list of live-in VPValues available in the VPlan.

LLVM_ABI_FOR_TEST void print(raw_ostream &O) const

Print this VPlan to O.

Definition VPlan.cpp:1065

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.

Definition VPlan.cpp:1027

LLVM_ABI_FOR_TEST VPlan * duplicate()

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

Definition VPlan.cpp:1153

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.

constexpr ScalarTy getFixedValue() const

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.

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

@ BasicBlock

Various leaf nodes.

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

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

Combine two pattern matchers matching L || R.

VPInstruction_match< VPInstruction::BranchOnCount > m_BranchOnCount()

VPInstruction_match< VPInstruction::BuildVector > m_BuildVector()

BuildVector is matches only its opcode, w/o matching its operands as the number of operands is not fi...

VPInstruction_match< VPInstruction::BranchOnCond > m_BranchOnCond()

bool isSingleScalar(const VPValue *VPV)

Returns true if VPV is a single scalar, either because it produces the same value for all lanes or on...

VPBasicBlock * getFirstLoopHeader(VPlan &Plan, VPDominatorTree &VPDT)

Returns the header block of the first, top-level loop, or null if none exist.

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.

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

zip iterator for two or more iteratable types.

decltype(auto) dyn_cast(const From &Val)

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

LLVM_ABI cl::opt< bool > EnableFSDiscriminator

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.

LLVM_ABI std::optional< MDNode * > makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef< StringRef > FollowupAttrs, const char *InheritOptionsAttrsPrefix="", bool AlwaysNew=false)

Create a new loop identifier for a loop created from a loop transformation.

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

auto cast_or_null(const Y &Val)

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.

auto dyn_cast_or_null(const Y &Val)

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.

SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)

Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...

Type * toVectorizedTy(Type *Ty, ElementCount EC)

A helper for converting to vectorized types.

bool canConstantBeExtended(const APInt *C, Type *NarrowType, TTI::PartialReductionExtendKind ExtKind)

Check if a constant CI can be safely treated as having been extended from a narrower type with the gi...

Definition VPlan.cpp:1718

class LLVM_GSL_OWNER SmallVector

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

cl::opt< unsigned > ForceTargetInstructionCost

bool isa(const From &Val)

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

RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)

RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)

FunctionAddr VTableAddr Next

DWARFExpression::Operation Op

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

LLVM_ABI bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, std::optional< unsigned > EstimatedLoopInvocationWeight=std::nullopt)

Set llvm.loop.estimated_trip_count with the value EstimatedTripCount in the loop metadata of L.

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

decltype(auto) cast(const From &Val)

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

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

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

Returns true if Element is found in Range.

ArrayRef< Type * > getContainedTypes(Type *const &Ty)

Returns the types contained in Ty.

auto seq(T Begin, T End)

Iterate over an integral type from Begin up to - but not including - End.

LLVM_ABI void DeleteDeadBlocks(ArrayRef< BasicBlock * > BBs, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)

Delete the specified blocks from BB.

std::unique_ptr< VPlan > VPlanPtr

Parameters that control the generic loop unrolling transformation.

bool UnrollVectorizedLoop

Don't disable runtime unroll for the loops which were vectorized.

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.

Definition VPlan.cpp:1729

InstructionCost getScalarizationOverhead(Type *ResultTy, ArrayRef< const VPValue * > Operands, ElementCount VF, bool AlwaysIncludeReplicatingR=false)

Estimate the overhead of scalarizing a recipe with result type ResultTy and Operands with VF.

Definition VPlan.cpp:1736

TargetTransformInfo::TargetCostKind CostKind

const TargetTransformInfo & TTI

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

LoopInfo * LI

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

VPTypeAnalysis TypeAnalysis

VPlan-based type analysis.

struct llvm::VPTransformState::DataState Data

struct llvm::VPTransformState::CFGState CFG

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

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

Definition VPlan.cpp:263

VPTransformState(const TargetTransformInfo *TTI, ElementCount VF, LoopInfo *LI, DominatorTree *DT, AssumptionCache *AC, IRBuilderBase &Builder, VPlan *Plan, Loop *CurrentParentLoop, Type *CanonicalIVTy)

Definition VPlan.cpp:223

std::optional< VPLane > Lane

Hold the index to generate specific scalar instructions.

IRBuilderBase & Builder

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

bool hasScalarValue(const VPValue *Def, VPLane Lane)

const TargetTransformInfo * TTI

Target Transform Info.

VPlan * Plan

Pointer to the VPlan code is generated for.

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

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

bool hasVectorValue(const VPValue *Def)

VPDominatorTree VPDT

VPlan-based dominator tree.

ElementCount VF

The chosen Vectorization Factor of the loop being vectorized.

Value * packScalarIntoVectorizedValue(const VPValue *Def, Value *WideValue, const VPLane &Lane)

Insert the scalar value of Def at Lane into Lane of WideValue and return the resulting value.

Definition VPlan.cpp:346

AssumptionCache * AC

Hold a pointer to AssumptionCache to register new assumptions after replicating assume calls.

void setDebugLocFrom(DebugLoc DL)

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

Definition VPlan.cpp:324

Loop * CurrentParentLoop

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

static LLVM_ABI_FOR_TEST void optimize(VPlan &Plan)

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