blob: c3fa05a11a248ff97d2b89ceb448b3d29bb5490b [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"
Adam Nemet2f2bd8c2016-07-26 17:52:02 +000019#include "llvm/Analysis/LoopInfo.h"
Igor Laevskyc3ccf5d2016-10-28 12:57:20 +000020#include "llvm/Analysis/LoopPass.h"
Weiming Zhao45d4cb92015-11-24 18:57:06 +000021#include "llvm/Analysis/ScalarEvolution.h"
Adam Nemet2f2bd8c2016-07-26 17:52:02 +000022#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
Elena Demikhovskyc434d092016-05-10 07:33:35 +000023#include "llvm/Analysis/ScalarEvolutionExpander.h"
Weiming Zhao45d4cb92015-11-24 18:57:06 +000024#include "llvm/Analysis/ScalarEvolutionExpressions.h"
Chandler Carruth6bda14b2017-06-06 11:49:48 +000025#include "llvm/Analysis/TargetTransformInfo.h"
Chandler Carruth31088a92016-02-19 10:45:18 +000026#include "llvm/IR/Dominators.h"
Karthik Bhat76aa6622015-04-20 04:38:33 +000027#include "llvm/IR/Instructions.h"
Weiming Zhao45d4cb92015-11-24 18:57:06 +000028#include "llvm/IR/Module.h"
Karthik Bhat76aa6622015-04-20 04:38:33 +000029#include "llvm/IR/PatternMatch.h"
30#include "llvm/IR/ValueHandle.h"
Chandler Carruth31088a92016-02-19 10:45:18 +000031#include "llvm/Pass.h"
Karthik Bhat76aa6622015-04-20 04:38:33 +000032#include "llvm/Support/Debug.h"
Chandler Carruth4a000882017-06-25 22:45:31 +000033#include "llvm/Transforms/Utils/BasicBlockUtils.h"
Karthik Bhat76aa6622015-04-20 04:38:33 +000034
35using namespace llvm;
36using namespace llvm::PatternMatch;
37
38#define DEBUG_TYPE "loop-utils"
39
Tyler Nowicki0a913102015-06-16 18:07:34 +000040bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
41 SmallPtrSetImpl<Instruction *> &Set) {
Karthik Bhat76aa6622015-04-20 04:38:33 +000042 for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
43 if (!Set.count(dyn_cast<Instruction>(*Use)))
44 return false;
45 return true;
46}
47
Chad Rosierc94f8e22015-08-27 14:12:17 +000048bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurrenceKind Kind) {
49 switch (Kind) {
50 default:
51 break;
52 case RK_IntegerAdd:
53 case RK_IntegerMult:
54 case RK_IntegerOr:
55 case RK_IntegerAnd:
56 case RK_IntegerXor:
57 case RK_IntegerMinMax:
58 return true;
59 }
60 return false;
61}
62
63bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurrenceKind Kind) {
64 return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind);
65}
66
67bool RecurrenceDescriptor::isArithmeticRecurrenceKind(RecurrenceKind Kind) {
68 switch (Kind) {
69 default:
70 break;
71 case RK_IntegerAdd:
72 case RK_IntegerMult:
73 case RK_FloatAdd:
74 case RK_FloatMult:
75 return true;
76 }
77 return false;
78}
79
80Instruction *
81RecurrenceDescriptor::lookThroughAnd(PHINode *Phi, Type *&RT,
82 SmallPtrSetImpl<Instruction *> &Visited,
83 SmallPtrSetImpl<Instruction *> &CI) {
84 if (!Phi->hasOneUse())
85 return Phi;
86
87 const APInt *M = nullptr;
88 Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
89
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.
Craig Topper72ee6942017-06-24 06:24:01 +000092 if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) {
Chad Rosierc94f8e22015-08-27 14:12:17 +000093 int32_t Bits = (*M + 1).exactLogBase2();
94 if (Bits > 0) {
95 RT = IntegerType::get(Phi->getContext(), Bits);
96 Visited.insert(Phi);
97 CI.insert(J);
98 return J;
99 }
100 }
101 return Phi;
102}
103
104bool RecurrenceDescriptor::getSourceExtensionKind(
105 Instruction *Start, Instruction *Exit, Type *RT, bool &IsSigned,
106 SmallPtrSetImpl<Instruction *> &Visited,
107 SmallPtrSetImpl<Instruction *> &CI) {
108
109 SmallVector<Instruction *, 8> Worklist;
110 bool FoundOneOperand = false;
Matthew Simpson29dc0f72015-09-10 21:12:57 +0000111 unsigned DstSize = RT->getPrimitiveSizeInBits();
Chad Rosierc94f8e22015-08-27 14:12:17 +0000112 Worklist.push_back(Exit);
113
114 // Traverse the instructions in the reduction expression, beginning with the
115 // exit value.
116 while (!Worklist.empty()) {
117 Instruction *I = Worklist.pop_back_val();
118 for (Use &U : I->operands()) {
119
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)
124 continue;
125
126 // Otherwise, investigate the operation if it is also in the expression.
127 if (Visited.count(J)) {
128 Worklist.push_back(J);
129 continue;
130 }
131
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
Matthew Simpson29dc0f72015-09-10 21:12:57 +0000134 // zero-extend instruction.
Chad Rosierc94f8e22015-08-27 14:12:17 +0000135 CastInst *Cast = dyn_cast<CastInst>(J);
136 bool IsSExtInst = isa<SExtInst>(J);
Matthew Simpson29dc0f72015-09-10 21:12:57 +0000137 if (!Cast || !Cast->hasOneUse() || !(isa<ZExtInst>(J) || IsSExtInst))
138 return false;
139
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)
Chad Rosierc94f8e22015-08-27 14:12:17 +0000144 return false;
145
146 // Furthermore, ensure that all such extends are of the same kind.
147 if (FoundOneOperand) {
148 if (IsSigned != IsSExtInst)
149 return false;
150 } else {
151 FoundOneOperand = true;
152 IsSigned = IsSExtInst;
153 }
154
Matthew Simpson29dc0f72015-09-10 21:12:57 +0000155 // 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
157 // cost model.
158 if (SrcSize == DstSize)
159 CI.insert(Cast);
Chad Rosierc94f8e22015-08-27 14:12:17 +0000160 }
161 }
162 return true;
163}
164
Tyler Nowicki0a913102015-06-16 18:07:34 +0000165bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
166 Loop *TheLoop, bool HasFunNoNaNAttr,
167 RecurrenceDescriptor &RedDes) {
Karthik Bhat76aa6622015-04-20 04:38:33 +0000168 if (Phi->getNumIncomingValues() != 2)
169 return false;
170
171 // Reduction variables are only found in the loop header block.
172 if (Phi->getParent() != TheLoop->getHeader())
173 return false;
174
175 // Obtain the reduction start value from the value that comes from the loop
176 // preheader.
177 Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
178
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;
186
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;
192
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;
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000197 InstDesc ReduxDesc(false, nullptr);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000198
Chad Rosierc94f8e22015-08-27 14:12:17 +0000199 // 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;
204
Karthik Bhat76aa6622015-04-20 04:38:33 +0000205 SmallPtrSet<Instruction *, 8> VisitedInsts;
206 SmallVector<Instruction *, 8> Worklist;
Chad Rosierc94f8e22015-08-27 14:12:17 +0000207
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))
215 return false;
216 } else {
217 if (!isIntegerRecurrenceKind(Kind))
218 return false;
219 if (isArithmeticRecurrenceKind(Kind))
220 Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
221 }
222
223 Worklist.push_back(Start);
224 VisitedInsts.insert(Start);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000225
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).
231 // - PHI:
232 // - All uses of the PHI must be the reduction (safe).
233 // - Otherwise, not safe.
Michael Kuperstein7cefb402017-01-18 19:02:52 +0000234 // - 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.
Karthik Bhat76aa6622015-04-20 04:38:33 +0000237 // - By an instruction that is not part of the reduction (not safe).
238 // This is either:
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();
243 Worklist.pop_back();
244
245 // No Users.
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())
249 return false;
250
251 bool IsAPhi = isa<PHINode>(Cur);
252
253 // A header PHI use other than the original PHI.
254 if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
255 return false;
256
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))))
262 return false;
263
Chad Rosierc94f8e22015-08-27 14:12:17 +0000264 // 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
266 // type-promoted).
267 if (Cur != Start) {
268 ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
269 if (!ReduxDesc.isRecurrence())
270 return false;
271 }
Karthik Bhat76aa6622015-04-20 04:38:33 +0000272
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))
276 return false;
277
278 // All inputs to a PHI node must be a reduction value.
279 if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
280 return false;
281
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;
287
288 // Check whether we found a reduction operator.
Chad Rosierc94f8e22015-08-27 14:12:17 +0000289 FoundReduxOp |= !IsAPhi && Cur != Start;
Karthik Bhat76aa6622015-04-20 04:38:33 +0000290
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);
298
299 // Check if we found the exit user.
300 BasicBlock *Parent = UI->getParent();
301 if (!TheLoop->contains(Parent)) {
Michael Kuperstein7cefb402017-01-18 19:02:52 +0000302 // If we already know this instruction is used externally, move on to
303 // the next user.
304 if (ExitInstruction == Cur)
305 continue;
306
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.
Karthik Bhat76aa6622015-04-20 04:38:33 +0000311 if (ExitInstruction != nullptr || Cur == Phi)
312 return false;
313
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.
David Majnemer42531262016-08-12 03:55:06 +0000317 if (!is_contained(Phi->operands(), Cur))
Karthik Bhat76aa6622015-04-20 04:38:33 +0000318 return false;
319
320 ExitInstruction = Cur;
321 continue;
322 }
323
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.
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000327 InstDesc IgnoredVal(false, nullptr);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000328 if (VisitedInsts.insert(UI).second) {
329 if (isa<PHINode>(UI))
330 PHIs.push_back(UI);
331 else
332 NonPHIs.push_back(UI);
333 } else if (!isa<PHINode>(UI) &&
334 ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
335 !isa<SelectInst>(UI)) ||
Tyler Nowicki0a913102015-06-16 18:07:34 +0000336 !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence()))
Karthik Bhat76aa6622015-04-20 04:38:33 +0000337 return false;
338
339 // Remember that we completed the cycle.
340 if (UI == Phi)
341 FoundStartPHI = true;
342 }
343 Worklist.append(PHIs.begin(), PHIs.end());
344 Worklist.append(NonPHIs.begin(), NonPHIs.end());
345 }
346
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)
351 return false;
352
353 if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
354 return false;
355
Chad Rosierc94f8e22015-08-27 14:12:17 +0000356 // 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.
359 if (Start != Phi)
360 if (!getSourceExtensionKind(Start, ExitInstruction, RecurrenceType,
361 IsSigned, VisitedInsts, CastInsts))
362 return false;
363
Karthik Bhat76aa6622015-04-20 04:38:33 +0000364 // 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.
366
367 // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
Tyler Nowicki0a913102015-06-16 18:07:34 +0000368 // is saved as part of the RecurrenceDescriptor.
Karthik Bhat76aa6622015-04-20 04:38:33 +0000369
370 // Save the description of this reduction variable.
Chad Rosierc94f8e22015-08-27 14:12:17 +0000371 RecurrenceDescriptor RD(
372 RdxStart, ExitInstruction, Kind, ReduxDesc.getMinMaxKind(),
373 ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000374 RedDes = RD;
375
376 return true;
377}
378
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).
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000381RecurrenceDescriptor::InstDesc
382RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) {
Karthik Bhat76aa6622015-04-20 04:38:33 +0000383
384 assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
385 "Expect a select instruction");
386 Instruction *Cmp = nullptr;
387 SelectInst *Select = nullptr;
388
389 // We must handle the select(cmp()) as a single instruction. Advance to the
390 // select.
391 if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
392 if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000393 return InstDesc(false, I);
394 return InstDesc(Select, Prev.getMinMaxKind());
Karthik Bhat76aa6622015-04-20 04:38:33 +0000395 }
396
397 // Only handle single use cases for now.
398 if (!(Select = dyn_cast<SelectInst>(I)))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000399 return InstDesc(false, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000400 if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
401 !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000402 return InstDesc(false, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000403 if (!Cmp->hasOneUse())
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000404 return InstDesc(false, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000405
406 Value *CmpLeft;
407 Value *CmpRight;
408
409 // Look for a min/max pattern.
410 if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000411 return InstDesc(Select, MRK_UIntMin);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000412 else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000413 return InstDesc(Select, MRK_UIntMax);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000414 else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000415 return InstDesc(Select, MRK_SIntMax);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000416 else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000417 return InstDesc(Select, MRK_SIntMin);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000418 else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000419 return InstDesc(Select, MRK_FloatMin);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000420 else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000421 return InstDesc(Select, MRK_FloatMax);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000422 else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000423 return InstDesc(Select, MRK_FloatMin);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000424 else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000425 return InstDesc(Select, MRK_FloatMax);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000426
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000427 return InstDesc(false, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000428}
429
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000430RecurrenceDescriptor::InstDesc
Tyler Nowicki0a913102015-06-16 18:07:34 +0000431RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000432 InstDesc &Prev, bool HasFunNoNaNAttr) {
Karthik Bhat76aa6622015-04-20 04:38:33 +0000433 bool FP = I->getType()->isFloatingPointTy();
Tyler Nowickic1a86f52015-08-10 19:51:46 +0000434 Instruction *UAI = Prev.getUnsafeAlgebraInst();
Sanjay Patel629c4112017-11-06 16:27:15 +0000435 if (!UAI && FP && !I->isFast())
Tyler Nowickic1a86f52015-08-10 19:51:46 +0000436 UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
437
Karthik Bhat76aa6622015-04-20 04:38:33 +0000438 switch (I->getOpcode()) {
439 default:
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000440 return InstDesc(false, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000441 case Instruction::PHI:
Tim Northover10a1e8b2016-05-27 16:40:27 +0000442 return InstDesc(I, Prev.getMinMaxKind(), Prev.getUnsafeAlgebraInst());
Karthik Bhat76aa6622015-04-20 04:38:33 +0000443 case Instruction::Sub:
444 case Instruction::Add:
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000445 return InstDesc(Kind == RK_IntegerAdd, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000446 case Instruction::Mul:
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000447 return InstDesc(Kind == RK_IntegerMult, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000448 case Instruction::And:
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000449 return InstDesc(Kind == RK_IntegerAnd, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000450 case Instruction::Or:
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000451 return InstDesc(Kind == RK_IntegerOr, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000452 case Instruction::Xor:
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000453 return InstDesc(Kind == RK_IntegerXor, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000454 case Instruction::FMul:
Tyler Nowickic1a86f52015-08-10 19:51:46 +0000455 return InstDesc(Kind == RK_FloatMult, I, UAI);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000456 case Instruction::FSub:
457 case Instruction::FAdd:
Tyler Nowickic1a86f52015-08-10 19:51:46 +0000458 return InstDesc(Kind == RK_FloatAdd, I, UAI);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000459 case Instruction::FCmp:
460 case Instruction::ICmp:
461 case Instruction::Select:
462 if (Kind != RK_IntegerMinMax &&
463 (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000464 return InstDesc(false, I);
Karthik Bhat76aa6622015-04-20 04:38:33 +0000465 return isMinMaxSelectCmpPattern(I, Prev);
466 }
467}
468
Tyler Nowicki0a913102015-06-16 18:07:34 +0000469bool RecurrenceDescriptor::hasMultipleUsesOf(
Karthik Bhat76aa6622015-04-20 04:38:33 +0000470 Instruction *I, SmallPtrSetImpl<Instruction *> &Insts) {
471 unsigned NumUses = 0;
472 for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
473 ++Use) {
474 if (Insts.count(dyn_cast<Instruction>(*Use)))
475 ++NumUses;
476 if (NumUses > 1)
477 return true;
478 }
479
480 return false;
481}
Tyler Nowicki0a913102015-06-16 18:07:34 +0000482bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
483 RecurrenceDescriptor &RedDes) {
Karthik Bhat76aa6622015-04-20 04:38:33 +0000484
Karthik Bhat76aa6622015-04-20 04:38:33 +0000485 BasicBlock *Header = TheLoop->getHeader();
486 Function &F = *Header->getParent();
Nirav Dave8dd66e52016-03-30 15:41:12 +0000487 bool HasFunNoNaNAttr =
488 F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
Karthik Bhat76aa6622015-04-20 04:38:33 +0000489
490 if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
491 DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
492 return true;
493 }
494 if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
495 DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
496 return true;
497 }
498 if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes)) {
499 DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
500 return true;
501 }
502 if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes)) {
503 DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
504 return true;
505 }
506 if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes)) {
507 DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
508 return true;
509 }
510 if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr,
511 RedDes)) {
512 DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
513 return true;
514 }
515 if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
516 DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
517 return true;
518 }
519 if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
520 DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
521 return true;
522 }
523 if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) {
524 DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi << "\n");
525 return true;
526 }
527 // Not a reduction of known type.
528 return false;
529}
530
Ayal Zaks2ff59d42017-06-30 21:05:06 +0000531bool RecurrenceDescriptor::isFirstOrderRecurrence(
532 PHINode *Phi, Loop *TheLoop,
533 DenseMap<Instruction *, Instruction *> &SinkAfter, DominatorTree *DT) {
Matthew Simpson29c997c2016-02-19 17:56:08 +0000534
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)
538 return false;
539
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)
545 return false;
546
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)
550 return false;
551
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));
Ayal Zaks2ff59d42017-06-30 21:05:06 +0000555 if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) ||
556 SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.
Matthew Simpson29c997c2016-02-19 17:56:08 +0000557 return false;
558
Anna Thomasdcdb3252017-04-13 18:59:25 +0000559 // 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.
Ayal Zaks2ff59d42017-06-30 21:05:06 +0000562 // 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())) {
Ayal Zaks25e28002017-08-15 08:32:59 +0000568 if (!DT->dominates(Previous, I)) // Otherwise we're good w/o sinking.
569 SinkAfter[I] = Previous;
Ayal Zaks2ff59d42017-06-30 21:05:06 +0000570 return true;
571 }
572 }
573
Matthew Simpson29c997c2016-02-19 17:56:08 +0000574 for (User *U : Phi->users())
Anna Thomas00dc1b72017-04-11 21:02:00 +0000575 if (auto *I = dyn_cast<Instruction>(U)) {
Matthew Simpson29c997c2016-02-19 17:56:08 +0000576 if (!DT->dominates(Previous, I))
577 return false;
Anna Thomas00dc1b72017-04-11 21:02:00 +0000578 }
Matthew Simpson29c997c2016-02-19 17:56:08 +0000579
580 return true;
581}
582
Karthik Bhat76aa6622015-04-20 04:38:33 +0000583/// This function returns the identity element (or neutral element) for
584/// the operation K.
Tyler Nowicki0a913102015-06-16 18:07:34 +0000585Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K,
586 Type *Tp) {
Karthik Bhat76aa6622015-04-20 04:38:33 +0000587 switch (K) {
588 case RK_IntegerXor:
589 case RK_IntegerAdd:
590 case RK_IntegerOr:
591 // Adding, Xoring, Oring zero to a number does not change it.
592 return ConstantInt::get(Tp, 0);
593 case RK_IntegerMult:
594 // Multiplying a number by 1 does not change it.
595 return ConstantInt::get(Tp, 1);
596 case RK_IntegerAnd:
597 // AND-ing a number with an all-1 value does not change it.
598 return ConstantInt::get(Tp, -1, true);
599 case RK_FloatMult:
600 // Multiplying a number by 1 does not change it.
601 return ConstantFP::get(Tp, 1.0L);
602 case RK_FloatAdd:
603 // Adding zero to a number does not change it.
604 return ConstantFP::get(Tp, 0.0L);
605 default:
Tyler Nowicki0a913102015-06-16 18:07:34 +0000606 llvm_unreachable("Unknown recurrence kind");
Karthik Bhat76aa6622015-04-20 04:38:33 +0000607 }
608}
609
Tyler Nowicki0a913102015-06-16 18:07:34 +0000610/// This function translates the recurrence kind to an LLVM binary operator.
611unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) {
Karthik Bhat76aa6622015-04-20 04:38:33 +0000612 switch (Kind) {
613 case RK_IntegerAdd:
614 return Instruction::Add;
615 case RK_IntegerMult:
616 return Instruction::Mul;
617 case RK_IntegerOr:
618 return Instruction::Or;
619 case RK_IntegerAnd:
620 return Instruction::And;
621 case RK_IntegerXor:
622 return Instruction::Xor;
623 case RK_FloatMult:
624 return Instruction::FMul;
625 case RK_FloatAdd:
626 return Instruction::FAdd;
627 case RK_IntegerMinMax:
628 return Instruction::ICmp;
629 case RK_FloatMinMax:
630 return Instruction::FCmp;
631 default:
Tyler Nowicki0a913102015-06-16 18:07:34 +0000632 llvm_unreachable("Unknown recurrence operation");
Karthik Bhat76aa6622015-04-20 04:38:33 +0000633 }
634}
635
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000636Value *RecurrenceDescriptor::createMinMaxOp(IRBuilder<> &Builder,
637 MinMaxRecurrenceKind RK,
638 Value *Left, Value *Right) {
Karthik Bhat76aa6622015-04-20 04:38:33 +0000639 CmpInst::Predicate P = CmpInst::ICMP_NE;
640 switch (RK) {
641 default:
Tyler Nowicki0a913102015-06-16 18:07:34 +0000642 llvm_unreachable("Unknown min/max recurrence kind");
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000643 case MRK_UIntMin:
Karthik Bhat76aa6622015-04-20 04:38:33 +0000644 P = CmpInst::ICMP_ULT;
645 break;
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000646 case MRK_UIntMax:
Karthik Bhat76aa6622015-04-20 04:38:33 +0000647 P = CmpInst::ICMP_UGT;
648 break;
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000649 case MRK_SIntMin:
Karthik Bhat76aa6622015-04-20 04:38:33 +0000650 P = CmpInst::ICMP_SLT;
651 break;
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000652 case MRK_SIntMax:
Karthik Bhat76aa6622015-04-20 04:38:33 +0000653 P = CmpInst::ICMP_SGT;
654 break;
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000655 case MRK_FloatMin:
Karthik Bhat76aa6622015-04-20 04:38:33 +0000656 P = CmpInst::FCMP_OLT;
657 break;
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000658 case MRK_FloatMax:
Karthik Bhat76aa6622015-04-20 04:38:33 +0000659 P = CmpInst::FCMP_OGT;
660 break;
661 }
662
Sanjay Patel629c4112017-11-06 16:27:15 +0000663 // We only match FP sequences that are 'fast', so we can unconditionally
James Molloy50a4c272015-09-21 19:41:19 +0000664 // set it on any generated instructions.
665 IRBuilder<>::FastMathFlagGuard FMFG(Builder);
666 FastMathFlags FMF;
Sanjay Patel629c4112017-11-06 16:27:15 +0000667 FMF.setFast();
Sanjay Patela2528152016-01-12 18:03:37 +0000668 Builder.setFastMathFlags(FMF);
James Molloy50a4c272015-09-21 19:41:19 +0000669
Karthik Bhat76aa6622015-04-20 04:38:33 +0000670 Value *Cmp;
Tyler Nowicki27b2c392015-06-16 22:59:45 +0000671 if (RK == MRK_FloatMin || RK == MRK_FloatMax)
Karthik Bhat76aa6622015-04-20 04:38:33 +0000672 Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
673 else
674 Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
675
676 Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
677 return Select;
678}
Karthik Bhat24e6cc22015-04-23 08:29:20 +0000679
James Molloy1bbf15c2015-08-27 09:53:00 +0000680InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
Dorit Nuzman4750c782017-12-14 07:56:31 +0000681 const SCEV *Step, BinaryOperator *BOp,
682 SmallVectorImpl<Instruction *> *Casts)
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000683 : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
James Molloy1bbf15c2015-08-27 09:53:00 +0000684 assert(IK != IK_NoInduction && "Not an induction");
Elena Demikhovskyc434d092016-05-10 07:33:35 +0000685
686 // Start value type should match the induction kind and the value
687 // itself should not be null.
James Molloy1bbf15c2015-08-27 09:53:00 +0000688 assert(StartValue && "StartValue is null");
James Molloy1bbf15c2015-08-27 09:53:00 +0000689 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");
Elena Demikhovskyc434d092016-05-10 07:33:35 +0000693
694 // Check the Step Value. It should be non-zero integer value.
695 assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
696 "Step value is zero");
697
698 assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
699 "Step value should be constant for pointer induction");
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000700 assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
701 "StepValue is not an integer");
702
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");
Dorit Nuzman4750c782017-12-14 07:56:31 +0000709
710 if (Casts) {
711 for (auto &Inst : *Casts) {
712 RedundantCasts.push_back(Inst);
713 }
714 }
James Molloy1bbf15c2015-08-27 09:53:00 +0000715}
716
717int InductionDescriptor::getConsecutiveDirection() const {
Elena Demikhovskyc434d092016-05-10 07:33:35 +0000718 ConstantInt *ConstStep = getConstIntStepValue();
719 if (ConstStep && (ConstStep->isOne() || ConstStep->isMinusOne()))
720 return ConstStep->getSExtValue();
James Molloy1bbf15c2015-08-27 09:53:00 +0000721 return 0;
722}
723
Elena Demikhovskyc434d092016-05-10 07:33:35 +0000724ConstantInt *InductionDescriptor::getConstIntStepValue() const {
725 if (isa<SCEVConstant>(Step))
726 return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
727 return nullptr;
728}
729
730Value *InductionDescriptor::transform(IRBuilder<> &B, Value *Index,
731 ScalarEvolution *SE,
732 const DataLayout& DL) const {
733
734 SCEVExpander Exp(*SE, DL, "induction");
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000735 assert(Index->getType() == Step->getType() &&
736 "Index type does not match StepValue type");
James Molloy1bbf15c2015-08-27 09:53:00 +0000737 switch (IK) {
Elena Demikhovskyc434d092016-05-10 07:33:35 +0000738 case IK_IntInduction: {
James Molloy1bbf15c2015-08-27 09:53:00 +0000739 assert(Index->getType() == StartValue->getType() &&
740 "Index type does not match StartValue type");
Elena Demikhovskyc434d092016-05-10 07:33:35 +0000741
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.
749
750 if (getConstIntStepValue() &&
751 getConstIntStepValue()->isMinusOne())
James Molloy1bbf15c2015-08-27 09:53:00 +0000752 return B.CreateSub(StartValue, Index);
Elena Demikhovskyc434d092016-05-10 07:33:35 +0000753 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());
759 }
760 case IK_PtrInduction: {
Elena Demikhovskyc434d092016-05-10 07:33:35 +0000761 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());
James Molloy1bbf15c2015-08-27 09:53:00 +0000765 return B.CreateGEP(nullptr, StartValue, Index);
Elena Demikhovskyc434d092016-05-10 07:33:35 +0000766 }
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000767 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");
773
774 Value *StepValue = cast<SCEVUnknown>(Step)->getValue();
775
776 // Floating point operations had to be 'fast' to enable the induction.
777 FastMathFlags Flags;
Sanjay Patel629c4112017-11-06 16:27:15 +0000778 Flags.setFast();
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000779
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);
784
785 Value *BOp = B.CreateBinOp(InductionBinOp->getOpcode() , StartValue,
786 MulExp, "induction");
787 if (isa<Instruction>(BOp))
788 cast<Instruction>(BOp)->setFastMathFlags(Flags);
789
790 return BOp;
791 }
James Molloy1bbf15c2015-08-27 09:53:00 +0000792 case IK_NoInduction:
793 return nullptr;
794 }
795 llvm_unreachable("invalid enum");
796}
797
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000798bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop,
799 ScalarEvolution *SE,
800 InductionDescriptor &D) {
801
802 // Here we only handle FP induction variables.
803 assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
804
805 if (TheLoop->getHeader() != Phi->getParent())
806 return false;
807
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)
811 return false;
812 Value *BEValue = nullptr, *StartValue = nullptr;
813 if (TheLoop->contains(Phi->getIncomingBlock(0))) {
814 BEValue = Phi->getIncomingValue(0);
815 StartValue = Phi->getIncomingValue(1);
816 } else {
817 assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
Dorit Nuzman4750c782017-12-14 07:56:31 +0000818 "Unexpected Phi node in the loop");
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000819 BEValue = Phi->getIncomingValue(1);
820 StartValue = Phi->getIncomingValue(0);
821 }
822
823 BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
824 if (!BOp)
825 return false;
826
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);
836
837 if (!Addend)
838 return false;
839
840 // The addend should be loop invariant
841 if (auto *I = dyn_cast<Instruction>(Addend))
842 if (TheLoop->contains(I))
843 return false;
844
845 // FP Step has unknown SCEV
846 const SCEV *Step = SE->getUnknown(Addend);
847 D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
848 return true;
849}
850
Dorit Nuzman4750c782017-12-14 07:56:31 +0000851/// 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).
860///
861/// For example, without a predicate the scev expression can take the following
862/// form:
863/// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
864///
865/// It corresponds to the following IR sequence:
866/// %for.body:
867/// %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
868/// %casted_phi = "ExtTrunc i64 %x"
869/// %add = add i64 %casted_phi, %step
870///
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
876/// or:
877/// ExtTrunc2: %t = shl %x, m
878/// %casted_phi = ashr %t, m
879///
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).
883bool getCastsForInductionPHI(
884 PredicatedScalarEvolution &PSE, const SCEVUnknown *PhiScev,
885 const SCEVAddRecExpr *AR, SmallVectorImpl<Instruction *> &CastInsts) {
886
887 assert(CastInsts.empty() && "CastInsts is expected to be empty.");
888 auto *PN = cast<PHINode>(PhiScev->getValue());
889 assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression");
890 const Loop *L = AR->getLoop();
891
892 // Find any cast instructions that participate in the def-use chain of
893 // PhiScev in the loop.
894 // FORNOW/TODO: We currently expect the def-use chain to include only
895 // two-operand instructions, where one of the operands is an invariant.
896 // createAddRecFromPHIWithCasts() currently does not support anything more
897 // involved than that, so we keep the search simple. This can be
898 // extended/generalized as needed.
899
900 auto getDef = [&](const Value *Val) -> Value * {
901 const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
902 if (!BinOp)
903 return nullptr;
904 Value *Op0 = BinOp->getOperand(0);
905 Value *Op1 = BinOp->getOperand(1);
906 Value *Def = nullptr;
907 if (L->isLoopInvariant(Op0))
908 Def = Op1;
909 else if (L->isLoopInvariant(Op1))
910 Def = Op0;
911 return Def;
912 };
913
914 // Look for the instruction that defines the induction via the
915 // loop backedge.
916 BasicBlock *Latch = L->getLoopLatch();
917 if (!Latch)
918 return false;
919 Value *Val = PN->getIncomingValueForBlock(Latch);
920 if (!Val)
921 return false;
922
923 // Follow the def-use chain until the induction phi is reached.
924 // If on the way we encounter a Value that has the same SCEV Expr as the
925 // phi node, we can consider the instructions we visit from that point
926 // as part of the cast-sequence that can be ignored.
927 bool InCastSequence = false;
928 auto *Inst = dyn_cast<Instruction>(Val);
929 while (Val != PN) {
930 // If we encountered a phi node other than PN, or if we left the loop,
931 // we bail out.
932 if (!Inst || !L->contains(Inst)) {
933 return false;
934 }
935 auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val));
936 if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR))
937 InCastSequence = true;
938 if (InCastSequence) {
939 // Only the last instruction in the cast sequence is expected to have
940 // uses outside the induction def-use chain.
941 if (!CastInsts.empty())
942 if (!Inst->hasOneUse())
943 return false;
944 CastInsts.push_back(Inst);
945 }
946 Val = getDef(Val);
947 if (!Val)
948 return false;
949 Inst = dyn_cast<Instruction>(Val);
950 }
951
952 return InCastSequence;
953}
954
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000955bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
Silviu Barangac05bab82016-05-05 15:20:39 +0000956 PredicatedScalarEvolution &PSE,
957 InductionDescriptor &D,
958 bool Assume) {
959 Type *PhiTy = Phi->getType();
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000960
961 // Handle integer and pointer inductions variables.
962 // Now we handle also FP induction but not trying to make a
963 // recurrent expression from the PHI node in-place.
964
965 if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() &&
966 !PhiTy->isFloatTy() && !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
Silviu Barangac05bab82016-05-05 15:20:39 +0000967 return false;
968
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000969 if (PhiTy->isFloatingPointTy())
970 return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);
971
Silviu Barangac05bab82016-05-05 15:20:39 +0000972 const SCEV *PhiScev = PSE.getSCEV(Phi);
973 const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
974
975 // We need this expression to be an AddRecExpr.
976 if (Assume && !AR)
977 AR = PSE.getAsAddRec(Phi);
978
979 if (!AR) {
980 DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
981 return false;
982 }
983
Dorit Nuzman4750c782017-12-14 07:56:31 +0000984 // Record any Cast instructions that participate in the induction update
985 const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
986 // If we started from an UnknownSCEV, and managed to build an addRecurrence
987 // only after enabling Assume with PSCEV, this means we may have encountered
988 // cast instructions that required adding a runtime check in order to
989 // guarantee the correctness of the AddRecurence respresentation of the
990 // induction.
991 if (PhiScev != AR && SymbolicPhi) {
992 SmallVector<Instruction *, 2> Casts;
993 if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts))
994 return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts);
995 }
996
Elena Demikhovsky376a18b2016-07-24 07:24:54 +0000997 return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
Silviu Barangac05bab82016-05-05 15:20:39 +0000998}
999
Dorit Nuzman4750c782017-12-14 07:56:31 +00001000bool InductionDescriptor::isInductionPHI(
1001 PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
1002 InductionDescriptor &D, const SCEV *Expr,
1003 SmallVectorImpl<Instruction *> *CastsToIgnore) {
Karthik Bhat24e6cc22015-04-23 08:29:20 +00001004 Type *PhiTy = Phi->getType();
1005 // We only handle integer and pointer inductions variables.
1006 if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
1007 return false;
1008
1009 // Check that the PHI is consecutive.
Silviu Barangac05bab82016-05-05 15:20:39 +00001010 const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
Karthik Bhat24e6cc22015-04-23 08:29:20 +00001011 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
Silviu Barangac05bab82016-05-05 15:20:39 +00001012
Karthik Bhat24e6cc22015-04-23 08:29:20 +00001013 if (!AR) {
1014 DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1015 return false;
1016 }
1017
Michael Kupersteinee31cbe2017-01-10 19:32:30 +00001018 if (AR->getLoop() != TheLoop) {
1019 // FIXME: We should treat this as a uniform. Unfortunately, we
1020 // don't currently know how to handled uniform PHIs.
1021 DEBUG(dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
Dorit Nuzman4750c782017-12-14 07:56:31 +00001022 return false;
Michael Kupersteinee31cbe2017-01-10 19:32:30 +00001023 }
1024
James Molloy1bbf15c2015-08-27 09:53:00 +00001025 Value *StartValue =
1026 Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
Karthik Bhat24e6cc22015-04-23 08:29:20 +00001027 const SCEV *Step = AR->getStepRecurrence(*SE);
1028 // Calculate the pointer stride and check if it is consecutive.
Elena Demikhovskyc434d092016-05-10 07:33:35 +00001029 // The stride may be a constant or a loop invariant integer value.
1030 const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
Elena Demikhovsky376a18b2016-07-24 07:24:54 +00001031 if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
Karthik Bhat24e6cc22015-04-23 08:29:20 +00001032 return false;
1033
Karthik Bhat24e6cc22015-04-23 08:29:20 +00001034 if (PhiTy->isIntegerTy()) {
Dorit Nuzman4750c782017-12-14 07:56:31 +00001035 D = InductionDescriptor(StartValue, IK_IntInduction, Step, /*BOp=*/ nullptr,
1036 CastsToIgnore);
Karthik Bhat24e6cc22015-04-23 08:29:20 +00001037 return true;
1038 }
1039
1040 assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
Elena Demikhovskyc434d092016-05-10 07:33:35 +00001041 // Pointer induction should be a constant.
1042 if (!ConstStep)
1043 return false;
1044
1045 ConstantInt *CV = ConstStep->getValue();
Karthik Bhat24e6cc22015-04-23 08:29:20 +00001046 Type *PointerElementType = PhiTy->getPointerElementType();
1047 // The pointer stride cannot be determined if the pointer element type is not
1048 // sized.
1049 if (!PointerElementType->isSized())
1050 return false;
1051
1052 const DataLayout &DL = Phi->getModule()->getDataLayout();
1053 int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
David Majnemerb58f32f2015-06-05 10:52:40 +00001054 if (!Size)
1055 return false;
1056
Karthik Bhat24e6cc22015-04-23 08:29:20 +00001057 int64_t CVSize = CV->getSExtValue();
1058 if (CVSize % Size)
1059 return false;
Elena Demikhovskyc434d092016-05-10 07:33:35 +00001060 auto *StepValue = SE->getConstant(CV->getType(), CVSize / Size,
1061 true /* signed */);
James Molloy1bbf15c2015-08-27 09:53:00 +00001062 D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue);
Karthik Bhat24e6cc22015-04-23 08:29:20 +00001063 return true;
1064}
Ashutosh Nemac5b7b552015-08-19 05:40:42 +00001065
Chandler Carruth4a000882017-06-25 22:45:31 +00001066bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
1067 bool PreserveLCSSA) {
1068 bool Changed = false;
1069
1070 // We re-use a vector for the in-loop predecesosrs.
1071 SmallVector<BasicBlock *, 4> InLoopPredecessors;
1072
1073 auto RewriteExit = [&](BasicBlock *BB) {
1074 assert(InLoopPredecessors.empty() &&
1075 "Must start with an empty predecessors list!");
1076 auto Cleanup = make_scope_exit([&] { InLoopPredecessors.clear(); });
1077
1078 // See if there are any non-loop predecessors of this exit block and
1079 // keep track of the in-loop predecessors.
1080 bool IsDedicatedExit = true;
1081 for (auto *PredBB : predecessors(BB))
1082 if (L->contains(PredBB)) {
1083 if (isa<IndirectBrInst>(PredBB->getTerminator()))
1084 // We cannot rewrite exiting edges from an indirectbr.
1085 return false;
1086
1087 InLoopPredecessors.push_back(PredBB);
1088 } else {
1089 IsDedicatedExit = false;
1090 }
1091
1092 assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!");
1093
1094 // Nothing to do if this is already a dedicated exit.
1095 if (IsDedicatedExit)
1096 return false;
1097
1098 auto *NewExitBB = SplitBlockPredecessors(
1099 BB, InLoopPredecessors, ".loopexit", DT, LI, PreserveLCSSA);
1100
1101 if (!NewExitBB)
1102 DEBUG(dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
1103 << *L << "\n");
1104 else
1105 DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
1106 << NewExitBB->getName() << "\n");
1107 return true;
1108 };
1109
1110 // Walk the exit blocks directly rather than building up a data structure for
1111 // them, but only visit each one once.
1112 SmallPtrSet<BasicBlock *, 4> Visited;
1113 for (auto *BB : L->blocks())
1114 for (auto *SuccBB : successors(BB)) {
1115 // We're looking for exit blocks so skip in-loop successors.
1116 if (L->contains(SuccBB))
1117 continue;
1118
1119 // Visit each exit block exactly once.
1120 if (!Visited.insert(SuccBB).second)
1121 continue;
1122
1123 Changed |= RewriteExit(SuccBB);
1124 }
1125
1126 return Changed;
1127}
1128
Ashutosh Nemac5b7b552015-08-19 05:40:42 +00001129/// \brief Returns the instructions that use values defined in the loop.
1130SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) {
1131 SmallVector<Instruction *, 8> UsedOutside;
1132
1133 for (auto *Block : L->getBlocks())
1134 // FIXME: I believe that this could use copy_if if the Inst reference could
1135 // be adapted into a pointer.
1136 for (auto &Inst : *Block) {
1137 auto Users = Inst.users();
David Majnemer0a16c222016-08-11 21:15:00 +00001138 if (any_of(Users, [&](User *U) {
Ashutosh Nemac5b7b552015-08-19 05:40:42 +00001139 auto *Use = cast<Instruction>(U);
1140 return !L->contains(Use->getParent());
1141 }))
1142 UsedOutside.push_back(&Inst);
1143 }
1144
1145 return UsedOutside;
1146}
Chandler Carruth31088a92016-02-19 10:45:18 +00001147
1148void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) {
1149 // By definition, all loop passes need the LoopInfo analysis and the
1150 // Dominator tree it depends on. Because they all participate in the loop
1151 // pass manager, they must also preserve these.
1152 AU.addRequired<DominatorTreeWrapperPass>();
1153 AU.addPreserved<DominatorTreeWrapperPass>();
1154 AU.addRequired<LoopInfoWrapperPass>();
1155 AU.addPreserved<LoopInfoWrapperPass>();
1156
1157 // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
1158 // here because users shouldn't directly get them from this header.
1159 extern char &LoopSimplifyID;
1160 extern char &LCSSAID;
1161 AU.addRequiredID(LoopSimplifyID);
1162 AU.addPreservedID(LoopSimplifyID);
1163 AU.addRequiredID(LCSSAID);
1164 AU.addPreservedID(LCSSAID);
Igor Laevskyc3ccf5d2016-10-28 12:57:20 +00001165 // This is used in the LPPassManager to perform LCSSA verification on passes
1166 // which preserve lcssa form
1167 AU.addRequired<LCSSAVerificationPass>();
1168 AU.addPreserved<LCSSAVerificationPass>();
Chandler Carruth31088a92016-02-19 10:45:18 +00001169
1170 // Loop passes are designed to run inside of a loop pass manager which means
1171 // that any function analyses they require must be required by the first loop
1172 // pass in the manager (so that it is computed before the loop pass manager
1173 // runs) and preserved by all loop pasess in the manager. To make this
1174 // reasonably robust, the set needed for most loop passes is maintained here.
1175 // If your loop pass requires an analysis not listed here, you will need to
1176 // carefully audit the loop pass manager nesting structure that results.
1177 AU.addRequired<AAResultsWrapperPass>();
1178 AU.addPreserved<AAResultsWrapperPass>();
1179 AU.addPreserved<BasicAAWrapperPass>();
1180 AU.addPreserved<GlobalsAAWrapperPass>();
1181 AU.addPreserved<SCEVAAWrapperPass>();
1182 AU.addRequired<ScalarEvolutionWrapperPass>();
1183 AU.addPreserved<ScalarEvolutionWrapperPass>();
1184}
1185
1186/// Manually defined generic "LoopPass" dependency initialization. This is used
1187/// to initialize the exact set of passes from above in \c
1188/// getLoopAnalysisUsage. It can be used within a loop pass's initialization
1189/// with:
1190///
1191/// INITIALIZE_PASS_DEPENDENCY(LoopPass)
1192///
1193/// As-if "LoopPass" were a pass.
1194void llvm::initializeLoopPassPass(PassRegistry &Registry) {
1195 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1196 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1197 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
Easwaran Ramane12c4872016-06-09 19:44:46 +00001198 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
Chandler Carruth31088a92016-02-19 10:45:18 +00001199 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
1200 INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
1201 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
1202 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
1203 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
1204}
Adam Nemet963341c2016-04-21 17:33:17 +00001205
Adam Nemetfe3def72016-04-22 19:10:05 +00001206/// \brief Find string metadata for loop
1207///
1208/// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
1209/// operand or null otherwise. If the string metadata is not found return
1210/// Optional's not-a-value.
1211Optional<const MDOperand *> llvm::findStringMetadataForLoop(Loop *TheLoop,
1212 StringRef Name) {
Adam Nemet963341c2016-04-21 17:33:17 +00001213 MDNode *LoopID = TheLoop->getLoopID();
Adam Nemetfe3def72016-04-22 19:10:05 +00001214 // Return none if LoopID is false.
Adam Nemet963341c2016-04-21 17:33:17 +00001215 if (!LoopID)
Adam Nemetfe3def72016-04-22 19:10:05 +00001216 return None;
Adam Nemet293be662016-04-21 17:33:20 +00001217
1218 // First operand should refer to the loop id itself.
1219 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
1220 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
1221
Adam Nemet963341c2016-04-21 17:33:17 +00001222 // Iterate over LoopID operands and look for MDString Metadata
1223 for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
1224 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
1225 if (!MD)
1226 continue;
1227 MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1228 if (!S)
1229 continue;
1230 // Return true if MDString holds expected MetaData.
1231 if (Name.equals(S->getString()))
Adam Nemetfe3def72016-04-22 19:10:05 +00001232 switch (MD->getNumOperands()) {
1233 case 1:
1234 return nullptr;
1235 case 2:
1236 return &MD->getOperand(1);
1237 default:
1238 llvm_unreachable("loop metadata has 0 or 1 operand");
1239 }
Adam Nemet963341c2016-04-21 17:33:17 +00001240 }
Adam Nemetfe3def72016-04-22 19:10:05 +00001241 return None;
Adam Nemet963341c2016-04-21 17:33:17 +00001242}
Evgeniy Stepanov122f9842016-06-10 20:03:17 +00001243
Alina Sbirlea7ed58562017-09-15 00:04:16 +00001244/// Does a BFS from a given node to all of its children inside a given loop.
1245/// The returned vector of nodes includes the starting point.
1246SmallVector<DomTreeNode *, 16>
1247llvm::collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop) {
1248 SmallVector<DomTreeNode *, 16> Worklist;
1249 auto AddRegionToWorklist = [&](DomTreeNode *DTN) {
1250 // Only include subregions in the top level loop.
1251 BasicBlock *BB = DTN->getBlock();
1252 if (CurLoop->contains(BB))
1253 Worklist.push_back(DTN);
1254 };
1255
1256 AddRegionToWorklist(N);
1257
1258 for (size_t I = 0; I < Worklist.size(); I++)
1259 for (DomTreeNode *Child : Worklist[I]->getChildren())
1260 AddRegionToWorklist(Child);
1261
1262 return Worklist;
1263}
1264
Marcello Maggionidf3e71e2017-10-04 20:42:46 +00001265void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT = nullptr,
1266 ScalarEvolution *SE = nullptr,
1267 LoopInfo *LI = nullptr) {
Hans Wennborg899809d2017-10-04 21:14:07 +00001268 assert((!DT || L->isLCSSAForm(*DT)) && "Expected LCSSA!");
Marcello Maggionidf3e71e2017-10-04 20:42:46 +00001269 auto *Preheader = L->getLoopPreheader();
1270 assert(Preheader && "Preheader should exist!");
1271
1272 // Now that we know the removal is safe, remove the loop by changing the
1273 // branch from the preheader to go to the single exit block.
1274 //
1275 // Because we're deleting a large chunk of code at once, the sequence in which
1276 // we remove things is very important to avoid invalidation issues.
1277
1278 // Tell ScalarEvolution that the loop is deleted. Do this before
1279 // deleting the loop so that ScalarEvolution can look at the loop
1280 // to determine what it needs to clean up.
1281 if (SE)
1282 SE->forgetLoop(L);
1283
1284 auto *ExitBlock = L->getUniqueExitBlock();
1285 assert(ExitBlock && "Should have a unique exit block!");
1286 assert(L->hasDedicatedExits() && "Loop should have dedicated exits!");
1287
1288 auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator());
1289 assert(OldBr && "Preheader must end with a branch");
1290 assert(OldBr->isUnconditional() && "Preheader must have a single successor");
1291 // Connect the preheader to the exit block. Keep the old edge to the header
1292 // around to perform the dominator tree update in two separate steps
1293 // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
1294 // preheader -> header.
1295 //
1296 //
1297 // 0. Preheader 1. Preheader 2. Preheader
1298 // | | | |
1299 // V | V |
1300 // Header <--\ | Header <--\ | Header <--\
1301 // | | | | | | | | | | |
1302 // | V | | | V | | | V |
1303 // | Body --/ | | Body --/ | | Body --/
1304 // V V V V V
1305 // Exit Exit Exit
1306 //
1307 // By doing this is two separate steps we can perform the dominator tree
1308 // update without using the batch update API.
1309 //
1310 // Even when the loop is never executed, we cannot remove the edge from the
1311 // source block to the exit block. Consider the case where the unexecuted loop
1312 // branches back to an outer loop. If we deleted the loop and removed the edge
1313 // coming to this inner loop, this will break the outer loop structure (by
1314 // deleting the backedge of the outer loop). If the outer loop is indeed a
1315 // non-loop, it will be deleted in a future iteration of loop deletion pass.
1316 IRBuilder<> Builder(OldBr);
1317 Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock);
1318 // Remove the old branch. The conditional branch becomes a new terminator.
1319 OldBr->eraseFromParent();
1320
1321 // Rewrite phis in the exit block to get their inputs from the Preheader
1322 // instead of the exiting block.
1323 BasicBlock::iterator BI = ExitBlock->begin();
1324 while (PHINode *P = dyn_cast<PHINode>(BI)) {
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.
1328 int PredIndex = 0;
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
1336 // being deleted).
1337 for (unsigned i = 0, e = P->getNumIncomingValues() - 1; i != e; ++i)
1338 P->removeIncomingValue(e - i, false);
1339
1340 assert((P->getNumIncomingValues() == 1 &&
1341 P->getIncomingBlock(PredIndex) == Preheader) &&
1342 "Should have exactly one value and that's from the preheader!");
1343 ++BI;
1344 }
1345
1346 // Disconnect the loop body by branching directly to its exit.
1347 Builder.SetInsertPoint(Preheader->getTerminator());
1348 Builder.CreateBr(ExitBlock);
1349 // Remove the old branch.
1350 Preheader->getTerminator()->eraseFromParent();
1351
1352 if (DT) {
1353 // Update the dominator tree by informing it about the new edge from the
1354 // preheader to the exit.
1355 DT->insertEdge(Preheader, ExitBlock);
1356 // Inform the dominator tree about the removed edge.
1357 DT->deleteEdge(Preheader, L->getHeader());
1358 }
1359
1360 // Remove the block from the reference counting scheme, so that we can
1361 // delete it freely later.
1362 for (auto *Block : L->blocks())
1363 Block->dropAllReferences();
1364
1365 if (LI) {
1366 // Erase the instructions and the blocks without having to worry
1367 // about ordering because we already dropped the references.
1368 // NOTE: This iteration is safe because erasing the block does not remove
1369 // its entry from the loop's block list. We do that in the next section.
1370 for (Loop::block_iterator LpI = L->block_begin(), LpE = L->block_end();
1371 LpI != LpE; ++LpI)
1372 (*LpI)->eraseFromParent();
1373
1374 // Finally, the blocks from loopinfo. This has to happen late because
1375 // otherwise our loop iterators won't work.
1376
1377 SmallPtrSet<BasicBlock *, 8> blocks;
1378 blocks.insert(L->block_begin(), L->block_end());
1379 for (BasicBlock *BB : blocks)
1380 LI->removeBlock(BB);
1381
1382 // The last step is to update LoopInfo now that we've eliminated this loop.
1383 LI->erase(L);
1384 }
1385}
1386
Evgeniy Stepanov122f9842016-06-10 20:03:17 +00001387/// Returns true if the instruction in a loop is guaranteed to execute at least
1388/// once.
1389bool llvm::isGuaranteedToExecute(const Instruction &Inst,
1390 const DominatorTree *DT, const Loop *CurLoop,
1391 const LoopSafetyInfo *SafetyInfo) {
1392 // We have to check to make sure that the instruction dominates all
Evgeniy Stepanov58ccc092017-04-24 18:25:07 +00001393 // of the exit blocks. If it doesn't, then there is a path out of the loop
1394 // which does not execute this instruction, so we can't hoist it.
1395
1396 // If the instruction is in the header block for the loop (which is very
1397 // common), it is always guaranteed to dominate the exit blocks. Since this
1398 // is a common case, and can save some work, check it now.
1399 if (Inst.getParent() == CurLoop->getHeader())
1400 // If there's a throw in the header block, we can't guarantee we'll reach
1401 // Inst.
1402 return !SafetyInfo->HeaderMayThrow;
1403
1404 // Somewhere in this loop there is an instruction which may throw and make us
1405 // exit the loop.
1406 if (SafetyInfo->MayThrow)
1407 return false;
Evgeniy Stepanov122f9842016-06-10 20:03:17 +00001408
1409 // Get the exit blocks for the current loop.
1410 SmallVector<BasicBlock *, 8> ExitBlocks;
1411 CurLoop->getExitBlocks(ExitBlocks);
1412
1413 // Verify that the block dominates each of the exit blocks of the loop.
1414 for (BasicBlock *ExitBlock : ExitBlocks)
1415 if (!DT->dominates(Inst.getParent(), ExitBlock))
1416 return false;
1417
1418 // As a degenerate case, if the loop is statically infinite then we haven't
1419 // proven anything since there are no exit blocks.
Evgeniy Stepanov58ccc092017-04-24 18:25:07 +00001420 if (ExitBlocks.empty())
Evgeniy Stepanov122f9842016-06-10 20:03:17 +00001421 return false;
1422
Eli Friedmanf1da33e2016-06-11 21:48:25 +00001423 // FIXME: In general, we have to prove that the loop isn't an infinite loop.
1424 // See http::llvm.org/PR24078 . (The "ExitBlocks.empty()" check above is
1425 // just a special case of this.)
Evgeniy Stepanov122f9842016-06-10 20:03:17 +00001426 return true;
1427}
Dehao Chen41d72a82016-11-17 01:17:02 +00001428
1429Optional<unsigned> llvm::getLoopEstimatedTripCount(Loop *L) {
1430 // Only support loops with a unique exiting block, and a latch.
1431 if (!L->getExitingBlock())
1432 return None;
1433
1434 // Get the branch weights for the the loop's backedge.
1435 BranchInst *LatchBR =
1436 dyn_cast<BranchInst>(L->getLoopLatch()->getTerminator());
1437 if (!LatchBR || LatchBR->getNumSuccessors() != 2)
1438 return None;
1439
1440 assert((LatchBR->getSuccessor(0) == L->getHeader() ||
1441 LatchBR->getSuccessor(1) == L->getHeader()) &&
1442 "At least one edge out of the latch must go to the header");
1443
1444 // To estimate the number of times the loop body was executed, we want to
1445 // know the number of times the backedge was taken, vs. the number of times
1446 // we exited the loop.
Dehao Chen41d72a82016-11-17 01:17:02 +00001447 uint64_t TrueVal, FalseVal;
Michael Kupersteinb151a642016-11-30 21:13:57 +00001448 if (!LatchBR->extractProfMetadata(TrueVal, FalseVal))
Dehao Chen41d72a82016-11-17 01:17:02 +00001449 return None;
1450
Michael Kupersteinb151a642016-11-30 21:13:57 +00001451 if (!TrueVal || !FalseVal)
1452 return 0;
Dehao Chen41d72a82016-11-17 01:17:02 +00001453
Michael Kupersteinb151a642016-11-30 21:13:57 +00001454 // Divide the count of the backedge by the count of the edge exiting the loop,
1455 // rounding to nearest.
Dehao Chen41d72a82016-11-17 01:17:02 +00001456 if (LatchBR->getSuccessor(0) == L->getHeader())
Michael Kupersteinb151a642016-11-30 21:13:57 +00001457 return (TrueVal + (FalseVal / 2)) / FalseVal;
Dehao Chen41d72a82016-11-17 01:17:02 +00001458 else
Michael Kupersteinb151a642016-11-30 21:13:57 +00001459 return (FalseVal + (TrueVal / 2)) / TrueVal;
Dehao Chen41d72a82016-11-17 01:17:02 +00001460}
Amara Emersoncf9daa32017-05-09 10:43:25 +00001461
1462/// \brief Adds a 'fast' flag to floating point operations.
1463static Value *addFastMathFlag(Value *V) {
1464 if (isa<FPMathOperator>(V)) {
1465 FastMathFlags Flags;
Sanjay Patel629c4112017-11-06 16:27:15 +00001466 Flags.setFast();
Amara Emersoncf9daa32017-05-09 10:43:25 +00001467 cast<Instruction>(V)->setFastMathFlags(Flags);
1468 }
1469 return V;
1470}
1471
1472// Helper to generate a log2 shuffle reduction.
Amara Emerson836b0f42017-05-10 09:42:49 +00001473Value *
1474llvm::getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op,
1475 RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind,
1476 ArrayRef<Value *> RedOps) {
Amara Emersoncf9daa32017-05-09 10:43:25 +00001477 unsigned VF = Src->getType()->getVectorNumElements();
1478 // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
1479 // and vector ops, reducing the set of values being computed by half each
1480 // round.
1481 assert(isPowerOf2_32(VF) &&
1482 "Reduction emission only supported for pow2 vectors!");
1483 Value *TmpVec = Src;
1484 SmallVector<Constant *, 32> ShuffleMask(VF, nullptr);
1485 for (unsigned i = VF; i != 1; i >>= 1) {
1486 // Move the upper half of the vector to the lower half.
1487 for (unsigned j = 0; j != i / 2; ++j)
1488 ShuffleMask[j] = Builder.getInt32(i / 2 + j);
1489
1490 // Fill the rest of the mask with undef.
1491 std::fill(&ShuffleMask[i / 2], ShuffleMask.end(),
1492 UndefValue::get(Builder.getInt32Ty()));
1493
1494 Value *Shuf = Builder.CreateShuffleVector(
1495 TmpVec, UndefValue::get(TmpVec->getType()),
1496 ConstantVector::get(ShuffleMask), "rdx.shuf");
1497
1498 if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
1499 // Floating point operations had to be 'fast' to enable the reduction.
1500 TmpVec = addFastMathFlag(Builder.CreateBinOp((Instruction::BinaryOps)Op,
1501 TmpVec, Shuf, "bin.rdx"));
1502 } else {
1503 assert(MinMaxKind != RecurrenceDescriptor::MRK_Invalid &&
1504 "Invalid min/max");
1505 TmpVec = RecurrenceDescriptor::createMinMaxOp(Builder, MinMaxKind, TmpVec,
1506 Shuf);
1507 }
1508 if (!RedOps.empty())
1509 propagateIRFlags(TmpVec, RedOps);
1510 }
1511 // The result is in the first element of the vector.
1512 return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
1513}
1514
1515/// Create a simple vector reduction specified by an opcode and some
1516/// flags (if generating min/max reductions).
1517Value *llvm::createSimpleTargetReduction(
1518 IRBuilder<> &Builder, const TargetTransformInfo *TTI, unsigned Opcode,
1519 Value *Src, TargetTransformInfo::ReductionFlags Flags,
1520 ArrayRef<Value *> RedOps) {
1521 assert(isa<VectorType>(Src->getType()) && "Type must be a vector");
1522
1523 Value *ScalarUdf = UndefValue::get(Src->getType()->getVectorElementType());
1524 std::function<Value*()> BuildFunc;
1525 using RD = RecurrenceDescriptor;
1526 RD::MinMaxRecurrenceKind MinMaxKind = RD::MRK_Invalid;
1527 // TODO: Support creating ordered reductions.
Sanjay Patel1ea7b6f2017-12-06 19:11:23 +00001528 FastMathFlags FMFFast;
1529 FMFFast.setFast();
Amara Emersoncf9daa32017-05-09 10:43:25 +00001530
1531 switch (Opcode) {
1532 case Instruction::Add:
1533 BuildFunc = [&]() { return Builder.CreateAddReduce(Src); };
1534 break;
1535 case Instruction::Mul:
1536 BuildFunc = [&]() { return Builder.CreateMulReduce(Src); };
1537 break;
1538 case Instruction::And:
1539 BuildFunc = [&]() { return Builder.CreateAndReduce(Src); };
1540 break;
1541 case Instruction::Or:
1542 BuildFunc = [&]() { return Builder.CreateOrReduce(Src); };
1543 break;
1544 case Instruction::Xor:
1545 BuildFunc = [&]() { return Builder.CreateXorReduce(Src); };
1546 break;
1547 case Instruction::FAdd:
1548 BuildFunc = [&]() {
1549 auto Rdx = Builder.CreateFAddReduce(ScalarUdf, Src);
Sanjay Patel1ea7b6f2017-12-06 19:11:23 +00001550 cast<CallInst>(Rdx)->setFastMathFlags(FMFFast);
Amara Emersoncf9daa32017-05-09 10:43:25 +00001551 return Rdx;
1552 };
1553 break;
1554 case Instruction::FMul:
1555 BuildFunc = [&]() {
1556 auto Rdx = Builder.CreateFMulReduce(ScalarUdf, Src);
Sanjay Patel1ea7b6f2017-12-06 19:11:23 +00001557 cast<CallInst>(Rdx)->setFastMathFlags(FMFFast);
Amara Emersoncf9daa32017-05-09 10:43:25 +00001558 return Rdx;
1559 };
1560 break;
1561 case Instruction::ICmp:
1562 if (Flags.IsMaxOp) {
1563 MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMax : RD::MRK_UIntMax;
1564 BuildFunc = [&]() {
1565 return Builder.CreateIntMaxReduce(Src, Flags.IsSigned);
1566 };
1567 } else {
1568 MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMin : RD::MRK_UIntMin;
1569 BuildFunc = [&]() {
1570 return Builder.CreateIntMinReduce(Src, Flags.IsSigned);
1571 };
1572 }
1573 break;
1574 case Instruction::FCmp:
1575 if (Flags.IsMaxOp) {
1576 MinMaxKind = RD::MRK_FloatMax;
1577 BuildFunc = [&]() { return Builder.CreateFPMaxReduce(Src, Flags.NoNaN); };
1578 } else {
1579 MinMaxKind = RD::MRK_FloatMin;
1580 BuildFunc = [&]() { return Builder.CreateFPMinReduce(Src, Flags.NoNaN); };
1581 }
1582 break;
1583 default:
1584 llvm_unreachable("Unhandled opcode");
1585 break;
1586 }
1587 if (TTI->useReductionIntrinsic(Opcode, Src->getType(), Flags))
1588 return BuildFunc();
1589 return getShuffleReduction(Builder, Src, Opcode, MinMaxKind, RedOps);
1590}
1591
1592/// Create a vector reduction using a given recurrence descriptor.
Sanjay Patel3e069f52017-12-06 19:37:00 +00001593Value *llvm::createTargetReduction(IRBuilder<> &B,
Amara Emersoncf9daa32017-05-09 10:43:25 +00001594 const TargetTransformInfo *TTI,
1595 RecurrenceDescriptor &Desc, Value *Src,
1596 bool NoNaN) {
1597 // TODO: Support in-order reductions based on the recurrence descriptor.
Sanjay Patel3e069f52017-12-06 19:37:00 +00001598 using RD = RecurrenceDescriptor;
1599 RD::RecurrenceKind RecKind = Desc.getRecurrenceKind();
Amara Emersoncf9daa32017-05-09 10:43:25 +00001600 TargetTransformInfo::ReductionFlags Flags;
1601 Flags.NoNaN = NoNaN;
Amara Emersoncf9daa32017-05-09 10:43:25 +00001602 switch (RecKind) {
Sanjay Patel3e069f52017-12-06 19:37:00 +00001603 case RD::RK_FloatAdd:
1604 return createSimpleTargetReduction(B, TTI, Instruction::FAdd, Src, Flags);
1605 case RD::RK_FloatMult:
1606 return createSimpleTargetReduction(B, TTI, Instruction::FMul, Src, Flags);
1607 case RD::RK_IntegerAdd:
1608 return createSimpleTargetReduction(B, TTI, Instruction::Add, Src, Flags);
1609 case RD::RK_IntegerMult:
1610 return createSimpleTargetReduction(B, TTI, Instruction::Mul, Src, Flags);
1611 case RD::RK_IntegerAnd:
1612 return createSimpleTargetReduction(B, TTI, Instruction::And, Src, Flags);
1613 case RD::RK_IntegerOr:
1614 return createSimpleTargetReduction(B, TTI, Instruction::Or, Src, Flags);
1615 case RD::RK_IntegerXor:
1616 return createSimpleTargetReduction(B, TTI, Instruction::Xor, Src, Flags);
1617 case RD::RK_IntegerMinMax: {
1618 RD::MinMaxRecurrenceKind MMKind = Desc.getMinMaxRecurrenceKind();
1619 Flags.IsMaxOp = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_UIntMax);
1620 Flags.IsSigned = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_SIntMin);
1621 return createSimpleTargetReduction(B, TTI, Instruction::ICmp, Src, Flags);
Amara Emersoncf9daa32017-05-09 10:43:25 +00001622 }
Sanjay Patel3e069f52017-12-06 19:37:00 +00001623 case RD::RK_FloatMinMax: {
1624 Flags.IsMaxOp = Desc.getMinMaxRecurrenceKind() == RD::MRK_FloatMax;
1625 return createSimpleTargetReduction(B, TTI, Instruction::FCmp, Src, Flags);
Amara Emersoncf9daa32017-05-09 10:43:25 +00001626 }
1627 default:
1628 llvm_unreachable("Unhandled RecKind");
1629 }
1630}
1631
Dinar Temirbulatova61f4b82017-07-19 10:02:07 +00001632void llvm::propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue) {
1633 auto *VecOp = dyn_cast<Instruction>(I);
1634 if (!VecOp)
1635 return;
1636 auto *Intersection = (OpValue == nullptr) ? dyn_cast<Instruction>(VL[0])
1637 : dyn_cast<Instruction>(OpValue);
1638 if (!Intersection)
1639 return;
1640 const unsigned Opcode = Intersection->getOpcode();
1641 VecOp->copyIRFlags(Intersection);
1642 for (auto *V : VL) {
1643 auto *Instr = dyn_cast<Instruction>(V);
1644 if (!Instr)
1645 continue;
1646 if (OpValue == nullptr || Opcode == Instr->getOpcode())
1647 VecOp->andIRFlags(V);
Amara Emersoncf9daa32017-05-09 10:43:25 +00001648 }
1649}