VPlanConstruction.cpp Source File (original) (raw)

28#define DEBUG_TYPE "vplan"

30using namespace llvm;

33namespace {

35class PlainCFGBuilder {

37 Loop *TheLoop;

46 std::unique_ptr Plan;

64 void fixHeaderPhis();

66#ifndef NDEBUG

67 bool isExternalDef(Value *Val);

68#endif

72public:

74 : TheLoop(Lp), LI(LI), LVer(LVer), Plan(std::make_unique(Lp)) {}

77 std::unique_ptr buildPlainCFG();

78};

79}

87 VPBBPreds.push_back(getOrCreateVPBB(Pred));

89}

92 return L && BB == L->getHeader();

93}

96void PlainCFGBuilder::fixHeaderPhis() {

97 for (auto *Phi : PhisToFix) {

98 assert(IRDef2VPValue.count(Phi) && "Missing VPInstruction for PHINode.");

99 VPValue *VPVal = IRDef2VPValue[Phi];

102 assert(PhiR->getNumOperands() == 0 && "Expected VPPhi with no operands.");

104 "Expected Phi in header block.");

105 assert(Phi->getNumOperands() == 2 &&

106 "header phi must have exactly 2 operands");

108 PhiR->addOperand(

109 getOrCreateVPOperand(Phi->getIncomingValueForBlock(Pred)));

110 }

111}

112

113

114

115VPBasicBlock *PlainCFGBuilder::getOrCreateVPBB(BasicBlock *BB) {

116 if (auto *VPBB = BB2VPBB.lookup(BB)) {

117

118 return VPBB;

119 }

120

121

123 LLVM_DEBUG(dbgs() << "Creating VPBasicBlock for " << Name << "\n");

124 VPBasicBlock *VPBB = Plan->createVPBasicBlock(Name);

125 BB2VPBB[BB] = VPBB;

126 return VPBB;

127}

128

129#ifndef NDEBUG

130

131

132

133

134

135bool PlainCFGBuilder::isExternalDef(Value *Val) {

136

137

139 if (!Inst)

140 return true;

141

142

143 return !TheLoop->contains(Inst);

144}

145#endif

146

147

148

149

150

151VPValue *PlainCFGBuilder::getOrCreateVPOperand(Value *IRVal) {

152 auto VPValIt = IRDef2VPValue.find(IRVal);

153 if (VPValIt != IRDef2VPValue.end())

154

155

156 return VPValIt->second;

157

158

159

160

161

162

163

164

165 assert(isExternalDef(IRVal) && "Expected external definition as operand.");

166

167

168

169 VPValue *NewVPVal = Plan->getOrAddLiveIn(IRVal);

170 IRDef2VPValue[IRVal] = NewVPVal;

171 return NewVPVal;

172}

173

174

175

176

177void PlainCFGBuilder::createVPInstructionsForVPBB(VPBasicBlock *VPBB,

178 BasicBlock *BB) {

180

183

184

185

187 "Instruction shouldn't have been visited.");

188

190

191

192 if (Br->isConditional()) {

193 VPValue *Cond = getOrCreateVPOperand(Br->getCondition());

195 VPIRMetadata(*Inst), Inst->getDebugLoc());

196 }

197

198

199 continue;

200 }

201

203

204 if (SI->getNumCases() == 0)

205 continue;

207 for (auto Case : SI->cases())

208 Ops.push_back(getOrCreateVPOperand(Case.getCaseValue()));

209 VPIRBuilder.createNaryOp(Instruction::Switch, Ops, Inst, {},

210 VPIRMetadata(*Inst), Inst->getDebugLoc());

211 continue;

212 }

213

214 VPSingleDefRecipe *NewR;

216

217

218

219 NewR = VPIRBuilder.createScalarPhi({}, Phi->getDebugLoc(), "vec.phi");

222

223

224 PhisToFix.push_back(Phi);

225 } else {

226

227

228 DenseMap<const VPBasicBlock *, VPValue *> VPPredToIncomingValue;

229 for (unsigned I = 0; I != Phi->getNumOperands(); ++I) {

230 VPPredToIncomingValue[BB2VPBB[Phi->getIncomingBlock(I)]] =

231 getOrCreateVPOperand(Phi->getIncomingValue(I));

232 }

235 VPPredToIncomingValue.lookup(Pred->getExitingBasicBlock()));

236 }

237 } else {

238

239

240 VPIRMetadata MD(*Inst);

242 const auto &[AliasScopeMD, NoAliasMD] =

244 if (AliasScopeMD)

245 MD.setMetadata(LLVMContext::MD_alias_scope, AliasScopeMD);

246 if (NoAliasMD)

247 MD.setMetadata(LLVMContext::MD_noalias, NoAliasMD);

248 }

249

250

251

254 VPOperands.push_back(getOrCreateVPOperand(Op));

255

257 NewR = VPIRBuilder.createScalarCast(CI->getOpcode(), VPOperands[0],

258 CI->getType(), CI->getDebugLoc(),

259 VPIRFlags(*CI), MD);

261 } else {

262

263

264 NewR =

266 VPIRFlags(*Inst), MD, Inst->getDebugLoc());

267 }

268 }

269

270 IRDef2VPValue[Inst] = NewR;

271 }

272}

273

274

275std::unique_ptr PlainCFGBuilder::buildPlainCFG() {

277 BB2VPBB[Entry->getIRBasicBlock()] = Entry;

278 for (VPIRBasicBlock *ExitVPBB : Plan->getExitBlocks())

279 BB2VPBB[ExitVPBB->getIRBasicBlock()] = ExitVPBB;

280

281

282

283

284

285

286

287

288

289

292 "Unexpected loop preheader");

293 for (auto &I : *ThePreheaderBB) {

294 if (I.getType()->isVoidTy())

295 continue;

296 IRDef2VPValue[&I] = Plan->getOrAddLiveIn(&I);

297 }

298

299 LoopBlocksRPO RPO(TheLoop);

300 RPO.perform(LI);

301

302 for (BasicBlock *BB : RPO) {

303

304 VPBasicBlock *VPBB = getOrCreateVPBB(BB);

305

306 setVPBBPredsFromBB(VPBB, BB);

307

308

309 createVPInstructionsForVPBB(VPBB, BB);

310

311

312

313

316 getOrCreateVPBB(SI->getDefaultDest())};

317 for (auto Case : SI->cases())

318 Succs.push_back(getOrCreateVPBB(Case.getCaseSuccessor()));

320 continue;

321 }

323 unsigned NumSuccs = succ_size(BB);

324 if (NumSuccs == 1) {

326 continue;

327 }

328 assert(BI->isConditional() && NumSuccs == 2 && BI->isConditional() &&

329 "block must have conditional branch with 2 successors");

330

331 BasicBlock *IRSucc0 = BI->getSuccessor(0);

332 BasicBlock *IRSucc1 = BI->getSuccessor(1);

333 VPBasicBlock *Successor0 = getOrCreateVPBB(IRSucc0);

334 VPBasicBlock *Successor1 = getOrCreateVPBB(IRSucc1);

336 }

337

338 for (auto *EB : Plan->getExitBlocks())

339 setVPBBPredsFromBB(EB, EB->getIRBasicBlock());

340

341

342

343

344 fixHeaderPhis();

345

346 Plan->getEntry()->setOneSuccessor(getOrCreateVPBB(TheLoop->getHeader()));

347 Plan->getEntry()->setPlan(&*Plan);

348

349

350

351

352

353

354 for (auto *EB : Plan->getExitBlocks()) {

355 for (VPRecipeBase &R : EB->phis()) {

357 PHINode &Phi = PhiR->getIRPhi();

358 assert(PhiR->getNumOperands() == 0 &&

359 "no phi operands should be added yet");

360 for (BasicBlock *Pred : predecessors(EB->getIRBasicBlock()))

361 PhiR->addOperand(

362 getOrCreateVPOperand(Phi.getIncomingValueForBlock(Pred)));

363 }

364 }

365

366 LLVM_DEBUG(Plan->setName("Plain CFG\n"); dbgs() << *Plan);

367 return std::move(Plan);

368}

369

370

371

372

373

374

375

376

380 if (Preds.size() != 2)

381 return false;

382

383 auto *PreheaderVPBB = Preds[0];

384 auto *LatchVPBB = Preds[1];

385 if (!VPDT.dominates(PreheaderVPBB, HeaderVPB) ||

386 !VPDT.dominates(HeaderVPB, LatchVPBB)) {

387 std::swap(PreheaderVPBB, LatchVPBB);

388

389 if (!VPDT.dominates(PreheaderVPBB, HeaderVPB) ||

390 !VPDT.dominates(HeaderVPB, LatchVPBB))

391 return false;

392

393

394

397 R.swapOperands();

398 }

399

400

401

402

403

404

405

406 if (LatchVPBB->getSingleSuccessor() ||

407 LatchVPBB->getSuccessors()[0] != HeaderVPB)

408 return true;

409

410 assert(LatchVPBB->getNumSuccessors() == 2 && "Must have 2 successors");

414 "terminator must be a BranchOnCond");

416 Not->insertBefore(Term);

417 Term->setOperand(0, Not);

418 LatchVPBB->swapSuccessors();

419

420 return true;

421}

422

423

427

431 assert(LatchExitVPB && "Latch expected to be left with a single successor");

432

433

434

435

436

441 R->setEntry(HeaderVPB);

442 R->setExiting(LatchVPBB);

443

444

447}

448

449

450

454 Value *StartIdx = ConstantInt::get(IdxTy, 0);

456

457

459 HeaderVPBB->insert(CanonicalIVPHI, HeaderVPBB->begin());

460

461

462

467 }

468

470

471

472

473 auto *CanonicalIVIncrement = Builder.createOverflowingOp(

474 Instruction::Add, {CanonicalIVPHI, &Plan.getVFxUF()}, {true, false}, DL,

475 "index.next");

476 CanonicalIVPHI->addOperand(CanonicalIVIncrement);

477

478

481 LatchDL);

482}

483

484

485

489 if (EB->getSinglePredecessor() != MiddleVPBB)

490 continue;

491

494 for (unsigned Idx = 0; Idx != ExitIRI->getNumIncoming(); ++Idx) {

495 VPRecipeBase *Inc = ExitIRI->getIncomingValue(Idx)->getDefiningRecipe();

496 if (!Inc)

497 continue;

498 assert(ExitIRI->getNumOperands() == 1 &&

499 ExitIRI->getParent()->getSinglePredecessor() == MiddleVPBB &&

500 "exit values from early exits must be fixed when branch to "

501 "early-exit is added");

502 ExitIRI->extractLastLaneOfLastPartOfFirstOperand(B);

503 }

504 }

505 }

506}

507

511

514 auto *LatchVPBB = cast(HeaderVPBB->getPredecessors()[1]);

515

518

520

521

522

523

524 if (LatchVPBB->getNumSuccessors() == 2) {

527 } else {

529 LatchVPBB->swapSuccessors();

530 }

531

533

534

535

536

539 "Invalid backedge-taken count");

542 InductionTy, TheLoop);

544

547

548

549

551

552

553

556

558

559 VPBuilder ScalarPHBuilder(ScalarPH);

560 for (const auto &[PhiR, ScalarPhiR] : zip_equal(

564 {VectorPhiR, VectorPhiR->getOperand(0)}, VectorPhiR->getDebugLoc());

566 }

567}

568

569std::unique_ptr

573 PlainCFGBuilder Builder(TheLoop, &LI, LVer);

574 std::unique_ptr VPlan0 = Builder.buildPlainCFG();

576 return VPlan0;

577}

578

580 bool HasUncountableEarlyExit) {

583 auto *LatchVPBB = cast(MiddleVPBB->getSinglePredecessor());

585

586

587

588

589

590

591 [[maybe_unused]] bool HandledUncountableEarlyExit = false;

594 if (Pred == MiddleVPBB)

595 continue;

596 if (HasUncountableEarlyExit) {

597 assert(!HandledUncountableEarlyExit &&

598 "can handle exactly one uncountable early exit");

601 HandledUncountableEarlyExit = true;

602 } else {

605 }

608 }

609 }

610

611 assert((!HasUncountableEarlyExit || HandledUncountableEarlyExit) &&

612 "missed an uncountable exit that must be handled");

613}

614

616 bool RequiresScalarEpilogueCheck,

617 bool TailFolded) {

620

621

622

623 if (MiddleVPBB->getNumSuccessors() == 1) {

625 "must have ScalarPH as single successor");

626 return;

627 }

628

629 assert(MiddleVPBB->getNumSuccessors() == 2 && "must have 2 successors");

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646 auto *LatchVPBB = cast(MiddleVPBB->getSinglePredecessor());

647 DebugLoc LatchDL = LatchVPBB->getTerminator()->getDebugLoc();

650 if (!RequiresScalarEpilogueCheck)

652 else if (TailFolded)

654 else

658}

659

665

667 TopRegion->setName("vector loop");

669}

670

671

672

674

677 bool AddBranchWeights) {

686

687

688

692 assert(cast(&R)->getNumIncoming() == NumPredecessors - 1 &&

693 "must have incoming values for all operands");

694 R.addOperand(R.getOperand(NumPredecessors - 2));

695 }

696

698 auto *Term =

703 if (AddBranchWeights) {

705 MDNode *BranchWeights =

707 Term->setMetadata(LLVMContext::MD_prof, BranchWeights);

708 }

709}

710

713 ElementCount MinProfitableTripCount, bool RequiresScalarEpilogue,

714 bool TailFolded, bool CheckNeededWithTailFolding, Loop *OrigLoop,

716

717

718

719

720

723

726 Type *TripCountTy = TripCount->getType();

727 auto GetMinTripCount = [&]() -> const SCEV * {

728

729 const SCEV *VFxUF =

733

734 return VFxUF;

735 }

736 const SCEV *MinProfitableTripCountSCEV =

738 return SE.getUMaxExpr(MinProfitableTripCountSCEV, VFxUF);

739 };

740

744 const SCEV *Step = GetMinTripCount();

745 if (TailFolded) {

746 if (CheckNeededWithTailFolding) {

747

748

749

750

751

752 VPValue *MaxUIntTripCount =

754 VPValue *DistanceToMax = Builder.createNaryOp(

755 Instruction::Sub, {MaxUIntTripCount, TripCountVPV},

757

758

759

760

761 TripCountCheck = Builder.createICmp(ICmpInst::ICMP_ULT, DistanceToMax,

762 Builder.createExpandSCEV(Step), DL);

763 } else {

764

765

766 }

767 } else {

768

769

771

773

774

775 TripCountCheck = Plan.getTrue();

777 TripCount, Step)) {

778

779

780 VPValue *MinTripCountVPV = Builder.createExpandSCEV(Step);

781 TripCountCheck = Builder.createICmp(

782 CmpPred, TripCountVPV, MinTripCountVPV, DL, "min.iters.check");

783 }

784 }

791 Term->setMetadata(LLVMContext::MD_prof, BranchWeights);

792 }

793}

794

797 bool RequiresScalarEpilogue, ElementCount EpilogueVF, unsigned EpilogueUF,

798 unsigned MainLoopStep, unsigned EpilogueLoopStep, ScalarEvolution &SE) {

799

805 Instruction::Sub, {TC, Plan.getOrAddLiveIn(VectorTripCount)},

807

808

809

811 auto *CheckMinIters = Builder.createICmp(

815

816

817

818

819

820

821

822 unsigned EstimatedSkipCount = std::min(MainLoopStep, EpilogueLoopStep);

823 const uint32_t Weights[] = {EstimatedSkipCount,

824 MainLoopStep - EstimatedSkipCount};

826 MDNode *BranchWeights =

828 Branch->setMetadata(LLVMContext::MD_prof, BranchWeights);

829}

830

831

832

833template

838

839

840

844

847 auto *MinMaxR =

849 if (!MinMaxR)

850 return nullptr;

851

852

853

857 return nullptr;

858

859 if (MinMaxR->getOperand(0) == RedPhiR)

860 return MinMaxR->getOperand(1);

861

862 assert(MinMaxR->getOperand(1) == RedPhiR &&

863 "Reduction phi operand expected");

864 return MinMaxR->getOperand(0);

865 };

866

869 MinMaxNumReductionsToHandle;

870 bool HasUnsupportedPhi = false;

873 continue;

875 if (!Cur) {

876

877 HasUnsupportedPhi = true;

878 continue;

879 }

881 Cur->getRecurrenceKind())) {

882 HasUnsupportedPhi = true;

883 continue;

884 }

885

886 VPValue *MinMaxOp = GetMinMaxCompareValue(Cur);

887 if (!MinMaxOp)

888 return false;

889

890 MinMaxNumReductionsToHandle.emplace_back(Cur, MinMaxOp);

891 }

892

893 if (MinMaxNumReductionsToHandle.empty())

894 return true;

895

896

897

898

900 return false;

901

902

903

904

905

906

907

911 for (auto &R : *VPBB) {

913 return false;

914 }

915 }

916

919 VPValue *AllNaNLanes = nullptr;

921 for (const auto &[_, MinMaxOp] : MinMaxNumReductionsToHandle) {

924 AllNaNLanes = AllNaNLanes ? LatchBuilder.createOr(AllNaNLanes, RedNaNLanes)

925 : RedNaNLanes;

926 }

927

931 VPBuilder MiddleBuilder(MiddleVPBB, MiddleVPBB->begin());

932 for (const auto &[RedPhiR, _] : MinMaxNumReductionsToHandle) {

934 RedPhiR->getRecurrenceKind()) &&

935 "unsupported reduction");

936

937

938

939 auto *RdxResult =

941

942 auto *NewSel = MiddleBuilder.createSelect(AnyNaNLane, RedPhiR,

943 RdxResult->getOperand(1));

945 assert(!RdxResults.contains(RdxResult) && "RdxResult already used");

946 RdxResults.insert(RdxResult);

947 }

948

949 auto *LatchExitingBranch = LatchVPBB->getTerminator();

951 "Unexpected terminator");

952 auto *IsLatchExitTaken = LatchBuilder.createICmp(

954 LatchExitingBranch->getOperand(1));

955 auto *AnyExitTaken = LatchBuilder.createNaryOp(

956 Instruction::Or, {AnyNaNLane, IsLatchExitTaken});

959

960

961

962

965 VPValue *VecV = ResumeR->getOperand(0);

966 if (RdxResults.contains(VecV))

967 continue;

969 if (DerivedIV->getNumUsers() == 1 &&

971 auto *NewSel =

975 DerivedIV->setOperand(1, NewSel);

976 continue;

977 }

978 }

979

980

982 LLVM_DEBUG(dbgs() << "Found resume phi we cannot update for VPlan with "

983 "FMaxNum/FMinNum reduction.\n");

984 return false;

985 }

989 }

990

993 VPValue *MiddleCond = MiddleTerm->getOperand(0);

995 MiddleBuilder.createAnd(MiddleCond, MiddleBuilder.createNot(AnyNaNLane));

997 return true;

998}

999

1004

1005 if (!MinMaxPhiR || !MinMaxPhiR->hasUsesOutsideReductionChain())

1006 continue;

1007

1008

1009

1010

1011

1012

1013

1014 RecurKind RdxKind = MinMaxPhiR->getRecurrenceKind();

1017 "only min/max recurrences support users outside the reduction chain");

1018

1019 auto *MinMaxOp =

1021 if (!MinMaxOp)

1022 return false;

1023

1024

1025

1028 return false;

1029

1030

1031

1032 assert(MinMaxOp->getNumUsers() == 2 &&

1033 "MinMaxOp must have exactly 2 users");

1034 VPValue *MinMaxOpValue = MinMaxOp->getOperand(0);

1035 if (MinMaxOpValue == MinMaxPhiR)

1036 MinMaxOpValue = MinMaxOp->getOperand(1);

1037

1043 if (!Cmp || Cmp->getNumUsers() != 1 ||

1044 (CmpOpA != MinMaxOpValue && CmpOpB != MinMaxOpValue))

1045 return false;

1046

1047 if (MinMaxOpValue != CmpOpB)

1049

1050

1051

1052

1053

1054 if (MinMaxPhiR->getNumUsers() != 3)

1055 return false;

1056

1060 "one user must be MinMaxOp");

1061 assert(MinMaxResult && "MinMaxResult must be a user of MinMaxPhiR");

1063 "MinMaxResult must be a user of MinMaxOp (and of MinMaxPhiR");

1064

1065

1071 return false;

1072

1076 }

1077

1080 FindIVPhiR->getRecurrenceKind()))

1081 return false;

1082

1083

1086 return false;

1087

1089 switch (RdxKind) {

1098 default:

1100 }

1101 }();

1102

1103

1104

1105 if (Pred != RdxPredicate)

1106 return false;

1107

1108 assert(!FindIVPhiR->isInLoop() && !FindIVPhiR->isOrdered() &&

1109 "cannot handle inloop/ordered reductions yet");

1110

1111

1112

1113

1114

1115

1116

1117

1118

1119

1120

1121

1122

1123

1124

1125

1126

1127

1128

1129

1130

1131

1135 "both results must be computed in the same block");

1138

1141 auto *FinalMinMaxCmp =

1145 auto *FinalIVSelect =

1146 B.createSelect(FinalMinMaxCmp, LastIVExiting, Sentinel);

1147 FindIVResult->setOperand(3, FinalIVSelect);

1148 }

1149 return true;

1150}

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

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

static std::pair< Value *, APInt > getMask(Value *WideMask, unsigned Factor, ElementCount LeafValueEC)

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

This file provides a LoopVectorizationPlanner class.

static constexpr uint32_t MinItersBypassWeights[]

static DebugLoc getDebugLoc(MachineBasicBlock::instr_iterator FirstMI, MachineBasicBlock::instr_iterator LastMI)

Return the first DebugLoc that has line number information, given a range of instructions.

const SmallVectorImpl< MachineOperand > & Cond

static void createLoopRegion(VPlan &Plan, VPBlockBase *HeaderVPB)

Create a new VPRegionBlock for the loop starting at HeaderVPB.

Definition VPlanConstruction.cpp:424

static bool isHeaderBB(BasicBlock *BB, Loop *L)

Definition VPlanConstruction.cpp:91

static VPRecipeBase * findUserOf(VPValue *V, const MatchT &P)

If V is used by a recipe matching pattern P, return it.

Definition VPlanConstruction.cpp:834

static void addInitialSkeleton(VPlan &Plan, Type *InductionTy, DebugLoc IVDL, PredicatedScalarEvolution &PSE, Loop *TheLoop)

Definition VPlanConstruction.cpp:508

static void addCanonicalIVRecipes(VPlan &Plan, VPBasicBlock *HeaderVPBB, VPBasicBlock *LatchVPBB, Type *IdxTy, DebugLoc DL)

Definition VPlanConstruction.cpp:451

static bool canonicalHeaderAndLatch(VPBlockBase *HeaderVPB, const VPDominatorTree &VPDT)

Checks if HeaderVPB is a loop header block in the plain CFG; that is, it has exactly 2 predecessors (...

Definition VPlanConstruction.cpp:377

static constexpr uint32_t CheckBypassWeights[]

Definition VPlanConstruction.cpp:673

static void createExtractsForLiveOuts(VPlan &Plan, VPBasicBlock *MiddleVPBB)

Creates extracts for values in Plan defined in a loop region and used outside a loop region.

Definition VPlanConstruction.cpp:486

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

static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)

Returns the opcode of Values or ~0 if they do not all agree.

This file provides utility VPlan to VPlan transformations.

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

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

size_t size() const

size - Get the array size.

LLVM Basic Block Representation.

LLVM_ABI iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const

Return a const iterator range over the instructions in the block, skipping any debug instructions.

LLVM_ABI const BasicBlock * getSingleSuccessor() const

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

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

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

@ ICMP_SLE

signed less or equal

@ ICMP_UGE

unsigned greater or equal

@ ICMP_ULT

unsigned less than

@ ICMP_SGE

signed greater or equal

@ ICMP_ULE

unsigned less or equal

@ FCMP_UNO

1 0 0 0 True if unordered: isnan(X) | isnan(Y)

Predicate getSwappedPredicate() const

For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.

Predicate getInversePredicate() const

For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...

An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...

static DebugLoc getUnknown()

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

iterator find(const_arg_type_t< KeyT > Val)

size_type count(const_arg_type_t< KeyT > Val) const

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

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

dominates - Returns true iff A dominates B.

LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY

Return the number of successors that this instruction has.

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

unsigned getOpcode() const

Returns a member of one of the enums like Instruction::Add.

bool contains(const LoopT *L) const

Return true if the specified loop is contained within in this loop.

BlockT * getHeader() const

BlockT * getLoopPreheader() const

If there is a preheader for this loop, return it.

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

This class emits a version of the loop where run-time checks ensure that may-alias pointers can't ove...

std::pair< MDNode *, MDNode * > getNoAliasMetadataFor(const Instruction *OrigInst) const

Returns a pair containing the alias_scope and noalias metadata nodes for OrigInst,...

Represents a single loop in the control flow graph.

LLVM_ABI MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)

Return metadata containing two branch weights.

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.

LLVM_ABI const SCEV * getSymbolicMaxBackedgeTakenCount()

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

static bool isFPMinMaxNumRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is a floating-point minnum/maxnum kind.

static bool isFindLastIVRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...

static bool isIntMinMaxRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is an integer min/max kind.

This class represents an analyzed expression in the program.

LLVM_ABI Type * getType() const

Return the LLVM type of this SCEV expression.

The main scalar evolution driver.

LLVM_ABI const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)

LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)

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

LLVM_ABI const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)

LLVM_ABI const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)

Try to apply information from loop guards for L to Expr.

LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)

Test if the given expression is known to satisfy the condition described by Pred, LHS,...

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

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

bool contains(ConstPtrType Ptr) const

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

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

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

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

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

iterator begin()

Recipe iterator methods.

iterator_range< iterator > phis()

Returns an iterator range over the PHI-like recipes in the block.

iterator getFirstNonPhi()

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

VPRecipeBase * getTerminator()

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

const VPRecipeBase & back() const

void insert(VPRecipeBase *Recipe, iterator InsertPt)

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.

const VPBasicBlock * getExitingBasicBlock() const

void setName(const Twine &newName)

void swapSuccessors()

Swap successors of the block. The block must have exactly 2 successors.

size_t getNumPredecessors() const

void setPredecessors(ArrayRef< VPBlockBase * > NewPreds)

Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.

const VPBlocksTy & getPredecessors() const

void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse)

Set two given VPBlockBases IfTrue and IfFalse to be the two successors of this VPBlockBase.

VPBlockBase * getSinglePredecessor() const

void swapPredecessors()

Swap predecessors of the block.

const VPBasicBlock * getEntryBasicBlock() const

void setOneSuccessor(VPBlockBase *Successor)

Set a given VPBlockBase Successor as the single successor of this VPBlockBase.

void setParent(VPRegionBlock *P)

VPBlockBase * getSingleSuccessor() const

const VPBlocksTy & getSuccessors() const

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

Insert disconnected VPBlockBase NewBlock after BlockPtr.

static void insertOnEdge(VPBlockBase *From, VPBlockBase *To, VPBlockBase *BlockPtr)

Inserts BlockPtr on the edge between From and To.

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.

VPInstruction * createOr(VPValue *LHS, VPValue *RHS, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")

VPInstruction * createScalarCast(Instruction::CastOps Opcode, VPValue *Op, Type *ResultTy, DebugLoc DL, const VPIRFlags &Flags={}, const VPIRMetadata &Metadata={})

VPInstruction * createNot(VPValue *Operand, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")

VPInstruction * createSelect(VPValue *Cond, VPValue *TrueVal, VPValue *FalseVal, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="", std::optional< FastMathFlags > FMFs=std::nullopt)

VPBasicBlock::iterator getInsertPoint() const

VPInstruction * createFCmp(CmpInst::Predicate Pred, VPValue *A, VPValue *B, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")

Create a new FCmp VPInstruction with predicate Pred and operands A and B.

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

VPInstruction * createICmp(CmpInst::Predicate Pred, VPValue *A, VPValue *B, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")

Create a new ICmp VPInstruction with predicate Pred and operands A and B.

VPInstruction * createAnd(VPValue *LHS, VPValue *RHS, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")

void setInsertPoint(VPBasicBlock *TheBB)

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

VPInstruction * createNaryOp(unsigned Opcode, ArrayRef< VPValue * > Operands, Instruction *Inst=nullptr, const VPIRFlags &Flags={}, const VPIRMetadata &MD={}, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")

Create an N-ary operation with Opcode, Operands and set Inst as its underlying Instruction.

Canonical scalar induction phi of the vector loop.

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

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

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

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

VPBasicBlock * getParent()

DebugLoc getDebugLoc() const

Returns the debug location of the recipe.

void moveBefore(VPBasicBlock &BB, iplist< VPRecipeBase >::iterator I)

Unlink this recipe and insert into BB before I.

iplist< VPRecipeBase >::iterator eraseFromParent()

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

void moveAfter(VPRecipeBase *MovePos)

Unlink this recipe from its current VPBasicBlock and insert it into the VPBasicBlock that MovePos liv...

A recipe for handling reduction phis.

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

VPCanonicalIVPHIRecipe * getCanonicalIV()

Returns the canonical induction recipe of the region.

void setOperand(unsigned I, VPValue *New)

VPValue * getOperand(unsigned N) const

void addOperand(VPValue *Operand)

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

void setUnderlyingValue(Value *Val)

unsigned getNumUsers() const

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

LLVMContext & getContext() const

VPBasicBlock * getEntry()

VPValue & getVectorTripCount()

The vector trip count.

VPValue & getVFxUF()

Returns VF * UF of the vector loop region.

VPValue * getTripCount() const

The trip count of the original loop.

VPValue * getTrue()

Return a VPValue wrapping i1 true.

ArrayRef< VPIRBasicBlock * > getExitBlocks() const

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

VPValue * getConstantInt(Type *Ty, uint64_t Val, bool IsSigned=false)

Return a VPValue wrapping a ConstantInt with the given type and value.

LLVM_ABI_FOR_TEST VPRegionBlock * getVectorLoopRegion()

Returns the VPRegionBlock of the vector loop.

void setTripCount(VPValue *NewTripCount)

Set the trip count assuming it is currently null; if it is not - use resetTripCount().

VPBasicBlock * getMiddleBlock()

Returns the 'middle' block of the plan, that is the block that selects whether to execute the scalar ...

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

VPValue * getFalse()

Return a VPValue wrapping i1 false.

VPValue * getOrAddLiveIn(Value *V)

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

VPRegionBlock * createLoopRegion(const std::string &Name="", VPBlockBase *Entry=nullptr, VPBlockBase *Exiting=nullptr)

Create a new loop region with Name and entry and exiting blocks set to Entry and Exiting respectively...

VPBasicBlock * getScalarPreheader() const

Return the VPBasicBlock for the preheader of the scalar loop.

VPIRBasicBlock * getScalarHeader() const

Return the VPIRBasicBlock wrapping the header of the scalar loop.

VPBasicBlock * getVectorPreheader()

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

bool hasScalarTail() const

Returns true if the scalar tail may execute after the vector loop.

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

Returns the minimum value this quantity can represent.

self_iterator getIterator()

#define llvm_unreachable(msg)

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

@ BasicBlock

Various leaf nodes.

match_combine_or< CastInst_match< OpTy, TruncInst >, OpTy > m_TruncOrSelf(const OpTy &Op)

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

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

IntrinsicID_match m_Intrinsic()

Match intrinsic calls like this: m_IntrinsicIntrinsic::fabs(m_Value(X))

ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)

Matches SelectInst.

class_match< CmpInst > m_Cmp()

Matches any compare instruction and ignore it.

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

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

VPInstruction_match< VPInstruction::BranchOnCount > m_BranchOnCount()

class_match< VPValue > m_VPValue()

Match an arbitrary VPValue and ignore it.

bind_ty< VPInstruction > m_VPInstruction(VPInstruction *&V)

Match a VPInstruction, capturing if we match.

VPInstruction_match< VPInstruction::BranchOnCond > m_BranchOnCond()

NodeAddr< PhiNode * > Phi

friend class Instruction

Iterator for Instructions in a `BasicBlock.

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

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

const SCEV * getSCEVExprForVPValue(const VPValue *V, ScalarEvolution &SE, const Loop *L=nullptr)

Return the SCEV expression for V.

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.

FunctionAddr VTableAddr Value

LLVM_ABI Intrinsic::ID getMinMaxReductionIntrinsicOp(Intrinsic::ID RdxID)

Returns the min/max intrinsic used when expanding a min/max reduction.

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

zip iterator that assumes that all iteratees have the same length.

decltype(auto) dyn_cast(const From &Val)

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

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)

LLVM_ABI raw_ostream & dbgs()

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

FunctionAddr VTableAddr Count

auto succ_size(const MachineBasicBlock *BB)

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

class LLVM_GSL_OWNER SmallVector

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

iterator_range< po_iterator< VPBlockShallowTraversalWrapper< VPBlockBase * > > > vp_post_order_shallow(VPBlockBase *G)

Returns an iterator range to traverse the graph starting at G in post order.

bool isa(const From &Val)

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

RecurKind

These are the kinds of recurrences that we support.

@ UMin

Unsigned integer min implemented in terms of select(cmp()).

@ SMax

Signed integer max implemented in terms of select(cmp()).

@ SMin

Signed integer min implemented in terms of select(cmp()).

@ UMax

Unsigned integer max implemented in terms of select(cmp()).

DWARFExpression::Operation Op

ArrayRef(const T &OneElt) -> ArrayRef< T >

decltype(auto) cast(const From &Val)

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

auto find_if(R &&Range, UnaryPredicate P)

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

auto predecessors(const MachineBasicBlock *BB)

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

Returns true if Element is found in Range.

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

static bool handleMultiUseReductions(VPlan &Plan)

Try to legalize reductions with multiple in-loop uses.

Definition VPlanConstruction.cpp:1000

static LLVM_ABI_FOR_TEST std::unique_ptr< VPlan > buildVPlan0(Loop *TheLoop, LoopInfo &LI, Type *InductionTy, DebugLoc IVDL, PredicatedScalarEvolution &PSE, LoopVersioning *LVer=nullptr)

Create a base VPlan0, serving as the common starting point for all later candidates.

Definition VPlanConstruction.cpp:570

static LLVM_ABI_FOR_TEST void handleEarlyExits(VPlan &Plan, bool HasUncountableExit)

Update Plan to account for all early exits.

Definition VPlanConstruction.cpp:579

static void addMinimumIterationCheck(VPlan &Plan, ElementCount VF, unsigned UF, ElementCount MinProfitableTripCount, bool RequiresScalarEpilogue, bool TailFolded, bool CheckNeededWithTailFolding, Loop *OrigLoop, const uint32_t *MinItersBypassWeights, DebugLoc DL, ScalarEvolution &SE)

Definition VPlanConstruction.cpp:711

static bool handleMaxMinNumReductions(VPlan &Plan)

Check if Plan contains any FMaxNum or FMinNum reductions.

Definition VPlanConstruction.cpp:845

static LLVM_ABI_FOR_TEST void createLoopRegions(VPlan &Plan)

Replace loops in Plan's flat CFG with VPRegionBlocks, turning Plan's flat CFG into a hierarchical CFG...

Definition VPlanConstruction.cpp:660

static void attachCheckBlock(VPlan &Plan, Value *Cond, BasicBlock *CheckBlock, bool AddBranchWeights)

Wrap runtime check block CheckBlock in a VPIRBB and Cond in a VPValue and connect the block to Plan,...

Definition VPlanConstruction.cpp:675

static void handleUncountableEarlyExit(VPBasicBlock *EarlyExitingVPBB, VPBasicBlock *EarlyExitVPBB, VPlan &Plan, VPBasicBlock *HeaderVPBB, VPBasicBlock *LatchVPBB)

Update Plan to account for the uncountable early exit from EarlyExitingVPBB to EarlyExitVPBB by.

static void addMinimumVectorEpilogueIterationCheck(VPlan &Plan, Value *TripCount, Value *VectorTripCount, bool RequiresScalarEpilogue, ElementCount EpilogueVF, unsigned EpilogueUF, unsigned MainLoopStep, unsigned EpilogueLoopStep, ScalarEvolution &SE)

Add a check to Plan to see if the epilogue vector loop should be executed.

Definition VPlanConstruction.cpp:795

static LLVM_ABI_FOR_TEST void addMiddleCheck(VPlan &Plan, bool RequiresScalarEpilogueCheck, bool TailFolded)

If a check is needed to guard executing the scalar epilogue loop, it will be added to the middle bloc...

Definition VPlanConstruction.cpp:615