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