Bug Summary

File:lib/Transforms/Scalar/LoopInterchange.cpp
Warning:line 1282, column 3
Value stored to 'InnerLoopLatch' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name LoopInterchange.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn329677/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/lib/Transforms/Scalar -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-04-11-031539-24776-1 -x c++ /build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Scalar/LoopInterchange.cpp
1//===- LoopInterchange.cpp - Loop interchange pass-------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This Pass handles loop interchange transform.
11// This pass interchanges loops to provide a more cache-friendly memory access
12// patterns.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/SmallVector.h"
18#include "llvm/ADT/Statistic.h"
19#include "llvm/ADT/StringRef.h"
20#include "llvm/Analysis/AliasAnalysis.h"
21#include "llvm/Analysis/DependenceAnalysis.h"
22#include "llvm/Analysis/LoopInfo.h"
23#include "llvm/Analysis/OptimizationRemarkEmitter.h"
24#include "llvm/Analysis/ScalarEvolution.h"
25#include "llvm/Analysis/ScalarEvolutionExpressions.h"
26#include "llvm/IR/BasicBlock.h"
27#include "llvm/IR/Constants.h"
28#include "llvm/IR/DiagnosticInfo.h"
29#include "llvm/IR/Dominators.h"
30#include "llvm/IR/Function.h"
31#include "llvm/IR/InstrTypes.h"
32#include "llvm/IR/Instruction.h"
33#include "llvm/IR/Instructions.h"
34#include "llvm/IR/Type.h"
35#include "llvm/IR/User.h"
36#include "llvm/IR/Value.h"
37#include "llvm/Pass.h"
38#include "llvm/Support/Casting.h"
39#include "llvm/Support/CommandLine.h"
40#include "llvm/Support/Debug.h"
41#include "llvm/Support/ErrorHandling.h"
42#include "llvm/Support/raw_ostream.h"
43#include "llvm/Transforms/Scalar.h"
44#include "llvm/Transforms/Utils.h"
45#include "llvm/Transforms/Utils/BasicBlockUtils.h"
46#include "llvm/Transforms/Utils/LoopUtils.h"
47#include <cassert>
48#include <utility>
49#include <vector>
50
51using namespace llvm;
52
53#define DEBUG_TYPE"loop-interchange" "loop-interchange"
54
55STATISTIC(LoopsInterchanged, "Number of loops interchanged")static llvm::Statistic LoopsInterchanged = {"loop-interchange"
, "LoopsInterchanged", "Number of loops interchanged", {0}, {
false}}
;
56
57static cl::opt<int> LoopInterchangeCostThreshold(
58 "loop-interchange-threshold", cl::init(0), cl::Hidden,
59 cl::desc("Interchange if you gain more than this number"));
60
61namespace {
62
63using LoopVector = SmallVector<Loop *, 8>;
64
65// TODO: Check if we can use a sparse matrix here.
66using CharMatrix = std::vector<std::vector<char>>;
67
68} // end anonymous namespace
69
70// Maximum number of dependencies that can be handled in the dependency matrix.
71static const unsigned MaxMemInstrCount = 100;
72
73// Maximum loop depth supported.
74static const unsigned MaxLoopNestDepth = 10;
75
76#ifdef DUMP_DEP_MATRICIES
77static void printDepMatrix(CharMatrix &DepMatrix) {
78 for (auto &Row : DepMatrix) {
79 for (auto D : Row)
80 DEBUG(dbgs() << D << " ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << D << " "; } } while
(false)
;
81 DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "\n"; } } while (false
)
;
82 }
83}
84#endif
85
86static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
87 Loop *L, DependenceInfo *DI) {
88 using ValueVector = SmallVector<Value *, 16>;
89
90 ValueVector MemInstr;
91
92 // For each block.
93 for (BasicBlock *BB : L->blocks()) {
94 // Scan the BB and collect legal loads and stores.
95 for (Instruction &I : *BB) {
96 if (!isa<Instruction>(I))
97 return false;
98 if (auto *Ld = dyn_cast<LoadInst>(&I)) {
99 if (!Ld->isSimple())
100 return false;
101 MemInstr.push_back(&I);
102 } else if (auto *St = dyn_cast<StoreInst>(&I)) {
103 if (!St->isSimple())
104 return false;
105 MemInstr.push_back(&I);
106 }
107 }
108 }
109
110 DEBUG(dbgs() << "Found " << MemInstr.size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Found " << MemInstr
.size() << " Loads and Stores to analyze\n"; } } while (
false)
111 << " Loads and Stores to analyze\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Found " << MemInstr
.size() << " Loads and Stores to analyze\n"; } } while (
false)
;
112
113 ValueVector::iterator I, IE, J, JE;
114
115 for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
116 for (J = I, JE = MemInstr.end(); J != JE; ++J) {
117 std::vector<char> Dep;
118 Instruction *Src = cast<Instruction>(*I);
119 Instruction *Dst = cast<Instruction>(*J);
120 if (Src == Dst)
121 continue;
122 // Ignore Input dependencies.
123 if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
124 continue;
125 // Track Output, Flow, and Anti dependencies.
126 if (auto D = DI->depends(Src, Dst, true)) {
127 assert(D->isOrdered() && "Expected an output, flow or anti dep.")(static_cast <bool> (D->isOrdered() && "Expected an output, flow or anti dep."
) ? void (0) : __assert_fail ("D->isOrdered() && \"Expected an output, flow or anti dep.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Scalar/LoopInterchange.cpp"
, 127, __extension__ __PRETTY_FUNCTION__))
;
128 DEBUG(StringRef DepType =do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { StringRef DepType = D->isFlow() ? "flow"
: D->isAnti() ? "anti" : "output"; dbgs() << "Found "
<< DepType << " dependency between Src and Dst\n"
<< " Src:" << *Src << "\n Dst:" << *
Dst << '\n'; } } while (false)
129 D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { StringRef DepType = D->isFlow() ? "flow"
: D->isAnti() ? "anti" : "output"; dbgs() << "Found "
<< DepType << " dependency between Src and Dst\n"
<< " Src:" << *Src << "\n Dst:" << *
Dst << '\n'; } } while (false)
130 dbgs() << "Found " << DepTypedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { StringRef DepType = D->isFlow() ? "flow"
: D->isAnti() ? "anti" : "output"; dbgs() << "Found "
<< DepType << " dependency between Src and Dst\n"
<< " Src:" << *Src << "\n Dst:" << *
Dst << '\n'; } } while (false)
131 << " dependency between Src and Dst\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { StringRef DepType = D->isFlow() ? "flow"
: D->isAnti() ? "anti" : "output"; dbgs() << "Found "
<< DepType << " dependency between Src and Dst\n"
<< " Src:" << *Src << "\n Dst:" << *
Dst << '\n'; } } while (false)
132 << " Src:" << *Src << "\n Dst:" << *Dst << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { StringRef DepType = D->isFlow() ? "flow"
: D->isAnti() ? "anti" : "output"; dbgs() << "Found "
<< DepType << " dependency between Src and Dst\n"
<< " Src:" << *Src << "\n Dst:" << *
Dst << '\n'; } } while (false)
;
133 unsigned Levels = D->getLevels();
134 char Direction;
135 for (unsigned II = 1; II <= Levels; ++II) {
136 const SCEV *Distance = D->getDistance(II);
137 const SCEVConstant *SCEVConst =
138 dyn_cast_or_null<SCEVConstant>(Distance);
139 if (SCEVConst) {
140 const ConstantInt *CI = SCEVConst->getValue();
141 if (CI->isNegative())
142 Direction = '<';
143 else if (CI->isZero())
144 Direction = '=';
145 else
146 Direction = '>';
147 Dep.push_back(Direction);
148 } else if (D->isScalar(II)) {
149 Direction = 'S';
150 Dep.push_back(Direction);
151 } else {
152 unsigned Dir = D->getDirection(II);
153 if (Dir == Dependence::DVEntry::LT ||
154 Dir == Dependence::DVEntry::LE)
155 Direction = '<';
156 else if (Dir == Dependence::DVEntry::GT ||
157 Dir == Dependence::DVEntry::GE)
158 Direction = '>';
159 else if (Dir == Dependence::DVEntry::EQ)
160 Direction = '=';
161 else
162 Direction = '*';
163 Dep.push_back(Direction);
164 }
165 }
166 while (Dep.size() != Level) {
167 Dep.push_back('I');
168 }
169
170 DepMatrix.push_back(Dep);
171 if (DepMatrix.size() > MaxMemInstrCount) {
172 DEBUG(dbgs() << "Cannot handle more than " << MaxMemInstrCountdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Cannot handle more than "
<< MaxMemInstrCount << " dependencies inside loop\n"
; } } while (false)
173 << " dependencies inside loop\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Cannot handle more than "
<< MaxMemInstrCount << " dependencies inside loop\n"
; } } while (false)
;
174 return false;
175 }
176 }
177 }
178 }
179
180 return true;
181}
182
183// A loop is moved from index 'from' to an index 'to'. Update the Dependence
184// matrix by exchanging the two columns.
185static void interChangeDependencies(CharMatrix &DepMatrix, unsigned FromIndx,
186 unsigned ToIndx) {
187 unsigned numRows = DepMatrix.size();
188 for (unsigned i = 0; i < numRows; ++i) {
189 char TmpVal = DepMatrix[i][ToIndx];
190 DepMatrix[i][ToIndx] = DepMatrix[i][FromIndx];
191 DepMatrix[i][FromIndx] = TmpVal;
192 }
193}
194
195// Checks if outermost non '=','S'or'I' dependence in the dependence matrix is
196// '>'
197static bool isOuterMostDepPositive(CharMatrix &DepMatrix, unsigned Row,
198 unsigned Column) {
199 for (unsigned i = 0; i <= Column; ++i) {
200 if (DepMatrix[Row][i] == '<')
201 return false;
202 if (DepMatrix[Row][i] == '>')
203 return true;
204 }
205 // All dependencies were '=','S' or 'I'
206 return false;
207}
208
209// Checks if no dependence exist in the dependency matrix in Row before Column.
210static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row,
211 unsigned Column) {
212 for (unsigned i = 0; i < Column; ++i) {
213 if (DepMatrix[Row][i] != '=' && DepMatrix[Row][i] != 'S' &&
214 DepMatrix[Row][i] != 'I')
215 return false;
216 }
217 return true;
218}
219
220static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row,
221 unsigned OuterLoopId, char InnerDep,
222 char OuterDep) {
223 if (isOuterMostDepPositive(DepMatrix, Row, OuterLoopId))
224 return false;
225
226 if (InnerDep == OuterDep)
227 return true;
228
229 // It is legal to interchange if and only if after interchange no row has a
230 // '>' direction as the leftmost non-'='.
231
232 if (InnerDep == '=' || InnerDep == 'S' || InnerDep == 'I')
233 return true;
234
235 if (InnerDep == '<')
236 return true;
237
238 if (InnerDep == '>') {
239 // If OuterLoopId represents outermost loop then interchanging will make the
240 // 1st dependency as '>'
241 if (OuterLoopId == 0)
242 return false;
243
244 // If all dependencies before OuterloopId are '=','S'or 'I'. Then
245 // interchanging will result in this row having an outermost non '='
246 // dependency of '>'
247 if (!containsNoDependence(DepMatrix, Row, OuterLoopId))
248 return true;
249 }
250
251 return false;
252}
253
254// Checks if it is legal to interchange 2 loops.
255// [Theorem] A permutation of the loops in a perfect nest is legal if and only
256// if the direction matrix, after the same permutation is applied to its
257// columns, has no ">" direction as the leftmost non-"=" direction in any row.
258static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,
259 unsigned InnerLoopId,
260 unsigned OuterLoopId) {
261 unsigned NumRows = DepMatrix.size();
262 // For each row check if it is valid to interchange.
263 for (unsigned Row = 0; Row < NumRows; ++Row) {
264 char InnerDep = DepMatrix[Row][InnerLoopId];
265 char OuterDep = DepMatrix[Row][OuterLoopId];
266 if (InnerDep == '*' || OuterDep == '*')
267 return false;
268 if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep, OuterDep))
269 return false;
270 }
271 return true;
272}
273
274static void populateWorklist(Loop &L, SmallVector<LoopVector, 8> &V) {
275 DEBUG(dbgs() << "Calling populateWorklist on Func: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Calling populateWorklist on Func: "
<< L.getHeader()->getParent()->getName() <<
" Loop: %" << L.getHeader()->getName() << '\n'
; } } while (false)
276 << L.getHeader()->getParent()->getName() << " Loop: %"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Calling populateWorklist on Func: "
<< L.getHeader()->getParent()->getName() <<
" Loop: %" << L.getHeader()->getName() << '\n'
; } } while (false)
277 << L.getHeader()->getName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Calling populateWorklist on Func: "
<< L.getHeader()->getParent()->getName() <<
" Loop: %" << L.getHeader()->getName() << '\n'
; } } while (false)
;
278 LoopVector LoopList;
279 Loop *CurrentLoop = &L;
280 const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
281 while (!Vec->empty()) {
282 // The current loop has multiple subloops in it hence it is not tightly
283 // nested.
284 // Discard all loops above it added into Worklist.
285 if (Vec->size() != 1) {
286 LoopList.clear();
287 return;
288 }
289 LoopList.push_back(CurrentLoop);
290 CurrentLoop = Vec->front();
291 Vec = &CurrentLoop->getSubLoops();
292 }
293 LoopList.push_back(CurrentLoop);
294 V.push_back(std::move(LoopList));
295}
296
297static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) {
298 PHINode *InnerIndexVar = L->getCanonicalInductionVariable();
299 if (InnerIndexVar)
300 return InnerIndexVar;
301 if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr)
302 return nullptr;
303 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
304 PHINode *PhiVar = cast<PHINode>(I);
305 Type *PhiTy = PhiVar->getType();
306 if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
307 !PhiTy->isPointerTy())
308 return nullptr;
309 const SCEVAddRecExpr *AddRec =
310 dyn_cast<SCEVAddRecExpr>(SE->getSCEV(PhiVar));
311 if (!AddRec || !AddRec->isAffine())
312 continue;
313 const SCEV *Step = AddRec->getStepRecurrence(*SE);
314 if (!isa<SCEVConstant>(Step))
315 continue;
316 // Found the induction variable.
317 // FIXME: Handle loops with more than one induction variable. Note that,
318 // currently, legality makes sure we have only one induction variable.
319 return PhiVar;
320 }
321 return nullptr;
322}
323
324namespace {
325
326/// LoopInterchangeLegality checks if it is legal to interchange the loop.
327class LoopInterchangeLegality {
328public:
329 LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
330 LoopInfo *LI, DominatorTree *DT, bool PreserveLCSSA,
331 OptimizationRemarkEmitter *ORE)
332 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
333 PreserveLCSSA(PreserveLCSSA), ORE(ORE) {}
334
335 /// Check if the loops can be interchanged.
336 bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
337 CharMatrix &DepMatrix);
338
339 /// Check if the loop structure is understood. We do not handle triangular
340 /// loops for now.
341 bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
342
343 bool currentLimitations();
344
345 bool hasInnerLoopReduction() { return InnerLoopHasReduction; }
346
347private:
348 bool tightlyNested(Loop *Outer, Loop *Inner);
349 bool containsUnsafeInstructionsInHeader(BasicBlock *BB);
350 bool areAllUsesReductions(Instruction *Ins, Loop *L);
351 bool containsUnsafeInstructionsInLatch(BasicBlock *BB);
352 bool findInductionAndReductions(Loop *L,
353 SmallVector<PHINode *, 8> &Inductions,
354 SmallVector<PHINode *, 8> &Reductions);
355
356 Loop *OuterLoop;
357 Loop *InnerLoop;
358
359 ScalarEvolution *SE;
360 LoopInfo *LI;
361 DominatorTree *DT;
362 bool PreserveLCSSA;
363
364 /// Interface to emit optimization remarks.
365 OptimizationRemarkEmitter *ORE;
366
367 bool InnerLoopHasReduction = false;
368};
369
370/// LoopInterchangeProfitability checks if it is profitable to interchange the
371/// loop.
372class LoopInterchangeProfitability {
373public:
374 LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
375 OptimizationRemarkEmitter *ORE)
376 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
377
378 /// Check if the loop interchange is profitable.
379 bool isProfitable(unsigned InnerLoopId, unsigned OuterLoopId,
380 CharMatrix &DepMatrix);
381
382private:
383 int getInstrOrderCost();
384
385 Loop *OuterLoop;
386 Loop *InnerLoop;
387
388 /// Scev analysis.
389 ScalarEvolution *SE;
390
391 /// Interface to emit optimization remarks.
392 OptimizationRemarkEmitter *ORE;
393};
394
395/// LoopInterchangeTransform interchanges the loop.
396class LoopInterchangeTransform {
397public:
398 LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
399 LoopInfo *LI, DominatorTree *DT,
400 BasicBlock *LoopNestExit,
401 bool InnerLoopContainsReductions)
402 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
403 LoopExit(LoopNestExit),
404 InnerLoopHasReduction(InnerLoopContainsReductions) {}
405
406 /// Interchange OuterLoop and InnerLoop.
407 bool transform();
408 void restructureLoops(Loop *NewInner, Loop *NewOuter,
409 BasicBlock *OrigInnerPreHeader,
410 BasicBlock *OrigOuterPreHeader);
411 void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
412
413private:
414 void splitInnerLoopLatch(Instruction *);
415 void splitInnerLoopHeader();
416 bool adjustLoopLinks();
417 void adjustLoopPreheaders();
418 bool adjustLoopBranches();
419 void updateIncomingBlock(BasicBlock *CurrBlock, BasicBlock *OldPred,
420 BasicBlock *NewPred);
421
422 Loop *OuterLoop;
423 Loop *InnerLoop;
424
425 /// Scev analysis.
426 ScalarEvolution *SE;
427
428 LoopInfo *LI;
429 DominatorTree *DT;
430 BasicBlock *LoopExit;
431 bool InnerLoopHasReduction;
432};
433
434// Main LoopInterchange Pass.
435struct LoopInterchange : public FunctionPass {
436 static char ID;
437 ScalarEvolution *SE = nullptr;
438 LoopInfo *LI = nullptr;
439 DependenceInfo *DI = nullptr;
440 DominatorTree *DT = nullptr;
441 bool PreserveLCSSA;
442
443 /// Interface to emit optimization remarks.
444 OptimizationRemarkEmitter *ORE;
445
446 LoopInterchange() : FunctionPass(ID) {
447 initializeLoopInterchangePass(*PassRegistry::getPassRegistry());
448 }
449
450 void getAnalysisUsage(AnalysisUsage &AU) const override {
451 AU.addRequired<ScalarEvolutionWrapperPass>();
452 AU.addRequired<AAResultsWrapperPass>();
453 AU.addRequired<DominatorTreeWrapperPass>();
454 AU.addRequired<LoopInfoWrapperPass>();
455 AU.addRequired<DependenceAnalysisWrapperPass>();
456 AU.addRequiredID(LoopSimplifyID);
457 AU.addRequiredID(LCSSAID);
458 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
459
460 AU.addPreserved<DominatorTreeWrapperPass>();
461 AU.addPreserved<LoopInfoWrapperPass>();
462 }
463
464 bool runOnFunction(Function &F) override {
465 if (skipFunction(F))
466 return false;
467
468 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
469 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
470 DI = &getAnalysis<DependenceAnalysisWrapperPass>().getDI();
471 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
472 ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
473 PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
474
475 // Build up a worklist of loop pairs to analyze.
476 SmallVector<LoopVector, 8> Worklist;
477
478 for (Loop *L : *LI)
479 populateWorklist(*L, Worklist);
480
481 DEBUG(dbgs() << "Worklist size = " << Worklist.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Worklist size = " <<
Worklist.size() << "\n"; } } while (false)
;
482 bool Changed = true;
483 while (!Worklist.empty()) {
484 LoopVector LoopList = Worklist.pop_back_val();
485 Changed = processLoopList(LoopList, F);
486 }
487 return Changed;
488 }
489
490 bool isComputableLoopNest(LoopVector LoopList) {
491 for (Loop *L : LoopList) {
492 const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
493 if (ExitCountOuter == SE->getCouldNotCompute()) {
494 DEBUG(dbgs() << "Couldn't compute backedge count\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Couldn't compute backedge count\n"
; } } while (false)
;
495 return false;
496 }
497 if (L->getNumBackEdges() != 1) {
498 DEBUG(dbgs() << "NumBackEdges is not equal to 1\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "NumBackEdges is not equal to 1\n"
; } } while (false)
;
499 return false;
500 }
501 if (!L->getExitingBlock()) {
502 DEBUG(dbgs() << "Loop doesn't have unique exit block\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loop doesn't have unique exit block\n"
; } } while (false)
;
503 return false;
504 }
505 }
506 return true;
507 }
508
509 unsigned selectLoopForInterchange(const LoopVector &LoopList) {
510 // TODO: Add a better heuristic to select the loop to be interchanged based
511 // on the dependence matrix. Currently we select the innermost loop.
512 return LoopList.size() - 1;
513 }
514
515 bool processLoopList(LoopVector LoopList, Function &F) {
516 bool Changed = false;
517 unsigned LoopNestDepth = LoopList.size();
518 if (LoopNestDepth < 2) {
519 DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loop doesn't contain minimum nesting level.\n"
; } } while (false)
;
520 return false;
521 }
522 if (LoopNestDepth > MaxLoopNestDepth) {
523 DEBUG(dbgs() << "Cannot handle loops of depth greater than "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Cannot handle loops of depth greater than "
<< MaxLoopNestDepth << "\n"; } } while (false)
524 << MaxLoopNestDepth << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Cannot handle loops of depth greater than "
<< MaxLoopNestDepth << "\n"; } } while (false)
;
525 return false;
526 }
527 if (!isComputableLoopNest(LoopList)) {
528 DEBUG(dbgs() << "Not valid loop candidate for interchange\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Not valid loop candidate for interchange\n"
; } } while (false)
;
529 return false;
530 }
531
532 DEBUG(dbgs() << "Processing LoopList of size = " << LoopNestDepth << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Processing LoopList of size = "
<< LoopNestDepth << "\n"; } } while (false)
;
533
534 CharMatrix DependencyMatrix;
535 Loop *OuterMostLoop = *(LoopList.begin());
536 if (!populateDependencyMatrix(DependencyMatrix, LoopNestDepth,
537 OuterMostLoop, DI)) {
538 DEBUG(dbgs() << "Populating dependency matrix failed\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Populating dependency matrix failed\n"
; } } while (false)
;
539 return false;
540 }
541#ifdef DUMP_DEP_MATRICIES
542 DEBUG(dbgs() << "Dependence before interchange\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Dependence before interchange\n"
; } } while (false)
;
543 printDepMatrix(DependencyMatrix);
544#endif
545
546 BasicBlock *OuterMostLoopLatch = OuterMostLoop->getLoopLatch();
547 BranchInst *OuterMostLoopLatchBI =
548 dyn_cast<BranchInst>(OuterMostLoopLatch->getTerminator());
549 if (!OuterMostLoopLatchBI || OuterMostLoopLatchBI->getNumSuccessors() != 2)
550 return false;
551
552 // Since we currently do not handle LCSSA PHI's any failure in loop
553 // condition will now branch to LoopNestExit.
554 // TODO: This should be removed once we handle LCSSA PHI nodes.
555
556 // Get the Outermost loop exit.
557 BasicBlock *LoopNestExit;
558 if (OuterMostLoopLatchBI->getSuccessor(0) == OuterMostLoop->getHeader())
559 LoopNestExit = OuterMostLoopLatchBI->getSuccessor(1);
560 else
561 LoopNestExit = OuterMostLoopLatchBI->getSuccessor(0);
562
563 if (isa<PHINode>(LoopNestExit->begin())) {
564 DEBUG(dbgs() << "PHI Nodes in loop nest exit is not handled for now "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "PHI Nodes in loop nest exit is not handled for now "
"since on failure all loops branch to loop nest exit.\n"; } }
while (false)
565 "since on failure all loops branch to loop nest exit.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "PHI Nodes in loop nest exit is not handled for now "
"since on failure all loops branch to loop nest exit.\n"; } }
while (false)
;
566 return false;
567 }
568
569 unsigned SelecLoopId = selectLoopForInterchange(LoopList);
570 // Move the selected loop outwards to the best possible position.
571 for (unsigned i = SelecLoopId; i > 0; i--) {
572 bool Interchanged =
573 processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix);
574 if (!Interchanged)
575 return Changed;
576 // Loops interchanged reflect the same in LoopList
577 std::swap(LoopList[i - 1], LoopList[i]);
578
579 // Update the DependencyMatrix
580 interChangeDependencies(DependencyMatrix, i, i - 1);
581#ifdef DUMP_DEP_MATRICIES
582 DEBUG(dbgs() << "Dependence after interchange\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Dependence after interchange\n"
; } } while (false)
;
583 printDepMatrix(DependencyMatrix);
584#endif
585 Changed |= Interchanged;
586 }
587 return Changed;
588 }
589
590 bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
591 unsigned OuterLoopId, BasicBlock *LoopNestExit,
592 std::vector<std::vector<char>> &DependencyMatrix) {
593 DEBUG(dbgs() << "Processing Inner Loop Id = " << InnerLoopIddo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Processing Inner Loop Id = "
<< InnerLoopId << " and OuterLoopId = " <<
OuterLoopId << "\n"; } } while (false)
594 << " and OuterLoopId = " << OuterLoopId << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Processing Inner Loop Id = "
<< InnerLoopId << " and OuterLoopId = " <<
OuterLoopId << "\n"; } } while (false)
;
595 Loop *InnerLoop = LoopList[InnerLoopId];
596 Loop *OuterLoop = LoopList[OuterLoopId];
597
598 LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, LI, DT,
599 PreserveLCSSA, ORE);
600 if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
601 DEBUG(dbgs() << "Not interchanging loops. Cannot prove legality.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Not interchanging loops. Cannot prove legality.\n"
; } } while (false)
;
602 return false;
603 }
604 DEBUG(dbgs() << "Loops are legal to interchange\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops are legal to interchange\n"
; } } while (false)
;
605 LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE);
606 if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
607 DEBUG(dbgs() << "Interchanging loops not profitable.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Interchanging loops not profitable.\n"
; } } while (false)
;
608 return false;
609 }
610
611 ORE->emit([&]() {
612 return OptimizationRemark(DEBUG_TYPE"loop-interchange", "Interchanged",
613 InnerLoop->getStartLoc(),
614 InnerLoop->getHeader())
615 << "Loop interchanged with enclosing loop.";
616 });
617
618 LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT,
619 LoopNestExit, LIL.hasInnerLoopReduction());
620 LIT.transform();
621 DEBUG(dbgs() << "Loops interchanged.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops interchanged.\n"
; } } while (false)
;
622 LoopsInterchanged++;
623 return true;
624 }
625};
626
627} // end anonymous namespace
628
629bool LoopInterchangeLegality::areAllUsesReductions(Instruction *Ins, Loop *L) {
630 return llvm::none_of(Ins->users(), [=](User *U) -> bool {
631 auto *UserIns = dyn_cast<PHINode>(U);
632 RecurrenceDescriptor RD;
633 return !UserIns || !RecurrenceDescriptor::isReductionPHI(UserIns, L, RD);
634 });
635}
636
637bool LoopInterchangeLegality::containsUnsafeInstructionsInHeader(
638 BasicBlock *BB) {
639 for (auto I = BB->begin(), E = BB->end(); I != E; ++I) {
640 // Load corresponding to reduction PHI's are safe while concluding if
641 // tightly nested.
642 if (LoadInst *L = dyn_cast<LoadInst>(I)) {
643 if (!areAllUsesReductions(L, InnerLoop))
644 return true;
645 } else if (I->mayHaveSideEffects() || I->mayReadFromMemory())
646 return true;
647 }
648 return false;
649}
650
651bool LoopInterchangeLegality::containsUnsafeInstructionsInLatch(
652 BasicBlock *BB) {
653 for (auto I = BB->begin(), E = BB->end(); I != E; ++I) {
654 // Stores corresponding to reductions are safe while concluding if tightly
655 // nested.
656 if (StoreInst *L = dyn_cast<StoreInst>(I)) {
657 if (!isa<PHINode>(L->getOperand(0)))
658 return true;
659 } else if (I->mayHaveSideEffects() || I->mayReadFromMemory())
660 return true;
661 }
662 return false;
663}
664
665bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
666 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
667 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
668 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
669
670 DEBUG(dbgs() << "Checking if loops are tightly nested\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Checking if loops are tightly nested\n"
; } } while (false)
;
671
672 // A perfectly nested loop will not have any branch in between the outer and
673 // inner block i.e. outer header will branch to either inner preheader and
674 // outerloop latch.
675 BranchInst *OuterLoopHeaderBI =
676 dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
677 if (!OuterLoopHeaderBI)
678 return false;
679
680 for (BasicBlock *Succ : OuterLoopHeaderBI->successors())
681 if (Succ != InnerLoopPreHeader && Succ != OuterLoopLatch)
682 return false;
683
684 DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Checking instructions in Loop header and Loop latch\n"
; } } while (false)
;
685 // We do not have any basic block in between now make sure the outer header
686 // and outer loop latch doesn't contain any unsafe instructions.
687 if (containsUnsafeInstructionsInHeader(OuterLoopHeader) ||
688 containsUnsafeInstructionsInLatch(OuterLoopLatch))
689 return false;
690
691 DEBUG(dbgs() << "Loops are perfectly nested\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops are perfectly nested\n"
; } } while (false)
;
692 // We have a perfect loop nest.
693 return true;
694}
695
696bool LoopInterchangeLegality::isLoopStructureUnderstood(
697 PHINode *InnerInduction) {
698 unsigned Num = InnerInduction->getNumOperands();
699 BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
700 for (unsigned i = 0; i < Num; ++i) {
701 Value *Val = InnerInduction->getOperand(i);
702 if (isa<Constant>(Val))
703 continue;
704 Instruction *I = dyn_cast<Instruction>(Val);
705 if (!I)
706 return false;
707 // TODO: Handle triangular loops.
708 // e.g. for(int i=0;i<N;i++)
709 // for(int j=i;j<N;j++)
710 unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
711 if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
712 InnerLoopPreheader &&
713 !OuterLoop->isLoopInvariant(I)) {
714 return false;
715 }
716 }
717 return true;
718}
719
720bool LoopInterchangeLegality::findInductionAndReductions(
721 Loop *L, SmallVector<PHINode *, 8> &Inductions,
722 SmallVector<PHINode *, 8> &Reductions) {
723 if (!L->getLoopLatch() || !L->getLoopPredecessor())
724 return false;
725 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
726 RecurrenceDescriptor RD;
727 InductionDescriptor ID;
728 PHINode *PHI = cast<PHINode>(I);
729 if (InductionDescriptor::isInductionPHI(PHI, L, SE, ID))
730 Inductions.push_back(PHI);
731 else if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD))
732 Reductions.push_back(PHI);
733 else {
734 DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Failed to recognize PHI as an induction or reduction.\n"
; } } while (false)
735 dbgs() << "Failed to recognize PHI as an induction or reduction.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Failed to recognize PHI as an induction or reduction.\n"
; } } while (false)
;
736 return false;
737 }
738 }
739 return true;
740}
741
742static bool containsSafePHI(BasicBlock *Block, bool isOuterLoopExitBlock) {
743 for (auto I = Block->begin(); isa<PHINode>(I); ++I) {
744 PHINode *PHI = cast<PHINode>(I);
745 // Reduction lcssa phi will have only 1 incoming block that from loop latch.
746 if (PHI->getNumIncomingValues() > 1)
747 return false;
748 Instruction *Ins = dyn_cast<Instruction>(PHI->getIncomingValue(0));
749 if (!Ins)
750 return false;
751 // Incoming value for lcssa phi's in outer loop exit can only be inner loop
752 // exits lcssa phi else it would not be tightly nested.
753 if (!isa<PHINode>(Ins) && isOuterLoopExitBlock)
754 return false;
755 }
756 return true;
757}
758
759static BasicBlock *getLoopLatchExitBlock(BasicBlock *LatchBlock,
760 BasicBlock *LoopHeader) {
761 if (BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator())) {
762 assert(BI->getNumSuccessors() == 2 &&(static_cast <bool> (BI->getNumSuccessors() == 2 &&
"Branch leaving loop latch must have 2 successors") ? void (
0) : __assert_fail ("BI->getNumSuccessors() == 2 && \"Branch leaving loop latch must have 2 successors\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Scalar/LoopInterchange.cpp"
, 763, __extension__ __PRETTY_FUNCTION__))
763 "Branch leaving loop latch must have 2 successors")(static_cast <bool> (BI->getNumSuccessors() == 2 &&
"Branch leaving loop latch must have 2 successors") ? void (
0) : __assert_fail ("BI->getNumSuccessors() == 2 && \"Branch leaving loop latch must have 2 successors\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Scalar/LoopInterchange.cpp"
, 763, __extension__ __PRETTY_FUNCTION__))
;
764 for (BasicBlock *Succ : BI->successors()) {
765 if (Succ == LoopHeader)
766 continue;
767 return Succ;
768 }
769 }
770 return nullptr;
771}
772
773// This function indicates the current limitations in the transform as a result
774// of which we do not proceed.
775bool LoopInterchangeLegality::currentLimitations() {
776 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
777 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
778 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
779 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
780 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
781
782 PHINode *InnerInductionVar;
783 SmallVector<PHINode *, 8> Inductions;
784 SmallVector<PHINode *, 8> Reductions;
785 if (!findInductionAndReductions(InnerLoop, Inductions, Reductions)) {
786 DEBUG(dbgs() << "Only inner loops with induction or reduction PHI nodes "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Only inner loops with induction or reduction PHI nodes "
<< "are supported currently.\n"; } } while (false)
787 << "are supported currently.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Only inner loops with induction or reduction PHI nodes "
<< "are supported currently.\n"; } } while (false)
;
788 ORE->emit([&]() {
789 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "UnsupportedPHIInner",
790 InnerLoop->getStartLoc(),
791 InnerLoop->getHeader())
792 << "Only inner loops with induction or reduction PHI nodes can be"
793 " interchange currently.";
794 });
795 return true;
796 }
797
798 // TODO: Currently we handle only loops with 1 induction variable.
799 if (Inductions.size() != 1) {
800 DEBUG(dbgs() << "We currently only support loops with 1 induction variable."do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "We currently only support loops with 1 induction variable."
<< "Failed to interchange due to current limitation\n"
; } } while (false)
801 << "Failed to interchange due to current limitation\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "We currently only support loops with 1 induction variable."
<< "Failed to interchange due to current limitation\n"
; } } while (false)
;
802 ORE->emit([&]() {
803 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "MultiInductionInner",
804 InnerLoop->getStartLoc(),
805 InnerLoop->getHeader())
806 << "Only inner loops with 1 induction variable can be "
807 "interchanged currently.";
808 });
809 return true;
810 }
811 if (Reductions.size() > 0)
812 InnerLoopHasReduction = true;
813
814 InnerInductionVar = Inductions.pop_back_val();
815 Reductions.clear();
816 if (!findInductionAndReductions(OuterLoop, Inductions, Reductions)) {
817 DEBUG(dbgs() << "Only outer loops with induction or reduction PHI nodes "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Only outer loops with induction or reduction PHI nodes "
<< "are supported currently.\n"; } } while (false)
818 << "are supported currently.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Only outer loops with induction or reduction PHI nodes "
<< "are supported currently.\n"; } } while (false)
;
819 ORE->emit([&]() {
820 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "UnsupportedPHIOuter",
821 OuterLoop->getStartLoc(),
822 OuterLoop->getHeader())
823 << "Only outer loops with induction or reduction PHI nodes can be"
824 " interchanged currently.";
825 });
826 return true;
827 }
828
829 // Outer loop cannot have reduction because then loops will not be tightly
830 // nested.
831 if (!Reductions.empty()) {
832 DEBUG(dbgs() << "Outer loops with reductions are not supported "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Outer loops with reductions are not supported "
<< "currently.\n"; } } while (false)
833 << "currently.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Outer loops with reductions are not supported "
<< "currently.\n"; } } while (false)
;
834 ORE->emit([&]() {
835 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "ReductionsOuter",
836 OuterLoop->getStartLoc(),
837 OuterLoop->getHeader())
838 << "Outer loops with reductions cannot be interchangeed "
839 "currently.";
840 });
841 return true;
842 }
843 // TODO: Currently we handle only loops with 1 induction variable.
844 if (Inductions.size() != 1) {
845 DEBUG(dbgs() << "Loops with more than 1 induction variables are not "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops with more than 1 induction variables are not "
<< "supported currently.\n"; } } while (false)
846 << "supported currently.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops with more than 1 induction variables are not "
<< "supported currently.\n"; } } while (false)
;
847 ORE->emit([&]() {
848 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "MultiIndutionOuter",
849 OuterLoop->getStartLoc(),
850 OuterLoop->getHeader())
851 << "Only outer loops with 1 induction variable can be "
852 "interchanged currently.";
853 });
854 return true;
855 }
856
857 // TODO: Triangular loops are not handled for now.
858 if (!isLoopStructureUnderstood(InnerInductionVar)) {
859 DEBUG(dbgs() << "Loop structure not understood by pass\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loop structure not understood by pass\n"
; } } while (false)
;
860 ORE->emit([&]() {
861 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "UnsupportedStructureInner",
862 InnerLoop->getStartLoc(),
863 InnerLoop->getHeader())
864 << "Inner loop structure not understood currently.";
865 });
866 return true;
867 }
868
869 // TODO: We only handle LCSSA PHI's corresponding to reduction for now.
870 BasicBlock *LoopExitBlock =
871 getLoopLatchExitBlock(OuterLoopLatch, OuterLoopHeader);
872 if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, true)) {
873 DEBUG(dbgs() << "Can only handle LCSSA PHIs in outer loops currently.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Can only handle LCSSA PHIs in outer loops currently.\n"
; } } while (false)
;
874 ORE->emit([&]() {
875 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "NoLCSSAPHIOuter",
876 OuterLoop->getStartLoc(),
877 OuterLoop->getHeader())
878 << "Only outer loops with LCSSA PHIs can be interchange "
879 "currently.";
880 });
881 return true;
882 }
883
884 LoopExitBlock = getLoopLatchExitBlock(InnerLoopLatch, InnerLoopHeader);
885 if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, false)) {
886 DEBUG(dbgs() << "Can only handle LCSSA PHIs in inner loops currently.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Can only handle LCSSA PHIs in inner loops currently.\n"
; } } while (false)
;
887 ORE->emit([&]() {
888 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "NoLCSSAPHIOuterInner",
889 InnerLoop->getStartLoc(),
890 InnerLoop->getHeader())
891 << "Only inner loops with LCSSA PHIs can be interchange "
892 "currently.";
893 });
894 return true;
895 }
896
897 // TODO: Current limitation: Since we split the inner loop latch at the point
898 // were induction variable is incremented (induction.next); We cannot have
899 // more than 1 user of induction.next since it would result in broken code
900 // after split.
901 // e.g.
902 // for(i=0;i<N;i++) {
903 // for(j = 0;j<M;j++) {
904 // A[j+1][i+2] = A[j][i]+k;
905 // }
906 // }
907 Instruction *InnerIndexVarInc = nullptr;
908 if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader)
909 InnerIndexVarInc =
910 dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1));
911 else
912 InnerIndexVarInc =
913 dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0));
914
915 if (!InnerIndexVarInc) {
916 DEBUG(dbgs() << "Did not find an instruction to increment the induction "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Did not find an instruction to increment the induction "
<< "variable.\n"; } } while (false)
917 << "variable.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Did not find an instruction to increment the induction "
<< "variable.\n"; } } while (false)
;
918 ORE->emit([&]() {
919 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "NoIncrementInInner",
920 InnerLoop->getStartLoc(),
921 InnerLoop->getHeader())
922 << "The inner loop does not increment the induction variable.";
923 });
924 return true;
925 }
926
927 // Since we split the inner loop latch on this induction variable. Make sure
928 // we do not have any instruction between the induction variable and branch
929 // instruction.
930
931 bool FoundInduction = false;
932 for (const Instruction &I : llvm::reverse(*InnerLoopLatch)) {
933 if (isa<BranchInst>(I) || isa<CmpInst>(I) || isa<TruncInst>(I) ||
934 isa<ZExtInst>(I))
935 continue;
936
937 // We found an instruction. If this is not induction variable then it is not
938 // safe to split this loop latch.
939 if (!I.isIdenticalTo(InnerIndexVarInc)) {
940 DEBUG(dbgs() << "Found unsupported instructions between induction "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Found unsupported instructions between induction "
<< "variable increment and branch.\n"; } } while (false
)
941 << "variable increment and branch.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Found unsupported instructions between induction "
<< "variable increment and branch.\n"; } } while (false
)
;
942 ORE->emit([&]() {
943 return OptimizationRemarkMissed(
944 DEBUG_TYPE"loop-interchange", "UnsupportedInsBetweenInduction",
945 InnerLoop->getStartLoc(), InnerLoop->getHeader())
946 << "Found unsupported instruction between induction variable "
947 "increment and branch.";
948 });
949 return true;
950 }
951
952 FoundInduction = true;
953 break;
954 }
955 // The loop latch ended and we didn't find the induction variable return as
956 // current limitation.
957 if (!FoundInduction) {
958 DEBUG(dbgs() << "Did not find the induction variable.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Did not find the induction variable.\n"
; } } while (false)
;
959 ORE->emit([&]() {
960 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "NoIndutionVariable",
961 InnerLoop->getStartLoc(),
962 InnerLoop->getHeader())
963 << "Did not find the induction variable.";
964 });
965 return true;
966 }
967 return false;
968}
969
970bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
971 unsigned OuterLoopId,
972 CharMatrix &DepMatrix) {
973 if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
974 DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopIddo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Failed interchange InnerLoopId = "
<< InnerLoopId << " and OuterLoopId = " <<
OuterLoopId << " due to dependence\n"; } } while (false
)
975 << " and OuterLoopId = " << OuterLoopIddo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Failed interchange InnerLoopId = "
<< InnerLoopId << " and OuterLoopId = " <<
OuterLoopId << " due to dependence\n"; } } while (false
)
976 << " due to dependence\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Failed interchange InnerLoopId = "
<< InnerLoopId << " and OuterLoopId = " <<
OuterLoopId << " due to dependence\n"; } } while (false
)
;
977 ORE->emit([&]() {
978 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "Dependence",
979 InnerLoop->getStartLoc(),
980 InnerLoop->getHeader())
981 << "Cannot interchange loops due to dependences.";
982 });
983 return false;
984 }
985
986 // Check if outer and inner loop contain legal instructions only.
987 for (auto *BB : OuterLoop->blocks())
988 for (Instruction &I : *BB)
989 if (CallInst *CI = dyn_cast<CallInst>(&I)) {
990 // readnone functions do not prevent interchanging.
991 if (CI->doesNotReadMemory())
992 continue;
993 DEBUG(dbgs() << "Loops with call instructions cannot be interchanged "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops with call instructions cannot be interchanged "
<< "safely."; } } while (false)
994 << "safely.")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops with call instructions cannot be interchanged "
<< "safely."; } } while (false)
;
995 ORE->emit([&]() {
996 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "CallInst",
997 CI->getDebugLoc(),
998 CI->getParent())
999 << "Cannot interchange loops due to call instruction.";
1000 });
1001
1002 return false;
1003 }
1004
1005 // Create unique Preheaders if we already do not have one.
1006 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1007 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1008
1009 // Create a unique outer preheader -
1010 // 1) If OuterLoop preheader is not present.
1011 // 2) If OuterLoop Preheader is same as OuterLoop Header
1012 // 3) If OuterLoop Preheader is same as Header of the previous loop.
1013 // 4) If OuterLoop Preheader is Entry node.
1014 if (!OuterLoopPreHeader || OuterLoopPreHeader == OuterLoop->getHeader() ||
1015 isa<PHINode>(OuterLoopPreHeader->begin()) ||
1016 !OuterLoopPreHeader->getUniquePredecessor()) {
1017 OuterLoopPreHeader =
1018 InsertPreheaderForLoop(OuterLoop, DT, LI, PreserveLCSSA);
1019 }
1020
1021 if (!InnerLoopPreHeader || InnerLoopPreHeader == InnerLoop->getHeader() ||
1022 InnerLoopPreHeader == OuterLoop->getHeader()) {
1023 InnerLoopPreHeader =
1024 InsertPreheaderForLoop(InnerLoop, DT, LI, PreserveLCSSA);
1025 }
1026
1027 // TODO: The loops could not be interchanged due to current limitations in the
1028 // transform module.
1029 if (currentLimitations()) {
1030 DEBUG(dbgs() << "Not legal because of current transform limitation\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Not legal because of current transform limitation\n"
; } } while (false)
;
1031 return false;
1032 }
1033
1034 // Check if the loops are tightly nested.
1035 if (!tightlyNested(OuterLoop, InnerLoop)) {
1036 DEBUG(dbgs() << "Loops not tightly nested\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops not tightly nested\n"
; } } while (false)
;
1037 ORE->emit([&]() {
1038 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "NotTightlyNested",
1039 InnerLoop->getStartLoc(),
1040 InnerLoop->getHeader())
1041 << "Cannot interchange loops because they are not tightly "
1042 "nested.";
1043 });
1044 return false;
1045 }
1046
1047 return true;
1048}
1049
1050int LoopInterchangeProfitability::getInstrOrderCost() {
1051 unsigned GoodOrder, BadOrder;
1052 BadOrder = GoodOrder = 0;
1053 for (BasicBlock *BB : InnerLoop->blocks()) {
1054 for (Instruction &Ins : *BB) {
1055 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) {
1056 unsigned NumOp = GEP->getNumOperands();
1057 bool FoundInnerInduction = false;
1058 bool FoundOuterInduction = false;
1059 for (unsigned i = 0; i < NumOp; ++i) {
1060 const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i));
1061 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal);
1062 if (!AR)
1063 continue;
1064
1065 // If we find the inner induction after an outer induction e.g.
1066 // for(int i=0;i<N;i++)
1067 // for(int j=0;j<N;j++)
1068 // A[i][j] = A[i-1][j-1]+k;
1069 // then it is a good order.
1070 if (AR->getLoop() == InnerLoop) {
1071 // We found an InnerLoop induction after OuterLoop induction. It is
1072 // a good order.
1073 FoundInnerInduction = true;
1074 if (FoundOuterInduction) {
1075 GoodOrder++;
1076 break;
1077 }
1078 }
1079 // If we find the outer induction after an inner induction e.g.
1080 // for(int i=0;i<N;i++)
1081 // for(int j=0;j<N;j++)
1082 // A[j][i] = A[j-1][i-1]+k;
1083 // then it is a bad order.
1084 if (AR->getLoop() == OuterLoop) {
1085 // We found an OuterLoop induction after InnerLoop induction. It is
1086 // a bad order.
1087 FoundOuterInduction = true;
1088 if (FoundInnerInduction) {
1089 BadOrder++;
1090 break;
1091 }
1092 }
1093 }
1094 }
1095 }
1096 }
1097 return GoodOrder - BadOrder;
1098}
1099
1100static bool isProfitableForVectorization(unsigned InnerLoopId,
1101 unsigned OuterLoopId,
1102 CharMatrix &DepMatrix) {
1103 // TODO: Improve this heuristic to catch more cases.
1104 // If the inner loop is loop independent or doesn't carry any dependency it is
1105 // profitable to move this to outer position.
1106 for (auto &Row : DepMatrix) {
1107 if (Row[InnerLoopId] != 'S' && Row[InnerLoopId] != 'I')
1108 return false;
1109 // TODO: We need to improve this heuristic.
1110 if (Row[OuterLoopId] != '=')
1111 return false;
1112 }
1113 // If outer loop has dependence and inner loop is loop independent then it is
1114 // profitable to interchange to enable parallelism.
1115 return true;
1116}
1117
1118bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId,
1119 unsigned OuterLoopId,
1120 CharMatrix &DepMatrix) {
1121 // TODO: Add better profitability checks.
1122 // e.g
1123 // 1) Construct dependency matrix and move the one with no loop carried dep
1124 // inside to enable vectorization.
1125
1126 // This is rough cost estimation algorithm. It counts the good and bad order
1127 // of induction variables in the instruction and allows reordering if number
1128 // of bad orders is more than good.
1129 int Cost = getInstrOrderCost();
1130 DEBUG(dbgs() << "Cost = " << Cost << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Cost = " << Cost
<< "\n"; } } while (false)
;
1131 if (Cost < -LoopInterchangeCostThreshold)
1132 return true;
1133
1134 // It is not profitable as per current cache profitability model. But check if
1135 // we can move this loop outside to improve parallelism.
1136 if (isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix))
1137 return true;
1138
1139 ORE->emit([&]() {
1140 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "InterchangeNotProfitable",
1141 InnerLoop->getStartLoc(),
1142 InnerLoop->getHeader())
1143 << "Interchanging loops is too costly (cost="
1144 << ore::NV("Cost", Cost) << ", threshold="
1145 << ore::NV("Threshold", LoopInterchangeCostThreshold)
1146 << ") and it does not improve parallelism.";
1147 });
1148 return false;
1149}
1150
1151void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
1152 Loop *InnerLoop) {
1153 for (Loop::iterator I = OuterLoop->begin(), E = OuterLoop->end(); I != E;
1154 ++I) {
1155 if (*I == InnerLoop) {
1156 OuterLoop->removeChildLoop(I);
1157 return;
1158 }
1159 }
1160 llvm_unreachable("Couldn't find loop")::llvm::llvm_unreachable_internal("Couldn't find loop", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1160)
;
1161}
1162
1163/// Update LoopInfo, after interchanging. NewInner and NewOuter refer to the
1164/// new inner and outer loop after interchanging: NewInner is the original
1165/// outer loop and NewOuter is the original inner loop.
1166///
1167/// Before interchanging, we have the following structure
1168/// Outer preheader
1169// Outer header
1170// Inner preheader
1171// Inner header
1172// Inner body
1173// Inner latch
1174// outer bbs
1175// Outer latch
1176//
1177// After interchanging:
1178// Inner preheader
1179// Inner header
1180// Outer preheader
1181// Outer header
1182// Inner body
1183// outer bbs
1184// Outer latch
1185// Inner latch
1186void LoopInterchangeTransform::restructureLoops(
1187 Loop *NewInner, Loop *NewOuter, BasicBlock *OrigInnerPreHeader,
1188 BasicBlock *OrigOuterPreHeader) {
1189 Loop *OuterLoopParent = OuterLoop->getParentLoop();
1190 // The original inner loop preheader moves from the new inner loop to
1191 // the parent loop, if there is one.
1192 NewInner->removeBlockFromLoop(OrigInnerPreHeader);
1193 LI->changeLoopFor(OrigInnerPreHeader, OuterLoopParent);
1194
1195 // Switch the loop levels.
1196 if (OuterLoopParent) {
1197 // Remove the loop from its parent loop.
1198 removeChildLoop(OuterLoopParent, NewInner);
1199 removeChildLoop(NewInner, NewOuter);
1200 OuterLoopParent->addChildLoop(NewOuter);
1201 } else {
1202 removeChildLoop(NewInner, NewOuter);
1203 LI->changeTopLevelLoop(NewInner, NewOuter);
1204 }
1205 while (!NewOuter->empty())
1206 NewInner->addChildLoop(NewOuter->removeChildLoop(NewOuter->begin()));
1207 NewOuter->addChildLoop(NewInner);
1208
1209 // BBs from the original inner loop.
1210 SmallVector<BasicBlock *, 8> OrigInnerBBs(NewOuter->blocks());
1211
1212 // Add BBs from the original outer loop to the original inner loop (excluding
1213 // BBs already in inner loop)
1214 for (BasicBlock *BB : NewInner->blocks())
1215 if (LI->getLoopFor(BB) == NewInner)
1216 NewOuter->addBlockEntry(BB);
1217
1218 // Now remove inner loop header and latch from the new inner loop and move
1219 // other BBs (the loop body) to the new inner loop.
1220 BasicBlock *OuterHeader = NewOuter->getHeader();
1221 BasicBlock *OuterLatch = NewOuter->getLoopLatch();
1222 for (BasicBlock *BB : OrigInnerBBs) {
1223 // Remove the new outer loop header and latch from the new inner loop.
1224 if (BB == OuterHeader || BB == OuterLatch)
1225 NewInner->removeBlockFromLoop(BB);
1226 else
1227 LI->changeLoopFor(BB, NewInner);
1228 }
1229
1230 // The preheader of the original outer loop becomes part of the new
1231 // outer loop.
1232 NewOuter->addBlockEntry(OrigOuterPreHeader);
1233 LI->changeLoopFor(OrigOuterPreHeader, NewOuter);
1234}
1235
1236bool LoopInterchangeTransform::transform() {
1237 bool Transformed = false;
1238 Instruction *InnerIndexVar;
1239
1240 if (InnerLoop->getSubLoops().empty()) {
1241 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1242 DEBUG(dbgs() << "Calling Split Inner Loop\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Calling Split Inner Loop\n"
; } } while (false)
;
1243 PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
1244 if (!InductionPHI) {
1245 DEBUG(dbgs() << "Failed to find the point to split loop latch \n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Failed to find the point to split loop latch \n"
; } } while (false)
;
1246 return false;
1247 }
1248
1249 if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
1250 InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
1251 else
1252 InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
1253
1254 // Ensure that InductionPHI is the first Phi node as required by
1255 // splitInnerLoopHeader
1256 if (&InductionPHI->getParent()->front() != InductionPHI)
1257 InductionPHI->moveBefore(&InductionPHI->getParent()->front());
1258
1259 // Split at the place were the induction variable is
1260 // incremented/decremented.
1261 // TODO: This splitting logic may not work always. Fix this.
1262 splitInnerLoopLatch(InnerIndexVar);
1263 DEBUG(dbgs() << "splitInnerLoopLatch done\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "splitInnerLoopLatch done\n"
; } } while (false)
;
1264
1265 // Splits the inner loops phi nodes out into a separate basic block.
1266 splitInnerLoopHeader();
1267 DEBUG(dbgs() << "splitInnerLoopHeader done\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "splitInnerLoopHeader done\n"
; } } while (false)
;
1268 }
1269
1270 Transformed |= adjustLoopLinks();
1271 if (!Transformed) {
1272 DEBUG(dbgs() << "adjustLoopLinks failed\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "adjustLoopLinks failed\n"
; } } while (false)
;
1273 return false;
1274 }
1275
1276 return true;
1277}
1278
1279void LoopInterchangeTransform::splitInnerLoopLatch(Instruction *Inc) {
1280 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1281 BasicBlock *InnerLoopLatchPred = InnerLoopLatch;
1282 InnerLoopLatch = SplitBlock(InnerLoopLatchPred, Inc, DT, LI);
Value stored to 'InnerLoopLatch' is never read
1283}
1284
1285void LoopInterchangeTransform::splitInnerLoopHeader() {
1286 // Split the inner loop header out. Here make sure that the reduction PHI's
1287 // stay in the innerloop body.
1288 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1289 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1290 SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI);
1291 if (InnerLoopHasReduction) {
1292 // Adjust Reduction PHI's in the block. The induction PHI must be the first
1293 // PHI in InnerLoopHeader for this to work.
1294 SmallVector<PHINode *, 8> PHIVec;
1295 for (auto I = std::next(InnerLoopHeader->begin()); isa<PHINode>(I); ++I) {
1296 PHINode *PHI = dyn_cast<PHINode>(I);
1297 Value *V = PHI->getIncomingValueForBlock(InnerLoopPreHeader);
1298 PHI->replaceAllUsesWith(V);
1299 PHIVec.push_back((PHI));
1300 }
1301 for (PHINode *P : PHIVec) {
1302 P->eraseFromParent();
1303 }
1304 }
1305
1306 DEBUG(dbgs() << "Output of splitInnerLoopHeader InnerLoopHeaderSucc & "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Output of splitInnerLoopHeader InnerLoopHeaderSucc & "
"InnerLoopHeader\n"; } } while (false)
1307 "InnerLoopHeader\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Output of splitInnerLoopHeader InnerLoopHeaderSucc & "
"InnerLoopHeader\n"; } } while (false)
;
1308}
1309
1310/// \brief Move all instructions except the terminator from FromBB right before
1311/// InsertBefore
1312static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
1313 auto &ToList = InsertBefore->getParent()->getInstList();
1314 auto &FromList = FromBB->getInstList();
1315
1316 ToList.splice(InsertBefore->getIterator(), FromList, FromList.begin(),
1317 FromBB->getTerminator()->getIterator());
1318}
1319
1320void LoopInterchangeTransform::updateIncomingBlock(BasicBlock *CurrBlock,
1321 BasicBlock *OldPred,
1322 BasicBlock *NewPred) {
1323 for (auto I = CurrBlock->begin(); isa<PHINode>(I); ++I) {
1324 PHINode *PHI = cast<PHINode>(I);
1325 unsigned Num = PHI->getNumIncomingValues();
1326 for (unsigned i = 0; i < Num; ++i) {
1327 if (PHI->getIncomingBlock(i) == OldPred)
1328 PHI->setIncomingBlock(i, NewPred);
1329 }
1330 }
1331}
1332
1333/// \brief Update BI to jump to NewBB instead of OldBB. Records updates to
1334/// the dominator tree in DTUpdates, if DT should be preserved.
1335static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB,
1336 BasicBlock *NewBB,
1337 std::vector<DominatorTree::UpdateType> &DTUpdates) {
1338 assert(llvm::count_if(BI->successors(),(static_cast <bool> (llvm::count_if(BI->successors()
, [OldBB](BasicBlock *BB) { return BB == OldBB; }) < 2 &&
"BI must jump to OldBB at most once.") ? void (0) : __assert_fail
("llvm::count_if(BI->successors(), [OldBB](BasicBlock *BB) { return BB == OldBB; }) < 2 && \"BI must jump to OldBB at most once.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1340, __extension__ __PRETTY_FUNCTION__))
1339 [OldBB](BasicBlock *BB) { return BB == OldBB; }) < 2 &&(static_cast <bool> (llvm::count_if(BI->successors()
, [OldBB](BasicBlock *BB) { return BB == OldBB; }) < 2 &&
"BI must jump to OldBB at most once.") ? void (0) : __assert_fail
("llvm::count_if(BI->successors(), [OldBB](BasicBlock *BB) { return BB == OldBB; }) < 2 && \"BI must jump to OldBB at most once.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1340, __extension__ __PRETTY_FUNCTION__))
1340 "BI must jump to OldBB at most once.")(static_cast <bool> (llvm::count_if(BI->successors()
, [OldBB](BasicBlock *BB) { return BB == OldBB; }) < 2 &&
"BI must jump to OldBB at most once.") ? void (0) : __assert_fail
("llvm::count_if(BI->successors(), [OldBB](BasicBlock *BB) { return BB == OldBB; }) < 2 && \"BI must jump to OldBB at most once.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1340, __extension__ __PRETTY_FUNCTION__))
;
1341 for (unsigned i = 0, e = BI->getNumSuccessors(); i < e; ++i) {
1342 if (BI->getSuccessor(i) == OldBB) {
1343 BI->setSuccessor(i, NewBB);
1344
1345 DTUpdates.push_back(
1346 {DominatorTree::UpdateKind::Insert, BI->getParent(), NewBB});
1347 DTUpdates.push_back(
1348 {DominatorTree::UpdateKind::Delete, BI->getParent(), OldBB});
1349 break;
1350 }
1351 }
1352}
1353
1354bool LoopInterchangeTransform::adjustLoopBranches() {
1355 DEBUG(dbgs() << "adjustLoopBranches called\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "adjustLoopBranches called\n"
; } } while (false)
;
1356 std::vector<DominatorTree::UpdateType> DTUpdates;
1357
1358 // Adjust the loop preheader
1359 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1360 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1361 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1362 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1363 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1364 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1365 BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
1366 BasicBlock *InnerLoopLatchPredecessor =
1367 InnerLoopLatch->getUniquePredecessor();
1368 BasicBlock *InnerLoopLatchSuccessor;
1369 BasicBlock *OuterLoopLatchSuccessor;
1370
1371 BranchInst *OuterLoopLatchBI =
1372 dyn_cast<BranchInst>(OuterLoopLatch->getTerminator());
1373 BranchInst *InnerLoopLatchBI =
1374 dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
1375 BranchInst *OuterLoopHeaderBI =
1376 dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
1377 BranchInst *InnerLoopHeaderBI =
1378 dyn_cast<BranchInst>(InnerLoopHeader->getTerminator());
1379
1380 if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||
1381 !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||
1382 !InnerLoopHeaderBI)
1383 return false;
1384
1385 BranchInst *InnerLoopLatchPredecessorBI =
1386 dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator());
1387 BranchInst *OuterLoopPredecessorBI =
1388 dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator());
1389
1390 if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
1391 return false;
1392 BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
1393 if (!InnerLoopHeaderSuccessor)
1394 return false;
1395
1396 // Adjust Loop Preheader and headers
1397 updateSuccessor(OuterLoopPredecessorBI, OuterLoopPreHeader,
1398 InnerLoopPreHeader, DTUpdates);
1399 updateSuccessor(OuterLoopHeaderBI, OuterLoopLatch, LoopExit, DTUpdates);
1400 updateSuccessor(OuterLoopHeaderBI, InnerLoopPreHeader,
1401 InnerLoopHeaderSuccessor, DTUpdates);
1402
1403 // Adjust reduction PHI's now that the incoming block has changed.
1404 updateIncomingBlock(InnerLoopHeaderSuccessor, InnerLoopHeader,
1405 OuterLoopHeader);
1406
1407 updateSuccessor(InnerLoopHeaderBI, InnerLoopHeaderSuccessor,
1408 OuterLoopPreHeader, DTUpdates);
1409
1410 // -------------Adjust loop latches-----------
1411 if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
1412 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
1413 else
1414 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
1415
1416 updateSuccessor(InnerLoopLatchPredecessorBI, InnerLoopLatch,
1417 InnerLoopLatchSuccessor, DTUpdates);
1418
1419 // Adjust PHI nodes in InnerLoopLatchSuccessor. Update all uses of PHI with
1420 // the value and remove this PHI node from inner loop.
1421 SmallVector<PHINode *, 8> LcssaVec;
1422 for (auto I = InnerLoopLatchSuccessor->begin(); isa<PHINode>(I); ++I) {
1423 PHINode *LcssaPhi = cast<PHINode>(I);
1424 LcssaVec.push_back(LcssaPhi);
1425 }
1426 for (PHINode *P : LcssaVec) {
1427 Value *Incoming = P->getIncomingValueForBlock(InnerLoopLatch);
1428 P->replaceAllUsesWith(Incoming);
1429 P->eraseFromParent();
1430 }
1431
1432 if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
1433 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
1434 else
1435 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
1436
1437 updateSuccessor(InnerLoopLatchBI, InnerLoopLatchSuccessor,
1438 OuterLoopLatchSuccessor, DTUpdates);
1439 updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,
1440 DTUpdates);
1441
1442 updateIncomingBlock(OuterLoopLatchSuccessor, OuterLoopLatch, InnerLoopLatch);
1443
1444 DT->applyUpdates(DTUpdates);
1445 restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader,
1446 OuterLoopPreHeader);
1447
1448 return true;
1449}
1450
1451void LoopInterchangeTransform::adjustLoopPreheaders() {
1452 // We have interchanged the preheaders so we need to interchange the data in
1453 // the preheader as well.
1454 // This is because the content of inner preheader was previously executed
1455 // inside the outer loop.
1456 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1457 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1458 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1459 BranchInst *InnerTermBI =
1460 cast<BranchInst>(InnerLoopPreHeader->getTerminator());
1461
1462 // These instructions should now be executed inside the loop.
1463 // Move instruction into a new block after outer header.
1464 moveBBContents(InnerLoopPreHeader, OuterLoopHeader->getTerminator());
1465 // These instructions were not executed previously in the loop so move them to
1466 // the older inner loop preheader.
1467 moveBBContents(OuterLoopPreHeader, InnerTermBI);
1468}
1469
1470bool LoopInterchangeTransform::adjustLoopLinks() {
1471 // Adjust all branches in the inner and outer loop.
1472 bool Changed = adjustLoopBranches();
1473 if (Changed)
1474 adjustLoopPreheaders();
1475 return Changed;
1476}
1477
1478char LoopInterchange::ID = 0;
1479
1480INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",static void *initializeLoopInterchangePassOnce(PassRegistry &
Registry) {
1481 "Interchanges loops for cache reuse", false, false)static void *initializeLoopInterchangePassOnce(PassRegistry &
Registry) {
1482INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
1483INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)initializeDependenceAnalysisWrapperPassPass(Registry);
1484INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
1485INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)initializeScalarEvolutionWrapperPassPass(Registry);
1486INITIALIZE_PASS_DEPENDENCY(LoopSimplify)initializeLoopSimplifyPass(Registry);
1487INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)initializeLCSSAWrapperPassPass(Registry);
1488INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)initializeLoopInfoWrapperPassPass(Registry);
1489INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)initializeOptimizationRemarkEmitterWrapperPassPass(Registry);
1490
1491INITIALIZE_PASS_END(LoopInterchange, "loop-interchange",PassInfo *PI = new PassInfo( "Interchanges loops for cache reuse"
, "loop-interchange", &LoopInterchange::ID, PassInfo::NormalCtor_t
(callDefaultCtor<LoopInterchange>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeLoopInterchangePassFlag; void llvm::initializeLoopInterchangePass
(PassRegistry &Registry) { llvm::call_once(InitializeLoopInterchangePassFlag
, initializeLoopInterchangePassOnce, std::ref(Registry)); }
1492 "Interchanges loops for cache reuse", false, false)PassInfo *PI = new PassInfo( "Interchanges loops for cache reuse"
, "loop-interchange", &LoopInterchange::ID, PassInfo::NormalCtor_t
(callDefaultCtor<LoopInterchange>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeLoopInterchangePassFlag; void llvm::initializeLoopInterchangePass
(PassRegistry &Registry) { llvm::call_once(InitializeLoopInterchangePassFlag
, initializeLoopInterchangePassOnce, std::ref(Registry)); }
1493
1494Pass *llvm::createLoopInterchangePass() { return new LoopInterchange(); }