blob: a4aaf783d41b1a284295927aa22c9cf89ccd9df6 [file] [log] [blame]
Karthik Bhat76aa6622015-04-20 04:38:33 +00001//===-- LoopUtils.cpp - Loop Utility functions -------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines common loop utility functions.
11//
12//===----------------------------------------------------------------------===//
13
Adam Nemet2f2bd8c2016-07-26 17:52:02 +000014#include "llvm/Transforms/Utils/LoopUtils.h"
Chandler Carruth4a000882017-06-25 22:45:31 +000015#include "llvm/ADT/ScopeExit.h"
Chandler Carruth31088a92016-02-19 10:45:18 +000016#include "llvm/Analysis/AliasAnalysis.h"
17#include "llvm/Analysis/BasicAliasAnalysis.h"
Chandler Carruth31088a92016-02-19 10:45:18 +000018#include "llvm/Analysis/GlobalsModRef.h"
Philip Reamesa21d5f12018-03-15 21:04:28 +000019#include "llvm/Analysis/InstructionSimplify.h"
Adam Nemet2f2bd8c2016-07-26 17:52:02 +000020#include "llvm/Analysis/LoopInfo.h"
Igor Laevskyc3ccf5d2016-10-28 12:57:20 +000021#include "llvm/Analysis/LoopPass.h"
Philip Reames23aed5e2018-03-20 22:45:23 +000022#include "llvm/Analysis/MustExecute.h"
Weiming Zhao45d4cb92015-11-24 18:57:06 +000023#include "llvm/Analysis/ScalarEvolution.h"
Adam Nemet2f2bd8c2016-07-26 17:52:02 +000024#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
Elena Demikhovskyc434d092016-05-10 07:33:35 +000025#include "llvm/Analysis/ScalarEvolutionExpander.h"
Weiming Zhao45d4cb92015-11-24 18:57:06 +000026#include "llvm/Analysis/ScalarEvolutionExpressions.h"
Chandler Carruth6bda14b2017-06-06 11:49:48 +000027#include "llvm/Analysis/TargetTransformInfo.h"
Chad Rosiera097bc62018-02-04 15:42:24 +000028#include "llvm/Analysis/ValueTracking.h"
Chijun Sima21a8b602018-08-03 05:08:17 +000029#include "llvm/IR/DomTreeUpdater.h"
Chandler Carruth31088a92016-02-19 10:45:18 +000030#include "llvm/IR/Dominators.h"
Karthik Bhat76aa6622015-04-20 04:38:33 +000031#include "llvm/IR/Instructions.h"
Weiming Zhao45d4cb92015-11-24 18:57:06 +000032#include "llvm/IR/Module.h"
Karthik Bhat76aa6622015-04-20 04:38:33 +000033#include "llvm/IR/PatternMatch.h"
34#include "llvm/IR/ValueHandle.h"
Chandler Carruth31088a92016-02-19 10:45:18 +000035#include "llvm/Pass.h"
Karthik Bhat76aa6622015-04-20 04:38:33 +000036#include "llvm/Support/Debug.h"
Chad Rosiera097bc62018-02-04 15:42:24 +000037#include "llvm/Support/KnownBits.h"
Chandler Carruth4a000882017-06-25 22:45:31 +000038#include "llvm/Transforms/Utils/BasicBlockUtils.h"
Karthik Bhat76aa6622015-04-20 04:38:33 +000039
40using namespace llvm;
41using namespace llvm::PatternMatch;
42
43#define DEBUG_TYPE "loop-utils"
44
Tyler Nowicki0a913102015-06-16 18:07:34 +000045bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
46 SmallPtrSetImpl<Instruction *> &Set) {
Karthik Bhat76aa6622015-04-20 04:38:33 +000047 for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
48 if (!Set.count(dyn_cast<Instruction>(*Use)))
49 return false;
50 return true;
51}
52
Chad Rosierc94f8e22015-08-27 14:12:17 +000053bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurrenceKind Kind) {
54 switch (Kind) {
55 default:
56 break;
57 case RK_IntegerAdd:
58 case RK_IntegerMult:
59 case RK_IntegerOr:
60 case RK_IntegerAnd:
61 case RK_IntegerXor:
62 case RK_IntegerMinMax:
63 return true;
64 }
65 return false;
66}
67
68bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurrenceKind Kind) {
69 return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind);
70}
71
72bool RecurrenceDescriptor::isArithmeticRecurrenceKind(RecurrenceKind Kind) {
73 switch (Kind) {
74 default:
75 break;
76 case RK_IntegerAdd:
77 case RK_IntegerMult:
78 case RK_FloatAdd:
79 case RK_FloatMult:
80 return true;
81 }
82 return false;
83}
84
Chad Rosiera097bc62018-02-04 15:42:24 +000085/// Determines if Phi may have been type-promoted. If Phi has a single user
86/// that ANDs the Phi with a type mask, return the user. RT is updated to
87/// account for the narrower bit width represented by the mask, and the AND
88/// instruction is added to CI.
89static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT,
90 SmallPtrSetImpl<Instruction *> &Visited,
91 SmallPtrSetImpl<Instruction *> &CI) {
Chad Rosierc94f8e22015-08-27 14:12:17 +000092 if (!Phi->hasOneUse())
93 return Phi;
94
95 const APInt *M = nullptr;
96 Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
97
98 // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
99 // with a new integer type of the corresponding bit width.
Craig Topper72ee6942017-06-24 06:24:01 +0000100 if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) {
Chad Rosierc94f8e22015-08-27 14:12:17 +0000101 int32_t Bits = (*M + 1).exactLogBase2();
102 if (Bits > 0) {
103 RT = IntegerType::get(Phi->getContext(), Bits);
104 Visited.insert(Phi);
105 CI.insert(J);
106 return J;
107 }
108 }
109 return Phi;
110}
111
Chad Rosiera097bc62018-02-04 15:42:24 +0000112/// Compute the minimal bit width needed to represent a reduction whose exit
113/// instruction is given by Exit.
114static std::pair<Type *, bool> computeRecurrenceType(Instruction *Exit,
115 DemandedBits *DB,
116 AssumptionCache *AC,
117 DominatorTree *DT) {
118 bool IsSigned = false;
119 const DataLayout &DL = Exit->getModule()->getDataLayout();
120 uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType());
Chad Rosierc94f8e22015-08-27 14:12:17 +0000121
Chad Rosiera097bc62018-02-04 15:42:24 +0000122 if (DB) {
123 // Use the demanded bits analysis to determine the bits that are live out
124 // of the exit instruction, rounding up to the nearest power of two. If the
125 // use of demanded bits results in a smaller bit width, we know the value
126 // must be positive (i.e., IsSigned = false), because if this were not the
127 // case, the sign bit would have been demanded.
128 auto Mask = DB->getDemandedBits(Exit);
129 MaxBitWidth = Mask.getBitWidth() - Mask.countLeadingZeros();
130 }
Chad Rosierc94f8e22015-08-27 14:12:17 +0000131
Chad Rosiera097bc62018-02-04 15:42:24 +0000132 if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) {
133 // If demanded bits wasn't able to limit the bit width, we can try to use
134 // value tracking instead. This can be the case, for example, if the value
135 // may be negative.
136 auto NumSignBits = ComputeNumSignBits(Exit, DL, 0, AC, nullptr, DT);
137 auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType());
138 MaxBitWidth = NumTypeBits - NumSignBits;
139 KnownBits Bits = computeKnownBits(Exit, DL);
140 if (!Bits.isNonNegative()) {
141 // If the value is not known to be non-negative, we set IsSigned to true,
142 // meaning that we will use sext instructions instead of zext
143 // instructions to restore the original type.
144 IsSigned = true;
145 if (!Bits.isNegative())
146 // If the value is not known to be negative, we don't known what the
147 // upper bit is, and therefore, we don't know what kind of extend we
148 // will need. In this case, just increase the bit width by one bit and
149 // use sext.
150 ++MaxBitWidth;
Chad Rosierc94f8e22015-08-27 14:12:17 +0000151 }
152 }
Chad Rosiera097bc62018-02-04 15:42:24 +0000153 if (!isPowerOf2_64(MaxBitWidth))
154 MaxBitWidth = NextPowerOf2(MaxBitWidth);
155
156 return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth),
157 IsSigned);
158}
159
160/// Collect cast instructions that can be ignored in the vectorizer's cost
161/// model, given a reduction exit value and the minimal type in which the
162/// reduction can be represented.
163static void collectCastsToIgnore(Loop *TheLoop, Instruction *Exit,
164 Type *RecurrenceType,
165 SmallPtrSetImpl<Instruction *> &Casts) {
166
167 SmallVector<Instruction *, 8> Worklist;
168 SmallPtrSet<Instruction *, 8> Visited;
169 Worklist.push_back(Exit);
170
171 while (!Worklist.empty()) {
172 Instruction *Val = Worklist.pop_back_val();
173 Visited.insert(Val);
174 if (auto *Cast = dyn_cast<CastInst>(Val))
175 if (Cast->getSrcTy() == RecurrenceType) {
176 // If the source type of a cast instruction is equal to the recurrence
177 // type, it will be eliminated, and should be ignored in the vectorizer
178 // cost model.
179 Casts.insert(Cast);
180 continue;
181 }
182
183 // Add all operands to the work list if they are loop-varying values that
184 // we haven't yet visited.
185 for (Value *O : cast<User>(Val)->operands())
186 if (auto *I = dyn_cast<Instruction>(O))
187 if (TheLoop->contains(I) && !Visited.count(I))
188 Worklist.push_back(I);
189 }
Chad Rosierc94f8e22015-08-27 14:12:17 +0000190}
191
Tyler Nowicki0a913102015-06-16 18:07:34 +0000192bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
193 Loop *TheLoop, bool HasFunNoNaNAttr,
Chad Rosiera097bc62018-02-04 15:42:24 +0000194 RecurrenceDescriptor &RedDes,
195 DemandedBits *DB,
196 AssumptionCache *AC,
197 DominatorTree *DT) {
Karthik Bhat76aa6622015-04-20 04:38:33 +0000198 if (Phi->getNumIncomingValues() != 2)
199 return false;
200
201 // Reduction variables are only found in the loop header block.
202 if (Phi->getParent() != TheLoop->getHeader())
203 return false;
204
205 // Obtain the reduction start value from the value that comes from the loop
206 // preheader.
207 Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
208
209 // ExitInstruction is the single value which is used outside the loop.
210 // We only allow for a single reduction value to be used outside the loop.
211 // This includes users of the reduction, variables (which form a cycle
212 // which ends in the phi node).
213 Instruction *ExitInstruction = nullptr;
214 // Indicates that we found a reduction operation in our scan.
215 bool FoundReduxOp = false;
216
217 // We start with the PHI node and scan for all of the users of this
218 // instruction. All users must be instructions that can be used as reduction
219 // variables (such as ADD). We must have a single out-of-block user. The cycle
220 // must include the original PHI.
221 bool FoundStartPHI = false;
222
223 // To recognize min/max patterns formed by a icmp select sequence, we store
224 // the number of instruction we saw from the recognized min/max pattern,
225 // to make sure we only see exactly the two instructions.
226 unsigned NumCmpSelectPatternInst = 0;
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000227 InstDesc ReduxDesc(false, nullptr);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000228
Chad Rosierc94f8e22015-08-27 14:12:17 +0000229 // Data used for determining if the recurrence has been type-promoted.
230 Type *RecurrenceType = Phi->getType();
231 SmallPtrSet<Instruction *, 4> CastInsts;
232 Instruction *Start = Phi;
233 bool IsSigned = false;
234
Karthik Bhat76aa6622015-04-20 04:38:33 +0000235 SmallPtrSet<Instruction *, 8> VisitedInsts;
236 SmallVector<Instruction *, 8> Worklist;
Chad Rosierc94f8e22015-08-27 14:12:17 +0000237
238 // Return early if the recurrence kind does not match the type of Phi. If the
239 // recurrence kind is arithmetic, we attempt to look through AND operations
240 // resulting from the type promotion performed by InstCombine. Vector
241 // operations are not limited to the legal integer widths, so we may be able
242 // to evaluate the reduction in the narrower width.
243 if (RecurrenceType->isFloatingPointTy()) {
244 if (!isFloatingPointRecurrenceKind(Kind))
245 return false;
246 } else {
247 if (!isIntegerRecurrenceKind(Kind))
248 return false;
249 if (isArithmeticRecurrenceKind(Kind))
250 Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
251 }
252
253 Worklist.push_back(Start);
254 VisitedInsts.insert(Start);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000255
256 // A value in the reduction can be used:
257 // - By the reduction:
258 // - Reduction operation:
259 // - One use of reduction value (safe).
260 // - Multiple use of reduction value (not safe).
261 // - PHI:
262 // - All uses of the PHI must be the reduction (safe).
263 // - Otherwise, not safe.
Michael Kuperstein7cefb402017-01-18 19:02:52 +0000264 // - By instructions outside of the loop (safe).
265 // * One value may have several outside users, but all outside
266 // uses must be of the same value.
Karthik Bhat76aa6622015-04-20 04:38:33 +0000267 // - By an instruction that is not part of the reduction (not safe).
268 // This is either:
269 // * An instruction type other than PHI or the reduction operation.
270 // * A PHI in the header other than the initial PHI.
271 while (!Worklist.empty()) {
272 Instruction *Cur = Worklist.back();
273 Worklist.pop_back();
274
275 // No Users.
276 // If the instruction has no users then this is a broken chain and can't be
277 // a reduction variable.
278 if (Cur->use_empty())
279 return false;
280
281 bool IsAPhi = isa<PHINode>(Cur);
282
283 // A header PHI use other than the original PHI.
284 if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
285 return false;
286
287 // Reductions of instructions such as Div, and Sub is only possible if the
288 // LHS is the reduction variable.
289 if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
290 !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
291 !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
292 return false;
293
Chad Rosierc94f8e22015-08-27 14:12:17 +0000294 // Any reduction instruction must be of one of the allowed kinds. We ignore
295 // the starting value (the Phi or an AND instruction if the Phi has been
296 // type-promoted).
297 if (Cur != Start) {
298 ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
299 if (!ReduxDesc.isRecurrence())
300 return false;
301 }
Karthik Bhat76aa6622015-04-20 04:38:33 +0000302
303 // A reduction operation must only have one use of the reduction value.
304 if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax &&
305 hasMultipleUsesOf(Cur, VisitedInsts))
306 return false;
307
308 // All inputs to a PHI node must be a reduction value.
309 if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
310 return false;
311
312 if (Kind == RK_IntegerMinMax &&
313 (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
314 ++NumCmpSelectPatternInst;
315 if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
316 ++NumCmpSelectPatternInst;
317
318 // Check whether we found a reduction operator.
Chad Rosierc94f8e22015-08-27 14:12:17 +0000319 FoundReduxOp |= !IsAPhi && Cur != Start;
Karthik Bhat76aa6622015-04-20 04:38:33 +0000320
321 // Process users of current instruction. Push non-PHI nodes after PHI nodes
322 // onto the stack. This way we are going to have seen all inputs to PHI
323 // nodes once we get to them.
324 SmallVector<Instruction *, 8> NonPHIs;
325 SmallVector<Instruction *, 8> PHIs;
326 for (User *U : Cur->users()) {
327 Instruction *UI = cast<Instruction>(U);
328
329 // Check if we found the exit user.
330 BasicBlock *Parent = UI->getParent();
331 if (!TheLoop->contains(Parent)) {
Michael Kuperstein7cefb402017-01-18 19:02:52 +0000332 // If we already know this instruction is used externally, move on to
333 // the next user.
334 if (ExitInstruction == Cur)
335 continue;
336
337 // Exit if you find multiple values used outside or if the header phi
338 // node is being used. In this case the user uses the value of the
339 // previous iteration, in which case we would loose "VF-1" iterations of
340 // the reduction operation if we vectorize.
Karthik Bhat76aa6622015-04-20 04:38:33 +0000341 if (ExitInstruction != nullptr || Cur == Phi)
342 return false;
343
344 // The instruction used by an outside user must be the last instruction
345 // before we feed back to the reduction phi. Otherwise, we loose VF-1
346 // operations on the value.
David Majnemer42531262016-08-12 03:55:06 +0000347 if (!is_contained(Phi->operands(), Cur))
Karthik Bhat76aa6622015-04-20 04:38:33 +0000348 return false;
349
350 ExitInstruction = Cur;
351 continue;
352 }
353
354 // Process instructions only once (termination). Each reduction cycle
355 // value must only be used once, except by phi nodes and min/max
356 // reductions which are represented as a cmp followed by a select.
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000357 InstDesc IgnoredVal(false, nullptr);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000358 if (VisitedInsts.insert(UI).second) {
359 if (isa<PHINode>(UI))
360 PHIs.push_back(UI);
361 else
362 NonPHIs.push_back(UI);
363 } else if (!isa<PHINode>(UI) &&
364 ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
365 !isa<SelectInst>(UI)) ||
Tyler Nowicki0a913102015-06-16 18:07:34 +0000366 !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence()))
Karthik Bhat76aa6622015-04-20 04:38:33 +0000367 return false;
368
369 // Remember that we completed the cycle.
370 if (UI == Phi)
371 FoundStartPHI = true;
372 }
373 Worklist.append(PHIs.begin(), PHIs.end());
374 Worklist.append(NonPHIs.begin(), NonPHIs.end());
375 }
376
377 // This means we have seen one but not the other instruction of the
378 // pattern or more than just a select and cmp.
379 if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
380 NumCmpSelectPatternInst != 2)
381 return false;
382
383 if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
384 return false;
385
Chad Rosiera097bc62018-02-04 15:42:24 +0000386 if (Start != Phi) {
387 // If the starting value is not the same as the phi node, we speculatively
388 // looked through an 'and' instruction when evaluating a potential
389 // arithmetic reduction to determine if it may have been type-promoted.
390 //
391 // We now compute the minimal bit width that is required to represent the
392 // reduction. If this is the same width that was indicated by the 'and', we
393 // can represent the reduction in the smaller type. The 'and' instruction
394 // will be eliminated since it will essentially be a cast instruction that
395 // can be ignore in the cost model. If we compute a different type than we
396 // did when evaluating the 'and', the 'and' will not be eliminated, and we
397 // will end up with different kinds of operations in the recurrence
398 // expression (e.g., RK_IntegerAND, RK_IntegerADD). We give up if this is
399 // the case.
400 //
401 // The vectorizer relies on InstCombine to perform the actual
402 // type-shrinking. It does this by inserting instructions to truncate the
403 // exit value of the reduction to the width indicated by RecurrenceType and
404 // then extend this value back to the original width. If IsSigned is false,
405 // a 'zext' instruction will be generated; otherwise, a 'sext' will be
406 // used.
407 //
408 // TODO: We should not rely on InstCombine to rewrite the reduction in the
409 // smaller type. We should just generate a correctly typed expression
410 // to begin with.
411 Type *ComputedType;
412 std::tie(ComputedType, IsSigned) =
413 computeRecurrenceType(ExitInstruction, DB, AC, DT);
414 if (ComputedType != RecurrenceType)
Chad Rosierc94f8e22015-08-27 14:12:17 +0000415 return false;
416
Chad Rosiera097bc62018-02-04 15:42:24 +0000417 // The recurrence expression will be represented in a narrower type. If
418 // there are any cast instructions that will be unnecessary, collect them
419 // in CastInsts. Note that the 'and' instruction was already included in
420 // this list.
421 //
422 // TODO: A better way to represent this may be to tag in some way all the
423 // instructions that are a part of the reduction. The vectorizer cost
424 // model could then apply the recurrence type to these instructions,
425 // without needing a white list of instructions to ignore.
426 collectCastsToIgnore(TheLoop, ExitInstruction, RecurrenceType, CastInsts);
427 }
428
Karthik Bhat76aa6622015-04-20 04:38:33 +0000429 // We found a reduction var if we have reached the original phi node and we
430 // only have a single instruction with out-of-loop users.
431
432 // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
Tyler Nowicki0a913102015-06-16 18:07:34 +0000433 // is saved as part of the RecurrenceDescriptor.
Karthik Bhat76aa6622015-04-20 04:38:33 +0000434
435 // Save the description of this reduction variable.
Chad Rosierc94f8e22015-08-27 14:12:17 +0000436 RecurrenceDescriptor RD(
437 RdxStart, ExitInstruction, Kind, ReduxDesc.getMinMaxKind(),
438 ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000439 RedDes = RD;
440
441 return true;
442}
443
444/// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
445/// pattern corresponding to a min(X, Y) or max(X, Y).
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000446RecurrenceDescriptor::InstDesc
447RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) {
Karthik Bhat76aa6622015-04-20 04:38:33 +0000448
449 assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
450 "Expect a select instruction");
451 Instruction *Cmp = nullptr;
452 SelectInst *Select = nullptr;
453
454 // We must handle the select(cmp()) as a single instruction. Advance to the
455 // select.
456 if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
457 if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000458 return InstDesc(false, I);
459 return InstDesc(Select, Prev.getMinMaxKind());
Karthik Bhat76aa6622015-04-20 04:38:33 +0000460 }
461
462 // Only handle single use cases for now.
463 if (!(Select = dyn_cast<SelectInst>(I)))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000464 return InstDesc(false, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000465 if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
466 !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000467 return InstDesc(false, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000468 if (!Cmp->hasOneUse())
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000469 return InstDesc(false, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000470
471 Value *CmpLeft;
472 Value *CmpRight;
473
474 // Look for a min/max pattern.
475 if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000476 return InstDesc(Select, MRK_UIntMin);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000477 else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000478 return InstDesc(Select, MRK_UIntMax);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000479 else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000480 return InstDesc(Select, MRK_SIntMax);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000481 else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000482 return InstDesc(Select, MRK_SIntMin);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000483 else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000484 return InstDesc(Select, MRK_FloatMin);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000485 else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000486 return InstDesc(Select, MRK_FloatMax);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000487 else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000488 return InstDesc(Select, MRK_FloatMin);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000489 else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000490 return InstDesc(Select, MRK_FloatMax);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000491
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000492 return InstDesc(false, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000493}
494
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000495RecurrenceDescriptor::InstDesc
Tyler Nowicki0a913102015-06-16 18:07:34 +0000496RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000497 InstDesc &Prev, bool HasFunNoNaNAttr) {
Karthik Bhat76aa6622015-04-20 04:38:33 +0000498 bool FP = I->getType()->isFloatingPointTy();
Tyler Nowickic1a86f52015-08-10 19:51:46 +0000499 Instruction *UAI = Prev.getUnsafeAlgebraInst();
Sanjay Patel629c4112017-11-06 16:27:15 +0000500 if (!UAI && FP && !I->isFast())
Tyler Nowickic1a86f52015-08-10 19:51:46 +0000501 UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
502
Karthik Bhat76aa6622015-04-20 04:38:33 +0000503 switch (I->getOpcode()) {
504 default:
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000505 return InstDesc(false, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000506 case Instruction::PHI:
Tim Northover10a1e8b2016-05-27 16:40:27 +0000507 return InstDesc(I, Prev.getMinMaxKind(), Prev.getUnsafeAlgebraInst());
Karthik Bhat76aa6622015-04-20 04:38:33 +0000508 case Instruction::Sub:
509 case Instruction::Add:
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000510 return InstDesc(Kind == RK_IntegerAdd, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000511 case Instruction::Mul:
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000512 return InstDesc(Kind == RK_IntegerMult, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000513 case Instruction::And:
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000514 return InstDesc(Kind == RK_IntegerAnd, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000515 case Instruction::Or:
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000516 return InstDesc(Kind == RK_IntegerOr, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000517 case Instruction::Xor:
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000518 return InstDesc(Kind == RK_IntegerXor, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000519 case Instruction::FMul:
Tyler Nowickic1a86f52015-08-10 19:51:46 +0000520 return InstDesc(Kind == RK_FloatMult, I, UAI);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000521 case Instruction::FSub:
522 case Instruction::FAdd:
Tyler Nowickic1a86f52015-08-10 19:51:46 +0000523 return InstDesc(Kind == RK_FloatAdd, I, UAI);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000524 case Instruction::FCmp:
525 case Instruction::ICmp:
526 case Instruction::Select:
527 if (Kind != RK_IntegerMinMax &&
528 (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000529 return InstDesc(false, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000530 return isMinMaxSelectCmpPattern(I, Prev);
531 }
532}
533
Tyler Nowicki0a913102015-06-16 18:07:34 +0000534bool RecurrenceDescriptor::hasMultipleUsesOf(
Karthik Bhat76aa6622015-04-20 04:38:33 +0000535 Instruction *I, SmallPtrSetImpl<Instruction *> &Insts) {
536 unsigned NumUses = 0;
537 for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
538 ++Use) {
539 if (Insts.count(dyn_cast<Instruction>(*Use)))
540 ++NumUses;
541 if (NumUses > 1)
542 return true;
543 }
544
545 return false;
546}
Tyler Nowicki0a913102015-06-16 18:07:34 +0000547bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
Chad Rosiera097bc62018-02-04 15:42:24 +0000548 RecurrenceDescriptor &RedDes,
549 DemandedBits *DB, AssumptionCache *AC,
550 DominatorTree *DT) {
Karthik Bhat76aa6622015-04-20 04:38:33 +0000551
Karthik Bhat76aa6622015-04-20 04:38:33 +0000552 BasicBlock *Header = TheLoop->getHeader();
553 Function &F = *Header->getParent();
Nirav Dave8dd66e52016-03-30 15:41:12 +0000554 bool HasFunNoNaNAttr =
555 F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
Karthik Bhat76aa6622015-04-20 04:38:33 +0000556
Chad Rosiera097bc62018-02-04 15:42:24 +0000557 if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
558 AC, DT)) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000559 LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
Karthik Bhat76aa6622015-04-20 04:38:33 +0000560 return true;
561 }
Chad Rosiera097bc62018-02-04 15:42:24 +0000562 if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
563 AC, DT)) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000564 LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
Karthik Bhat76aa6622015-04-20 04:38:33 +0000565 return true;
566 }
Chad Rosiera097bc62018-02-04 15:42:24 +0000567 if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes, DB,
568 AC, DT)) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000569 LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
Karthik Bhat76aa6622015-04-20 04:38:33 +0000570 return true;
571 }
Chad Rosiera097bc62018-02-04 15:42:24 +0000572 if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
573 AC, DT)) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000574 LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
Karthik Bhat76aa6622015-04-20 04:38:33 +0000575 return true;
576 }
Chad Rosiera097bc62018-02-04 15:42:24 +0000577 if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes, DB,
578 AC, DT)) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000579 LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
Karthik Bhat76aa6622015-04-20 04:38:33 +0000580 return true;
581 }
Chad Rosiera097bc62018-02-04 15:42:24 +0000582 if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr, RedDes,
583 DB, AC, DT)) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000584 LLVM_DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
Karthik Bhat76aa6622015-04-20 04:38:33 +0000585 return true;
586 }
Chad Rosiera097bc62018-02-04 15:42:24 +0000587 if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
588 AC, DT)) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000589 LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
Karthik Bhat76aa6622015-04-20 04:38:33 +0000590 return true;
591 }
Chad Rosiera097bc62018-02-04 15:42:24 +0000592 if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
593 AC, DT)) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000594 LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
Karthik Bhat76aa6622015-04-20 04:38:33 +0000595 return true;
596 }
Chad Rosiera097bc62018-02-04 15:42:24 +0000597 if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes, DB,
598 AC, DT)) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000599 LLVM_DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi
600 << "\n");
Karthik Bhat76aa6622015-04-20 04:38:33 +0000601 return true;
602 }
603 // Not a reduction of known type.
604 return false;
605}
606
Ayal Zaks2ff59d42017-06-30 21:05:06 +0000607bool RecurrenceDescriptor::isFirstOrderRecurrence(
608 PHINode *Phi, Loop *TheLoop,
609 DenseMap<Instruction *, Instruction *> &SinkAfter, DominatorTree *DT) {
Matthew Simpson29c997c2016-02-19 17:56:08 +0000610
611 // Ensure the phi node is in the loop header and has two incoming values.
612 if (Phi->getParent() != TheLoop->getHeader() ||
613 Phi->getNumIncomingValues() != 2)
614 return false;
615
616 // Ensure the loop has a preheader and a single latch block. The loop
617 // vectorizer will need the latch to set up the next iteration of the loop.
618 auto *Preheader = TheLoop->getLoopPreheader();
619 auto *Latch = TheLoop->getLoopLatch();
620 if (!Preheader || !Latch)
621 return false;
622
623 // Ensure the phi node's incoming blocks are the loop preheader and latch.
624 if (Phi->getBasicBlockIndex(Preheader) < 0 ||
625 Phi->getBasicBlockIndex(Latch) < 0)
626 return false;
627
628 // Get the previous value. The previous value comes from the latch edge while
629 // the initial value comes form the preheader edge.
630 auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
Ayal Zaks2ff59d42017-06-30 21:05:06 +0000631 if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) ||
632 SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.
Matthew Simpson29c997c2016-02-19 17:56:08 +0000633 return false;
634
Anna Thomasdcdb3252017-04-13 18:59:25 +0000635 // Ensure every user of the phi node is dominated by the previous value.
636 // The dominance requirement ensures the loop vectorizer will not need to
637 // vectorize the initial value prior to the first iteration of the loop.
Ayal Zaks2ff59d42017-06-30 21:05:06 +0000638 // TODO: Consider extending this sinking to handle other kinds of instructions
639 // and expressions, beyond sinking a single cast past Previous.
640 if (Phi->hasOneUse()) {
641 auto *I = Phi->user_back();
642 if (I->isCast() && (I->getParent() == Phi->getParent()) && I->hasOneUse() &&
643 DT->dominates(Previous, I->user_back())) {
Ayal Zaks25e28002017-08-15 08:32:59 +0000644 if (!DT->dominates(Previous, I)) // Otherwise we're good w/o sinking.
645 SinkAfter[I] = Previous;
Ayal Zaks2ff59d42017-06-30 21:05:06 +0000646 return true;
647 }
648 }
649
Matthew Simpson29c997c2016-02-19 17:56:08 +0000650 for (User *U : Phi->users())
Anna Thomas00dc1b72017-04-11 21:02:00 +0000651 if (auto *I = dyn_cast<Instruction>(U)) {
Matthew Simpson29c997c2016-02-19 17:56:08 +0000652 if (!DT->dominates(Previous, I))
653 return false;
Anna Thomas00dc1b72017-04-11 21:02:00 +0000654 }
Matthew Simpson29c997c2016-02-19 17:56:08 +0000655
656 return true;
657}
658
Karthik Bhat76aa6622015-04-20 04:38:33 +0000659/// This function returns the identity element (or neutral element) for
660/// the operation K.
Tyler Nowicki0a913102015-06-16 18:07:34 +0000661Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K,
662 Type *Tp) {
Karthik Bhat76aa6622015-04-20 04:38:33 +0000663 switch (K) {
664 case RK_IntegerXor:
665 case RK_IntegerAdd:
666 case RK_IntegerOr:
667 // Adding, Xoring, Oring zero to a number does not change it.
668 return ConstantInt::get(Tp, 0);
669 case RK_IntegerMult:
670 // Multiplying a number by 1 does not change it.
671 return ConstantInt::get(Tp, 1);
672 case RK_IntegerAnd:
673 // AND-ing a number with an all-1 value does not change it.
674 return ConstantInt::get(Tp, -1, true);
675 case RK_FloatMult:
676 // Multiplying a number by 1 does not change it.
677 return ConstantFP::get(Tp, 1.0L);
678 case RK_FloatAdd:
679 // Adding zero to a number does not change it.
680 return ConstantFP::get(Tp, 0.0L);
681 default:
Tyler Nowicki0a913102015-06-16 18:07:34 +0000682 llvm_unreachable("Unknown recurrence kind");
Karthik Bhat76aa6622015-04-20 04:38:33 +0000683 }
684}
685
Tyler Nowicki0a913102015-06-16 18:07:34 +0000686/// This function translates the recurrence kind to an LLVM binary operator.
687unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) {
Karthik Bhat76aa6622015-04-20 04:38:33 +0000688 switch (Kind) {
689 case RK_IntegerAdd:
690 return Instruction::Add;
691 case RK_IntegerMult:
692 return Instruction::Mul;
693 case RK_IntegerOr:
694 return Instruction::Or;
695 case RK_IntegerAnd:
696 return Instruction::And;
697 case RK_IntegerXor:
698 return Instruction::Xor;
699 case RK_FloatMult:
700 return Instruction::FMul;
701 case RK_FloatAdd:
702 return Instruction::FAdd;
703 case RK_IntegerMinMax:
704 return Instruction::ICmp;
705 case RK_FloatMinMax:
706 return Instruction::FCmp;
707 default:
Tyler Nowicki0a913102015-06-16 18:07:34 +0000708 llvm_unreachable("Unknown recurrence operation");
Karthik Bhat76aa6622015-04-20 04:38:33 +0000709 }
710}
711
James Molloy1bbf15c2015-08-27 09:53:00 +0000712InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
Dorit Nuzman4750c782017-12-14 07:56:31 +0000713 const SCEV *Step, BinaryOperator *BOp,
714 SmallVectorImpl<Instruction *> *Casts)
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000715 : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
James Molloy1bbf15c2015-08-27 09:53:00 +0000716 assert(IK != IK_NoInduction && "Not an induction");
Elena Demikhovskyc434d092016-05-10 07:33:35 +0000717
718 // Start value type should match the induction kind and the value
719 // itself should not be null.
James Molloy1bbf15c2015-08-27 09:53:00 +0000720 assert(StartValue && "StartValue is null");
James Molloy1bbf15c2015-08-27 09:53:00 +0000721 assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
722 "StartValue is not a pointer for pointer induction");
723 assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
724 "StartValue is not an integer for integer induction");
Elena Demikhovskyc434d092016-05-10 07:33:35 +0000725
726 // Check the Step Value. It should be non-zero integer value.
727 assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
728 "Step value is zero");
729
730 assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
731 "Step value should be constant for pointer induction");
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000732 assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
733 "StepValue is not an integer");
734
735 assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
736 "StepValue is not FP for FpInduction");
737 assert((IK != IK_FpInduction || (InductionBinOp &&
738 (InductionBinOp->getOpcode() == Instruction::FAdd ||
739 InductionBinOp->getOpcode() == Instruction::FSub))) &&
740 "Binary opcode should be specified for FP induction");
Dorit Nuzman4750c782017-12-14 07:56:31 +0000741
742 if (Casts) {
743 for (auto &Inst : *Casts) {
744 RedundantCasts.push_back(Inst);
745 }
746 }
James Molloy1bbf15c2015-08-27 09:53:00 +0000747}
748
749int InductionDescriptor::getConsecutiveDirection() const {
Elena Demikhovskyc434d092016-05-10 07:33:35 +0000750 ConstantInt *ConstStep = getConstIntStepValue();
751 if (ConstStep && (ConstStep->isOne() || ConstStep->isMinusOne()))
752 return ConstStep->getSExtValue();
James Molloy1bbf15c2015-08-27 09:53:00 +0000753 return 0;
754}
755
Elena Demikhovskyc434d092016-05-10 07:33:35 +0000756ConstantInt *InductionDescriptor::getConstIntStepValue() const {
757 if (isa<SCEVConstant>(Step))
758 return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
759 return nullptr;
760}
761
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000762bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop,
763 ScalarEvolution *SE,
764 InductionDescriptor &D) {
765
766 // Here we only handle FP induction variables.
767 assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
768
769 if (TheLoop->getHeader() != Phi->getParent())
770 return false;
771
772 // The loop may have multiple entrances or multiple exits; we can analyze
773 // this phi if it has a unique entry value and a unique backedge value.
774 if (Phi->getNumIncomingValues() != 2)
775 return false;
776 Value *BEValue = nullptr, *StartValue = nullptr;
777 if (TheLoop->contains(Phi->getIncomingBlock(0))) {
778 BEValue = Phi->getIncomingValue(0);
779 StartValue = Phi->getIncomingValue(1);
780 } else {
781 assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
Dorit Nuzman4750c782017-12-14 07:56:31 +0000782 "Unexpected Phi node in the loop");
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000783 BEValue = Phi->getIncomingValue(1);
784 StartValue = Phi->getIncomingValue(0);
785 }
786
787 BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
788 if (!BOp)
789 return false;
790
791 Value *Addend = nullptr;
792 if (BOp->getOpcode() == Instruction::FAdd) {
793 if (BOp->getOperand(0) == Phi)
794 Addend = BOp->getOperand(1);
795 else if (BOp->getOperand(1) == Phi)
796 Addend = BOp->getOperand(0);
797 } else if (BOp->getOpcode() == Instruction::FSub)
798 if (BOp->getOperand(0) == Phi)
799 Addend = BOp->getOperand(1);
800
801 if (!Addend)
802 return false;
803
804 // The addend should be loop invariant
805 if (auto *I = dyn_cast<Instruction>(Addend))
806 if (TheLoop->contains(I))
807 return false;
808
809 // FP Step has unknown SCEV
810 const SCEV *Step = SE->getUnknown(Addend);
811 D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
812 return true;
813}
814
Dorit Nuzman4750c782017-12-14 07:56:31 +0000815/// This function is called when we suspect that the update-chain of a phi node
Simon Pilgrima74f4ae2018-04-06 17:01:54 +0000816/// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
817/// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
818/// predicate P under which the SCEV expression for the phi can be the
819/// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
820/// cast instructions that are involved in the update-chain of this induction.
821/// A caller that adds the required runtime predicate can be free to drop these
822/// cast instructions, and compute the phi using \p AR (instead of some scev
Dorit Nuzman4750c782017-12-14 07:56:31 +0000823/// expression with casts).
824///
825/// For example, without a predicate the scev expression can take the following
826/// form:
827/// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
828///
829/// It corresponds to the following IR sequence:
830/// %for.body:
831/// %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
832/// %casted_phi = "ExtTrunc i64 %x"
833/// %add = add i64 %casted_phi, %step
834///
835/// where %x is given in \p PN,
836/// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
837/// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
838/// several forms, for example, such as:
839/// ExtTrunc1: %casted_phi = and %x, 2^n-1
840/// or:
841/// ExtTrunc2: %t = shl %x, m
842/// %casted_phi = ashr %t, m
843///
844/// If we are able to find such sequence, we return the instructions
845/// we found, namely %casted_phi and the instructions on its use-def chain up
846/// to the phi (not including the phi).
Benjamin Kramer802e6252017-12-24 12:46:22 +0000847static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE,
848 const SCEVUnknown *PhiScev,
849 const SCEVAddRecExpr *AR,
850 SmallVectorImpl<Instruction *> &CastInsts) {
Dorit Nuzman4750c782017-12-14 07:56:31 +0000851
852 assert(CastInsts.empty() && "CastInsts is expected to be empty.");
853 auto *PN = cast<PHINode>(PhiScev->getValue());
854 assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression");
855 const Loop *L = AR->getLoop();
856
Simon Pilgrima74f4ae2018-04-06 17:01:54 +0000857 // Find any cast instructions that participate in the def-use chain of
Dorit Nuzman4750c782017-12-14 07:56:31 +0000858 // PhiScev in the loop.
859 // FORNOW/TODO: We currently expect the def-use chain to include only
860 // two-operand instructions, where one of the operands is an invariant.
861 // createAddRecFromPHIWithCasts() currently does not support anything more
862 // involved than that, so we keep the search simple. This can be
863 // extended/generalized as needed.
864
865 auto getDef = [&](const Value *Val) -> Value * {
866 const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
867 if (!BinOp)
868 return nullptr;
869 Value *Op0 = BinOp->getOperand(0);
870 Value *Op1 = BinOp->getOperand(1);
871 Value *Def = nullptr;
872 if (L->isLoopInvariant(Op0))
873 Def = Op1;
874 else if (L->isLoopInvariant(Op1))
875 Def = Op0;
876 return Def;
877 };
878
879 // Look for the instruction that defines the induction via the
880 // loop backedge.
881 BasicBlock *Latch = L->getLoopLatch();
882 if (!Latch)
883 return false;
884 Value *Val = PN->getIncomingValueForBlock(Latch);
885 if (!Val)
886 return false;
887
888 // Follow the def-use chain until the induction phi is reached.
889 // If on the way we encounter a Value that has the same SCEV Expr as the
890 // phi node, we can consider the instructions we visit from that point
891 // as part of the cast-sequence that can be ignored.
892 bool InCastSequence = false;
893 auto *Inst = dyn_cast<Instruction>(Val);
894 while (Val != PN) {
895 // If we encountered a phi node other than PN, or if we left the loop,
896 // we bail out.
897 if (!Inst || !L->contains(Inst)) {
898 return false;
899 }
900 auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val));
901 if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR))
902 InCastSequence = true;
903 if (InCastSequence) {
904 // Only the last instruction in the cast sequence is expected to have
905 // uses outside the induction def-use chain.
906 if (!CastInsts.empty())
907 if (!Inst->hasOneUse())
908 return false;
909 CastInsts.push_back(Inst);
910 }
911 Val = getDef(Val);
912 if (!Val)
913 return false;
914 Inst = dyn_cast<Instruction>(Val);
915 }
916
917 return InCastSequence;
918}
919
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000920bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
Silviu Barangac05bab82016-05-05 15:20:39 +0000921 PredicatedScalarEvolution &PSE,
922 InductionDescriptor &D,
923 bool Assume) {
924 Type *PhiTy = Phi->getType();
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000925
926 // Handle integer and pointer inductions variables.
927 // Now we handle also FP induction but not trying to make a
928 // recurrent expression from the PHI node in-place.
929
930 if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() &&
931 !PhiTy->isFloatTy() && !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
Silviu Barangac05bab82016-05-05 15:20:39 +0000932 return false;
933
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000934 if (PhiTy->isFloatingPointTy())
935 return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);
936
Silviu Barangac05bab82016-05-05 15:20:39 +0000937 const SCEV *PhiScev = PSE.getSCEV(Phi);
938 const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
939
940 // We need this expression to be an AddRecExpr.
941 if (Assume && !AR)
942 AR = PSE.getAsAddRec(Phi);
943
944 if (!AR) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000945 LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
Silviu Barangac05bab82016-05-05 15:20:39 +0000946 return false;
947 }
948
Dorit Nuzman4750c782017-12-14 07:56:31 +0000949 // Record any Cast instructions that participate in the induction update
950 const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
951 // If we started from an UnknownSCEV, and managed to build an addRecurrence
952 // only after enabling Assume with PSCEV, this means we may have encountered
953 // cast instructions that required adding a runtime check in order to
954 // guarantee the correctness of the AddRecurence respresentation of the
955 // induction.
956 if (PhiScev != AR && SymbolicPhi) {
957 SmallVector<Instruction *, 2> Casts;
958 if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts))
959 return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts);
960 }
961
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000962 return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
Silviu Barangac05bab82016-05-05 15:20:39 +0000963}
964
Dorit Nuzman4750c782017-12-14 07:56:31 +0000965bool InductionDescriptor::isInductionPHI(
966 PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
967 InductionDescriptor &D, const SCEV *Expr,
968 SmallVectorImpl<Instruction *> *CastsToIgnore) {
Karthik Bhat24e6cc22015-04-23 08:29:20 +0000969 Type *PhiTy = Phi->getType();
970 // We only handle integer and pointer inductions variables.
971 if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
972 return false;
973
974 // Check that the PHI is consecutive.
Silviu Barangac05bab82016-05-05 15:20:39 +0000975 const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
Karthik Bhat24e6cc22015-04-23 08:29:20 +0000976 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
Silviu Barangac05bab82016-05-05 15:20:39 +0000977
Karthik Bhat24e6cc22015-04-23 08:29:20 +0000978 if (!AR) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000979 LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
Karthik Bhat24e6cc22015-04-23 08:29:20 +0000980 return false;
981 }
982
Michael Kupersteinee31cbe2017-01-10 19:32:30 +0000983 if (AR->getLoop() != TheLoop) {
984 // FIXME: We should treat this as a uniform. Unfortunately, we
985 // don't currently know how to handled uniform PHIs.
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000986 LLVM_DEBUG(
987 dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
Dorit Nuzman4750c782017-12-14 07:56:31 +0000988 return false;
Michael Kupersteinee31cbe2017-01-10 19:32:30 +0000989 }
990
James Molloy1bbf15c2015-08-27 09:53:00 +0000991 Value *StartValue =
992 Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
Karthik Bhat24e6cc22015-04-23 08:29:20 +0000993 const SCEV *Step = AR->getStepRecurrence(*SE);
994 // Calculate the pointer stride and check if it is consecutive.
Elena Demikhovskyc434d092016-05-10 07:33:35 +0000995 // The stride may be a constant or a loop invariant integer value.
996 const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000997 if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
Karthik Bhat24e6cc22015-04-23 08:29:20 +0000998 return false;
999
Karthik Bhat24e6cc22015-04-23 08:29:20 +00001000 if (PhiTy->isIntegerTy()) {
Dorit Nuzman4750c782017-12-14 07:56:31 +00001001 D = InductionDescriptor(StartValue, IK_IntInduction, Step, /*BOp=*/ nullptr,
1002 CastsToIgnore);
Karthik Bhat24e6cc22015-04-23 08:29:20 +00001003 return true;
1004 }
1005
1006 assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
Elena Demikhovskyc434d092016-05-10 07:33:35 +00001007 // Pointer induction should be a constant.
1008 if (!ConstStep)
1009 return false;
1010
1011 ConstantInt *CV = ConstStep->getValue();
Karthik Bhat24e6cc22015-04-23 08:29:20 +00001012 Type *PointerElementType = PhiTy->getPointerElementType();
1013 // The pointer stride cannot be determined if the pointer element type is not
1014 // sized.
1015 if (!PointerElementType->isSized())
1016 return false;
1017
1018 const DataLayout &DL = Phi->getModule()->getDataLayout();
1019 int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
David Majnemerb58f32f2015-06-05 10:52:40 +00001020 if (!Size)
1021 return false;
1022
Karthik Bhat24e6cc22015-04-23 08:29:20 +00001023 int64_t CVSize = CV->getSExtValue();
1024 if (CVSize % Size)
1025 return false;
Elena Demikhovskyc434d092016-05-10 07:33:35 +00001026 auto *StepValue = SE->getConstant(CV->getType(), CVSize / Size,
1027 true /* signed */);
James Molloy1bbf15c2015-08-27 09:53:00 +00001028 D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue);
Karthik Bhat24e6cc22015-04-23 08:29:20 +00001029 return true;
1030}
Ashutosh Nemac5b7b552015-08-19 05:40:42 +00001031
Chandler Carruth4a000882017-06-25 22:45:31 +00001032bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
1033 bool PreserveLCSSA) {
1034 bool Changed = false;
1035
1036 // We re-use a vector for the in-loop predecesosrs.
1037 SmallVector<BasicBlock *, 4> InLoopPredecessors;
1038
1039 auto RewriteExit = [&](BasicBlock *BB) {
1040 assert(InLoopPredecessors.empty() &&
1041 "Must start with an empty predecessors list!");
1042 auto Cleanup = make_scope_exit([&] { InLoopPredecessors.clear(); });
1043
1044 // See if there are any non-loop predecessors of this exit block and
1045 // keep track of the in-loop predecessors.
1046 bool IsDedicatedExit = true;
1047 for (auto *PredBB : predecessors(BB))
1048 if (L->contains(PredBB)) {
1049 if (isa<IndirectBrInst>(PredBB->getTerminator()))
1050 // We cannot rewrite exiting edges from an indirectbr.
1051 return false;
1052
1053 InLoopPredecessors.push_back(PredBB);
1054 } else {
1055 IsDedicatedExit = false;
1056 }
1057
1058 assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!");
1059
1060 // Nothing to do if this is already a dedicated exit.
1061 if (IsDedicatedExit)
1062 return false;
1063
1064 auto *NewExitBB = SplitBlockPredecessors(
Alina Sbirleaab6f84f72018-08-21 23:32:03 +00001065 BB, InLoopPredecessors, ".loopexit", DT, LI, nullptr, PreserveLCSSA);
Chandler Carruth4a000882017-06-25 22:45:31 +00001066
1067 if (!NewExitBB)
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001068 LLVM_DEBUG(
1069 dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
1070 << *L << "\n");
Chandler Carruth4a000882017-06-25 22:45:31 +00001071 else
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001072 LLVM_DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
1073 << NewExitBB->getName() << "\n");
Chandler Carruth4a000882017-06-25 22:45:31 +00001074 return true;
1075 };
1076
1077 // Walk the exit blocks directly rather than building up a data structure for
1078 // them, but only visit each one once.
1079 SmallPtrSet<BasicBlock *, 4> Visited;
1080 for (auto *BB : L->blocks())
1081 for (auto *SuccBB : successors(BB)) {
1082 // We're looking for exit blocks so skip in-loop successors.
1083 if (L->contains(SuccBB))
1084 continue;
1085
1086 // Visit each exit block exactly once.
1087 if (!Visited.insert(SuccBB).second)
1088 continue;
1089
1090 Changed |= RewriteExit(SuccBB);
1091 }
1092
1093 return Changed;
1094}
1095
Adrian Prantl5f8f34e42018-05-01 15:54:18 +00001096/// Returns the instructions that use values defined in the loop.
Ashutosh Nemac5b7b552015-08-19 05:40:42 +00001097SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) {
1098 SmallVector<Instruction *, 8> UsedOutside;
1099
1100 for (auto *Block : L->getBlocks())
1101 // FIXME: I believe that this could use copy_if if the Inst reference could
1102 // be adapted into a pointer.
1103 for (auto &Inst : *Block) {
1104 auto Users = Inst.users();
David Majnemer0a16c222016-08-11 21:15:00 +00001105 if (any_of(Users, [&](User *U) {
Ashutosh Nemac5b7b552015-08-19 05:40:42 +00001106 auto *Use = cast<Instruction>(U);
1107 return !L->contains(Use->getParent());
1108 }))
1109 UsedOutside.push_back(&Inst);
1110 }
1111
1112 return UsedOutside;
1113}
Chandler Carruth31088a92016-02-19 10:45:18 +00001114
1115void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) {
1116 // By definition, all loop passes need the LoopInfo analysis and the
1117 // Dominator tree it depends on. Because they all participate in the loop
1118 // pass manager, they must also preserve these.
1119 AU.addRequired<DominatorTreeWrapperPass>();
1120 AU.addPreserved<DominatorTreeWrapperPass>();
1121 AU.addRequired<LoopInfoWrapperPass>();
1122 AU.addPreserved<LoopInfoWrapperPass>();
1123
1124 // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
1125 // here because users shouldn't directly get them from this header.
1126 extern char &LoopSimplifyID;
1127 extern char &LCSSAID;
1128 AU.addRequiredID(LoopSimplifyID);
1129 AU.addPreservedID(LoopSimplifyID);
1130 AU.addRequiredID(LCSSAID);
1131 AU.addPreservedID(LCSSAID);
Igor Laevskyc3ccf5d2016-10-28 12:57:20 +00001132 // This is used in the LPPassManager to perform LCSSA verification on passes
1133 // which preserve lcssa form
1134 AU.addRequired<LCSSAVerificationPass>();
1135 AU.addPreserved<LCSSAVerificationPass>();
Chandler Carruth31088a92016-02-19 10:45:18 +00001136
1137 // Loop passes are designed to run inside of a loop pass manager which means
1138 // that any function analyses they require must be required by the first loop
1139 // pass in the manager (so that it is computed before the loop pass manager
1140 // runs) and preserved by all loop pasess in the manager. To make this
1141 // reasonably robust, the set needed for most loop passes is maintained here.
1142 // If your loop pass requires an analysis not listed here, you will need to
1143 // carefully audit the loop pass manager nesting structure that results.
1144 AU.addRequired<AAResultsWrapperPass>();
1145 AU.addPreserved<AAResultsWrapperPass>();
1146 AU.addPreserved<BasicAAWrapperPass>();
1147 AU.addPreserved<GlobalsAAWrapperPass>();
1148 AU.addPreserved<SCEVAAWrapperPass>();
1149 AU.addRequired<ScalarEvolutionWrapperPass>();
1150 AU.addPreserved<ScalarEvolutionWrapperPass>();
1151}
1152
1153/// Manually defined generic "LoopPass" dependency initialization. This is used
1154/// to initialize the exact set of passes from above in \c
1155/// getLoopAnalysisUsage. It can be used within a loop pass's initialization
1156/// with:
1157///
1158/// INITIALIZE_PASS_DEPENDENCY(LoopPass)
1159///
1160/// As-if "LoopPass" were a pass.
1161void llvm::initializeLoopPassPass(PassRegistry &Registry) {
1162 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1163 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1164 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
Easwaran Ramane12c4872016-06-09 19:44:46 +00001165 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
Chandler Carruth31088a92016-02-19 10:45:18 +00001166 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
1167 INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
1168 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
1169 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
1170 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
1171}
Adam Nemet963341c2016-04-21 17:33:17 +00001172
Adrian Prantl5f8f34e42018-05-01 15:54:18 +00001173/// Find string metadata for loop
Adam Nemetfe3def72016-04-22 19:10:05 +00001174///
1175/// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
1176/// operand or null otherwise. If the string metadata is not found return
1177/// Optional's not-a-value.
1178Optional<const MDOperand *> llvm::findStringMetadataForLoop(Loop *TheLoop,
1179 StringRef Name) {
Adam Nemet963341c2016-04-21 17:33:17 +00001180 MDNode *LoopID = TheLoop->getLoopID();
Adam Nemetfe3def72016-04-22 19:10:05 +00001181 // Return none if LoopID is false.
Adam Nemet963341c2016-04-21 17:33:17 +00001182 if (!LoopID)
Adam Nemetfe3def72016-04-22 19:10:05 +00001183 return None;
Adam Nemet293be662016-04-21 17:33:20 +00001184
1185 // First operand should refer to the loop id itself.
1186 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
1187 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
1188
Adam Nemet963341c2016-04-21 17:33:17 +00001189 // Iterate over LoopID operands and look for MDString Metadata
1190 for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
1191 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
1192 if (!MD)
1193 continue;
1194 MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1195 if (!S)
1196 continue;
1197 // Return true if MDString holds expected MetaData.
1198 if (Name.equals(S->getString()))
Adam Nemetfe3def72016-04-22 19:10:05 +00001199 switch (MD->getNumOperands()) {
1200 case 1:
1201 return nullptr;
1202 case 2:
1203 return &MD->getOperand(1);
1204 default:
1205 llvm_unreachable("loop metadata has 0 or 1 operand");
1206 }
Adam Nemet963341c2016-04-21 17:33:17 +00001207 }
Adam Nemetfe3def72016-04-22 19:10:05 +00001208 return None;
Adam Nemet963341c2016-04-21 17:33:17 +00001209}
Evgeniy Stepanov122f9842016-06-10 20:03:17 +00001210
Alina Sbirlea7ed58562017-09-15 00:04:16 +00001211/// Does a BFS from a given node to all of its children inside a given loop.
1212/// The returned vector of nodes includes the starting point.
1213SmallVector<DomTreeNode *, 16>
1214llvm::collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop) {
1215 SmallVector<DomTreeNode *, 16> Worklist;
1216 auto AddRegionToWorklist = [&](DomTreeNode *DTN) {
1217 // Only include subregions in the top level loop.
1218 BasicBlock *BB = DTN->getBlock();
1219 if (CurLoop->contains(BB))
1220 Worklist.push_back(DTN);
1221 };
1222
1223 AddRegionToWorklist(N);
1224
1225 for (size_t I = 0; I < Worklist.size(); I++)
1226 for (DomTreeNode *Child : Worklist[I]->getChildren())
1227 AddRegionToWorklist(Child);
1228
1229 return Worklist;
1230}
1231
Marcello Maggionidf3e71e2017-10-04 20:42:46 +00001232void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT = nullptr,
1233 ScalarEvolution *SE = nullptr,
1234 LoopInfo *LI = nullptr) {
Hans Wennborg899809d2017-10-04 21:14:07 +00001235 assert((!DT || L->isLCSSAForm(*DT)) && "Expected LCSSA!");
Marcello Maggionidf3e71e2017-10-04 20:42:46 +00001236 auto *Preheader = L->getLoopPreheader();
1237 assert(Preheader && "Preheader should exist!");
1238
1239 // Now that we know the removal is safe, remove the loop by changing the
1240 // branch from the preheader to go to the single exit block.
1241 //
1242 // Because we're deleting a large chunk of code at once, the sequence in which
1243 // we remove things is very important to avoid invalidation issues.
1244
1245 // Tell ScalarEvolution that the loop is deleted. Do this before
1246 // deleting the loop so that ScalarEvolution can look at the loop
1247 // to determine what it needs to clean up.
1248 if (SE)
1249 SE->forgetLoop(L);
1250
1251 auto *ExitBlock = L->getUniqueExitBlock();
1252 assert(ExitBlock && "Should have a unique exit block!");
1253 assert(L->hasDedicatedExits() && "Loop should have dedicated exits!");
1254
1255 auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator());
1256 assert(OldBr && "Preheader must end with a branch");
1257 assert(OldBr->isUnconditional() && "Preheader must have a single successor");
1258 // Connect the preheader to the exit block. Keep the old edge to the header
1259 // around to perform the dominator tree update in two separate steps
1260 // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
1261 // preheader -> header.
1262 //
1263 //
1264 // 0. Preheader 1. Preheader 2. Preheader
1265 // | | | |
1266 // V | V |
1267 // Header <--\ | Header <--\ | Header <--\
1268 // | | | | | | | | | | |
1269 // | V | | | V | | | V |
1270 // | Body --/ | | Body --/ | | Body --/
1271 // V V V V V
1272 // Exit Exit Exit
1273 //
1274 // By doing this is two separate steps we can perform the dominator tree
1275 // update without using the batch update API.
1276 //
1277 // Even when the loop is never executed, we cannot remove the edge from the
1278 // source block to the exit block. Consider the case where the unexecuted loop
1279 // branches back to an outer loop. If we deleted the loop and removed the edge
1280 // coming to this inner loop, this will break the outer loop structure (by
1281 // deleting the backedge of the outer loop). If the outer loop is indeed a
1282 // non-loop, it will be deleted in a future iteration of loop deletion pass.
1283 IRBuilder<> Builder(OldBr);
1284 Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock);
1285 // Remove the old branch. The conditional branch becomes a new terminator.
1286 OldBr->eraseFromParent();
1287
1288 // Rewrite phis in the exit block to get their inputs from the Preheader
1289 // instead of the exiting block.
Benjamin Kramerc7fc81e2017-12-30 15:27:33 +00001290 for (PHINode &P : ExitBlock->phis()) {
Marcello Maggionidf3e71e2017-10-04 20:42:46 +00001291 // Set the zero'th element of Phi to be from the preheader and remove all
1292 // other incoming values. Given the loop has dedicated exits, all other
1293 // incoming values must be from the exiting blocks.
1294 int PredIndex = 0;
Benjamin Kramerc7fc81e2017-12-30 15:27:33 +00001295 P.setIncomingBlock(PredIndex, Preheader);
Marcello Maggionidf3e71e2017-10-04 20:42:46 +00001296 // Removes all incoming values from all other exiting blocks (including
1297 // duplicate values from an exiting block).
1298 // Nuke all entries except the zero'th entry which is the preheader entry.
1299 // NOTE! We need to remove Incoming Values in the reverse order as done
1300 // below, to keep the indices valid for deletion (removeIncomingValues
1301 // updates getNumIncomingValues and shifts all values down into the operand
1302 // being deleted).
Benjamin Kramerc7fc81e2017-12-30 15:27:33 +00001303 for (unsigned i = 0, e = P.getNumIncomingValues() - 1; i != e; ++i)
1304 P.removeIncomingValue(e - i, false);
Marcello Maggionidf3e71e2017-10-04 20:42:46 +00001305
Benjamin Kramerc7fc81e2017-12-30 15:27:33 +00001306 assert((P.getNumIncomingValues() == 1 &&
1307 P.getIncomingBlock(PredIndex) == Preheader) &&
Marcello Maggionidf3e71e2017-10-04 20:42:46 +00001308 "Should have exactly one value and that's from the preheader!");
Marcello Maggionidf3e71e2017-10-04 20:42:46 +00001309 }
1310
1311 // Disconnect the loop body by branching directly to its exit.
1312 Builder.SetInsertPoint(Preheader->getTerminator());
1313 Builder.CreateBr(ExitBlock);
1314 // Remove the old branch.
1315 Preheader->getTerminator()->eraseFromParent();
1316
Chijun Sima21a8b602018-08-03 05:08:17 +00001317 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
Marcello Maggionidf3e71e2017-10-04 20:42:46 +00001318 if (DT) {
1319 // Update the dominator tree by informing it about the new edge from the
1320 // preheader to the exit.
Chijun Sima21a8b602018-08-03 05:08:17 +00001321 DTU.insertEdge(Preheader, ExitBlock);
Marcello Maggionidf3e71e2017-10-04 20:42:46 +00001322 // Inform the dominator tree about the removed edge.
Chijun Sima21a8b602018-08-03 05:08:17 +00001323 DTU.deleteEdge(Preheader, L->getHeader());
Marcello Maggionidf3e71e2017-10-04 20:42:46 +00001324 }
1325
Serguei Katkova757d652018-01-12 07:24:43 +00001326 // Given LCSSA form is satisfied, we should not have users of instructions
1327 // within the dead loop outside of the loop. However, LCSSA doesn't take
1328 // unreachable uses into account. We handle them here.
1329 // We could do it after drop all references (in this case all users in the
1330 // loop will be already eliminated and we have less work to do but according
1331 // to API doc of User::dropAllReferences only valid operation after dropping
1332 // references, is deletion. So let's substitute all usages of
1333 // instruction from the loop with undef value of corresponding type first.
1334 for (auto *Block : L->blocks())
1335 for (Instruction &I : *Block) {
1336 auto *Undef = UndefValue::get(I.getType());
1337 for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E;) {
1338 Use &U = *UI;
1339 ++UI;
1340 if (auto *Usr = dyn_cast<Instruction>(U.getUser()))
1341 if (L->contains(Usr->getParent()))
1342 continue;
1343 // If we have a DT then we can check that uses outside a loop only in
1344 // unreachable block.
1345 if (DT)
1346 assert(!DT->isReachableFromEntry(U) &&
1347 "Unexpected user in reachable block");
1348 U.set(Undef);
1349 }
1350 }
1351
Marcello Maggionidf3e71e2017-10-04 20:42:46 +00001352 // Remove the block from the reference counting scheme, so that we can
1353 // delete it freely later.
1354 for (auto *Block : L->blocks())
1355 Block->dropAllReferences();
1356
1357 if (LI) {
1358 // Erase the instructions and the blocks without having to worry
1359 // about ordering because we already dropped the references.
1360 // NOTE: This iteration is safe because erasing the block does not remove
1361 // its entry from the loop's block list. We do that in the next section.
1362 for (Loop::block_iterator LpI = L->block_begin(), LpE = L->block_end();
1363 LpI != LpE; ++LpI)
1364 (*LpI)->eraseFromParent();
1365
1366 // Finally, the blocks from loopinfo. This has to happen late because
1367 // otherwise our loop iterators won't work.
1368
1369 SmallPtrSet<BasicBlock *, 8> blocks;
1370 blocks.insert(L->block_begin(), L->block_end());
1371 for (BasicBlock *BB : blocks)
1372 LI->removeBlock(BB);
1373
1374 // The last step is to update LoopInfo now that we've eliminated this loop.
1375 LI->erase(L);
1376 }
1377}
1378
Dehao Chen41d72a82016-11-17 01:17:02 +00001379Optional<unsigned> llvm::getLoopEstimatedTripCount(Loop *L) {
1380 // Only support loops with a unique exiting block, and a latch.
1381 if (!L->getExitingBlock())
1382 return None;
1383
Hiroshi Inoued24ddcd2018-01-19 10:55:29 +00001384 // Get the branch weights for the loop's backedge.
Dehao Chen41d72a82016-11-17 01:17:02 +00001385 BranchInst *LatchBR =
1386 dyn_cast<BranchInst>(L->getLoopLatch()->getTerminator());
1387 if (!LatchBR || LatchBR->getNumSuccessors() != 2)
1388 return None;
1389
1390 assert((LatchBR->getSuccessor(0) == L->getHeader() ||
1391 LatchBR->getSuccessor(1) == L->getHeader()) &&
1392 "At least one edge out of the latch must go to the header");
1393
1394 // To estimate the number of times the loop body was executed, we want to
1395 // know the number of times the backedge was taken, vs. the number of times
1396 // we exited the loop.
Dehao Chen41d72a82016-11-17 01:17:02 +00001397 uint64_t TrueVal, FalseVal;
Michael Kupersteinb151a642016-11-30 21:13:57 +00001398 if (!LatchBR->extractProfMetadata(TrueVal, FalseVal))
Dehao Chen41d72a82016-11-17 01:17:02 +00001399 return None;
1400
Michael Kupersteinb151a642016-11-30 21:13:57 +00001401 if (!TrueVal || !FalseVal)
1402 return 0;
Dehao Chen41d72a82016-11-17 01:17:02 +00001403
Michael Kupersteinb151a642016-11-30 21:13:57 +00001404 // Divide the count of the backedge by the count of the edge exiting the loop,
1405 // rounding to nearest.
Dehao Chen41d72a82016-11-17 01:17:02 +00001406 if (LatchBR->getSuccessor(0) == L->getHeader())
Michael Kupersteinb151a642016-11-30 21:13:57 +00001407 return (TrueVal + (FalseVal / 2)) / FalseVal;
Dehao Chen41d72a82016-11-17 01:17:02 +00001408 else
Michael Kupersteinb151a642016-11-30 21:13:57 +00001409 return (FalseVal + (TrueVal / 2)) / TrueVal;
Dehao Chen41d72a82016-11-17 01:17:02 +00001410}
Amara Emersoncf9daa32017-05-09 10:43:25 +00001411
David Green6cb64782018-08-15 10:59:41 +00001412bool llvm::hasIterationCountInvariantInParent(Loop *InnerLoop,
1413 ScalarEvolution &SE) {
David Green395b80c2018-08-11 06:57:28 +00001414 Loop *OuterL = InnerLoop->getParentLoop();
1415 if (!OuterL)
1416 return true;
1417
1418 // Get the backedge taken count for the inner loop
1419 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1420 const SCEV *InnerLoopBECountSC = SE.getExitCount(InnerLoop, InnerLoopLatch);
1421 if (isa<SCEVCouldNotCompute>(InnerLoopBECountSC) ||
1422 !InnerLoopBECountSC->getType()->isIntegerTy())
1423 return false;
1424
1425 // Get whether count is invariant to the outer loop
1426 ScalarEvolution::LoopDisposition LD =
1427 SE.getLoopDisposition(InnerLoopBECountSC, OuterL);
1428 if (LD != ScalarEvolution::LoopInvariant)
1429 return false;
1430
1431 return true;
1432}
1433
Adrian Prantl5f8f34e42018-05-01 15:54:18 +00001434/// Adds a 'fast' flag to floating point operations.
Amara Emersoncf9daa32017-05-09 10:43:25 +00001435static Value *addFastMathFlag(Value *V) {
1436 if (isa<FPMathOperator>(V)) {
1437 FastMathFlags Flags;
Sanjay Patel629c4112017-11-06 16:27:15 +00001438 Flags.setFast();
Amara Emersoncf9daa32017-05-09 10:43:25 +00001439 cast<Instruction>(V)->setFastMathFlags(Flags);
1440 }
1441 return V;
1442}
1443
Vikram TV6594dc32018-09-10 05:05:08 +00001444Value *llvm::createMinMaxOp(IRBuilder<> &Builder,
1445 RecurrenceDescriptor::MinMaxRecurrenceKind RK,
1446 Value *Left, Value *Right) {
1447 CmpInst::Predicate P = CmpInst::ICMP_NE;
1448 switch (RK) {
1449 default:
1450 llvm_unreachable("Unknown min/max recurrence kind");
1451 case RecurrenceDescriptor::MRK_UIntMin:
1452 P = CmpInst::ICMP_ULT;
1453 break;
1454 case RecurrenceDescriptor::MRK_UIntMax:
1455 P = CmpInst::ICMP_UGT;
1456 break;
1457 case RecurrenceDescriptor::MRK_SIntMin:
1458 P = CmpInst::ICMP_SLT;
1459 break;
1460 case RecurrenceDescriptor::MRK_SIntMax:
1461 P = CmpInst::ICMP_SGT;
1462 break;
1463 case RecurrenceDescriptor::MRK_FloatMin:
1464 P = CmpInst::FCMP_OLT;
1465 break;
1466 case RecurrenceDescriptor::MRK_FloatMax:
1467 P = CmpInst::FCMP_OGT;
1468 break;
1469 }
1470
1471 // We only match FP sequences that are 'fast', so we can unconditionally
1472 // set it on any generated instructions.
1473 IRBuilder<>::FastMathFlagGuard FMFG(Builder);
1474 FastMathFlags FMF;
1475 FMF.setFast();
1476 Builder.setFastMathFlags(FMF);
1477
1478 Value *Cmp;
1479 if (RK == RecurrenceDescriptor::MRK_FloatMin ||
1480 RK == RecurrenceDescriptor::MRK_FloatMax)
1481 Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
1482 else
1483 Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
1484
1485 Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
1486 return Select;
1487}
1488
Simon Pilgrim23c21822018-04-09 15:44:20 +00001489// Helper to generate an ordered reduction.
1490Value *
1491llvm::getOrderedReduction(IRBuilder<> &Builder, Value *Acc, Value *Src,
1492 unsigned Op,
1493 RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind,
1494 ArrayRef<Value *> RedOps) {
1495 unsigned VF = Src->getType()->getVectorNumElements();
1496
1497 // Extract and apply reduction ops in ascending order:
1498 // e.g. ((((Acc + Scl[0]) + Scl[1]) + Scl[2]) + ) ... + Scl[VF-1]
1499 Value *Result = Acc;
1500 for (unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
1501 Value *Ext =
1502 Builder.CreateExtractElement(Src, Builder.getInt32(ExtractIdx));
1503
1504 if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
1505 Result = Builder.CreateBinOp((Instruction::BinaryOps)Op, Result, Ext,
1506 "bin.rdx");
1507 } else {
1508 assert(MinMaxKind != RecurrenceDescriptor::MRK_Invalid &&
1509 "Invalid min/max");
Vikram TV6594dc32018-09-10 05:05:08 +00001510 Result = createMinMaxOp(Builder, MinMaxKind, Result, Ext);
Simon Pilgrim23c21822018-04-09 15:44:20 +00001511 }
1512
1513 if (!RedOps.empty())
1514 propagateIRFlags(Result, RedOps);
1515 }
1516
1517 return Result;
1518}
1519
Amara Emersoncf9daa32017-05-09 10:43:25 +00001520// Helper to generate a log2 shuffle reduction.
Amara Emerson836b0f42017-05-10 09:42:49 +00001521Value *
1522llvm::getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op,
1523 RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind,
1524 ArrayRef<Value *> RedOps) {
Amara Emersoncf9daa32017-05-09 10:43:25 +00001525 unsigned VF = Src->getType()->getVectorNumElements();
1526 // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
1527 // and vector ops, reducing the set of values being computed by half each
1528 // round.
1529 assert(isPowerOf2_32(VF) &&
1530 "Reduction emission only supported for pow2 vectors!");
1531 Value *TmpVec = Src;
1532 SmallVector<Constant *, 32> ShuffleMask(VF, nullptr);
1533 for (unsigned i = VF; i != 1; i >>= 1) {
1534 // Move the upper half of the vector to the lower half.
1535 for (unsigned j = 0; j != i / 2; ++j)
1536 ShuffleMask[j] = Builder.getInt32(i / 2 + j);
1537
1538 // Fill the rest of the mask with undef.
1539 std::fill(&ShuffleMask[i / 2], ShuffleMask.end(),
1540 UndefValue::get(Builder.getInt32Ty()));
1541
1542 Value *Shuf = Builder.CreateShuffleVector(
1543 TmpVec, UndefValue::get(TmpVec->getType()),
1544 ConstantVector::get(ShuffleMask), "rdx.shuf");
1545
1546 if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
1547 // Floating point operations had to be 'fast' to enable the reduction.
1548 TmpVec = addFastMathFlag(Builder.CreateBinOp((Instruction::BinaryOps)Op,
1549 TmpVec, Shuf, "bin.rdx"));
1550 } else {
1551 assert(MinMaxKind != RecurrenceDescriptor::MRK_Invalid &&
1552 "Invalid min/max");
Vikram TV6594dc32018-09-10 05:05:08 +00001553 TmpVec = createMinMaxOp(Builder, MinMaxKind, TmpVec, Shuf);
Amara Emersoncf9daa32017-05-09 10:43:25 +00001554 }
1555 if (!RedOps.empty())
1556 propagateIRFlags(TmpVec, RedOps);
1557 }
1558 // The result is in the first element of the vector.
1559 return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
1560}
1561
1562/// Create a simple vector reduction specified by an opcode and some
1563/// flags (if generating min/max reductions).
1564Value *llvm::createSimpleTargetReduction(
1565 IRBuilder<> &Builder, const TargetTransformInfo *TTI, unsigned Opcode,
1566 Value *Src, TargetTransformInfo::ReductionFlags Flags,
1567 ArrayRef<Value *> RedOps) {
1568 assert(isa<VectorType>(Src->getType()) && "Type must be a vector");
1569
1570 Value *ScalarUdf = UndefValue::get(Src->getType()->getVectorElementType());
1571 std::function<Value*()> BuildFunc;
1572 using RD = RecurrenceDescriptor;
1573 RD::MinMaxRecurrenceKind MinMaxKind = RD::MRK_Invalid;
1574 // TODO: Support creating ordered reductions.
Sanjay Patel1ea7b6f2017-12-06 19:11:23 +00001575 FastMathFlags FMFFast;
1576 FMFFast.setFast();
Amara Emersoncf9daa32017-05-09 10:43:25 +00001577
1578 switch (Opcode) {
1579 case Instruction::Add:
1580 BuildFunc = [&]() { return Builder.CreateAddReduce(Src); };
1581 break;
1582 case Instruction::Mul:
1583 BuildFunc = [&]() { return Builder.CreateMulReduce(Src); };
1584 break;
1585 case Instruction::And:
1586 BuildFunc = [&]() { return Builder.CreateAndReduce(Src); };
1587 break;
1588 case Instruction::Or:
1589 BuildFunc = [&]() { return Builder.CreateOrReduce(Src); };
1590 break;
1591 case Instruction::Xor:
1592 BuildFunc = [&]() { return Builder.CreateXorReduce(Src); };
1593 break;
1594 case Instruction::FAdd:
1595 BuildFunc = [&]() {
1596 auto Rdx = Builder.CreateFAddReduce(ScalarUdf, Src);
Sanjay Patel1ea7b6f2017-12-06 19:11:23 +00001597 cast<CallInst>(Rdx)->setFastMathFlags(FMFFast);
Amara Emersoncf9daa32017-05-09 10:43:25 +00001598 return Rdx;
1599 };
1600 break;
1601 case Instruction::FMul:
1602 BuildFunc = [&]() {
1603 auto Rdx = Builder.CreateFMulReduce(ScalarUdf, Src);
Sanjay Patel1ea7b6f2017-12-06 19:11:23 +00001604 cast<CallInst>(Rdx)->setFastMathFlags(FMFFast);
Amara Emersoncf9daa32017-05-09 10:43:25 +00001605 return Rdx;
1606 };
1607 break;
1608 case Instruction::ICmp:
1609 if (Flags.IsMaxOp) {
1610 MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMax : RD::MRK_UIntMax;
1611 BuildFunc = [&]() {
1612 return Builder.CreateIntMaxReduce(Src, Flags.IsSigned);
1613 };
1614 } else {
1615 MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMin : RD::MRK_UIntMin;
1616 BuildFunc = [&]() {
1617 return Builder.CreateIntMinReduce(Src, Flags.IsSigned);
1618 };
1619 }
1620 break;
1621 case Instruction::FCmp:
1622 if (Flags.IsMaxOp) {
1623 MinMaxKind = RD::MRK_FloatMax;
1624 BuildFunc = [&]() { return Builder.CreateFPMaxReduce(Src, Flags.NoNaN); };
1625 } else {
1626 MinMaxKind = RD::MRK_FloatMin;
1627 BuildFunc = [&]() { return Builder.CreateFPMinReduce(Src, Flags.NoNaN); };
1628 }
1629 break;
1630 default:
1631 llvm_unreachable("Unhandled opcode");
1632 break;
1633 }
1634 if (TTI->useReductionIntrinsic(Opcode, Src->getType(), Flags))
1635 return BuildFunc();
1636 return getShuffleReduction(Builder, Src, Opcode, MinMaxKind, RedOps);
1637}
1638
1639/// Create a vector reduction using a given recurrence descriptor.
Sanjay Patel3e069f52017-12-06 19:37:00 +00001640Value *llvm::createTargetReduction(IRBuilder<> &B,
Amara Emersoncf9daa32017-05-09 10:43:25 +00001641 const TargetTransformInfo *TTI,
1642 RecurrenceDescriptor &Desc, Value *Src,
1643 bool NoNaN) {
1644 // TODO: Support in-order reductions based on the recurrence descriptor.
Sanjay Patel3e069f52017-12-06 19:37:00 +00001645 using RD = RecurrenceDescriptor;
1646 RD::RecurrenceKind RecKind = Desc.getRecurrenceKind();
Amara Emersoncf9daa32017-05-09 10:43:25 +00001647 TargetTransformInfo::ReductionFlags Flags;
1648 Flags.NoNaN = NoNaN;
Amara Emersoncf9daa32017-05-09 10:43:25 +00001649 switch (RecKind) {
Sanjay Patel3e069f52017-12-06 19:37:00 +00001650 case RD::RK_FloatAdd:
1651 return createSimpleTargetReduction(B, TTI, Instruction::FAdd, Src, Flags);
1652 case RD::RK_FloatMult:
1653 return createSimpleTargetReduction(B, TTI, Instruction::FMul, Src, Flags);
1654 case RD::RK_IntegerAdd:
1655 return createSimpleTargetReduction(B, TTI, Instruction::Add, Src, Flags);
1656 case RD::RK_IntegerMult:
1657 return createSimpleTargetReduction(B, TTI, Instruction::Mul, Src, Flags);
1658 case RD::RK_IntegerAnd:
1659 return createSimpleTargetReduction(B, TTI, Instruction::And, Src, Flags);
1660 case RD::RK_IntegerOr:
1661 return createSimpleTargetReduction(B, TTI, Instruction::Or, Src, Flags);
1662 case RD::RK_IntegerXor:
1663 return createSimpleTargetReduction(B, TTI, Instruction::Xor, Src, Flags);
1664 case RD::RK_IntegerMinMax: {
1665 RD::MinMaxRecurrenceKind MMKind = Desc.getMinMaxRecurrenceKind();
1666 Flags.IsMaxOp = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_UIntMax);
1667 Flags.IsSigned = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_SIntMin);
1668 return createSimpleTargetReduction(B, TTI, Instruction::ICmp, Src, Flags);
Amara Emersoncf9daa32017-05-09 10:43:25 +00001669 }
Sanjay Patel3e069f52017-12-06 19:37:00 +00001670 case RD::RK_FloatMinMax: {
1671 Flags.IsMaxOp = Desc.getMinMaxRecurrenceKind() == RD::MRK_FloatMax;
1672 return createSimpleTargetReduction(B, TTI, Instruction::FCmp, Src, Flags);
Amara Emersoncf9daa32017-05-09 10:43:25 +00001673 }
1674 default:
1675 llvm_unreachable("Unhandled RecKind");
1676 }
1677}
1678
Dinar Temirbulatova61f4b82017-07-19 10:02:07 +00001679void llvm::propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue) {
1680 auto *VecOp = dyn_cast<Instruction>(I);
1681 if (!VecOp)
1682 return;
1683 auto *Intersection = (OpValue == nullptr) ? dyn_cast<Instruction>(VL[0])
1684 : dyn_cast<Instruction>(OpValue);
1685 if (!Intersection)
1686 return;
1687 const unsigned Opcode = Intersection->getOpcode();
1688 VecOp->copyIRFlags(Intersection);
1689 for (auto *V : VL) {
1690 auto *Instr = dyn_cast<Instruction>(V);
1691 if (!Instr)
1692 continue;
1693 if (OpValue == nullptr || Opcode == Instr->getOpcode())
1694 VecOp->andIRFlags(V);
Amara Emersoncf9daa32017-05-09 10:43:25 +00001695 }
1696}