1 //===-- LoopUtils.cpp - Loop Utility functions -------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines common loop utility functions.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Analysis/LoopInfo.h"
15 #include "llvm/IR/Instructions.h"
16 #include "llvm/IR/PatternMatch.h"
17 #include "llvm/IR/ValueHandle.h"
18 #include "llvm/Support/Debug.h"
19 #include "llvm/Analysis/ScalarEvolution.h"
20 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
21 #include "llvm/IR/Module.h"
22 #include "llvm/Transforms/Utils/LoopUtils.h"
25 using namespace llvm::PatternMatch;
27 #define DEBUG_TYPE "loop-utils"
29 bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
30 SmallPtrSetImpl<Instruction *> &Set) {
31 for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
32 if (!Set.count(dyn_cast<Instruction>(*Use)))
37 bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
38 Loop *TheLoop, bool HasFunNoNaNAttr,
39 RecurrenceDescriptor &RedDes) {
40 if (Phi->getNumIncomingValues() != 2)
43 // Reduction variables are only found in the loop header block.
44 if (Phi->getParent() != TheLoop->getHeader())
47 // Obtain the reduction start value from the value that comes from the loop
49 Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
51 // ExitInstruction is the single value which is used outside the loop.
52 // We only allow for a single reduction value to be used outside the loop.
53 // This includes users of the reduction, variables (which form a cycle
54 // which ends in the phi node).
55 Instruction *ExitInstruction = nullptr;
56 // Indicates that we found a reduction operation in our scan.
57 bool FoundReduxOp = false;
59 // We start with the PHI node and scan for all of the users of this
60 // instruction. All users must be instructions that can be used as reduction
61 // variables (such as ADD). We must have a single out-of-block user. The cycle
62 // must include the original PHI.
63 bool FoundStartPHI = false;
65 // To recognize min/max patterns formed by a icmp select sequence, we store
66 // the number of instruction we saw from the recognized min/max pattern,
67 // to make sure we only see exactly the two instructions.
68 unsigned NumCmpSelectPatternInst = 0;
69 InstDesc ReduxDesc(false, nullptr);
71 SmallPtrSet<Instruction *, 8> VisitedInsts;
72 SmallVector<Instruction *, 8> Worklist;
73 Worklist.push_back(Phi);
74 VisitedInsts.insert(Phi);
76 // A value in the reduction can be used:
77 // - By the reduction:
78 // - Reduction operation:
79 // - One use of reduction value (safe).
80 // - Multiple use of reduction value (not safe).
82 // - All uses of the PHI must be the reduction (safe).
83 // - Otherwise, not safe.
84 // - By one instruction outside of the loop (safe).
85 // - By further instructions outside of the loop (not safe).
86 // - By an instruction that is not part of the reduction (not safe).
88 // * An instruction type other than PHI or the reduction operation.
89 // * A PHI in the header other than the initial PHI.
90 while (!Worklist.empty()) {
91 Instruction *Cur = Worklist.back();
95 // If the instruction has no users then this is a broken chain and can't be
96 // a reduction variable.
100 bool IsAPhi = isa<PHINode>(Cur);
102 // A header PHI use other than the original PHI.
103 if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
106 // Reductions of instructions such as Div, and Sub is only possible if the
107 // LHS is the reduction variable.
108 if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
109 !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
110 !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
113 // Any reduction instruction must be of one of the allowed kinds.
114 ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
115 if (!ReduxDesc.isRecurrence())
118 // A reduction operation must only have one use of the reduction value.
119 if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax &&
120 hasMultipleUsesOf(Cur, VisitedInsts))
123 // All inputs to a PHI node must be a reduction value.
124 if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
127 if (Kind == RK_IntegerMinMax &&
128 (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
129 ++NumCmpSelectPatternInst;
130 if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
131 ++NumCmpSelectPatternInst;
133 // Check whether we found a reduction operator.
134 FoundReduxOp |= !IsAPhi;
136 // Process users of current instruction. Push non-PHI nodes after PHI nodes
137 // onto the stack. This way we are going to have seen all inputs to PHI
138 // nodes once we get to them.
139 SmallVector<Instruction *, 8> NonPHIs;
140 SmallVector<Instruction *, 8> PHIs;
141 for (User *U : Cur->users()) {
142 Instruction *UI = cast<Instruction>(U);
144 // Check if we found the exit user.
145 BasicBlock *Parent = UI->getParent();
146 if (!TheLoop->contains(Parent)) {
147 // Exit if you find multiple outside users or if the header phi node is
148 // being used. In this case the user uses the value of the previous
149 // iteration, in which case we would loose "VF-1" iterations of the
150 // reduction operation if we vectorize.
151 if (ExitInstruction != nullptr || Cur == Phi)
154 // The instruction used by an outside user must be the last instruction
155 // before we feed back to the reduction phi. Otherwise, we loose VF-1
156 // operations on the value.
157 if (std::find(Phi->op_begin(), Phi->op_end(), Cur) == Phi->op_end())
160 ExitInstruction = Cur;
164 // Process instructions only once (termination). Each reduction cycle
165 // value must only be used once, except by phi nodes and min/max
166 // reductions which are represented as a cmp followed by a select.
167 InstDesc IgnoredVal(false, nullptr);
168 if (VisitedInsts.insert(UI).second) {
169 if (isa<PHINode>(UI))
172 NonPHIs.push_back(UI);
173 } else if (!isa<PHINode>(UI) &&
174 ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
175 !isa<SelectInst>(UI)) ||
176 !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence()))
179 // Remember that we completed the cycle.
181 FoundStartPHI = true;
183 Worklist.append(PHIs.begin(), PHIs.end());
184 Worklist.append(NonPHIs.begin(), NonPHIs.end());
187 // This means we have seen one but not the other instruction of the
188 // pattern or more than just a select and cmp.
189 if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
190 NumCmpSelectPatternInst != 2)
193 if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
196 // We found a reduction var if we have reached the original phi node and we
197 // only have a single instruction with out-of-loop users.
199 // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
200 // is saved as part of the RecurrenceDescriptor.
202 // Save the description of this reduction variable.
203 RecurrenceDescriptor RD(RdxStart, ExitInstruction, Kind,
204 ReduxDesc.getMinMaxKind(),
205 ReduxDesc.getUnsafeAlgebraInst());
212 /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
213 /// pattern corresponding to a min(X, Y) or max(X, Y).
214 RecurrenceDescriptor::InstDesc
215 RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) {
217 assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
218 "Expect a select instruction");
219 Instruction *Cmp = nullptr;
220 SelectInst *Select = nullptr;
222 // We must handle the select(cmp()) as a single instruction. Advance to the
224 if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
225 if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
226 return InstDesc(false, I);
227 return InstDesc(Select, Prev.getMinMaxKind());
230 // Only handle single use cases for now.
231 if (!(Select = dyn_cast<SelectInst>(I)))
232 return InstDesc(false, I);
233 if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
234 !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
235 return InstDesc(false, I);
236 if (!Cmp->hasOneUse())
237 return InstDesc(false, I);
242 // Look for a min/max pattern.
243 if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
244 return InstDesc(Select, MRK_UIntMin);
245 else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
246 return InstDesc(Select, MRK_UIntMax);
247 else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
248 return InstDesc(Select, MRK_SIntMax);
249 else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
250 return InstDesc(Select, MRK_SIntMin);
251 else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
252 return InstDesc(Select, MRK_FloatMin);
253 else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
254 return InstDesc(Select, MRK_FloatMax);
255 else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
256 return InstDesc(Select, MRK_FloatMin);
257 else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
258 return InstDesc(Select, MRK_FloatMax);
260 return InstDesc(false, I);
263 RecurrenceDescriptor::InstDesc
264 RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
265 InstDesc &Prev, bool HasFunNoNaNAttr) {
266 bool FP = I->getType()->isFloatingPointTy();
267 Instruction *UAI = Prev.getUnsafeAlgebraInst();
268 if (!UAI && FP && !I->hasUnsafeAlgebra())
269 UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
271 switch (I->getOpcode()) {
273 return InstDesc(false, I);
274 case Instruction::PHI:
276 (Kind != RK_FloatMult && Kind != RK_FloatAdd && Kind != RK_FloatMinMax))
277 return InstDesc(false, I);
278 return InstDesc(I, Prev.getMinMaxKind());
279 case Instruction::Sub:
280 case Instruction::Add:
281 return InstDesc(Kind == RK_IntegerAdd, I);
282 case Instruction::Mul:
283 return InstDesc(Kind == RK_IntegerMult, I);
284 case Instruction::And:
285 return InstDesc(Kind == RK_IntegerAnd, I);
286 case Instruction::Or:
287 return InstDesc(Kind == RK_IntegerOr, I);
288 case Instruction::Xor:
289 return InstDesc(Kind == RK_IntegerXor, I);
290 case Instruction::FMul:
291 return InstDesc(Kind == RK_FloatMult, I, UAI);
292 case Instruction::FSub:
293 case Instruction::FAdd:
294 return InstDesc(Kind == RK_FloatAdd, I, UAI);
295 case Instruction::FCmp:
296 case Instruction::ICmp:
297 case Instruction::Select:
298 if (Kind != RK_IntegerMinMax &&
299 (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
300 return InstDesc(false, I);
301 return isMinMaxSelectCmpPattern(I, Prev);
305 bool RecurrenceDescriptor::hasMultipleUsesOf(
306 Instruction *I, SmallPtrSetImpl<Instruction *> &Insts) {
307 unsigned NumUses = 0;
308 for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
310 if (Insts.count(dyn_cast<Instruction>(*Use)))
318 bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
319 RecurrenceDescriptor &RedDes) {
321 bool HasFunNoNaNAttr = false;
322 BasicBlock *Header = TheLoop->getHeader();
323 Function &F = *Header->getParent();
324 if (F.hasFnAttribute("no-nans-fp-math"))
326 F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
328 if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
329 DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
332 if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
333 DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
336 if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes)) {
337 DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
340 if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes)) {
341 DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
344 if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes)) {
345 DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
348 if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr,
350 DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
353 if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
354 DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
357 if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
358 DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
361 if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) {
362 DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi << "\n");
365 // Not a reduction of known type.
369 /// This function returns the identity element (or neutral element) for
371 Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K,
377 // Adding, Xoring, Oring zero to a number does not change it.
378 return ConstantInt::get(Tp, 0);
380 // Multiplying a number by 1 does not change it.
381 return ConstantInt::get(Tp, 1);
383 // AND-ing a number with an all-1 value does not change it.
384 return ConstantInt::get(Tp, -1, true);
386 // Multiplying a number by 1 does not change it.
387 return ConstantFP::get(Tp, 1.0L);
389 // Adding zero to a number does not change it.
390 return ConstantFP::get(Tp, 0.0L);
392 llvm_unreachable("Unknown recurrence kind");
396 /// This function translates the recurrence kind to an LLVM binary operator.
397 unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) {
400 return Instruction::Add;
402 return Instruction::Mul;
404 return Instruction::Or;
406 return Instruction::And;
408 return Instruction::Xor;
410 return Instruction::FMul;
412 return Instruction::FAdd;
413 case RK_IntegerMinMax:
414 return Instruction::ICmp;
416 return Instruction::FCmp;
418 llvm_unreachable("Unknown recurrence operation");
422 Value *RecurrenceDescriptor::createMinMaxOp(IRBuilder<> &Builder,
423 MinMaxRecurrenceKind RK,
424 Value *Left, Value *Right) {
425 CmpInst::Predicate P = CmpInst::ICMP_NE;
428 llvm_unreachable("Unknown min/max recurrence kind");
430 P = CmpInst::ICMP_ULT;
433 P = CmpInst::ICMP_UGT;
436 P = CmpInst::ICMP_SLT;
439 P = CmpInst::ICMP_SGT;
442 P = CmpInst::FCMP_OLT;
445 P = CmpInst::FCMP_OGT;
450 if (RK == MRK_FloatMin || RK == MRK_FloatMax)
451 Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
453 Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
455 Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
459 bool llvm::isInductionPHI(PHINode *Phi, ScalarEvolution *SE,
460 ConstantInt *&StepValue) {
461 Type *PhiTy = Phi->getType();
462 // We only handle integer and pointer inductions variables.
463 if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
466 // Check that the PHI is consecutive.
467 const SCEV *PhiScev = SE->getSCEV(Phi);
468 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
470 DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
474 const SCEV *Step = AR->getStepRecurrence(*SE);
475 // Calculate the pointer stride and check if it is consecutive.
476 const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
480 ConstantInt *CV = C->getValue();
481 if (PhiTy->isIntegerTy()) {
486 assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
487 Type *PointerElementType = PhiTy->getPointerElementType();
488 // The pointer stride cannot be determined if the pointer element type is not
490 if (!PointerElementType->isSized())
493 const DataLayout &DL = Phi->getModule()->getDataLayout();
494 int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
498 int64_t CVSize = CV->getSExtValue();
501 StepValue = ConstantInt::getSigned(CV->getType(), CVSize / Size);
505 /// \brief Returns the instructions that use values defined in the loop.
506 SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) {
507 SmallVector<Instruction *, 8> UsedOutside;
509 for (auto *Block : L->getBlocks())
510 // FIXME: I believe that this could use copy_if if the Inst reference could
511 // be adapted into a pointer.
512 for (auto &Inst : *Block) {
513 auto Users = Inst.users();
514 if (std::any_of(Users.begin(), Users.end(), [&](User *U) {
515 auto *Use = cast<Instruction>(U);
516 return !L->contains(Use->getParent());
518 UsedOutside.push_back(&Inst);