LLVM 22.0.0git
VPlanAnalysis.cpp
Go to the documentation of this file.
1//===- VPlanAnalysis.cpp - Various Analyses working on VPlan ----*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "VPlanAnalysis.h"
10#include "VPlan.h"
11#include "VPlanCFG.h"
12#include "VPlanDominatorTree.h"
13#include "VPlanHelpers.h"
15#include "llvm/ADT/TypeSwitch.h"
18#include "llvm/IR/Instruction.h"
20
21using namespace llvm;
22
23#define DEBUG_TYPE "vplan"
24
26 if (auto LoopRegion = Plan.getVectorLoopRegion()) {
27 if (const auto *CanIV = dyn_cast<VPCanonicalIVPHIRecipe>(
28 &LoopRegion->getEntryBasicBlock()->front())) {
29 CanonicalIVTy = CanIV->getScalarType();
30 return;
31 }
32 }
33
34 // If there's no canonical IV, retrieve the type from the trip count
35 // expression.
36 auto *TC = Plan.getTripCount();
37 if (TC->isLiveIn()) {
38 CanonicalIVTy = TC->getLiveInIRValue()->getType();
39 return;
40 }
41 CanonicalIVTy = cast<VPExpandSCEVRecipe>(TC)->getSCEV()->getType();
42}
43
44Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPBlendRecipe *R) {
45 Type *ResTy = inferScalarType(R->getIncomingValue(0));
46 for (unsigned I = 1, E = R->getNumIncomingValues(); I != E; ++I) {
47 VPValue *Inc = R->getIncomingValue(I);
48 assert(inferScalarType(Inc) == ResTy &&
49 "different types inferred for different incoming values");
50 CachedTypes[Inc] = ResTy;
51 }
52 return ResTy;
53}
54
55Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPInstruction *R) {
56 // Set the result type from the first operand, check if the types for all
57 // other operands match and cache them.
58 auto SetResultTyFromOp = [this, R]() {
59 Type *ResTy = inferScalarType(R->getOperand(0));
60 for (unsigned Op = 1; Op != R->getNumOperands(); ++Op) {
61 VPValue *OtherV = R->getOperand(Op);
62 assert(inferScalarType(OtherV) == ResTy &&
63 "different types inferred for different operands");
64 CachedTypes[OtherV] = ResTy;
65 }
66 return ResTy;
67 };
68
69 unsigned Opcode = R->getOpcode();
71 return SetResultTyFromOp();
72
73 switch (Opcode) {
74 case Instruction::ExtractElement:
75 case Instruction::Freeze:
78 return inferScalarType(R->getOperand(0));
79 case Instruction::Select: {
80 Type *ResTy = inferScalarType(R->getOperand(1));
81 VPValue *OtherV = R->getOperand(2);
82 assert(inferScalarType(OtherV) == ResTy &&
83 "different types inferred for different operands");
84 CachedTypes[OtherV] = ResTy;
85 return ResTy;
86 }
87 case Instruction::ICmp:
88 case Instruction::FCmp:
90 assert(inferScalarType(R->getOperand(0)) ==
91 inferScalarType(R->getOperand(1)) &&
92 "different types inferred for different operands");
93 return IntegerType::get(Ctx, 1);
95 return inferScalarType(R->getOperand(1));
98 return inferScalarType(R->getOperand(0));
99 }
101 return Type::getIntNTy(Ctx, 32);
102 case Instruction::PHI:
103 // Infer the type of first operand only, as other operands of header phi's
104 // may lead to infinite recursion.
105 return inferScalarType(R->getOperand(0));
114 return SetResultTyFromOp();
116 return inferScalarType(R->getOperand(1));
118 return Type::getIntNTy(Ctx, 64);
122 Type *BaseTy = inferScalarType(R->getOperand(0));
123 if (auto *VecTy = dyn_cast<VectorType>(BaseTy))
124 return VecTy->getElementType();
125 return BaseTy;
126 }
128 assert(inferScalarType(R->getOperand(0))->isIntegerTy(1) &&
129 inferScalarType(R->getOperand(1))->isIntegerTy(1) &&
130 "LogicalAnd operands should be bool");
131 return IntegerType::get(Ctx, 1);
135 // Return the type based on first operand.
136 return inferScalarType(R->getOperand(0));
139 return Type::getVoidTy(Ctx);
140 default:
141 break;
142 }
143 // Type inference not implemented for opcode.
144 LLVM_DEBUG({
145 dbgs() << "LV: Found unhandled opcode for: ";
146 R->getVPSingleValue()->dump();
147 });
148 llvm_unreachable("Unhandled opcode!");
149}
150
151Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPWidenRecipe *R) {
152 unsigned Opcode = R->getOpcode();
153 if (Instruction::isBinaryOp(Opcode) || Instruction::isShift(Opcode) ||
155 Type *ResTy = inferScalarType(R->getOperand(0));
156 assert(ResTy == inferScalarType(R->getOperand(1)) &&
157 "types for both operands must match for binary op");
158 CachedTypes[R->getOperand(1)] = ResTy;
159 return ResTy;
160 }
161
162 switch (Opcode) {
163 case Instruction::ICmp:
164 case Instruction::FCmp:
165 return IntegerType::get(Ctx, 1);
166 case Instruction::FNeg:
167 case Instruction::Freeze:
168 return inferScalarType(R->getOperand(0));
169 case Instruction::ExtractValue: {
170 assert(R->getNumOperands() == 2 && "expected single level extractvalue");
171 auto *StructTy = cast<StructType>(inferScalarType(R->getOperand(0)));
172 auto *CI = cast<ConstantInt>(R->getOperand(1)->getLiveInIRValue());
173 return StructTy->getTypeAtIndex(CI->getZExtValue());
174 }
175 default:
176 break;
177 }
178
179 // Type inference not implemented for opcode.
180 LLVM_DEBUG({
181 dbgs() << "LV: Found unhandled opcode for: ";
182 R->getVPSingleValue()->dump();
183 });
184 llvm_unreachable("Unhandled opcode!");
185}
186
187Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPWidenCallRecipe *R) {
188 auto &CI = *cast<CallInst>(R->getUnderlyingInstr());
189 return CI.getType();
190}
191
192Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPWidenMemoryRecipe *R) {
194 "Store recipes should not define any values");
195 return cast<LoadInst>(&R->getIngredient())->getType();
196}
197
198Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPWidenSelectRecipe *R) {
199 Type *ResTy = inferScalarType(R->getOperand(1));
200 VPValue *OtherV = R->getOperand(2);
201 assert(inferScalarType(OtherV) == ResTy &&
202 "different types inferred for different operands");
203 CachedTypes[OtherV] = ResTy;
204 return ResTy;
205}
206
207Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPReplicateRecipe *R) {
208 unsigned Opcode = R->getUnderlyingInstr()->getOpcode();
209
210 if (Instruction::isBinaryOp(Opcode) || Instruction::isShift(Opcode) ||
212 Type *ResTy = inferScalarType(R->getOperand(0));
213 assert(ResTy == inferScalarType(R->getOperand(1)) &&
214 "inferred types for operands of binary op don't match");
215 CachedTypes[R->getOperand(1)] = ResTy;
216 return ResTy;
217 }
218
219 if (Instruction::isCast(Opcode))
220 return R->getUnderlyingInstr()->getType();
221
222 switch (Opcode) {
223 case Instruction::Call: {
224 unsigned CallIdx = R->getNumOperands() - (R->isPredicated() ? 2 : 1);
225 return cast<Function>(R->getOperand(CallIdx)->getLiveInIRValue())
226 ->getReturnType();
227 }
228 case Instruction::Select: {
229 Type *ResTy = inferScalarType(R->getOperand(1));
230 assert(ResTy == inferScalarType(R->getOperand(2)) &&
231 "inferred types for operands of select op don't match");
232 CachedTypes[R->getOperand(2)] = ResTy;
233 return ResTy;
234 }
235 case Instruction::ICmp:
236 case Instruction::FCmp:
237 return IntegerType::get(Ctx, 1);
238 case Instruction::Alloca:
239 case Instruction::ExtractValue:
240 return R->getUnderlyingInstr()->getType();
241 case Instruction::Freeze:
242 case Instruction::FNeg:
243 case Instruction::GetElementPtr:
244 return inferScalarType(R->getOperand(0));
245 case Instruction::Load:
246 return cast<LoadInst>(R->getUnderlyingInstr())->getType();
247 case Instruction::Store:
248 // FIXME: VPReplicateRecipes with store opcodes still define a result
249 // VPValue, so we need to handle them here. Remove the code here once this
250 // is modeled accurately in VPlan.
251 return Type::getVoidTy(Ctx);
252 default:
253 break;
254 }
255 // Type inference not implemented for opcode.
256 LLVM_DEBUG({
257 dbgs() << "LV: Found unhandled opcode for: ";
258 R->getVPSingleValue()->dump();
259 });
260 llvm_unreachable("Unhandled opcode");
261}
262
264 if (Type *CachedTy = CachedTypes.lookup(V))
265 return CachedTy;
266
267 if (V->isLiveIn()) {
268 if (auto *IRValue = V->getLiveInIRValue())
269 return IRValue->getType();
270 // All VPValues without any underlying IR value (like the vector trip count
271 // or the backedge-taken count) have the same type as the canonical IV.
272 return CanonicalIVTy;
273 }
274
275 Type *ResultTy =
276 TypeSwitch<const VPRecipeBase *, Type *>(V->getDefiningRecipe())
280 [this](const auto *R) {
281 // Handle header phi recipes, except VPWidenIntOrFpInduction
282 // which needs special handling due it being possibly truncated.
283 // TODO: consider inferring/caching type of siblings, e.g.,
284 // backedge value, here and in cases below.
285 return inferScalarType(R->getStartValue());
286 })
287 .Case<VPWidenIntOrFpInductionRecipe, VPDerivedIVRecipe>(
288 [](const auto *R) { return R->getScalarType(); })
292 VPPartialReductionRecipe>([this](const VPRecipeBase *R) {
293 return inferScalarType(R->getOperand(0));
294 })
295 // VPInstructionWithType must be handled before VPInstruction.
298 [](const auto *R) { return R->getResultType(); })
301 [this](const auto *R) { return inferScalarTypeForRecipe(R); })
302 .Case<VPInterleaveBase>([V](const auto *R) {
303 // TODO: Use info from interleave group.
304 return V->getUnderlyingValue()->getType();
305 })
306 .Case<VPExpandSCEVRecipe>([](const VPExpandSCEVRecipe *R) {
307 return R->getSCEV()->getType();
308 })
309 .Case<VPReductionRecipe>([this](const auto *R) {
310 return inferScalarType(R->getChainOp());
311 })
312 .Case<VPExpressionRecipe>([this](const auto *R) {
313 return inferScalarType(R->getOperandOfResultType());
314 });
315
316 assert(ResultTy && "could not infer type for the given VPValue");
317 CachedTypes[V] = ResultTy;
318 return ResultTy;
319}
320
322 VPlan &Plan, DenseSet<VPRecipeBase *> &EphRecipes) {
323 // First, collect seed recipes which are operands of assumes.
327 for (VPRecipeBase &R : *VPBB) {
328 auto *RepR = dyn_cast<VPReplicateRecipe>(&R);
329 if (!RepR || !match(RepR->getUnderlyingInstr(),
331 continue;
332 Worklist.push_back(RepR);
333 EphRecipes.insert(RepR);
334 }
335 }
336
337 // Process operands of candidates in worklist and add them to the set of
338 // ephemeral recipes, if they don't have side-effects and are only used by
339 // other ephemeral recipes.
340 while (!Worklist.empty()) {
341 VPRecipeBase *Cur = Worklist.pop_back_val();
342 for (VPValue *Op : Cur->operands()) {
343 auto *OpR = Op->getDefiningRecipe();
344 if (!OpR || OpR->mayHaveSideEffects() || EphRecipes.contains(OpR))
345 continue;
346 if (any_of(Op->users(), [EphRecipes](VPUser *U) {
347 auto *UR = dyn_cast<VPRecipeBase>(U);
348 return !UR || !EphRecipes.contains(UR);
349 }))
350 continue;
351 EphRecipes.insert(OpR);
352 Worklist.push_back(OpR);
353 }
354 }
355}
356
359
361 const VPRecipeBase *B) {
362 if (A == B)
363 return false;
364
365 auto LocalComesBefore = [](const VPRecipeBase *A, const VPRecipeBase *B) {
366 for (auto &R : *A->getParent()) {
367 if (&R == A)
368 return true;
369 if (&R == B)
370 return false;
371 }
372 llvm_unreachable("recipe not found");
373 };
374 const VPBlockBase *ParentA = A->getParent();
375 const VPBlockBase *ParentB = B->getParent();
376 if (ParentA == ParentB)
377 return LocalComesBefore(A, B);
378
379#ifndef NDEBUG
380 auto GetReplicateRegion = [](VPRecipeBase *R) -> VPRegionBlock * {
381 VPRegionBlock *Region = R->getRegion();
382 if (Region && Region->isReplicator()) {
383 assert(Region->getNumSuccessors() == 1 &&
384 Region->getNumPredecessors() == 1 && "Expected SESE region!");
385 assert(R->getParent()->size() == 1 &&
386 "A recipe in an original replicator region must be the only "
387 "recipe in its block");
388 return Region;
389 }
390 return nullptr;
391 };
392 assert(!GetReplicateRegion(const_cast<VPRecipeBase *>(A)) &&
393 "No replicate regions expected at this point");
394 assert(!GetReplicateRegion(const_cast<VPRecipeBase *>(B)) &&
395 "No replicate regions expected at this point");
396#endif
397 return Base::properlyDominates(ParentA, ParentB);
398}
399
401 unsigned OverrideMaxNumRegs) const {
402 return any_of(MaxLocalUsers, [&TTI, &OverrideMaxNumRegs](auto &LU) {
403 return LU.second > (OverrideMaxNumRegs > 0
404 ? OverrideMaxNumRegs
405 : TTI.getNumberOfRegisters(LU.first));
406 });
407}
408
411 const SmallPtrSetImpl<const Value *> &ValuesToIgnore) {
412 // Each 'key' in the map opens a new interval. The values
413 // of the map are the index of the 'last seen' usage of the
414 // VPValue that is the key.
416
417 // Maps indices to recipes.
419 // Marks the end of each interval.
420 IntervalMap EndPoint;
421 // Saves the list of VPValues that are used in the loop.
423 // Saves the list of values that are used in the loop but are defined outside
424 // the loop (not including non-recipe values such as arguments and
425 // constants).
426 SmallSetVector<VPValue *, 8> LoopInvariants;
427 LoopInvariants.insert(&Plan.getVectorTripCount());
428
429 // We scan the loop in a topological order in order and assign a number to
430 // each recipe. We use RPO to ensure that defs are met before their users. We
431 // assume that each recipe that has in-loop users starts an interval. We
432 // record every time that an in-loop value is used, so we have a list of the
433 // first occurences of each recipe and last occurrence of each VPValue.
434 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
436 LoopRegion);
438 if (!VPBB->getParent())
439 break;
440 for (VPRecipeBase &R : *VPBB) {
441 Idx2Recipe.push_back(&R);
442
443 // Save the end location of each USE.
444 for (VPValue *U : R.operands()) {
445 auto *DefR = U->getDefiningRecipe();
446
447 // Ignore non-recipe values such as arguments, constants, etc.
448 // FIXME: Might need some motivation why these values are ignored. If
449 // for example an argument is used inside the loop it will increase the
450 // register pressure (so shouldn't we add it to LoopInvariants).
451 if (!DefR && (!U->getLiveInIRValue() ||
452 !isa<Instruction>(U->getLiveInIRValue())))
453 continue;
454
455 // If this recipe is outside the loop then record it and continue.
456 if (!DefR) {
457 LoopInvariants.insert(U);
458 continue;
459 }
460
461 // Overwrite previous end points.
462 EndPoint[U] = Idx2Recipe.size();
463 Ends.insert(U);
464 }
465 }
466 if (VPBB == LoopRegion->getExiting()) {
467 // VPWidenIntOrFpInductionRecipes are used implicitly at the end of the
468 // exiting block, where their increment will get materialized eventually.
469 for (auto &R : LoopRegion->getEntryBasicBlock()->phis()) {
470 if (auto *WideIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&R)) {
471 EndPoint[WideIV] = Idx2Recipe.size();
472 Ends.insert(WideIV);
473 }
474 }
475 }
476 }
477
478 // Saves the list of intervals that end with the index in 'key'.
479 using VPValueList = SmallVector<VPValue *, 2>;
481
482 // Next, we transpose the EndPoints into a multi map that holds the list of
483 // intervals that *end* at a specific location.
484 for (auto &Interval : EndPoint)
485 TransposeEnds[Interval.second].push_back(Interval.first);
486
487 SmallPtrSet<VPValue *, 8> OpenIntervals;
490
491 LLVM_DEBUG(dbgs() << "LV(REG): Calculating max register usage:\n");
492
493 VPTypeAnalysis TypeInfo(Plan);
494
495 const auto &TTICapture = TTI;
496 auto GetRegUsage = [&TTICapture](Type *Ty, ElementCount VF) -> unsigned {
497 if (Ty->isTokenTy() || !VectorType::isValidElementType(Ty) ||
498 (VF.isScalable() &&
499 !TTICapture.isElementTypeLegalForScalableVector(Ty)))
500 return 0;
501 return TTICapture.getRegUsageForType(VectorType::get(Ty, VF));
502 };
503
504 // We scan the instructions linearly and record each time that a new interval
505 // starts, by placing it in a set. If we find this value in TransposEnds then
506 // we remove it from the set. The max register usage is the maximum register
507 // usage of the recipes of the set.
508 for (unsigned int Idx = 0, Sz = Idx2Recipe.size(); Idx < Sz; ++Idx) {
509 VPRecipeBase *R = Idx2Recipe[Idx];
510
511 // Remove all of the VPValues that end at this location.
512 VPValueList &List = TransposeEnds[Idx];
513 for (VPValue *ToRemove : List)
514 OpenIntervals.erase(ToRemove);
515
516 // Ignore recipes that are never used within the loop and do not have side
517 // effects.
518 if (none_of(R->definedValues(),
519 [&Ends](VPValue *Def) { return Ends.count(Def); }) &&
520 !R->mayHaveSideEffects())
521 continue;
522
523 // Skip recipes for ignored values.
524 // TODO: Should mark recipes for ephemeral values that cannot be removed
525 // explictly in VPlan.
526 if (isa<VPSingleDefRecipe>(R) &&
527 ValuesToIgnore.contains(
528 cast<VPSingleDefRecipe>(R)->getUnderlyingValue()))
529 continue;
530
531 // For each VF find the maximum usage of registers.
532 for (unsigned J = 0, E = VFs.size(); J < E; ++J) {
533 // Count the number of registers used, per register class, given all open
534 // intervals.
535 // Note that elements in this SmallMapVector will be default constructed
536 // as 0. So we can use "RegUsage[ClassID] += n" in the code below even if
537 // there is no previous entry for ClassID.
539
540 for (auto *VPV : OpenIntervals) {
541 // Skip values that weren't present in the original loop.
542 // TODO: Remove after removing the legacy
543 // LoopVectorizationCostModel::calculateRegisterUsage
546 continue;
547
548 if (VFs[J].isScalar() ||
553 (cast<VPReductionPHIRecipe>(VPV))->isInLoop())) {
554 unsigned ClassID =
555 TTI.getRegisterClassForType(false, TypeInfo.inferScalarType(VPV));
556 // FIXME: The target might use more than one register for the type
557 // even in the scalar case.
558 RegUsage[ClassID] += 1;
559 } else {
560 // The output from scaled phis and scaled reductions actually has
561 // fewer lanes than the VF.
562 unsigned ScaleFactor =
563 vputils::getVFScaleFactor(VPV->getDefiningRecipe());
564 ElementCount VF = VFs[J].divideCoefficientBy(ScaleFactor);
565 LLVM_DEBUG(if (VF != VFs[J]) {
566 dbgs() << "LV(REG): Scaled down VF from " << VFs[J] << " to " << VF
567 << " for " << *R << "\n";
568 });
569
570 Type *ScalarTy = TypeInfo.inferScalarType(VPV);
571 unsigned ClassID = TTI.getRegisterClassForType(true, ScalarTy);
572 RegUsage[ClassID] += GetRegUsage(ScalarTy, VF);
573 }
574 }
575
576 for (const auto &Pair : RegUsage) {
577 auto &Entry = MaxUsages[J][Pair.first];
578 Entry = std::max(Entry, Pair.second);
579 }
580 }
581
582 LLVM_DEBUG(dbgs() << "LV(REG): At #" << Idx << " Interval # "
583 << OpenIntervals.size() << '\n');
584
585 // Add used VPValues defined by the current recipe to the list of open
586 // intervals.
587 for (VPValue *DefV : R->definedValues())
588 if (Ends.contains(DefV))
589 OpenIntervals.insert(DefV);
590 }
591
592 // We also search for instructions that are defined outside the loop, but are
593 // used inside the loop. We need this number separately from the max-interval
594 // usage number because when we unroll, loop-invariant values do not take
595 // more register.
597 for (unsigned Idx = 0, End = VFs.size(); Idx < End; ++Idx) {
598 // Note that elements in this SmallMapVector will be default constructed
599 // as 0. So we can use "Invariant[ClassID] += n" in the code below even if
600 // there is no previous entry for ClassID.
602
603 for (auto *In : LoopInvariants) {
604 // FIXME: The target might use more than one register for the type
605 // even in the scalar case.
606 bool IsScalar = vputils::onlyScalarValuesUsed(In);
607
608 ElementCount VF = IsScalar ? ElementCount::getFixed(1) : VFs[Idx];
609 unsigned ClassID = TTI.getRegisterClassForType(
610 VF.isVector(), TypeInfo.inferScalarType(In));
611 Invariant[ClassID] += GetRegUsage(TypeInfo.inferScalarType(In), VF);
612 }
613
614 LLVM_DEBUG({
615 dbgs() << "LV(REG): VF = " << VFs[Idx] << '\n';
616 dbgs() << "LV(REG): Found max usage: " << MaxUsages[Idx].size()
617 << " item\n";
618 for (const auto &pair : MaxUsages[Idx]) {
619 dbgs() << "LV(REG): RegisterClass: "
620 << TTI.getRegisterClassName(pair.first) << ", " << pair.second
621 << " registers\n";
622 }
623 dbgs() << "LV(REG): Found invariant usage: " << Invariant.size()
624 << " item\n";
625 for (const auto &pair : Invariant) {
626 dbgs() << "LV(REG): RegisterClass: "
627 << TTI.getRegisterClassName(pair.first) << ", " << pair.second
628 << " registers\n";
629 }
630 });
631
632 RU.LoopInvariantRegs = Invariant;
633 RU.MaxLocalUsers = MaxUsages[Idx];
634 RUs[Idx] = RU;
635 }
636
637 return RUs;
638}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
ReachingDefInfo InstSet & ToRemove
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 I(x, y, z)
Definition MD5.cpp:58
std::pair< uint64_t, uint64_t > Interval
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
#define LLVM_DEBUG(...)
Definition Debug.h:114
This pass exposes codegen information to IR-level passes.
This file implements the TypeSwitch template, which mimics a switch() statement whose cases are type ...
This file implements dominator tree analysis for a single level of a VPlan's H-CFG.
This file contains the declarations of different VPlan-related auxiliary helpers.
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),...
Definition ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition ArrayRef.h:147
Implements a dense probed hash-table based set.
Definition DenseSet.h:279
Core dominator tree base class.
bool properlyDominates(const DomTreeNodeBase< VPBlockBase > *A, const DomTreeNodeBase< VPBlockBase > *B) const
constexpr bool isVector() const
One or more elements.
Definition TypeSize.h:325
static constexpr ElementCount getFixed(ScalarTy MinVal)
Definition TypeSize.h:310
bool isCast() const
bool isBinaryOp() const
bool isBitwiseLogicOp() const
Return true if this is and/or/xor.
bool isShift() const
bool isUnaryOp() const
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition Type.cpp:319
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition SetVector.h:150
size_type size() const
Definition SmallPtrSet.h:99
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
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.
A SetVector that performs no allocations if smaller than a certain size.
Definition SetVector.h:338
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
This class implements a switch-like dispatch statement for a value of 'T' using dyn_cast functionalit...
Definition TypeSwitch.h:88
TypeSwitch< T, ResultT > & Case(CallableT &&caseFn)
Add a case on the given type.
Definition TypeSwitch.h:97
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:45
static LLVM_ABI Type * getVoidTy(LLVMContext &C)
Definition Type.cpp:281
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition Type.h:240
static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition Type.cpp:301
A recipe for generating the active lane mask for the vector loop that is used to predicate the vector...
Definition VPlan.h:3513
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition VPlan.h:3800
iterator_range< iterator > phis()
Returns an iterator range over the PHI-like recipes in the block.
Definition VPlan.h:3888
A recipe for vectorizing a phi-node as a sequence of mask-based select instructions.
Definition VPlan.h:2406
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition VPlan.h:80
const VPBasicBlock * getEntryBasicBlock() const
Definition VPlan.cpp:170
static auto blocksOnly(const T &Range)
Return an iterator range over Range which only includes BlockTy blocks.
Definition VPlanUtils.h:238
A recipe for generating conditional branches on the bits of a mask.
Definition VPlan.h:2946
Canonical scalar induction phi of the vector loop.
Definition VPlan.h:3456
A recipe for converting the input value IV value to the corresponding value of an IV with different s...
Definition VPlan.h:3621
bool properlyDominates(const VPRecipeBase *A, const VPRecipeBase *B)
A recipe for generating the phi node for the current index of elements, adjusted in accordance with E...
Definition VPlan.h:3544
Recipe to expand a SCEV expression.
Definition VPlan.h:3419
A specialization of VPInstruction augmenting it with a dedicated result type, to be used when the opc...
Definition VPlan.h:1191
This is a concrete Recipe that models a single VPlan-level instruction.
Definition VPlan.h:979
@ ExtractLane
Extracts a single lane (first operand) from a set of vector operands.
Definition VPlan.h:1063
@ ComputeAnyOfResult
Compute the final result of a AnyOf reduction with select(cmp(),x,y), where one of (x,...
Definition VPlan.h:1017
@ ResumeForEpilogue
Explicit user for the resume phi of the canonical induction in the main VPlan, used by the epilogue v...
Definition VPlan.h:1066
@ Unpack
Extracts all lanes from its (non-scalable) vector operand.
Definition VPlan.h:1014
@ FirstOrderRecurrenceSplice
Definition VPlan.h:985
@ ReductionStartVector
Start vector for reductions with 3 operands: the original start value, the identity value for the red...
Definition VPlan.h:1057
@ BuildVector
Creates a fixed-width vector containing all operands.
Definition VPlan.h:1009
@ BuildStructVector
Given operands of (the same) struct type, creates a struct of fixed- width vectors each containing a ...
Definition VPlan.h:1006
@ CanonicalIVIncrementForPart
Definition VPlan.h:999
@ CalculateTripCountMinusVF
Definition VPlan.h:997
A recipe for forming partial reductions.
Definition VPlan.h:2765
VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when control converges back from ...
Definition VPlan.h:3127
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition VPlan.h:386
A recipe for handling reduction phis.
Definition VPlan.h:2334
A recipe to represent inloop reduction operations, performing a reduction on a vector operand into a ...
Definition VPlan.h:2669
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition VPlan.h:3988
const VPBlockBase * getEntry() const
Definition VPlan.h:4024
const VPBlockBase * getExiting() const
Definition VPlan.h:4036
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
Definition VPlan.h:2868
A recipe for handling phi nodes of integer and floating-point inductions, producing their scalar valu...
Definition VPlan.h:3690
An analysis for type-inference for VPValues.
LLVMContext & getContext()
Return the LLVMContext used by the analysis.
Type * inferScalarType(const VPValue *V)
Infer the type of V. Returns the scalar type of V.
VPTypeAnalysis(const VPlan &Plan)
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition VPlanValue.h:199
operand_range operands()
Definition VPlanValue.h:267
A recipe to compute a pointer to the last element of each part of a widened memory access for widened...
Definition VPlan.h:1845
A recipe to compute the pointers for widened memory accesses of IndexTy.
Definition VPlan.h:1904
A recipe for widening Call instructions using library calls.
Definition VPlan.h:1633
A Recipe for widening the canonical induction variable of the vector loop.
Definition VPlan.h:3585
VPWidenCastRecipe is a recipe to create vector cast instructions.
Definition VPlan.h:1486
A recipe for handling GEP instructions.
Definition VPlan.h:1773
A recipe for widening vector intrinsics.
Definition VPlan.h:1544
A common base class for widening memory operations.
Definition VPlan.h:3169
A recipe for widened phis.
Definition VPlan.h:2257
VPWidenRecipe is a recipe for producing a widened instruction using the opcode and operands of the re...
Definition VPlan.h:1443
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition VPlan.h:4112
VPValue & getVectorTripCount()
The vector trip count.
Definition VPlan.h:4305
LLVM_ABI_FOR_TEST VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition VPlan.cpp:1027
static LLVM_ABI VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
static LLVM_ABI bool isValidElementType(Type *ElemTy)
Return true if the specified type is valid as a element type.
std::pair< iterator, bool > insert(const ValueT &V)
Definition DenseSet.h:202
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition DenseSet.h:175
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool match(Val *V, const Pattern &P)
IntrinsicID_match m_Intrinsic()
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
bool onlyScalarValuesUsed(const VPValue *Def)
Returns true if only scalar values of Def are used by all users.
unsigned getVFScaleFactor(VPRecipeBase *R)
Get the VF scaling factor applied to the recipe's output, if the recipe has one.
This is an optimization pass for GlobalISel generic memory operations.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
iterator_range< df_iterator< VPBlockDeepTraversalWrapper< VPBlockBase * > > > vp_depth_first_deep(VPBlockBase *G)
Returns an iterator range to traverse the graph starting at G in depth-first order while traversing t...
Definition VPlanCFG.h:243
SmallVector< VPRegisterUsage, 8 > calculateRegisterUsageForPlan(VPlan &Plan, ArrayRef< ElementCount > VFs, const TargetTransformInfo &TTI, const SmallPtrSetImpl< const Value * > &ValuesToIgnore)
Estimate the register usage for Plan and vectorization factors in VFs by calculating the highest numb...
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1732
void collectEphemeralRecipesForVPlan(VPlan &Plan, DenseSet< VPRecipeBase * > &EphRecipes)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1739
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
TargetTransformInfo TTI
DWARFExpression::Operation Op
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
A MapVector that performs no allocations if smaller than a certain size.
Definition MapVector.h:257
A recipe for handling first-order recurrence phis.
Definition VPlan.h:2299
A struct that represents some properties of the register usage of a loop.
SmallMapVector< unsigned, unsigned, 4 > MaxLocalUsers
Holds the maximum number of concurrent live intervals in the loop.
bool exceedsMaxNumRegs(const TargetTransformInfo &TTI, unsigned OverrideMaxNumRegs=0) const
Check if any of the tracked live intervals exceeds the number of available registers for the target.
SmallMapVector< unsigned, unsigned, 4 > LoopInvariantRegs
Holds the number of loop invariant values that are used in the loop.
A recipe for widening select instructions.
Definition VPlan.h:1727