LLVM 18.0.0git
LoopRerollPass.cpp
Go to the documentation of this file.
1//===- LoopReroll.cpp - Loop rerolling pass -------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass implements a simple loop reroller.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/ADT/APInt.h"
14#include "llvm/ADT/BitVector.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/DenseSet.h"
17#include "llvm/ADT/MapVector.h"
18#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/Statistic.h"
30#include "llvm/IR/BasicBlock.h"
31#include "llvm/IR/Constants.h"
32#include "llvm/IR/Dominators.h"
33#include "llvm/IR/InstrTypes.h"
34#include "llvm/IR/Instruction.h"
37#include "llvm/IR/Module.h"
38#include "llvm/IR/Type.h"
39#include "llvm/IR/Use.h"
40#include "llvm/IR/User.h"
41#include "llvm/IR/Value.h"
44#include "llvm/Support/Debug.h"
52#include <cassert>
53#include <cstddef>
54#include <cstdint>
55#include <iterator>
56#include <map>
57#include <utility>
58
59using namespace llvm;
60
61#define DEBUG_TYPE "loop-reroll"
62
63STATISTIC(NumRerolledLoops, "Number of rerolled loops");
64
66NumToleratedFailedMatches("reroll-num-tolerated-failed-matches", cl::init(400),
68 cl::desc("The maximum number of failures to tolerate"
69 " during fuzzy matching. (default: 400)"));
70
71// This loop re-rolling transformation aims to transform loops like this:
72//
73// int foo(int a);
74// void bar(int *x) {
75// for (int i = 0; i < 500; i += 3) {
76// foo(i);
77// foo(i+1);
78// foo(i+2);
79// }
80// }
81//
82// into a loop like this:
83//
84// void bar(int *x) {
85// for (int i = 0; i < 500; ++i)
86// foo(i);
87// }
88//
89// It does this by looking for loops that, besides the latch code, are composed
90// of isomorphic DAGs of instructions, with each DAG rooted at some increment
91// to the induction variable, and where each DAG is isomorphic to the DAG
92// rooted at the induction variable (excepting the sub-DAGs which root the
93// other induction-variable increments). In other words, we're looking for loop
94// bodies of the form:
95//
96// %iv = phi [ (preheader, ...), (body, %iv.next) ]
97// f(%iv)
98// %iv.1 = add %iv, 1 <-- a root increment
99// f(%iv.1)
100// %iv.2 = add %iv, 2 <-- a root increment
101// f(%iv.2)
102// %iv.scale_m_1 = add %iv, scale-1 <-- a root increment
103// f(%iv.scale_m_1)
104// ...
105// %iv.next = add %iv, scale
106// %cmp = icmp(%iv, ...)
107// br %cmp, header, exit
108//
109// where each f(i) is a set of instructions that, collectively, are a function
110// only of i (and other loop-invariant values).
111//
112// As a special case, we can also reroll loops like this:
113//
114// int foo(int);
115// void bar(int *x) {
116// for (int i = 0; i < 500; ++i) {
117// x[3*i] = foo(0);
118// x[3*i+1] = foo(0);
119// x[3*i+2] = foo(0);
120// }
121// }
122//
123// into this:
124//
125// void bar(int *x) {
126// for (int i = 0; i < 1500; ++i)
127// x[i] = foo(0);
128// }
129//
130// in which case, we're looking for inputs like this:
131//
132// %iv = phi [ (preheader, ...), (body, %iv.next) ]
133// %scaled.iv = mul %iv, scale
134// f(%scaled.iv)
135// %scaled.iv.1 = add %scaled.iv, 1
136// f(%scaled.iv.1)
137// %scaled.iv.2 = add %scaled.iv, 2
138// f(%scaled.iv.2)
139// %scaled.iv.scale_m_1 = add %scaled.iv, scale-1
140// f(%scaled.iv.scale_m_1)
141// ...
142// %iv.next = add %iv, 1
143// %cmp = icmp(%iv, ...)
144// br %cmp, header, exit
145
146namespace {
147
148 enum IterationLimits {
149 /// The maximum number of iterations that we'll try and reroll.
150 IL_MaxRerollIterations = 32,
151 /// The bitvector index used by loop induction variables and other
152 /// instructions that belong to all iterations.
153 IL_All,
154 IL_End
155 };
156
157 class LoopReroll {
158 public:
159 LoopReroll(AliasAnalysis *AA, LoopInfo *LI, ScalarEvolution *SE,
160 TargetLibraryInfo *TLI, DominatorTree *DT, bool PreserveLCSSA)
161 : AA(AA), LI(LI), SE(SE), TLI(TLI), DT(DT),
162 PreserveLCSSA(PreserveLCSSA) {}
163 bool runOnLoop(Loop *L);
164
165 protected:
166 AliasAnalysis *AA;
167 LoopInfo *LI;
168 ScalarEvolution *SE;
170 DominatorTree *DT;
171 bool PreserveLCSSA;
172
173 using SmallInstructionVector = SmallVector<Instruction *, 16>;
174 using SmallInstructionSet = SmallPtrSet<Instruction *, 16>;
175 using TinyInstructionVector = SmallVector<Instruction *, 1>;
176
177 // Map between induction variable and its increment
179
180 // For loop with multiple induction variables, remember the ones used only to
181 // control the loop.
182 TinyInstructionVector LoopControlIVs;
183
184 // A chain of isomorphic instructions, identified by a single-use PHI
185 // representing a reduction. Only the last value may be used outside the
186 // loop.
187 struct SimpleLoopReduction {
188 SimpleLoopReduction(Instruction *P, Loop *L) : Instructions(1, P) {
189 assert(isa<PHINode>(P) && "First reduction instruction must be a PHI");
190 add(L);
191 }
192
193 bool valid() const {
194 return Valid;
195 }
196
197 Instruction *getPHI() const {
198 assert(Valid && "Using invalid reduction");
199 return Instructions.front();
200 }
201
202 Instruction *getReducedValue() const {
203 assert(Valid && "Using invalid reduction");
204 return Instructions.back();
205 }
206
207 Instruction *get(size_t i) const {
208 assert(Valid && "Using invalid reduction");
209 return Instructions[i+1];
210 }
211
212 Instruction *operator [] (size_t i) const { return get(i); }
213
214 // The size, ignoring the initial PHI.
215 size_t size() const {
216 assert(Valid && "Using invalid reduction");
217 return Instructions.size()-1;
218 }
219
220 using iterator = SmallInstructionVector::iterator;
222
223 iterator begin() {
224 assert(Valid && "Using invalid reduction");
225 return std::next(Instructions.begin());
226 }
227
228 const_iterator begin() const {
229 assert(Valid && "Using invalid reduction");
230 return std::next(Instructions.begin());
231 }
232
233 iterator end() { return Instructions.end(); }
234 const_iterator end() const { return Instructions.end(); }
235
236 protected:
237 bool Valid = false;
238 SmallInstructionVector Instructions;
239
240 void add(Loop *L);
241 };
242
243 // The set of all reductions, and state tracking of possible reductions
244 // during loop instruction processing.
245 struct ReductionTracker {
246 using SmallReductionVector = SmallVector<SimpleLoopReduction, 16>;
247
248 // Add a new possible reduction.
249 void addSLR(SimpleLoopReduction &SLR) { PossibleReds.push_back(SLR); }
250
251 // Setup to track possible reductions corresponding to the provided
252 // rerolling scale. Only reductions with a number of non-PHI instructions
253 // that is divisible by the scale are considered. Three instructions sets
254 // are filled in:
255 // - A set of all possible instructions in eligible reductions.
256 // - A set of all PHIs in eligible reductions
257 // - A set of all reduced values (last instructions) in eligible
258 // reductions.
259 void restrictToScale(uint64_t Scale,
260 SmallInstructionSet &PossibleRedSet,
261 SmallInstructionSet &PossibleRedPHISet,
262 SmallInstructionSet &PossibleRedLastSet) {
263 PossibleRedIdx.clear();
264 PossibleRedIter.clear();
265 Reds.clear();
266
267 for (unsigned i = 0, e = PossibleReds.size(); i != e; ++i)
268 if (PossibleReds[i].size() % Scale == 0) {
269 PossibleRedLastSet.insert(PossibleReds[i].getReducedValue());
270 PossibleRedPHISet.insert(PossibleReds[i].getPHI());
271
272 PossibleRedSet.insert(PossibleReds[i].getPHI());
273 PossibleRedIdx[PossibleReds[i].getPHI()] = i;
274 for (Instruction *J : PossibleReds[i]) {
275 PossibleRedSet.insert(J);
276 PossibleRedIdx[J] = i;
277 }
278 }
279 }
280
281 // The functions below are used while processing the loop instructions.
282
283 // Are the two instructions both from reductions, and furthermore, from
284 // the same reduction?
285 bool isPairInSame(Instruction *J1, Instruction *J2) {
286 DenseMap<Instruction *, int>::iterator J1I = PossibleRedIdx.find(J1);
287 if (J1I != PossibleRedIdx.end()) {
288 DenseMap<Instruction *, int>::iterator J2I = PossibleRedIdx.find(J2);
289 if (J2I != PossibleRedIdx.end() && J1I->second == J2I->second)
290 return true;
291 }
292
293 return false;
294 }
295
296 // The two provided instructions, the first from the base iteration, and
297 // the second from iteration i, form a matched pair. If these are part of
298 // a reduction, record that fact.
299 void recordPair(Instruction *J1, Instruction *J2, unsigned i) {
300 if (PossibleRedIdx.count(J1)) {
301 assert(PossibleRedIdx.count(J2) &&
302 "Recording reduction vs. non-reduction instruction?");
303
304 PossibleRedIter[J1] = 0;
305 PossibleRedIter[J2] = i;
306
307 int Idx = PossibleRedIdx[J1];
308 assert(Idx == PossibleRedIdx[J2] &&
309 "Recording pair from different reductions?");
310 Reds.insert(Idx);
311 }
312 }
313
314 // The functions below can be called after we've finished processing all
315 // instructions in the loop, and we know which reductions were selected.
316
317 bool validateSelected();
318 void replaceSelected();
319
320 protected:
321 // The vector of all possible reductions (for any scale).
322 SmallReductionVector PossibleReds;
323
324 DenseMap<Instruction *, int> PossibleRedIdx;
325 DenseMap<Instruction *, int> PossibleRedIter;
326 DenseSet<int> Reds;
327 };
328
329 // A DAGRootSet models an induction variable being used in a rerollable
330 // loop. For example,
331 //
332 // x[i*3+0] = y1
333 // x[i*3+1] = y2
334 // x[i*3+2] = y3
335 //
336 // Base instruction -> i*3
337 // +---+----+
338 // / | \
339 // ST[y1] +1 +2 <-- Roots
340 // | |
341 // ST[y2] ST[y3]
342 //
343 // There may be multiple DAGRoots, for example:
344 //
345 // x[i*2+0] = ... (1)
346 // x[i*2+1] = ... (1)
347 // x[i*2+4] = ... (2)
348 // x[i*2+5] = ... (2)
349 // x[(i+1234)*2+5678] = ... (3)
350 // x[(i+1234)*2+5679] = ... (3)
351 //
352 // The loop will be rerolled by adding a new loop induction variable,
353 // one for the Base instruction in each DAGRootSet.
354 //
355 struct DAGRootSet {
356 Instruction *BaseInst;
357 SmallInstructionVector Roots;
358
359 // The instructions between IV and BaseInst (but not including BaseInst).
360 SmallInstructionSet SubsumedInsts;
361 };
362
363 // The set of all DAG roots, and state tracking of all roots
364 // for a particular induction variable.
365 struct DAGRootTracker {
366 DAGRootTracker(LoopReroll *Parent, Loop *L, Instruction *IV,
369 bool PreserveLCSSA,
371 TinyInstructionVector LoopCtrlIVs)
372 : Parent(Parent), L(L), SE(SE), AA(AA), TLI(TLI), DT(DT), LI(LI),
373 PreserveLCSSA(PreserveLCSSA), IV(IV), IVToIncMap(IncrMap),
374 LoopControlIVs(LoopCtrlIVs) {}
375
376 /// Stage 1: Find all the DAG roots for the induction variable.
377 bool findRoots();
378
379 /// Stage 2: Validate if the found roots are valid.
380 bool validate(ReductionTracker &Reductions);
381
382 /// Stage 3: Assuming validate() returned true, perform the
383 /// replacement.
384 /// @param BackedgeTakenCount The backedge-taken count of L.
385 void replace(const SCEV *BackedgeTakenCount);
386
387 protected:
389
390 void findRootsRecursive(Instruction *IVU,
391 SmallInstructionSet SubsumedInsts);
392 bool findRootsBase(Instruction *IVU, SmallInstructionSet SubsumedInsts);
393 bool collectPossibleRoots(Instruction *Base,
394 std::map<int64_t,Instruction*> &Roots);
395 bool validateRootSet(DAGRootSet &DRS);
396
397 bool collectUsedInstructions(SmallInstructionSet &PossibleRedSet);
398 void collectInLoopUserSet(const SmallInstructionVector &Roots,
399 const SmallInstructionSet &Exclude,
400 const SmallInstructionSet &Final,
402 void collectInLoopUserSet(Instruction *Root,
403 const SmallInstructionSet &Exclude,
404 const SmallInstructionSet &Final,
406
407 UsesTy::iterator nextInstr(int Val, UsesTy &In,
408 const SmallInstructionSet &Exclude,
409 UsesTy::iterator *StartI=nullptr);
410 bool isBaseInst(Instruction *I);
411 bool isRootInst(Instruction *I);
412 bool instrDependsOn(Instruction *I,
413 UsesTy::iterator Start,
415 void replaceIV(DAGRootSet &DRS, const SCEV *Start, const SCEV *IncrExpr);
416
417 LoopReroll *Parent;
418
419 // Members of Parent, replicated here for brevity.
420 Loop *L;
421 ScalarEvolution *SE;
422 AliasAnalysis *AA;
424 DominatorTree *DT;
425 LoopInfo *LI;
426 bool PreserveLCSSA;
427
428 // The loop induction variable.
429 Instruction *IV;
430
431 // Loop step amount.
432 int64_t Inc;
433
434 // Loop reroll count; if Inc == 1, this records the scaling applied
435 // to the indvar: a[i*2+0] = ...; a[i*2+1] = ... ;
436 // If Inc is not 1, Scale = Inc.
437 uint64_t Scale;
438
439 // The roots themselves.
441
442 // All increment instructions for IV.
443 SmallInstructionVector LoopIncs;
444
445 // Map of all instructions in the loop (in order) to the iterations
446 // they are used in (or specially, IL_All for instructions
447 // used in the loop increment mechanism).
448 UsesTy Uses;
449
450 // Map between induction variable and its increment
452
453 TinyInstructionVector LoopControlIVs;
454 };
455
456 // Check if it is a compare-like instruction whose user is a branch
457 bool isCompareUsedByBranch(Instruction *I) {
458 auto *TI = I->getParent()->getTerminator();
459 if (!isa<BranchInst>(TI) || !isa<CmpInst>(I))
460 return false;
461 return I->hasOneUse() && TI->getOperand(0) == I;
462 };
463
464 bool isLoopControlIV(Loop *L, Instruction *IV);
465 void collectPossibleIVs(Loop *L, SmallInstructionVector &PossibleIVs);
466 void collectPossibleReductions(Loop *L,
467 ReductionTracker &Reductions);
468 bool reroll(Instruction *IV, Loop *L, BasicBlock *Header,
469 const SCEV *BackedgeTakenCount, ReductionTracker &Reductions);
470 };
471
472} // end anonymous namespace
473
474// Returns true if the provided instruction is used outside the given loop.
475// This operates like Instruction::isUsedOutsideOfBlock, but considers PHIs in
476// non-loop blocks to be outside the loop.
478 for (User *U : I->users()) {
479 if (!L->contains(cast<Instruction>(U)))
480 return true;
481 }
482 return false;
483}
484
485// Check if an IV is only used to control the loop. There are two cases:
486// 1. It only has one use which is loop increment, and the increment is only
487// used by comparison and the PHI (could has sext with nsw in between), and the
488// comparison is only used by branch.
489// 2. It is used by loop increment and the comparison, the loop increment is
490// only used by the PHI, and the comparison is used only by the branch.
491bool LoopReroll::isLoopControlIV(Loop *L, Instruction *IV) {
492 unsigned IVUses = IV->getNumUses();
493 if (IVUses != 2 && IVUses != 1)
494 return false;
495
496 for (auto *User : IV->users()) {
497 int32_t IncOrCmpUses = User->getNumUses();
498 bool IsCompInst = isCompareUsedByBranch(cast<Instruction>(User));
499
500 // User can only have one or two uses.
501 if (IncOrCmpUses != 2 && IncOrCmpUses != 1)
502 return false;
503
504 // Case 1
505 if (IVUses == 1) {
506 // The only user must be the loop increment.
507 // The loop increment must have two uses.
508 if (IsCompInst || IncOrCmpUses != 2)
509 return false;
510 }
511
512 // Case 2
513 if (IVUses == 2 && IncOrCmpUses != 1)
514 return false;
515
516 // The users of the IV must be a binary operation or a comparison
517 if (auto *BO = dyn_cast<BinaryOperator>(User)) {
518 if (BO->getOpcode() == Instruction::Add) {
519 // Loop Increment
520 // User of Loop Increment should be either PHI or CMP
521 for (auto *UU : User->users()) {
522 if (PHINode *PN = dyn_cast<PHINode>(UU)) {
523 if (PN != IV)
524 return false;
525 }
526 // Must be a CMP or an ext (of a value with nsw) then CMP
527 else {
528 auto *UUser = cast<Instruction>(UU);
529 // Skip SExt if we are extending an nsw value
530 // TODO: Allow ZExt too
531 if (BO->hasNoSignedWrap() && UUser->hasOneUse() &&
532 isa<SExtInst>(UUser))
533 UUser = cast<Instruction>(*(UUser->user_begin()));
534 if (!isCompareUsedByBranch(UUser))
535 return false;
536 }
537 }
538 } else
539 return false;
540 // Compare : can only have one use, and must be branch
541 } else if (!IsCompInst)
542 return false;
543 }
544 return true;
545}
546
547// Collect the list of loop induction variables with respect to which it might
548// be possible to reroll the loop.
549void LoopReroll::collectPossibleIVs(Loop *L,
550 SmallInstructionVector &PossibleIVs) {
551 for (Instruction &IV : L->getHeader()->phis()) {
552 if (!IV.getType()->isIntegerTy() && !IV.getType()->isPointerTy())
553 continue;
554
555 if (const SCEVAddRecExpr *PHISCEV =
556 dyn_cast<SCEVAddRecExpr>(SE->getSCEV(&IV))) {
557 if (PHISCEV->getLoop() != L)
558 continue;
559 if (!PHISCEV->isAffine())
560 continue;
561 const auto *IncSCEV = dyn_cast<SCEVConstant>(PHISCEV->getStepRecurrence(*SE));
562 if (IncSCEV) {
563 IVToIncMap[&IV] = IncSCEV->getValue()->getSExtValue();
564 LLVM_DEBUG(dbgs() << "LRR: Possible IV: " << IV << " = " << *PHISCEV
565 << "\n");
566
567 if (isLoopControlIV(L, &IV)) {
568 LoopControlIVs.push_back(&IV);
569 LLVM_DEBUG(dbgs() << "LRR: Loop control only IV: " << IV
570 << " = " << *PHISCEV << "\n");
571 } else
572 PossibleIVs.push_back(&IV);
573 }
574 }
575 }
576}
577
578// Add the remainder of the reduction-variable chain to the instruction vector
579// (the initial PHINode has already been added). If successful, the object is
580// marked as valid.
581void LoopReroll::SimpleLoopReduction::add(Loop *L) {
582 assert(!Valid && "Cannot add to an already-valid chain");
583
584 // The reduction variable must be a chain of single-use instructions
585 // (including the PHI), except for the last value (which is used by the PHI
586 // and also outside the loop).
587 Instruction *C = Instructions.front();
588 if (C->user_empty())
589 return;
590
591 do {
592 C = cast<Instruction>(*C->user_begin());
593 if (C->hasOneUse()) {
594 if (!C->isBinaryOp())
595 return;
596
597 if (!(isa<PHINode>(Instructions.back()) ||
598 C->isSameOperationAs(Instructions.back())))
599 return;
600
601 Instructions.push_back(C);
602 }
603 } while (C->hasOneUse());
604
605 if (Instructions.size() < 2 ||
606 !C->isSameOperationAs(Instructions.back()) ||
607 C->use_empty())
608 return;
609
610 // C is now the (potential) last instruction in the reduction chain.
611 for (User *U : C->users()) {
612 // The only in-loop user can be the initial PHI.
613 if (L->contains(cast<Instruction>(U)))
614 if (cast<Instruction>(U) != Instructions.front())
615 return;
616 }
617
618 Instructions.push_back(C);
619 Valid = true;
620}
621
622// Collect the vector of possible reduction variables.
623void LoopReroll::collectPossibleReductions(Loop *L,
624 ReductionTracker &Reductions) {
625 BasicBlock *Header = L->getHeader();
626 for (BasicBlock::iterator I = Header->begin(),
627 IE = Header->getFirstInsertionPt(); I != IE; ++I) {
628 if (!isa<PHINode>(I))
629 continue;
630 if (!I->getType()->isSingleValueType())
631 continue;
632
633 SimpleLoopReduction SLR(&*I, L);
634 if (!SLR.valid())
635 continue;
636
637 LLVM_DEBUG(dbgs() << "LRR: Possible reduction: " << *I << " (with "
638 << SLR.size() << " chained instructions)\n");
639 Reductions.addSLR(SLR);
640 }
641}
642
643// Collect the set of all users of the provided root instruction. This set of
644// users contains not only the direct users of the root instruction, but also
645// all users of those users, and so on. There are two exceptions:
646//
647// 1. Instructions in the set of excluded instructions are never added to the
648// use set (even if they are users). This is used, for example, to exclude
649// including root increments in the use set of the primary IV.
650//
651// 2. Instructions in the set of final instructions are added to the use set
652// if they are users, but their users are not added. This is used, for
653// example, to prevent a reduction update from forcing all later reduction
654// updates into the use set.
655void LoopReroll::DAGRootTracker::collectInLoopUserSet(
656 Instruction *Root, const SmallInstructionSet &Exclude,
657 const SmallInstructionSet &Final,
659 SmallInstructionVector Queue(1, Root);
660 while (!Queue.empty()) {
661 Instruction *I = Queue.pop_back_val();
662 if (!Users.insert(I).second)
663 continue;
664
665 if (!Final.count(I))
666 for (Use &U : I->uses()) {
667 Instruction *User = cast<Instruction>(U.getUser());
668 if (PHINode *PN = dyn_cast<PHINode>(User)) {
669 // Ignore "wrap-around" uses to PHIs of this loop's header.
670 if (PN->getIncomingBlock(U) == L->getHeader())
671 continue;
672 }
673
674 if (L->contains(User) && !Exclude.count(User)) {
675 Queue.push_back(User);
676 }
677 }
678
679 // We also want to collect single-user "feeder" values.
680 for (Use &U : I->operands()) {
681 if (Instruction *Op = dyn_cast<Instruction>(U))
682 if (Op->hasOneUse() && L->contains(Op) && !Exclude.count(Op) &&
683 !Final.count(Op))
684 Queue.push_back(Op);
685 }
686 }
687}
688
689// Collect all of the users of all of the provided root instructions (combined
690// into a single set).
691void LoopReroll::DAGRootTracker::collectInLoopUserSet(
692 const SmallInstructionVector &Roots,
693 const SmallInstructionSet &Exclude,
694 const SmallInstructionSet &Final,
696 for (Instruction *Root : Roots)
697 collectInLoopUserSet(Root, Exclude, Final, Users);
698}
699
701 if (LoadInst *LI = dyn_cast<LoadInst>(I))
702 return LI->isUnordered();
703 if (StoreInst *SI = dyn_cast<StoreInst>(I))
704 return SI->isUnordered();
705 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I))
706 return !MI->isVolatile();
707 return false;
708}
709
710/// Return true if IVU is a "simple" arithmetic operation.
711/// This is used for narrowing the search space for DAGRoots; only arithmetic
712/// and GEPs can be part of a DAGRoot.
713static bool isSimpleArithmeticOp(User *IVU) {
714 if (Instruction *I = dyn_cast<Instruction>(IVU)) {
715 switch (I->getOpcode()) {
716 default: return false;
717 case Instruction::Add:
718 case Instruction::Sub:
719 case Instruction::Mul:
720 case Instruction::Shl:
721 case Instruction::AShr:
722 case Instruction::LShr:
723 case Instruction::GetElementPtr:
724 case Instruction::Trunc:
725 case Instruction::ZExt:
726 case Instruction::SExt:
727 return true;
728 }
729 }
730 return false;
731}
732
734 BinaryOperator *BO = dyn_cast<BinaryOperator>(U);
735
736 if ((BO && BO->getOpcode() != Instruction::Add) ||
737 (!BO && !isa<GetElementPtrInst>(U)))
738 return false;
739
740 for (auto *UU : U->users()) {
741 PHINode *PN = dyn_cast<PHINode>(UU);
742 if (PN && PN == IV)
743 return true;
744 }
745 return false;
746}
747
748bool LoopReroll::DAGRootTracker::
749collectPossibleRoots(Instruction *Base, std::map<int64_t,Instruction*> &Roots) {
750 SmallInstructionVector BaseUsers;
751
752 for (auto *I : Base->users()) {
753 ConstantInt *CI = nullptr;
754
755 if (isLoopIncrement(I, IV)) {
756 LoopIncs.push_back(cast<Instruction>(I));
757 continue;
758 }
759
760 // The root nodes must be either GEPs, ORs or ADDs.
761 if (auto *BO = dyn_cast<BinaryOperator>(I)) {
762 if (BO->getOpcode() == Instruction::Add ||
763 BO->getOpcode() == Instruction::Or)
764 CI = dyn_cast<ConstantInt>(BO->getOperand(1));
765 } else if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
766 Value *LastOperand = GEP->getOperand(GEP->getNumOperands()-1);
767 CI = dyn_cast<ConstantInt>(LastOperand);
768 }
769
770 if (!CI) {
771 if (Instruction *II = dyn_cast<Instruction>(I)) {
772 BaseUsers.push_back(II);
773 continue;
774 } else {
775 LLVM_DEBUG(dbgs() << "LRR: Aborting due to non-instruction: " << *I
776 << "\n");
777 return false;
778 }
779 }
780
781 int64_t V = std::abs(CI->getValue().getSExtValue());
782 if (Roots.find(V) != Roots.end())
783 // No duplicates, please.
784 return false;
785
786 Roots[V] = cast<Instruction>(I);
787 }
788
789 // Make sure we have at least two roots.
790 if (Roots.empty() || (Roots.size() == 1 && BaseUsers.empty()))
791 return false;
792
793 // If we found non-loop-inc, non-root users of Base, assume they are
794 // for the zeroth root index. This is because "add %a, 0" gets optimized
795 // away.
796 if (BaseUsers.size()) {
797 if (Roots.find(0) != Roots.end()) {
798 LLVM_DEBUG(dbgs() << "LRR: Multiple roots found for base - aborting!\n");
799 return false;
800 }
801 Roots[0] = Base;
802 }
803
804 // Calculate the number of users of the base, or lowest indexed, iteration.
805 unsigned NumBaseUses = BaseUsers.size();
806 if (NumBaseUses == 0)
807 NumBaseUses = Roots.begin()->second->getNumUses();
808
809 // Check that every node has the same number of users.
810 for (auto &KV : Roots) {
811 if (KV.first == 0)
812 continue;
813 if (!KV.second->hasNUses(NumBaseUses)) {
814 LLVM_DEBUG(dbgs() << "LRR: Aborting - Root and Base #users not the same: "
815 << "#Base=" << NumBaseUses
816 << ", #Root=" << KV.second->getNumUses() << "\n");
817 return false;
818 }
819 }
820
821 return true;
822}
823
824void LoopReroll::DAGRootTracker::
825findRootsRecursive(Instruction *I, SmallInstructionSet SubsumedInsts) {
826 // Does the user look like it could be part of a root set?
827 // All its users must be simple arithmetic ops.
828 if (I->hasNUsesOrMore(IL_MaxRerollIterations + 1))
829 return;
830
831 if (I != IV && findRootsBase(I, SubsumedInsts))
832 return;
833
834 SubsumedInsts.insert(I);
835
836 for (User *V : I->users()) {
837 Instruction *I = cast<Instruction>(V);
838 if (is_contained(LoopIncs, I))
839 continue;
840
842 continue;
843
844 // The recursive call makes a copy of SubsumedInsts.
845 findRootsRecursive(I, SubsumedInsts);
846 }
847}
848
849bool LoopReroll::DAGRootTracker::validateRootSet(DAGRootSet &DRS) {
850 if (DRS.Roots.empty())
851 return false;
852
853 // If the value of the base instruction is used outside the loop, we cannot
854 // reroll the loop. Check for other root instructions is unnecessary because
855 // they don't match any base instructions if their values are used outside.
856 if (hasUsesOutsideLoop(DRS.BaseInst, L))
857 return false;
858
859 // Consider a DAGRootSet with N-1 roots (so N different values including
860 // BaseInst).
861 // Define d = Roots[0] - BaseInst, which should be the same as
862 // Roots[I] - Roots[I-1] for all I in [1..N).
863 // Define D = BaseInst@J - BaseInst@J-1, where "@J" means the value at the
864 // loop iteration J.
865 //
866 // Now, For the loop iterations to be consecutive:
867 // D = d * N
868 const auto *ADR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(DRS.BaseInst));
869 if (!ADR)
870 return false;
871
872 // Check that the first root is evenly spaced.
873 unsigned N = DRS.Roots.size() + 1;
874 const SCEV *StepSCEV = SE->getMinusSCEV(SE->getSCEV(DRS.Roots[0]), ADR);
875 if (isa<SCEVCouldNotCompute>(StepSCEV) || StepSCEV->getType()->isPointerTy())
876 return false;
877 const SCEV *ScaleSCEV = SE->getConstant(StepSCEV->getType(), N);
878 if (ADR->getStepRecurrence(*SE) != SE->getMulExpr(StepSCEV, ScaleSCEV))
879 return false;
880
881 // Check that the remainling roots are evenly spaced.
882 for (unsigned i = 1; i < N - 1; ++i) {
883 const SCEV *NewStepSCEV = SE->getMinusSCEV(SE->getSCEV(DRS.Roots[i]),
884 SE->getSCEV(DRS.Roots[i-1]));
885 if (NewStepSCEV != StepSCEV)
886 return false;
887 }
888
889 return true;
890}
891
892bool LoopReroll::DAGRootTracker::
893findRootsBase(Instruction *IVU, SmallInstructionSet SubsumedInsts) {
894 // The base of a RootSet must be an AddRec, so it can be erased.
895 const auto *IVU_ADR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(IVU));
896 if (!IVU_ADR || IVU_ADR->getLoop() != L)
897 return false;
898
899 std::map<int64_t, Instruction*> V;
900 if (!collectPossibleRoots(IVU, V))
901 return false;
902
903 // If we didn't get a root for index zero, then IVU must be
904 // subsumed.
905 if (V.find(0) == V.end())
906 SubsumedInsts.insert(IVU);
907
908 // Partition the vector into monotonically increasing indexes.
909 DAGRootSet DRS;
910 DRS.BaseInst = nullptr;
911
912 SmallVector<DAGRootSet, 16> PotentialRootSets;
913
914 for (auto &KV : V) {
915 if (!DRS.BaseInst) {
916 DRS.BaseInst = KV.second;
917 DRS.SubsumedInsts = SubsumedInsts;
918 } else if (DRS.Roots.empty()) {
919 DRS.Roots.push_back(KV.second);
920 } else if (V.find(KV.first - 1) != V.end()) {
921 DRS.Roots.push_back(KV.second);
922 } else {
923 // Linear sequence terminated.
924 if (!validateRootSet(DRS))
925 return false;
926
927 // Construct a new DAGRootSet with the next sequence.
928 PotentialRootSets.push_back(DRS);
929 DRS.BaseInst = KV.second;
930 DRS.Roots.clear();
931 }
932 }
933
934 if (!validateRootSet(DRS))
935 return false;
936
937 PotentialRootSets.push_back(DRS);
938
939 RootSets.append(PotentialRootSets.begin(), PotentialRootSets.end());
940
941 return true;
942}
943
944bool LoopReroll::DAGRootTracker::findRoots() {
945 Inc = IVToIncMap[IV];
946
947 assert(RootSets.empty() && "Unclean state!");
948 if (std::abs(Inc) == 1) {
949 for (auto *IVU : IV->users()) {
950 if (isLoopIncrement(IVU, IV))
951 LoopIncs.push_back(cast<Instruction>(IVU));
952 }
953 findRootsRecursive(IV, SmallInstructionSet());
954 LoopIncs.push_back(IV);
955 } else {
956 if (!findRootsBase(IV, SmallInstructionSet()))
957 return false;
958 }
959
960 // Ensure all sets have the same size.
961 if (RootSets.empty()) {
962 LLVM_DEBUG(dbgs() << "LRR: Aborting because no root sets found!\n");
963 return false;
964 }
965 for (auto &V : RootSets) {
966 if (V.Roots.empty() || V.Roots.size() != RootSets[0].Roots.size()) {
968 dbgs()
969 << "LRR: Aborting because not all root sets have the same size\n");
970 return false;
971 }
972 }
973
974 Scale = RootSets[0].Roots.size() + 1;
975
976 if (Scale > IL_MaxRerollIterations) {
977 LLVM_DEBUG(dbgs() << "LRR: Aborting - too many iterations found. "
978 << "#Found=" << Scale
979 << ", #Max=" << IL_MaxRerollIterations << "\n");
980 return false;
981 }
982
983 LLVM_DEBUG(dbgs() << "LRR: Successfully found roots: Scale=" << Scale
984 << "\n");
985
986 return true;
987}
988
989bool LoopReroll::DAGRootTracker::collectUsedInstructions(SmallInstructionSet &PossibleRedSet) {
990 // Populate the MapVector with all instructions in the block, in order first,
991 // so we can iterate over the contents later in perfect order.
992 for (auto &I : *L->getHeader()) {
993 Uses[&I].resize(IL_End);
994 }
995
996 SmallInstructionSet Exclude;
997 for (auto &DRS : RootSets) {
998 Exclude.insert(DRS.Roots.begin(), DRS.Roots.end());
999 Exclude.insert(DRS.SubsumedInsts.begin(), DRS.SubsumedInsts.end());
1000 Exclude.insert(DRS.BaseInst);
1001 }
1002 Exclude.insert(LoopIncs.begin(), LoopIncs.end());
1003
1004 for (auto &DRS : RootSets) {
1006 collectInLoopUserSet(DRS.BaseInst, Exclude, PossibleRedSet, VBase);
1007 for (auto *I : VBase) {
1008 Uses[I].set(0);
1009 }
1010
1011 unsigned Idx = 1;
1012 for (auto *Root : DRS.Roots) {
1014 collectInLoopUserSet(Root, Exclude, PossibleRedSet, V);
1015
1016 // While we're here, check the use sets are the same size.
1017 if (V.size() != VBase.size()) {
1018 LLVM_DEBUG(dbgs() << "LRR: Aborting - use sets are different sizes\n");
1019 return false;
1020 }
1021
1022 for (auto *I : V) {
1023 Uses[I].set(Idx);
1024 }
1025 ++Idx;
1026 }
1027
1028 // Make sure our subsumed instructions are remembered too.
1029 for (auto *I : DRS.SubsumedInsts) {
1030 Uses[I].set(IL_All);
1031 }
1032 }
1033
1034 // Make sure the loop increments are also accounted for.
1035
1036 Exclude.clear();
1037 for (auto &DRS : RootSets) {
1038 Exclude.insert(DRS.Roots.begin(), DRS.Roots.end());
1039 Exclude.insert(DRS.SubsumedInsts.begin(), DRS.SubsumedInsts.end());
1040 Exclude.insert(DRS.BaseInst);
1041 }
1042
1044 collectInLoopUserSet(LoopIncs, Exclude, PossibleRedSet, V);
1045 for (auto *I : V) {
1046 if (I->mayHaveSideEffects()) {
1047 LLVM_DEBUG(dbgs() << "LRR: Aborting - "
1048 << "An instruction which does not belong to any root "
1049 << "sets must not have side effects: " << *I);
1050 return false;
1051 }
1052 Uses[I].set(IL_All);
1053 }
1054
1055 return true;
1056}
1057
1058/// Get the next instruction in "In" that is a member of set Val.
1059/// Start searching from StartI, and do not return anything in Exclude.
1060/// If StartI is not given, start from In.begin().
1062LoopReroll::DAGRootTracker::nextInstr(int Val, UsesTy &In,
1063 const SmallInstructionSet &Exclude,
1064 UsesTy::iterator *StartI) {
1065 UsesTy::iterator I = StartI ? *StartI : In.begin();
1066 while (I != In.end() && (I->second.test(Val) == 0 ||
1067 Exclude.contains(I->first)))
1068 ++I;
1069 return I;
1070}
1071
1072bool LoopReroll::DAGRootTracker::isBaseInst(Instruction *I) {
1073 for (auto &DRS : RootSets) {
1074 if (DRS.BaseInst == I)
1075 return true;
1076 }
1077 return false;
1078}
1079
1080bool LoopReroll::DAGRootTracker::isRootInst(Instruction *I) {
1081 for (auto &DRS : RootSets) {
1082 if (is_contained(DRS.Roots, I))
1083 return true;
1084 }
1085 return false;
1086}
1087
1088/// Return true if instruction I depends on any instruction between
1089/// Start and End.
1090bool LoopReroll::DAGRootTracker::instrDependsOn(Instruction *I,
1091 UsesTy::iterator Start,
1092 UsesTy::iterator End) {
1093 for (auto *U : I->users()) {
1094 for (auto It = Start; It != End; ++It)
1095 if (U == It->first)
1096 return true;
1097 }
1098 return false;
1099}
1100
1101static bool isIgnorableInst(const Instruction *I) {
1102 if (isa<DbgInfoIntrinsic>(I))
1103 return true;
1104 const IntrinsicInst* II = dyn_cast<IntrinsicInst>(I);
1105 if (!II)
1106 return false;
1107 switch (II->getIntrinsicID()) {
1108 default:
1109 return false;
1110 case Intrinsic::annotation:
1111 case Intrinsic::ptr_annotation:
1112 case Intrinsic::var_annotation:
1113 // TODO: the following intrinsics may also be allowed:
1114 // lifetime_start, lifetime_end, invariant_start, invariant_end
1115 return true;
1116 }
1117 return false;
1118}
1119
1120bool LoopReroll::DAGRootTracker::validate(ReductionTracker &Reductions) {
1121 // We now need to check for equivalence of the use graph of each root with
1122 // that of the primary induction variable (excluding the roots). Our goal
1123 // here is not to solve the full graph isomorphism problem, but rather to
1124 // catch common cases without a lot of work. As a result, we will assume
1125 // that the relative order of the instructions in each unrolled iteration
1126 // is the same (although we will not make an assumption about how the
1127 // different iterations are intermixed). Note that while the order must be
1128 // the same, the instructions may not be in the same basic block.
1129
1130 // An array of just the possible reductions for this scale factor. When we
1131 // collect the set of all users of some root instructions, these reduction
1132 // instructions are treated as 'final' (their uses are not considered).
1133 // This is important because we don't want the root use set to search down
1134 // the reduction chain.
1135 SmallInstructionSet PossibleRedSet;
1136 SmallInstructionSet PossibleRedLastSet;
1137 SmallInstructionSet PossibleRedPHISet;
1138 Reductions.restrictToScale(Scale, PossibleRedSet,
1139 PossibleRedPHISet, PossibleRedLastSet);
1140
1141 // Populate "Uses" with where each instruction is used.
1142 if (!collectUsedInstructions(PossibleRedSet))
1143 return false;
1144
1145 // Make sure we mark the reduction PHIs as used in all iterations.
1146 for (auto *I : PossibleRedPHISet) {
1147 Uses[I].set(IL_All);
1148 }
1149
1150 // Make sure we mark loop-control-only PHIs as used in all iterations. See
1151 // comment above LoopReroll::isLoopControlIV for more information.
1152 BasicBlock *Header = L->getHeader();
1153 for (Instruction *LoopControlIV : LoopControlIVs) {
1154 for (auto *U : LoopControlIV->users()) {
1155 Instruction *IVUser = dyn_cast<Instruction>(U);
1156 // IVUser could be loop increment or compare
1157 Uses[IVUser].set(IL_All);
1158 for (auto *UU : IVUser->users()) {
1159 Instruction *UUser = dyn_cast<Instruction>(UU);
1160 // UUser could be compare, PHI or branch
1161 Uses[UUser].set(IL_All);
1162 // Skip SExt
1163 if (isa<SExtInst>(UUser)) {
1164 UUser = dyn_cast<Instruction>(*(UUser->user_begin()));
1165 Uses[UUser].set(IL_All);
1166 }
1167 // Is UUser a compare instruction?
1168 if (UU->hasOneUse()) {
1169 Instruction *BI = dyn_cast<BranchInst>(*UUser->user_begin());
1170 if (BI == cast<BranchInst>(Header->getTerminator()))
1171 Uses[BI].set(IL_All);
1172 }
1173 }
1174 }
1175 }
1176
1177 // Make sure all instructions in the loop are in one and only one
1178 // set.
1179 for (auto &KV : Uses) {
1180 if (KV.second.count() != 1 && !isIgnorableInst(KV.first)) {
1181 LLVM_DEBUG(
1182 dbgs() << "LRR: Aborting - instruction is not used in 1 iteration: "
1183 << *KV.first << " (#uses=" << KV.second.count() << ")\n");
1184 return false;
1185 }
1186 }
1187
1188 LLVM_DEBUG(for (auto &KV
1189 : Uses) {
1190 dbgs() << "LRR: " << KV.second.find_first() << "\t" << *KV.first << "\n";
1191 });
1192
1193 BatchAAResults BatchAA(*AA);
1194 for (unsigned Iter = 1; Iter < Scale; ++Iter) {
1195 // In addition to regular aliasing information, we need to look for
1196 // instructions from later (future) iterations that have side effects
1197 // preventing us from reordering them past other instructions with side
1198 // effects.
1199 bool FutureSideEffects = false;
1200 AliasSetTracker AST(BatchAA);
1201 // The map between instructions in f(%iv.(i+1)) and f(%iv).
1203
1204 // Compare iteration Iter to the base.
1205 SmallInstructionSet Visited;
1206 auto BaseIt = nextInstr(0, Uses, Visited);
1207 auto RootIt = nextInstr(Iter, Uses, Visited);
1208 auto LastRootIt = Uses.begin();
1209
1210 while (BaseIt != Uses.end() && RootIt != Uses.end()) {
1211 Instruction *BaseInst = BaseIt->first;
1212 Instruction *RootInst = RootIt->first;
1213
1214 // Skip over the IV or root instructions; only match their users.
1215 bool Continue = false;
1216 if (isBaseInst(BaseInst)) {
1217 Visited.insert(BaseInst);
1218 BaseIt = nextInstr(0, Uses, Visited);
1219 Continue = true;
1220 }
1221 if (isRootInst(RootInst)) {
1222 LastRootIt = RootIt;
1223 Visited.insert(RootInst);
1224 RootIt = nextInstr(Iter, Uses, Visited);
1225 Continue = true;
1226 }
1227 if (Continue) continue;
1228
1229 if (!BaseInst->isSameOperationAs(RootInst)) {
1230 // Last chance saloon. We don't try and solve the full isomorphism
1231 // problem, but try and at least catch the case where two instructions
1232 // *of different types* are round the wrong way. We won't be able to
1233 // efficiently tell, given two ADD instructions, which way around we
1234 // should match them, but given an ADD and a SUB, we can at least infer
1235 // which one is which.
1236 //
1237 // This should allow us to deal with a greater subset of the isomorphism
1238 // problem. It does however change a linear algorithm into a quadratic
1239 // one, so limit the number of probes we do.
1240 auto TryIt = RootIt;
1241 unsigned N = NumToleratedFailedMatches;
1242 while (TryIt != Uses.end() &&
1243 !BaseInst->isSameOperationAs(TryIt->first) &&
1244 N--) {
1245 ++TryIt;
1246 TryIt = nextInstr(Iter, Uses, Visited, &TryIt);
1247 }
1248
1249 if (TryIt == Uses.end() || TryIt == RootIt ||
1250 instrDependsOn(TryIt->first, RootIt, TryIt)) {
1251 LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at "
1252 << *BaseInst << " vs. " << *RootInst << "\n");
1253 return false;
1254 }
1255
1256 RootIt = TryIt;
1257 RootInst = TryIt->first;
1258 }
1259
1260 // All instructions between the last root and this root
1261 // may belong to some other iteration. If they belong to a
1262 // future iteration, then they're dangerous to alias with.
1263 //
1264 // Note that because we allow a limited amount of flexibility in the order
1265 // that we visit nodes, LastRootIt might be *before* RootIt, in which
1266 // case we've already checked this set of instructions so we shouldn't
1267 // do anything.
1268 for (; LastRootIt < RootIt; ++LastRootIt) {
1269 Instruction *I = LastRootIt->first;
1270 if (LastRootIt->second.find_first() < (int)Iter)
1271 continue;
1272 if (I->mayWriteToMemory())
1273 AST.add(I);
1274 // Note: This is specifically guarded by a check on isa<PHINode>,
1275 // which while a valid (somewhat arbitrary) micro-optimization, is
1276 // needed because otherwise isSafeToSpeculativelyExecute returns
1277 // false on PHI nodes.
1278 if (!isa<PHINode>(I) && !isUnorderedLoadStore(I) &&
1280 // Intervening instructions cause side effects.
1281 FutureSideEffects = true;
1282 }
1283
1284 // Make sure that this instruction, which is in the use set of this
1285 // root instruction, does not also belong to the base set or the set of
1286 // some other root instruction.
1287 if (RootIt->second.count() > 1) {
1288 LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst
1289 << " vs. " << *RootInst << " (prev. case overlap)\n");
1290 return false;
1291 }
1292
1293 // Make sure that we don't alias with any instruction in the alias set
1294 // tracker. If we do, then we depend on a future iteration, and we
1295 // can't reroll.
1296 if (RootInst->mayReadFromMemory()) {
1297 for (auto &K : AST) {
1298 if (isModOrRefSet(K.aliasesUnknownInst(RootInst, BatchAA))) {
1299 LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at "
1300 << *BaseInst << " vs. " << *RootInst
1301 << " (depends on future store)\n");
1302 return false;
1303 }
1304 }
1305 }
1306
1307 // If we've past an instruction from a future iteration that may have
1308 // side effects, and this instruction might also, then we can't reorder
1309 // them, and this matching fails. As an exception, we allow the alias
1310 // set tracker to handle regular (unordered) load/store dependencies.
1311 if (FutureSideEffects && ((!isUnorderedLoadStore(BaseInst) &&
1312 !isSafeToSpeculativelyExecute(BaseInst)) ||
1313 (!isUnorderedLoadStore(RootInst) &&
1314 !isSafeToSpeculativelyExecute(RootInst)))) {
1315 LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst
1316 << " vs. " << *RootInst
1317 << " (side effects prevent reordering)\n");
1318 return false;
1319 }
1320
1321 // For instructions that are part of a reduction, if the operation is
1322 // associative, then don't bother matching the operands (because we
1323 // already know that the instructions are isomorphic, and the order
1324 // within the iteration does not matter). For non-associative reductions,
1325 // we do need to match the operands, because we need to reject
1326 // out-of-order instructions within an iteration!
1327 // For example (assume floating-point addition), we need to reject this:
1328 // x += a[i]; x += b[i];
1329 // x += a[i+1]; x += b[i+1];
1330 // x += b[i+2]; x += a[i+2];
1331 bool InReduction = Reductions.isPairInSame(BaseInst, RootInst);
1332
1333 if (!(InReduction && BaseInst->isAssociative())) {
1334 bool Swapped = false, SomeOpMatched = false;
1335 for (unsigned j = 0; j < BaseInst->getNumOperands(); ++j) {
1336 Value *Op2 = RootInst->getOperand(j);
1337
1338 // If this is part of a reduction (and the operation is not
1339 // associatve), then we match all operands, but not those that are
1340 // part of the reduction.
1341 if (InReduction)
1342 if (Instruction *Op2I = dyn_cast<Instruction>(Op2))
1343 if (Reductions.isPairInSame(RootInst, Op2I))
1344 continue;
1345
1346 DenseMap<Value *, Value *>::iterator BMI = BaseMap.find(Op2);
1347 if (BMI != BaseMap.end()) {
1348 Op2 = BMI->second;
1349 } else {
1350 for (auto &DRS : RootSets) {
1351 if (DRS.Roots[Iter-1] == (Instruction*) Op2) {
1352 Op2 = DRS.BaseInst;
1353 break;
1354 }
1355 }
1356 }
1357
1358 if (BaseInst->getOperand(Swapped ? unsigned(!j) : j) != Op2) {
1359 // If we've not already decided to swap the matched operands, and
1360 // we've not already matched our first operand (note that we could
1361 // have skipped matching the first operand because it is part of a
1362 // reduction above), and the instruction is commutative, then try
1363 // the swapped match.
1364 if (!Swapped && BaseInst->isCommutative() && !SomeOpMatched &&
1365 BaseInst->getOperand(!j) == Op2) {
1366 Swapped = true;
1367 } else {
1369 << "LRR: iteration root match failed at " << *BaseInst
1370 << " vs. " << *RootInst << " (operand " << j << ")\n");
1371 return false;
1372 }
1373 }
1374
1375 SomeOpMatched = true;
1376 }
1377 }
1378
1379 if ((!PossibleRedLastSet.count(BaseInst) &&
1380 hasUsesOutsideLoop(BaseInst, L)) ||
1381 (!PossibleRedLastSet.count(RootInst) &&
1382 hasUsesOutsideLoop(RootInst, L))) {
1383 LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst
1384 << " vs. " << *RootInst << " (uses outside loop)\n");
1385 return false;
1386 }
1387
1388 Reductions.recordPair(BaseInst, RootInst, Iter);
1389 BaseMap.insert(std::make_pair(RootInst, BaseInst));
1390
1391 LastRootIt = RootIt;
1392 Visited.insert(BaseInst);
1393 Visited.insert(RootInst);
1394 BaseIt = nextInstr(0, Uses, Visited);
1395 RootIt = nextInstr(Iter, Uses, Visited);
1396 }
1397 assert(BaseIt == Uses.end() && RootIt == Uses.end() &&
1398 "Mismatched set sizes!");
1399 }
1400
1401 LLVM_DEBUG(dbgs() << "LRR: Matched all iteration increments for " << *IV
1402 << "\n");
1403
1404 return true;
1405}
1406
1407void LoopReroll::DAGRootTracker::replace(const SCEV *BackedgeTakenCount) {
1408 BasicBlock *Header = L->getHeader();
1409
1410 // Compute the start and increment for each BaseInst before we start erasing
1411 // instructions.
1414 for (auto &DRS : RootSets) {
1415 const SCEVAddRecExpr *IVSCEV =
1416 cast<SCEVAddRecExpr>(SE->getSCEV(DRS.BaseInst));
1417 StartExprs.push_back(IVSCEV->getStart());
1418 IncrExprs.push_back(SE->getMinusSCEV(SE->getSCEV(DRS.Roots[0]), IVSCEV));
1419 }
1420
1421 // Remove instructions associated with non-base iterations.
1422 for (Instruction &Inst : llvm::make_early_inc_range(llvm::reverse(*Header))) {
1423 unsigned I = Uses[&Inst].find_first();
1424 if (I > 0 && I < IL_All) {
1425 LLVM_DEBUG(dbgs() << "LRR: removing: " << Inst << "\n");
1426 Inst.eraseFromParent();
1427 }
1428 }
1429
1430 // Rewrite each BaseInst using SCEV.
1431 for (size_t i = 0, e = RootSets.size(); i != e; ++i)
1432 // Insert the new induction variable.
1433 replaceIV(RootSets[i], StartExprs[i], IncrExprs[i]);
1434
1435 { // Limit the lifetime of SCEVExpander.
1436 BranchInst *BI = cast<BranchInst>(Header->getTerminator());
1437 const DataLayout &DL = Header->getModule()->getDataLayout();
1438 SCEVExpander Expander(*SE, DL, "reroll");
1439 auto Zero = SE->getZero(BackedgeTakenCount->getType());
1440 auto One = SE->getOne(BackedgeTakenCount->getType());
1441 auto NewIVSCEV = SE->getAddRecExpr(Zero, One, L, SCEV::FlagAnyWrap);
1442 Value *NewIV =
1443 Expander.expandCodeFor(NewIVSCEV, BackedgeTakenCount->getType(),
1444 Header->getFirstNonPHIOrDbg());
1445 // FIXME: This arithmetic can overflow.
1446 auto TripCount = SE->getAddExpr(BackedgeTakenCount, One);
1447 auto ScaledTripCount = SE->getMulExpr(
1448 TripCount, SE->getConstant(BackedgeTakenCount->getType(), Scale));
1449 auto ScaledBECount = SE->getMinusSCEV(ScaledTripCount, One);
1450 Value *TakenCount =
1451 Expander.expandCodeFor(ScaledBECount, BackedgeTakenCount->getType(),
1452 Header->getFirstNonPHIOrDbg());
1453 Value *Cond =
1454 new ICmpInst(BI, CmpInst::ICMP_EQ, NewIV, TakenCount, "exitcond");
1455 BI->setCondition(Cond);
1456
1457 if (BI->getSuccessor(1) != Header)
1458 BI->swapSuccessors();
1459 }
1460
1461 SimplifyInstructionsInBlock(Header, TLI);
1462 DeleteDeadPHIs(Header, TLI);
1463}
1464
1465void LoopReroll::DAGRootTracker::replaceIV(DAGRootSet &DRS,
1466 const SCEV *Start,
1467 const SCEV *IncrExpr) {
1468 BasicBlock *Header = L->getHeader();
1469 Instruction *Inst = DRS.BaseInst;
1470
1471 const SCEV *NewIVSCEV =
1472 SE->getAddRecExpr(Start, IncrExpr, L, SCEV::FlagAnyWrap);
1473
1474 { // Limit the lifetime of SCEVExpander.
1475 const DataLayout &DL = Header->getModule()->getDataLayout();
1476 SCEVExpander Expander(*SE, DL, "reroll");
1477 Value *NewIV = Expander.expandCodeFor(NewIVSCEV, Inst->getType(),
1478 Header->getFirstNonPHIOrDbg());
1479
1480 for (auto &KV : Uses)
1481 if (KV.second.find_first() == 0)
1482 KV.first->replaceUsesOfWith(Inst, NewIV);
1483 }
1484}
1485
1486// Validate the selected reductions. All iterations must have an isomorphic
1487// part of the reduction chain and, for non-associative reductions, the chain
1488// entries must appear in order.
1489bool LoopReroll::ReductionTracker::validateSelected() {
1490 // For a non-associative reduction, the chain entries must appear in order.
1491 for (int i : Reds) {
1492 int PrevIter = 0, BaseCount = 0, Count = 0;
1493 for (Instruction *J : PossibleReds[i]) {
1494 // Note that all instructions in the chain must have been found because
1495 // all instructions in the function must have been assigned to some
1496 // iteration.
1497 int Iter = PossibleRedIter[J];
1498 if (Iter != PrevIter && Iter != PrevIter + 1 &&
1499 !PossibleReds[i].getReducedValue()->isAssociative()) {
1500 LLVM_DEBUG(dbgs() << "LRR: Out-of-order non-associative reduction: "
1501 << J << "\n");
1502 return false;
1503 }
1504
1505 if (Iter != PrevIter) {
1506 if (Count != BaseCount) {
1508 << "LRR: Iteration " << PrevIter << " reduction use count "
1509 << Count << " is not equal to the base use count "
1510 << BaseCount << "\n");
1511 return false;
1512 }
1513
1514 Count = 0;
1515 }
1516
1517 ++Count;
1518 if (Iter == 0)
1519 ++BaseCount;
1520
1521 PrevIter = Iter;
1522 }
1523 }
1524
1525 return true;
1526}
1527
1528// For all selected reductions, remove all parts except those in the first
1529// iteration (and the PHI). Replace outside uses of the reduced value with uses
1530// of the first-iteration reduced value (in other words, reroll the selected
1531// reductions).
1532void LoopReroll::ReductionTracker::replaceSelected() {
1533 // Fixup reductions to refer to the last instruction associated with the
1534 // first iteration (not the last).
1535 for (int i : Reds) {
1536 int j = 0;
1537 for (int e = PossibleReds[i].size(); j != e; ++j)
1538 if (PossibleRedIter[PossibleReds[i][j]] != 0) {
1539 --j;
1540 break;
1541 }
1542
1543 // Replace users with the new end-of-chain value.
1544 SmallInstructionVector Users;
1545 for (User *U : PossibleReds[i].getReducedValue()->users()) {
1546 Users.push_back(cast<Instruction>(U));
1547 }
1548
1549 for (Instruction *User : Users)
1550 User->replaceUsesOfWith(PossibleReds[i].getReducedValue(),
1551 PossibleReds[i][j]);
1552 }
1553}
1554
1555// Reroll the provided loop with respect to the provided induction variable.
1556// Generally, we're looking for a loop like this:
1557//
1558// %iv = phi [ (preheader, ...), (body, %iv.next) ]
1559// f(%iv)
1560// %iv.1 = add %iv, 1 <-- a root increment
1561// f(%iv.1)
1562// %iv.2 = add %iv, 2 <-- a root increment
1563// f(%iv.2)
1564// %iv.scale_m_1 = add %iv, scale-1 <-- a root increment
1565// f(%iv.scale_m_1)
1566// ...
1567// %iv.next = add %iv, scale
1568// %cmp = icmp(%iv, ...)
1569// br %cmp, header, exit
1570//
1571// Notably, we do not require that f(%iv), f(%iv.1), etc. be isolated groups of
1572// instructions. In other words, the instructions in f(%iv), f(%iv.1), etc. can
1573// be intermixed with eachother. The restriction imposed by this algorithm is
1574// that the relative order of the isomorphic instructions in f(%iv), f(%iv.1),
1575// etc. be the same.
1576//
1577// First, we collect the use set of %iv, excluding the other increment roots.
1578// This gives us f(%iv). Then we iterate over the loop instructions (scale-1)
1579// times, having collected the use set of f(%iv.(i+1)), during which we:
1580// - Ensure that the next unmatched instruction in f(%iv) is isomorphic to
1581// the next unmatched instruction in f(%iv.(i+1)).
1582// - Ensure that both matched instructions don't have any external users
1583// (with the exception of last-in-chain reduction instructions).
1584// - Track the (aliasing) write set, and other side effects, of all
1585// instructions that belong to future iterations that come before the matched
1586// instructions. If the matched instructions read from that write set, then
1587// f(%iv) or f(%iv.(i+1)) has some dependency on instructions in
1588// f(%iv.(j+1)) for some j > i, and we cannot reroll the loop. Similarly,
1589// if any of these future instructions had side effects (could not be
1590// speculatively executed), and so do the matched instructions, when we
1591// cannot reorder those side-effect-producing instructions, and rerolling
1592// fails.
1593//
1594// Finally, we make sure that all loop instructions are either loop increment
1595// roots, belong to simple latch code, parts of validated reductions, part of
1596// f(%iv) or part of some f(%iv.i). If all of that is true (and all reductions
1597// have been validated), then we reroll the loop.
1598bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header,
1599 const SCEV *BackedgeTakenCount,
1600 ReductionTracker &Reductions) {
1601 DAGRootTracker DAGRoots(this, L, IV, SE, AA, TLI, DT, LI, PreserveLCSSA,
1602 IVToIncMap, LoopControlIVs);
1603
1604 if (!DAGRoots.findRoots())
1605 return false;
1606 LLVM_DEBUG(dbgs() << "LRR: Found all root induction increments for: " << *IV
1607 << "\n");
1608
1609 if (!DAGRoots.validate(Reductions))
1610 return false;
1611 if (!Reductions.validateSelected())
1612 return false;
1613 // At this point, we've validated the rerolling, and we're committed to
1614 // making changes!
1615
1616 Reductions.replaceSelected();
1617 DAGRoots.replace(BackedgeTakenCount);
1618
1619 ++NumRerolledLoops;
1620 return true;
1621}
1622
1623bool LoopReroll::runOnLoop(Loop *L) {
1624 BasicBlock *Header = L->getHeader();
1625 LLVM_DEBUG(dbgs() << "LRR: F[" << Header->getParent()->getName() << "] Loop %"
1626 << Header->getName() << " (" << L->getNumBlocks()
1627 << " block(s))\n");
1628
1629 // For now, we'll handle only single BB loops.
1630 if (L->getNumBlocks() > 1)
1631 return false;
1632
1634 return false;
1635
1636 const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
1637 LLVM_DEBUG(dbgs() << "\n Before Reroll:\n" << *(L->getHeader()) << "\n");
1638 LLVM_DEBUG(dbgs() << "LRR: backedge-taken count = " << *BackedgeTakenCount
1639 << "\n");
1640
1641 // First, we need to find the induction variable with respect to which we can
1642 // reroll (there may be several possible options).
1643 SmallInstructionVector PossibleIVs;
1644 IVToIncMap.clear();
1645 LoopControlIVs.clear();
1646 collectPossibleIVs(L, PossibleIVs);
1647
1648 if (PossibleIVs.empty()) {
1649 LLVM_DEBUG(dbgs() << "LRR: No possible IVs found\n");
1650 return false;
1651 }
1652
1653 ReductionTracker Reductions;
1654 collectPossibleReductions(L, Reductions);
1655 bool Changed = false;
1656
1657 // For each possible IV, collect the associated possible set of 'root' nodes
1658 // (i+1, i+2, etc.).
1659 for (Instruction *PossibleIV : PossibleIVs)
1660 if (reroll(PossibleIV, L, Header, BackedgeTakenCount, Reductions)) {
1661 Changed = true;
1662 break;
1663 }
1664 LLVM_DEBUG(dbgs() << "\n After Reroll:\n" << *(L->getHeader()) << "\n");
1665
1666 // Trip count of L has changed so SE must be re-evaluated.
1667 if (Changed)
1668 SE->forgetLoop(L);
1669
1670 return Changed;
1671}
1672
1675 LPMUpdater &U) {
1676 return LoopReroll(&AR.AA, &AR.LI, &AR.SE, &AR.TLI, &AR.DT, true).runOnLoop(&L)
1679}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements a class to represent arbitrary precision integral constant values and operations...
This file implements the BitVector class.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
bool End
Definition: ELF_riscv.cpp:469
Rewrite Partial Register Uses
Hexagon Common GEP
IRTranslator LLVM IR MI
iv Induction Variable Users
Definition: IVUsers.cpp:48
iv users
Definition: IVUsers.cpp:48
static bool isIgnorableInst(const Instruction *I)
static cl::opt< unsigned > NumToleratedFailedMatches("reroll-num-tolerated-failed-matches", cl::init(400), cl::Hidden, cl::desc("The maximum number of failures to tolerate" " during fuzzy matching. (default: 400)"))
static bool isLoopIncrement(User *U, Instruction *IV)
static bool isSimpleArithmeticOp(User *IVU)
Return true if IVU is a "simple" arithmetic operation.
static bool isUnorderedLoadStore(Instruction *I)
static bool hasUsesOutsideLoop(Instruction *I, Loop *L)
#define I(x, y, z)
Definition: MD5.cpp:58
This file implements a map that provides insertion order iteration.
Module.h This file contains the declarations for the Module class.
#define P(N)
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
This defines the Use class.
static bool isAssociative(const COFFSection &Section)
static const uint32_t IV[8]
Definition: blake3_impl.h:78
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1507
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
BinaryOps getOpcode() const
Definition: InstrTypes.h:391
Conditional or Unconditional Branch instruction.
void setCondition(Value *V)
void swapSuccessors()
Swap the successors of this branch instruction.
BasicBlock * getSuccessor(unsigned i) const
@ ICMP_EQ
equal
Definition: InstrTypes.h:732
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:136
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
This instruction compares its operands according to the predicate given to the constructor.
bool isSameOperationAs(const Instruction *I, unsigned flags=0) const LLVM_READONLY
This function determines if the specified instruction executes the same operation as the current one.
bool isAssociative() const LLVM_READONLY
Return true if the instruction is associative:
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:54
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
An instruction for reading from memory.
Definition: Instructions.h:177
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:47
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
typename VectorType::iterator iterator
Definition: MapVector.h:49
This is the common base class for memset/memcpy/memmove.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
This node represents a polynomial recurrence on the trip count of the specified loop.
This class uses information about analyze scalars to rewrite expressions in canonical form.
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
Provides information about what library functions are available for the current target.
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:255
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
Value * getOperand(unsigned i) const
Definition: User.h:169
unsigned getNumOperands() const
Definition: User.h:191
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
user_iterator user_begin()
Definition: Value.h:397
iterator_range< user_iterator > users()
Definition: Value.h:421
unsigned getNumUses() const
This method computes the number of uses of this Value.
Definition: Value.cpp:255
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
void validate(const Triple &TT, const FeatureBitset &FeatureBits)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
constexpr double e
Definition: MathExtras.h:31
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:228
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:237
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1685
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:666
bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Scan the specified basic block and try to simplify any instructions in it and recursively delete dead...
Definition: Local.cpp:717
bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Examine each PHI in the given block and delete it if it is dead.
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:429
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool isModOrRefSet(const ModRefInfo MRI)
Definition: ModRef.h:42
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
void replace(Container &Cont, typename Container::iterator ContIt, typename Container::iterator ContEnd, RandomAccessIterator ValIt, RandomAccessIterator ValEnd)
Given a sequence container Cont, replace the range [ContIt, ContEnd) with the range [ValIt,...
Definition: STLExtras.h:2044
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1884
#define N
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...