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/Transforms/Utils/LoopUtils.h"
15 #include "llvm/ADT/ScopeExit.h"
16 #include "llvm/Analysis/AliasAnalysis.h"
17 #include "llvm/Analysis/BasicAliasAnalysis.h"
18 #include "llvm/Analysis/GlobalsModRef.h"
19 #include "llvm/Analysis/LoopInfo.h"
20 #include "llvm/Analysis/LoopPass.h"
21 #include "llvm/Analysis/ScalarEvolution.h"
22 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
23 #include "llvm/Analysis/ScalarEvolutionExpander.h"
24 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
25 #include "llvm/Analysis/TargetTransformInfo.h"
26 #include "llvm/IR/Dominators.h"
27 #include "llvm/IR/Instructions.h"
28 #include "llvm/IR/Module.h"
29 #include "llvm/IR/PatternMatch.h"
30 #include "llvm/IR/ValueHandle.h"
31 #include "llvm/Pass.h"
32 #include "llvm/Support/Debug.h"
33 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
36 using namespace llvm::PatternMatch;
38 #define DEBUG_TYPE "loop-utils"
40 bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
41 SmallPtrSetImpl<Instruction *> &Set) {
42 for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
43 if (!Set.count(dyn_cast<Instruction>(*Use)))
48 bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurrenceKind Kind) {
57 case RK_IntegerMinMax:
63 bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurrenceKind Kind) {
64 return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind);
67 bool RecurrenceDescriptor::isArithmeticRecurrenceKind(RecurrenceKind Kind) {
81 RecurrenceDescriptor::lookThroughAnd(PHINode *Phi, Type *&RT,
82 SmallPtrSetImpl<Instruction *> &Visited,
83 SmallPtrSetImpl<Instruction *> &CI) {
84 if (!Phi->hasOneUse())
87 const APInt *M = nullptr;
88 Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
90 // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
91 // with a new integer type of the corresponding bit width.
92 if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) {
93 int32_t Bits = (*M + 1).exactLogBase2();
95 RT = IntegerType::get(Phi->getContext(), Bits);
104 bool RecurrenceDescriptor::getSourceExtensionKind(
105 Instruction *Start, Instruction *Exit, Type *RT, bool &IsSigned,
106 SmallPtrSetImpl<Instruction *> &Visited,
107 SmallPtrSetImpl<Instruction *> &CI) {
109 SmallVector<Instruction *, 8> Worklist;
110 bool FoundOneOperand = false;
111 unsigned DstSize = RT->getPrimitiveSizeInBits();
112 Worklist.push_back(Exit);
114 // Traverse the instructions in the reduction expression, beginning with the
116 while (!Worklist.empty()) {
117 Instruction *I = Worklist.pop_back_val();
118 for (Use &U : I->operands()) {
120 // Terminate the traversal if the operand is not an instruction, or we
121 // reach the starting value.
122 Instruction *J = dyn_cast<Instruction>(U.get());
123 if (!J || J == Start)
126 // Otherwise, investigate the operation if it is also in the expression.
127 if (Visited.count(J)) {
128 Worklist.push_back(J);
132 // If the operand is not in Visited, it is not a reduction operation, but
133 // it does feed into one. Make sure it is either a single-use sign- or
134 // zero-extend instruction.
135 CastInst *Cast = dyn_cast<CastInst>(J);
136 bool IsSExtInst = isa<SExtInst>(J);
137 if (!Cast || !Cast->hasOneUse() || !(isa<ZExtInst>(J) || IsSExtInst))
140 // Ensure the source type of the extend is no larger than the reduction
141 // type. It is not necessary for the types to be identical.
142 unsigned SrcSize = Cast->getSrcTy()->getPrimitiveSizeInBits();
143 if (SrcSize > DstSize)
146 // Furthermore, ensure that all such extends are of the same kind.
147 if (FoundOneOperand) {
148 if (IsSigned != IsSExtInst)
151 FoundOneOperand = true;
152 IsSigned = IsSExtInst;
155 // Lastly, if the source type of the extend matches the reduction type,
156 // add the extend to CI so that we can avoid accounting for it in the
158 if (SrcSize == DstSize)
165 bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
166 Loop *TheLoop, bool HasFunNoNaNAttr,
167 RecurrenceDescriptor &RedDes) {
168 if (Phi->getNumIncomingValues() != 2)
171 // Reduction variables are only found in the loop header block.
172 if (Phi->getParent() != TheLoop->getHeader())
175 // Obtain the reduction start value from the value that comes from the loop
177 Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
179 // ExitInstruction is the single value which is used outside the loop.
180 // We only allow for a single reduction value to be used outside the loop.
181 // This includes users of the reduction, variables (which form a cycle
182 // which ends in the phi node).
183 Instruction *ExitInstruction = nullptr;
184 // Indicates that we found a reduction operation in our scan.
185 bool FoundReduxOp = false;
187 // We start with the PHI node and scan for all of the users of this
188 // instruction. All users must be instructions that can be used as reduction
189 // variables (such as ADD). We must have a single out-of-block user. The cycle
190 // must include the original PHI.
191 bool FoundStartPHI = false;
193 // To recognize min/max patterns formed by a icmp select sequence, we store
194 // the number of instruction we saw from the recognized min/max pattern,
195 // to make sure we only see exactly the two instructions.
196 unsigned NumCmpSelectPatternInst = 0;
197 InstDesc ReduxDesc(false, nullptr);
199 // Data used for determining if the recurrence has been type-promoted.
200 Type *RecurrenceType = Phi->getType();
201 SmallPtrSet<Instruction *, 4> CastInsts;
202 Instruction *Start = Phi;
203 bool IsSigned = false;
205 SmallPtrSet<Instruction *, 8> VisitedInsts;
206 SmallVector<Instruction *, 8> Worklist;
208 // Return early if the recurrence kind does not match the type of Phi. If the
209 // recurrence kind is arithmetic, we attempt to look through AND operations
210 // resulting from the type promotion performed by InstCombine. Vector
211 // operations are not limited to the legal integer widths, so we may be able
212 // to evaluate the reduction in the narrower width.
213 if (RecurrenceType->isFloatingPointTy()) {
214 if (!isFloatingPointRecurrenceKind(Kind))
217 if (!isIntegerRecurrenceKind(Kind))
219 if (isArithmeticRecurrenceKind(Kind))
220 Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
223 Worklist.push_back(Start);
224 VisitedInsts.insert(Start);
226 // A value in the reduction can be used:
227 // - By the reduction:
228 // - Reduction operation:
229 // - One use of reduction value (safe).
230 // - Multiple use of reduction value (not safe).
232 // - All uses of the PHI must be the reduction (safe).
233 // - Otherwise, not safe.
234 // - By instructions outside of the loop (safe).
235 // * One value may have several outside users, but all outside
236 // uses must be of the same value.
237 // - By an instruction that is not part of the reduction (not safe).
239 // * An instruction type other than PHI or the reduction operation.
240 // * A PHI in the header other than the initial PHI.
241 while (!Worklist.empty()) {
242 Instruction *Cur = Worklist.back();
246 // If the instruction has no users then this is a broken chain and can't be
247 // a reduction variable.
248 if (Cur->use_empty())
251 bool IsAPhi = isa<PHINode>(Cur);
253 // A header PHI use other than the original PHI.
254 if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
257 // Reductions of instructions such as Div, and Sub is only possible if the
258 // LHS is the reduction variable.
259 if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
260 !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
261 !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
264 // Any reduction instruction must be of one of the allowed kinds. We ignore
265 // the starting value (the Phi or an AND instruction if the Phi has been
268 ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
269 if (!ReduxDesc.isRecurrence())
273 // A reduction operation must only have one use of the reduction value.
274 if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax &&
275 hasMultipleUsesOf(Cur, VisitedInsts))
278 // All inputs to a PHI node must be a reduction value.
279 if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
282 if (Kind == RK_IntegerMinMax &&
283 (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
284 ++NumCmpSelectPatternInst;
285 if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
286 ++NumCmpSelectPatternInst;
288 // Check whether we found a reduction operator.
289 FoundReduxOp |= !IsAPhi && Cur != Start;
291 // Process users of current instruction. Push non-PHI nodes after PHI nodes
292 // onto the stack. This way we are going to have seen all inputs to PHI
293 // nodes once we get to them.
294 SmallVector<Instruction *, 8> NonPHIs;
295 SmallVector<Instruction *, 8> PHIs;
296 for (User *U : Cur->users()) {
297 Instruction *UI = cast<Instruction>(U);
299 // Check if we found the exit user.
300 BasicBlock *Parent = UI->getParent();
301 if (!TheLoop->contains(Parent)) {
302 // If we already know this instruction is used externally, move on to
304 if (ExitInstruction == Cur)
307 // Exit if you find multiple values used outside or if the header phi
308 // node is being used. In this case the user uses the value of the
309 // previous iteration, in which case we would loose "VF-1" iterations of
310 // the reduction operation if we vectorize.
311 if (ExitInstruction != nullptr || Cur == Phi)
314 // The instruction used by an outside user must be the last instruction
315 // before we feed back to the reduction phi. Otherwise, we loose VF-1
316 // operations on the value.
317 if (!is_contained(Phi->operands(), Cur))
320 ExitInstruction = Cur;
324 // Process instructions only once (termination). Each reduction cycle
325 // value must only be used once, except by phi nodes and min/max
326 // reductions which are represented as a cmp followed by a select.
327 InstDesc IgnoredVal(false, nullptr);
328 if (VisitedInsts.insert(UI).second) {
329 if (isa<PHINode>(UI))
332 NonPHIs.push_back(UI);
333 } else if (!isa<PHINode>(UI) &&
334 ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
335 !isa<SelectInst>(UI)) ||
336 !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence()))
339 // Remember that we completed the cycle.
341 FoundStartPHI = true;
343 Worklist.append(PHIs.begin(), PHIs.end());
344 Worklist.append(NonPHIs.begin(), NonPHIs.end());
347 // This means we have seen one but not the other instruction of the
348 // pattern or more than just a select and cmp.
349 if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
350 NumCmpSelectPatternInst != 2)
353 if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
356 // If we think Phi may have been type-promoted, we also need to ensure that
357 // all source operands of the reduction are either SExtInsts or ZEstInsts. If
358 // so, we will be able to evaluate the reduction in the narrower bit width.
360 if (!getSourceExtensionKind(Start, ExitInstruction, RecurrenceType,
361 IsSigned, VisitedInsts, CastInsts))
364 // We found a reduction var if we have reached the original phi node and we
365 // only have a single instruction with out-of-loop users.
367 // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
368 // is saved as part of the RecurrenceDescriptor.
370 // Save the description of this reduction variable.
371 RecurrenceDescriptor RD(
372 RdxStart, ExitInstruction, Kind, ReduxDesc.getMinMaxKind(),
373 ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
379 /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
380 /// pattern corresponding to a min(X, Y) or max(X, Y).
381 RecurrenceDescriptor::InstDesc
382 RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) {
384 assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
385 "Expect a select instruction");
386 Instruction *Cmp = nullptr;
387 SelectInst *Select = nullptr;
389 // We must handle the select(cmp()) as a single instruction. Advance to the
391 if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
392 if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
393 return InstDesc(false, I);
394 return InstDesc(Select, Prev.getMinMaxKind());
397 // Only handle single use cases for now.
398 if (!(Select = dyn_cast<SelectInst>(I)))
399 return InstDesc(false, I);
400 if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
401 !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
402 return InstDesc(false, I);
403 if (!Cmp->hasOneUse())
404 return InstDesc(false, I);
409 // Look for a min/max pattern.
410 if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
411 return InstDesc(Select, MRK_UIntMin);
412 else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
413 return InstDesc(Select, MRK_UIntMax);
414 else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
415 return InstDesc(Select, MRK_SIntMax);
416 else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
417 return InstDesc(Select, MRK_SIntMin);
418 else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
419 return InstDesc(Select, MRK_FloatMin);
420 else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
421 return InstDesc(Select, MRK_FloatMax);
422 else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
423 return InstDesc(Select, MRK_FloatMin);
424 else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
425 return InstDesc(Select, MRK_FloatMax);
427 return InstDesc(false, I);
430 RecurrenceDescriptor::InstDesc
431 RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
432 InstDesc &Prev, bool HasFunNoNaNAttr) {
433 bool FP = I->getType()->isFloatingPointTy();
434 Instruction *UAI = Prev.getUnsafeAlgebraInst();
435 if (!UAI && FP && !I->isFast())
436 UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
438 switch (I->getOpcode()) {
440 return InstDesc(false, I);
441 case Instruction::PHI:
442 return InstDesc(I, Prev.getMinMaxKind(), Prev.getUnsafeAlgebraInst());
443 case Instruction::Sub:
444 case Instruction::Add:
445 return InstDesc(Kind == RK_IntegerAdd, I);
446 case Instruction::Mul:
447 return InstDesc(Kind == RK_IntegerMult, I);
448 case Instruction::And:
449 return InstDesc(Kind == RK_IntegerAnd, I);
450 case Instruction::Or:
451 return InstDesc(Kind == RK_IntegerOr, I);
452 case Instruction::Xor:
453 return InstDesc(Kind == RK_IntegerXor, I);
454 case Instruction::FMul:
455 return InstDesc(Kind == RK_FloatMult, I, UAI);
456 case Instruction::FSub:
457 case Instruction::FAdd:
458 return InstDesc(Kind == RK_FloatAdd, I, UAI);
459 case Instruction::FCmp:
460 case Instruction::ICmp:
461 case Instruction::Select:
462 if (Kind != RK_IntegerMinMax &&
463 (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
464 return InstDesc(false, I);
465 return isMinMaxSelectCmpPattern(I, Prev);
469 bool RecurrenceDescriptor::hasMultipleUsesOf(
470 Instruction *I, SmallPtrSetImpl<Instruction *> &Insts) {
471 unsigned NumUses = 0;
472 for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
474 if (Insts.count(dyn_cast<Instruction>(*Use)))
482 bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
483 RecurrenceDescriptor &RedDes) {
485 BasicBlock *Header = TheLoop->getHeader();
486 Function &F = *Header->getParent();
487 bool HasFunNoNaNAttr =
488 F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
490 if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
491 DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
494 if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
495 DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
498 if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes)) {
499 DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
502 if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes)) {
503 DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
506 if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes)) {
507 DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
510 if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr,
512 DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
515 if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
516 DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
519 if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
520 DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
523 if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) {
524 DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi << "\n");
527 // Not a reduction of known type.
531 bool RecurrenceDescriptor::isFirstOrderRecurrence(
532 PHINode *Phi, Loop *TheLoop,
533 DenseMap<Instruction *, Instruction *> &SinkAfter, DominatorTree *DT) {
535 // Ensure the phi node is in the loop header and has two incoming values.
536 if (Phi->getParent() != TheLoop->getHeader() ||
537 Phi->getNumIncomingValues() != 2)
540 // Ensure the loop has a preheader and a single latch block. The loop
541 // vectorizer will need the latch to set up the next iteration of the loop.
542 auto *Preheader = TheLoop->getLoopPreheader();
543 auto *Latch = TheLoop->getLoopLatch();
544 if (!Preheader || !Latch)
547 // Ensure the phi node's incoming blocks are the loop preheader and latch.
548 if (Phi->getBasicBlockIndex(Preheader) < 0 ||
549 Phi->getBasicBlockIndex(Latch) < 0)
552 // Get the previous value. The previous value comes from the latch edge while
553 // the initial value comes form the preheader edge.
554 auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
555 if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) ||
556 SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.
559 // Ensure every user of the phi node is dominated by the previous value.
560 // The dominance requirement ensures the loop vectorizer will not need to
561 // vectorize the initial value prior to the first iteration of the loop.
562 // TODO: Consider extending this sinking to handle other kinds of instructions
563 // and expressions, beyond sinking a single cast past Previous.
564 if (Phi->hasOneUse()) {
565 auto *I = Phi->user_back();
566 if (I->isCast() && (I->getParent() == Phi->getParent()) && I->hasOneUse() &&
567 DT->dominates(Previous, I->user_back())) {
568 if (!DT->dominates(Previous, I)) // Otherwise we're good w/o sinking.
569 SinkAfter[I] = Previous;
574 for (User *U : Phi->users())
575 if (auto *I = dyn_cast<Instruction>(U)) {
576 if (!DT->dominates(Previous, I))
583 /// This function returns the identity element (or neutral element) for
585 Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K,
591 // Adding, Xoring, Oring zero to a number does not change it.
592 return ConstantInt::get(Tp, 0);
594 // Multiplying a number by 1 does not change it.
595 return ConstantInt::get(Tp, 1);
597 // AND-ing a number with an all-1 value does not change it.
598 return ConstantInt::get(Tp, -1, true);
600 // Multiplying a number by 1 does not change it.
601 return ConstantFP::get(Tp, 1.0L);
603 // Adding zero to a number does not change it.
604 return ConstantFP::get(Tp, 0.0L);
606 llvm_unreachable("Unknown recurrence kind");
610 /// This function translates the recurrence kind to an LLVM binary operator.
611 unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) {
614 return Instruction::Add;
616 return Instruction::Mul;
618 return Instruction::Or;
620 return Instruction::And;
622 return Instruction::Xor;
624 return Instruction::FMul;
626 return Instruction::FAdd;
627 case RK_IntegerMinMax:
628 return Instruction::ICmp;
630 return Instruction::FCmp;
632 llvm_unreachable("Unknown recurrence operation");
636 Value *RecurrenceDescriptor::createMinMaxOp(IRBuilder<> &Builder,
637 MinMaxRecurrenceKind RK,
638 Value *Left, Value *Right) {
639 CmpInst::Predicate P = CmpInst::ICMP_NE;
642 llvm_unreachable("Unknown min/max recurrence kind");
644 P = CmpInst::ICMP_ULT;
647 P = CmpInst::ICMP_UGT;
650 P = CmpInst::ICMP_SLT;
653 P = CmpInst::ICMP_SGT;
656 P = CmpInst::FCMP_OLT;
659 P = CmpInst::FCMP_OGT;
663 // We only match FP sequences that are 'fast', so we can unconditionally
664 // set it on any generated instructions.
665 IRBuilder<>::FastMathFlagGuard FMFG(Builder);
668 Builder.setFastMathFlags(FMF);
671 if (RK == MRK_FloatMin || RK == MRK_FloatMax)
672 Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
674 Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
676 Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
680 InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
681 const SCEV *Step, BinaryOperator *BOp,
682 SmallVectorImpl<Instruction *> *Casts)
683 : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
684 assert(IK != IK_NoInduction && "Not an induction");
686 // Start value type should match the induction kind and the value
687 // itself should not be null.
688 assert(StartValue && "StartValue is null");
689 assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
690 "StartValue is not a pointer for pointer induction");
691 assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
692 "StartValue is not an integer for integer induction");
694 // Check the Step Value. It should be non-zero integer value.
695 assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
696 "Step value is zero");
698 assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
699 "Step value should be constant for pointer induction");
700 assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
701 "StepValue is not an integer");
703 assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
704 "StepValue is not FP for FpInduction");
705 assert((IK != IK_FpInduction || (InductionBinOp &&
706 (InductionBinOp->getOpcode() == Instruction::FAdd ||
707 InductionBinOp->getOpcode() == Instruction::FSub))) &&
708 "Binary opcode should be specified for FP induction");
711 for (auto &Inst : *Casts) {
712 RedundantCasts.push_back(Inst);
717 int InductionDescriptor::getConsecutiveDirection() const {
718 ConstantInt *ConstStep = getConstIntStepValue();
719 if (ConstStep && (ConstStep->isOne() || ConstStep->isMinusOne()))
720 return ConstStep->getSExtValue();
724 ConstantInt *InductionDescriptor::getConstIntStepValue() const {
725 if (isa<SCEVConstant>(Step))
726 return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
730 Value *InductionDescriptor::transform(IRBuilder<> &B, Value *Index,
732 const DataLayout& DL) const {
734 SCEVExpander Exp(*SE, DL, "induction");
735 assert(Index->getType() == Step->getType() &&
736 "Index type does not match StepValue type");
738 case IK_IntInduction: {
739 assert(Index->getType() == StartValue->getType() &&
740 "Index type does not match StartValue type");
742 // FIXME: Theoretically, we can call getAddExpr() of ScalarEvolution
743 // and calculate (Start + Index * Step) for all cases, without
744 // special handling for "isOne" and "isMinusOne".
745 // But in the real life the result code getting worse. We mix SCEV
746 // expressions and ADD/SUB operations and receive redundant
747 // intermediate values being calculated in different ways and
748 // Instcombine is unable to reduce them all.
750 if (getConstIntStepValue() &&
751 getConstIntStepValue()->isMinusOne())
752 return B.CreateSub(StartValue, Index);
753 if (getConstIntStepValue() &&
754 getConstIntStepValue()->isOne())
755 return B.CreateAdd(StartValue, Index);
756 const SCEV *S = SE->getAddExpr(SE->getSCEV(StartValue),
757 SE->getMulExpr(Step, SE->getSCEV(Index)));
758 return Exp.expandCodeFor(S, StartValue->getType(), &*B.GetInsertPoint());
760 case IK_PtrInduction: {
761 assert(isa<SCEVConstant>(Step) &&
762 "Expected constant step for pointer induction");
763 const SCEV *S = SE->getMulExpr(SE->getSCEV(Index), Step);
764 Index = Exp.expandCodeFor(S, Index->getType(), &*B.GetInsertPoint());
765 return B.CreateGEP(nullptr, StartValue, Index);
767 case IK_FpInduction: {
768 assert(Step->getType()->isFloatingPointTy() && "Expected FP Step value");
769 assert(InductionBinOp &&
770 (InductionBinOp->getOpcode() == Instruction::FAdd ||
771 InductionBinOp->getOpcode() == Instruction::FSub) &&
772 "Original bin op should be defined for FP induction");
774 Value *StepValue = cast<SCEVUnknown>(Step)->getValue();
776 // Floating point operations had to be 'fast' to enable the induction.
780 Value *MulExp = B.CreateFMul(StepValue, Index);
781 if (isa<Instruction>(MulExp))
782 // We have to check, the MulExp may be a constant.
783 cast<Instruction>(MulExp)->setFastMathFlags(Flags);
785 Value *BOp = B.CreateBinOp(InductionBinOp->getOpcode() , StartValue,
786 MulExp, "induction");
787 if (isa<Instruction>(BOp))
788 cast<Instruction>(BOp)->setFastMathFlags(Flags);
795 llvm_unreachable("invalid enum");
798 bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop,
800 InductionDescriptor &D) {
802 // Here we only handle FP induction variables.
803 assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
805 if (TheLoop->getHeader() != Phi->getParent())
808 // The loop may have multiple entrances or multiple exits; we can analyze
809 // this phi if it has a unique entry value and a unique backedge value.
810 if (Phi->getNumIncomingValues() != 2)
812 Value *BEValue = nullptr, *StartValue = nullptr;
813 if (TheLoop->contains(Phi->getIncomingBlock(0))) {
814 BEValue = Phi->getIncomingValue(0);
815 StartValue = Phi->getIncomingValue(1);
817 assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
818 "Unexpected Phi node in the loop");
819 BEValue = Phi->getIncomingValue(1);
820 StartValue = Phi->getIncomingValue(0);
823 BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
827 Value *Addend = nullptr;
828 if (BOp->getOpcode() == Instruction::FAdd) {
829 if (BOp->getOperand(0) == Phi)
830 Addend = BOp->getOperand(1);
831 else if (BOp->getOperand(1) == Phi)
832 Addend = BOp->getOperand(0);
833 } else if (BOp->getOpcode() == Instruction::FSub)
834 if (BOp->getOperand(0) == Phi)
835 Addend = BOp->getOperand(1);
840 // The addend should be loop invariant
841 if (auto *I = dyn_cast<Instruction>(Addend))
842 if (TheLoop->contains(I))
845 // FP Step has unknown SCEV
846 const SCEV *Step = SE->getUnknown(Addend);
847 D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
851 /// This function is called when we suspect that the update-chain of a phi node
852 /// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
853 /// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
854 /// predicate P under which the SCEV expression for the phi can be the
855 /// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
856 /// cast instructions that are involved in the update-chain of this induction.
857 /// A caller that adds the required runtime predicate can be free to drop these
858 /// cast instructions, and compute the phi using \p AR (instead of some scev
859 /// expression with casts).
861 /// For example, without a predicate the scev expression can take the following
863 /// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
865 /// It corresponds to the following IR sequence:
867 /// %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
868 /// %casted_phi = "ExtTrunc i64 %x"
869 /// %add = add i64 %casted_phi, %step
871 /// where %x is given in \p PN,
872 /// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
873 /// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
874 /// several forms, for example, such as:
875 /// ExtTrunc1: %casted_phi = and %x, 2^n-1
877 /// ExtTrunc2: %t = shl %x, m
878 /// %casted_phi = ashr %t, m
880 /// If we are able to find such sequence, we return the instructions
881 /// we found, namely %casted_phi and the instructions on its use-def chain up
882 /// to the phi (not including the phi).
883 static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE,
884 const SCEVUnknown *PhiScev,
885 const SCEVAddRecExpr *AR,
886 SmallVectorImpl<Instruction *> &CastInsts) {
888 assert(CastInsts.empty() && "CastInsts is expected to be empty.");
889 auto *PN = cast<PHINode>(PhiScev->getValue());
890 assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression");
891 const Loop *L = AR->getLoop();
893 // Find any cast instructions that participate in the def-use chain of
894 // PhiScev in the loop.
895 // FORNOW/TODO: We currently expect the def-use chain to include only
896 // two-operand instructions, where one of the operands is an invariant.
897 // createAddRecFromPHIWithCasts() currently does not support anything more
898 // involved than that, so we keep the search simple. This can be
899 // extended/generalized as needed.
901 auto getDef = [&](const Value *Val) -> Value * {
902 const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
905 Value *Op0 = BinOp->getOperand(0);
906 Value *Op1 = BinOp->getOperand(1);
907 Value *Def = nullptr;
908 if (L->isLoopInvariant(Op0))
910 else if (L->isLoopInvariant(Op1))
915 // Look for the instruction that defines the induction via the
917 BasicBlock *Latch = L->getLoopLatch();
920 Value *Val = PN->getIncomingValueForBlock(Latch);
924 // Follow the def-use chain until the induction phi is reached.
925 // If on the way we encounter a Value that has the same SCEV Expr as the
926 // phi node, we can consider the instructions we visit from that point
927 // as part of the cast-sequence that can be ignored.
928 bool InCastSequence = false;
929 auto *Inst = dyn_cast<Instruction>(Val);
931 // If we encountered a phi node other than PN, or if we left the loop,
933 if (!Inst || !L->contains(Inst)) {
936 auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val));
937 if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR))
938 InCastSequence = true;
939 if (InCastSequence) {
940 // Only the last instruction in the cast sequence is expected to have
941 // uses outside the induction def-use chain.
942 if (!CastInsts.empty())
943 if (!Inst->hasOneUse())
945 CastInsts.push_back(Inst);
950 Inst = dyn_cast<Instruction>(Val);
953 return InCastSequence;
956 bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
957 PredicatedScalarEvolution &PSE,
958 InductionDescriptor &D,
960 Type *PhiTy = Phi->getType();
962 // Handle integer and pointer inductions variables.
963 // Now we handle also FP induction but not trying to make a
964 // recurrent expression from the PHI node in-place.
966 if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() &&
967 !PhiTy->isFloatTy() && !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
970 if (PhiTy->isFloatingPointTy())
971 return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);
973 const SCEV *PhiScev = PSE.getSCEV(Phi);
974 const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
976 // We need this expression to be an AddRecExpr.
978 AR = PSE.getAsAddRec(Phi);
981 DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
985 // Record any Cast instructions that participate in the induction update
986 const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
987 // If we started from an UnknownSCEV, and managed to build an addRecurrence
988 // only after enabling Assume with PSCEV, this means we may have encountered
989 // cast instructions that required adding a runtime check in order to
990 // guarantee the correctness of the AddRecurence respresentation of the
992 if (PhiScev != AR && SymbolicPhi) {
993 SmallVector<Instruction *, 2> Casts;
994 if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts))
995 return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts);
998 return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
1001 bool InductionDescriptor::isInductionPHI(
1002 PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
1003 InductionDescriptor &D, const SCEV *Expr,
1004 SmallVectorImpl<Instruction *> *CastsToIgnore) {
1005 Type *PhiTy = Phi->getType();
1006 // We only handle integer and pointer inductions variables.
1007 if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
1010 // Check that the PHI is consecutive.
1011 const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
1012 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1015 DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1019 if (AR->getLoop() != TheLoop) {
1020 // FIXME: We should treat this as a uniform. Unfortunately, we
1021 // don't currently know how to handled uniform PHIs.
1022 DEBUG(dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
1027 Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
1028 const SCEV *Step = AR->getStepRecurrence(*SE);
1029 // Calculate the pointer stride and check if it is consecutive.
1030 // The stride may be a constant or a loop invariant integer value.
1031 const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
1032 if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
1035 if (PhiTy->isIntegerTy()) {
1036 D = InductionDescriptor(StartValue, IK_IntInduction, Step, /*BOp=*/ nullptr,
1041 assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
1042 // Pointer induction should be a constant.
1046 ConstantInt *CV = ConstStep->getValue();
1047 Type *PointerElementType = PhiTy->getPointerElementType();
1048 // The pointer stride cannot be determined if the pointer element type is not
1050 if (!PointerElementType->isSized())
1053 const DataLayout &DL = Phi->getModule()->getDataLayout();
1054 int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
1058 int64_t CVSize = CV->getSExtValue();
1061 auto *StepValue = SE->getConstant(CV->getType(), CVSize / Size,
1063 D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue);
1067 bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
1068 bool PreserveLCSSA) {
1069 bool Changed = false;
1071 // We re-use a vector for the in-loop predecesosrs.
1072 SmallVector<BasicBlock *, 4> InLoopPredecessors;
1074 auto RewriteExit = [&](BasicBlock *BB) {
1075 assert(InLoopPredecessors.empty() &&
1076 "Must start with an empty predecessors list!");
1077 auto Cleanup = make_scope_exit([&] { InLoopPredecessors.clear(); });
1079 // See if there are any non-loop predecessors of this exit block and
1080 // keep track of the in-loop predecessors.
1081 bool IsDedicatedExit = true;
1082 for (auto *PredBB : predecessors(BB))
1083 if (L->contains(PredBB)) {
1084 if (isa<IndirectBrInst>(PredBB->getTerminator()))
1085 // We cannot rewrite exiting edges from an indirectbr.
1088 InLoopPredecessors.push_back(PredBB);
1090 IsDedicatedExit = false;
1093 assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!");
1095 // Nothing to do if this is already a dedicated exit.
1096 if (IsDedicatedExit)
1099 auto *NewExitBB = SplitBlockPredecessors(
1100 BB, InLoopPredecessors, ".loopexit", DT, LI, PreserveLCSSA);
1103 DEBUG(dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
1106 DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
1107 << NewExitBB->getName() << "\n");
1111 // Walk the exit blocks directly rather than building up a data structure for
1112 // them, but only visit each one once.
1113 SmallPtrSet<BasicBlock *, 4> Visited;
1114 for (auto *BB : L->blocks())
1115 for (auto *SuccBB : successors(BB)) {
1116 // We're looking for exit blocks so skip in-loop successors.
1117 if (L->contains(SuccBB))
1120 // Visit each exit block exactly once.
1121 if (!Visited.insert(SuccBB).second)
1124 Changed |= RewriteExit(SuccBB);
1130 /// \brief Returns the instructions that use values defined in the loop.
1131 SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) {
1132 SmallVector<Instruction *, 8> UsedOutside;
1134 for (auto *Block : L->getBlocks())
1135 // FIXME: I believe that this could use copy_if if the Inst reference could
1136 // be adapted into a pointer.
1137 for (auto &Inst : *Block) {
1138 auto Users = Inst.users();
1139 if (any_of(Users, [&](User *U) {
1140 auto *Use = cast<Instruction>(U);
1141 return !L->contains(Use->getParent());
1143 UsedOutside.push_back(&Inst);
1149 void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) {
1150 // By definition, all loop passes need the LoopInfo analysis and the
1151 // Dominator tree it depends on. Because they all participate in the loop
1152 // pass manager, they must also preserve these.
1153 AU.addRequired<DominatorTreeWrapperPass>();
1154 AU.addPreserved<DominatorTreeWrapperPass>();
1155 AU.addRequired<LoopInfoWrapperPass>();
1156 AU.addPreserved<LoopInfoWrapperPass>();
1158 // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
1159 // here because users shouldn't directly get them from this header.
1160 extern char &LoopSimplifyID;
1161 extern char &LCSSAID;
1162 AU.addRequiredID(LoopSimplifyID);
1163 AU.addPreservedID(LoopSimplifyID);
1164 AU.addRequiredID(LCSSAID);
1165 AU.addPreservedID(LCSSAID);
1166 // This is used in the LPPassManager to perform LCSSA verification on passes
1167 // which preserve lcssa form
1168 AU.addRequired<LCSSAVerificationPass>();
1169 AU.addPreserved<LCSSAVerificationPass>();
1171 // Loop passes are designed to run inside of a loop pass manager which means
1172 // that any function analyses they require must be required by the first loop
1173 // pass in the manager (so that it is computed before the loop pass manager
1174 // runs) and preserved by all loop pasess in the manager. To make this
1175 // reasonably robust, the set needed for most loop passes is maintained here.
1176 // If your loop pass requires an analysis not listed here, you will need to
1177 // carefully audit the loop pass manager nesting structure that results.
1178 AU.addRequired<AAResultsWrapperPass>();
1179 AU.addPreserved<AAResultsWrapperPass>();
1180 AU.addPreserved<BasicAAWrapperPass>();
1181 AU.addPreserved<GlobalsAAWrapperPass>();
1182 AU.addPreserved<SCEVAAWrapperPass>();
1183 AU.addRequired<ScalarEvolutionWrapperPass>();
1184 AU.addPreserved<ScalarEvolutionWrapperPass>();
1187 /// Manually defined generic "LoopPass" dependency initialization. This is used
1188 /// to initialize the exact set of passes from above in \c
1189 /// getLoopAnalysisUsage. It can be used within a loop pass's initialization
1192 /// INITIALIZE_PASS_DEPENDENCY(LoopPass)
1194 /// As-if "LoopPass" were a pass.
1195 void llvm::initializeLoopPassPass(PassRegistry &Registry) {
1196 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1197 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1198 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
1199 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
1200 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
1201 INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
1202 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
1203 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
1204 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
1207 /// \brief Find string metadata for loop
1209 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
1210 /// operand or null otherwise. If the string metadata is not found return
1211 /// Optional's not-a-value.
1212 Optional<const MDOperand *> llvm::findStringMetadataForLoop(Loop *TheLoop,
1214 MDNode *LoopID = TheLoop->getLoopID();
1215 // Return none if LoopID is false.
1219 // First operand should refer to the loop id itself.
1220 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
1221 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
1223 // Iterate over LoopID operands and look for MDString Metadata
1224 for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
1225 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
1228 MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1231 // Return true if MDString holds expected MetaData.
1232 if (Name.equals(S->getString()))
1233 switch (MD->getNumOperands()) {
1237 return &MD->getOperand(1);
1239 llvm_unreachable("loop metadata has 0 or 1 operand");
1245 /// Does a BFS from a given node to all of its children inside a given loop.
1246 /// The returned vector of nodes includes the starting point.
1247 SmallVector<DomTreeNode *, 16>
1248 llvm::collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop) {
1249 SmallVector<DomTreeNode *, 16> Worklist;
1250 auto AddRegionToWorklist = [&](DomTreeNode *DTN) {
1251 // Only include subregions in the top level loop.
1252 BasicBlock *BB = DTN->getBlock();
1253 if (CurLoop->contains(BB))
1254 Worklist.push_back(DTN);
1257 AddRegionToWorklist(N);
1259 for (size_t I = 0; I < Worklist.size(); I++)
1260 for (DomTreeNode *Child : Worklist[I]->getChildren())
1261 AddRegionToWorklist(Child);
1266 void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT = nullptr,
1267 ScalarEvolution *SE = nullptr,
1268 LoopInfo *LI = nullptr) {
1269 assert((!DT || L->isLCSSAForm(*DT)) && "Expected LCSSA!");
1270 auto *Preheader = L->getLoopPreheader();
1271 assert(Preheader && "Preheader should exist!");
1273 // Now that we know the removal is safe, remove the loop by changing the
1274 // branch from the preheader to go to the single exit block.
1276 // Because we're deleting a large chunk of code at once, the sequence in which
1277 // we remove things is very important to avoid invalidation issues.
1279 // Tell ScalarEvolution that the loop is deleted. Do this before
1280 // deleting the loop so that ScalarEvolution can look at the loop
1281 // to determine what it needs to clean up.
1285 auto *ExitBlock = L->getUniqueExitBlock();
1286 assert(ExitBlock && "Should have a unique exit block!");
1287 assert(L->hasDedicatedExits() && "Loop should have dedicated exits!");
1289 auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator());
1290 assert(OldBr && "Preheader must end with a branch");
1291 assert(OldBr->isUnconditional() && "Preheader must have a single successor");
1292 // Connect the preheader to the exit block. Keep the old edge to the header
1293 // around to perform the dominator tree update in two separate steps
1294 // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
1295 // preheader -> header.
1298 // 0. Preheader 1. Preheader 2. Preheader
1301 // Header <--\ | Header <--\ | Header <--\
1302 // | | | | | | | | | | |
1303 // | V | | | V | | | V |
1304 // | Body --/ | | Body --/ | | Body --/
1308 // By doing this is two separate steps we can perform the dominator tree
1309 // update without using the batch update API.
1311 // Even when the loop is never executed, we cannot remove the edge from the
1312 // source block to the exit block. Consider the case where the unexecuted loop
1313 // branches back to an outer loop. If we deleted the loop and removed the edge
1314 // coming to this inner loop, this will break the outer loop structure (by
1315 // deleting the backedge of the outer loop). If the outer loop is indeed a
1316 // non-loop, it will be deleted in a future iteration of loop deletion pass.
1317 IRBuilder<> Builder(OldBr);
1318 Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock);
1319 // Remove the old branch. The conditional branch becomes a new terminator.
1320 OldBr->eraseFromParent();
1322 // Rewrite phis in the exit block to get their inputs from the Preheader
1323 // instead of the exiting block.
1324 for (PHINode &P : ExitBlock->phis()) {
1325 // Set the zero'th element of Phi to be from the preheader and remove all
1326 // other incoming values. Given the loop has dedicated exits, all other
1327 // incoming values must be from the exiting blocks.
1329 P.setIncomingBlock(PredIndex, Preheader);
1330 // Removes all incoming values from all other exiting blocks (including
1331 // duplicate values from an exiting block).
1332 // Nuke all entries except the zero'th entry which is the preheader entry.
1333 // NOTE! We need to remove Incoming Values in the reverse order as done
1334 // below, to keep the indices valid for deletion (removeIncomingValues
1335 // updates getNumIncomingValues and shifts all values down into the operand
1337 for (unsigned i = 0, e = P.getNumIncomingValues() - 1; i != e; ++i)
1338 P.removeIncomingValue(e - i, false);
1340 assert((P.getNumIncomingValues() == 1 &&
1341 P.getIncomingBlock(PredIndex) == Preheader) &&
1342 "Should have exactly one value and that's from the preheader!");
1345 // Disconnect the loop body by branching directly to its exit.
1346 Builder.SetInsertPoint(Preheader->getTerminator());
1347 Builder.CreateBr(ExitBlock);
1348 // Remove the old branch.
1349 Preheader->getTerminator()->eraseFromParent();
1352 // Update the dominator tree by informing it about the new edge from the
1353 // preheader to the exit.
1354 DT->insertEdge(Preheader, ExitBlock);
1355 // Inform the dominator tree about the removed edge.
1356 DT->deleteEdge(Preheader, L->getHeader());
1359 // Remove the block from the reference counting scheme, so that we can
1360 // delete it freely later.
1361 for (auto *Block : L->blocks())
1362 Block->dropAllReferences();
1365 // Erase the instructions and the blocks without having to worry
1366 // about ordering because we already dropped the references.
1367 // NOTE: This iteration is safe because erasing the block does not remove
1368 // its entry from the loop's block list. We do that in the next section.
1369 for (Loop::block_iterator LpI = L->block_begin(), LpE = L->block_end();
1371 (*LpI)->eraseFromParent();
1373 // Finally, the blocks from loopinfo. This has to happen late because
1374 // otherwise our loop iterators won't work.
1376 SmallPtrSet<BasicBlock *, 8> blocks;
1377 blocks.insert(L->block_begin(), L->block_end());
1378 for (BasicBlock *BB : blocks)
1379 LI->removeBlock(BB);
1381 // The last step is to update LoopInfo now that we've eliminated this loop.
1386 /// Returns true if the instruction in a loop is guaranteed to execute at least
1388 bool llvm::isGuaranteedToExecute(const Instruction &Inst,
1389 const DominatorTree *DT, const Loop *CurLoop,
1390 const LoopSafetyInfo *SafetyInfo) {
1391 // We have to check to make sure that the instruction dominates all
1392 // of the exit blocks. If it doesn't, then there is a path out of the loop
1393 // which does not execute this instruction, so we can't hoist it.
1395 // If the instruction is in the header block for the loop (which is very
1396 // common), it is always guaranteed to dominate the exit blocks. Since this
1397 // is a common case, and can save some work, check it now.
1398 if (Inst.getParent() == CurLoop->getHeader())
1399 // If there's a throw in the header block, we can't guarantee we'll reach
1401 return !SafetyInfo->HeaderMayThrow;
1403 // Somewhere in this loop there is an instruction which may throw and make us
1405 if (SafetyInfo->MayThrow)
1408 // Get the exit blocks for the current loop.
1409 SmallVector<BasicBlock *, 8> ExitBlocks;
1410 CurLoop->getExitBlocks(ExitBlocks);
1412 // Verify that the block dominates each of the exit blocks of the loop.
1413 for (BasicBlock *ExitBlock : ExitBlocks)
1414 if (!DT->dominates(Inst.getParent(), ExitBlock))
1417 // As a degenerate case, if the loop is statically infinite then we haven't
1418 // proven anything since there are no exit blocks.
1419 if (ExitBlocks.empty())
1422 // FIXME: In general, we have to prove that the loop isn't an infinite loop.
1423 // See http::llvm.org/PR24078 . (The "ExitBlocks.empty()" check above is
1424 // just a special case of this.)
1428 Optional<unsigned> llvm::getLoopEstimatedTripCount(Loop *L) {
1429 // Only support loops with a unique exiting block, and a latch.
1430 if (!L->getExitingBlock())
1433 // Get the branch weights for the the loop's backedge.
1434 BranchInst *LatchBR =
1435 dyn_cast<BranchInst>(L->getLoopLatch()->getTerminator());
1436 if (!LatchBR || LatchBR->getNumSuccessors() != 2)
1439 assert((LatchBR->getSuccessor(0) == L->getHeader() ||
1440 LatchBR->getSuccessor(1) == L->getHeader()) &&
1441 "At least one edge out of the latch must go to the header");
1443 // To estimate the number of times the loop body was executed, we want to
1444 // know the number of times the backedge was taken, vs. the number of times
1445 // we exited the loop.
1446 uint64_t TrueVal, FalseVal;
1447 if (!LatchBR->extractProfMetadata(TrueVal, FalseVal))
1450 if (!TrueVal || !FalseVal)
1453 // Divide the count of the backedge by the count of the edge exiting the loop,
1454 // rounding to nearest.
1455 if (LatchBR->getSuccessor(0) == L->getHeader())
1456 return (TrueVal + (FalseVal / 2)) / FalseVal;
1458 return (FalseVal + (TrueVal / 2)) / TrueVal;
1461 /// \brief Adds a 'fast' flag to floating point operations.
1462 static Value *addFastMathFlag(Value *V) {
1463 if (isa<FPMathOperator>(V)) {
1464 FastMathFlags Flags;
1466 cast<Instruction>(V)->setFastMathFlags(Flags);
1471 // Helper to generate a log2 shuffle reduction.
1473 llvm::getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op,
1474 RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind,
1475 ArrayRef<Value *> RedOps) {
1476 unsigned VF = Src->getType()->getVectorNumElements();
1477 // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
1478 // and vector ops, reducing the set of values being computed by half each
1480 assert(isPowerOf2_32(VF) &&
1481 "Reduction emission only supported for pow2 vectors!");
1482 Value *TmpVec = Src;
1483 SmallVector<Constant *, 32> ShuffleMask(VF, nullptr);
1484 for (unsigned i = VF; i != 1; i >>= 1) {
1485 // Move the upper half of the vector to the lower half.
1486 for (unsigned j = 0; j != i / 2; ++j)
1487 ShuffleMask[j] = Builder.getInt32(i / 2 + j);
1489 // Fill the rest of the mask with undef.
1490 std::fill(&ShuffleMask[i / 2], ShuffleMask.end(),
1491 UndefValue::get(Builder.getInt32Ty()));
1493 Value *Shuf = Builder.CreateShuffleVector(
1494 TmpVec, UndefValue::get(TmpVec->getType()),
1495 ConstantVector::get(ShuffleMask), "rdx.shuf");
1497 if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
1498 // Floating point operations had to be 'fast' to enable the reduction.
1499 TmpVec = addFastMathFlag(Builder.CreateBinOp((Instruction::BinaryOps)Op,
1500 TmpVec, Shuf, "bin.rdx"));
1502 assert(MinMaxKind != RecurrenceDescriptor::MRK_Invalid &&
1504 TmpVec = RecurrenceDescriptor::createMinMaxOp(Builder, MinMaxKind, TmpVec,
1507 if (!RedOps.empty())
1508 propagateIRFlags(TmpVec, RedOps);
1510 // The result is in the first element of the vector.
1511 return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
1514 /// Create a simple vector reduction specified by an opcode and some
1515 /// flags (if generating min/max reductions).
1516 Value *llvm::createSimpleTargetReduction(
1517 IRBuilder<> &Builder, const TargetTransformInfo *TTI, unsigned Opcode,
1518 Value *Src, TargetTransformInfo::ReductionFlags Flags,
1519 ArrayRef<Value *> RedOps) {
1520 assert(isa<VectorType>(Src->getType()) && "Type must be a vector");
1522 Value *ScalarUdf = UndefValue::get(Src->getType()->getVectorElementType());
1523 std::function<Value*()> BuildFunc;
1524 using RD = RecurrenceDescriptor;
1525 RD::MinMaxRecurrenceKind MinMaxKind = RD::MRK_Invalid;
1526 // TODO: Support creating ordered reductions.
1527 FastMathFlags FMFFast;
1531 case Instruction::Add:
1532 BuildFunc = [&]() { return Builder.CreateAddReduce(Src); };
1534 case Instruction::Mul:
1535 BuildFunc = [&]() { return Builder.CreateMulReduce(Src); };
1537 case Instruction::And:
1538 BuildFunc = [&]() { return Builder.CreateAndReduce(Src); };
1540 case Instruction::Or:
1541 BuildFunc = [&]() { return Builder.CreateOrReduce(Src); };
1543 case Instruction::Xor:
1544 BuildFunc = [&]() { return Builder.CreateXorReduce(Src); };
1546 case Instruction::FAdd:
1548 auto Rdx = Builder.CreateFAddReduce(ScalarUdf, Src);
1549 cast<CallInst>(Rdx)->setFastMathFlags(FMFFast);
1553 case Instruction::FMul:
1555 auto Rdx = Builder.CreateFMulReduce(ScalarUdf, Src);
1556 cast<CallInst>(Rdx)->setFastMathFlags(FMFFast);
1560 case Instruction::ICmp:
1561 if (Flags.IsMaxOp) {
1562 MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMax : RD::MRK_UIntMax;
1564 return Builder.CreateIntMaxReduce(Src, Flags.IsSigned);
1567 MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMin : RD::MRK_UIntMin;
1569 return Builder.CreateIntMinReduce(Src, Flags.IsSigned);
1573 case Instruction::FCmp:
1574 if (Flags.IsMaxOp) {
1575 MinMaxKind = RD::MRK_FloatMax;
1576 BuildFunc = [&]() { return Builder.CreateFPMaxReduce(Src, Flags.NoNaN); };
1578 MinMaxKind = RD::MRK_FloatMin;
1579 BuildFunc = [&]() { return Builder.CreateFPMinReduce(Src, Flags.NoNaN); };
1583 llvm_unreachable("Unhandled opcode");
1586 if (TTI->useReductionIntrinsic(Opcode, Src->getType(), Flags))
1588 return getShuffleReduction(Builder, Src, Opcode, MinMaxKind, RedOps);
1591 /// Create a vector reduction using a given recurrence descriptor.
1592 Value *llvm::createTargetReduction(IRBuilder<> &B,
1593 const TargetTransformInfo *TTI,
1594 RecurrenceDescriptor &Desc, Value *Src,
1596 // TODO: Support in-order reductions based on the recurrence descriptor.
1597 using RD = RecurrenceDescriptor;
1598 RD::RecurrenceKind RecKind = Desc.getRecurrenceKind();
1599 TargetTransformInfo::ReductionFlags Flags;
1600 Flags.NoNaN = NoNaN;
1602 case RD::RK_FloatAdd:
1603 return createSimpleTargetReduction(B, TTI, Instruction::FAdd, Src, Flags);
1604 case RD::RK_FloatMult:
1605 return createSimpleTargetReduction(B, TTI, Instruction::FMul, Src, Flags);
1606 case RD::RK_IntegerAdd:
1607 return createSimpleTargetReduction(B, TTI, Instruction::Add, Src, Flags);
1608 case RD::RK_IntegerMult:
1609 return createSimpleTargetReduction(B, TTI, Instruction::Mul, Src, Flags);
1610 case RD::RK_IntegerAnd:
1611 return createSimpleTargetReduction(B, TTI, Instruction::And, Src, Flags);
1612 case RD::RK_IntegerOr:
1613 return createSimpleTargetReduction(B, TTI, Instruction::Or, Src, Flags);
1614 case RD::RK_IntegerXor:
1615 return createSimpleTargetReduction(B, TTI, Instruction::Xor, Src, Flags);
1616 case RD::RK_IntegerMinMax: {
1617 RD::MinMaxRecurrenceKind MMKind = Desc.getMinMaxRecurrenceKind();
1618 Flags.IsMaxOp = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_UIntMax);
1619 Flags.IsSigned = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_SIntMin);
1620 return createSimpleTargetReduction(B, TTI, Instruction::ICmp, Src, Flags);
1622 case RD::RK_FloatMinMax: {
1623 Flags.IsMaxOp = Desc.getMinMaxRecurrenceKind() == RD::MRK_FloatMax;
1624 return createSimpleTargetReduction(B, TTI, Instruction::FCmp, Src, Flags);
1627 llvm_unreachable("Unhandled RecKind");
1631 void llvm::propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue) {
1632 auto *VecOp = dyn_cast<Instruction>(I);
1635 auto *Intersection = (OpValue == nullptr) ? dyn_cast<Instruction>(VL[0])
1636 : dyn_cast<Instruction>(OpValue);
1639 const unsigned Opcode = Intersection->getOpcode();
1640 VecOp->copyIRFlags(Intersection);
1641 for (auto *V : VL) {
1642 auto *Instr = dyn_cast<Instruction>(V);
1645 if (OpValue == nullptr || Opcode == Instr->getOpcode())
1646 VecOp->andIRFlags(V);