File: | build/source/llvm/lib/Analysis/IVDescriptors.cpp |
Warning: | line 1157, column 12 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- llvm/Analysis/IVDescriptors.cpp - IndVar Descriptors -----*- 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 | // This file "describes" induction and recurrence variables. | ||||
10 | // | ||||
11 | //===----------------------------------------------------------------------===// | ||||
12 | |||||
13 | #include "llvm/Analysis/IVDescriptors.h" | ||||
14 | #include "llvm/Analysis/DemandedBits.h" | ||||
15 | #include "llvm/Analysis/LoopInfo.h" | ||||
16 | #include "llvm/Analysis/ScalarEvolution.h" | ||||
17 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" | ||||
18 | #include "llvm/Analysis/ValueTracking.h" | ||||
19 | #include "llvm/IR/Dominators.h" | ||||
20 | #include "llvm/IR/Instructions.h" | ||||
21 | #include "llvm/IR/Module.h" | ||||
22 | #include "llvm/IR/PatternMatch.h" | ||||
23 | #include "llvm/IR/ValueHandle.h" | ||||
24 | #include "llvm/Support/Debug.h" | ||||
25 | #include "llvm/Support/KnownBits.h" | ||||
26 | |||||
27 | #include <set> | ||||
28 | |||||
29 | using namespace llvm; | ||||
30 | using namespace llvm::PatternMatch; | ||||
31 | |||||
32 | #define DEBUG_TYPE"iv-descriptors" "iv-descriptors" | ||||
33 | |||||
34 | bool RecurrenceDescriptor::areAllUsesIn(Instruction *I, | ||||
35 | SmallPtrSetImpl<Instruction *> &Set) { | ||||
36 | for (const Use &Use : I->operands()) | ||||
37 | if (!Set.count(dyn_cast<Instruction>(Use))) | ||||
38 | return false; | ||||
39 | return true; | ||||
40 | } | ||||
41 | |||||
42 | bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurKind Kind) { | ||||
43 | switch (Kind) { | ||||
44 | default: | ||||
45 | break; | ||||
46 | case RecurKind::Add: | ||||
47 | case RecurKind::Mul: | ||||
48 | case RecurKind::Or: | ||||
49 | case RecurKind::And: | ||||
50 | case RecurKind::Xor: | ||||
51 | case RecurKind::SMax: | ||||
52 | case RecurKind::SMin: | ||||
53 | case RecurKind::UMax: | ||||
54 | case RecurKind::UMin: | ||||
55 | case RecurKind::SelectICmp: | ||||
56 | case RecurKind::SelectFCmp: | ||||
57 | return true; | ||||
58 | } | ||||
59 | return false; | ||||
60 | } | ||||
61 | |||||
62 | bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurKind Kind) { | ||||
63 | return (Kind != RecurKind::None) && !isIntegerRecurrenceKind(Kind); | ||||
64 | } | ||||
65 | |||||
66 | /// Determines if Phi may have been type-promoted. If Phi has a single user | ||||
67 | /// that ANDs the Phi with a type mask, return the user. RT is updated to | ||||
68 | /// account for the narrower bit width represented by the mask, and the AND | ||||
69 | /// instruction is added to CI. | ||||
70 | static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT, | ||||
71 | SmallPtrSetImpl<Instruction *> &Visited, | ||||
72 | SmallPtrSetImpl<Instruction *> &CI) { | ||||
73 | if (!Phi->hasOneUse()) | ||||
74 | return Phi; | ||||
75 | |||||
76 | const APInt *M = nullptr; | ||||
77 | Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser()); | ||||
78 | |||||
79 | // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT | ||||
80 | // with a new integer type of the corresponding bit width. | ||||
81 | if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) { | ||||
82 | int32_t Bits = (*M + 1).exactLogBase2(); | ||||
83 | if (Bits > 0) { | ||||
84 | RT = IntegerType::get(Phi->getContext(), Bits); | ||||
85 | Visited.insert(Phi); | ||||
86 | CI.insert(J); | ||||
87 | return J; | ||||
88 | } | ||||
89 | } | ||||
90 | return Phi; | ||||
91 | } | ||||
92 | |||||
93 | /// Compute the minimal bit width needed to represent a reduction whose exit | ||||
94 | /// instruction is given by Exit. | ||||
95 | static std::pair<Type *, bool> computeRecurrenceType(Instruction *Exit, | ||||
96 | DemandedBits *DB, | ||||
97 | AssumptionCache *AC, | ||||
98 | DominatorTree *DT) { | ||||
99 | bool IsSigned = false; | ||||
100 | const DataLayout &DL = Exit->getModule()->getDataLayout(); | ||||
101 | uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType()); | ||||
102 | |||||
103 | if (DB) { | ||||
104 | // Use the demanded bits analysis to determine the bits that are live out | ||||
105 | // of the exit instruction, rounding up to the nearest power of two. If the | ||||
106 | // use of demanded bits results in a smaller bit width, we know the value | ||||
107 | // must be positive (i.e., IsSigned = false), because if this were not the | ||||
108 | // case, the sign bit would have been demanded. | ||||
109 | auto Mask = DB->getDemandedBits(Exit); | ||||
110 | MaxBitWidth = Mask.getBitWidth() - Mask.countl_zero(); | ||||
111 | } | ||||
112 | |||||
113 | if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) { | ||||
114 | // If demanded bits wasn't able to limit the bit width, we can try to use | ||||
115 | // value tracking instead. This can be the case, for example, if the value | ||||
116 | // may be negative. | ||||
117 | auto NumSignBits = ComputeNumSignBits(Exit, DL, 0, AC, nullptr, DT); | ||||
118 | auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType()); | ||||
119 | MaxBitWidth = NumTypeBits - NumSignBits; | ||||
120 | KnownBits Bits = computeKnownBits(Exit, DL); | ||||
121 | if (!Bits.isNonNegative()) { | ||||
122 | // If the value is not known to be non-negative, we set IsSigned to true, | ||||
123 | // meaning that we will use sext instructions instead of zext | ||||
124 | // instructions to restore the original type. | ||||
125 | IsSigned = true; | ||||
126 | // Make sure at at least one sign bit is included in the result, so it | ||||
127 | // will get properly sign-extended. | ||||
128 | ++MaxBitWidth; | ||||
129 | } | ||||
130 | } | ||||
131 | MaxBitWidth = llvm::bit_ceil(MaxBitWidth); | ||||
132 | |||||
133 | return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth), | ||||
134 | IsSigned); | ||||
135 | } | ||||
136 | |||||
137 | /// Collect cast instructions that can be ignored in the vectorizer's cost | ||||
138 | /// model, given a reduction exit value and the minimal type in which the | ||||
139 | // reduction can be represented. Also search casts to the recurrence type | ||||
140 | // to find the minimum width used by the recurrence. | ||||
141 | static void collectCastInstrs(Loop *TheLoop, Instruction *Exit, | ||||
142 | Type *RecurrenceType, | ||||
143 | SmallPtrSetImpl<Instruction *> &Casts, | ||||
144 | unsigned &MinWidthCastToRecurTy) { | ||||
145 | |||||
146 | SmallVector<Instruction *, 8> Worklist; | ||||
147 | SmallPtrSet<Instruction *, 8> Visited; | ||||
148 | Worklist.push_back(Exit); | ||||
149 | MinWidthCastToRecurTy = -1U; | ||||
150 | |||||
151 | while (!Worklist.empty()) { | ||||
152 | Instruction *Val = Worklist.pop_back_val(); | ||||
153 | Visited.insert(Val); | ||||
154 | if (auto *Cast = dyn_cast<CastInst>(Val)) { | ||||
155 | if (Cast->getSrcTy() == RecurrenceType) { | ||||
156 | // If the source type of a cast instruction is equal to the recurrence | ||||
157 | // type, it will be eliminated, and should be ignored in the vectorizer | ||||
158 | // cost model. | ||||
159 | Casts.insert(Cast); | ||||
160 | continue; | ||||
161 | } | ||||
162 | if (Cast->getDestTy() == RecurrenceType) { | ||||
163 | // The minimum width used by the recurrence is found by checking for | ||||
164 | // casts on its operands. The minimum width is used by the vectorizer | ||||
165 | // when finding the widest type for in-loop reductions without any | ||||
166 | // loads/stores. | ||||
167 | MinWidthCastToRecurTy = std::min<unsigned>( | ||||
168 | MinWidthCastToRecurTy, Cast->getSrcTy()->getScalarSizeInBits()); | ||||
169 | continue; | ||||
170 | } | ||||
171 | } | ||||
172 | // Add all operands to the work list if they are loop-varying values that | ||||
173 | // we haven't yet visited. | ||||
174 | for (Value *O : cast<User>(Val)->operands()) | ||||
175 | if (auto *I = dyn_cast<Instruction>(O)) | ||||
176 | if (TheLoop->contains(I) && !Visited.count(I)) | ||||
177 | Worklist.push_back(I); | ||||
178 | } | ||||
179 | } | ||||
180 | |||||
181 | // Check if a given Phi node can be recognized as an ordered reduction for | ||||
182 | // vectorizing floating point operations without unsafe math. | ||||
183 | static bool checkOrderedReduction(RecurKind Kind, Instruction *ExactFPMathInst, | ||||
184 | Instruction *Exit, PHINode *Phi) { | ||||
185 | // Currently only FAdd and FMulAdd are supported. | ||||
186 | if (Kind != RecurKind::FAdd && Kind != RecurKind::FMulAdd) | ||||
187 | return false; | ||||
188 | |||||
189 | if (Kind == RecurKind::FAdd && Exit->getOpcode() != Instruction::FAdd) | ||||
190 | return false; | ||||
191 | |||||
192 | if (Kind == RecurKind::FMulAdd && | ||||
193 | !RecurrenceDescriptor::isFMulAddIntrinsic(Exit)) | ||||
194 | return false; | ||||
195 | |||||
196 | // Ensure the exit instruction has only one user other than the reduction PHI | ||||
197 | if (Exit != ExactFPMathInst || Exit->hasNUsesOrMore(3)) | ||||
198 | return false; | ||||
199 | |||||
200 | // The only pattern accepted is the one in which the reduction PHI | ||||
201 | // is used as one of the operands of the exit instruction | ||||
202 | auto *Op0 = Exit->getOperand(0); | ||||
203 | auto *Op1 = Exit->getOperand(1); | ||||
204 | if (Kind == RecurKind::FAdd && Op0 != Phi && Op1 != Phi) | ||||
205 | return false; | ||||
206 | if (Kind == RecurKind::FMulAdd && Exit->getOperand(2) != Phi) | ||||
207 | return false; | ||||
208 | |||||
209 | LLVM_DEBUG(dbgs() << "LV: Found an ordered reduction: Phi: " << *Phido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "LV: Found an ordered reduction: Phi: " << *Phi << ", ExitInst: " << *Exit << "\n"; } } while (false) | ||||
210 | << ", ExitInst: " << *Exit << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "LV: Found an ordered reduction: Phi: " << *Phi << ", ExitInst: " << *Exit << "\n"; } } while (false); | ||||
211 | |||||
212 | return true; | ||||
213 | } | ||||
214 | |||||
215 | bool RecurrenceDescriptor::AddReductionVar( | ||||
216 | PHINode *Phi, RecurKind Kind, Loop *TheLoop, FastMathFlags FuncFMF, | ||||
217 | RecurrenceDescriptor &RedDes, DemandedBits *DB, AssumptionCache *AC, | ||||
218 | DominatorTree *DT, ScalarEvolution *SE) { | ||||
219 | if (Phi->getNumIncomingValues() != 2) | ||||
220 | return false; | ||||
221 | |||||
222 | // Reduction variables are only found in the loop header block. | ||||
223 | if (Phi->getParent() != TheLoop->getHeader()) | ||||
224 | return false; | ||||
225 | |||||
226 | // Obtain the reduction start value from the value that comes from the loop | ||||
227 | // preheader. | ||||
228 | Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader()); | ||||
229 | |||||
230 | // ExitInstruction is the single value which is used outside the loop. | ||||
231 | // We only allow for a single reduction value to be used outside the loop. | ||||
232 | // This includes users of the reduction, variables (which form a cycle | ||||
233 | // which ends in the phi node). | ||||
234 | Instruction *ExitInstruction = nullptr; | ||||
235 | |||||
236 | // Variable to keep last visited store instruction. By the end of the | ||||
237 | // algorithm this variable will be either empty or having intermediate | ||||
238 | // reduction value stored in invariant address. | ||||
239 | StoreInst *IntermediateStore = nullptr; | ||||
240 | |||||
241 | // Indicates that we found a reduction operation in our scan. | ||||
242 | bool FoundReduxOp = false; | ||||
243 | |||||
244 | // We start with the PHI node and scan for all of the users of this | ||||
245 | // instruction. All users must be instructions that can be used as reduction | ||||
246 | // variables (such as ADD). We must have a single out-of-block user. The cycle | ||||
247 | // must include the original PHI. | ||||
248 | bool FoundStartPHI = false; | ||||
249 | |||||
250 | // To recognize min/max patterns formed by a icmp select sequence, we store | ||||
251 | // the number of instruction we saw from the recognized min/max pattern, | ||||
252 | // to make sure we only see exactly the two instructions. | ||||
253 | unsigned NumCmpSelectPatternInst = 0; | ||||
254 | InstDesc ReduxDesc(false, nullptr); | ||||
255 | |||||
256 | // Data used for determining if the recurrence has been type-promoted. | ||||
257 | Type *RecurrenceType = Phi->getType(); | ||||
258 | SmallPtrSet<Instruction *, 4> CastInsts; | ||||
259 | unsigned MinWidthCastToRecurrenceType; | ||||
260 | Instruction *Start = Phi; | ||||
261 | bool IsSigned = false; | ||||
262 | |||||
263 | SmallPtrSet<Instruction *, 8> VisitedInsts; | ||||
264 | SmallVector<Instruction *, 8> Worklist; | ||||
265 | |||||
266 | // Return early if the recurrence kind does not match the type of Phi. If the | ||||
267 | // recurrence kind is arithmetic, we attempt to look through AND operations | ||||
268 | // resulting from the type promotion performed by InstCombine. Vector | ||||
269 | // operations are not limited to the legal integer widths, so we may be able | ||||
270 | // to evaluate the reduction in the narrower width. | ||||
271 | if (RecurrenceType->isFloatingPointTy()) { | ||||
272 | if (!isFloatingPointRecurrenceKind(Kind)) | ||||
273 | return false; | ||||
274 | } else if (RecurrenceType->isIntegerTy()) { | ||||
275 | if (!isIntegerRecurrenceKind(Kind)) | ||||
276 | return false; | ||||
277 | if (!isMinMaxRecurrenceKind(Kind)) | ||||
278 | Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts); | ||||
279 | } else { | ||||
280 | // Pointer min/max may exist, but it is not supported as a reduction op. | ||||
281 | return false; | ||||
282 | } | ||||
283 | |||||
284 | Worklist.push_back(Start); | ||||
285 | VisitedInsts.insert(Start); | ||||
286 | |||||
287 | // Start with all flags set because we will intersect this with the reduction | ||||
288 | // flags from all the reduction operations. | ||||
289 | FastMathFlags FMF = FastMathFlags::getFast(); | ||||
290 | |||||
291 | // The first instruction in the use-def chain of the Phi node that requires | ||||
292 | // exact floating point operations. | ||||
293 | Instruction *ExactFPMathInst = nullptr; | ||||
294 | |||||
295 | // A value in the reduction can be used: | ||||
296 | // - By the reduction: | ||||
297 | // - Reduction operation: | ||||
298 | // - One use of reduction value (safe). | ||||
299 | // - Multiple use of reduction value (not safe). | ||||
300 | // - PHI: | ||||
301 | // - All uses of the PHI must be the reduction (safe). | ||||
302 | // - Otherwise, not safe. | ||||
303 | // - By instructions outside of the loop (safe). | ||||
304 | // * One value may have several outside users, but all outside | ||||
305 | // uses must be of the same value. | ||||
306 | // - By store instructions with a loop invariant address (safe with | ||||
307 | // the following restrictions): | ||||
308 | // * If there are several stores, all must have the same address. | ||||
309 | // * Final value should be stored in that loop invariant address. | ||||
310 | // - By an instruction that is not part of the reduction (not safe). | ||||
311 | // This is either: | ||||
312 | // * An instruction type other than PHI or the reduction operation. | ||||
313 | // * A PHI in the header other than the initial PHI. | ||||
314 | while (!Worklist.empty()) { | ||||
315 | Instruction *Cur = Worklist.pop_back_val(); | ||||
316 | |||||
317 | // Store instructions are allowed iff it is the store of the reduction | ||||
318 | // value to the same loop invariant memory location. | ||||
319 | if (auto *SI = dyn_cast<StoreInst>(Cur)) { | ||||
320 | if (!SE) { | ||||
321 | LLVM_DEBUG(dbgs() << "Store instructions are not processed without "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Store instructions are not processed without " << "Scalar Evolution Analysis\n"; } } while (false) | ||||
322 | << "Scalar Evolution Analysis\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Store instructions are not processed without " << "Scalar Evolution Analysis\n"; } } while (false); | ||||
323 | return false; | ||||
324 | } | ||||
325 | |||||
326 | const SCEV *PtrScev = SE->getSCEV(SI->getPointerOperand()); | ||||
327 | // Check it is the same address as previous stores | ||||
328 | if (IntermediateStore) { | ||||
329 | const SCEV *OtherScev = | ||||
330 | SE->getSCEV(IntermediateStore->getPointerOperand()); | ||||
331 | |||||
332 | if (OtherScev != PtrScev) { | ||||
333 | LLVM_DEBUG(dbgs() << "Storing reduction value to different addresses "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Storing reduction value to different addresses " << "inside the loop: " << *SI->getPointerOperand () << " and " << *IntermediateStore->getPointerOperand () << '\n'; } } while (false) | ||||
334 | << "inside the loop: " << *SI->getPointerOperand()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Storing reduction value to different addresses " << "inside the loop: " << *SI->getPointerOperand () << " and " << *IntermediateStore->getPointerOperand () << '\n'; } } while (false) | ||||
335 | << " and "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Storing reduction value to different addresses " << "inside the loop: " << *SI->getPointerOperand () << " and " << *IntermediateStore->getPointerOperand () << '\n'; } } while (false) | ||||
336 | << *IntermediateStore->getPointerOperand() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Storing reduction value to different addresses " << "inside the loop: " << *SI->getPointerOperand () << " and " << *IntermediateStore->getPointerOperand () << '\n'; } } while (false); | ||||
337 | return false; | ||||
338 | } | ||||
339 | } | ||||
340 | |||||
341 | // Check the pointer is loop invariant | ||||
342 | if (!SE->isLoopInvariant(PtrScev, TheLoop)) { | ||||
343 | LLVM_DEBUG(dbgs() << "Storing reduction value to non-uniform address "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Storing reduction value to non-uniform address " << "inside the loop: " << *SI->getPointerOperand () << '\n'; } } while (false) | ||||
344 | << "inside the loop: " << *SI->getPointerOperand()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Storing reduction value to non-uniform address " << "inside the loop: " << *SI->getPointerOperand () << '\n'; } } while (false) | ||||
345 | << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Storing reduction value to non-uniform address " << "inside the loop: " << *SI->getPointerOperand () << '\n'; } } while (false); | ||||
346 | return false; | ||||
347 | } | ||||
348 | |||||
349 | // IntermediateStore is always the last store in the loop. | ||||
350 | IntermediateStore = SI; | ||||
351 | continue; | ||||
352 | } | ||||
353 | |||||
354 | // No Users. | ||||
355 | // If the instruction has no users then this is a broken chain and can't be | ||||
356 | // a reduction variable. | ||||
357 | if (Cur->use_empty()) | ||||
358 | return false; | ||||
359 | |||||
360 | bool IsAPhi = isa<PHINode>(Cur); | ||||
361 | |||||
362 | // A header PHI use other than the original PHI. | ||||
363 | if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent()) | ||||
364 | return false; | ||||
365 | |||||
366 | // Reductions of instructions such as Div, and Sub is only possible if the | ||||
367 | // LHS is the reduction variable. | ||||
368 | if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) && | ||||
369 | !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) && | ||||
370 | !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0)))) | ||||
371 | return false; | ||||
372 | |||||
373 | // Any reduction instruction must be of one of the allowed kinds. We ignore | ||||
374 | // the starting value (the Phi or an AND instruction if the Phi has been | ||||
375 | // type-promoted). | ||||
376 | if (Cur != Start) { | ||||
377 | ReduxDesc = | ||||
378 | isRecurrenceInstr(TheLoop, Phi, Cur, Kind, ReduxDesc, FuncFMF); | ||||
379 | ExactFPMathInst = ExactFPMathInst == nullptr | ||||
380 | ? ReduxDesc.getExactFPMathInst() | ||||
381 | : ExactFPMathInst; | ||||
382 | if (!ReduxDesc.isRecurrence()) | ||||
383 | return false; | ||||
384 | // FIXME: FMF is allowed on phi, but propagation is not handled correctly. | ||||
385 | if (isa<FPMathOperator>(ReduxDesc.getPatternInst()) && !IsAPhi) { | ||||
386 | FastMathFlags CurFMF = ReduxDesc.getPatternInst()->getFastMathFlags(); | ||||
387 | if (auto *Sel = dyn_cast<SelectInst>(ReduxDesc.getPatternInst())) { | ||||
388 | // Accept FMF on either fcmp or select of a min/max idiom. | ||||
389 | // TODO: This is a hack to work-around the fact that FMF may not be | ||||
390 | // assigned/propagated correctly. If that problem is fixed or we | ||||
391 | // standardize on fmin/fmax via intrinsics, this can be removed. | ||||
392 | if (auto *FCmp = dyn_cast<FCmpInst>(Sel->getCondition())) | ||||
393 | CurFMF |= FCmp->getFastMathFlags(); | ||||
394 | } | ||||
395 | FMF &= CurFMF; | ||||
396 | } | ||||
397 | // Update this reduction kind if we matched a new instruction. | ||||
398 | // TODO: Can we eliminate the need for a 2nd InstDesc by keeping 'Kind' | ||||
399 | // state accurate while processing the worklist? | ||||
400 | if (ReduxDesc.getRecKind() != RecurKind::None) | ||||
401 | Kind = ReduxDesc.getRecKind(); | ||||
402 | } | ||||
403 | |||||
404 | bool IsASelect = isa<SelectInst>(Cur); | ||||
405 | |||||
406 | // A conditional reduction operation must only have 2 or less uses in | ||||
407 | // VisitedInsts. | ||||
408 | if (IsASelect && (Kind == RecurKind::FAdd || Kind == RecurKind::FMul) && | ||||
409 | hasMultipleUsesOf(Cur, VisitedInsts, 2)) | ||||
410 | return false; | ||||
411 | |||||
412 | // A reduction operation must only have one use of the reduction value. | ||||
413 | if (!IsAPhi && !IsASelect && !isMinMaxRecurrenceKind(Kind) && | ||||
414 | !isSelectCmpRecurrenceKind(Kind) && | ||||
415 | hasMultipleUsesOf(Cur, VisitedInsts, 1)) | ||||
416 | return false; | ||||
417 | |||||
418 | // All inputs to a PHI node must be a reduction value. | ||||
419 | if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts)) | ||||
420 | return false; | ||||
421 | |||||
422 | if ((isIntMinMaxRecurrenceKind(Kind) || Kind == RecurKind::SelectICmp) && | ||||
423 | (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur))) | ||||
424 | ++NumCmpSelectPatternInst; | ||||
425 | if ((isFPMinMaxRecurrenceKind(Kind) || Kind == RecurKind::SelectFCmp) && | ||||
426 | (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur))) | ||||
427 | ++NumCmpSelectPatternInst; | ||||
428 | |||||
429 | // Check whether we found a reduction operator. | ||||
430 | FoundReduxOp |= !IsAPhi && Cur != Start; | ||||
431 | |||||
432 | // Process users of current instruction. Push non-PHI nodes after PHI nodes | ||||
433 | // onto the stack. This way we are going to have seen all inputs to PHI | ||||
434 | // nodes once we get to them. | ||||
435 | SmallVector<Instruction *, 8> NonPHIs; | ||||
436 | SmallVector<Instruction *, 8> PHIs; | ||||
437 | for (User *U : Cur->users()) { | ||||
438 | Instruction *UI = cast<Instruction>(U); | ||||
439 | |||||
440 | // If the user is a call to llvm.fmuladd then the instruction can only be | ||||
441 | // the final operand. | ||||
442 | if (isFMulAddIntrinsic(UI)) | ||||
443 | if (Cur == UI->getOperand(0) || Cur == UI->getOperand(1)) | ||||
444 | return false; | ||||
445 | |||||
446 | // Check if we found the exit user. | ||||
447 | BasicBlock *Parent = UI->getParent(); | ||||
448 | if (!TheLoop->contains(Parent)) { | ||||
449 | // If we already know this instruction is used externally, move on to | ||||
450 | // the next user. | ||||
451 | if (ExitInstruction == Cur) | ||||
452 | continue; | ||||
453 | |||||
454 | // Exit if you find multiple values used outside or if the header phi | ||||
455 | // node is being used. In this case the user uses the value of the | ||||
456 | // previous iteration, in which case we would loose "VF-1" iterations of | ||||
457 | // the reduction operation if we vectorize. | ||||
458 | if (ExitInstruction != nullptr || Cur == Phi) | ||||
459 | return false; | ||||
460 | |||||
461 | // The instruction used by an outside user must be the last instruction | ||||
462 | // before we feed back to the reduction phi. Otherwise, we loose VF-1 | ||||
463 | // operations on the value. | ||||
464 | if (!is_contained(Phi->operands(), Cur)) | ||||
465 | return false; | ||||
466 | |||||
467 | ExitInstruction = Cur; | ||||
468 | continue; | ||||
469 | } | ||||
470 | |||||
471 | // Process instructions only once (termination). Each reduction cycle | ||||
472 | // value must only be used once, except by phi nodes and min/max | ||||
473 | // reductions which are represented as a cmp followed by a select. | ||||
474 | InstDesc IgnoredVal(false, nullptr); | ||||
475 | if (VisitedInsts.insert(UI).second) { | ||||
476 | if (isa<PHINode>(UI)) { | ||||
477 | PHIs.push_back(UI); | ||||
478 | } else { | ||||
479 | StoreInst *SI = dyn_cast<StoreInst>(UI); | ||||
480 | if (SI && SI->getPointerOperand() == Cur) { | ||||
481 | // Reduction variable chain can only be stored somewhere but it | ||||
482 | // can't be used as an address. | ||||
483 | return false; | ||||
484 | } | ||||
485 | NonPHIs.push_back(UI); | ||||
486 | } | ||||
487 | } else if (!isa<PHINode>(UI) && | ||||
488 | ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) && | ||||
489 | !isa<SelectInst>(UI)) || | ||||
490 | (!isConditionalRdxPattern(Kind, UI).isRecurrence() && | ||||
491 | !isSelectCmpPattern(TheLoop, Phi, UI, IgnoredVal) | ||||
492 | .isRecurrence() && | ||||
493 | !isMinMaxPattern(UI, Kind, IgnoredVal).isRecurrence()))) | ||||
494 | return false; | ||||
495 | |||||
496 | // Remember that we completed the cycle. | ||||
497 | if (UI == Phi) | ||||
498 | FoundStartPHI = true; | ||||
499 | } | ||||
500 | Worklist.append(PHIs.begin(), PHIs.end()); | ||||
501 | Worklist.append(NonPHIs.begin(), NonPHIs.end()); | ||||
502 | } | ||||
503 | |||||
504 | // This means we have seen one but not the other instruction of the | ||||
505 | // pattern or more than just a select and cmp. Zero implies that we saw a | ||||
506 | // llvm.min/max intrinsic, which is always OK. | ||||
507 | if (isMinMaxRecurrenceKind(Kind) && NumCmpSelectPatternInst != 2 && | ||||
508 | NumCmpSelectPatternInst != 0) | ||||
509 | return false; | ||||
510 | |||||
511 | if (isSelectCmpRecurrenceKind(Kind) && NumCmpSelectPatternInst != 1) | ||||
512 | return false; | ||||
513 | |||||
514 | if (IntermediateStore) { | ||||
515 | // Check that stored value goes to the phi node again. This way we make sure | ||||
516 | // that the value stored in IntermediateStore is indeed the final reduction | ||||
517 | // value. | ||||
518 | if (!is_contained(Phi->operands(), IntermediateStore->getValueOperand())) { | ||||
519 | LLVM_DEBUG(dbgs() << "Not a final reduction value stored: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Not a final reduction value stored: " << *IntermediateStore << '\n'; } } while (false) | ||||
520 | << *IntermediateStore << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Not a final reduction value stored: " << *IntermediateStore << '\n'; } } while (false); | ||||
521 | return false; | ||||
522 | } | ||||
523 | |||||
524 | // If there is an exit instruction it's value should be stored in | ||||
525 | // IntermediateStore | ||||
526 | if (ExitInstruction && | ||||
527 | IntermediateStore->getValueOperand() != ExitInstruction) { | ||||
528 | LLVM_DEBUG(dbgs() << "Last store Instruction of reduction value does not "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Last store Instruction of reduction value does not " "store last calculated value of the reduction: " << *IntermediateStore << '\n'; } } while (false) | ||||
529 | "store last calculated value of the reduction: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Last store Instruction of reduction value does not " "store last calculated value of the reduction: " << *IntermediateStore << '\n'; } } while (false) | ||||
530 | << *IntermediateStore << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Last store Instruction of reduction value does not " "store last calculated value of the reduction: " << *IntermediateStore << '\n'; } } while (false); | ||||
531 | return false; | ||||
532 | } | ||||
533 | |||||
534 | // If all uses are inside the loop (intermediate stores), then the | ||||
535 | // reduction value after the loop will be the one used in the last store. | ||||
536 | if (!ExitInstruction) | ||||
537 | ExitInstruction = cast<Instruction>(IntermediateStore->getValueOperand()); | ||||
538 | } | ||||
539 | |||||
540 | if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction) | ||||
541 | return false; | ||||
542 | |||||
543 | const bool IsOrdered = | ||||
544 | checkOrderedReduction(Kind, ExactFPMathInst, ExitInstruction, Phi); | ||||
545 | |||||
546 | if (Start != Phi) { | ||||
547 | // If the starting value is not the same as the phi node, we speculatively | ||||
548 | // looked through an 'and' instruction when evaluating a potential | ||||
549 | // arithmetic reduction to determine if it may have been type-promoted. | ||||
550 | // | ||||
551 | // We now compute the minimal bit width that is required to represent the | ||||
552 | // reduction. If this is the same width that was indicated by the 'and', we | ||||
553 | // can represent the reduction in the smaller type. The 'and' instruction | ||||
554 | // will be eliminated since it will essentially be a cast instruction that | ||||
555 | // can be ignore in the cost model. If we compute a different type than we | ||||
556 | // did when evaluating the 'and', the 'and' will not be eliminated, and we | ||||
557 | // will end up with different kinds of operations in the recurrence | ||||
558 | // expression (e.g., IntegerAND, IntegerADD). We give up if this is | ||||
559 | // the case. | ||||
560 | // | ||||
561 | // The vectorizer relies on InstCombine to perform the actual | ||||
562 | // type-shrinking. It does this by inserting instructions to truncate the | ||||
563 | // exit value of the reduction to the width indicated by RecurrenceType and | ||||
564 | // then extend this value back to the original width. If IsSigned is false, | ||||
565 | // a 'zext' instruction will be generated; otherwise, a 'sext' will be | ||||
566 | // used. | ||||
567 | // | ||||
568 | // TODO: We should not rely on InstCombine to rewrite the reduction in the | ||||
569 | // smaller type. We should just generate a correctly typed expression | ||||
570 | // to begin with. | ||||
571 | Type *ComputedType; | ||||
572 | std::tie(ComputedType, IsSigned) = | ||||
573 | computeRecurrenceType(ExitInstruction, DB, AC, DT); | ||||
574 | if (ComputedType != RecurrenceType) | ||||
575 | return false; | ||||
576 | } | ||||
577 | |||||
578 | // Collect cast instructions and the minimum width used by the recurrence. | ||||
579 | // If the starting value is not the same as the phi node and the computed | ||||
580 | // recurrence type is equal to the recurrence type, the recurrence expression | ||||
581 | // will be represented in a narrower or wider type. If there are any cast | ||||
582 | // instructions that will be unnecessary, collect them in CastsFromRecurTy. | ||||
583 | // Note that the 'and' instruction was already included in this list. | ||||
584 | // | ||||
585 | // TODO: A better way to represent this may be to tag in some way all the | ||||
586 | // instructions that are a part of the reduction. The vectorizer cost | ||||
587 | // model could then apply the recurrence type to these instructions, | ||||
588 | // without needing a white list of instructions to ignore. | ||||
589 | // This may also be useful for the inloop reductions, if it can be | ||||
590 | // kept simple enough. | ||||
591 | collectCastInstrs(TheLoop, ExitInstruction, RecurrenceType, CastInsts, | ||||
592 | MinWidthCastToRecurrenceType); | ||||
593 | |||||
594 | // We found a reduction var if we have reached the original phi node and we | ||||
595 | // only have a single instruction with out-of-loop users. | ||||
596 | |||||
597 | // The ExitInstruction(Instruction which is allowed to have out-of-loop users) | ||||
598 | // is saved as part of the RecurrenceDescriptor. | ||||
599 | |||||
600 | // Save the description of this reduction variable. | ||||
601 | RecurrenceDescriptor RD(RdxStart, ExitInstruction, IntermediateStore, Kind, | ||||
602 | FMF, ExactFPMathInst, RecurrenceType, IsSigned, | ||||
603 | IsOrdered, CastInsts, MinWidthCastToRecurrenceType); | ||||
604 | RedDes = RD; | ||||
605 | |||||
606 | return true; | ||||
607 | } | ||||
608 | |||||
609 | // We are looking for loops that do something like this: | ||||
610 | // int r = 0; | ||||
611 | // for (int i = 0; i < n; i++) { | ||||
612 | // if (src[i] > 3) | ||||
613 | // r = 3; | ||||
614 | // } | ||||
615 | // where the reduction value (r) only has two states, in this example 0 or 3. | ||||
616 | // The generated LLVM IR for this type of loop will be like this: | ||||
617 | // for.body: | ||||
618 | // %r = phi i32 [ %spec.select, %for.body ], [ 0, %entry ] | ||||
619 | // ... | ||||
620 | // %cmp = icmp sgt i32 %5, 3 | ||||
621 | // %spec.select = select i1 %cmp, i32 3, i32 %r | ||||
622 | // ... | ||||
623 | // In general we can support vectorization of loops where 'r' flips between | ||||
624 | // any two non-constants, provided they are loop invariant. The only thing | ||||
625 | // we actually care about at the end of the loop is whether or not any lane | ||||
626 | // in the selected vector is different from the start value. The final | ||||
627 | // across-vector reduction after the loop simply involves choosing the start | ||||
628 | // value if nothing changed (0 in the example above) or the other selected | ||||
629 | // value (3 in the example above). | ||||
630 | RecurrenceDescriptor::InstDesc | ||||
631 | RecurrenceDescriptor::isSelectCmpPattern(Loop *Loop, PHINode *OrigPhi, | ||||
632 | Instruction *I, InstDesc &Prev) { | ||||
633 | // We must handle the select(cmp(),x,y) as a single instruction. Advance to | ||||
634 | // the select. | ||||
635 | CmpInst::Predicate Pred; | ||||
636 | if (match(I, m_OneUse(m_Cmp(Pred, m_Value(), m_Value())))) { | ||||
637 | if (auto *Select = dyn_cast<SelectInst>(*I->user_begin())) | ||||
638 | return InstDesc(Select, Prev.getRecKind()); | ||||
639 | } | ||||
640 | |||||
641 | // Only match select with single use cmp condition. | ||||
642 | if (!match(I, m_Select(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), m_Value(), | ||||
643 | m_Value()))) | ||||
644 | return InstDesc(false, I); | ||||
645 | |||||
646 | SelectInst *SI = cast<SelectInst>(I); | ||||
647 | Value *NonPhi = nullptr; | ||||
648 | |||||
649 | if (OrigPhi == dyn_cast<PHINode>(SI->getTrueValue())) | ||||
650 | NonPhi = SI->getFalseValue(); | ||||
651 | else if (OrigPhi == dyn_cast<PHINode>(SI->getFalseValue())) | ||||
652 | NonPhi = SI->getTrueValue(); | ||||
653 | else | ||||
654 | return InstDesc(false, I); | ||||
655 | |||||
656 | // We are looking for selects of the form: | ||||
657 | // select(cmp(), phi, loop_invariant) or | ||||
658 | // select(cmp(), loop_invariant, phi) | ||||
659 | if (!Loop->isLoopInvariant(NonPhi)) | ||||
660 | return InstDesc(false, I); | ||||
661 | |||||
662 | return InstDesc(I, isa<ICmpInst>(I->getOperand(0)) ? RecurKind::SelectICmp | ||||
663 | : RecurKind::SelectFCmp); | ||||
664 | } | ||||
665 | |||||
666 | RecurrenceDescriptor::InstDesc | ||||
667 | RecurrenceDescriptor::isMinMaxPattern(Instruction *I, RecurKind Kind, | ||||
668 | const InstDesc &Prev) { | ||||
669 | assert((isa<CmpInst>(I) || isa<SelectInst>(I) || isa<CallInst>(I)) &&(static_cast <bool> ((isa<CmpInst>(I) || isa<SelectInst >(I) || isa<CallInst>(I)) && "Expected a cmp or select or call instruction" ) ? void (0) : __assert_fail ("(isa<CmpInst>(I) || isa<SelectInst>(I) || isa<CallInst>(I)) && \"Expected a cmp or select or call instruction\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 670, __extension__ __PRETTY_FUNCTION__ )) | ||||
670 | "Expected a cmp or select or call instruction")(static_cast <bool> ((isa<CmpInst>(I) || isa<SelectInst >(I) || isa<CallInst>(I)) && "Expected a cmp or select or call instruction" ) ? void (0) : __assert_fail ("(isa<CmpInst>(I) || isa<SelectInst>(I) || isa<CallInst>(I)) && \"Expected a cmp or select or call instruction\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 670, __extension__ __PRETTY_FUNCTION__ )); | ||||
671 | if (!isMinMaxRecurrenceKind(Kind)) | ||||
672 | return InstDesc(false, I); | ||||
673 | |||||
674 | // We must handle the select(cmp()) as a single instruction. Advance to the | ||||
675 | // select. | ||||
676 | CmpInst::Predicate Pred; | ||||
677 | if (match(I, m_OneUse(m_Cmp(Pred, m_Value(), m_Value())))) { | ||||
678 | if (auto *Select = dyn_cast<SelectInst>(*I->user_begin())) | ||||
679 | return InstDesc(Select, Prev.getRecKind()); | ||||
680 | } | ||||
681 | |||||
682 | // Only match select with single use cmp condition, or a min/max intrinsic. | ||||
683 | if (!isa<IntrinsicInst>(I) && | ||||
684 | !match(I, m_Select(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), m_Value(), | ||||
685 | m_Value()))) | ||||
686 | return InstDesc(false, I); | ||||
687 | |||||
688 | // Look for a min/max pattern. | ||||
689 | if (match(I, m_UMin(m_Value(), m_Value()))) | ||||
690 | return InstDesc(Kind == RecurKind::UMin, I); | ||||
691 | if (match(I, m_UMax(m_Value(), m_Value()))) | ||||
692 | return InstDesc(Kind == RecurKind::UMax, I); | ||||
693 | if (match(I, m_SMax(m_Value(), m_Value()))) | ||||
694 | return InstDesc(Kind == RecurKind::SMax, I); | ||||
695 | if (match(I, m_SMin(m_Value(), m_Value()))) | ||||
696 | return InstDesc(Kind == RecurKind::SMin, I); | ||||
697 | if (match(I, m_OrdFMin(m_Value(), m_Value()))) | ||||
698 | return InstDesc(Kind == RecurKind::FMin, I); | ||||
699 | if (match(I, m_OrdFMax(m_Value(), m_Value()))) | ||||
700 | return InstDesc(Kind == RecurKind::FMax, I); | ||||
701 | if (match(I, m_UnordFMin(m_Value(), m_Value()))) | ||||
702 | return InstDesc(Kind == RecurKind::FMin, I); | ||||
703 | if (match(I, m_UnordFMax(m_Value(), m_Value()))) | ||||
704 | return InstDesc(Kind == RecurKind::FMax, I); | ||||
705 | if (match(I, m_Intrinsic<Intrinsic::minnum>(m_Value(), m_Value()))) | ||||
706 | return InstDesc(Kind == RecurKind::FMin, I); | ||||
707 | if (match(I, m_Intrinsic<Intrinsic::maxnum>(m_Value(), m_Value()))) | ||||
708 | return InstDesc(Kind == RecurKind::FMax, I); | ||||
709 | |||||
710 | return InstDesc(false, I); | ||||
711 | } | ||||
712 | |||||
713 | /// Returns true if the select instruction has users in the compare-and-add | ||||
714 | /// reduction pattern below. The select instruction argument is the last one | ||||
715 | /// in the sequence. | ||||
716 | /// | ||||
717 | /// %sum.1 = phi ... | ||||
718 | /// ... | ||||
719 | /// %cmp = fcmp pred %0, %CFP | ||||
720 | /// %add = fadd %0, %sum.1 | ||||
721 | /// %sum.2 = select %cmp, %add, %sum.1 | ||||
722 | RecurrenceDescriptor::InstDesc | ||||
723 | RecurrenceDescriptor::isConditionalRdxPattern(RecurKind Kind, Instruction *I) { | ||||
724 | SelectInst *SI = dyn_cast<SelectInst>(I); | ||||
725 | if (!SI) | ||||
726 | return InstDesc(false, I); | ||||
727 | |||||
728 | CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition()); | ||||
729 | // Only handle single use cases for now. | ||||
730 | if (!CI || !CI->hasOneUse()) | ||||
731 | return InstDesc(false, I); | ||||
732 | |||||
733 | Value *TrueVal = SI->getTrueValue(); | ||||
734 | Value *FalseVal = SI->getFalseValue(); | ||||
735 | // Handle only when either of operands of select instruction is a PHI | ||||
736 | // node for now. | ||||
737 | if ((isa<PHINode>(*TrueVal) && isa<PHINode>(*FalseVal)) || | ||||
738 | (!isa<PHINode>(*TrueVal) && !isa<PHINode>(*FalseVal))) | ||||
739 | return InstDesc(false, I); | ||||
740 | |||||
741 | Instruction *I1 = | ||||
742 | isa<PHINode>(*TrueVal) ? dyn_cast<Instruction>(FalseVal) | ||||
743 | : dyn_cast<Instruction>(TrueVal); | ||||
744 | if (!I1 || !I1->isBinaryOp()) | ||||
745 | return InstDesc(false, I); | ||||
746 | |||||
747 | Value *Op1, *Op2; | ||||
748 | if (!(((m_FAdd(m_Value(Op1), m_Value(Op2)).match(I1) || | ||||
749 | m_FSub(m_Value(Op1), m_Value(Op2)).match(I1)) && | ||||
750 | I1->isFast()) || | ||||
751 | (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1) && (I1->isFast())) || | ||||
752 | ((m_Add(m_Value(Op1), m_Value(Op2)).match(I1) || | ||||
753 | m_Sub(m_Value(Op1), m_Value(Op2)).match(I1))) || | ||||
754 | (m_Mul(m_Value(Op1), m_Value(Op2)).match(I1)))) | ||||
755 | return InstDesc(false, I); | ||||
756 | |||||
757 | Instruction *IPhi = isa<PHINode>(*Op1) ? dyn_cast<Instruction>(Op1) | ||||
758 | : dyn_cast<Instruction>(Op2); | ||||
759 | if (!IPhi || IPhi != FalseVal) | ||||
760 | return InstDesc(false, I); | ||||
761 | |||||
762 | return InstDesc(true, SI); | ||||
763 | } | ||||
764 | |||||
765 | RecurrenceDescriptor::InstDesc | ||||
766 | RecurrenceDescriptor::isRecurrenceInstr(Loop *L, PHINode *OrigPhi, | ||||
767 | Instruction *I, RecurKind Kind, | ||||
768 | InstDesc &Prev, FastMathFlags FuncFMF) { | ||||
769 | assert(Prev.getRecKind() == RecurKind::None || Prev.getRecKind() == Kind)(static_cast <bool> (Prev.getRecKind() == RecurKind::None || Prev.getRecKind() == Kind) ? void (0) : __assert_fail ("Prev.getRecKind() == RecurKind::None || Prev.getRecKind() == Kind" , "llvm/lib/Analysis/IVDescriptors.cpp", 769, __extension__ __PRETTY_FUNCTION__ )); | ||||
770 | switch (I->getOpcode()) { | ||||
771 | default: | ||||
772 | return InstDesc(false, I); | ||||
773 | case Instruction::PHI: | ||||
774 | return InstDesc(I, Prev.getRecKind(), Prev.getExactFPMathInst()); | ||||
775 | case Instruction::Sub: | ||||
776 | case Instruction::Add: | ||||
777 | return InstDesc(Kind == RecurKind::Add, I); | ||||
778 | case Instruction::Mul: | ||||
779 | return InstDesc(Kind == RecurKind::Mul, I); | ||||
780 | case Instruction::And: | ||||
781 | return InstDesc(Kind == RecurKind::And, I); | ||||
782 | case Instruction::Or: | ||||
783 | return InstDesc(Kind == RecurKind::Or, I); | ||||
784 | case Instruction::Xor: | ||||
785 | return InstDesc(Kind == RecurKind::Xor, I); | ||||
786 | case Instruction::FDiv: | ||||
787 | case Instruction::FMul: | ||||
788 | return InstDesc(Kind == RecurKind::FMul, I, | ||||
789 | I->hasAllowReassoc() ? nullptr : I); | ||||
790 | case Instruction::FSub: | ||||
791 | case Instruction::FAdd: | ||||
792 | return InstDesc(Kind == RecurKind::FAdd, I, | ||||
793 | I->hasAllowReassoc() ? nullptr : I); | ||||
794 | case Instruction::Select: | ||||
795 | if (Kind == RecurKind::FAdd || Kind == RecurKind::FMul || | ||||
796 | Kind == RecurKind::Add || Kind == RecurKind::Mul) | ||||
797 | return isConditionalRdxPattern(Kind, I); | ||||
798 | [[fallthrough]]; | ||||
799 | case Instruction::FCmp: | ||||
800 | case Instruction::ICmp: | ||||
801 | case Instruction::Call: | ||||
802 | if (isSelectCmpRecurrenceKind(Kind)) | ||||
803 | return isSelectCmpPattern(L, OrigPhi, I, Prev); | ||||
804 | if (isIntMinMaxRecurrenceKind(Kind) || | ||||
805 | (((FuncFMF.noNaNs() && FuncFMF.noSignedZeros()) || | ||||
806 | (isa<FPMathOperator>(I) && I->hasNoNaNs() && | ||||
807 | I->hasNoSignedZeros())) && | ||||
808 | isFPMinMaxRecurrenceKind(Kind))) | ||||
809 | return isMinMaxPattern(I, Kind, Prev); | ||||
810 | else if (isFMulAddIntrinsic(I)) | ||||
811 | return InstDesc(Kind == RecurKind::FMulAdd, I, | ||||
812 | I->hasAllowReassoc() ? nullptr : I); | ||||
813 | return InstDesc(false, I); | ||||
814 | } | ||||
815 | } | ||||
816 | |||||
817 | bool RecurrenceDescriptor::hasMultipleUsesOf( | ||||
818 | Instruction *I, SmallPtrSetImpl<Instruction *> &Insts, | ||||
819 | unsigned MaxNumUses) { | ||||
820 | unsigned NumUses = 0; | ||||
821 | for (const Use &U : I->operands()) { | ||||
822 | if (Insts.count(dyn_cast<Instruction>(U))) | ||||
823 | ++NumUses; | ||||
824 | if (NumUses > MaxNumUses) | ||||
825 | return true; | ||||
826 | } | ||||
827 | |||||
828 | return false; | ||||
829 | } | ||||
830 | |||||
831 | bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop, | ||||
832 | RecurrenceDescriptor &RedDes, | ||||
833 | DemandedBits *DB, AssumptionCache *AC, | ||||
834 | DominatorTree *DT, | ||||
835 | ScalarEvolution *SE) { | ||||
836 | BasicBlock *Header = TheLoop->getHeader(); | ||||
837 | Function &F = *Header->getParent(); | ||||
838 | FastMathFlags FMF; | ||||
839 | FMF.setNoNaNs( | ||||
840 | F.getFnAttribute("no-nans-fp-math").getValueAsBool()); | ||||
841 | FMF.setNoSignedZeros( | ||||
842 | F.getFnAttribute("no-signed-zeros-fp-math").getValueAsBool()); | ||||
843 | |||||
844 | if (AddReductionVar(Phi, RecurKind::Add, TheLoop, FMF, RedDes, DB, AC, DT, | ||||
845 | SE)) { | ||||
846 | LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found an ADD reduction PHI." << *Phi << "\n"; } } while (false); | ||||
847 | return true; | ||||
848 | } | ||||
849 | if (AddReductionVar(Phi, RecurKind::Mul, TheLoop, FMF, RedDes, DB, AC, DT, | ||||
850 | SE)) { | ||||
851 | LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found a MUL reduction PHI." << *Phi << "\n"; } } while (false); | ||||
852 | return true; | ||||
853 | } | ||||
854 | if (AddReductionVar(Phi, RecurKind::Or, TheLoop, FMF, RedDes, DB, AC, DT, | ||||
855 | SE)) { | ||||
856 | LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found an OR reduction PHI." << *Phi << "\n"; } } while (false); | ||||
857 | return true; | ||||
858 | } | ||||
859 | if (AddReductionVar(Phi, RecurKind::And, TheLoop, FMF, RedDes, DB, AC, DT, | ||||
860 | SE)) { | ||||
861 | LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found an AND reduction PHI." << *Phi << "\n"; } } while (false); | ||||
862 | return true; | ||||
863 | } | ||||
864 | if (AddReductionVar(Phi, RecurKind::Xor, TheLoop, FMF, RedDes, DB, AC, DT, | ||||
865 | SE)) { | ||||
866 | LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found a XOR reduction PHI." << *Phi << "\n"; } } while (false); | ||||
867 | return true; | ||||
868 | } | ||||
869 | if (AddReductionVar(Phi, RecurKind::SMax, TheLoop, FMF, RedDes, DB, AC, DT, | ||||
870 | SE)) { | ||||
871 | LLVM_DEBUG(dbgs() << "Found a SMAX reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found a SMAX reduction PHI." << *Phi << "\n"; } } while (false); | ||||
872 | return true; | ||||
873 | } | ||||
874 | if (AddReductionVar(Phi, RecurKind::SMin, TheLoop, FMF, RedDes, DB, AC, DT, | ||||
875 | SE)) { | ||||
876 | LLVM_DEBUG(dbgs() << "Found a SMIN reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found a SMIN reduction PHI." << *Phi << "\n"; } } while (false); | ||||
877 | return true; | ||||
878 | } | ||||
879 | if (AddReductionVar(Phi, RecurKind::UMax, TheLoop, FMF, RedDes, DB, AC, DT, | ||||
880 | SE)) { | ||||
881 | LLVM_DEBUG(dbgs() << "Found a UMAX reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found a UMAX reduction PHI." << *Phi << "\n"; } } while (false); | ||||
882 | return true; | ||||
883 | } | ||||
884 | if (AddReductionVar(Phi, RecurKind::UMin, TheLoop, FMF, RedDes, DB, AC, DT, | ||||
885 | SE)) { | ||||
886 | LLVM_DEBUG(dbgs() << "Found a UMIN reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found a UMIN reduction PHI." << *Phi << "\n"; } } while (false); | ||||
887 | return true; | ||||
888 | } | ||||
889 | if (AddReductionVar(Phi, RecurKind::SelectICmp, TheLoop, FMF, RedDes, DB, AC, | ||||
890 | DT, SE)) { | ||||
891 | LLVM_DEBUG(dbgs() << "Found an integer conditional select reduction PHI."do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found an integer conditional select reduction PHI." << *Phi << "\n"; } } while (false) | ||||
892 | << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found an integer conditional select reduction PHI." << *Phi << "\n"; } } while (false); | ||||
893 | return true; | ||||
894 | } | ||||
895 | if (AddReductionVar(Phi, RecurKind::FMul, TheLoop, FMF, RedDes, DB, AC, DT, | ||||
896 | SE)) { | ||||
897 | LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found an FMult reduction PHI." << *Phi << "\n"; } } while (false); | ||||
898 | return true; | ||||
899 | } | ||||
900 | if (AddReductionVar(Phi, RecurKind::FAdd, TheLoop, FMF, RedDes, DB, AC, DT, | ||||
901 | SE)) { | ||||
902 | LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n"; } } while (false); | ||||
903 | return true; | ||||
904 | } | ||||
905 | if (AddReductionVar(Phi, RecurKind::FMax, TheLoop, FMF, RedDes, DB, AC, DT, | ||||
906 | SE)) { | ||||
907 | LLVM_DEBUG(dbgs() << "Found a float MAX reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found a float MAX reduction PHI." << *Phi << "\n"; } } while (false); | ||||
908 | return true; | ||||
909 | } | ||||
910 | if (AddReductionVar(Phi, RecurKind::FMin, TheLoop, FMF, RedDes, DB, AC, DT, | ||||
911 | SE)) { | ||||
912 | LLVM_DEBUG(dbgs() << "Found a float MIN reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found a float MIN reduction PHI." << *Phi << "\n"; } } while (false); | ||||
913 | return true; | ||||
914 | } | ||||
915 | if (AddReductionVar(Phi, RecurKind::SelectFCmp, TheLoop, FMF, RedDes, DB, AC, | ||||
916 | DT, SE)) { | ||||
917 | LLVM_DEBUG(dbgs() << "Found a float conditional select reduction PHI."do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found a float conditional select reduction PHI." << " PHI." << *Phi << "\n"; } } while (false ) | ||||
918 | << " PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found a float conditional select reduction PHI." << " PHI." << *Phi << "\n"; } } while (false ); | ||||
919 | return true; | ||||
920 | } | ||||
921 | if (AddReductionVar(Phi, RecurKind::FMulAdd, TheLoop, FMF, RedDes, DB, AC, DT, | ||||
922 | SE)) { | ||||
923 | LLVM_DEBUG(dbgs() << "Found an FMulAdd reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "Found an FMulAdd reduction PHI." << *Phi << "\n"; } } while (false); | ||||
924 | return true; | ||||
925 | } | ||||
926 | // Not a reduction of known type. | ||||
927 | return false; | ||||
928 | } | ||||
929 | |||||
930 | bool RecurrenceDescriptor::isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop, | ||||
931 | DominatorTree *DT) { | ||||
932 | |||||
933 | // Ensure the phi node is in the loop header and has two incoming values. | ||||
934 | if (Phi->getParent() != TheLoop->getHeader() || | ||||
935 | Phi->getNumIncomingValues() != 2) | ||||
936 | return false; | ||||
937 | |||||
938 | // Ensure the loop has a preheader and a single latch block. The loop | ||||
939 | // vectorizer will need the latch to set up the next iteration of the loop. | ||||
940 | auto *Preheader = TheLoop->getLoopPreheader(); | ||||
941 | auto *Latch = TheLoop->getLoopLatch(); | ||||
942 | if (!Preheader || !Latch) | ||||
943 | return false; | ||||
944 | |||||
945 | // Ensure the phi node's incoming blocks are the loop preheader and latch. | ||||
946 | if (Phi->getBasicBlockIndex(Preheader) < 0 || | ||||
947 | Phi->getBasicBlockIndex(Latch) < 0) | ||||
948 | return false; | ||||
949 | |||||
950 | // Get the previous value. The previous value comes from the latch edge while | ||||
951 | // the initial value comes from the preheader edge. | ||||
952 | auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch)); | ||||
953 | |||||
954 | // If Previous is a phi in the header, go through incoming values from the | ||||
955 | // latch until we find a non-phi value. Use this as the new Previous, all uses | ||||
956 | // in the header will be dominated by the original phi, but need to be moved | ||||
957 | // after the non-phi previous value. | ||||
958 | SmallPtrSet<PHINode *, 4> SeenPhis; | ||||
959 | while (auto *PrevPhi = dyn_cast_or_null<PHINode>(Previous)) { | ||||
960 | if (PrevPhi->getParent() != Phi->getParent()) | ||||
961 | return false; | ||||
962 | if (!SeenPhis.insert(PrevPhi).second) | ||||
963 | return false; | ||||
964 | Previous = dyn_cast<Instruction>(PrevPhi->getIncomingValueForBlock(Latch)); | ||||
965 | } | ||||
966 | |||||
967 | if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous)) | ||||
968 | return false; | ||||
969 | |||||
970 | // Ensure every user of the phi node (recursively) is dominated by the | ||||
971 | // previous value. The dominance requirement ensures the loop vectorizer will | ||||
972 | // not need to vectorize the initial value prior to the first iteration of the | ||||
973 | // loop. | ||||
974 | // TODO: Consider extending this sinking to handle memory instructions. | ||||
975 | |||||
976 | SmallPtrSet<Value *, 8> Seen; | ||||
977 | BasicBlock *PhiBB = Phi->getParent(); | ||||
978 | SmallVector<Instruction *, 8> WorkList; | ||||
979 | auto TryToPushSinkCandidate = [&](Instruction *SinkCandidate) { | ||||
980 | // Cyclic dependence. | ||||
981 | if (Previous == SinkCandidate) | ||||
982 | return false; | ||||
983 | |||||
984 | if (!Seen.insert(SinkCandidate).second) | ||||
985 | return true; | ||||
986 | if (DT->dominates(Previous, | ||||
987 | SinkCandidate)) // We already are good w/o sinking. | ||||
988 | return true; | ||||
989 | |||||
990 | if (SinkCandidate->getParent() != PhiBB || | ||||
991 | SinkCandidate->mayHaveSideEffects() || | ||||
992 | SinkCandidate->mayReadFromMemory() || SinkCandidate->isTerminator()) | ||||
993 | return false; | ||||
994 | |||||
995 | // If we reach a PHI node that is not dominated by Previous, we reached a | ||||
996 | // header PHI. No need for sinking. | ||||
997 | if (isa<PHINode>(SinkCandidate)) | ||||
998 | return true; | ||||
999 | |||||
1000 | // Sink User tentatively and check its users | ||||
1001 | WorkList.push_back(SinkCandidate); | ||||
1002 | return true; | ||||
1003 | }; | ||||
1004 | |||||
1005 | WorkList.push_back(Phi); | ||||
1006 | // Try to recursively sink instructions and their users after Previous. | ||||
1007 | while (!WorkList.empty()) { | ||||
1008 | Instruction *Current = WorkList.pop_back_val(); | ||||
1009 | for (User *User : Current->users()) { | ||||
1010 | if (!TryToPushSinkCandidate(cast<Instruction>(User))) | ||||
1011 | return false; | ||||
1012 | } | ||||
1013 | } | ||||
1014 | |||||
1015 | return true; | ||||
1016 | } | ||||
1017 | |||||
1018 | /// This function returns the identity element (or neutral element) for | ||||
1019 | /// the operation K. | ||||
1020 | Value *RecurrenceDescriptor::getRecurrenceIdentity(RecurKind K, Type *Tp, | ||||
1021 | FastMathFlags FMF) const { | ||||
1022 | switch (K) { | ||||
1023 | case RecurKind::Xor: | ||||
1024 | case RecurKind::Add: | ||||
1025 | case RecurKind::Or: | ||||
1026 | // Adding, Xoring, Oring zero to a number does not change it. | ||||
1027 | return ConstantInt::get(Tp, 0); | ||||
1028 | case RecurKind::Mul: | ||||
1029 | // Multiplying a number by 1 does not change it. | ||||
1030 | return ConstantInt::get(Tp, 1); | ||||
1031 | case RecurKind::And: | ||||
1032 | // AND-ing a number with an all-1 value does not change it. | ||||
1033 | return ConstantInt::get(Tp, -1, true); | ||||
1034 | case RecurKind::FMul: | ||||
1035 | // Multiplying a number by 1 does not change it. | ||||
1036 | return ConstantFP::get(Tp, 1.0L); | ||||
1037 | case RecurKind::FMulAdd: | ||||
1038 | case RecurKind::FAdd: | ||||
1039 | // Adding zero to a number does not change it. | ||||
1040 | // FIXME: Ideally we should not need to check FMF for FAdd and should always | ||||
1041 | // use -0.0. However, this will currently result in mixed vectors of 0.0/-0.0. | ||||
1042 | // Instead, we should ensure that 1) the FMF from FAdd are propagated to the PHI | ||||
1043 | // nodes where possible, and 2) PHIs with the nsz flag + -0.0 use 0.0. This would | ||||
1044 | // mean we can then remove the check for noSignedZeros() below (see D98963). | ||||
1045 | if (FMF.noSignedZeros()) | ||||
1046 | return ConstantFP::get(Tp, 0.0L); | ||||
1047 | return ConstantFP::get(Tp, -0.0L); | ||||
1048 | case RecurKind::UMin: | ||||
1049 | return ConstantInt::get(Tp, -1, true); | ||||
1050 | case RecurKind::UMax: | ||||
1051 | return ConstantInt::get(Tp, 0); | ||||
1052 | case RecurKind::SMin: | ||||
1053 | return ConstantInt::get(Tp, | ||||
1054 | APInt::getSignedMaxValue(Tp->getIntegerBitWidth())); | ||||
1055 | case RecurKind::SMax: | ||||
1056 | return ConstantInt::get(Tp, | ||||
1057 | APInt::getSignedMinValue(Tp->getIntegerBitWidth())); | ||||
1058 | case RecurKind::FMin: | ||||
1059 | assert((FMF.noNaNs() && FMF.noSignedZeros()) &&(static_cast <bool> ((FMF.noNaNs() && FMF.noSignedZeros ()) && "nnan, nsz is expected to be set for FP min reduction." ) ? void (0) : __assert_fail ("(FMF.noNaNs() && FMF.noSignedZeros()) && \"nnan, nsz is expected to be set for FP min reduction.\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1060, __extension__ __PRETTY_FUNCTION__ )) | ||||
1060 | "nnan, nsz is expected to be set for FP min reduction.")(static_cast <bool> ((FMF.noNaNs() && FMF.noSignedZeros ()) && "nnan, nsz is expected to be set for FP min reduction." ) ? void (0) : __assert_fail ("(FMF.noNaNs() && FMF.noSignedZeros()) && \"nnan, nsz is expected to be set for FP min reduction.\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1060, __extension__ __PRETTY_FUNCTION__ )); | ||||
1061 | return ConstantFP::getInfinity(Tp, false /*Negative*/); | ||||
1062 | case RecurKind::FMax: | ||||
1063 | assert((FMF.noNaNs() && FMF.noSignedZeros()) &&(static_cast <bool> ((FMF.noNaNs() && FMF.noSignedZeros ()) && "nnan, nsz is expected to be set for FP max reduction." ) ? void (0) : __assert_fail ("(FMF.noNaNs() && FMF.noSignedZeros()) && \"nnan, nsz is expected to be set for FP max reduction.\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1064, __extension__ __PRETTY_FUNCTION__ )) | ||||
1064 | "nnan, nsz is expected to be set for FP max reduction.")(static_cast <bool> ((FMF.noNaNs() && FMF.noSignedZeros ()) && "nnan, nsz is expected to be set for FP max reduction." ) ? void (0) : __assert_fail ("(FMF.noNaNs() && FMF.noSignedZeros()) && \"nnan, nsz is expected to be set for FP max reduction.\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1064, __extension__ __PRETTY_FUNCTION__ )); | ||||
1065 | return ConstantFP::getInfinity(Tp, true /*Negative*/); | ||||
1066 | case RecurKind::SelectICmp: | ||||
1067 | case RecurKind::SelectFCmp: | ||||
1068 | return getRecurrenceStartValue(); | ||||
1069 | break; | ||||
1070 | default: | ||||
1071 | llvm_unreachable("Unknown recurrence kind")::llvm::llvm_unreachable_internal("Unknown recurrence kind", "llvm/lib/Analysis/IVDescriptors.cpp" , 1071); | ||||
1072 | } | ||||
1073 | } | ||||
1074 | |||||
1075 | unsigned RecurrenceDescriptor::getOpcode(RecurKind Kind) { | ||||
1076 | switch (Kind) { | ||||
1077 | case RecurKind::Add: | ||||
1078 | return Instruction::Add; | ||||
1079 | case RecurKind::Mul: | ||||
1080 | return Instruction::Mul; | ||||
1081 | case RecurKind::Or: | ||||
1082 | return Instruction::Or; | ||||
1083 | case RecurKind::And: | ||||
1084 | return Instruction::And; | ||||
1085 | case RecurKind::Xor: | ||||
1086 | return Instruction::Xor; | ||||
1087 | case RecurKind::FMul: | ||||
1088 | return Instruction::FMul; | ||||
1089 | case RecurKind::FMulAdd: | ||||
1090 | case RecurKind::FAdd: | ||||
1091 | return Instruction::FAdd; | ||||
1092 | case RecurKind::SMax: | ||||
1093 | case RecurKind::SMin: | ||||
1094 | case RecurKind::UMax: | ||||
1095 | case RecurKind::UMin: | ||||
1096 | case RecurKind::SelectICmp: | ||||
1097 | return Instruction::ICmp; | ||||
1098 | case RecurKind::FMax: | ||||
1099 | case RecurKind::FMin: | ||||
1100 | case RecurKind::SelectFCmp: | ||||
1101 | return Instruction::FCmp; | ||||
1102 | default: | ||||
1103 | llvm_unreachable("Unknown recurrence operation")::llvm::llvm_unreachable_internal("Unknown recurrence operation" , "llvm/lib/Analysis/IVDescriptors.cpp", 1103); | ||||
1104 | } | ||||
1105 | } | ||||
1106 | |||||
1107 | SmallVector<Instruction *, 4> | ||||
1108 | RecurrenceDescriptor::getReductionOpChain(PHINode *Phi, Loop *L) const { | ||||
1109 | SmallVector<Instruction *, 4> ReductionOperations; | ||||
1110 | unsigned RedOp = getOpcode(Kind); | ||||
1111 | |||||
1112 | // Search down from the Phi to the LoopExitInstr, looking for instructions | ||||
1113 | // with a single user of the correct type for the reduction. | ||||
1114 | |||||
1115 | // Note that we check that the type of the operand is correct for each item in | ||||
1116 | // the chain, including the last (the loop exit value). This can come up from | ||||
1117 | // sub, which would otherwise be treated as an add reduction. MinMax also need | ||||
1118 | // to check for a pair of icmp/select, for which we use getNextInstruction and | ||||
1119 | // isCorrectOpcode functions to step the right number of instruction, and | ||||
1120 | // check the icmp/select pair. | ||||
1121 | // FIXME: We also do not attempt to look through Select's yet, which might | ||||
1122 | // be part of the reduction chain, or attempt to looks through And's to find a | ||||
1123 | // smaller bitwidth. Subs are also currently not allowed (which are usually | ||||
1124 | // treated as part of a add reduction) as they are expected to generally be | ||||
1125 | // more expensive than out-of-loop reductions, and need to be costed more | ||||
1126 | // carefully. | ||||
1127 | unsigned ExpectedUses = 1; | ||||
1128 | if (RedOp
| ||||
| |||||
1129 | ExpectedUses = 2; | ||||
1130 | |||||
1131 | auto getNextInstruction = [&](Instruction *Cur) -> Instruction * { | ||||
1132 | for (auto *User : Cur->users()) { | ||||
1133 | Instruction *UI = cast<Instruction>(User); | ||||
1134 | if (isa<PHINode>(UI)) | ||||
1135 | continue; | ||||
1136 | if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) { | ||||
1137 | // We are expecting a icmp/select pair, which we go to the next select | ||||
1138 | // instruction if we can. We already know that Cur has 2 uses. | ||||
1139 | if (isa<SelectInst>(UI)) | ||||
1140 | return UI; | ||||
1141 | continue; | ||||
1142 | } | ||||
1143 | return UI; | ||||
1144 | } | ||||
1145 | return nullptr; | ||||
1146 | }; | ||||
1147 | auto isCorrectOpcode = [&](Instruction *Cur) { | ||||
1148 | if (RedOp
| ||||
1149 | Value *LHS, *RHS; | ||||
1150 | return SelectPatternResult::isMinOrMax( | ||||
1151 | matchSelectPattern(Cur, LHS, RHS).Flavor); | ||||
1152 | } | ||||
1153 | // Recognize a call to the llvm.fmuladd intrinsic. | ||||
1154 | if (isFMulAddIntrinsic(Cur)) | ||||
1155 | return true; | ||||
1156 | |||||
1157 | return Cur->getOpcode() == RedOp; | ||||
| |||||
1158 | }; | ||||
1159 | |||||
1160 | // Attempt to look through Phis which are part of the reduction chain | ||||
1161 | unsigned ExtraPhiUses = 0; | ||||
1162 | Instruction *RdxInstr = LoopExitInstr; | ||||
1163 | if (auto ExitPhi
| ||||
1164 | if (ExitPhi->getNumIncomingValues() != 2) | ||||
1165 | return {}; | ||||
1166 | |||||
1167 | Instruction *Inc0 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(0)); | ||||
1168 | Instruction *Inc1 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(1)); | ||||
1169 | |||||
1170 | Instruction *Chain = nullptr; | ||||
1171 | if (Inc0 == Phi) | ||||
1172 | Chain = Inc1; | ||||
1173 | else if (Inc1 == Phi) | ||||
1174 | Chain = Inc0; | ||||
1175 | else | ||||
1176 | return {}; | ||||
1177 | |||||
1178 | RdxInstr = Chain; | ||||
1179 | ExtraPhiUses = 1; | ||||
1180 | } | ||||
1181 | |||||
1182 | // The loop exit instruction we check first (as a quick test) but add last. We | ||||
1183 | // check the opcode is correct (and dont allow them to be Subs) and that they | ||||
1184 | // have expected to have the expected number of uses. They will have one use | ||||
1185 | // from the phi and one from a LCSSA value, no matter the type. | ||||
1186 | if (!isCorrectOpcode(RdxInstr) || !LoopExitInstr->hasNUses(2)) | ||||
1187 | return {}; | ||||
1188 | |||||
1189 | // Check that the Phi has one (or two for min/max) uses, plus an extra use | ||||
1190 | // for conditional reductions. | ||||
1191 | if (!Phi->hasNUses(ExpectedUses + ExtraPhiUses)) | ||||
1192 | return {}; | ||||
1193 | |||||
1194 | Instruction *Cur = getNextInstruction(Phi); | ||||
1195 | |||||
1196 | // Each other instruction in the chain should have the expected number of uses | ||||
1197 | // and be the correct opcode. | ||||
1198 | while (Cur != RdxInstr) { | ||||
1199 | if (!Cur || !isCorrectOpcode(Cur) || !Cur->hasNUses(ExpectedUses)) | ||||
1200 | return {}; | ||||
1201 | |||||
1202 | ReductionOperations.push_back(Cur); | ||||
1203 | Cur = getNextInstruction(Cur); | ||||
1204 | } | ||||
1205 | |||||
1206 | ReductionOperations.push_back(Cur); | ||||
1207 | return ReductionOperations; | ||||
1208 | } | ||||
1209 | |||||
1210 | InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K, | ||||
1211 | const SCEV *Step, BinaryOperator *BOp, | ||||
1212 | Type *ElementType, | ||||
1213 | SmallVectorImpl<Instruction *> *Casts) | ||||
1214 | : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp), | ||||
1215 | ElementType(ElementType) { | ||||
1216 | assert(IK != IK_NoInduction && "Not an induction")(static_cast <bool> (IK != IK_NoInduction && "Not an induction" ) ? void (0) : __assert_fail ("IK != IK_NoInduction && \"Not an induction\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1216, __extension__ __PRETTY_FUNCTION__ )); | ||||
1217 | |||||
1218 | // Start value type should match the induction kind and the value | ||||
1219 | // itself should not be null. | ||||
1220 | assert(StartValue && "StartValue is null")(static_cast <bool> (StartValue && "StartValue is null" ) ? void (0) : __assert_fail ("StartValue && \"StartValue is null\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1220, __extension__ __PRETTY_FUNCTION__ )); | ||||
1221 | assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&(static_cast <bool> ((IK != IK_PtrInduction || StartValue ->getType()->isPointerTy()) && "StartValue is not a pointer for pointer induction" ) ? void (0) : __assert_fail ("(IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) && \"StartValue is not a pointer for pointer induction\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1222, __extension__ __PRETTY_FUNCTION__ )) | ||||
1222 | "StartValue is not a pointer for pointer induction")(static_cast <bool> ((IK != IK_PtrInduction || StartValue ->getType()->isPointerTy()) && "StartValue is not a pointer for pointer induction" ) ? void (0) : __assert_fail ("(IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) && \"StartValue is not a pointer for pointer induction\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1222, __extension__ __PRETTY_FUNCTION__ )); | ||||
1223 | assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&(static_cast <bool> ((IK != IK_IntInduction || StartValue ->getType()->isIntegerTy()) && "StartValue is not an integer for integer induction" ) ? void (0) : __assert_fail ("(IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) && \"StartValue is not an integer for integer induction\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1224, __extension__ __PRETTY_FUNCTION__ )) | ||||
1224 | "StartValue is not an integer for integer induction")(static_cast <bool> ((IK != IK_IntInduction || StartValue ->getType()->isIntegerTy()) && "StartValue is not an integer for integer induction" ) ? void (0) : __assert_fail ("(IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) && \"StartValue is not an integer for integer induction\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1224, __extension__ __PRETTY_FUNCTION__ )); | ||||
1225 | |||||
1226 | // Check the Step Value. It should be non-zero integer value. | ||||
1227 | assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&(static_cast <bool> ((!getConstIntStepValue() || !getConstIntStepValue ()->isZero()) && "Step value is zero") ? void (0) : __assert_fail ("(!getConstIntStepValue() || !getConstIntStepValue()->isZero()) && \"Step value is zero\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1228, __extension__ __PRETTY_FUNCTION__ )) | ||||
1228 | "Step value is zero")(static_cast <bool> ((!getConstIntStepValue() || !getConstIntStepValue ()->isZero()) && "Step value is zero") ? void (0) : __assert_fail ("(!getConstIntStepValue() || !getConstIntStepValue()->isZero()) && \"Step value is zero\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1228, __extension__ __PRETTY_FUNCTION__ )); | ||||
1229 | |||||
1230 | assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&(static_cast <bool> ((IK == IK_FpInduction || Step-> getType()->isIntegerTy()) && "StepValue is not an integer" ) ? void (0) : __assert_fail ("(IK == IK_FpInduction || Step->getType()->isIntegerTy()) && \"StepValue is not an integer\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1231, __extension__ __PRETTY_FUNCTION__ )) | ||||
1231 | "StepValue is not an integer")(static_cast <bool> ((IK == IK_FpInduction || Step-> getType()->isIntegerTy()) && "StepValue is not an integer" ) ? void (0) : __assert_fail ("(IK == IK_FpInduction || Step->getType()->isIntegerTy()) && \"StepValue is not an integer\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1231, __extension__ __PRETTY_FUNCTION__ )); | ||||
1232 | |||||
1233 | assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&(static_cast <bool> ((IK != IK_FpInduction || Step-> getType()->isFloatingPointTy()) && "StepValue is not FP for FpInduction" ) ? void (0) : __assert_fail ("(IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) && \"StepValue is not FP for FpInduction\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1234, __extension__ __PRETTY_FUNCTION__ )) | ||||
1234 | "StepValue is not FP for FpInduction")(static_cast <bool> ((IK != IK_FpInduction || Step-> getType()->isFloatingPointTy()) && "StepValue is not FP for FpInduction" ) ? void (0) : __assert_fail ("(IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) && \"StepValue is not FP for FpInduction\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1234, __extension__ __PRETTY_FUNCTION__ )); | ||||
1235 | assert((IK != IK_FpInduction ||(static_cast <bool> ((IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && "Binary opcode should be specified for FP induction") ? void (0) : __assert_fail ("(IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && \"Binary opcode should be specified for FP induction\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1239, __extension__ __PRETTY_FUNCTION__ )) | ||||
1236 | (InductionBinOp &&(static_cast <bool> ((IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && "Binary opcode should be specified for FP induction") ? void (0) : __assert_fail ("(IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && \"Binary opcode should be specified for FP induction\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1239, __extension__ __PRETTY_FUNCTION__ )) | ||||
1237 | (InductionBinOp->getOpcode() == Instruction::FAdd ||(static_cast <bool> ((IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && "Binary opcode should be specified for FP induction") ? void (0) : __assert_fail ("(IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && \"Binary opcode should be specified for FP induction\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1239, __extension__ __PRETTY_FUNCTION__ )) | ||||
1238 | InductionBinOp->getOpcode() == Instruction::FSub))) &&(static_cast <bool> ((IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && "Binary opcode should be specified for FP induction") ? void (0) : __assert_fail ("(IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && \"Binary opcode should be specified for FP induction\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1239, __extension__ __PRETTY_FUNCTION__ )) | ||||
1239 | "Binary opcode should be specified for FP induction")(static_cast <bool> ((IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && "Binary opcode should be specified for FP induction") ? void (0) : __assert_fail ("(IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && \"Binary opcode should be specified for FP induction\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1239, __extension__ __PRETTY_FUNCTION__ )); | ||||
1240 | |||||
1241 | if (IK == IK_PtrInduction) | ||||
1242 | assert(ElementType && "Pointer induction must have element type")(static_cast <bool> (ElementType && "Pointer induction must have element type" ) ? void (0) : __assert_fail ("ElementType && \"Pointer induction must have element type\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1242, __extension__ __PRETTY_FUNCTION__ )); | ||||
1243 | else | ||||
1244 | assert(!ElementType && "Non-pointer induction cannot have element type")(static_cast <bool> (!ElementType && "Non-pointer induction cannot have element type" ) ? void (0) : __assert_fail ("!ElementType && \"Non-pointer induction cannot have element type\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1244, __extension__ __PRETTY_FUNCTION__ )); | ||||
1245 | |||||
1246 | if (Casts) { | ||||
1247 | for (auto &Inst : *Casts) { | ||||
1248 | RedundantCasts.push_back(Inst); | ||||
1249 | } | ||||
1250 | } | ||||
1251 | } | ||||
1252 | |||||
1253 | ConstantInt *InductionDescriptor::getConstIntStepValue() const { | ||||
1254 | if (isa<SCEVConstant>(Step)) | ||||
1255 | return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue()); | ||||
1256 | return nullptr; | ||||
1257 | } | ||||
1258 | |||||
1259 | bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop, | ||||
1260 | ScalarEvolution *SE, | ||||
1261 | InductionDescriptor &D) { | ||||
1262 | |||||
1263 | // Here we only handle FP induction variables. | ||||
1264 | assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type")(static_cast <bool> (Phi->getType()->isFloatingPointTy () && "Unexpected Phi type") ? void (0) : __assert_fail ("Phi->getType()->isFloatingPointTy() && \"Unexpected Phi type\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1264, __extension__ __PRETTY_FUNCTION__ )); | ||||
1265 | |||||
1266 | if (TheLoop->getHeader() != Phi->getParent()) | ||||
1267 | return false; | ||||
1268 | |||||
1269 | // The loop may have multiple entrances or multiple exits; we can analyze | ||||
1270 | // this phi if it has a unique entry value and a unique backedge value. | ||||
1271 | if (Phi->getNumIncomingValues() != 2) | ||||
1272 | return false; | ||||
1273 | Value *BEValue = nullptr, *StartValue = nullptr; | ||||
1274 | if (TheLoop->contains(Phi->getIncomingBlock(0))) { | ||||
1275 | BEValue = Phi->getIncomingValue(0); | ||||
1276 | StartValue = Phi->getIncomingValue(1); | ||||
1277 | } else { | ||||
1278 | assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&(static_cast <bool> (TheLoop->contains(Phi->getIncomingBlock (1)) && "Unexpected Phi node in the loop") ? void (0) : __assert_fail ("TheLoop->contains(Phi->getIncomingBlock(1)) && \"Unexpected Phi node in the loop\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1279, __extension__ __PRETTY_FUNCTION__ )) | ||||
1279 | "Unexpected Phi node in the loop")(static_cast <bool> (TheLoop->contains(Phi->getIncomingBlock (1)) && "Unexpected Phi node in the loop") ? void (0) : __assert_fail ("TheLoop->contains(Phi->getIncomingBlock(1)) && \"Unexpected Phi node in the loop\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1279, __extension__ __PRETTY_FUNCTION__ )); | ||||
1280 | BEValue = Phi->getIncomingValue(1); | ||||
1281 | StartValue = Phi->getIncomingValue(0); | ||||
1282 | } | ||||
1283 | |||||
1284 | BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue); | ||||
1285 | if (!BOp) | ||||
1286 | return false; | ||||
1287 | |||||
1288 | Value *Addend = nullptr; | ||||
1289 | if (BOp->getOpcode() == Instruction::FAdd) { | ||||
1290 | if (BOp->getOperand(0) == Phi) | ||||
1291 | Addend = BOp->getOperand(1); | ||||
1292 | else if (BOp->getOperand(1) == Phi) | ||||
1293 | Addend = BOp->getOperand(0); | ||||
1294 | } else if (BOp->getOpcode() == Instruction::FSub) | ||||
1295 | if (BOp->getOperand(0) == Phi) | ||||
1296 | Addend = BOp->getOperand(1); | ||||
1297 | |||||
1298 | if (!Addend) | ||||
1299 | return false; | ||||
1300 | |||||
1301 | // The addend should be loop invariant | ||||
1302 | if (auto *I = dyn_cast<Instruction>(Addend)) | ||||
1303 | if (TheLoop->contains(I)) | ||||
1304 | return false; | ||||
1305 | |||||
1306 | // FP Step has unknown SCEV | ||||
1307 | const SCEV *Step = SE->getUnknown(Addend); | ||||
1308 | D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp); | ||||
1309 | return true; | ||||
1310 | } | ||||
1311 | |||||
1312 | /// This function is called when we suspect that the update-chain of a phi node | ||||
1313 | /// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts, | ||||
1314 | /// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime | ||||
1315 | /// predicate P under which the SCEV expression for the phi can be the | ||||
1316 | /// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the | ||||
1317 | /// cast instructions that are involved in the update-chain of this induction. | ||||
1318 | /// A caller that adds the required runtime predicate can be free to drop these | ||||
1319 | /// cast instructions, and compute the phi using \p AR (instead of some scev | ||||
1320 | /// expression with casts). | ||||
1321 | /// | ||||
1322 | /// For example, without a predicate the scev expression can take the following | ||||
1323 | /// form: | ||||
1324 | /// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy) | ||||
1325 | /// | ||||
1326 | /// It corresponds to the following IR sequence: | ||||
1327 | /// %for.body: | ||||
1328 | /// %x = phi i64 [ 0, %ph ], [ %add, %for.body ] | ||||
1329 | /// %casted_phi = "ExtTrunc i64 %x" | ||||
1330 | /// %add = add i64 %casted_phi, %step | ||||
1331 | /// | ||||
1332 | /// where %x is given in \p PN, | ||||
1333 | /// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate, | ||||
1334 | /// and the IR sequence that "ExtTrunc i64 %x" represents can take one of | ||||
1335 | /// several forms, for example, such as: | ||||
1336 | /// ExtTrunc1: %casted_phi = and %x, 2^n-1 | ||||
1337 | /// or: | ||||
1338 | /// ExtTrunc2: %t = shl %x, m | ||||
1339 | /// %casted_phi = ashr %t, m | ||||
1340 | /// | ||||
1341 | /// If we are able to find such sequence, we return the instructions | ||||
1342 | /// we found, namely %casted_phi and the instructions on its use-def chain up | ||||
1343 | /// to the phi (not including the phi). | ||||
1344 | static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE, | ||||
1345 | const SCEVUnknown *PhiScev, | ||||
1346 | const SCEVAddRecExpr *AR, | ||||
1347 | SmallVectorImpl<Instruction *> &CastInsts) { | ||||
1348 | |||||
1349 | assert(CastInsts.empty() && "CastInsts is expected to be empty.")(static_cast <bool> (CastInsts.empty() && "CastInsts is expected to be empty." ) ? void (0) : __assert_fail ("CastInsts.empty() && \"CastInsts is expected to be empty.\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1349, __extension__ __PRETTY_FUNCTION__ )); | ||||
1350 | auto *PN = cast<PHINode>(PhiScev->getValue()); | ||||
1351 | assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression")(static_cast <bool> (PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression" ) ? void (0) : __assert_fail ("PSE.getSCEV(PN) == AR && \"Unexpected phi node SCEV expression\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1351, __extension__ __PRETTY_FUNCTION__ )); | ||||
1352 | const Loop *L = AR->getLoop(); | ||||
1353 | |||||
1354 | // Find any cast instructions that participate in the def-use chain of | ||||
1355 | // PhiScev in the loop. | ||||
1356 | // FORNOW/TODO: We currently expect the def-use chain to include only | ||||
1357 | // two-operand instructions, where one of the operands is an invariant. | ||||
1358 | // createAddRecFromPHIWithCasts() currently does not support anything more | ||||
1359 | // involved than that, so we keep the search simple. This can be | ||||
1360 | // extended/generalized as needed. | ||||
1361 | |||||
1362 | auto getDef = [&](const Value *Val) -> Value * { | ||||
1363 | const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val); | ||||
1364 | if (!BinOp) | ||||
1365 | return nullptr; | ||||
1366 | Value *Op0 = BinOp->getOperand(0); | ||||
1367 | Value *Op1 = BinOp->getOperand(1); | ||||
1368 | Value *Def = nullptr; | ||||
1369 | if (L->isLoopInvariant(Op0)) | ||||
1370 | Def = Op1; | ||||
1371 | else if (L->isLoopInvariant(Op1)) | ||||
1372 | Def = Op0; | ||||
1373 | return Def; | ||||
1374 | }; | ||||
1375 | |||||
1376 | // Look for the instruction that defines the induction via the | ||||
1377 | // loop backedge. | ||||
1378 | BasicBlock *Latch = L->getLoopLatch(); | ||||
1379 | if (!Latch) | ||||
1380 | return false; | ||||
1381 | Value *Val = PN->getIncomingValueForBlock(Latch); | ||||
1382 | if (!Val) | ||||
1383 | return false; | ||||
1384 | |||||
1385 | // Follow the def-use chain until the induction phi is reached. | ||||
1386 | // If on the way we encounter a Value that has the same SCEV Expr as the | ||||
1387 | // phi node, we can consider the instructions we visit from that point | ||||
1388 | // as part of the cast-sequence that can be ignored. | ||||
1389 | bool InCastSequence = false; | ||||
1390 | auto *Inst = dyn_cast<Instruction>(Val); | ||||
1391 | while (Val != PN) { | ||||
1392 | // If we encountered a phi node other than PN, or if we left the loop, | ||||
1393 | // we bail out. | ||||
1394 | if (!Inst || !L->contains(Inst)) { | ||||
1395 | return false; | ||||
1396 | } | ||||
1397 | auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val)); | ||||
1398 | if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR)) | ||||
1399 | InCastSequence = true; | ||||
1400 | if (InCastSequence) { | ||||
1401 | // Only the last instruction in the cast sequence is expected to have | ||||
1402 | // uses outside the induction def-use chain. | ||||
1403 | if (!CastInsts.empty()) | ||||
1404 | if (!Inst->hasOneUse()) | ||||
1405 | return false; | ||||
1406 | CastInsts.push_back(Inst); | ||||
1407 | } | ||||
1408 | Val = getDef(Val); | ||||
1409 | if (!Val) | ||||
1410 | return false; | ||||
1411 | Inst = dyn_cast<Instruction>(Val); | ||||
1412 | } | ||||
1413 | |||||
1414 | return InCastSequence; | ||||
1415 | } | ||||
1416 | |||||
1417 | bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop, | ||||
1418 | PredicatedScalarEvolution &PSE, | ||||
1419 | InductionDescriptor &D, bool Assume) { | ||||
1420 | Type *PhiTy = Phi->getType(); | ||||
1421 | |||||
1422 | // Handle integer and pointer inductions variables. | ||||
1423 | // Now we handle also FP induction but not trying to make a | ||||
1424 | // recurrent expression from the PHI node in-place. | ||||
1425 | |||||
1426 | if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && !PhiTy->isFloatTy() && | ||||
1427 | !PhiTy->isDoubleTy() && !PhiTy->isHalfTy()) | ||||
1428 | return false; | ||||
1429 | |||||
1430 | if (PhiTy->isFloatingPointTy()) | ||||
1431 | return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D); | ||||
1432 | |||||
1433 | const SCEV *PhiScev = PSE.getSCEV(Phi); | ||||
1434 | const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev); | ||||
1435 | |||||
1436 | // We need this expression to be an AddRecExpr. | ||||
1437 | if (Assume && !AR) | ||||
1438 | AR = PSE.getAsAddRec(Phi); | ||||
1439 | |||||
1440 | if (!AR) { | ||||
1441 | LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "LV: PHI is not a poly recurrence.\n" ; } } while (false); | ||||
1442 | return false; | ||||
1443 | } | ||||
1444 | |||||
1445 | // Record any Cast instructions that participate in the induction update | ||||
1446 | const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev); | ||||
1447 | // If we started from an UnknownSCEV, and managed to build an addRecurrence | ||||
1448 | // only after enabling Assume with PSCEV, this means we may have encountered | ||||
1449 | // cast instructions that required adding a runtime check in order to | ||||
1450 | // guarantee the correctness of the AddRecurrence respresentation of the | ||||
1451 | // induction. | ||||
1452 | if (PhiScev != AR && SymbolicPhi) { | ||||
1453 | SmallVector<Instruction *, 2> Casts; | ||||
1454 | if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts)) | ||||
1455 | return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts); | ||||
1456 | } | ||||
1457 | |||||
1458 | return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR); | ||||
1459 | } | ||||
1460 | |||||
1461 | bool InductionDescriptor::isInductionPHI( | ||||
1462 | PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE, | ||||
1463 | InductionDescriptor &D, const SCEV *Expr, | ||||
1464 | SmallVectorImpl<Instruction *> *CastsToIgnore) { | ||||
1465 | Type *PhiTy = Phi->getType(); | ||||
1466 | // We only handle integer and pointer inductions variables. | ||||
1467 | if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy()) | ||||
1468 | return false; | ||||
1469 | |||||
1470 | // Check that the PHI is consecutive. | ||||
1471 | const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi); | ||||
1472 | const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev); | ||||
1473 | |||||
1474 | if (!AR) { | ||||
1475 | LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "LV: PHI is not a poly recurrence.\n" ; } } while (false); | ||||
1476 | return false; | ||||
1477 | } | ||||
1478 | |||||
1479 | if (AR->getLoop() != TheLoop) { | ||||
1480 | // FIXME: We should treat this as a uniform. Unfortunately, we | ||||
1481 | // don't currently know how to handled uniform PHIs. | ||||
1482 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n" ; } } while (false) | ||||
1483 | dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("iv-descriptors")) { dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n" ; } } while (false); | ||||
1484 | return false; | ||||
1485 | } | ||||
1486 | |||||
1487 | // This function assumes that InductionPhi is called only on Phi nodes | ||||
1488 | // present inside loop headers. Check for the same, and throw an assert if | ||||
1489 | // the current Phi is not present inside the loop header. | ||||
1490 | assert(Phi->getParent() == AR->getLoop()->getHeader()(static_cast <bool> (Phi->getParent() == AR->getLoop ()->getHeader() && "Invalid Phi node, not present in loop header" ) ? void (0) : __assert_fail ("Phi->getParent() == AR->getLoop()->getHeader() && \"Invalid Phi node, not present in loop header\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1491, __extension__ __PRETTY_FUNCTION__ )) | ||||
1491 | && "Invalid Phi node, not present in loop header")(static_cast <bool> (Phi->getParent() == AR->getLoop ()->getHeader() && "Invalid Phi node, not present in loop header" ) ? void (0) : __assert_fail ("Phi->getParent() == AR->getLoop()->getHeader() && \"Invalid Phi node, not present in loop header\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1491, __extension__ __PRETTY_FUNCTION__ )); | ||||
1492 | |||||
1493 | Value *StartValue = | ||||
1494 | Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader()); | ||||
1495 | |||||
1496 | BasicBlock *Latch = AR->getLoop()->getLoopLatch(); | ||||
1497 | if (!Latch) | ||||
1498 | return false; | ||||
1499 | |||||
1500 | const SCEV *Step = AR->getStepRecurrence(*SE); | ||||
1501 | // Calculate the pointer stride and check if it is consecutive. | ||||
1502 | // The stride may be a constant or a loop invariant integer value. | ||||
1503 | const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step); | ||||
1504 | if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop)) | ||||
1505 | return false; | ||||
1506 | |||||
1507 | if (PhiTy->isIntegerTy()) { | ||||
1508 | BinaryOperator *BOp = | ||||
1509 | dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch)); | ||||
1510 | D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp, | ||||
1511 | /* ElementType */ nullptr, CastsToIgnore); | ||||
1512 | return true; | ||||
1513 | } | ||||
1514 | |||||
1515 | assert(PhiTy->isPointerTy() && "The PHI must be a pointer")(static_cast <bool> (PhiTy->isPointerTy() && "The PHI must be a pointer") ? void (0) : __assert_fail ("PhiTy->isPointerTy() && \"The PHI must be a pointer\"" , "llvm/lib/Analysis/IVDescriptors.cpp", 1515, __extension__ __PRETTY_FUNCTION__ )); | ||||
1516 | PointerType *PtrTy = cast<PointerType>(PhiTy); | ||||
1517 | |||||
1518 | // Always use i8 element type for opaque pointer inductions. | ||||
1519 | // This allows induction variables w/non-constant steps. | ||||
1520 | if (PtrTy->isOpaque()) { | ||||
1521 | D = InductionDescriptor(StartValue, IK_PtrInduction, Step, | ||||
1522 | /* BinOp */ nullptr, | ||||
1523 | Type::getInt8Ty(PtrTy->getContext())); | ||||
1524 | return true; | ||||
1525 | } | ||||
1526 | |||||
1527 | // Pointer induction should be a constant. | ||||
1528 | // TODO: This could be generalized, but should probably just | ||||
1529 | // be dropped instead once the migration to opaque ptrs is | ||||
1530 | // complete. | ||||
1531 | if (!ConstStep) | ||||
1532 | return false; | ||||
1533 | |||||
1534 | Type *ElementType = PtrTy->getNonOpaquePointerElementType(); | ||||
1535 | if (!ElementType->isSized()) | ||||
1536 | return false; | ||||
1537 | |||||
1538 | ConstantInt *CV = ConstStep->getValue(); | ||||
1539 | const DataLayout &DL = Phi->getModule()->getDataLayout(); | ||||
1540 | TypeSize TySize = DL.getTypeAllocSize(ElementType); | ||||
1541 | // TODO: We could potentially support this for scalable vectors if we can | ||||
1542 | // prove at compile time that the constant step is always a multiple of | ||||
1543 | // the scalable type. | ||||
1544 | if (TySize.isZero() || TySize.isScalable()) | ||||
1545 | return false; | ||||
1546 | |||||
1547 | int64_t Size = static_cast<int64_t>(TySize.getFixedValue()); | ||||
1548 | int64_t CVSize = CV->getSExtValue(); | ||||
1549 | if (CVSize % Size) | ||||
1550 | return false; | ||||
1551 | auto *StepValue = | ||||
1552 | SE->getConstant(CV->getType(), CVSize / Size, true /* signed */); | ||||
1553 | D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue, | ||||
1554 | /* BinOp */ nullptr, ElementType); | ||||
1555 | return true; | ||||
1556 | } |