xref: /llvm-project/llvm/lib/Transforms/Vectorize/VPlanAnalysis.cpp (revision 060d62b48aeb5080ffcae1dc56e41a06c6f56701) 
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 "llvm/ADT/TypeSwitch.h"
14 #include "llvm/Analysis/ScalarEvolution.h"
15 #include "llvm/IR/Instruction.h"
16 #include "llvm/IR/PatternMatch.h"
17 #include "llvm/Support/GenericDomTreeConstruction.h"
18 
19 using namespace llvm;
20 
21 #define DEBUG_TYPE "vplan"
22 
23 Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPBlendRecipe *R) {
24   Type *ResTy = inferScalarType(R->getIncomingValue(0));
25   for (unsigned I = 1, E = R->getNumIncomingValues(); I != E; ++I) {
26     VPValue *Inc = R->getIncomingValue(I);
27     assert(inferScalarType(Inc) == ResTy &&
28            "different types inferred for different incoming values");
29     CachedTypes[Inc] = ResTy;
30   }
31   return ResTy;
32 }
33 
34 Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPInstruction *R) {
35   // Set the result type from the first operand, check if the types for all
36   // other operands match and cache them.
37   auto SetResultTyFromOp = [this, R]() {
38     Type *ResTy = inferScalarType(R->getOperand(0));
39     for (unsigned Op = 1; Op != R->getNumOperands(); ++Op) {
40       VPValue *OtherV = R->getOperand(Op);
41       assert(inferScalarType(OtherV) == ResTy &&
42              "different types inferred for different operands");
43       CachedTypes[OtherV] = ResTy;
44     }
45     return ResTy;
46   };
47 
48   unsigned Opcode = R->getOpcode();
49   if (Instruction::isBinaryOp(Opcode) || Instruction::isUnaryOp(Opcode))
50     return SetResultTyFromOp();
51 
52   switch (Opcode) {
53   case Instruction::Select: {
54     Type *ResTy = inferScalarType(R->getOperand(1));
55     VPValue *OtherV = R->getOperand(2);
56     assert(inferScalarType(OtherV) == ResTy &&
57            "different types inferred for different operands");
58     CachedTypes[OtherV] = ResTy;
59     return ResTy;
60   }
61   case Instruction::ICmp:
62   case VPInstruction::ActiveLaneMask:
63     return inferScalarType(R->getOperand(1));
64   case VPInstruction::ExplicitVectorLength:
65     return Type::getIntNTy(Ctx, 32);
66   case VPInstruction::FirstOrderRecurrenceSplice:
67   case VPInstruction::Not:
68     return SetResultTyFromOp();
69   case VPInstruction::ExtractFromEnd: {
70     Type *BaseTy = inferScalarType(R->getOperand(0));
71     if (auto *VecTy = dyn_cast<VectorType>(BaseTy))
72       return VecTy->getElementType();
73     return BaseTy;
74   }
75   case VPInstruction::LogicalAnd:
76     return IntegerType::get(Ctx, 1);
77   case VPInstruction::PtrAdd:
78     // Return the type based on the pointer argument (i.e. first operand).
79     return inferScalarType(R->getOperand(0));
80   case VPInstruction::BranchOnCond:
81   case VPInstruction::BranchOnCount:
82     return Type::getVoidTy(Ctx);
83   default:
84     break;
85   }
86   // Type inference not implemented for opcode.
87   LLVM_DEBUG({
88     dbgs() << "LV: Found unhandled opcode for: ";
89     R->getVPSingleValue()->dump();
90   });
91   llvm_unreachable("Unhandled opcode!");
92 }
93 
94 Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPWidenRecipe *R) {
95   unsigned Opcode = R->getOpcode();
96   if (Instruction::isBinaryOp(Opcode) || Instruction::isShift(Opcode) ||
97       Instruction::isBitwiseLogicOp(Opcode)) {
98     Type *ResTy = inferScalarType(R->getOperand(0));
99     assert(ResTy == inferScalarType(R->getOperand(1)) &&
100            "types for both operands must match for binary op");
101     CachedTypes[R->getOperand(1)] = ResTy;
102     return ResTy;
103   }
104 
105   switch (Opcode) {
106   case Instruction::ICmp:
107   case Instruction::FCmp:
108     return IntegerType::get(Ctx, 1);
109   case Instruction::FNeg:
110   case Instruction::Freeze:
111     return inferScalarType(R->getOperand(0));
112   default:
113     break;
114   }
115 
116   // Type inference not implemented for opcode.
117   LLVM_DEBUG({
118     dbgs() << "LV: Found unhandled opcode for: ";
119     R->getVPSingleValue()->dump();
120   });
121   llvm_unreachable("Unhandled opcode!");
122 }
123 
124 Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPWidenCallRecipe *R) {
125   auto &CI = *cast<CallInst>(R->getUnderlyingInstr());
126   return CI.getType();
127 }
128 
129 Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPWidenMemoryRecipe *R) {
130   assert((isa<VPWidenLoadRecipe, VPWidenLoadEVLRecipe>(R)) &&
131          "Store recipes should not define any values");
132   return cast<LoadInst>(&R->getIngredient())->getType();
133 }
134 
135 Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPWidenSelectRecipe *R) {
136   Type *ResTy = inferScalarType(R->getOperand(1));
137   VPValue *OtherV = R->getOperand(2);
138   assert(inferScalarType(OtherV) == ResTy &&
139          "different types inferred for different operands");
140   CachedTypes[OtherV] = ResTy;
141   return ResTy;
142 }
143 
144 Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPReplicateRecipe *R) {
145   unsigned Opcode = R->getUnderlyingInstr()->getOpcode();
146 
147   if (Instruction::isBinaryOp(Opcode) || Instruction::isShift(Opcode) ||
148       Instruction::isBitwiseLogicOp(Opcode)) {
149     Type *ResTy = inferScalarType(R->getOperand(0));
150     assert(ResTy == inferScalarType(R->getOperand(1)) &&
151            "inferred types for operands of binary op don't match");
152     CachedTypes[R->getOperand(1)] = ResTy;
153     return ResTy;
154   }
155 
156   if (Instruction::isCast(Opcode))
157     return R->getUnderlyingInstr()->getType();
158 
159   switch (Opcode) {
160   case Instruction::Call: {
161     unsigned CallIdx = R->getNumOperands() - (R->isPredicated() ? 2 : 1);
162     return cast<Function>(R->getOperand(CallIdx)->getLiveInIRValue())
163         ->getReturnType();
164   }
165   case Instruction::Select: {
166     Type *ResTy = inferScalarType(R->getOperand(1));
167     assert(ResTy == inferScalarType(R->getOperand(2)) &&
168            "inferred types for operands of select op don't match");
169     CachedTypes[R->getOperand(2)] = ResTy;
170     return ResTy;
171   }
172   case Instruction::ICmp:
173   case Instruction::FCmp:
174     return IntegerType::get(Ctx, 1);
175   case Instruction::Alloca:
176   case Instruction::ExtractValue:
177     return R->getUnderlyingInstr()->getType();
178   case Instruction::Freeze:
179   case Instruction::FNeg:
180   case Instruction::GetElementPtr:
181     return inferScalarType(R->getOperand(0));
182   case Instruction::Load:
183     return cast<LoadInst>(R->getUnderlyingInstr())->getType();
184   case Instruction::Store:
185     // FIXME: VPReplicateRecipes with store opcodes still define a result
186     // VPValue, so we need to handle them here. Remove the code here once this
187     // is modeled accurately in VPlan.
188     return Type::getVoidTy(Ctx);
189   default:
190     break;
191   }
192   // Type inference not implemented for opcode.
193   LLVM_DEBUG({
194     dbgs() << "LV: Found unhandled opcode for: ";
195     R->getVPSingleValue()->dump();
196   });
197   llvm_unreachable("Unhandled opcode");
198 }
199 
200 Type *VPTypeAnalysis::inferScalarType(const VPValue *V) {
201   if (Type *CachedTy = CachedTypes.lookup(V))
202     return CachedTy;
203 
204   if (V->isLiveIn()) {
205     if (auto *IRValue = V->getLiveInIRValue())
206       return IRValue->getType();
207     // All VPValues without any underlying IR value (like the vector trip count
208     // or the backedge-taken count) have the same type as the canonical IV.
209     return CanonicalIVTy;
210   }
211 
212   Type *ResultTy =
213       TypeSwitch<const VPRecipeBase *, Type *>(V->getDefiningRecipe())
214           .Case<VPActiveLaneMaskPHIRecipe, VPCanonicalIVPHIRecipe,
215                 VPFirstOrderRecurrencePHIRecipe, VPReductionPHIRecipe,
216                 VPWidenPointerInductionRecipe, VPEVLBasedIVPHIRecipe,
217                 VPScalarPHIRecipe>([this](const auto *R) {
218             // Handle header phi recipes, except VPWidenIntOrFpInduction
219             // which needs special handling due it being possibly truncated.
220             // TODO: consider inferring/caching type of siblings, e.g.,
221             // backedge value, here and in cases below.
222             return inferScalarType(R->getStartValue());
223           })
224           .Case<VPWidenIntOrFpInductionRecipe, VPDerivedIVRecipe>(
225               [](const auto *R) { return R->getScalarType(); })
226           .Case<VPReductionRecipe, VPPredInstPHIRecipe, VPWidenPHIRecipe,
227                 VPScalarIVStepsRecipe, VPWidenGEPRecipe, VPVectorPointerRecipe,
228                 VPReverseVectorPointerRecipe, VPWidenCanonicalIVRecipe,
229                 VPPartialReductionRecipe>([this](const VPRecipeBase *R) {
230             return inferScalarType(R->getOperand(0));
231           })
232           .Case<VPBlendRecipe, VPInstruction, VPWidenRecipe, VPWidenEVLRecipe,
233                 VPReplicateRecipe, VPWidenCallRecipe, VPWidenMemoryRecipe,
234                 VPWidenSelectRecipe>(
235               [this](const auto *R) { return inferScalarTypeForRecipe(R); })
236           .Case<VPWidenIntrinsicRecipe>([](const VPWidenIntrinsicRecipe *R) {
237             return R->getResultType();
238           })
239           .Case<VPInterleaveRecipe>([V](const VPInterleaveRecipe *R) {
240             // TODO: Use info from interleave group.
241             return V->getUnderlyingValue()->getType();
242           })
243           .Case<VPWidenCastRecipe>(
244               [](const VPWidenCastRecipe *R) { return R->getResultType(); })
245           .Case<VPScalarCastRecipe>(
246               [](const VPScalarCastRecipe *R) { return R->getResultType(); })
247           .Case<VPExpandSCEVRecipe>([](const VPExpandSCEVRecipe *R) {
248             return R->getSCEV()->getType();
249           })
250           .Case<VPReductionRecipe>([this](const auto *R) {
251             return inferScalarType(R->getChainOp());
252           });
253 
254   assert(ResultTy && "could not infer type for the given VPValue");
255   CachedTypes[V] = ResultTy;
256   return ResultTy;
257 }
258 
259 void llvm::collectEphemeralRecipesForVPlan(
260     VPlan &Plan, DenseSet<VPRecipeBase *> &EphRecipes) {
261   // First, collect seed recipes which are operands of assumes.
262   SmallVector<VPRecipeBase *> Worklist;
263   for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
264            vp_depth_first_deep(Plan.getVectorLoopRegion()->getEntry()))) {
265     for (VPRecipeBase &R : *VPBB) {
266       auto *RepR = dyn_cast<VPReplicateRecipe>(&R);
267       if (!RepR || !match(RepR->getUnderlyingInstr(),
268                           PatternMatch::m_Intrinsic<Intrinsic::assume>()))
269         continue;
270       Worklist.push_back(RepR);
271       EphRecipes.insert(RepR);
272     }
273   }
274 
275   // Process operands of candidates in worklist and add them to the set of
276   // ephemeral recipes, if they don't have side-effects and are only used by
277   // other ephemeral recipes.
278   while (!Worklist.empty()) {
279     VPRecipeBase *Cur = Worklist.pop_back_val();
280     for (VPValue *Op : Cur->operands()) {
281       auto *OpR = Op->getDefiningRecipe();
282       if (!OpR || OpR->mayHaveSideEffects() || EphRecipes.contains(OpR))
283         continue;
284       if (any_of(Op->users(), [EphRecipes](VPUser *U) {
285             auto *UR = dyn_cast<VPRecipeBase>(U);
286             return !UR || !EphRecipes.contains(UR);
287           }))
288         continue;
289       EphRecipes.insert(OpR);
290       Worklist.push_back(OpR);
291     }
292   }
293 }
294 
295 template void DomTreeBuilder::Calculate<DominatorTreeBase<VPBlockBase, false>>(
296     DominatorTreeBase<VPBlockBase, false> &DT);
297 
298 bool VPDominatorTree::properlyDominates(const VPRecipeBase *A,
299                                         const VPRecipeBase *B) {
300   if (A == B)
301     return false;
302 
303   auto LocalComesBefore = [](const VPRecipeBase *A, const VPRecipeBase *B) {
304     for (auto &R : *A->getParent()) {
305       if (&R == A)
306         return true;
307       if (&R == B)
308         return false;
309     }
310     llvm_unreachable("recipe not found");
311   };
312   const VPBlockBase *ParentA = A->getParent();
313   const VPBlockBase *ParentB = B->getParent();
314   if (ParentA == ParentB)
315     return LocalComesBefore(A, B);
316 
317 #ifndef NDEBUG
318   auto GetReplicateRegion = [](VPRecipeBase *R) -> VPRegionBlock * {
319     auto *Region = dyn_cast_or_null<VPRegionBlock>(R->getParent()->getParent());
320     if (Region && Region->isReplicator()) {
321       assert(Region->getNumSuccessors() == 1 &&
322              Region->getNumPredecessors() == 1 && "Expected SESE region!");
323       assert(R->getParent()->size() == 1 &&
324              "A recipe in an original replicator region must be the only "
325              "recipe in its block");
326       return Region;
327     }
328     return nullptr;
329   };
330   assert(!GetReplicateRegion(const_cast<VPRecipeBase *>(A)) &&
331          "No replicate regions expected at this point");
332   assert(!GetReplicateRegion(const_cast<VPRecipeBase *>(B)) &&
333          "No replicate regions expected at this point");
334 #endif
335   return Base::properlyDominates(ParentA, ParentB);
336 }
337