Bug Summary

File:lib/Transforms/Scalar/LoopRerollPass.cpp
Warning:line 475, column 18
Called C++ object pointer is null

Annotated Source Code

/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp

1//===- LoopReroll.cpp - Loop rerolling pass -------------------------------===//
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 pass implements a simple loop reroller.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/ADT/APInt.h"
15#include "llvm/ADT/BitVector.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/DenseSet.h"
18#include "llvm/ADT/MapVector.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SmallSet.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/Statistic.h"
23#include "llvm/Analysis/AliasAnalysis.h"
24#include "llvm/Analysis/AliasSetTracker.h"
25#include "llvm/Analysis/LoopInfo.h"
26#include "llvm/Analysis/LoopPass.h"
27#include "llvm/Analysis/ScalarEvolution.h"
28#include "llvm/Analysis/ScalarEvolutionExpander.h"
29#include "llvm/Analysis/ScalarEvolutionExpressions.h"
30#include "llvm/Analysis/TargetLibraryInfo.h"
31#include "llvm/Analysis/ValueTracking.h"
32#include "llvm/IR/BasicBlock.h"
33#include "llvm/IR/Constants.h"
34#include "llvm/IR/DataLayout.h"
35#include "llvm/IR/DerivedTypes.h"
36#include "llvm/IR/Dominators.h"
37#include "llvm/IR/IRBuilder.h"
38#include "llvm/IR/InstrTypes.h"
39#include "llvm/IR/Instruction.h"
40#include "llvm/IR/Instructions.h"
41#include "llvm/IR/IntrinsicInst.h"
42#include "llvm/IR/Intrinsics.h"
43#include "llvm/IR/Module.h"
44#include "llvm/IR/Type.h"
45#include "llvm/IR/Use.h"
46#include "llvm/IR/User.h"
47#include "llvm/IR/Value.h"
48#include "llvm/Pass.h"
49#include "llvm/Support/Casting.h"
50#include "llvm/Support/CommandLine.h"
51#include "llvm/Support/Debug.h"
52#include "llvm/Support/raw_ostream.h"
53#include "llvm/Transforms/Scalar.h"
54#include "llvm/Transforms/Utils/BasicBlockUtils.h"
55#include "llvm/Transforms/Utils/Local.h"
56#include "llvm/Transforms/Utils/LoopUtils.h"
57#include <cassert>
58#include <cstddef>
59#include <cstdint>
60#include <cstdlib>
61#include <iterator>
62#include <map>
63#include <utility>
64
65using namespace llvm;
66
67#define DEBUG_TYPE"loop-reroll" "loop-reroll"
68
69STATISTIC(NumRerolledLoops, "Number of rerolled loops")static llvm::Statistic NumRerolledLoops = {"loop-reroll", "NumRerolledLoops"
, "Number of rerolled loops", {0}, false}
;
70
71static cl::opt<unsigned>
72MaxInc("max-reroll-increment", cl::init(2048), cl::Hidden,
73 cl::desc("The maximum increment for loop rerolling"));
74
75static cl::opt<unsigned>
76NumToleratedFailedMatches("reroll-num-tolerated-failed-matches", cl::init(400),
77 cl::Hidden,
78 cl::desc("The maximum number of failures to tolerate"
79 " during fuzzy matching. (default: 400)"));
80
81// This loop re-rolling transformation aims to transform loops like this:
82//
83// int foo(int a);
84// void bar(int *x) {
85// for (int i = 0; i < 500; i += 3) {
86// foo(i);
87// foo(i+1);
88// foo(i+2);
89// }
90// }
91//
92// into a loop like this:
93//
94// void bar(int *x) {
95// for (int i = 0; i < 500; ++i)
96// foo(i);
97// }
98//
99// It does this by looking for loops that, besides the latch code, are composed
100// of isomorphic DAGs of instructions, with each DAG rooted at some increment
101// to the induction variable, and where each DAG is isomorphic to the DAG
102// rooted at the induction variable (excepting the sub-DAGs which root the
103// other induction-variable increments). In other words, we're looking for loop
104// bodies of the form:
105//
106// %iv = phi [ (preheader, ...), (body, %iv.next) ]
107// f(%iv)
108// %iv.1 = add %iv, 1 <-- a root increment
109// f(%iv.1)
110// %iv.2 = add %iv, 2 <-- a root increment
111// f(%iv.2)
112// %iv.scale_m_1 = add %iv, scale-1 <-- a root increment
113// f(%iv.scale_m_1)
114// ...
115// %iv.next = add %iv, scale
116// %cmp = icmp(%iv, ...)
117// br %cmp, header, exit
118//
119// where each f(i) is a set of instructions that, collectively, are a function
120// only of i (and other loop-invariant values).
121//
122// As a special case, we can also reroll loops like this:
123//
124// int foo(int);
125// void bar(int *x) {
126// for (int i = 0; i < 500; ++i) {
127// x[3*i] = foo(0);
128// x[3*i+1] = foo(0);
129// x[3*i+2] = foo(0);
130// }
131// }
132//
133// into this:
134//
135// void bar(int *x) {
136// for (int i = 0; i < 1500; ++i)
137// x[i] = foo(0);
138// }
139//
140// in which case, we're looking for inputs like this:
141//
142// %iv = phi [ (preheader, ...), (body, %iv.next) ]
143// %scaled.iv = mul %iv, scale
144// f(%scaled.iv)
145// %scaled.iv.1 = add %scaled.iv, 1
146// f(%scaled.iv.1)
147// %scaled.iv.2 = add %scaled.iv, 2
148// f(%scaled.iv.2)
149// %scaled.iv.scale_m_1 = add %scaled.iv, scale-1
150// f(%scaled.iv.scale_m_1)
151// ...
152// %iv.next = add %iv, 1
153// %cmp = icmp(%iv, ...)
154// br %cmp, header, exit
155
156namespace {
157
158 enum IterationLimits {
159 /// The maximum number of iterations that we'll try and reroll.
160 IL_MaxRerollIterations = 32,
161 /// The bitvector index used by loop induction variables and other
162 /// instructions that belong to all iterations.
163 IL_All,
164 IL_End
165 };
166
167 class LoopReroll : public LoopPass {
168 public:
169 static char ID; // Pass ID, replacement for typeid
170
171 LoopReroll() : LoopPass(ID) {
172 initializeLoopRerollPass(*PassRegistry::getPassRegistry());
173 }
174
175 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
176
177 void getAnalysisUsage(AnalysisUsage &AU) const override {
178 AU.addRequired<TargetLibraryInfoWrapperPass>();
179 getLoopAnalysisUsage(AU);
180 }
181
182 protected:
183 AliasAnalysis *AA;
184 LoopInfo *LI;
185 ScalarEvolution *SE;
186 TargetLibraryInfo *TLI;
187 DominatorTree *DT;
188 bool PreserveLCSSA;
189
190 using SmallInstructionVector = SmallVector<Instruction *, 16>;
191 using SmallInstructionSet = SmallSet<Instruction *, 16>;
192
193 // Map between induction variable and its increment
194 DenseMap<Instruction *, int64_t> IVToIncMap;
195
196 // For loop with multiple induction variable, remember the one used only to
197 // control the loop.
198 Instruction *LoopControlIV;
199
200 // A chain of isomorphic instructions, identified by a single-use PHI
201 // representing a reduction. Only the last value may be used outside the
202 // loop.
203 struct SimpleLoopReduction {
204 SimpleLoopReduction(Instruction *P, Loop *L) : Instructions(1, P) {
205 assert(isa<PHINode>(P) && "First reduction instruction must be a PHI")((isa<PHINode>(P) && "First reduction instruction must be a PHI"
) ? static_cast<void> (0) : __assert_fail ("isa<PHINode>(P) && \"First reduction instruction must be a PHI\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 205, __PRETTY_FUNCTION__))
;
206 add(L);
207 }
208
209 bool valid() const {
210 return Valid;
211 }
212
213 Instruction *getPHI() const {
214 assert(Valid && "Using invalid reduction")((Valid && "Using invalid reduction") ? static_cast<
void> (0) : __assert_fail ("Valid && \"Using invalid reduction\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 214, __PRETTY_FUNCTION__))
;
215 return Instructions.front();
216 }
217
218 Instruction *getReducedValue() const {
219 assert(Valid && "Using invalid reduction")((Valid && "Using invalid reduction") ? static_cast<
void> (0) : __assert_fail ("Valid && \"Using invalid reduction\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 219, __PRETTY_FUNCTION__))
;
220 return Instructions.back();
221 }
222
223 Instruction *get(size_t i) const {
224 assert(Valid && "Using invalid reduction")((Valid && "Using invalid reduction") ? static_cast<
void> (0) : __assert_fail ("Valid && \"Using invalid reduction\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 224, __PRETTY_FUNCTION__))
;
225 return Instructions[i+1];
226 }
227
228 Instruction *operator [] (size_t i) const { return get(i); }
229
230 // The size, ignoring the initial PHI.
231 size_t size() const {
232 assert(Valid && "Using invalid reduction")((Valid && "Using invalid reduction") ? static_cast<
void> (0) : __assert_fail ("Valid && \"Using invalid reduction\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 232, __PRETTY_FUNCTION__))
;
233 return Instructions.size()-1;
234 }
235
236 using iterator = SmallInstructionVector::iterator;
237 using const_iterator = SmallInstructionVector::const_iterator;
238
239 iterator begin() {
240 assert(Valid && "Using invalid reduction")((Valid && "Using invalid reduction") ? static_cast<
void> (0) : __assert_fail ("Valid && \"Using invalid reduction\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 240, __PRETTY_FUNCTION__))
;
241 return std::next(Instructions.begin());
242 }
243
244 const_iterator begin() const {
245 assert(Valid && "Using invalid reduction")((Valid && "Using invalid reduction") ? static_cast<
void> (0) : __assert_fail ("Valid && \"Using invalid reduction\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 245, __PRETTY_FUNCTION__))
;
246 return std::next(Instructions.begin());
247 }
248
249 iterator end() { return Instructions.end(); }
250 const_iterator end() const { return Instructions.end(); }
251
252 protected:
253 bool Valid = false;
254 SmallInstructionVector Instructions;
255
256 void add(Loop *L);
257 };
258
259 // The set of all reductions, and state tracking of possible reductions
260 // during loop instruction processing.
261 struct ReductionTracker {
262 using SmallReductionVector = SmallVector<SimpleLoopReduction, 16>;
263
264 // Add a new possible reduction.
265 void addSLR(SimpleLoopReduction &SLR) { PossibleReds.push_back(SLR); }
266
267 // Setup to track possible reductions corresponding to the provided
268 // rerolling scale. Only reductions with a number of non-PHI instructions
269 // that is divisible by the scale are considered. Three instructions sets
270 // are filled in:
271 // - A set of all possible instructions in eligible reductions.
272 // - A set of all PHIs in eligible reductions
273 // - A set of all reduced values (last instructions) in eligible
274 // reductions.
275 void restrictToScale(uint64_t Scale,
276 SmallInstructionSet &PossibleRedSet,
277 SmallInstructionSet &PossibleRedPHISet,
278 SmallInstructionSet &PossibleRedLastSet) {
279 PossibleRedIdx.clear();
280 PossibleRedIter.clear();
281 Reds.clear();
282
283 for (unsigned i = 0, e = PossibleReds.size(); i != e; ++i)
284 if (PossibleReds[i].size() % Scale == 0) {
285 PossibleRedLastSet.insert(PossibleReds[i].getReducedValue());
286 PossibleRedPHISet.insert(PossibleReds[i].getPHI());
287
288 PossibleRedSet.insert(PossibleReds[i].getPHI());
289 PossibleRedIdx[PossibleReds[i].getPHI()] = i;
290 for (Instruction *J : PossibleReds[i]) {
291 PossibleRedSet.insert(J);
292 PossibleRedIdx[J] = i;
293 }
294 }
295 }
296
297 // The functions below are used while processing the loop instructions.
298
299 // Are the two instructions both from reductions, and furthermore, from
300 // the same reduction?
301 bool isPairInSame(Instruction *J1, Instruction *J2) {
302 DenseMap<Instruction *, int>::iterator J1I = PossibleRedIdx.find(J1);
303 if (J1I != PossibleRedIdx.end()) {
304 DenseMap<Instruction *, int>::iterator J2I = PossibleRedIdx.find(J2);
305 if (J2I != PossibleRedIdx.end() && J1I->second == J2I->second)
306 return true;
307 }
308
309 return false;
310 }
311
312 // The two provided instructions, the first from the base iteration, and
313 // the second from iteration i, form a matched pair. If these are part of
314 // a reduction, record that fact.
315 void recordPair(Instruction *J1, Instruction *J2, unsigned i) {
316 if (PossibleRedIdx.count(J1)) {
317 assert(PossibleRedIdx.count(J2) &&((PossibleRedIdx.count(J2) && "Recording reduction vs. non-reduction instruction?"
) ? static_cast<void> (0) : __assert_fail ("PossibleRedIdx.count(J2) && \"Recording reduction vs. non-reduction instruction?\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 318, __PRETTY_FUNCTION__))
318 "Recording reduction vs. non-reduction instruction?")((PossibleRedIdx.count(J2) && "Recording reduction vs. non-reduction instruction?"
) ? static_cast<void> (0) : __assert_fail ("PossibleRedIdx.count(J2) && \"Recording reduction vs. non-reduction instruction?\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 318, __PRETTY_FUNCTION__))
;
319
320 PossibleRedIter[J1] = 0;
321 PossibleRedIter[J2] = i;
322
323 int Idx = PossibleRedIdx[J1];
324 assert(Idx == PossibleRedIdx[J2] &&((Idx == PossibleRedIdx[J2] && "Recording pair from different reductions?"
) ? static_cast<void> (0) : __assert_fail ("Idx == PossibleRedIdx[J2] && \"Recording pair from different reductions?\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 325, __PRETTY_FUNCTION__))
325 "Recording pair from different reductions?")((Idx == PossibleRedIdx[J2] && "Recording pair from different reductions?"
) ? static_cast<void> (0) : __assert_fail ("Idx == PossibleRedIdx[J2] && \"Recording pair from different reductions?\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 325, __PRETTY_FUNCTION__))
;
326 Reds.insert(Idx);
327 }
328 }
329
330 // The functions below can be called after we've finished processing all
331 // instructions in the loop, and we know which reductions were selected.
332
333 bool validateSelected();
334 void replaceSelected();
335
336 protected:
337 // The vector of all possible reductions (for any scale).
338 SmallReductionVector PossibleReds;
339
340 DenseMap<Instruction *, int> PossibleRedIdx;
341 DenseMap<Instruction *, int> PossibleRedIter;
342 DenseSet<int> Reds;
343 };
344
345 // A DAGRootSet models an induction variable being used in a rerollable
346 // loop. For example,
347 //
348 // x[i*3+0] = y1
349 // x[i*3+1] = y2
350 // x[i*3+2] = y3
351 //
352 // Base instruction -> i*3
353 // +---+----+
354 // / | \
355 // ST[y1] +1 +2 <-- Roots
356 // | |
357 // ST[y2] ST[y3]
358 //
359 // There may be multiple DAGRoots, for example:
360 //
361 // x[i*2+0] = ... (1)
362 // x[i*2+1] = ... (1)
363 // x[i*2+4] = ... (2)
364 // x[i*2+5] = ... (2)
365 // x[(i+1234)*2+5678] = ... (3)
366 // x[(i+1234)*2+5679] = ... (3)
367 //
368 // The loop will be rerolled by adding a new loop induction variable,
369 // one for the Base instruction in each DAGRootSet.
370 //
371 struct DAGRootSet {
372 Instruction *BaseInst;
373 SmallInstructionVector Roots;
374
375 // The instructions between IV and BaseInst (but not including BaseInst).
376 SmallInstructionSet SubsumedInsts;
377 };
378
379 // The set of all DAG roots, and state tracking of all roots
380 // for a particular induction variable.
381 struct DAGRootTracker {
382 DAGRootTracker(LoopReroll *Parent, Loop *L, Instruction *IV,
383 ScalarEvolution *SE, AliasAnalysis *AA,
384 TargetLibraryInfo *TLI, DominatorTree *DT, LoopInfo *LI,
385 bool PreserveLCSSA,
386 DenseMap<Instruction *, int64_t> &IncrMap,
387 Instruction *LoopCtrlIV)
388 : Parent(Parent), L(L), SE(SE), AA(AA), TLI(TLI), DT(DT), LI(LI),
389 PreserveLCSSA(PreserveLCSSA), IV(IV), IVToIncMap(IncrMap),
390 LoopControlIV(LoopCtrlIV) {}
391
392 /// Stage 1: Find all the DAG roots for the induction variable.
393 bool findRoots();
394
395 /// Stage 2: Validate if the found roots are valid.
396 bool validate(ReductionTracker &Reductions);
397
398 /// Stage 3: Assuming validate() returned true, perform the
399 /// replacement.
400 /// @param IterCount The maximum iteration count of L.
401 void replace(const SCEV *IterCount);
402
403 protected:
404 using UsesTy = MapVector<Instruction *, BitVector>;
405
406 void findRootsRecursive(Instruction *IVU,
407 SmallInstructionSet SubsumedInsts);
408 bool findRootsBase(Instruction *IVU, SmallInstructionSet SubsumedInsts);
409 bool collectPossibleRoots(Instruction *Base,
410 std::map<int64_t,Instruction*> &Roots);
411 bool validateRootSet(DAGRootSet &DRS);
412
413 bool collectUsedInstructions(SmallInstructionSet &PossibleRedSet);
414 void collectInLoopUserSet(const SmallInstructionVector &Roots,
415 const SmallInstructionSet &Exclude,
416 const SmallInstructionSet &Final,
417 DenseSet<Instruction *> &Users);
418 void collectInLoopUserSet(Instruction *Root,
419 const SmallInstructionSet &Exclude,
420 const SmallInstructionSet &Final,
421 DenseSet<Instruction *> &Users);
422
423 UsesTy::iterator nextInstr(int Val, UsesTy &In,
424 const SmallInstructionSet &Exclude,
425 UsesTy::iterator *StartI=nullptr);
426 bool isBaseInst(Instruction *I);
427 bool isRootInst(Instruction *I);
428 bool instrDependsOn(Instruction *I,
429 UsesTy::iterator Start,
430 UsesTy::iterator End);
431 void replaceIV(Instruction *Inst, Instruction *IV, const SCEV *IterCount);
432 void updateNonLoopCtrlIncr();
433
434 LoopReroll *Parent;
435
436 // Members of Parent, replicated here for brevity.
437 Loop *L;
438 ScalarEvolution *SE;
439 AliasAnalysis *AA;
440 TargetLibraryInfo *TLI;
441 DominatorTree *DT;
442 LoopInfo *LI;
443 bool PreserveLCSSA;
444
445 // The loop induction variable.
446 Instruction *IV;
447
448 // Loop step amount.
449 int64_t Inc;
450
451 // Loop reroll count; if Inc == 1, this records the scaling applied
452 // to the indvar: a[i*2+0] = ...; a[i*2+1] = ... ;
453 // If Inc is not 1, Scale = Inc.
454 uint64_t Scale;
455
456 // The roots themselves.
457 SmallVector<DAGRootSet,16> RootSets;
458
459 // All increment instructions for IV.
460 SmallInstructionVector LoopIncs;
461
462 // Map of all instructions in the loop (in order) to the iterations
463 // they are used in (or specially, IL_All for instructions
464 // used in the loop increment mechanism).
465 UsesTy Uses;
466
467 // Map between induction variable and its increment
468 DenseMap<Instruction *, int64_t> &IVToIncMap;
469
470 Instruction *LoopControlIV;
471 };
472
473 // Check if it is a compare-like instruction whose user is a branch
474 bool isCompareUsedByBranch(Instruction *I) {
475 auto *TI = I->getParent()->getTerminator();
80
Called C++ object pointer is null
476 if (!isa<BranchInst>(TI) || !isa<CmpInst>(I))
477 return false;
478 return I->hasOneUse() && TI->getOperand(0) == I;
479 };
480
481 bool isLoopControlIV(Loop *L, Instruction *IV);
482 void collectPossibleIVs(Loop *L, SmallInstructionVector &PossibleIVs);
483 void collectPossibleReductions(Loop *L,
484 ReductionTracker &Reductions);
485 bool reroll(Instruction *IV, Loop *L, BasicBlock *Header, const SCEV *IterCount,
486 ReductionTracker &Reductions);
487 };
488
489} // end anonymous namespace
490
491char LoopReroll::ID = 0;
492
493INITIALIZE_PASS_BEGIN(LoopReroll, "loop-reroll", "Reroll loops", false, false)static void *initializeLoopRerollPassOnce(PassRegistry &Registry
) {
494INITIALIZE_PASS_DEPENDENCY(LoopPass)initializeLoopPassPass(Registry);
495INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
496INITIALIZE_PASS_END(LoopReroll, "loop-reroll", "Reroll loops", false, false)PassInfo *PI = new PassInfo( "Reroll loops", "loop-reroll", &
LoopReroll::ID, PassInfo::NormalCtor_t(callDefaultCtor<LoopReroll
>), false, false); Registry.registerPass(*PI, true); return
PI; } static llvm::once_flag InitializeLoopRerollPassFlag; void
llvm::initializeLoopRerollPass(PassRegistry &Registry) {
llvm::call_once(InitializeLoopRerollPassFlag, initializeLoopRerollPassOnce
, std::ref(Registry)); }
497
498Pass *llvm::createLoopRerollPass() {
499 return new LoopReroll;
500}
501
502// Returns true if the provided instruction is used outside the given loop.
503// This operates like Instruction::isUsedOutsideOfBlock, but considers PHIs in
504// non-loop blocks to be outside the loop.
505static bool hasUsesOutsideLoop(Instruction *I, Loop *L) {
506 for (User *U : I->users()) {
507 if (!L->contains(cast<Instruction>(U)))
508 return true;
509 }
510 return false;
511}
512
513static const SCEVConstant *getIncrmentFactorSCEV(ScalarEvolution *SE,
514 const SCEV *SCEVExpr,
515 Instruction &IV) {
516 const SCEVMulExpr *MulSCEV = dyn_cast<SCEVMulExpr>(SCEVExpr);
517
518 // If StepRecurrence of a SCEVExpr is a constant (c1 * c2, c2 = sizeof(ptr)),
519 // Return c1.
520 if (!MulSCEV && IV.getType()->isPointerTy())
521 if (const SCEVConstant *IncSCEV = dyn_cast<SCEVConstant>(SCEVExpr)) {
522 const PointerType *PTy = cast<PointerType>(IV.getType());
523 Type *ElTy = PTy->getElementType();
524 const SCEV *SizeOfExpr =
525 SE->getSizeOfExpr(SE->getEffectiveSCEVType(IV.getType()), ElTy);
526 if (IncSCEV->getValue()->getValue().isNegative()) {
527 const SCEV *NewSCEV =
528 SE->getUDivExpr(SE->getNegativeSCEV(SCEVExpr), SizeOfExpr);
529 return dyn_cast<SCEVConstant>(SE->getNegativeSCEV(NewSCEV));
530 } else {
531 return dyn_cast<SCEVConstant>(SE->getUDivExpr(SCEVExpr, SizeOfExpr));
532 }
533 }
534
535 if (!MulSCEV)
536 return nullptr;
537
538 // If StepRecurrence of a SCEVExpr is a c * sizeof(x), where c is constant,
539 // Return c.
540 const SCEVConstant *CIncSCEV = nullptr;
541 for (const SCEV *Operand : MulSCEV->operands()) {
542 if (const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Operand)) {
543 CIncSCEV = Constant;
544 } else if (const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(Operand)) {
545 Type *AllocTy;
546 if (!Unknown->isSizeOf(AllocTy))
547 break;
548 } else {
549 return nullptr;
550 }
551 }
552 return CIncSCEV;
553}
554
555// Check if an IV is only used to control the loop. There are two cases:
556// 1. It only has one use which is loop increment, and the increment is only
557// used by comparison and the PHI (could has sext with nsw in between), and the
558// comparison is only used by branch.
559// 2. It is used by loop increment and the comparison, the loop increment is
560// only used by the PHI, and the comparison is used only by the branch.
561bool LoopReroll::isLoopControlIV(Loop *L, Instruction *IV) {
562 unsigned IVUses = IV->getNumUses();
563 if (IVUses != 2 && IVUses != 1)
1
Assuming 'IVUses' is equal to 2
564 return false;
565
566 for (auto *User : IV->users()) {
567 int32_t IncOrCmpUses = User->getNumUses();
568 bool IsCompInst = isCompareUsedByBranch(cast<Instruction>(User));
569
570 // User can only have one or two uses.
571 if (IncOrCmpUses != 2 && IncOrCmpUses != 1)
2
Assuming 'IncOrCmpUses' is not equal to 2
3
Assuming 'IncOrCmpUses' is equal to 1
4
Taking false branch
11
Assuming 'IncOrCmpUses' is not equal to 2
12
Assuming 'IncOrCmpUses' is equal to 1
13
Taking false branch
20
Assuming 'IncOrCmpUses' is not equal to 2
21
Assuming 'IncOrCmpUses' is equal to 1
22
Taking false branch
572 return false;
573
574 // Case 1
575 if (IVUses == 1) {
5
Taking false branch
14
Taking false branch
23
Taking false branch
576 // The only user must be the loop increment.
577 // The loop increment must have two uses.
578 if (IsCompInst || IncOrCmpUses != 2)
579 return false;
580 }
581
582 // Case 2
583 if (IVUses == 2 && IncOrCmpUses != 1)
6
Taking false branch
15
Taking false branch
24
Taking false branch
584 return false;
585
586 // The users of the IV must be a binary operation or a comparison
587 if (auto *BO = dyn_cast<BinaryOperator>(User)) {
7
Assuming 'BO' is non-null
8
Taking true branch
16
Assuming 'BO' is non-null
17
Taking true branch
25
Assuming 'BO' is non-null
26
Taking true branch
588 if (BO->getOpcode() == Instruction::Add) {
9
Assuming the condition is true
10
Taking true branch
18
Assuming the condition is true
19
Taking true branch
27
Assuming the condition is true
28
Taking true branch
589 // Loop Increment
590 // User of Loop Increment should be either PHI or CMP
591 for (auto *UU : User->users()) {
592 if (PHINode *PN = dyn_cast<PHINode>(UU)) {
29
Taking false branch
593 if (PN != IV)
594 return false;
595 }
596 // Must be a CMP or an ext (of a value with nsw) then CMP
597 else {
598 Instruction *UUser = dyn_cast<Instruction>(UU);
30
Calling 'dyn_cast'
73
Returning from 'dyn_cast'
74
'UUser' initialized here
599 // Skip SExt if we are extending an nsw value
600 // TODO: Allow ZExt too
601 if (BO->hasNoSignedWrap() && UUser && UUser->hasOneUse() &&
75
Assuming the condition is true
76
Assuming pointer value is null
77
Assuming 'UUser' is null
602 isa<SExtInst>(UUser))
603 UUser = dyn_cast<Instruction>(*(UUser->user_begin()));
604 if (!isCompareUsedByBranch(UUser))
78
Passing null pointer value via 1st parameter 'I'
79
Calling 'LoopReroll::isCompareUsedByBranch'
605 return false;
606 }
607 }
608 } else
609 return false;
610 // Compare : can only have one use, and must be branch
611 } else if (!IsCompInst)
612 return false;
613 }
614 return true;
615}
616
617// Collect the list of loop induction variables with respect to which it might
618// be possible to reroll the loop.
619void LoopReroll::collectPossibleIVs(Loop *L,
620 SmallInstructionVector &PossibleIVs) {
621 BasicBlock *Header = L->getHeader();
622 for (BasicBlock::iterator I = Header->begin(),
623 IE = Header->getFirstInsertionPt(); I != IE; ++I) {
624 if (!isa<PHINode>(I))
625 continue;
626 if (!I->getType()->isIntegerTy() && !I->getType()->isPointerTy())
627 continue;
628
629 if (const SCEVAddRecExpr *PHISCEV =
630 dyn_cast<SCEVAddRecExpr>(SE->getSCEV(&*I))) {
631 if (PHISCEV->getLoop() != L)
632 continue;
633 if (!PHISCEV->isAffine())
634 continue;
635 const SCEVConstant *IncSCEV = nullptr;
636 if (I->getType()->isPointerTy())
637 IncSCEV =
638 getIncrmentFactorSCEV(SE, PHISCEV->getStepRecurrence(*SE), *I);
639 else
640 IncSCEV = dyn_cast<SCEVConstant>(PHISCEV->getStepRecurrence(*SE));
641 if (IncSCEV) {
642 const APInt &AInt = IncSCEV->getValue()->getValue().abs();
643 if (IncSCEV->getValue()->isZero() || AInt.uge(MaxInc))
644 continue;
645 IVToIncMap[&*I] = IncSCEV->getValue()->getSExtValue();
646 DEBUG(dbgs() << "LRR: Possible IV: " << *I << " = " << *PHISCEVdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Possible IV: " <<
*I << " = " << *PHISCEV << "\n"; } } while
(false)
647 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Possible IV: " <<
*I << " = " << *PHISCEV << "\n"; } } while
(false)
;
648
649 if (isLoopControlIV(L, &*I)) {
650 assert(!LoopControlIV && "Found two loop control only IV")((!LoopControlIV && "Found two loop control only IV")
? static_cast<void> (0) : __assert_fail ("!LoopControlIV && \"Found two loop control only IV\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 650, __PRETTY_FUNCTION__))
;
651 LoopControlIV = &(*I);
652 DEBUG(dbgs() << "LRR: Possible loop control only IV: " << *I << " = "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Possible loop control only IV: "
<< *I << " = " << *PHISCEV << "\n"; }
} while (false)
653 << *PHISCEV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Possible loop control only IV: "
<< *I << " = " << *PHISCEV << "\n"; }
} while (false)
;
654 } else
655 PossibleIVs.push_back(&*I);
656 }
657 }
658 }
659}
660
661// Add the remainder of the reduction-variable chain to the instruction vector
662// (the initial PHINode has already been added). If successful, the object is
663// marked as valid.
664void LoopReroll::SimpleLoopReduction::add(Loop *L) {
665 assert(!Valid && "Cannot add to an already-valid chain")((!Valid && "Cannot add to an already-valid chain") ?
static_cast<void> (0) : __assert_fail ("!Valid && \"Cannot add to an already-valid chain\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 665, __PRETTY_FUNCTION__))
;
666
667 // The reduction variable must be a chain of single-use instructions
668 // (including the PHI), except for the last value (which is used by the PHI
669 // and also outside the loop).
670 Instruction *C = Instructions.front();
671 if (C->user_empty())
672 return;
673
674 do {
675 C = cast<Instruction>(*C->user_begin());
676 if (C->hasOneUse()) {
677 if (!C->isBinaryOp())
678 return;
679
680 if (!(isa<PHINode>(Instructions.back()) ||
681 C->isSameOperationAs(Instructions.back())))
682 return;
683
684 Instructions.push_back(C);
685 }
686 } while (C->hasOneUse());
687
688 if (Instructions.size() < 2 ||
689 !C->isSameOperationAs(Instructions.back()) ||
690 C->use_empty())
691 return;
692
693 // C is now the (potential) last instruction in the reduction chain.
694 for (User *U : C->users()) {
695 // The only in-loop user can be the initial PHI.
696 if (L->contains(cast<Instruction>(U)))
697 if (cast<Instruction>(U) != Instructions.front())
698 return;
699 }
700
701 Instructions.push_back(C);
702 Valid = true;
703}
704
705// Collect the vector of possible reduction variables.
706void LoopReroll::collectPossibleReductions(Loop *L,
707 ReductionTracker &Reductions) {
708 BasicBlock *Header = L->getHeader();
709 for (BasicBlock::iterator I = Header->begin(),
710 IE = Header->getFirstInsertionPt(); I != IE; ++I) {
711 if (!isa<PHINode>(I))
712 continue;
713 if (!I->getType()->isSingleValueType())
714 continue;
715
716 SimpleLoopReduction SLR(&*I, L);
717 if (!SLR.valid())
718 continue;
719
720 DEBUG(dbgs() << "LRR: Possible reduction: " << *I << " (with " <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Possible reduction: "
<< *I << " (with " << SLR.size() << " chained instructions)\n"
; } } while (false)
721 SLR.size() << " chained instructions)\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Possible reduction: "
<< *I << " (with " << SLR.size() << " chained instructions)\n"
; } } while (false)
;
722 Reductions.addSLR(SLR);
723 }
724}
725
726// Collect the set of all users of the provided root instruction. This set of
727// users contains not only the direct users of the root instruction, but also
728// all users of those users, and so on. There are two exceptions:
729//
730// 1. Instructions in the set of excluded instructions are never added to the
731// use set (even if they are users). This is used, for example, to exclude
732// including root increments in the use set of the primary IV.
733//
734// 2. Instructions in the set of final instructions are added to the use set
735// if they are users, but their users are not added. This is used, for
736// example, to prevent a reduction update from forcing all later reduction
737// updates into the use set.
738void LoopReroll::DAGRootTracker::collectInLoopUserSet(
739 Instruction *Root, const SmallInstructionSet &Exclude,
740 const SmallInstructionSet &Final,
741 DenseSet<Instruction *> &Users) {
742 SmallInstructionVector Queue(1, Root);
743 while (!Queue.empty()) {
744 Instruction *I = Queue.pop_back_val();
745 if (!Users.insert(I).second)
746 continue;
747
748 if (!Final.count(I))
749 for (Use &U : I->uses()) {
750 Instruction *User = cast<Instruction>(U.getUser());
751 if (PHINode *PN = dyn_cast<PHINode>(User)) {
752 // Ignore "wrap-around" uses to PHIs of this loop's header.
753 if (PN->getIncomingBlock(U) == L->getHeader())
754 continue;
755 }
756
757 if (L->contains(User) && !Exclude.count(User)) {
758 Queue.push_back(User);
759 }
760 }
761
762 // We also want to collect single-user "feeder" values.
763 for (User::op_iterator OI = I->op_begin(),
764 OIE = I->op_end(); OI != OIE; ++OI) {
765 if (Instruction *Op = dyn_cast<Instruction>(*OI))
766 if (Op->hasOneUse() && L->contains(Op) && !Exclude.count(Op) &&
767 !Final.count(Op))
768 Queue.push_back(Op);
769 }
770 }
771}
772
773// Collect all of the users of all of the provided root instructions (combined
774// into a single set).
775void LoopReroll::DAGRootTracker::collectInLoopUserSet(
776 const SmallInstructionVector &Roots,
777 const SmallInstructionSet &Exclude,
778 const SmallInstructionSet &Final,
779 DenseSet<Instruction *> &Users) {
780 for (Instruction *Root : Roots)
781 collectInLoopUserSet(Root, Exclude, Final, Users);
782}
783
784static bool isUnorderedLoadStore(Instruction *I) {
785 if (LoadInst *LI = dyn_cast<LoadInst>(I))
786 return LI->isUnordered();
787 if (StoreInst *SI = dyn_cast<StoreInst>(I))
788 return SI->isUnordered();
789 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I))
790 return !MI->isVolatile();
791 return false;
792}
793
794/// Return true if IVU is a "simple" arithmetic operation.
795/// This is used for narrowing the search space for DAGRoots; only arithmetic
796/// and GEPs can be part of a DAGRoot.
797static bool isSimpleArithmeticOp(User *IVU) {
798 if (Instruction *I = dyn_cast<Instruction>(IVU)) {
799 switch (I->getOpcode()) {
800 default: return false;
801 case Instruction::Add:
802 case Instruction::Sub:
803 case Instruction::Mul:
804 case Instruction::Shl:
805 case Instruction::AShr:
806 case Instruction::LShr:
807 case Instruction::GetElementPtr:
808 case Instruction::Trunc:
809 case Instruction::ZExt:
810 case Instruction::SExt:
811 return true;
812 }
813 }
814 return false;
815}
816
817static bool isLoopIncrement(User *U, Instruction *IV) {
818 BinaryOperator *BO = dyn_cast<BinaryOperator>(U);
819
820 if ((BO && BO->getOpcode() != Instruction::Add) ||
821 (!BO && !isa<GetElementPtrInst>(U)))
822 return false;
823
824 for (auto *UU : U->users()) {
825 PHINode *PN = dyn_cast<PHINode>(UU);
826 if (PN && PN == IV)
827 return true;
828 }
829 return false;
830}
831
832bool LoopReroll::DAGRootTracker::
833collectPossibleRoots(Instruction *Base, std::map<int64_t,Instruction*> &Roots) {
834 SmallInstructionVector BaseUsers;
835
836 for (auto *I : Base->users()) {
837 ConstantInt *CI = nullptr;
838
839 if (isLoopIncrement(I, IV)) {
840 LoopIncs.push_back(cast<Instruction>(I));
841 continue;
842 }
843
844 // The root nodes must be either GEPs, ORs or ADDs.
845 if (auto *BO = dyn_cast<BinaryOperator>(I)) {
846 if (BO->getOpcode() == Instruction::Add ||
847 BO->getOpcode() == Instruction::Or)
848 CI = dyn_cast<ConstantInt>(BO->getOperand(1));
849 } else if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
850 Value *LastOperand = GEP->getOperand(GEP->getNumOperands()-1);
851 CI = dyn_cast<ConstantInt>(LastOperand);
852 }
853
854 if (!CI) {
855 if (Instruction *II = dyn_cast<Instruction>(I)) {
856 BaseUsers.push_back(II);
857 continue;
858 } else {
859 DEBUG(dbgs() << "LRR: Aborting due to non-instruction: " << *I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Aborting due to non-instruction: "
<< *I << "\n"; } } while (false)
;
860 return false;
861 }
862 }
863
864 int64_t V = std::abs(CI->getValue().getSExtValue());
865 if (Roots.find(V) != Roots.end())
866 // No duplicates, please.
867 return false;
868
869 Roots[V] = cast<Instruction>(I);
870 }
871
872 // Make sure we have at least two roots.
873 if (Roots.empty() || (Roots.size() == 1 && BaseUsers.empty()))
874 return false;
875
876 // If we found non-loop-inc, non-root users of Base, assume they are
877 // for the zeroth root index. This is because "add %a, 0" gets optimized
878 // away.
879 if (BaseUsers.size()) {
880 if (Roots.find(0) != Roots.end()) {
881 DEBUG(dbgs() << "LRR: Multiple roots found for base - aborting!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Multiple roots found for base - aborting!\n"
; } } while (false)
;
882 return false;
883 }
884 Roots[0] = Base;
885 }
886
887 // Calculate the number of users of the base, or lowest indexed, iteration.
888 unsigned NumBaseUses = BaseUsers.size();
889 if (NumBaseUses == 0)
890 NumBaseUses = Roots.begin()->second->getNumUses();
891
892 // Check that every node has the same number of users.
893 for (auto &KV : Roots) {
894 if (KV.first == 0)
895 continue;
896 if (!KV.second->hasNUses(NumBaseUses)) {
897 DEBUG(dbgs() << "LRR: Aborting - Root and Base #users not the same: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Aborting - Root and Base #users not the same: "
<< "#Base=" << NumBaseUses << ", #Root=" <<
KV.second->getNumUses() << "\n"; } } while (false)
898 << "#Base=" << NumBaseUses << ", #Root=" <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Aborting - Root and Base #users not the same: "
<< "#Base=" << NumBaseUses << ", #Root=" <<
KV.second->getNumUses() << "\n"; } } while (false)
899 KV.second->getNumUses() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Aborting - Root and Base #users not the same: "
<< "#Base=" << NumBaseUses << ", #Root=" <<
KV.second->getNumUses() << "\n"; } } while (false)
;
900 return false;
901 }
902 }
903
904 return true;
905}
906
907void LoopReroll::DAGRootTracker::
908findRootsRecursive(Instruction *I, SmallInstructionSet SubsumedInsts) {
909 // Does the user look like it could be part of a root set?
910 // All its users must be simple arithmetic ops.
911 if (I->hasNUsesOrMore(IL_MaxRerollIterations + 1))
912 return;
913
914 if (I != IV && findRootsBase(I, SubsumedInsts))
915 return;
916
917 SubsumedInsts.insert(I);
918
919 for (User *V : I->users()) {
920 Instruction *I = cast<Instruction>(V);
921 if (is_contained(LoopIncs, I))
922 continue;
923
924 if (!isSimpleArithmeticOp(I))
925 continue;
926
927 // The recursive call makes a copy of SubsumedInsts.
928 findRootsRecursive(I, SubsumedInsts);
929 }
930}
931
932bool LoopReroll::DAGRootTracker::validateRootSet(DAGRootSet &DRS) {
933 if (DRS.Roots.empty())
934 return false;
935
936 // Consider a DAGRootSet with N-1 roots (so N different values including
937 // BaseInst).
938 // Define d = Roots[0] - BaseInst, which should be the same as
939 // Roots[I] - Roots[I-1] for all I in [1..N).
940 // Define D = BaseInst@J - BaseInst@J-1, where "@J" means the value at the
941 // loop iteration J.
942 //
943 // Now, For the loop iterations to be consecutive:
944 // D = d * N
945 const auto *ADR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(DRS.BaseInst));
946 if (!ADR)
947 return false;
948 unsigned N = DRS.Roots.size() + 1;
949 const SCEV *StepSCEV = SE->getMinusSCEV(SE->getSCEV(DRS.Roots[0]), ADR);
950 const SCEV *ScaleSCEV = SE->getConstant(StepSCEV->getType(), N);
951 if (ADR->getStepRecurrence(*SE) != SE->getMulExpr(StepSCEV, ScaleSCEV))
952 return false;
953
954 return true;
955}
956
957bool LoopReroll::DAGRootTracker::
958findRootsBase(Instruction *IVU, SmallInstructionSet SubsumedInsts) {
959 // The base of a RootSet must be an AddRec, so it can be erased.
960 const auto *IVU_ADR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(IVU));
961 if (!IVU_ADR || IVU_ADR->getLoop() != L)
962 return false;
963
964 std::map<int64_t, Instruction*> V;
965 if (!collectPossibleRoots(IVU, V))
966 return false;
967
968 // If we didn't get a root for index zero, then IVU must be
969 // subsumed.
970 if (V.find(0) == V.end())
971 SubsumedInsts.insert(IVU);
972
973 // Partition the vector into monotonically increasing indexes.
974 DAGRootSet DRS;
975 DRS.BaseInst = nullptr;
976
977 SmallVector<DAGRootSet, 16> PotentialRootSets;
978
979 for (auto &KV : V) {
980 if (!DRS.BaseInst) {
981 DRS.BaseInst = KV.second;
982 DRS.SubsumedInsts = SubsumedInsts;
983 } else if (DRS.Roots.empty()) {
984 DRS.Roots.push_back(KV.second);
985 } else if (V.find(KV.first - 1) != V.end()) {
986 DRS.Roots.push_back(KV.second);
987 } else {
988 // Linear sequence terminated.
989 if (!validateRootSet(DRS))
990 return false;
991
992 // Construct a new DAGRootSet with the next sequence.
993 PotentialRootSets.push_back(DRS);
994 DRS.BaseInst = KV.second;
995 DRS.Roots.clear();
996 }
997 }
998
999 if (!validateRootSet(DRS))
1000 return false;
1001
1002 PotentialRootSets.push_back(DRS);
1003
1004 RootSets.append(PotentialRootSets.begin(), PotentialRootSets.end());
1005
1006 return true;
1007}
1008
1009bool LoopReroll::DAGRootTracker::findRoots() {
1010 Inc = IVToIncMap[IV];
1011
1012 assert(RootSets.empty() && "Unclean state!")((RootSets.empty() && "Unclean state!") ? static_cast
<void> (0) : __assert_fail ("RootSets.empty() && \"Unclean state!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 1012, __PRETTY_FUNCTION__))
;
1013 if (std::abs(Inc) == 1) {
1014 for (auto *IVU : IV->users()) {
1015 if (isLoopIncrement(IVU, IV))
1016 LoopIncs.push_back(cast<Instruction>(IVU));
1017 }
1018 findRootsRecursive(IV, SmallInstructionSet());
1019 LoopIncs.push_back(IV);
1020 } else {
1021 if (!findRootsBase(IV, SmallInstructionSet()))
1022 return false;
1023 }
1024
1025 // Ensure all sets have the same size.
1026 if (RootSets.empty()) {
1027 DEBUG(dbgs() << "LRR: Aborting because no root sets found!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Aborting because no root sets found!\n"
; } } while (false)
;
1028 return false;
1029 }
1030 for (auto &V : RootSets) {
1031 if (V.Roots.empty() || V.Roots.size() != RootSets[0].Roots.size()) {
1032 DEBUG(dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Aborting because not all root sets have the same size\n"
; } } while (false)
1033 << "LRR: Aborting because not all root sets have the same size\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Aborting because not all root sets have the same size\n"
; } } while (false)
;
1034 return false;
1035 }
1036 }
1037
1038 Scale = RootSets[0].Roots.size() + 1;
1039
1040 if (Scale > IL_MaxRerollIterations) {
1041 DEBUG(dbgs() << "LRR: Aborting - too many iterations found. "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Aborting - too many iterations found. "
<< "#Found=" << Scale << ", #Max=" <<
IL_MaxRerollIterations << "\n"; } } while (false)
1042 << "#Found=" << Scale << ", #Max=" << IL_MaxRerollIterationsdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Aborting - too many iterations found. "
<< "#Found=" << Scale << ", #Max=" <<
IL_MaxRerollIterations << "\n"; } } while (false)
1043 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Aborting - too many iterations found. "
<< "#Found=" << Scale << ", #Max=" <<
IL_MaxRerollIterations << "\n"; } } while (false)
;
1044 return false;
1045 }
1046
1047 DEBUG(dbgs() << "LRR: Successfully found roots: Scale=" << Scale << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Successfully found roots: Scale="
<< Scale << "\n"; } } while (false)
;
1048
1049 return true;
1050}
1051
1052bool LoopReroll::DAGRootTracker::collectUsedInstructions(SmallInstructionSet &PossibleRedSet) {
1053 // Populate the MapVector with all instructions in the block, in order first,
1054 // so we can iterate over the contents later in perfect order.
1055 for (auto &I : *L->getHeader()) {
1056 Uses[&I].resize(IL_End);
1057 }
1058
1059 SmallInstructionSet Exclude;
1060 for (auto &DRS : RootSets) {
1061 Exclude.insert(DRS.Roots.begin(), DRS.Roots.end());
1062 Exclude.insert(DRS.SubsumedInsts.begin(), DRS.SubsumedInsts.end());
1063 Exclude.insert(DRS.BaseInst);
1064 }
1065 Exclude.insert(LoopIncs.begin(), LoopIncs.end());
1066
1067 for (auto &DRS : RootSets) {
1068 DenseSet<Instruction*> VBase;
1069 collectInLoopUserSet(DRS.BaseInst, Exclude, PossibleRedSet, VBase);
1070 for (auto *I : VBase) {
1071 Uses[I].set(0);
1072 }
1073
1074 unsigned Idx = 1;
1075 for (auto *Root : DRS.Roots) {
1076 DenseSet<Instruction*> V;
1077 collectInLoopUserSet(Root, Exclude, PossibleRedSet, V);
1078
1079 // While we're here, check the use sets are the same size.
1080 if (V.size() != VBase.size()) {
1081 DEBUG(dbgs() << "LRR: Aborting - use sets are different sizes\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Aborting - use sets are different sizes\n"
; } } while (false)
;
1082 return false;
1083 }
1084
1085 for (auto *I : V) {
1086 Uses[I].set(Idx);
1087 }
1088 ++Idx;
1089 }
1090
1091 // Make sure our subsumed instructions are remembered too.
1092 for (auto *I : DRS.SubsumedInsts) {
1093 Uses[I].set(IL_All);
1094 }
1095 }
1096
1097 // Make sure the loop increments are also accounted for.
1098
1099 Exclude.clear();
1100 for (auto &DRS : RootSets) {
1101 Exclude.insert(DRS.Roots.begin(), DRS.Roots.end());
1102 Exclude.insert(DRS.SubsumedInsts.begin(), DRS.SubsumedInsts.end());
1103 Exclude.insert(DRS.BaseInst);
1104 }
1105
1106 DenseSet<Instruction*> V;
1107 collectInLoopUserSet(LoopIncs, Exclude, PossibleRedSet, V);
1108 for (auto *I : V) {
1109 Uses[I].set(IL_All);
1110 }
1111
1112 return true;
1113}
1114
1115/// Get the next instruction in "In" that is a member of set Val.
1116/// Start searching from StartI, and do not return anything in Exclude.
1117/// If StartI is not given, start from In.begin().
1118LoopReroll::DAGRootTracker::UsesTy::iterator
1119LoopReroll::DAGRootTracker::nextInstr(int Val, UsesTy &In,
1120 const SmallInstructionSet &Exclude,
1121 UsesTy::iterator *StartI) {
1122 UsesTy::iterator I = StartI ? *StartI : In.begin();
1123 while (I != In.end() && (I->second.test(Val) == 0 ||
1124 Exclude.count(I->first) != 0))
1125 ++I;
1126 return I;
1127}
1128
1129bool LoopReroll::DAGRootTracker::isBaseInst(Instruction *I) {
1130 for (auto &DRS : RootSets) {
1131 if (DRS.BaseInst == I)
1132 return true;
1133 }
1134 return false;
1135}
1136
1137bool LoopReroll::DAGRootTracker::isRootInst(Instruction *I) {
1138 for (auto &DRS : RootSets) {
1139 if (is_contained(DRS.Roots, I))
1140 return true;
1141 }
1142 return false;
1143}
1144
1145/// Return true if instruction I depends on any instruction between
1146/// Start and End.
1147bool LoopReroll::DAGRootTracker::instrDependsOn(Instruction *I,
1148 UsesTy::iterator Start,
1149 UsesTy::iterator End) {
1150 for (auto *U : I->users()) {
1151 for (auto It = Start; It != End; ++It)
1152 if (U == It->first)
1153 return true;
1154 }
1155 return false;
1156}
1157
1158static bool isIgnorableInst(const Instruction *I) {
1159 if (isa<DbgInfoIntrinsic>(I))
1160 return true;
1161 const IntrinsicInst* II = dyn_cast<IntrinsicInst>(I);
1162 if (!II)
1163 return false;
1164 switch (II->getIntrinsicID()) {
1165 default:
1166 return false;
1167 case Intrinsic::annotation:
1168 case Intrinsic::ptr_annotation:
1169 case Intrinsic::var_annotation:
1170 // TODO: the following intrinsics may also be whitelisted:
1171 // lifetime_start, lifetime_end, invariant_start, invariant_end
1172 return true;
1173 }
1174 return false;
1175}
1176
1177bool LoopReroll::DAGRootTracker::validate(ReductionTracker &Reductions) {
1178 // We now need to check for equivalence of the use graph of each root with
1179 // that of the primary induction variable (excluding the roots). Our goal
1180 // here is not to solve the full graph isomorphism problem, but rather to
1181 // catch common cases without a lot of work. As a result, we will assume
1182 // that the relative order of the instructions in each unrolled iteration
1183 // is the same (although we will not make an assumption about how the
1184 // different iterations are intermixed). Note that while the order must be
1185 // the same, the instructions may not be in the same basic block.
1186
1187 // An array of just the possible reductions for this scale factor. When we
1188 // collect the set of all users of some root instructions, these reduction
1189 // instructions are treated as 'final' (their uses are not considered).
1190 // This is important because we don't want the root use set to search down
1191 // the reduction chain.
1192 SmallInstructionSet PossibleRedSet;
1193 SmallInstructionSet PossibleRedLastSet;
1194 SmallInstructionSet PossibleRedPHISet;
1195 Reductions.restrictToScale(Scale, PossibleRedSet,
1196 PossibleRedPHISet, PossibleRedLastSet);
1197
1198 // Populate "Uses" with where each instruction is used.
1199 if (!collectUsedInstructions(PossibleRedSet))
1200 return false;
1201
1202 // Make sure we mark the reduction PHIs as used in all iterations.
1203 for (auto *I : PossibleRedPHISet) {
1204 Uses[I].set(IL_All);
1205 }
1206
1207 // Make sure we mark loop-control-only PHIs as used in all iterations. See
1208 // comment above LoopReroll::isLoopControlIV for more information.
1209 BasicBlock *Header = L->getHeader();
1210 if (LoopControlIV && LoopControlIV != IV) {
1211 for (auto *U : LoopControlIV->users()) {
1212 Instruction *IVUser = dyn_cast<Instruction>(U);
1213 // IVUser could be loop increment or compare
1214 Uses[IVUser].set(IL_All);
1215 for (auto *UU : IVUser->users()) {
1216 Instruction *UUser = dyn_cast<Instruction>(UU);
1217 // UUser could be compare, PHI or branch
1218 Uses[UUser].set(IL_All);
1219 // Skip SExt
1220 if (isa<SExtInst>(UUser)) {
1221 UUser = dyn_cast<Instruction>(*(UUser->user_begin()));
1222 Uses[UUser].set(IL_All);
1223 }
1224 // Is UUser a compare instruction?
1225 if (UU->hasOneUse()) {
1226 Instruction *BI = dyn_cast<BranchInst>(*UUser->user_begin());
1227 if (BI == cast<BranchInst>(Header->getTerminator()))
1228 Uses[BI].set(IL_All);
1229 }
1230 }
1231 }
1232 }
1233
1234 // Make sure all instructions in the loop are in one and only one
1235 // set.
1236 for (auto &KV : Uses) {
1237 if (KV.second.count() != 1 && !isIgnorableInst(KV.first)) {
1238 DEBUG(dbgs() << "LRR: Aborting - instruction is not used in 1 iteration: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Aborting - instruction is not used in 1 iteration: "
<< *KV.first << " (#uses=" << KV.second.count
() << ")\n"; } } while (false)
1239 << *KV.first << " (#uses=" << KV.second.count() << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Aborting - instruction is not used in 1 iteration: "
<< *KV.first << " (#uses=" << KV.second.count
() << ")\n"; } } while (false)
;
1240 return false;
1241 }
1242 }
1243
1244 DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { for (auto &KV : Uses) { dbgs() <<
"LRR: " << KV.second.find_first() << "\t" <<
*KV.first << "\n"; }; } } while (false)
1245 for (auto &KV : Uses) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { for (auto &KV : Uses) { dbgs() <<
"LRR: " << KV.second.find_first() << "\t" <<
*KV.first << "\n"; }; } } while (false)
1246 dbgs() << "LRR: " << KV.second.find_first() << "\t" << *KV.first << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { for (auto &KV : Uses) { dbgs() <<
"LRR: " << KV.second.find_first() << "\t" <<
*KV.first << "\n"; }; } } while (false)
1247 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { for (auto &KV : Uses) { dbgs() <<
"LRR: " << KV.second.find_first() << "\t" <<
*KV.first << "\n"; }; } } while (false)
1248 )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { for (auto &KV : Uses) { dbgs() <<
"LRR: " << KV.second.find_first() << "\t" <<
*KV.first << "\n"; }; } } while (false)
;
1249
1250 for (unsigned Iter = 1; Iter < Scale; ++Iter) {
1251 // In addition to regular aliasing information, we need to look for
1252 // instructions from later (future) iterations that have side effects
1253 // preventing us from reordering them past other instructions with side
1254 // effects.
1255 bool FutureSideEffects = false;
1256 AliasSetTracker AST(*AA);
1257 // The map between instructions in f(%iv.(i+1)) and f(%iv).
1258 DenseMap<Value *, Value *> BaseMap;
1259
1260 // Compare iteration Iter to the base.
1261 SmallInstructionSet Visited;
1262 auto BaseIt = nextInstr(0, Uses, Visited);
1263 auto RootIt = nextInstr(Iter, Uses, Visited);
1264 auto LastRootIt = Uses.begin();
1265
1266 while (BaseIt != Uses.end() && RootIt != Uses.end()) {
1267 Instruction *BaseInst = BaseIt->first;
1268 Instruction *RootInst = RootIt->first;
1269
1270 // Skip over the IV or root instructions; only match their users.
1271 bool Continue = false;
1272 if (isBaseInst(BaseInst)) {
1273 Visited.insert(BaseInst);
1274 BaseIt = nextInstr(0, Uses, Visited);
1275 Continue = true;
1276 }
1277 if (isRootInst(RootInst)) {
1278 LastRootIt = RootIt;
1279 Visited.insert(RootInst);
1280 RootIt = nextInstr(Iter, Uses, Visited);
1281 Continue = true;
1282 }
1283 if (Continue) continue;
1284
1285 if (!BaseInst->isSameOperationAs(RootInst)) {
1286 // Last chance saloon. We don't try and solve the full isomorphism
1287 // problem, but try and at least catch the case where two instructions
1288 // *of different types* are round the wrong way. We won't be able to
1289 // efficiently tell, given two ADD instructions, which way around we
1290 // should match them, but given an ADD and a SUB, we can at least infer
1291 // which one is which.
1292 //
1293 // This should allow us to deal with a greater subset of the isomorphism
1294 // problem. It does however change a linear algorithm into a quadratic
1295 // one, so limit the number of probes we do.
1296 auto TryIt = RootIt;
1297 unsigned N = NumToleratedFailedMatches;
1298 while (TryIt != Uses.end() &&
1299 !BaseInst->isSameOperationAs(TryIt->first) &&
1300 N--) {
1301 ++TryIt;
1302 TryIt = nextInstr(Iter, Uses, Visited, &TryIt);
1303 }
1304
1305 if (TryIt == Uses.end() || TryIt == RootIt ||
1306 instrDependsOn(TryIt->first, RootIt, TryIt)) {
1307 DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: iteration root match failed at "
<< *BaseInst << " vs. " << *RootInst <<
"\n"; } } while (false)
1308 " vs. " << *RootInst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: iteration root match failed at "
<< *BaseInst << " vs. " << *RootInst <<
"\n"; } } while (false)
;
1309 return false;
1310 }
1311
1312 RootIt = TryIt;
1313 RootInst = TryIt->first;
1314 }
1315
1316 // All instructions between the last root and this root
1317 // may belong to some other iteration. If they belong to a
1318 // future iteration, then they're dangerous to alias with.
1319 //
1320 // Note that because we allow a limited amount of flexibility in the order
1321 // that we visit nodes, LastRootIt might be *before* RootIt, in which
1322 // case we've already checked this set of instructions so we shouldn't
1323 // do anything.
1324 for (; LastRootIt < RootIt; ++LastRootIt) {
1325 Instruction *I = LastRootIt->first;
1326 if (LastRootIt->second.find_first() < (int)Iter)
1327 continue;
1328 if (I->mayWriteToMemory())
1329 AST.add(I);
1330 // Note: This is specifically guarded by a check on isa<PHINode>,
1331 // which while a valid (somewhat arbitrary) micro-optimization, is
1332 // needed because otherwise isSafeToSpeculativelyExecute returns
1333 // false on PHI nodes.
1334 if (!isa<PHINode>(I) && !isUnorderedLoadStore(I) &&
1335 !isSafeToSpeculativelyExecute(I))
1336 // Intervening instructions cause side effects.
1337 FutureSideEffects = true;
1338 }
1339
1340 // Make sure that this instruction, which is in the use set of this
1341 // root instruction, does not also belong to the base set or the set of
1342 // some other root instruction.
1343 if (RootIt->second.count() > 1) {
1344 DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: iteration root match failed at "
<< *BaseInst << " vs. " << *RootInst <<
" (prev. case overlap)\n"; } } while (false)
1345 " vs. " << *RootInst << " (prev. case overlap)\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: iteration root match failed at "
<< *BaseInst << " vs. " << *RootInst <<
" (prev. case overlap)\n"; } } while (false)
;
1346 return false;
1347 }
1348
1349 // Make sure that we don't alias with any instruction in the alias set
1350 // tracker. If we do, then we depend on a future iteration, and we
1351 // can't reroll.
1352 if (RootInst->mayReadFromMemory())
1353 for (auto &K : AST) {
1354 if (K.aliasesUnknownInst(RootInst, *AA)) {
1355 DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: iteration root match failed at "
<< *BaseInst << " vs. " << *RootInst <<
" (depends on future store)\n"; } } while (false)
1356 " vs. " << *RootInst << " (depends on future store)\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: iteration root match failed at "
<< *BaseInst << " vs. " << *RootInst <<
" (depends on future store)\n"; } } while (false)
;
1357 return false;
1358 }
1359 }
1360
1361 // If we've past an instruction from a future iteration that may have
1362 // side effects, and this instruction might also, then we can't reorder
1363 // them, and this matching fails. As an exception, we allow the alias
1364 // set tracker to handle regular (unordered) load/store dependencies.
1365 if (FutureSideEffects && ((!isUnorderedLoadStore(BaseInst) &&
1366 !isSafeToSpeculativelyExecute(BaseInst)) ||
1367 (!isUnorderedLoadStore(RootInst) &&
1368 !isSafeToSpeculativelyExecute(RootInst)))) {
1369 DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: iteration root match failed at "
<< *BaseInst << " vs. " << *RootInst <<
" (side effects prevent reordering)\n"; } } while (false)
1370 " vs. " << *RootInst <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: iteration root match failed at "
<< *BaseInst << " vs. " << *RootInst <<
" (side effects prevent reordering)\n"; } } while (false)
1371 " (side effects prevent reordering)\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: iteration root match failed at "
<< *BaseInst << " vs. " << *RootInst <<
" (side effects prevent reordering)\n"; } } while (false)
;
1372 return false;
1373 }
1374
1375 // For instructions that are part of a reduction, if the operation is
1376 // associative, then don't bother matching the operands (because we
1377 // already know that the instructions are isomorphic, and the order
1378 // within the iteration does not matter). For non-associative reductions,
1379 // we do need to match the operands, because we need to reject
1380 // out-of-order instructions within an iteration!
1381 // For example (assume floating-point addition), we need to reject this:
1382 // x += a[i]; x += b[i];
1383 // x += a[i+1]; x += b[i+1];
1384 // x += b[i+2]; x += a[i+2];
1385 bool InReduction = Reductions.isPairInSame(BaseInst, RootInst);
1386
1387 if (!(InReduction && BaseInst->isAssociative())) {
1388 bool Swapped = false, SomeOpMatched = false;
1389 for (unsigned j = 0; j < BaseInst->getNumOperands(); ++j) {
1390 Value *Op2 = RootInst->getOperand(j);
1391
1392 // If this is part of a reduction (and the operation is not
1393 // associatve), then we match all operands, but not those that are
1394 // part of the reduction.
1395 if (InReduction)
1396 if (Instruction *Op2I = dyn_cast<Instruction>(Op2))
1397 if (Reductions.isPairInSame(RootInst, Op2I))
1398 continue;
1399
1400 DenseMap<Value *, Value *>::iterator BMI = BaseMap.find(Op2);
1401 if (BMI != BaseMap.end()) {
1402 Op2 = BMI->second;
1403 } else {
1404 for (auto &DRS : RootSets) {
1405 if (DRS.Roots[Iter-1] == (Instruction*) Op2) {
1406 Op2 = DRS.BaseInst;
1407 break;
1408 }
1409 }
1410 }
1411
1412 if (BaseInst->getOperand(Swapped ? unsigned(!j) : j) != Op2) {
1413 // If we've not already decided to swap the matched operands, and
1414 // we've not already matched our first operand (note that we could
1415 // have skipped matching the first operand because it is part of a
1416 // reduction above), and the instruction is commutative, then try
1417 // the swapped match.
1418 if (!Swapped && BaseInst->isCommutative() && !SomeOpMatched &&
1419 BaseInst->getOperand(!j) == Op2) {
1420 Swapped = true;
1421 } else {
1422 DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInstdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: iteration root match failed at "
<< *BaseInst << " vs. " << *RootInst <<
" (operand " << j << ")\n"; } } while (false)
1423 << " vs. " << *RootInst << " (operand " << j << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: iteration root match failed at "
<< *BaseInst << " vs. " << *RootInst <<
" (operand " << j << ")\n"; } } while (false)
;
1424 return false;
1425 }
1426 }
1427
1428 SomeOpMatched = true;
1429 }
1430 }
1431
1432 if ((!PossibleRedLastSet.count(BaseInst) &&
1433 hasUsesOutsideLoop(BaseInst, L)) ||
1434 (!PossibleRedLastSet.count(RootInst) &&
1435 hasUsesOutsideLoop(RootInst, L))) {
1436 DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: iteration root match failed at "
<< *BaseInst << " vs. " << *RootInst <<
" (uses outside loop)\n"; } } while (false)
1437 " vs. " << *RootInst << " (uses outside loop)\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: iteration root match failed at "
<< *BaseInst << " vs. " << *RootInst <<
" (uses outside loop)\n"; } } while (false)
;
1438 return false;
1439 }
1440
1441 Reductions.recordPair(BaseInst, RootInst, Iter);
1442 BaseMap.insert(std::make_pair(RootInst, BaseInst));
1443
1444 LastRootIt = RootIt;
1445 Visited.insert(BaseInst);
1446 Visited.insert(RootInst);
1447 BaseIt = nextInstr(0, Uses, Visited);
1448 RootIt = nextInstr(Iter, Uses, Visited);
1449 }
1450 assert(BaseIt == Uses.end() && RootIt == Uses.end() &&((BaseIt == Uses.end() && RootIt == Uses.end() &&
"Mismatched set sizes!") ? static_cast<void> (0) : __assert_fail
("BaseIt == Uses.end() && RootIt == Uses.end() && \"Mismatched set sizes!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 1451, __PRETTY_FUNCTION__))
1451 "Mismatched set sizes!")((BaseIt == Uses.end() && RootIt == Uses.end() &&
"Mismatched set sizes!") ? static_cast<void> (0) : __assert_fail
("BaseIt == Uses.end() && RootIt == Uses.end() && \"Mismatched set sizes!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 1451, __PRETTY_FUNCTION__))
;
1452 }
1453
1454 DEBUG(dbgs() << "LRR: Matched all iteration increments for " <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Matched all iteration increments for "
<< *IV << "\n"; } } while (false)
1455 *IV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Matched all iteration increments for "
<< *IV << "\n"; } } while (false)
;
1456
1457 return true;
1458}
1459
1460void LoopReroll::DAGRootTracker::replace(const SCEV *IterCount) {
1461 BasicBlock *Header = L->getHeader();
1462 // Remove instructions associated with non-base iterations.
1463 for (BasicBlock::reverse_iterator J = Header->rbegin(), JE = Header->rend();
1464 J != JE;) {
1465 unsigned I = Uses[&*J].find_first();
1466 if (I > 0 && I < IL_All) {
1467 DEBUG(dbgs() << "LRR: removing: " << *J << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: removing: " <<
*J << "\n"; } } while (false)
;
1468 J++->eraseFromParent();
1469 continue;
1470 }
1471
1472 ++J;
1473 }
1474
1475 bool HasTwoIVs = LoopControlIV && LoopControlIV != IV;
1476
1477 if (HasTwoIVs) {
1478 updateNonLoopCtrlIncr();
1479 replaceIV(LoopControlIV, LoopControlIV, IterCount);
1480 } else
1481 // We need to create a new induction variable for each different BaseInst.
1482 for (auto &DRS : RootSets)
1483 // Insert the new induction variable.
1484 replaceIV(DRS.BaseInst, IV, IterCount);
1485
1486 SimplifyInstructionsInBlock(Header, TLI);
1487 DeleteDeadPHIs(Header, TLI);
1488}
1489
1490// For non-loop-control IVs, we only need to update the last increment
1491// with right amount, then we are done.
1492void LoopReroll::DAGRootTracker::updateNonLoopCtrlIncr() {
1493 const SCEV *NewInc = nullptr;
1494 for (auto *LoopInc : LoopIncs) {
1495 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LoopInc);
1496 const SCEVConstant *COp = nullptr;
1497 if (GEP && LoopInc->getOperand(0)->getType()->isPointerTy()) {
1498 COp = dyn_cast<SCEVConstant>(SE->getSCEV(LoopInc->getOperand(1)));
1499 } else {
1500 COp = dyn_cast<SCEVConstant>(SE->getSCEV(LoopInc->getOperand(0)));
1501 if (!COp)
1502 COp = dyn_cast<SCEVConstant>(SE->getSCEV(LoopInc->getOperand(1)));
1503 }
1504
1505 assert(COp && "Didn't find constant operand of LoopInc!\n")((COp && "Didn't find constant operand of LoopInc!\n"
) ? static_cast<void> (0) : __assert_fail ("COp && \"Didn't find constant operand of LoopInc!\\n\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 1505, __PRETTY_FUNCTION__))
;
1506
1507 const APInt &AInt = COp->getValue()->getValue();
1508 const SCEV *ScaleSCEV = SE->getConstant(COp->getType(), Scale);
1509 if (AInt.isNegative()) {
1510 NewInc = SE->getNegativeSCEV(COp);
1511 NewInc = SE->getUDivExpr(NewInc, ScaleSCEV);
1512 NewInc = SE->getNegativeSCEV(NewInc);
1513 } else
1514 NewInc = SE->getUDivExpr(COp, ScaleSCEV);
1515
1516 LoopInc->setOperand(1, dyn_cast<SCEVConstant>(NewInc)->getValue());
1517 }
1518}
1519
1520void LoopReroll::DAGRootTracker::replaceIV(Instruction *Inst,
1521 Instruction *InstIV,
1522 const SCEV *IterCount) {
1523 BasicBlock *Header = L->getHeader();
1524 int64_t Inc = IVToIncMap[InstIV];
1525 bool NeedNewIV = InstIV == LoopControlIV;
1526 bool Negative = !NeedNewIV && Inc < 0;
1527
1528 const SCEVAddRecExpr *RealIVSCEV = cast<SCEVAddRecExpr>(SE->getSCEV(Inst));
1529 const SCEV *Start = RealIVSCEV->getStart();
1530
1531 if (NeedNewIV)
1532 Start = SE->getConstant(Start->getType(), 0);
1533
1534 const SCEV *SizeOfExpr = nullptr;
1535 const SCEV *IncrExpr =
1536 SE->getConstant(RealIVSCEV->getType(), Negative ? -1 : 1);
1537 if (auto *PTy = dyn_cast<PointerType>(Inst->getType())) {
1538 Type *ElTy = PTy->getElementType();
1539 SizeOfExpr =
1540 SE->getSizeOfExpr(SE->getEffectiveSCEVType(Inst->getType()), ElTy);
1541 IncrExpr = SE->getMulExpr(IncrExpr, SizeOfExpr);
1542 }
1543 const SCEV *NewIVSCEV =
1544 SE->getAddRecExpr(Start, IncrExpr, L, SCEV::FlagAnyWrap);
1545
1546 { // Limit the lifetime of SCEVExpander.
1547 const DataLayout &DL = Header->getModule()->getDataLayout();
1548 SCEVExpander Expander(*SE, DL, "reroll");
1549 Value *NewIV = Expander.expandCodeFor(NewIVSCEV, Inst->getType(),
1550 Header->getFirstNonPHIOrDbg());
1551
1552 for (auto &KV : Uses)
1553 if (KV.second.find_first() == 0)
1554 KV.first->replaceUsesOfWith(Inst, NewIV);
1555
1556 if (BranchInst *BI = dyn_cast<BranchInst>(Header->getTerminator())) {
1557 // FIXME: Why do we need this check?
1558 if (Uses[BI].find_first() == IL_All) {
1559 const SCEV *ICSCEV = RealIVSCEV->evaluateAtIteration(IterCount, *SE);
1560
1561 if (NeedNewIV)
1562 ICSCEV = SE->getMulExpr(IterCount,
1563 SE->getConstant(IterCount->getType(), Scale));
1564
1565 // Iteration count SCEV minus or plus 1
1566 const SCEV *MinusPlus1SCEV =
1567 SE->getConstant(ICSCEV->getType(), Negative ? -1 : 1);
1568 if (Inst->getType()->isPointerTy()) {
1569 assert(SizeOfExpr && "SizeOfExpr is not initialized")((SizeOfExpr && "SizeOfExpr is not initialized") ? static_cast
<void> (0) : __assert_fail ("SizeOfExpr && \"SizeOfExpr is not initialized\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Transforms/Scalar/LoopRerollPass.cpp"
, 1569, __PRETTY_FUNCTION__))
;
1570 MinusPlus1SCEV = SE->getMulExpr(MinusPlus1SCEV, SizeOfExpr);
1571 }
1572
1573 const SCEV *ICMinusPlus1SCEV = SE->getMinusSCEV(ICSCEV, MinusPlus1SCEV);
1574 // Iteration count minus 1
1575 Instruction *InsertPtr = nullptr;
1576 if (isa<SCEVConstant>(ICMinusPlus1SCEV)) {
1577 InsertPtr = BI;
1578 } else {
1579 BasicBlock *Preheader = L->getLoopPreheader();
1580 if (!Preheader)
1581 Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA);
1582 InsertPtr = Preheader->getTerminator();
1583 }
1584
1585 if (!isa<PointerType>(NewIV->getType()) && NeedNewIV &&
1586 (SE->getTypeSizeInBits(NewIV->getType()) <
1587 SE->getTypeSizeInBits(ICMinusPlus1SCEV->getType()))) {
1588 IRBuilder<> Builder(BI);
1589 Builder.SetCurrentDebugLocation(BI->getDebugLoc());
1590 NewIV = Builder.CreateSExt(NewIV, ICMinusPlus1SCEV->getType());
1591 }
1592 Value *ICMinusPlus1 = Expander.expandCodeFor(
1593 ICMinusPlus1SCEV, NewIV->getType(), InsertPtr);
1594
1595 Value *Cond =
1596 new ICmpInst(BI, CmpInst::ICMP_EQ, NewIV, ICMinusPlus1, "exitcond");
1597 BI->setCondition(Cond);
1598
1599 if (BI->getSuccessor(1) != Header)
1600 BI->swapSuccessors();
1601 }
1602 }
1603 }
1604}
1605
1606// Validate the selected reductions. All iterations must have an isomorphic
1607// part of the reduction chain and, for non-associative reductions, the chain
1608// entries must appear in order.
1609bool LoopReroll::ReductionTracker::validateSelected() {
1610 // For a non-associative reduction, the chain entries must appear in order.
1611 for (int i : Reds) {
1612 int PrevIter = 0, BaseCount = 0, Count = 0;
1613 for (Instruction *J : PossibleReds[i]) {
1614 // Note that all instructions in the chain must have been found because
1615 // all instructions in the function must have been assigned to some
1616 // iteration.
1617 int Iter = PossibleRedIter[J];
1618 if (Iter != PrevIter && Iter != PrevIter + 1 &&
1619 !PossibleReds[i].getReducedValue()->isAssociative()) {
1620 DEBUG(dbgs() << "LRR: Out-of-order non-associative reduction: " <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Out-of-order non-associative reduction: "
<< J << "\n"; } } while (false)
1621 J << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Out-of-order non-associative reduction: "
<< J << "\n"; } } while (false)
;
1622 return false;
1623 }
1624
1625 if (Iter != PrevIter) {
1626 if (Count != BaseCount) {
1627 DEBUG(dbgs() << "LRR: Iteration " << PrevIter <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Iteration " <<
PrevIter << " reduction use count " << Count <<
" is not equal to the base use count " << BaseCount <<
"\n"; } } while (false)
1628 " reduction use count " << Count <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Iteration " <<
PrevIter << " reduction use count " << Count <<
" is not equal to the base use count " << BaseCount <<
"\n"; } } while (false)
1629 " is not equal to the base use count " <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Iteration " <<
PrevIter << " reduction use count " << Count <<
" is not equal to the base use count " << BaseCount <<
"\n"; } } while (false)
1630 BaseCount << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Iteration " <<
PrevIter << " reduction use count " << Count <<
" is not equal to the base use count " << BaseCount <<
"\n"; } } while (false)
;
1631 return false;
1632 }
1633
1634 Count = 0;
1635 }
1636
1637 ++Count;
1638 if (Iter == 0)
1639 ++BaseCount;
1640
1641 PrevIter = Iter;
1642 }
1643 }
1644
1645 return true;
1646}
1647
1648// For all selected reductions, remove all parts except those in the first
1649// iteration (and the PHI). Replace outside uses of the reduced value with uses
1650// of the first-iteration reduced value (in other words, reroll the selected
1651// reductions).
1652void LoopReroll::ReductionTracker::replaceSelected() {
1653 // Fixup reductions to refer to the last instruction associated with the
1654 // first iteration (not the last).
1655 for (int i : Reds) {
1656 int j = 0;
1657 for (int e = PossibleReds[i].size(); j != e; ++j)
1658 if (PossibleRedIter[PossibleReds[i][j]] != 0) {
1659 --j;
1660 break;
1661 }
1662
1663 // Replace users with the new end-of-chain value.
1664 SmallInstructionVector Users;
1665 for (User *U : PossibleReds[i].getReducedValue()->users()) {
1666 Users.push_back(cast<Instruction>(U));
1667 }
1668
1669 for (Instruction *User : Users)
1670 User->replaceUsesOfWith(PossibleReds[i].getReducedValue(),
1671 PossibleReds[i][j]);
1672 }
1673}
1674
1675// Reroll the provided loop with respect to the provided induction variable.
1676// Generally, we're looking for a loop like this:
1677//
1678// %iv = phi [ (preheader, ...), (body, %iv.next) ]
1679// f(%iv)
1680// %iv.1 = add %iv, 1 <-- a root increment
1681// f(%iv.1)
1682// %iv.2 = add %iv, 2 <-- a root increment
1683// f(%iv.2)
1684// %iv.scale_m_1 = add %iv, scale-1 <-- a root increment
1685// f(%iv.scale_m_1)
1686// ...
1687// %iv.next = add %iv, scale
1688// %cmp = icmp(%iv, ...)
1689// br %cmp, header, exit
1690//
1691// Notably, we do not require that f(%iv), f(%iv.1), etc. be isolated groups of
1692// instructions. In other words, the instructions in f(%iv), f(%iv.1), etc. can
1693// be intermixed with eachother. The restriction imposed by this algorithm is
1694// that the relative order of the isomorphic instructions in f(%iv), f(%iv.1),
1695// etc. be the same.
1696//
1697// First, we collect the use set of %iv, excluding the other increment roots.
1698// This gives us f(%iv). Then we iterate over the loop instructions (scale-1)
1699// times, having collected the use set of f(%iv.(i+1)), during which we:
1700// - Ensure that the next unmatched instruction in f(%iv) is isomorphic to
1701// the next unmatched instruction in f(%iv.(i+1)).
1702// - Ensure that both matched instructions don't have any external users
1703// (with the exception of last-in-chain reduction instructions).
1704// - Track the (aliasing) write set, and other side effects, of all
1705// instructions that belong to future iterations that come before the matched
1706// instructions. If the matched instructions read from that write set, then
1707// f(%iv) or f(%iv.(i+1)) has some dependency on instructions in
1708// f(%iv.(j+1)) for some j > i, and we cannot reroll the loop. Similarly,
1709// if any of these future instructions had side effects (could not be
1710// speculatively executed), and so do the matched instructions, when we
1711// cannot reorder those side-effect-producing instructions, and rerolling
1712// fails.
1713//
1714// Finally, we make sure that all loop instructions are either loop increment
1715// roots, belong to simple latch code, parts of validated reductions, part of
1716// f(%iv) or part of some f(%iv.i). If all of that is true (and all reductions
1717// have been validated), then we reroll the loop.
1718bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header,
1719 const SCEV *IterCount,
1720 ReductionTracker &Reductions) {
1721 DAGRootTracker DAGRoots(this, L, IV, SE, AA, TLI, DT, LI, PreserveLCSSA,
1722 IVToIncMap, LoopControlIV);
1723
1724 if (!DAGRoots.findRoots())
1725 return false;
1726 DEBUG(dbgs() << "LRR: Found all root induction increments for: " <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Found all root induction increments for: "
<< *IV << "\n"; } } while (false)
1727 *IV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: Found all root induction increments for: "
<< *IV << "\n"; } } while (false)
;
1728
1729 if (!DAGRoots.validate(Reductions))
1730 return false;
1731 if (!Reductions.validateSelected())
1732 return false;
1733 // At this point, we've validated the rerolling, and we're committed to
1734 // making changes!
1735
1736 Reductions.replaceSelected();
1737 DAGRoots.replace(IterCount);
1738
1739 ++NumRerolledLoops;
1740 return true;
1741}
1742
1743bool LoopReroll::runOnLoop(Loop *L, LPPassManager &LPM) {
1744 if (skipLoop(L))
1745 return false;
1746
1747 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
1748 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1749 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1750 TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1751 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1752 PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
1753
1754 BasicBlock *Header = L->getHeader();
1755 DEBUG(dbgs() << "LRR: F[" << Header->getParent()->getName() <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: F[" << Header->
getParent()->getName() << "] Loop %" << Header
->getName() << " (" << L->getNumBlocks() <<
" block(s))\n"; } } while (false)
1756 "] Loop %" << Header->getName() << " (" <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: F[" << Header->
getParent()->getName() << "] Loop %" << Header
->getName() << " (" << L->getNumBlocks() <<
" block(s))\n"; } } while (false)
1757 L->getNumBlocks() << " block(s))\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: F[" << Header->
getParent()->getName() << "] Loop %" << Header
->getName() << " (" << L->getNumBlocks() <<
" block(s))\n"; } } while (false)
;
1758
1759 // For now, we'll handle only single BB loops.
1760 if (L->getNumBlocks() > 1)
1761 return false;
1762
1763 if (!SE->hasLoopInvariantBackedgeTakenCount(L))
1764 return false;
1765
1766 const SCEV *LIBETC = SE->getBackedgeTakenCount(L);
1767 const SCEV *IterCount = SE->getAddExpr(LIBETC, SE->getOne(LIBETC->getType()));
1768 DEBUG(dbgs() << "\n Before Reroll:\n" << *(L->getHeader()) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "\n Before Reroll:\n" <<
*(L->getHeader()) << "\n"; } } while (false)
;
1769 DEBUG(dbgs() << "LRR: iteration count = " << *IterCount << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: iteration count = " <<
*IterCount << "\n"; } } while (false)
;
1770
1771 // First, we need to find the induction variable with respect to which we can
1772 // reroll (there may be several possible options).
1773 SmallInstructionVector PossibleIVs;
1774 IVToIncMap.clear();
1775 LoopControlIV = nullptr;
1776 collectPossibleIVs(L, PossibleIVs);
1777
1778 if (PossibleIVs.empty()) {
1779 DEBUG(dbgs() << "LRR: No possible IVs found\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "LRR: No possible IVs found\n"
; } } while (false)
;
1780 return false;
1781 }
1782
1783 ReductionTracker Reductions;
1784 collectPossibleReductions(L, Reductions);
1785 bool Changed = false;
1786
1787 // For each possible IV, collect the associated possible set of 'root' nodes
1788 // (i+1, i+2, etc.).
1789 for (Instruction *PossibleIV : PossibleIVs)
1790 if (reroll(PossibleIV, L, Header, IterCount, Reductions)) {
1791 Changed = true;
1792 break;
1793 }
1794 DEBUG(dbgs() << "\n After Reroll:\n" << *(L->getHeader()) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-reroll")) { dbgs() << "\n After Reroll:\n" <<
*(L->getHeader()) << "\n"; } } while (false)
;
1795
1796 // Trip count of L has changed so SE must be re-evaluated.
1797 if (Changed)
1798 SE->forgetLoop(L);
1799
1800 return Changed;
1801}

/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/Support/Casting.h

1//===- llvm/Support/Casting.h - Allow flexible, checked, casts --*- C++ -*-===//
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 the isa<X>(), cast<X>(), dyn_cast<X>(), cast_or_null<X>(),
11// and dyn_cast_or_null<X>() templates.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_SUPPORT_CASTING_H
16#define LLVM_SUPPORT_CASTING_H
17
18#include "llvm/Support/Compiler.h"
19#include "llvm/Support/type_traits.h"
20#include <cassert>
21#include <memory>
22#include <type_traits>
23
24namespace llvm {
25
26//===----------------------------------------------------------------------===//
27// isa<x> Support Templates
28//===----------------------------------------------------------------------===//
29
30// Define a template that can be specialized by smart pointers to reflect the
31// fact that they are automatically dereferenced, and are not involved with the
32// template selection process... the default implementation is a noop.
33//
34template<typename From> struct simplify_type {
35 using SimpleType = From; // The real type this represents...
36
37 // An accessor to get the real value...
38 static SimpleType &getSimplifiedValue(From &Val) { return Val; }
39};
40
41template<typename From> struct simplify_type<const From> {
42 using NonConstSimpleType = typename simplify_type<From>::SimpleType;
43 using SimpleType =
44 typename add_const_past_pointer<NonConstSimpleType>::type;
45 using RetType =
46 typename add_lvalue_reference_if_not_pointer<SimpleType>::type;
47
48 static RetType getSimplifiedValue(const From& Val) {
49 return simplify_type<From>::getSimplifiedValue(const_cast<From&>(Val));
34
Calling 'simplify_type::getSimplifiedValue'
35
Returning from 'simplify_type::getSimplifiedValue'
55
Calling 'simplify_type::getSimplifiedValue'
56
Returning from 'simplify_type::getSimplifiedValue'
50 }
51};
52
53// The core of the implementation of isa<X> is here; To and From should be
54// the names of classes. This template can be specialized to customize the
55// implementation of isa<> without rewriting it from scratch.
56template <typename To, typename From, typename Enabler = void>
57struct isa_impl {
58 static inline bool doit(const From &Val) {
59 return To::classof(&Val);
41
Calling 'Instruction::classof'
44
Returning from 'Instruction::classof'
62
Calling 'Instruction::classof'
65
Returning from 'Instruction::classof'
60 }
61};
62
63/// \brief Always allow upcasts, and perform no dynamic check for them.
64template <typename To, typename From>
65struct isa_impl<
66 To, From, typename std::enable_if<std::is_base_of<To, From>::value>::type> {
67 static inline bool doit(const From &) { return true; }
68};
69
70template <typename To, typename From> struct isa_impl_cl {
71 static inline bool doit(const From &Val) {
72 return isa_impl<To, From>::doit(Val);
73 }
74};
75
76template <typename To, typename From> struct isa_impl_cl<To, const From> {
77 static inline bool doit(const From &Val) {
78 return isa_impl<To, From>::doit(Val);
79 }
80};
81
82template <typename To, typename From>
83struct isa_impl_cl<To, const std::unique_ptr<From>> {
84 static inline bool doit(const std::unique_ptr<From> &Val) {
85 assert(Val && "isa<> used on a null pointer")((Val && "isa<> used on a null pointer") ? static_cast
<void> (0) : __assert_fail ("Val && \"isa<> used on a null pointer\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/Support/Casting.h"
, 85, __PRETTY_FUNCTION__))
;
86 return isa_impl_cl<To, From>::doit(*Val);
87 }
88};
89
90template <typename To, typename From> struct isa_impl_cl<To, From*> {
91 static inline bool doit(const From *Val) {
92 assert(Val && "isa<> used on a null pointer")((Val && "isa<> used on a null pointer") ? static_cast
<void> (0) : __assert_fail ("Val && \"isa<> used on a null pointer\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/Support/Casting.h"
, 92, __PRETTY_FUNCTION__))
;
93 return isa_impl<To, From>::doit(*Val);
94 }
95};
96
97template <typename To, typename From> struct isa_impl_cl<To, From*const> {
98 static inline bool doit(const From *Val) {
99 assert(Val && "isa<> used on a null pointer")((Val && "isa<> used on a null pointer") ? static_cast
<void> (0) : __assert_fail ("Val && \"isa<> used on a null pointer\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/Support/Casting.h"
, 99, __PRETTY_FUNCTION__))
;
100 return isa_impl<To, From>::doit(*Val);
101 }
102};
103
104template <typename To, typename From> struct isa_impl_cl<To, const From*> {
105 static inline bool doit(const From *Val) {
106 assert(Val && "isa<> used on a null pointer")((Val && "isa<> used on a null pointer") ? static_cast
<void> (0) : __assert_fail ("Val && \"isa<> used on a null pointer\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/Support/Casting.h"
, 106, __PRETTY_FUNCTION__))
;
39
Within the expansion of the macro 'assert':
60
Within the expansion of the macro 'assert':
107 return isa_impl<To, From>::doit(*Val);
40
Calling 'isa_impl::doit'
45
Returning from 'isa_impl::doit'
61
Calling 'isa_impl::doit'
66
Returning from 'isa_impl::doit'
108 }
109};
110
111template <typename To, typename From> struct isa_impl_cl<To, const From*const> {
112 static inline bool doit(const From *Val) {
113 assert(Val && "isa<> used on a null pointer")((Val && "isa<> used on a null pointer") ? static_cast
<void> (0) : __assert_fail ("Val && \"isa<> used on a null pointer\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/Support/Casting.h"
, 113, __PRETTY_FUNCTION__))
;
114 return isa_impl<To, From>::doit(*Val);
115 }
116};
117
118template<typename To, typename From, typename SimpleFrom>
119struct isa_impl_wrap {
120 // When From != SimplifiedType, we can simplify the type some more by using
121 // the simplify_type template.
122 static bool doit(const From &Val) {
123 return isa_impl_wrap<To, SimpleFrom,
37
Calling 'isa_impl_wrap::doit'
47
Returning from 'isa_impl_wrap::doit'
58
Calling 'isa_impl_wrap::doit'
68
Returning from 'isa_impl_wrap::doit'
124 typename simplify_type<SimpleFrom>::SimpleType>::doit(
125 simplify_type<const From>::getSimplifiedValue(Val));
33
Calling 'simplify_type::getSimplifiedValue'
36
Returning from 'simplify_type::getSimplifiedValue'
54
Calling 'simplify_type::getSimplifiedValue'
57
Returning from 'simplify_type::getSimplifiedValue'
126 }
127};
128
129template<typename To, typename FromTy>
130struct isa_impl_wrap<To, FromTy, FromTy> {
131 // When From == SimpleType, we are as simple as we are going to get.
132 static bool doit(const FromTy &Val) {
133 return isa_impl_cl<To,FromTy>::doit(Val);
38
Calling 'isa_impl_cl::doit'
46
Returning from 'isa_impl_cl::doit'
59
Calling 'isa_impl_cl::doit'
67
Returning from 'isa_impl_cl::doit'
134 }
135};
136
137// isa<X> - Return true if the parameter to the template is an instance of the
138// template type argument. Used like this:
139//
140// if (isa<Type>(myVal)) { ... }
141//
142template <class X, class Y> LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isa(const Y &Val) {
143 return isa_impl_wrap<X, const Y,
32
Calling 'isa_impl_wrap::doit'
48
Returning from 'isa_impl_wrap::doit'
53
Calling 'isa_impl_wrap::doit'
69
Returning from 'isa_impl_wrap::doit'
144 typename simplify_type<const Y>::SimpleType>::doit(Val);
145}
146
147//===----------------------------------------------------------------------===//
148// cast<x> Support Templates
149//===----------------------------------------------------------------------===//
150
151template<class To, class From> struct cast_retty;
152
153// Calculate what type the 'cast' function should return, based on a requested
154// type of To and a source type of From.
155template<class To, class From> struct cast_retty_impl {
156 using ret_type = To &; // Normal case, return Ty&
157};
158template<class To, class From> struct cast_retty_impl<To, const From> {
159 using ret_type = const To &; // Normal case, return Ty&
160};
161
162template<class To, class From> struct cast_retty_impl<To, From*> {
163 using ret_type = To *; // Pointer arg case, return Ty*
164};
165
166template<class To, class From> struct cast_retty_impl<To, const From*> {
167 using ret_type = const To *; // Constant pointer arg case, return const Ty*
168};
169
170template<class To, class From> struct cast_retty_impl<To, const From*const> {
171 using ret_type = const To *; // Constant pointer arg case, return const Ty*
172};
173
174template <class To, class From>
175struct cast_retty_impl<To, std::unique_ptr<From>> {
176private:
177 using PointerType = typename cast_retty_impl<To, From *>::ret_type;
178 using ResultType = typename std::remove_pointer<PointerType>::type;
179
180public:
181 using ret_type = std::unique_ptr<ResultType>;
182};
183
184template<class To, class From, class SimpleFrom>
185struct cast_retty_wrap {
186 // When the simplified type and the from type are not the same, use the type
187 // simplifier to reduce the type, then reuse cast_retty_impl to get the
188 // resultant type.
189 using ret_type = typename cast_retty<To, SimpleFrom>::ret_type;
190};
191
192template<class To, class FromTy>
193struct cast_retty_wrap<To, FromTy, FromTy> {
194 // When the simplified type is equal to the from type, use it directly.
195 using ret_type = typename cast_retty_impl<To,FromTy>::ret_type;
196};
197
198template<class To, class From>
199struct cast_retty {
200 using ret_type = typename cast_retty_wrap<
201 To, From, typename simplify_type<From>::SimpleType>::ret_type;
202};
203
204// Ensure the non-simple values are converted using the simplify_type template
205// that may be specialized by smart pointers...
206//
207template<class To, class From, class SimpleFrom> struct cast_convert_val {
208 // This is not a simple type, use the template to simplify it...
209 static typename cast_retty<To, From>::ret_type doit(From &Val) {
210 return cast_convert_val<To, SimpleFrom,
211 typename simplify_type<SimpleFrom>::SimpleType>::doit(
212 simplify_type<From>::getSimplifiedValue(Val));
213 }
214};
215
216template<class To, class FromTy> struct cast_convert_val<To,FromTy,FromTy> {
217 // This _is_ a simple type, just cast it.
218 static typename cast_retty<To, FromTy>::ret_type doit(const FromTy &Val) {
219 typename cast_retty<To, FromTy>::ret_type Res2
220 = (typename cast_retty<To, FromTy>::ret_type)const_cast<FromTy&>(Val);
221 return Res2;
222 }
223};
224
225template <class X> struct is_simple_type {
226 static const bool value =
227 std::is_same<X, typename simplify_type<X>::SimpleType>::value;
228};
229
230// cast<X> - Return the argument parameter cast to the specified type. This
231// casting operator asserts that the type is correct, so it does not return null
232// on failure. It does not allow a null argument (use cast_or_null for that).
233// It is typically used like this:
234//
235// cast<Instruction>(myVal)->getParent()
236//
237template <class X, class Y>
238inline typename std::enable_if<!is_simple_type<Y>::value,
239 typename cast_retty<X, const Y>::ret_type>::type
240cast(const Y &Val) {
241 assert(isa<X>(Val) && "cast<Ty>() argument of incompatible type!")((isa<X>(Val) && "cast<Ty>() argument of incompatible type!"
) ? static_cast<void> (0) : __assert_fail ("isa<X>(Val) && \"cast<Ty>() argument of incompatible type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/Support/Casting.h"
, 241, __PRETTY_FUNCTION__))
;
242 return cast_convert_val<
243 X, const Y, typename simplify_type<const Y>::SimpleType>::doit(Val);
244}
245
246template <class X, class Y>
247inline typename cast_retty<X, Y>::ret_type cast(Y &Val) {
248 assert(isa<X>(Val) && "cast<Ty>() argument of incompatible type!")((isa<X>(Val) && "cast<Ty>() argument of incompatible type!"
) ? static_cast<void> (0) : __assert_fail ("isa<X>(Val) && \"cast<Ty>() argument of incompatible type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/Support/Casting.h"
, 248, __PRETTY_FUNCTION__))
;
249 return cast_convert_val<X, Y,
250 typename simplify_type<Y>::SimpleType>::doit(Val);
251}
252
253template <class X, class Y>
254inline typename cast_retty<X, Y *>::ret_type cast(Y *Val) {
255 assert(isa<X>(Val) && "cast<Ty>() argument of incompatible type!")((isa<X>(Val) && "cast<Ty>() argument of incompatible type!"
) ? static_cast<void> (0) : __assert_fail ("isa<X>(Val) && \"cast<Ty>() argument of incompatible type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/Support/Casting.h"
, 255, __PRETTY_FUNCTION__))
;
52
Within the expansion of the macro 'assert':
a
Calling 'isa'
b
Returning from 'isa'
256 return cast_convert_val<X, Y*,
70
Calling 'cast_convert_val::doit'
71
Returning from 'cast_convert_val::doit'
257 typename simplify_type<Y*>::SimpleType>::doit(Val);
258}
259
260template <class X, class Y>
261inline typename cast_retty<X, std::unique_ptr<Y>>::ret_type
262cast(std::unique_ptr<Y> &&Val) {
263 assert(isa<X>(Val.get()) && "cast<Ty>() argument of incompatible type!")((isa<X>(Val.get()) && "cast<Ty>() argument of incompatible type!"
) ? static_cast<void> (0) : __assert_fail ("isa<X>(Val.get()) && \"cast<Ty>() argument of incompatible type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/Support/Casting.h"
, 263, __PRETTY_FUNCTION__))
;
264 using ret_type = typename cast_retty<X, std::unique_ptr<Y>>::ret_type;
265 return ret_type(
266 cast_convert_val<X, Y *, typename simplify_type<Y *>::SimpleType>::doit(
267 Val.release()));
268}
269
270// cast_or_null<X> - Functionally identical to cast, except that a null value is
271// accepted.
272//
273template <class X, class Y>
274LLVM_NODISCARD[[clang::warn_unused_result]] inline
275 typename std::enable_if<!is_simple_type<Y>::value,
276 typename cast_retty<X, const Y>::ret_type>::type
277 cast_or_null(const Y &Val) {
278 if (!Val)
279 return nullptr;
280 assert(isa<X>(Val) && "cast_or_null<Ty>() argument of incompatible type!")((isa<X>(Val) && "cast_or_null<Ty>() argument of incompatible type!"
) ? static_cast<void> (0) : __assert_fail ("isa<X>(Val) && \"cast_or_null<Ty>() argument of incompatible type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/Support/Casting.h"
, 280, __PRETTY_FUNCTION__))
;
281 return cast<X>(Val);
282}
283
284template <class X, class Y>
285LLVM_NODISCARD[[clang::warn_unused_result]] inline
286 typename std::enable_if<!is_simple_type<Y>::value,
287 typename cast_retty<X, Y>::ret_type>::type
288 cast_or_null(Y &Val) {
289 if (!Val)
290 return nullptr;
291 assert(isa<X>(Val) && "cast_or_null<Ty>() argument of incompatible type!")((isa<X>(Val) && "cast_or_null<Ty>() argument of incompatible type!"
) ? static_cast<void> (0) : __assert_fail ("isa<X>(Val) && \"cast_or_null<Ty>() argument of incompatible type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/Support/Casting.h"
, 291, __PRETTY_FUNCTION__))
;
292 return cast<X>(Val);
293}
294
295template <class X, class Y>
296LLVM_NODISCARD[[clang::warn_unused_result]] inline typename cast_retty<X, Y *>::ret_type
297cast_or_null(Y *Val) {
298 if (!Val) return nullptr;
299 assert(isa<X>(Val) && "cast_or_null<Ty>() argument of incompatible type!")((isa<X>(Val) && "cast_or_null<Ty>() argument of incompatible type!"
) ? static_cast<void> (0) : __assert_fail ("isa<X>(Val) && \"cast_or_null<Ty>() argument of incompatible type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/Support/Casting.h"
, 299, __PRETTY_FUNCTION__))
;
300 return cast<X>(Val);
301}
302
303template <class X, class Y>
304inline typename cast_retty<X, std::unique_ptr<Y>>::ret_type
305cast_or_null(std::unique_ptr<Y> &&Val) {
306 if (!Val)
307 return nullptr;
308 return cast<X>(std::move(Val));
309}
310
311// dyn_cast<X> - Return the argument parameter cast to the specified type. This
312// casting operator returns null if the argument is of the wrong type, so it can
313// be used to test for a type as well as cast if successful. This should be
314// used in the context of an if statement like this:
315//
316// if (const Instruction *I = dyn_cast<Instruction>(myVal)) { ... }
317//
318
319template <class X, class Y>
320LLVM_NODISCARD[[clang::warn_unused_result]] inline
321 typename std::enable_if<!is_simple_type<Y>::value,
322 typename cast_retty<X, const Y>::ret_type>::type
323 dyn_cast(const Y &Val) {
324 return isa<X>(Val) ? cast<X>(Val) : nullptr;
325}
326
327template <class X, class Y>
328LLVM_NODISCARD[[clang::warn_unused_result]] inline typename cast_retty<X, Y>::ret_type dyn_cast(Y &Val) {
329 return isa<X>(Val) ? cast<X>(Val) : nullptr;
330}
331
332template <class X, class Y>
333LLVM_NODISCARD[[clang::warn_unused_result]] inline typename cast_retty<X, Y *>::ret_type dyn_cast(Y *Val) {
334 return isa<X>(Val) ? cast<X>(Val) : nullptr;
31
Calling 'isa'
49
Returning from 'isa'
50
'?' condition is true
51
Calling 'cast'
72
Returning from 'cast'
335}
336
337// dyn_cast_or_null<X> - Functionally identical to dyn_cast, except that a null
338// value is accepted.
339//
340template <class X, class Y>
341LLVM_NODISCARD[[clang::warn_unused_result]] inline
342 typename std::enable_if<!is_simple_type<Y>::value,
343 typename cast_retty<X, const Y>::ret_type>::type
344 dyn_cast_or_null(const Y &Val) {
345 return (Val && isa<X>(Val)) ? cast<X>(Val) : nullptr;
346}
347
348template <class X, class Y>
349LLVM_NODISCARD[[clang::warn_unused_result]] inline
350 typename std::enable_if<!is_simple_type<Y>::value,
351 typename cast_retty<X, Y>::ret_type>::type
352 dyn_cast_or_null(Y &Val) {
353 return (Val && isa<X>(Val)) ? cast<X>(Val) : nullptr;
354}
355
356template <class X, class Y>
357LLVM_NODISCARD[[clang::warn_unused_result]] inline typename cast_retty<X, Y *>::ret_type
358dyn_cast_or_null(Y *Val) {
359 return (Val && isa<X>(Val)) ? cast<X>(Val) : nullptr;
360}
361
362// unique_dyn_cast<X> - Given a unique_ptr<Y>, try to return a unique_ptr<X>,
363// taking ownership of the input pointer iff isa<X>(Val) is true. If the
364// cast is successful, From refers to nullptr on exit and the casted value
365// is returned. If the cast is unsuccessful, the function returns nullptr
366// and From is unchanged.
367template <class X, class Y>
368LLVM_NODISCARD[[clang::warn_unused_result]] inline auto unique_dyn_cast(std::unique_ptr<Y> &Val)
369 -> decltype(cast<X>(Val)) {
370 if (!isa<X>(Val))
371 return nullptr;
372 return cast<X>(std::move(Val));
373}
374
375template <class X, class Y>
376LLVM_NODISCARD[[clang::warn_unused_result]] inline auto unique_dyn_cast(std::unique_ptr<Y> &&Val)
377 -> decltype(cast<X>(Val)) {
378 return unique_dyn_cast<X, Y>(Val);
379}
380
381// dyn_cast_or_null<X> - Functionally identical to unique_dyn_cast, except that
382// a null value is accepted.
383template <class X, class Y>
384LLVM_NODISCARD[[clang::warn_unused_result]] inline auto unique_dyn_cast_or_null(std::unique_ptr<Y> &Val)
385 -> decltype(cast<X>(Val)) {
386 if (!Val)
387 return nullptr;
388 return unique_dyn_cast<X, Y>(Val);
389}
390
391template <class X, class Y>
392LLVM_NODISCARD[[clang::warn_unused_result]] inline auto unique_dyn_cast_or_null(std::unique_ptr<Y> &&Val)
393 -> decltype(cast<X>(Val)) {
394 return unique_dyn_cast_or_null<X, Y>(Val);
395}
396
397} // end namespace llvm
398
399#endif // LLVM_SUPPORT_CASTING_H

/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/IR/Instruction.h

1//===-- llvm/Instruction.h - Instruction class definition -------*- C++ -*-===//
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 contains the declaration of the Instruction class, which is the
11// base class for all of the LLVM instructions.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_IR_INSTRUCTION_H
16#define LLVM_IR_INSTRUCTION_H
17
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/None.h"
20#include "llvm/ADT/StringRef.h"
21#include "llvm/ADT/ilist_node.h"
22#include "llvm/IR/DebugLoc.h"
23#include "llvm/IR/SymbolTableListTraits.h"
24#include "llvm/IR/User.h"
25#include "llvm/IR/Value.h"
26#include "llvm/Support/Casting.h"
27#include <algorithm>
28#include <cassert>
29#include <cstdint>
30#include <utility>
31
32namespace llvm {
33
34class BasicBlock;
35class FastMathFlags;
36class MDNode;
37struct AAMDNodes;
38
39template <> struct ilist_alloc_traits<Instruction> {
40 static inline void deleteNode(Instruction *V);
41};
42
43class Instruction : public User,
44 public ilist_node_with_parent<Instruction, BasicBlock> {
45 BasicBlock *Parent;
46 DebugLoc DbgLoc; // 'dbg' Metadata cache.
47
48 enum {
49 /// This is a bit stored in the SubClassData field which indicates whether
50 /// this instruction has metadata attached to it or not.
51 HasMetadataBit = 1 << 15
52 };
53
54protected:
55 ~Instruction(); // Use deleteValue() to delete a generic Instruction.
56
57public:
58 Instruction(const Instruction &) = delete;
59 Instruction &operator=(const Instruction &) = delete;
60
61 /// Specialize the methods defined in Value, as we know that an instruction
62 /// can only be used by other instructions.
63 Instruction *user_back() { return cast<Instruction>(*user_begin());}
64 const Instruction *user_back() const { return cast<Instruction>(*user_begin());}
65
66 inline const BasicBlock *getParent() const { return Parent; }
67 inline BasicBlock *getParent() { return Parent; }
68
69 /// Return the module owning the function this instruction belongs to
70 /// or nullptr it the function does not have a module.
71 ///
72 /// Note: this is undefined behavior if the instruction does not have a
73 /// parent, or the parent basic block does not have a parent function.
74 const Module *getModule() const;
75 Module *getModule() {
76 return const_cast<Module *>(
77 static_cast<const Instruction *>(this)->getModule());
78 }
79
80 /// Return the function this instruction belongs to.
81 ///
82 /// Note: it is undefined behavior to call this on an instruction not
83 /// currently inserted into a function.
84 const Function *getFunction() const;
85 Function *getFunction() {
86 return const_cast<Function *>(
87 static_cast<const Instruction *>(this)->getFunction());
88 }
89
90 /// This method unlinks 'this' from the containing basic block, but does not
91 /// delete it.
92 void removeFromParent();
93
94 /// This method unlinks 'this' from the containing basic block and deletes it.
95 ///
96 /// \returns an iterator pointing to the element after the erased one
97 SymbolTableList<Instruction>::iterator eraseFromParent();
98
99 /// Insert an unlinked instruction into a basic block immediately before
100 /// the specified instruction.
101 void insertBefore(Instruction *InsertPos);
102
103 /// Insert an unlinked instruction into a basic block immediately after the
104 /// specified instruction.
105 void insertAfter(Instruction *InsertPos);
106
107 /// Unlink this instruction from its current basic block and insert it into
108 /// the basic block that MovePos lives in, right before MovePos.
109 void moveBefore(Instruction *MovePos);
110
111 /// Unlink this instruction and insert into BB before I.
112 ///
113 /// \pre I is a valid iterator into BB.
114 void moveBefore(BasicBlock &BB, SymbolTableList<Instruction>::iterator I);
115
116 /// Unlink this instruction from its current basic block and insert it into
117 /// the basic block that MovePos lives in, right after MovePos.
118 void moveAfter(Instruction *MovePos);
119
120 //===--------------------------------------------------------------------===//
121 // Subclass classification.
122 //===--------------------------------------------------------------------===//
123
124 /// Returns a member of one of the enums like Instruction::Add.
125 unsigned getOpcode() const { return getValueID() - InstructionVal; }
126
127 const char *getOpcodeName() const { return getOpcodeName(getOpcode()); }
128 bool isTerminator() const { return isTerminator(getOpcode()); }
129 bool isBinaryOp() const { return isBinaryOp(getOpcode()); }
130 bool isShift() { return isShift(getOpcode()); }
131 bool isCast() const { return isCast(getOpcode()); }
132 bool isFuncletPad() const { return isFuncletPad(getOpcode()); }
133
134 static const char* getOpcodeName(unsigned OpCode);
135
136 static inline bool isTerminator(unsigned OpCode) {
137 return OpCode >= TermOpsBegin && OpCode < TermOpsEnd;
138 }
139
140 static inline bool isBinaryOp(unsigned Opcode) {
141 return Opcode >= BinaryOpsBegin && Opcode < BinaryOpsEnd;
142 }
143
144 /// Determine if the Opcode is one of the shift instructions.
145 static inline bool isShift(unsigned Opcode) {
146 return Opcode >= Shl && Opcode <= AShr;
147 }
148
149 /// Return true if this is a logical shift left or a logical shift right.
150 inline bool isLogicalShift() const {
151 return getOpcode() == Shl || getOpcode() == LShr;
152 }
153
154 /// Return true if this is an arithmetic shift right.
155 inline bool isArithmeticShift() const {
156 return getOpcode() == AShr;
157 }
158
159 /// Determine if the Opcode is and/or/xor.
160 static inline bool isBitwiseLogicOp(unsigned Opcode) {
161 return Opcode == And || Opcode == Or || Opcode == Xor;
162 }
163
164 /// Return true if this is and/or/xor.
165 inline bool isBitwiseLogicOp() const {
166 return isBitwiseLogicOp(getOpcode());
167 }
168
169 /// Determine if the OpCode is one of the CastInst instructions.
170 static inline bool isCast(unsigned OpCode) {
171 return OpCode >= CastOpsBegin && OpCode < CastOpsEnd;
172 }
173
174 /// Determine if the OpCode is one of the FuncletPadInst instructions.
175 static inline bool isFuncletPad(unsigned OpCode) {
176 return OpCode >= FuncletPadOpsBegin && OpCode < FuncletPadOpsEnd;
177 }
178
179 //===--------------------------------------------------------------------===//
180 // Metadata manipulation.
181 //===--------------------------------------------------------------------===//
182
183 /// Return true if this instruction has any metadata attached to it.
184 bool hasMetadata() const { return DbgLoc || hasMetadataHashEntry(); }
185
186 /// Return true if this instruction has metadata attached to it other than a
187 /// debug location.
188 bool hasMetadataOtherThanDebugLoc() const {
189 return hasMetadataHashEntry();
190 }
191
192 /// Get the metadata of given kind attached to this Instruction.
193 /// If the metadata is not found then return null.
194 MDNode *getMetadata(unsigned KindID) const {
195 if (!hasMetadata()) return nullptr;
196 return getMetadataImpl(KindID);
197 }
198
199 /// Get the metadata of given kind attached to this Instruction.
200 /// If the metadata is not found then return null.
201 MDNode *getMetadata(StringRef Kind) const {
202 if (!hasMetadata()) return nullptr;
203 return getMetadataImpl(Kind);
204 }
205
206 /// Get all metadata attached to this Instruction. The first element of each
207 /// pair returned is the KindID, the second element is the metadata value.
208 /// This list is returned sorted by the KindID.
209 void
210 getAllMetadata(SmallVectorImpl<std::pair<unsigned, MDNode *>> &MDs) const {
211 if (hasMetadata())
212 getAllMetadataImpl(MDs);
213 }
214
215 /// This does the same thing as getAllMetadata, except that it filters out the
216 /// debug location.
217 void getAllMetadataOtherThanDebugLoc(
218 SmallVectorImpl<std::pair<unsigned, MDNode *>> &MDs) const {
219 if (hasMetadataOtherThanDebugLoc())
220 getAllMetadataOtherThanDebugLocImpl(MDs);
221 }
222
223 /// Fills the AAMDNodes structure with AA metadata from this instruction.
224 /// When Merge is true, the existing AA metadata is merged with that from this
225 /// instruction providing the most-general result.
226 void getAAMetadata(AAMDNodes &N, bool Merge = false) const;
227
228 /// Set the metadata of the specified kind to the specified node. This updates
229 /// or replaces metadata if already present, or removes it if Node is null.
230 void setMetadata(unsigned KindID, MDNode *Node);
231 void setMetadata(StringRef Kind, MDNode *Node);
232
233 /// Copy metadata from \p SrcInst to this instruction. \p WL, if not empty,
234 /// specifies the list of meta data that needs to be copied. If \p WL is
235 /// empty, all meta data will be copied.
236 void copyMetadata(const Instruction &SrcInst,
237 ArrayRef<unsigned> WL = ArrayRef<unsigned>());
238
239 /// If the instruction has "branch_weights" MD_prof metadata and the MDNode
240 /// has three operands (including name string), swap the order of the
241 /// metadata.
242 void swapProfMetadata();
243
244 /// Drop all unknown metadata except for debug locations.
245 /// @{
246 /// Passes are required to drop metadata they don't understand. This is a
247 /// convenience method for passes to do so.
248 void dropUnknownNonDebugMetadata(ArrayRef<unsigned> KnownIDs);
249 void dropUnknownNonDebugMetadata() {
250 return dropUnknownNonDebugMetadata(None);
251 }
252 void dropUnknownNonDebugMetadata(unsigned ID1) {
253 return dropUnknownNonDebugMetadata(makeArrayRef(ID1));
254 }
255 void dropUnknownNonDebugMetadata(unsigned ID1, unsigned ID2) {
256 unsigned IDs[] = {ID1, ID2};
257 return dropUnknownNonDebugMetadata(IDs);
258 }
259 /// @}
260
261 /// Sets the metadata on this instruction from the AAMDNodes structure.
262 void setAAMetadata(const AAMDNodes &N);
263
264 /// Retrieve the raw weight values of a conditional branch or select.
265 /// Returns true on success with profile weights filled in.
266 /// Returns false if no metadata or invalid metadata was found.
267 bool extractProfMetadata(uint64_t &TrueVal, uint64_t &FalseVal) const;
268
269 /// Retrieve total raw weight values of a branch.
270 /// Returns true on success with profile total weights filled in.
271 /// Returns false if no metadata was found.
272 bool extractProfTotalWeight(uint64_t &TotalVal) const;
273
274 /// Updates branch_weights metadata by scaling it by \p S / \p T.
275 void updateProfWeight(uint64_t S, uint64_t T);
276
277 /// Sets the branch_weights metadata to \p W for CallInst.
278 void setProfWeight(uint64_t W);
279
280 /// Set the debug location information for this instruction.
281 void setDebugLoc(DebugLoc Loc) { DbgLoc = std::move(Loc); }
282
283 /// Return the debug location for this node as a DebugLoc.
284 const DebugLoc &getDebugLoc() const { return DbgLoc; }
285
286 /// Set or clear the nsw flag on this instruction, which must be an operator
287 /// which supports this flag. See LangRef.html for the meaning of this flag.
288 void setHasNoUnsignedWrap(bool b = true);
289
290 /// Set or clear the nsw flag on this instruction, which must be an operator
291 /// which supports this flag. See LangRef.html for the meaning of this flag.
292 void setHasNoSignedWrap(bool b = true);
293
294 /// Set or clear the exact flag on this instruction, which must be an operator
295 /// which supports this flag. See LangRef.html for the meaning of this flag.
296 void setIsExact(bool b = true);
297
298 /// Determine whether the no unsigned wrap flag is set.
299 bool hasNoUnsignedWrap() const;
300
301 /// Determine whether the no signed wrap flag is set.
302 bool hasNoSignedWrap() const;
303
304 /// Drops flags that may cause this instruction to evaluate to poison despite
305 /// having non-poison inputs.
306 void dropPoisonGeneratingFlags();
307
308 /// Determine whether the exact flag is set.
309 bool isExact() const;
310
311 /// Set or clear all fast-math-flags on this instruction, which must be an
312 /// operator which supports this flag. See LangRef.html for the meaning of
313 /// this flag.
314 void setFast(bool B);
315
316 /// Set or clear the reassociation flag on this instruction, which must be
317 /// an operator which supports this flag. See LangRef.html for the meaning of
318 /// this flag.
319 void setHasAllowReassoc(bool B);
320
321 /// Set or clear the no-nans flag on this instruction, which must be an
322 /// operator which supports this flag. See LangRef.html for the meaning of
323 /// this flag.
324 void setHasNoNaNs(bool B);
325
326 /// Set or clear the no-infs flag on this instruction, which must be an
327 /// operator which supports this flag. See LangRef.html for the meaning of
328 /// this flag.
329 void setHasNoInfs(bool B);
330
331 /// Set or clear the no-signed-zeros flag on this instruction, which must be
332 /// an operator which supports this flag. See LangRef.html for the meaning of
333 /// this flag.
334 void setHasNoSignedZeros(bool B);
335
336 /// Set or clear the allow-reciprocal flag on this instruction, which must be
337 /// an operator which supports this flag. See LangRef.html for the meaning of
338 /// this flag.
339 void setHasAllowReciprocal(bool B);
340
341 /// Set or clear the approximate-math-functions flag on this instruction,
342 /// which must be an operator which supports this flag. See LangRef.html for
343 /// the meaning of this flag.
344 void setHasApproxFunc(bool B);
345
346 /// Convenience function for setting multiple fast-math flags on this
347 /// instruction, which must be an operator which supports these flags. See
348 /// LangRef.html for the meaning of these flags.
349 void setFastMathFlags(FastMathFlags FMF);
350
351 /// Convenience function for transferring all fast-math flag values to this
352 /// instruction, which must be an operator which supports these flags. See
353 /// LangRef.html for the meaning of these flags.
354 void copyFastMathFlags(FastMathFlags FMF);
355
356 /// Determine whether all fast-math-flags are set.
357 bool isFast() const;
358
359 /// Determine whether the allow-reassociation flag is set.
360 bool hasAllowReassoc() const;
361
362 /// Determine whether the no-NaNs flag is set.
363 bool hasNoNaNs() const;
364
365 /// Determine whether the no-infs flag is set.
366 bool hasNoInfs() const;
367
368 /// Determine whether the no-signed-zeros flag is set.
369 bool hasNoSignedZeros() const;
370
371 /// Determine whether the allow-reciprocal flag is set.
372 bool hasAllowReciprocal() const;
373
374 /// Determine whether the allow-contract flag is set.
375 bool hasAllowContract() const;
376
377 /// Determine whether the approximate-math-functions flag is set.
378 bool hasApproxFunc() const;
379
380 /// Convenience function for getting all the fast-math flags, which must be an
381 /// operator which supports these flags. See LangRef.html for the meaning of
382 /// these flags.
383 FastMathFlags getFastMathFlags() const;
384
385 /// Copy I's fast-math flags
386 void copyFastMathFlags(const Instruction *I);
387
388 /// Convenience method to copy supported exact, fast-math, and (optionally)
389 /// wrapping flags from V to this instruction.
390 void copyIRFlags(const Value *V, bool IncludeWrapFlags = true);
391
392 /// Logical 'and' of any supported wrapping, exact, and fast-math flags of
393 /// V and this instruction.
394 void andIRFlags(const Value *V);
395
396 /// Merge 2 debug locations and apply it to the Instruction. If the
397 /// instruction is a CallIns, we need to traverse the inline chain to find
398 /// the common scope. This is not efficient for N-way merging as each time
399 /// you merge 2 iterations, you need to rebuild the hashmap to find the
400 /// common scope. However, we still choose this API because:
401 /// 1) Simplicity: it takes 2 locations instead of a list of locations.
402 /// 2) In worst case, it increases the complexity from O(N*I) to
403 /// O(2*N*I), where N is # of Instructions to merge, and I is the
404 /// maximum level of inline stack. So it is still linear.
405 /// 3) Merging of call instructions should be extremely rare in real
406 /// applications, thus the N-way merging should be in code path.
407 /// The DebugLoc attached to this instruction will be overwritten by the
408 /// merged DebugLoc.
409 void applyMergedLocation(const DILocation *LocA, const DILocation *LocB);
410
411private:
412 /// Return true if we have an entry in the on-the-side metadata hash.
413 bool hasMetadataHashEntry() const {
414 return (getSubclassDataFromValue() & HasMetadataBit) != 0;
415 }
416
417 // These are all implemented in Metadata.cpp.
418 MDNode *getMetadataImpl(unsigned KindID) const;
419 MDNode *getMetadataImpl(StringRef Kind) const;
420 void
421 getAllMetadataImpl(SmallVectorImpl<std::pair<unsigned, MDNode *>> &) const;
422 void getAllMetadataOtherThanDebugLocImpl(
423 SmallVectorImpl<std::pair<unsigned, MDNode *>> &) const;
424 /// Clear all hashtable-based metadata from this instruction.
425 void clearMetadataHashEntries();
426
427public:
428 //===--------------------------------------------------------------------===//
429 // Predicates and helper methods.
430 //===--------------------------------------------------------------------===//
431
432 /// Return true if the instruction is associative:
433 ///
434 /// Associative operators satisfy: x op (y op z) === (x op y) op z
435 ///
436 /// In LLVM, the Add, Mul, And, Or, and Xor operators are associative.
437 ///
438 bool isAssociative() const LLVM_READONLY__attribute__((__pure__));
439 static bool isAssociative(unsigned Opcode) {
440 return Opcode == And || Opcode == Or || Opcode == Xor ||
441 Opcode == Add || Opcode == Mul;
442 }
443
444 /// Return true if the instruction is commutative:
445 ///
446 /// Commutative operators satisfy: (x op y) === (y op x)
447 ///
448 /// In LLVM, these are the commutative operators, plus SetEQ and SetNE, when
449 /// applied to any type.
450 ///
451 bool isCommutative() const { return isCommutative(getOpcode()); }
452 static bool isCommutative(unsigned Opcode) {
453 switch (Opcode) {
454 case Add: case FAdd:
455 case Mul: case FMul:
456 case And: case Or: case Xor:
457 return true;
458 default:
459 return false;
460 }
461 }
462
463 /// Return true if the instruction is idempotent:
464 ///
465 /// Idempotent operators satisfy: x op x === x
466 ///
467 /// In LLVM, the And and Or operators are idempotent.
468 ///
469 bool isIdempotent() const { return isIdempotent(getOpcode()); }
470 static bool isIdempotent(unsigned Opcode) {
471 return Opcode == And || Opcode == Or;
472 }
473
474 /// Return true if the instruction is nilpotent:
475 ///
476 /// Nilpotent operators satisfy: x op x === Id,
477 ///
478 /// where Id is the identity for the operator, i.e. a constant such that
479 /// x op Id === x and Id op x === x for all x.
480 ///
481 /// In LLVM, the Xor operator is nilpotent.
482 ///
483 bool isNilpotent() const { return isNilpotent(getOpcode()); }
484 static bool isNilpotent(unsigned Opcode) {
485 return Opcode == Xor;
486 }
487
488 /// Return true if this instruction may modify memory.
489 bool mayWriteToMemory() const;
490
491 /// Return true if this instruction may read memory.
492 bool mayReadFromMemory() const;
493
494 /// Return true if this instruction may read or write memory.
495 bool mayReadOrWriteMemory() const {
496 return mayReadFromMemory() || mayWriteToMemory();
497 }
498
499 /// Return true if this instruction has an AtomicOrdering of unordered or
500 /// higher.
501 bool isAtomic() const;
502
503 /// Return true if this atomic instruction loads from memory.
504 bool hasAtomicLoad() const;
505
506 /// Return true if this atomic instruction stores to memory.
507 bool hasAtomicStore() const;
508
509 /// Return true if this instruction may throw an exception.
510 bool mayThrow() const;
511
512 /// Return true if this instruction behaves like a memory fence: it can load
513 /// or store to memory location without being given a memory location.
514 bool isFenceLike() const {
515 switch (getOpcode()) {
516 default:
517 return false;
518 // This list should be kept in sync with the list in mayWriteToMemory for
519 // all opcodes which don't have a memory location.
520 case Instruction::Fence:
521 case Instruction::CatchPad:
522 case Instruction::CatchRet:
523 case Instruction::Call:
524 case Instruction::Invoke:
525 return true;
526 }
527 }
528
529 /// Return true if the instruction may have side effects.
530 ///
531 /// Note that this does not consider malloc and alloca to have side
532 /// effects because the newly allocated memory is completely invisible to
533 /// instructions which don't use the returned value. For cases where this
534 /// matters, isSafeToSpeculativelyExecute may be more appropriate.
535 bool mayHaveSideEffects() const { return mayWriteToMemory() || mayThrow(); }
536
537 /// Return true if the instruction is a variety of EH-block.
538 bool isEHPad() const {
539 switch (getOpcode()) {
540 case Instruction::CatchSwitch:
541 case Instruction::CatchPad:
542 case Instruction::CleanupPad:
543 case Instruction::LandingPad:
544 return true;
545 default:
546 return false;
547 }
548 }
549
550 /// Create a copy of 'this' instruction that is identical in all ways except
551 /// the following:
552 /// * The instruction has no parent
553 /// * The instruction has no name
554 ///
555 Instruction *clone() const;
556
557 /// Return true if the specified instruction is exactly identical to the
558 /// current one. This means that all operands match and any extra information
559 /// (e.g. load is volatile) agree.
560 bool isIdenticalTo(const Instruction *I) const;
561
562 /// This is like isIdenticalTo, except that it ignores the
563 /// SubclassOptionalData flags, which may specify conditions under which the
564 /// instruction's result is undefined.
565 bool isIdenticalToWhenDefined(const Instruction *I) const;
566
567 /// When checking for operation equivalence (using isSameOperationAs) it is
568 /// sometimes useful to ignore certain attributes.
569 enum OperationEquivalenceFlags {
570 /// Check for equivalence ignoring load/store alignment.
571 CompareIgnoringAlignment = 1<<0,
572 /// Check for equivalence treating a type and a vector of that type
573 /// as equivalent.
574 CompareUsingScalarTypes = 1<<1
575 };
576
577 /// This function determines if the specified instruction executes the same
578 /// operation as the current one. This means that the opcodes, type, operand
579 /// types and any other factors affecting the operation must be the same. This
580 /// is similar to isIdenticalTo except the operands themselves don't have to
581 /// be identical.
582 /// @returns true if the specified instruction is the same operation as
583 /// the current one.
584 /// @brief Determine if one instruction is the same operation as another.
585 bool isSameOperationAs(const Instruction *I, unsigned flags = 0) const;
586
587 /// Return true if there are any uses of this instruction in blocks other than
588 /// the specified block. Note that PHI nodes are considered to evaluate their
589 /// operands in the corresponding predecessor block.
590 bool isUsedOutsideOfBlock(const BasicBlock *BB) const;
591
592
593 /// Methods for support type inquiry through isa, cast, and dyn_cast:
594 static bool classof(const Value *V) {
595 return V->getValueID() >= Value::InstructionVal;
42
Calling 'Value::getValueID'
43
Returning from 'Value::getValueID'
63
Calling 'Value::getValueID'
64
Returning from 'Value::getValueID'
596 }
597
598 //----------------------------------------------------------------------
599 // Exported enumerations.
600 //
601 enum TermOps { // These terminate basic blocks
602#define FIRST_TERM_INST(N) TermOpsBegin = N,
603#define HANDLE_TERM_INST(N, OPC, CLASS) OPC = N,
604#define LAST_TERM_INST(N) TermOpsEnd = N+1
605#include "llvm/IR/Instruction.def"
606 };
607
608 enum BinaryOps {
609#define FIRST_BINARY_INST(N) BinaryOpsBegin = N,
610#define HANDLE_BINARY_INST(N, OPC, CLASS) OPC = N,
611#define LAST_BINARY_INST(N) BinaryOpsEnd = N+1
612#include "llvm/IR/Instruction.def"
613 };
614
615 enum MemoryOps {
616#define FIRST_MEMORY_INST(N) MemoryOpsBegin = N,
617#define HANDLE_MEMORY_INST(N, OPC, CLASS) OPC = N,
618#define LAST_MEMORY_INST(N) MemoryOpsEnd = N+1
619#include "llvm/IR/Instruction.def"
620 };
621
622 enum CastOps {
623#define FIRST_CAST_INST(N) CastOpsBegin = N,
624#define HANDLE_CAST_INST(N, OPC, CLASS) OPC = N,
625#define LAST_CAST_INST(N) CastOpsEnd = N+1
626#include "llvm/IR/Instruction.def"
627 };
628
629 enum FuncletPadOps {
630#define FIRST_FUNCLETPAD_INST(N) FuncletPadOpsBegin = N,
631#define HANDLE_FUNCLETPAD_INST(N, OPC, CLASS) OPC = N,
632#define LAST_FUNCLETPAD_INST(N) FuncletPadOpsEnd = N+1
633#include "llvm/IR/Instruction.def"
634 };
635
636 enum OtherOps {
637#define FIRST_OTHER_INST(N) OtherOpsBegin = N,
638#define HANDLE_OTHER_INST(N, OPC, CLASS) OPC = N,
639#define LAST_OTHER_INST(N) OtherOpsEnd = N+1
640#include "llvm/IR/Instruction.def"
641 };
642
643private:
644 friend class SymbolTableListTraits<Instruction>;
645
646 // Shadow Value::setValueSubclassData with a private forwarding method so that
647 // subclasses cannot accidentally use it.
648 void setValueSubclassData(unsigned short D) {
649 Value::setValueSubclassData(D);
650 }
651
652 unsigned short getSubclassDataFromValue() const {
653 return Value::getSubclassDataFromValue();
654 }
655
656 void setHasMetadataHashEntry(bool V) {
657 setValueSubclassData((getSubclassDataFromValue() & ~HasMetadataBit) |
658 (V ? HasMetadataBit : 0));
659 }
660
661 void setParent(BasicBlock *P);
662
663protected:
664 // Instruction subclasses can stick up to 15 bits of stuff into the
665 // SubclassData field of instruction with these members.
666
667 // Verify that only the low 15 bits are used.
668 void setInstructionSubclassData(unsigned short D) {
669 assert((D & HasMetadataBit) == 0 && "Out of range value put into field")(((D & HasMetadataBit) == 0 && "Out of range value put into field"
) ? static_cast<void> (0) : __assert_fail ("(D & HasMetadataBit) == 0 && \"Out of range value put into field\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/IR/Instruction.h"
, 669, __PRETTY_FUNCTION__))
;
670 setValueSubclassData((getSubclassDataFromValue() & HasMetadataBit) | D);
671 }
672
673 unsigned getSubclassDataFromInstruction() const {
674 return getSubclassDataFromValue() & ~HasMetadataBit;
675 }
676
677 Instruction(Type *Ty, unsigned iType, Use *Ops, unsigned NumOps,
678 Instruction *InsertBefore = nullptr);
679 Instruction(Type *Ty, unsigned iType, Use *Ops, unsigned NumOps,
680 BasicBlock *InsertAtEnd);
681
682private:
683 /// Create a copy of this instruction.
684 Instruction *cloneImpl() const;
685};
686
687inline void ilist_alloc_traits<Instruction>::deleteNode(Instruction *V) {
688 V->deleteValue();
689}
690
691} // end namespace llvm
692
693#endif // LLVM_IR_INSTRUCTION_H