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