Bug Summary

File:llvm/lib/Transforms/Scalar/LoopInterchange.cpp
Warning:line 669, column 8
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -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-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 -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/build-llvm/lib/Transforms/Scalar -resource-dir /usr/lib/llvm-13/lib/clang/13.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/build-llvm/include -I /build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/include -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-13/lib/clang/13.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/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-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-06-13-111025-38230-1 -x c++ /build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
1//===- LoopInterchange.cpp - Loop interchange 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 handles loop interchange transform.
10// This pass interchanges loops to provide a more cache-friendly memory access
11// patterns.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Transforms/Scalar/LoopInterchange.h"
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/DependenceAnalysis.h"
21#include "llvm/Analysis/LoopInfo.h"
22#include "llvm/Analysis/LoopNestAnalysis.h"
23#include "llvm/Analysis/LoopPass.h"
24#include "llvm/Analysis/OptimizationRemarkEmitter.h"
25#include "llvm/Analysis/ScalarEvolution.h"
26#include "llvm/Analysis/ScalarEvolutionExpressions.h"
27#include "llvm/IR/BasicBlock.h"
28#include "llvm/IR/Constants.h"
29#include "llvm/IR/DiagnosticInfo.h"
30#include "llvm/IR/Dominators.h"
31#include "llvm/IR/Function.h"
32#include "llvm/IR/IRBuilder.h"
33#include "llvm/IR/InstrTypes.h"
34#include "llvm/IR/Instruction.h"
35#include "llvm/IR/Instructions.h"
36#include "llvm/IR/Type.h"
37#include "llvm/IR/User.h"
38#include "llvm/IR/Value.h"
39#include "llvm/InitializePasses.h"
40#include "llvm/Pass.h"
41#include "llvm/Support/Casting.h"
42#include "llvm/Support/CommandLine.h"
43#include "llvm/Support/Debug.h"
44#include "llvm/Support/ErrorHandling.h"
45#include "llvm/Support/raw_ostream.h"
46#include "llvm/Transforms/Scalar.h"
47#include "llvm/Transforms/Utils.h"
48#include "llvm/Transforms/Utils/BasicBlockUtils.h"
49#include "llvm/Transforms/Utils/LoopUtils.h"
50#include <cassert>
51#include <utility>
52#include <vector>
53
54using namespace llvm;
55
56#define DEBUG_TYPE"loop-interchange" "loop-interchange"
57
58STATISTIC(LoopsInterchanged, "Number of loops interchanged")static llvm::Statistic LoopsInterchanged = {"loop-interchange"
, "LoopsInterchanged", "Number of loops interchanged"}
;
59
60static cl::opt<int> LoopInterchangeCostThreshold(
61 "loop-interchange-threshold", cl::init(0), cl::Hidden,
62 cl::desc("Interchange if you gain more than this number"));
63
64namespace {
65
66using LoopVector = SmallVector<Loop *, 8>;
67
68// TODO: Check if we can use a sparse matrix here.
69using CharMatrix = std::vector<std::vector<char>>;
70
71} // end anonymous namespace
72
73// Maximum number of dependencies that can be handled in the dependency matrix.
74static const unsigned MaxMemInstrCount = 100;
75
76// Maximum loop depth supported.
77static const unsigned MaxLoopNestDepth = 10;
78
79#ifdef DUMP_DEP_MATRICIES
80static void printDepMatrix(CharMatrix &DepMatrix) {
81 for (auto &Row : DepMatrix) {
82 for (auto D : Row)
83 LLVM_DEBUG(dbgs() << D << " ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << D << " "; } } while
(false)
;
84 LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "\n"; } } while (false
)
;
85 }
86}
87#endif
88
89static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
90 Loop *L, DependenceInfo *DI) {
91 using ValueVector = SmallVector<Value *, 16>;
92
93 ValueVector MemInstr;
94
95 // For each block.
96 for (BasicBlock *BB : L->blocks()) {
97 // Scan the BB and collect legal loads and stores.
98 for (Instruction &I : *BB) {
99 if (!isa<Instruction>(I))
100 return false;
101 if (auto *Ld = dyn_cast<LoadInst>(&I)) {
102 if (!Ld->isSimple())
103 return false;
104 MemInstr.push_back(&I);
105 } else if (auto *St = dyn_cast<StoreInst>(&I)) {
106 if (!St->isSimple())
107 return false;
108 MemInstr.push_back(&I);
109 }
110 }
111 }
112
113 LLVM_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)
114 << " 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)
;
115
116 ValueVector::iterator I, IE, J, JE;
117
118 for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
119 for (J = I, JE = MemInstr.end(); J != JE; ++J) {
120 std::vector<char> Dep;
121 Instruction *Src = cast<Instruction>(*I);
122 Instruction *Dst = cast<Instruction>(*J);
123 if (Src == Dst)
124 continue;
125 // Ignore Input dependencies.
126 if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
127 continue;
128 // Track Output, Flow, and Anti dependencies.
129 if (auto D = DI->depends(Src, Dst, true)) {
130 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-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 130, __extension__ __PRETTY_FUNCTION__))
;
131 LLVM_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)
132 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)
133 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)
134 << " 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)
135 << " 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)
;
136 unsigned Levels = D->getLevels();
137 char Direction;
138 for (unsigned II = 1; II <= Levels; ++II) {
139 const SCEV *Distance = D->getDistance(II);
140 const SCEVConstant *SCEVConst =
141 dyn_cast_or_null<SCEVConstant>(Distance);
142 if (SCEVConst) {
143 const ConstantInt *CI = SCEVConst->getValue();
144 if (CI->isNegative())
145 Direction = '<';
146 else if (CI->isZero())
147 Direction = '=';
148 else
149 Direction = '>';
150 Dep.push_back(Direction);
151 } else if (D->isScalar(II)) {
152 Direction = 'S';
153 Dep.push_back(Direction);
154 } else {
155 unsigned Dir = D->getDirection(II);
156 if (Dir == Dependence::DVEntry::LT ||
157 Dir == Dependence::DVEntry::LE)
158 Direction = '<';
159 else if (Dir == Dependence::DVEntry::GT ||
160 Dir == Dependence::DVEntry::GE)
161 Direction = '>';
162 else if (Dir == Dependence::DVEntry::EQ)
163 Direction = '=';
164 else
165 Direction = '*';
166 Dep.push_back(Direction);
167 }
168 }
169 while (Dep.size() != Level) {
170 Dep.push_back('I');
171 }
172
173 DepMatrix.push_back(Dep);
174 if (DepMatrix.size() > MaxMemInstrCount) {
175 LLVM_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)
176 << " dependencies inside loop\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Cannot handle more than "
<< MaxMemInstrCount << " dependencies inside loop\n"
; } } while (false)
;
177 return false;
178 }
179 }
180 }
181 }
182
183 return true;
184}
185
186// A loop is moved from index 'from' to an index 'to'. Update the Dependence
187// matrix by exchanging the two columns.
188static void interChangeDependencies(CharMatrix &DepMatrix, unsigned FromIndx,
189 unsigned ToIndx) {
190 for (unsigned I = 0, E = DepMatrix.size(); I < E; ++I)
191 std::swap(DepMatrix[I][ToIndx], DepMatrix[I][FromIndx]);
192}
193
194// Checks if outermost non '=','S'or'I' dependence in the dependence matrix is
195// '>'
196static bool isOuterMostDepPositive(CharMatrix &DepMatrix, unsigned Row,
197 unsigned Column) {
198 for (unsigned i = 0; i <= Column; ++i) {
199 if (DepMatrix[Row][i] == '<')
200 return false;
201 if (DepMatrix[Row][i] == '>')
202 return true;
203 }
204 // All dependencies were '=','S' or 'I'
205 return false;
206}
207
208// Checks if no dependence exist in the dependency matrix in Row before Column.
209static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row,
210 unsigned Column) {
211 for (unsigned i = 0; i < Column; ++i) {
212 if (DepMatrix[Row][i] != '=' && DepMatrix[Row][i] != 'S' &&
213 DepMatrix[Row][i] != 'I')
214 return false;
215 }
216 return true;
217}
218
219static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row,
220 unsigned OuterLoopId, char InnerDep,
221 char OuterDep) {
222 if (isOuterMostDepPositive(DepMatrix, Row, OuterLoopId))
223 return false;
224
225 if (InnerDep == OuterDep)
226 return true;
227
228 // It is legal to interchange if and only if after interchange no row has a
229 // '>' direction as the leftmost non-'='.
230
231 if (InnerDep == '=' || InnerDep == 'S' || InnerDep == 'I')
232 return true;
233
234 if (InnerDep == '<')
235 return true;
236
237 if (InnerDep == '>') {
238 // If OuterLoopId represents outermost loop then interchanging will make the
239 // 1st dependency as '>'
240 if (OuterLoopId == 0)
241 return false;
242
243 // If all dependencies before OuterloopId are '=','S'or 'I'. Then
244 // interchanging will result in this row having an outermost non '='
245 // dependency of '>'
246 if (!containsNoDependence(DepMatrix, Row, OuterLoopId))
247 return true;
248 }
249
250 return false;
251}
252
253// Checks if it is legal to interchange 2 loops.
254// [Theorem] A permutation of the loops in a perfect nest is legal if and only
255// if the direction matrix, after the same permutation is applied to its
256// columns, has no ">" direction as the leftmost non-"=" direction in any row.
257static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,
258 unsigned InnerLoopId,
259 unsigned OuterLoopId) {
260 unsigned NumRows = DepMatrix.size();
261 // For each row check if it is valid to interchange.
262 for (unsigned Row = 0; Row < NumRows; ++Row) {
263 char InnerDep = DepMatrix[Row][InnerLoopId];
264 char OuterDep = DepMatrix[Row][OuterLoopId];
265 if (InnerDep == '*' || OuterDep == '*')
266 return false;
267 if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep, OuterDep))
268 return false;
269 }
270 return true;
271}
272
273static LoopVector populateWorklist(Loop &L) {
274 LLVM_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)
275 << 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)
276 << 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)
;
277 LoopVector LoopList;
278 Loop *CurrentLoop = &L;
279 const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
280 while (!Vec->empty()) {
281 // The current loop has multiple subloops in it hence it is not tightly
282 // nested.
283 // Discard all loops above it added into Worklist.
284 if (Vec->size() != 1)
285 return {};
286
287 LoopList.push_back(CurrentLoop);
288 CurrentLoop = Vec->front();
289 Vec = &CurrentLoop->getSubLoops();
290 }
291 LoopList.push_back(CurrentLoop);
292 return LoopList;
293}
294
295static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) {
296 PHINode *InnerIndexVar = L->getCanonicalInductionVariable();
297 if (InnerIndexVar)
298 return InnerIndexVar;
299 if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr)
300 return nullptr;
301 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
302 PHINode *PhiVar = cast<PHINode>(I);
303 Type *PhiTy = PhiVar->getType();
304 if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
305 !PhiTy->isPointerTy())
306 return nullptr;
307 const SCEVAddRecExpr *AddRec =
308 dyn_cast<SCEVAddRecExpr>(SE->getSCEV(PhiVar));
309 if (!AddRec || !AddRec->isAffine())
310 continue;
311 const SCEV *Step = AddRec->getStepRecurrence(*SE);
312 if (!isa<SCEVConstant>(Step))
313 continue;
314 // Found the induction variable.
315 // FIXME: Handle loops with more than one induction variable. Note that,
316 // currently, legality makes sure we have only one induction variable.
317 return PhiVar;
318 }
319 return nullptr;
320}
321
322namespace {
323
324/// LoopInterchangeLegality checks if it is legal to interchange the loop.
325class LoopInterchangeLegality {
326public:
327 LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
328 OptimizationRemarkEmitter *ORE)
329 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
330
331 /// Check if the loops can be interchanged.
332 bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
333 CharMatrix &DepMatrix);
334
335 /// Check if the loop structure is understood. We do not handle triangular
336 /// loops for now.
337 bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
338
339 bool currentLimitations();
340
341 const SmallPtrSetImpl<PHINode *> &getOuterInnerReductions() const {
342 return OuterInnerReductions;
343 }
344
345private:
346 bool tightlyNested(Loop *Outer, Loop *Inner);
347 bool containsUnsafeInstructions(BasicBlock *BB);
348
349 /// Discover induction and reduction PHIs in the header of \p L. Induction
350 /// PHIs are added to \p Inductions, reductions are added to
351 /// OuterInnerReductions. When the outer loop is passed, the inner loop needs
352 /// to be passed as \p InnerLoop.
353 bool findInductionAndReductions(Loop *L,
354 SmallVector<PHINode *, 8> &Inductions,
355 Loop *InnerLoop);
356
357 Loop *OuterLoop;
358 Loop *InnerLoop;
359
360 ScalarEvolution *SE;
361
362 /// Interface to emit optimization remarks.
363 OptimizationRemarkEmitter *ORE;
364
365 /// Set of reduction PHIs taking part of a reduction across the inner and
366 /// outer loop.
367 SmallPtrSet<PHINode *, 4> OuterInnerReductions;
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 const LoopInterchangeLegality &LIL)
401 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT), LIL(LIL) {}
402
403 /// Interchange OuterLoop and InnerLoop.
404 bool transform();
405 void restructureLoops(Loop *NewInner, Loop *NewOuter,
406 BasicBlock *OrigInnerPreHeader,
407 BasicBlock *OrigOuterPreHeader);
408 void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
409
410private:
411 bool adjustLoopLinks();
412 bool adjustLoopBranches();
413
414 Loop *OuterLoop;
415 Loop *InnerLoop;
416
417 /// Scev analysis.
418 ScalarEvolution *SE;
419
420 LoopInfo *LI;
421 DominatorTree *DT;
422
423 const LoopInterchangeLegality &LIL;
424};
425
426struct LoopInterchange {
427 ScalarEvolution *SE = nullptr;
428 LoopInfo *LI = nullptr;
429 DependenceInfo *DI = nullptr;
430 DominatorTree *DT = nullptr;
431
432 /// Interface to emit optimization remarks.
433 OptimizationRemarkEmitter *ORE;
434
435 LoopInterchange(ScalarEvolution *SE, LoopInfo *LI, DependenceInfo *DI,
436 DominatorTree *DT, OptimizationRemarkEmitter *ORE)
437 : SE(SE), LI(LI), DI(DI), DT(DT), ORE(ORE) {}
438
439 bool run(Loop *L) {
440 if (L->getParentLoop())
441 return false;
442
443 return processLoopList(populateWorklist(*L));
444 }
445
446 bool run(LoopNest &LN) {
447 const auto &LoopList = LN.getLoops();
448 for (unsigned I = 1; I < LoopList.size(); ++I)
449 if (LoopList[I]->getParentLoop() != LoopList[I - 1])
450 return false;
451 return processLoopList(LoopList);
452 }
453
454 bool isComputableLoopNest(ArrayRef<Loop *> LoopList) {
455 for (Loop *L : LoopList) {
456 const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
457 if (isa<SCEVCouldNotCompute>(ExitCountOuter)) {
458 LLVM_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)
;
459 return false;
460 }
461 if (L->getNumBackEdges() != 1) {
462 LLVM_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)
;
463 return false;
464 }
465 if (!L->getExitingBlock()) {
466 LLVM_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)
;
467 return false;
468 }
469 }
470 return true;
471 }
472
473 unsigned selectLoopForInterchange(ArrayRef<Loop *> LoopList) {
474 // TODO: Add a better heuristic to select the loop to be interchanged based
475 // on the dependence matrix. Currently we select the innermost loop.
476 return LoopList.size() - 1;
477 }
478
479 bool processLoopList(ArrayRef<Loop *> LoopList) {
480 bool Changed = false;
481 unsigned LoopNestDepth = LoopList.size();
482 if (LoopNestDepth < 2) {
483 LLVM_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)
;
484 return false;
485 }
486 if (LoopNestDepth > MaxLoopNestDepth) {
487 LLVM_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)
488 << MaxLoopNestDepth << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Cannot handle loops of depth greater than "
<< MaxLoopNestDepth << "\n"; } } while (false)
;
489 return false;
490 }
491 if (!isComputableLoopNest(LoopList)) {
492 LLVM_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)
;
493 return false;
494 }
495
496 LLVM_DEBUG(dbgs() << "Processing LoopList of size = " << LoopNestDepthdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Processing LoopList of size = "
<< LoopNestDepth << "\n"; } } while (false)
497 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Processing LoopList of size = "
<< LoopNestDepth << "\n"; } } while (false)
;
498
499 CharMatrix DependencyMatrix;
500 Loop *OuterMostLoop = *(LoopList.begin());
501 if (!populateDependencyMatrix(DependencyMatrix, LoopNestDepth,
502 OuterMostLoop, DI)) {
503 LLVM_DEBUG(dbgs() << "Populating dependency matrix failed\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Populating dependency matrix failed\n"
; } } while (false)
;
504 return false;
505 }
506#ifdef DUMP_DEP_MATRICIES
507 LLVM_DEBUG(dbgs() << "Dependence before interchange\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Dependence before interchange\n"
; } } while (false)
;
508 printDepMatrix(DependencyMatrix);
509#endif
510
511 // Get the Outermost loop exit.
512 BasicBlock *LoopNestExit = OuterMostLoop->getExitBlock();
513 if (!LoopNestExit) {
514 LLVM_DEBUG(dbgs() << "OuterMostLoop needs an unique exit block")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "OuterMostLoop needs an unique exit block"
; } } while (false)
;
515 return false;
516 }
517
518 unsigned SelecLoopId = selectLoopForInterchange(LoopList);
519 // Move the selected loop outwards to the best possible position.
520 Loop *LoopToBeInterchanged = LoopList[SelecLoopId];
521 for (unsigned i = SelecLoopId; i > 0; i--) {
522 bool Interchanged = processLoop(LoopToBeInterchanged, LoopList[i - 1], i,
523 i - 1, DependencyMatrix);
524 if (!Interchanged)
525 return Changed;
526 // Update the DependencyMatrix
527 interChangeDependencies(DependencyMatrix, i, i - 1);
528#ifdef DUMP_DEP_MATRICIES
529 LLVM_DEBUG(dbgs() << "Dependence after interchange\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Dependence after interchange\n"
; } } while (false)
;
530 printDepMatrix(DependencyMatrix);
531#endif
532 Changed |= Interchanged;
533 }
534 return Changed;
535 }
536
537 bool processLoop(Loop *InnerLoop, Loop *OuterLoop, unsigned InnerLoopId,
538 unsigned OuterLoopId,
539 std::vector<std::vector<char>> &DependencyMatrix) {
540 LLVM_DEBUG(dbgs() << "Processing InnerLoopId = " << InnerLoopIddo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Processing InnerLoopId = "
<< InnerLoopId << " and OuterLoopId = " <<
OuterLoopId << "\n"; } } while (false)
541 << " and OuterLoopId = " << OuterLoopId << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Processing InnerLoopId = "
<< InnerLoopId << " and OuterLoopId = " <<
OuterLoopId << "\n"; } } while (false)
;
542 LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE);
543 if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
544 LLVM_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)
;
545 return false;
546 }
547 LLVM_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)
;
548 LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE);
549 if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
550 LLVM_DEBUG(dbgs() << "Interchanging loops not profitable.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Interchanging loops not profitable.\n"
; } } while (false)
;
551 return false;
552 }
553
554 ORE->emit([&]() {
555 return OptimizationRemark(DEBUG_TYPE"loop-interchange", "Interchanged",
556 InnerLoop->getStartLoc(),
557 InnerLoop->getHeader())
558 << "Loop interchanged with enclosing loop.";
559 });
560
561 LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, LIL);
562 LIT.transform();
563 LLVM_DEBUG(dbgs() << "Loops interchanged.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops interchanged.\n"
; } } while (false)
;
564 LoopsInterchanged++;
565
566 assert(InnerLoop->isLCSSAForm(*DT) &&(static_cast <bool> (InnerLoop->isLCSSAForm(*DT) &&
"Inner loop not left in LCSSA form after loop interchange!")
? void (0) : __assert_fail ("InnerLoop->isLCSSAForm(*DT) && \"Inner loop not left in LCSSA form after loop interchange!\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 567, __extension__ __PRETTY_FUNCTION__))
567 "Inner loop not left in LCSSA form after loop interchange!")(static_cast <bool> (InnerLoop->isLCSSAForm(*DT) &&
"Inner loop not left in LCSSA form after loop interchange!")
? void (0) : __assert_fail ("InnerLoop->isLCSSAForm(*DT) && \"Inner loop not left in LCSSA form after loop interchange!\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 567, __extension__ __PRETTY_FUNCTION__))
;
568 assert(OuterLoop->isLCSSAForm(*DT) &&(static_cast <bool> (OuterLoop->isLCSSAForm(*DT) &&
"Outer loop not left in LCSSA form after loop interchange!")
? void (0) : __assert_fail ("OuterLoop->isLCSSAForm(*DT) && \"Outer loop not left in LCSSA form after loop interchange!\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 569, __extension__ __PRETTY_FUNCTION__))
569 "Outer loop not left in LCSSA form after loop interchange!")(static_cast <bool> (OuterLoop->isLCSSAForm(*DT) &&
"Outer loop not left in LCSSA form after loop interchange!")
? void (0) : __assert_fail ("OuterLoop->isLCSSAForm(*DT) && \"Outer loop not left in LCSSA form after loop interchange!\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 569, __extension__ __PRETTY_FUNCTION__))
;
570
571 return true;
572 }
573};
574
575} // end anonymous namespace
576
577bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB) {
578 return any_of(*BB, [](const Instruction &I) {
579 return I.mayHaveSideEffects() || I.mayReadFromMemory();
580 });
581}
582
583bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
584 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
585 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
586 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
587
588 LLVM_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)
;
589
590 // A perfectly nested loop will not have any branch in between the outer and
591 // inner block i.e. outer header will branch to either inner preheader and
592 // outerloop latch.
593 BranchInst *OuterLoopHeaderBI =
594 dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
595 if (!OuterLoopHeaderBI)
596 return false;
597
598 for (BasicBlock *Succ : successors(OuterLoopHeaderBI))
599 if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader() &&
600 Succ != OuterLoopLatch)
601 return false;
602
603 LLVM_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)
;
604 // We do not have any basic block in between now make sure the outer header
605 // and outer loop latch doesn't contain any unsafe instructions.
606 if (containsUnsafeInstructions(OuterLoopHeader) ||
607 containsUnsafeInstructions(OuterLoopLatch))
608 return false;
609
610 // Also make sure the inner loop preheader does not contain any unsafe
611 // instructions. Note that all instructions in the preheader will be moved to
612 // the outer loop header when interchanging.
613 if (InnerLoopPreHeader != OuterLoopHeader &&
614 containsUnsafeInstructions(InnerLoopPreHeader))
615 return false;
616
617 BasicBlock *InnerLoopExit = InnerLoop->getExitBlock();
618 // Ensure the inner loop exit block flows to the outer loop latch possibly
619 // through empty blocks.
620 const BasicBlock &SuccInner =
621 LoopNest::skipEmptyBlockUntil(InnerLoopExit, OuterLoopLatch);
622 if (&SuccInner != OuterLoopLatch) {
623 LLVM_DEBUG(dbgs() << "Inner loop exit block " << *InnerLoopExitdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Inner loop exit block "
<< *InnerLoopExit << " does not lead to the outer loop latch.\n"
;; } } while (false)
624 << " does not lead to the outer loop latch.\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Inner loop exit block "
<< *InnerLoopExit << " does not lead to the outer loop latch.\n"
;; } } while (false)
;
625 return false;
626 }
627 // The inner loop exit block does flow to the outer loop latch and not some
628 // other BBs, now make sure it contains safe instructions, since it will be
629 // moved into the (new) inner loop after interchange.
630 if (containsUnsafeInstructions(InnerLoopExit))
631 return false;
632
633 LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops are perfectly nested\n"
; } } while (false)
;
634 // We have a perfect loop nest.
635 return true;
636}
637
638bool LoopInterchangeLegality::isLoopStructureUnderstood(
639 PHINode *InnerInduction) {
640 unsigned Num = InnerInduction->getNumOperands();
641 BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
642 for (unsigned i = 0; i < Num; ++i) {
15
Assuming 'i' is >= 'Num'
16
Loop condition is false. Execution continues on line 666
643 Value *Val = InnerInduction->getOperand(i);
644 if (isa<Constant>(Val))
645 continue;
646 Instruction *I = dyn_cast<Instruction>(Val);
647 if (!I)
648 return false;
649 // TODO: Handle triangular loops.
650 // e.g. for(int i=0;i<N;i++)
651 // for(int j=i;j<N;j++)
652 unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
653 if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
654 InnerLoopPreheader &&
655 !OuterLoop->isLoopInvariant(I)) {
656 return false;
657 }
658 }
659
660 // TODO: Handle triangular loops of another form.
661 // e.g. for(int i=0;i<N;i++)
662 // for(int j=0;j<i;j++)
663 // or,
664 // for(int i=0;i<N;i++)
665 // for(int j=0;j*i<N;j++)
666 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
667 BranchInst *InnerLoopLatchBI =
18
'InnerLoopLatchBI' initialized to a null pointer value
668 dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
17
Assuming the object is not a 'BranchInst'
669 if (!InnerLoopLatchBI->isConditional())
19
Called C++ object pointer is null
670 return false;
671 if (CmpInst *InnerLoopCmp =
672 dyn_cast<CmpInst>(InnerLoopLatchBI->getCondition())) {
673 Value *Op0 = InnerLoopCmp->getOperand(0);
674 Value *Op1 = InnerLoopCmp->getOperand(1);
675
676 // LHS and RHS of the inner loop exit condition, e.g.,
677 // in "for(int j=0;j<i;j++)", LHS is j and RHS is i.
678 Value *Left = nullptr;
679 Value *Right = nullptr;
680
681 // Check if V only involves inner loop induction variable.
682 // Return true if V is InnerInduction, or a cast from
683 // InnerInduction, or a binary operator that involves
684 // InnerInduction and a constant.
685 std::function<bool(Value *)> IsPathToIndVar;
686 IsPathToIndVar = [&InnerInduction, &IsPathToIndVar](Value *V) -> bool {
687 if (V == InnerInduction)
688 return true;
689 if (isa<Constant>(V))
690 return true;
691 Instruction *I = dyn_cast<Instruction>(V);
692 if (!I)
693 return false;
694 if (isa<CastInst>(I))
695 return IsPathToIndVar(I->getOperand(0));
696 if (isa<BinaryOperator>(I))
697 return IsPathToIndVar(I->getOperand(0)) &&
698 IsPathToIndVar(I->getOperand(1));
699 return false;
700 };
701
702 if (IsPathToIndVar(Op0) && !isa<Constant>(Op0)) {
703 Left = Op0;
704 Right = Op1;
705 } else if (IsPathToIndVar(Op1) && !isa<Constant>(Op1)) {
706 Left = Op1;
707 Right = Op0;
708 }
709
710 if (Left == nullptr)
711 return false;
712
713 const SCEV *S = SE->getSCEV(Right);
714 if (!SE->isLoopInvariant(S, OuterLoop))
715 return false;
716 }
717
718 return true;
719}
720
721// If SV is a LCSSA PHI node with a single incoming value, return the incoming
722// value.
723static Value *followLCSSA(Value *SV) {
724 PHINode *PHI = dyn_cast<PHINode>(SV);
725 if (!PHI)
726 return SV;
727
728 if (PHI->getNumIncomingValues() != 1)
729 return SV;
730 return followLCSSA(PHI->getIncomingValue(0));
731}
732
733// Check V's users to see if it is involved in a reduction in L.
734static PHINode *findInnerReductionPhi(Loop *L, Value *V) {
735 // Reduction variables cannot be constants.
736 if (isa<Constant>(V))
737 return nullptr;
738
739 for (Value *User : V->users()) {
740 if (PHINode *PHI = dyn_cast<PHINode>(User)) {
741 if (PHI->getNumIncomingValues() == 1)
742 continue;
743 RecurrenceDescriptor RD;
744 if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD))
745 return PHI;
746 return nullptr;
747 }
748 }
749
750 return nullptr;
751}
752
753bool LoopInterchangeLegality::findInductionAndReductions(
754 Loop *L, SmallVector<PHINode *, 8> &Inductions, Loop *InnerLoop) {
755 if (!L->getLoopLatch() || !L->getLoopPredecessor())
756 return false;
757 for (PHINode &PHI : L->getHeader()->phis()) {
758 RecurrenceDescriptor RD;
759 InductionDescriptor ID;
760 if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID))
761 Inductions.push_back(&PHI);
762 else {
763 // PHIs in inner loops need to be part of a reduction in the outer loop,
764 // discovered when checking the PHIs of the outer loop earlier.
765 if (!InnerLoop) {
766 if (!OuterInnerReductions.count(&PHI)) {
767 LLVM_DEBUG(dbgs() << "Inner loop PHI is not part of reductions "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Inner loop PHI is not part of reductions "
"across the outer loop.\n"; } } while (false)
768 "across the outer loop.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Inner loop PHI is not part of reductions "
"across the outer loop.\n"; } } while (false)
;
769 return false;
770 }
771 } else {
772 assert(PHI.getNumIncomingValues() == 2 &&(static_cast <bool> (PHI.getNumIncomingValues() == 2 &&
"Phis in loop header should have exactly 2 incoming values")
? void (0) : __assert_fail ("PHI.getNumIncomingValues() == 2 && \"Phis in loop header should have exactly 2 incoming values\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 773, __extension__ __PRETTY_FUNCTION__))
773 "Phis in loop header should have exactly 2 incoming values")(static_cast <bool> (PHI.getNumIncomingValues() == 2 &&
"Phis in loop header should have exactly 2 incoming values")
? void (0) : __assert_fail ("PHI.getNumIncomingValues() == 2 && \"Phis in loop header should have exactly 2 incoming values\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 773, __extension__ __PRETTY_FUNCTION__))
;
774 // Check if we have a PHI node in the outer loop that has a reduction
775 // result from the inner loop as an incoming value.
776 Value *V = followLCSSA(PHI.getIncomingValueForBlock(L->getLoopLatch()));
777 PHINode *InnerRedPhi = findInnerReductionPhi(InnerLoop, V);
778 if (!InnerRedPhi ||
779 !llvm::is_contained(InnerRedPhi->incoming_values(), &PHI)) {
780 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Failed to recognize PHI as an induction or reduction.\n"
; } } while (false)
781 dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Failed to recognize PHI as an induction or reduction.\n"
; } } while (false)
782 << "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)
;
783 return false;
784 }
785 OuterInnerReductions.insert(&PHI);
786 OuterInnerReductions.insert(InnerRedPhi);
787 }
788 }
789 }
790 return true;
791}
792
793// This function indicates the current limitations in the transform as a result
794// of which we do not proceed.
795bool LoopInterchangeLegality::currentLimitations() {
796 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
797 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
798
799 // transform currently expects the loop latches to also be the exiting
800 // blocks.
801 if (InnerLoop->getExitingBlock() != InnerLoopLatch ||
1
Assuming the condition is false
5
Taking false branch
802 OuterLoop->getExitingBlock() != OuterLoop->getLoopLatch() ||
2
Assuming the condition is false
803 !isa<BranchInst>(InnerLoopLatch->getTerminator()) ||
3
Assuming the object is a 'BranchInst'
804 !isa<BranchInst>(OuterLoop->getLoopLatch()->getTerminator())) {
4
Assuming the object is a 'BranchInst'
805 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops where the latch is not the exiting block are not"
<< " supported currently.\n"; } } while (false)
806 dbgs() << "Loops where the latch is not the exiting block are not"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops where the latch is not the exiting block are not"
<< " supported currently.\n"; } } while (false)
807 << " supported currently.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops where the latch is not the exiting block are not"
<< " supported currently.\n"; } } while (false)
;
808 ORE->emit([&]() {
809 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "ExitingNotLatch",
810 OuterLoop->getStartLoc(),
811 OuterLoop->getHeader())
812 << "Loops where the latch is not the exiting block cannot be"
813 " interchange currently.";
814 });
815 return true;
816 }
817
818 PHINode *InnerInductionVar;
819 SmallVector<PHINode *, 8> Inductions;
820 if (!findInductionAndReductions(OuterLoop, Inductions, InnerLoop)) {
6
Assuming the condition is false
7
Taking false branch
821 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Only outer loops with induction or reduction PHI nodes "
<< "are supported currently.\n"; } } while (false)
822 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)
823 << "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)
;
824 ORE->emit([&]() {
825 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "UnsupportedPHIOuter",
826 OuterLoop->getStartLoc(),
827 OuterLoop->getHeader())
828 << "Only outer loops with induction or reduction PHI nodes can be"
829 " interchanged currently.";
830 });
831 return true;
832 }
833
834 // TODO: Currently we handle only loops with 1 induction variable.
835 if (Inductions.size() != 1) {
8
Assuming the condition is false
9
Taking false branch
836 LLVM_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)
837 << "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)
;
838 ORE->emit([&]() {
839 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "MultiIndutionOuter",
840 OuterLoop->getStartLoc(),
841 OuterLoop->getHeader())
842 << "Only outer loops with 1 induction variable can be "
843 "interchanged currently.";
844 });
845 return true;
846 }
847
848 Inductions.clear();
849 if (!findInductionAndReductions(InnerLoop, Inductions, nullptr)) {
10
Assuming the condition is false
11
Taking false branch
850 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Only inner loops with induction or reduction PHI nodes "
<< "are supported currently.\n"; } } while (false)
851 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)
852 << "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)
;
853 ORE->emit([&]() {
854 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "UnsupportedPHIInner",
855 InnerLoop->getStartLoc(),
856 InnerLoop->getHeader())
857 << "Only inner loops with induction or reduction PHI nodes can be"
858 " interchange currently.";
859 });
860 return true;
861 }
862
863 // TODO: Currently we handle only loops with 1 induction variable.
864 if (Inductions.size() != 1) {
12
Assuming the condition is false
13
Taking false branch
865 LLVM_DEBUG(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)
866 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)
867 << "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)
;
868 ORE->emit([&]() {
869 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "MultiInductionInner",
870 InnerLoop->getStartLoc(),
871 InnerLoop->getHeader())
872 << "Only inner loops with 1 induction variable can be "
873 "interchanged currently.";
874 });
875 return true;
876 }
877 InnerInductionVar = Inductions.pop_back_val();
878
879 // TODO: Triangular loops are not handled for now.
880 if (!isLoopStructureUnderstood(InnerInductionVar)) {
14
Calling 'LoopInterchangeLegality::isLoopStructureUnderstood'
881 LLVM_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)
;
882 ORE->emit([&]() {
883 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "UnsupportedStructureInner",
884 InnerLoop->getStartLoc(),
885 InnerLoop->getHeader())
886 << "Inner loop structure not understood currently.";
887 });
888 return true;
889 }
890
891 // TODO: Current limitation: Since we split the inner loop latch at the point
892 // were induction variable is incremented (induction.next); We cannot have
893 // more than 1 user of induction.next since it would result in broken code
894 // after split.
895 // e.g.
896 // for(i=0;i<N;i++) {
897 // for(j = 0;j<M;j++) {
898 // A[j+1][i+2] = A[j][i]+k;
899 // }
900 // }
901 Instruction *InnerIndexVarInc = nullptr;
902 if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader)
903 InnerIndexVarInc =
904 dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1));
905 else
906 InnerIndexVarInc =
907 dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0));
908
909 if (!InnerIndexVarInc) {
910 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Did not find an instruction to increment the induction "
<< "variable.\n"; } } while (false)
911 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)
912 << "variable.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Did not find an instruction to increment the induction "
<< "variable.\n"; } } while (false)
;
913 ORE->emit([&]() {
914 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "NoIncrementInInner",
915 InnerLoop->getStartLoc(),
916 InnerLoop->getHeader())
917 << "The inner loop does not increment the induction variable.";
918 });
919 return true;
920 }
921
922 // Since we split the inner loop latch on this induction variable. Make sure
923 // we do not have any instruction between the induction variable and branch
924 // instruction.
925
926 bool FoundInduction = false;
927 for (const Instruction &I :
928 llvm::reverse(InnerLoopLatch->instructionsWithoutDebug())) {
929 if (isa<BranchInst>(I) || isa<CmpInst>(I) || isa<TruncInst>(I) ||
930 isa<ZExtInst>(I))
931 continue;
932
933 // We found an instruction. If this is not induction variable then it is not
934 // safe to split this loop latch.
935 if (!I.isIdenticalTo(InnerIndexVarInc)) {
936 LLVM_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
)
937 << "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
)
;
938 ORE->emit([&]() {
939 return OptimizationRemarkMissed(
940 DEBUG_TYPE"loop-interchange", "UnsupportedInsBetweenInduction",
941 InnerLoop->getStartLoc(), InnerLoop->getHeader())
942 << "Found unsupported instruction between induction variable "
943 "increment and branch.";
944 });
945 return true;
946 }
947
948 FoundInduction = true;
949 break;
950 }
951 // The loop latch ended and we didn't find the induction variable return as
952 // current limitation.
953 if (!FoundInduction) {
954 LLVM_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)
;
955 ORE->emit([&]() {
956 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "NoIndutionVariable",
957 InnerLoop->getStartLoc(),
958 InnerLoop->getHeader())
959 << "Did not find the induction variable.";
960 });
961 return true;
962 }
963 return false;
964}
965
966// We currently only support LCSSA PHI nodes in the inner loop exit, if their
967// users are either reduction PHIs or PHIs outside the outer loop (which means
968// the we are only interested in the final value after the loop).
969static bool
970areInnerLoopExitPHIsSupported(Loop *InnerL, Loop *OuterL,
971 SmallPtrSetImpl<PHINode *> &Reductions) {
972 BasicBlock *InnerExit = OuterL->getUniqueExitBlock();
973 for (PHINode &PHI : InnerExit->phis()) {
974 // Reduction lcssa phi will have only 1 incoming block that from loop latch.
975 if (PHI.getNumIncomingValues() > 1)
976 return false;
977 if (any_of(PHI.users(), [&Reductions, OuterL](User *U) {
978 PHINode *PN = dyn_cast<PHINode>(U);
979 return !PN ||
980 (!Reductions.count(PN) && OuterL->contains(PN->getParent()));
981 })) {
982 return false;
983 }
984 }
985 return true;
986}
987
988// We currently support LCSSA PHI nodes in the outer loop exit, if their
989// incoming values do not come from the outer loop latch or if the
990// outer loop latch has a single predecessor. In that case, the value will
991// be available if both the inner and outer loop conditions are true, which
992// will still be true after interchanging. If we have multiple predecessor,
993// that may not be the case, e.g. because the outer loop latch may be executed
994// if the inner loop is not executed.
995static bool areOuterLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop) {
996 BasicBlock *LoopNestExit = OuterLoop->getUniqueExitBlock();
997 for (PHINode &PHI : LoopNestExit->phis()) {
998 // FIXME: We currently are not able to detect floating point reductions
999 // and have to use floating point PHIs as a proxy to prevent
1000 // interchanging in the presence of floating point reductions.
1001 if (PHI.getType()->isFloatingPointTy())
1002 return false;
1003 for (unsigned i = 0; i < PHI.getNumIncomingValues(); i++) {
1004 Instruction *IncomingI = dyn_cast<Instruction>(PHI.getIncomingValue(i));
1005 if (!IncomingI || IncomingI->getParent() != OuterLoop->getLoopLatch())
1006 continue;
1007
1008 // The incoming value is defined in the outer loop latch. Currently we
1009 // only support that in case the outer loop latch has a single predecessor.
1010 // This guarantees that the outer loop latch is executed if and only if
1011 // the inner loop is executed (because tightlyNested() guarantees that the
1012 // outer loop header only branches to the inner loop or the outer loop
1013 // latch).
1014 // FIXME: We could weaken this logic and allow multiple predecessors,
1015 // if the values are produced outside the loop latch. We would need
1016 // additional logic to update the PHI nodes in the exit block as
1017 // well.
1018 if (OuterLoop->getLoopLatch()->getUniquePredecessor() == nullptr)
1019 return false;
1020 }
1021 }
1022 return true;
1023}
1024
1025bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
1026 unsigned OuterLoopId,
1027 CharMatrix &DepMatrix) {
1028 if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
1029 LLVM_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
)
1030 << " and OuterLoopId = " << OuterLoopIddo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Failed interchange InnerLoopId = "
<< InnerLoopId << " and OuterLoopId = " <<
OuterLoopId << " due to dependence\n"; } } while (false
)
1031 << " 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
)
;
1032 ORE->emit([&]() {
1033 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "Dependence",
1034 InnerLoop->getStartLoc(),
1035 InnerLoop->getHeader())
1036 << "Cannot interchange loops due to dependences.";
1037 });
1038 return false;
1039 }
1040 // Check if outer and inner loop contain legal instructions only.
1041 for (auto *BB : OuterLoop->blocks())
1042 for (Instruction &I : BB->instructionsWithoutDebug())
1043 if (CallInst *CI = dyn_cast<CallInst>(&I)) {
1044 // readnone functions do not prevent interchanging.
1045 if (CI->doesNotReadMemory())
1046 continue;
1047 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops with call instructions cannot be interchanged "
<< "safely."; } } while (false)
1048 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)
1049 << "safely.")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops with call instructions cannot be interchanged "
<< "safely."; } } while (false)
;
1050 ORE->emit([&]() {
1051 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "CallInst",
1052 CI->getDebugLoc(),
1053 CI->getParent())
1054 << "Cannot interchange loops due to call instruction.";
1055 });
1056
1057 return false;
1058 }
1059
1060 // TODO: The loops could not be interchanged due to current limitations in the
1061 // transform module.
1062 if (currentLimitations()) {
1063 LLVM_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)
;
1064 return false;
1065 }
1066
1067 // Check if the loops are tightly nested.
1068 if (!tightlyNested(OuterLoop, InnerLoop)) {
1069 LLVM_DEBUG(dbgs() << "Loops not tightly nested\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops not tightly nested\n"
; } } while (false)
;
1070 ORE->emit([&]() {
1071 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "NotTightlyNested",
1072 InnerLoop->getStartLoc(),
1073 InnerLoop->getHeader())
1074 << "Cannot interchange loops because they are not tightly "
1075 "nested.";
1076 });
1077 return false;
1078 }
1079
1080 if (!areInnerLoopExitPHIsSupported(OuterLoop, InnerLoop,
1081 OuterInnerReductions)) {
1082 LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop exit.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Found unsupported PHI nodes in inner loop exit.\n"
; } } while (false)
;
1083 ORE->emit([&]() {
1084 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "UnsupportedExitPHI",
1085 InnerLoop->getStartLoc(),
1086 InnerLoop->getHeader())
1087 << "Found unsupported PHI node in loop exit.";
1088 });
1089 return false;
1090 }
1091
1092 if (!areOuterLoopExitPHIsSupported(OuterLoop, InnerLoop)) {
1093 LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in outer loop exit.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Found unsupported PHI nodes in outer loop exit.\n"
; } } while (false)
;
1094 ORE->emit([&]() {
1095 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "UnsupportedExitPHI",
1096 OuterLoop->getStartLoc(),
1097 OuterLoop->getHeader())
1098 << "Found unsupported PHI node in loop exit.";
1099 });
1100 return false;
1101 }
1102
1103 return true;
1104}
1105
1106int LoopInterchangeProfitability::getInstrOrderCost() {
1107 unsigned GoodOrder, BadOrder;
1108 BadOrder = GoodOrder = 0;
1109 for (BasicBlock *BB : InnerLoop->blocks()) {
1110 for (Instruction &Ins : *BB) {
1111 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) {
1112 unsigned NumOp = GEP->getNumOperands();
1113 bool FoundInnerInduction = false;
1114 bool FoundOuterInduction = false;
1115 for (unsigned i = 0; i < NumOp; ++i) {
1116 // Skip operands that are not SCEV-able.
1117 if (!SE->isSCEVable(GEP->getOperand(i)->getType()))
1118 continue;
1119
1120 const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i));
1121 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal);
1122 if (!AR)
1123 continue;
1124
1125 // If we find the inner induction after an outer induction e.g.
1126 // for(int i=0;i<N;i++)
1127 // for(int j=0;j<N;j++)
1128 // A[i][j] = A[i-1][j-1]+k;
1129 // then it is a good order.
1130 if (AR->getLoop() == InnerLoop) {
1131 // We found an InnerLoop induction after OuterLoop induction. It is
1132 // a good order.
1133 FoundInnerInduction = true;
1134 if (FoundOuterInduction) {
1135 GoodOrder++;
1136 break;
1137 }
1138 }
1139 // If we find the outer induction after an inner induction e.g.
1140 // for(int i=0;i<N;i++)
1141 // for(int j=0;j<N;j++)
1142 // A[j][i] = A[j-1][i-1]+k;
1143 // then it is a bad order.
1144 if (AR->getLoop() == OuterLoop) {
1145 // We found an OuterLoop induction after InnerLoop induction. It is
1146 // a bad order.
1147 FoundOuterInduction = true;
1148 if (FoundInnerInduction) {
1149 BadOrder++;
1150 break;
1151 }
1152 }
1153 }
1154 }
1155 }
1156 }
1157 return GoodOrder - BadOrder;
1158}
1159
1160static bool isProfitableForVectorization(unsigned InnerLoopId,
1161 unsigned OuterLoopId,
1162 CharMatrix &DepMatrix) {
1163 // TODO: Improve this heuristic to catch more cases.
1164 // If the inner loop is loop independent or doesn't carry any dependency it is
1165 // profitable to move this to outer position.
1166 for (auto &Row : DepMatrix) {
1167 if (Row[InnerLoopId] != 'S' && Row[InnerLoopId] != 'I')
1168 return false;
1169 // TODO: We need to improve this heuristic.
1170 if (Row[OuterLoopId] != '=')
1171 return false;
1172 }
1173 // If outer loop has dependence and inner loop is loop independent then it is
1174 // profitable to interchange to enable parallelism.
1175 // If there are no dependences, interchanging will not improve anything.
1176 return !DepMatrix.empty();
1177}
1178
1179bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId,
1180 unsigned OuterLoopId,
1181 CharMatrix &DepMatrix) {
1182 // TODO: Add better profitability checks.
1183 // e.g
1184 // 1) Construct dependency matrix and move the one with no loop carried dep
1185 // inside to enable vectorization.
1186
1187 // This is rough cost estimation algorithm. It counts the good and bad order
1188 // of induction variables in the instruction and allows reordering if number
1189 // of bad orders is more than good.
1190 int Cost = getInstrOrderCost();
1191 LLVM_DEBUG(dbgs() << "Cost = " << Cost << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Cost = " << Cost
<< "\n"; } } while (false)
;
1192 if (Cost < -LoopInterchangeCostThreshold)
1193 return true;
1194
1195 // It is not profitable as per current cache profitability model. But check if
1196 // we can move this loop outside to improve parallelism.
1197 if (isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix))
1198 return true;
1199
1200 ORE->emit([&]() {
1201 return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "InterchangeNotProfitable",
1202 InnerLoop->getStartLoc(),
1203 InnerLoop->getHeader())
1204 << "Interchanging loops is too costly (cost="
1205 << ore::NV("Cost", Cost) << ", threshold="
1206 << ore::NV("Threshold", LoopInterchangeCostThreshold)
1207 << ") and it does not improve parallelism.";
1208 });
1209 return false;
1210}
1211
1212void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
1213 Loop *InnerLoop) {
1214 for (Loop *L : *OuterLoop)
1215 if (L == InnerLoop) {
1216 OuterLoop->removeChildLoop(L);
1217 return;
1218 }
1219 llvm_unreachable("Couldn't find loop")::llvm::llvm_unreachable_internal("Couldn't find loop", "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1219)
;
1220}
1221
1222/// Update LoopInfo, after interchanging. NewInner and NewOuter refer to the
1223/// new inner and outer loop after interchanging: NewInner is the original
1224/// outer loop and NewOuter is the original inner loop.
1225///
1226/// Before interchanging, we have the following structure
1227/// Outer preheader
1228// Outer header
1229// Inner preheader
1230// Inner header
1231// Inner body
1232// Inner latch
1233// outer bbs
1234// Outer latch
1235//
1236// After interchanging:
1237// Inner preheader
1238// Inner header
1239// Outer preheader
1240// Outer header
1241// Inner body
1242// outer bbs
1243// Outer latch
1244// Inner latch
1245void LoopInterchangeTransform::restructureLoops(
1246 Loop *NewInner, Loop *NewOuter, BasicBlock *OrigInnerPreHeader,
1247 BasicBlock *OrigOuterPreHeader) {
1248 Loop *OuterLoopParent = OuterLoop->getParentLoop();
1249 // The original inner loop preheader moves from the new inner loop to
1250 // the parent loop, if there is one.
1251 NewInner->removeBlockFromLoop(OrigInnerPreHeader);
1252 LI->changeLoopFor(OrigInnerPreHeader, OuterLoopParent);
1253
1254 // Switch the loop levels.
1255 if (OuterLoopParent) {
1256 // Remove the loop from its parent loop.
1257 removeChildLoop(OuterLoopParent, NewInner);
1258 removeChildLoop(NewInner, NewOuter);
1259 OuterLoopParent->addChildLoop(NewOuter);
1260 } else {
1261 removeChildLoop(NewInner, NewOuter);
1262 LI->changeTopLevelLoop(NewInner, NewOuter);
1263 }
1264 while (!NewOuter->isInnermost())
1265 NewInner->addChildLoop(NewOuter->removeChildLoop(NewOuter->begin()));
1266 NewOuter->addChildLoop(NewInner);
1267
1268 // BBs from the original inner loop.
1269 SmallVector<BasicBlock *, 8> OrigInnerBBs(NewOuter->blocks());
1270
1271 // Add BBs from the original outer loop to the original inner loop (excluding
1272 // BBs already in inner loop)
1273 for (BasicBlock *BB : NewInner->blocks())
1274 if (LI->getLoopFor(BB) == NewInner)
1275 NewOuter->addBlockEntry(BB);
1276
1277 // Now remove inner loop header and latch from the new inner loop and move
1278 // other BBs (the loop body) to the new inner loop.
1279 BasicBlock *OuterHeader = NewOuter->getHeader();
1280 BasicBlock *OuterLatch = NewOuter->getLoopLatch();
1281 for (BasicBlock *BB : OrigInnerBBs) {
1282 // Nothing will change for BBs in child loops.
1283 if (LI->getLoopFor(BB) != NewOuter)
1284 continue;
1285 // Remove the new outer loop header and latch from the new inner loop.
1286 if (BB == OuterHeader || BB == OuterLatch)
1287 NewInner->removeBlockFromLoop(BB);
1288 else
1289 LI->changeLoopFor(BB, NewInner);
1290 }
1291
1292 // The preheader of the original outer loop becomes part of the new
1293 // outer loop.
1294 NewOuter->addBlockEntry(OrigOuterPreHeader);
1295 LI->changeLoopFor(OrigOuterPreHeader, NewOuter);
1296
1297 // Tell SE that we move the loops around.
1298 SE->forgetLoop(NewOuter);
1299 SE->forgetLoop(NewInner);
1300}
1301
1302bool LoopInterchangeTransform::transform() {
1303 bool Transformed = false;
1304 Instruction *InnerIndexVar;
1305
1306 if (InnerLoop->getSubLoops().empty()) {
1307 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1308 LLVM_DEBUG(dbgs() << "Splitting the inner loop latch\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Splitting the inner loop latch\n"
; } } while (false)
;
1309 PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
1310 if (!InductionPHI) {
1311 LLVM_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)
;
1312 return false;
1313 }
1314
1315 if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
1316 InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
1317 else
1318 InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
1319
1320 // Ensure that InductionPHI is the first Phi node.
1321 if (&InductionPHI->getParent()->front() != InductionPHI)
1322 InductionPHI->moveBefore(&InductionPHI->getParent()->front());
1323
1324 // Create a new latch block for the inner loop. We split at the
1325 // current latch's terminator and then move the condition and all
1326 // operands that are not either loop-invariant or the induction PHI into the
1327 // new latch block.
1328 BasicBlock *NewLatch =
1329 SplitBlock(InnerLoop->getLoopLatch(),
1330 InnerLoop->getLoopLatch()->getTerminator(), DT, LI);
1331
1332 SmallSetVector<Instruction *, 4> WorkList;
1333 unsigned i = 0;
1334 auto MoveInstructions = [&i, &WorkList, this, InductionPHI, NewLatch]() {
1335 for (; i < WorkList.size(); i++) {
1336 // Duplicate instruction and move it the new latch. Update uses that
1337 // have been moved.
1338 Instruction *NewI = WorkList[i]->clone();
1339 NewI->insertBefore(NewLatch->getFirstNonPHI());
1340 assert(!NewI->mayHaveSideEffects() &&(static_cast <bool> (!NewI->mayHaveSideEffects() &&
"Moving instructions with side-effects may change behavior of "
"the loop nest!") ? void (0) : __assert_fail ("!NewI->mayHaveSideEffects() && \"Moving instructions with side-effects may change behavior of \" \"the loop nest!\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1342, __extension__ __PRETTY_FUNCTION__))
1341 "Moving instructions with side-effects may change behavior of "(static_cast <bool> (!NewI->mayHaveSideEffects() &&
"Moving instructions with side-effects may change behavior of "
"the loop nest!") ? void (0) : __assert_fail ("!NewI->mayHaveSideEffects() && \"Moving instructions with side-effects may change behavior of \" \"the loop nest!\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1342, __extension__ __PRETTY_FUNCTION__))
1342 "the loop nest!")(static_cast <bool> (!NewI->mayHaveSideEffects() &&
"Moving instructions with side-effects may change behavior of "
"the loop nest!") ? void (0) : __assert_fail ("!NewI->mayHaveSideEffects() && \"Moving instructions with side-effects may change behavior of \" \"the loop nest!\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1342, __extension__ __PRETTY_FUNCTION__))
;
1343 for (Use &U : llvm::make_early_inc_range(WorkList[i]->uses())) {
1344 Instruction *UserI = cast<Instruction>(U.getUser());
1345 if (!InnerLoop->contains(UserI->getParent()) ||
1346 UserI->getParent() == NewLatch || UserI == InductionPHI)
1347 U.set(NewI);
1348 }
1349 // Add operands of moved instruction to the worklist, except if they are
1350 // outside the inner loop or are the induction PHI.
1351 for (Value *Op : WorkList[i]->operands()) {
1352 Instruction *OpI = dyn_cast<Instruction>(Op);
1353 if (!OpI ||
1354 this->LI->getLoopFor(OpI->getParent()) != this->InnerLoop ||
1355 OpI == InductionPHI)
1356 continue;
1357 WorkList.insert(OpI);
1358 }
1359 }
1360 };
1361
1362 // FIXME: Should we interchange when we have a constant condition?
1363 Instruction *CondI = dyn_cast<Instruction>(
1364 cast<BranchInst>(InnerLoop->getLoopLatch()->getTerminator())
1365 ->getCondition());
1366 if (CondI)
1367 WorkList.insert(CondI);
1368 MoveInstructions();
1369 WorkList.insert(cast<Instruction>(InnerIndexVar));
1370 MoveInstructions();
1371
1372 // Splits the inner loops phi nodes out into a separate basic block.
1373 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1374 SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI);
1375 LLVM_DEBUG(dbgs() << "splitting InnerLoopHeader done\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "splitting InnerLoopHeader done\n"
; } } while (false)
;
1376 }
1377
1378 // Instructions in the original inner loop preheader may depend on values
1379 // defined in the outer loop header. Move them there, because the original
1380 // inner loop preheader will become the entry into the interchanged loop nest.
1381 // Currently we move all instructions and rely on LICM to move invariant
1382 // instructions outside the loop nest.
1383 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1384 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1385 if (InnerLoopPreHeader != OuterLoopHeader) {
1386 SmallPtrSet<Instruction *, 4> NeedsMoving;
1387 for (Instruction &I :
1388 make_early_inc_range(make_range(InnerLoopPreHeader->begin(),
1389 std::prev(InnerLoopPreHeader->end()))))
1390 I.moveBefore(OuterLoopHeader->getTerminator());
1391 }
1392
1393 Transformed |= adjustLoopLinks();
1394 if (!Transformed) {
1395 LLVM_DEBUG(dbgs() << "adjustLoopLinks failed\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "adjustLoopLinks failed\n"
; } } while (false)
;
1396 return false;
1397 }
1398
1399 return true;
1400}
1401
1402/// \brief Move all instructions except the terminator from FromBB right before
1403/// InsertBefore
1404static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
1405 auto &ToList = InsertBefore->getParent()->getInstList();
1406 auto &FromList = FromBB->getInstList();
1407
1408 ToList.splice(InsertBefore->getIterator(), FromList, FromList.begin(),
1409 FromBB->getTerminator()->getIterator());
1410}
1411
1412/// Swap instructions between \p BB1 and \p BB2 but keep terminators intact.
1413static void swapBBContents(BasicBlock *BB1, BasicBlock *BB2) {
1414 // Save all non-terminator instructions of BB1 into TempInstrs and unlink them
1415 // from BB1 afterwards.
1416 auto Iter = map_range(*BB1, [](Instruction &I) { return &I; });
1417 SmallVector<Instruction *, 4> TempInstrs(Iter.begin(), std::prev(Iter.end()));
1418 for (Instruction *I : TempInstrs)
1419 I->removeFromParent();
1420
1421 // Move instructions from BB2 to BB1.
1422 moveBBContents(BB2, BB1->getTerminator());
1423
1424 // Move instructions from TempInstrs to BB2.
1425 for (Instruction *I : TempInstrs)
1426 I->insertBefore(BB2->getTerminator());
1427}
1428
1429// Update BI to jump to NewBB instead of OldBB. Records updates to the
1430// dominator tree in DTUpdates. If \p MustUpdateOnce is true, assert that
1431// \p OldBB is exactly once in BI's successor list.
1432static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB,
1433 BasicBlock *NewBB,
1434 std::vector<DominatorTree::UpdateType> &DTUpdates,
1435 bool MustUpdateOnce = true) {
1436 assert((!MustUpdateOnce ||(static_cast <bool> ((!MustUpdateOnce || llvm::count_if
(successors(BI), [OldBB](BasicBlock *BB) { return BB == OldBB
; }) == 1) && "BI must jump to OldBB exactly once.") ?
void (0) : __assert_fail ("(!MustUpdateOnce || llvm::count_if(successors(BI), [OldBB](BasicBlock *BB) { return BB == OldBB; }) == 1) && \"BI must jump to OldBB exactly once.\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1440, __extension__ __PRETTY_FUNCTION__))
1437 llvm::count_if(successors(BI),(static_cast <bool> ((!MustUpdateOnce || llvm::count_if
(successors(BI), [OldBB](BasicBlock *BB) { return BB == OldBB
; }) == 1) && "BI must jump to OldBB exactly once.") ?
void (0) : __assert_fail ("(!MustUpdateOnce || llvm::count_if(successors(BI), [OldBB](BasicBlock *BB) { return BB == OldBB; }) == 1) && \"BI must jump to OldBB exactly once.\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1440, __extension__ __PRETTY_FUNCTION__))
1438 [OldBB](BasicBlock *BB) {(static_cast <bool> ((!MustUpdateOnce || llvm::count_if
(successors(BI), [OldBB](BasicBlock *BB) { return BB == OldBB
; }) == 1) && "BI must jump to OldBB exactly once.") ?
void (0) : __assert_fail ("(!MustUpdateOnce || llvm::count_if(successors(BI), [OldBB](BasicBlock *BB) { return BB == OldBB; }) == 1) && \"BI must jump to OldBB exactly once.\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1440, __extension__ __PRETTY_FUNCTION__))
1439 return BB == OldBB;(static_cast <bool> ((!MustUpdateOnce || llvm::count_if
(successors(BI), [OldBB](BasicBlock *BB) { return BB == OldBB
; }) == 1) && "BI must jump to OldBB exactly once.") ?
void (0) : __assert_fail ("(!MustUpdateOnce || llvm::count_if(successors(BI), [OldBB](BasicBlock *BB) { return BB == OldBB; }) == 1) && \"BI must jump to OldBB exactly once.\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1440, __extension__ __PRETTY_FUNCTION__))
1440 }) == 1) && "BI must jump to OldBB exactly once.")(static_cast <bool> ((!MustUpdateOnce || llvm::count_if
(successors(BI), [OldBB](BasicBlock *BB) { return BB == OldBB
; }) == 1) && "BI must jump to OldBB exactly once.") ?
void (0) : __assert_fail ("(!MustUpdateOnce || llvm::count_if(successors(BI), [OldBB](BasicBlock *BB) { return BB == OldBB; }) == 1) && \"BI must jump to OldBB exactly once.\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1440, __extension__ __PRETTY_FUNCTION__))
;
1441 bool Changed = false;
1442 for (Use &Op : BI->operands())
1443 if (Op == OldBB) {
1444 Op.set(NewBB);
1445 Changed = true;
1446 }
1447
1448 if (Changed) {
1449 DTUpdates.push_back(
1450 {DominatorTree::UpdateKind::Insert, BI->getParent(), NewBB});
1451 DTUpdates.push_back(
1452 {DominatorTree::UpdateKind::Delete, BI->getParent(), OldBB});
1453 }
1454 assert(Changed && "Expected a successor to be updated")(static_cast <bool> (Changed && "Expected a successor to be updated"
) ? void (0) : __assert_fail ("Changed && \"Expected a successor to be updated\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1454, __extension__ __PRETTY_FUNCTION__))
;
1455}
1456
1457// Move Lcssa PHIs to the right place.
1458static void moveLCSSAPhis(BasicBlock *InnerExit, BasicBlock *InnerHeader,
1459 BasicBlock *InnerLatch, BasicBlock *OuterHeader,
1460 BasicBlock *OuterLatch, BasicBlock *OuterExit,
1461 Loop *InnerLoop, LoopInfo *LI) {
1462
1463 // Deal with LCSSA PHI nodes in the exit block of the inner loop, that are
1464 // defined either in the header or latch. Those blocks will become header and
1465 // latch of the new outer loop, and the only possible users can PHI nodes
1466 // in the exit block of the loop nest or the outer loop header (reduction
1467 // PHIs, in that case, the incoming value must be defined in the inner loop
1468 // header). We can just substitute the user with the incoming value and remove
1469 // the PHI.
1470 for (PHINode &P : make_early_inc_range(InnerExit->phis())) {
1471 assert(P.getNumIncomingValues() == 1 &&(static_cast <bool> (P.getNumIncomingValues() == 1 &&
"Only loops with a single exit are supported!") ? void (0) :
__assert_fail ("P.getNumIncomingValues() == 1 && \"Only loops with a single exit are supported!\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1472, __extension__ __PRETTY_FUNCTION__))
1472 "Only loops with a single exit are supported!")(static_cast <bool> (P.getNumIncomingValues() == 1 &&
"Only loops with a single exit are supported!") ? void (0) :
__assert_fail ("P.getNumIncomingValues() == 1 && \"Only loops with a single exit are supported!\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1472, __extension__ __PRETTY_FUNCTION__))
;
1473
1474 // Incoming values are guaranteed be instructions currently.
1475 auto IncI = cast<Instruction>(P.getIncomingValueForBlock(InnerLatch));
1476 // Skip phis with incoming values from the inner loop body, excluding the
1477 // header and latch.
1478 if (IncI->getParent() != InnerLatch && IncI->getParent() != InnerHeader)
1479 continue;
1480
1481 assert(all_of(P.users(),(static_cast <bool> (all_of(P.users(), [OuterHeader, OuterExit
, IncI, InnerHeader](User *U) { return (cast<PHINode>(U
)->getParent() == OuterHeader && IncI->getParent
() == InnerHeader) || cast<PHINode>(U)->getParent() ==
OuterExit; }) && "Can only replace phis iff the uses are in the loop nest exit or "
"the incoming value is defined in the inner header (it will "
"dominate all loop blocks after interchanging)") ? void (0) :
__assert_fail ("all_of(P.users(), [OuterHeader, OuterExit, IncI, InnerHeader](User *U) { return (cast<PHINode>(U)->getParent() == OuterHeader && IncI->getParent() == InnerHeader) || cast<PHINode>(U)->getParent() == OuterExit; }) && \"Can only replace phis iff the uses are in the loop nest exit or \" \"the incoming value is defined in the inner header (it will \" \"dominate all loop blocks after interchanging)\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1489, __extension__ __PRETTY_FUNCTION__))
1482 [OuterHeader, OuterExit, IncI, InnerHeader](User *U) {(static_cast <bool> (all_of(P.users(), [OuterHeader, OuterExit
, IncI, InnerHeader](User *U) { return (cast<PHINode>(U
)->getParent() == OuterHeader && IncI->getParent
() == InnerHeader) || cast<PHINode>(U)->getParent() ==
OuterExit; }) && "Can only replace phis iff the uses are in the loop nest exit or "
"the incoming value is defined in the inner header (it will "
"dominate all loop blocks after interchanging)") ? void (0) :
__assert_fail ("all_of(P.users(), [OuterHeader, OuterExit, IncI, InnerHeader](User *U) { return (cast<PHINode>(U)->getParent() == OuterHeader && IncI->getParent() == InnerHeader) || cast<PHINode>(U)->getParent() == OuterExit; }) && \"Can only replace phis iff the uses are in the loop nest exit or \" \"the incoming value is defined in the inner header (it will \" \"dominate all loop blocks after interchanging)\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1489, __extension__ __PRETTY_FUNCTION__))
1483 return (cast<PHINode>(U)->getParent() == OuterHeader &&(static_cast <bool> (all_of(P.users(), [OuterHeader, OuterExit
, IncI, InnerHeader](User *U) { return (cast<PHINode>(U
)->getParent() == OuterHeader && IncI->getParent
() == InnerHeader) || cast<PHINode>(U)->getParent() ==
OuterExit; }) && "Can only replace phis iff the uses are in the loop nest exit or "
"the incoming value is defined in the inner header (it will "
"dominate all loop blocks after interchanging)") ? void (0) :
__assert_fail ("all_of(P.users(), [OuterHeader, OuterExit, IncI, InnerHeader](User *U) { return (cast<PHINode>(U)->getParent() == OuterHeader && IncI->getParent() == InnerHeader) || cast<PHINode>(U)->getParent() == OuterExit; }) && \"Can only replace phis iff the uses are in the loop nest exit or \" \"the incoming value is defined in the inner header (it will \" \"dominate all loop blocks after interchanging)\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1489, __extension__ __PRETTY_FUNCTION__))
1484 IncI->getParent() == InnerHeader) ||(static_cast <bool> (all_of(P.users(), [OuterHeader, OuterExit
, IncI, InnerHeader](User *U) { return (cast<PHINode>(U
)->getParent() == OuterHeader && IncI->getParent
() == InnerHeader) || cast<PHINode>(U)->getParent() ==
OuterExit; }) && "Can only replace phis iff the uses are in the loop nest exit or "
"the incoming value is defined in the inner header (it will "
"dominate all loop blocks after interchanging)") ? void (0) :
__assert_fail ("all_of(P.users(), [OuterHeader, OuterExit, IncI, InnerHeader](User *U) { return (cast<PHINode>(U)->getParent() == OuterHeader && IncI->getParent() == InnerHeader) || cast<PHINode>(U)->getParent() == OuterExit; }) && \"Can only replace phis iff the uses are in the loop nest exit or \" \"the incoming value is defined in the inner header (it will \" \"dominate all loop blocks after interchanging)\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1489, __extension__ __PRETTY_FUNCTION__))
1485 cast<PHINode>(U)->getParent() == OuterExit;(static_cast <bool> (all_of(P.users(), [OuterHeader, OuterExit
, IncI, InnerHeader](User *U) { return (cast<PHINode>(U
)->getParent() == OuterHeader && IncI->getParent
() == InnerHeader) || cast<PHINode>(U)->getParent() ==
OuterExit; }) && "Can only replace phis iff the uses are in the loop nest exit or "
"the incoming value is defined in the inner header (it will "
"dominate all loop blocks after interchanging)") ? void (0) :
__assert_fail ("all_of(P.users(), [OuterHeader, OuterExit, IncI, InnerHeader](User *U) { return (cast<PHINode>(U)->getParent() == OuterHeader && IncI->getParent() == InnerHeader) || cast<PHINode>(U)->getParent() == OuterExit; }) && \"Can only replace phis iff the uses are in the loop nest exit or \" \"the incoming value is defined in the inner header (it will \" \"dominate all loop blocks after interchanging)\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1489, __extension__ __PRETTY_FUNCTION__))
1486 }) &&(static_cast <bool> (all_of(P.users(), [OuterHeader, OuterExit
, IncI, InnerHeader](User *U) { return (cast<PHINode>(U
)->getParent() == OuterHeader && IncI->getParent
() == InnerHeader) || cast<PHINode>(U)->getParent() ==
OuterExit; }) && "Can only replace phis iff the uses are in the loop nest exit or "
"the incoming value is defined in the inner header (it will "
"dominate all loop blocks after interchanging)") ? void (0) :
__assert_fail ("all_of(P.users(), [OuterHeader, OuterExit, IncI, InnerHeader](User *U) { return (cast<PHINode>(U)->getParent() == OuterHeader && IncI->getParent() == InnerHeader) || cast<PHINode>(U)->getParent() == OuterExit; }) && \"Can only replace phis iff the uses are in the loop nest exit or \" \"the incoming value is defined in the inner header (it will \" \"dominate all loop blocks after interchanging)\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1489, __extension__ __PRETTY_FUNCTION__))
1487 "Can only replace phis iff the uses are in the loop nest exit or "(static_cast <bool> (all_of(P.users(), [OuterHeader, OuterExit
, IncI, InnerHeader](User *U) { return (cast<PHINode>(U
)->getParent() == OuterHeader && IncI->getParent
() == InnerHeader) || cast<PHINode>(U)->getParent() ==
OuterExit; }) && "Can only replace phis iff the uses are in the loop nest exit or "
"the incoming value is defined in the inner header (it will "
"dominate all loop blocks after interchanging)") ? void (0) :
__assert_fail ("all_of(P.users(), [OuterHeader, OuterExit, IncI, InnerHeader](User *U) { return (cast<PHINode>(U)->getParent() == OuterHeader && IncI->getParent() == InnerHeader) || cast<PHINode>(U)->getParent() == OuterExit; }) && \"Can only replace phis iff the uses are in the loop nest exit or \" \"the incoming value is defined in the inner header (it will \" \"dominate all loop blocks after interchanging)\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1489, __extension__ __PRETTY_FUNCTION__))
1488 "the incoming value is defined in the inner header (it will "(static_cast <bool> (all_of(P.users(), [OuterHeader, OuterExit
, IncI, InnerHeader](User *U) { return (cast<PHINode>(U
)->getParent() == OuterHeader && IncI->getParent
() == InnerHeader) || cast<PHINode>(U)->getParent() ==
OuterExit; }) && "Can only replace phis iff the uses are in the loop nest exit or "
"the incoming value is defined in the inner header (it will "
"dominate all loop blocks after interchanging)") ? void (0) :
__assert_fail ("all_of(P.users(), [OuterHeader, OuterExit, IncI, InnerHeader](User *U) { return (cast<PHINode>(U)->getParent() == OuterHeader && IncI->getParent() == InnerHeader) || cast<PHINode>(U)->getParent() == OuterExit; }) && \"Can only replace phis iff the uses are in the loop nest exit or \" \"the incoming value is defined in the inner header (it will \" \"dominate all loop blocks after interchanging)\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1489, __extension__ __PRETTY_FUNCTION__))
1489 "dominate all loop blocks after interchanging)")(static_cast <bool> (all_of(P.users(), [OuterHeader, OuterExit
, IncI, InnerHeader](User *U) { return (cast<PHINode>(U
)->getParent() == OuterHeader && IncI->getParent
() == InnerHeader) || cast<PHINode>(U)->getParent() ==
OuterExit; }) && "Can only replace phis iff the uses are in the loop nest exit or "
"the incoming value is defined in the inner header (it will "
"dominate all loop blocks after interchanging)") ? void (0) :
__assert_fail ("all_of(P.users(), [OuterHeader, OuterExit, IncI, InnerHeader](User *U) { return (cast<PHINode>(U)->getParent() == OuterHeader && IncI->getParent() == InnerHeader) || cast<PHINode>(U)->getParent() == OuterExit; }) && \"Can only replace phis iff the uses are in the loop nest exit or \" \"the incoming value is defined in the inner header (it will \" \"dominate all loop blocks after interchanging)\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1489, __extension__ __PRETTY_FUNCTION__))
;
1490 P.replaceAllUsesWith(IncI);
1491 P.eraseFromParent();
1492 }
1493
1494 SmallVector<PHINode *, 8> LcssaInnerExit;
1495 for (PHINode &P : InnerExit->phis())
1496 LcssaInnerExit.push_back(&P);
1497
1498 SmallVector<PHINode *, 8> LcssaInnerLatch;
1499 for (PHINode &P : InnerLatch->phis())
1500 LcssaInnerLatch.push_back(&P);
1501
1502 // Lcssa PHIs for values used outside the inner loop are in InnerExit.
1503 // If a PHI node has users outside of InnerExit, it has a use outside the
1504 // interchanged loop and we have to preserve it. We move these to
1505 // InnerLatch, which will become the new exit block for the innermost
1506 // loop after interchanging.
1507 for (PHINode *P : LcssaInnerExit)
1508 P->moveBefore(InnerLatch->getFirstNonPHI());
1509
1510 // If the inner loop latch contains LCSSA PHIs, those come from a child loop
1511 // and we have to move them to the new inner latch.
1512 for (PHINode *P : LcssaInnerLatch)
1513 P->moveBefore(InnerExit->getFirstNonPHI());
1514
1515 // Deal with LCSSA PHI nodes in the loop nest exit block. For PHIs that have
1516 // incoming values defined in the outer loop, we have to add a new PHI
1517 // in the inner loop latch, which became the exit block of the outer loop,
1518 // after interchanging.
1519 if (OuterExit) {
1520 for (PHINode &P : OuterExit->phis()) {
1521 if (P.getNumIncomingValues() != 1)
1522 continue;
1523 // Skip Phis with incoming values defined in the inner loop. Those should
1524 // already have been updated.
1525 auto I = dyn_cast<Instruction>(P.getIncomingValue(0));
1526 if (!I || LI->getLoopFor(I->getParent()) == InnerLoop)
1527 continue;
1528
1529 PHINode *NewPhi = dyn_cast<PHINode>(P.clone());
1530 NewPhi->setIncomingValue(0, P.getIncomingValue(0));
1531 NewPhi->setIncomingBlock(0, OuterLatch);
1532 // We might have incoming edges from other BBs, i.e., the original outer
1533 // header.
1534 for (auto *Pred : predecessors(InnerLatch)) {
1535 if (Pred == OuterLatch)
1536 continue;
1537 NewPhi->addIncoming(P.getIncomingValue(0), Pred);
1538 }
1539 NewPhi->insertBefore(InnerLatch->getFirstNonPHI());
1540 P.setIncomingValue(0, NewPhi);
1541 }
1542 }
1543
1544 // Now adjust the incoming blocks for the LCSSA PHIs.
1545 // For PHIs moved from Inner's exit block, we need to replace Inner's latch
1546 // with the new latch.
1547 InnerLatch->replacePhiUsesWith(InnerLatch, OuterLatch);
1548}
1549
1550bool LoopInterchangeTransform::adjustLoopBranches() {
1551 LLVM_DEBUG(dbgs() << "adjustLoopBranches called\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "adjustLoopBranches called\n"
; } } while (false)
;
1552 std::vector<DominatorTree::UpdateType> DTUpdates;
1553
1554 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1555 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1556
1557 assert(OuterLoopPreHeader != OuterLoop->getHeader() &&(static_cast <bool> (OuterLoopPreHeader != OuterLoop->
getHeader() && InnerLoopPreHeader != InnerLoop->getHeader
() && OuterLoopPreHeader && InnerLoopPreHeader
&& "Guaranteed by loop-simplify form") ? void (0) : __assert_fail
("OuterLoopPreHeader != OuterLoop->getHeader() && InnerLoopPreHeader != InnerLoop->getHeader() && OuterLoopPreHeader && InnerLoopPreHeader && \"Guaranteed by loop-simplify form\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1559, __extension__ __PRETTY_FUNCTION__))
1558 InnerLoopPreHeader != InnerLoop->getHeader() && OuterLoopPreHeader &&(static_cast <bool> (OuterLoopPreHeader != OuterLoop->
getHeader() && InnerLoopPreHeader != InnerLoop->getHeader
() && OuterLoopPreHeader && InnerLoopPreHeader
&& "Guaranteed by loop-simplify form") ? void (0) : __assert_fail
("OuterLoopPreHeader != OuterLoop->getHeader() && InnerLoopPreHeader != InnerLoop->getHeader() && OuterLoopPreHeader && InnerLoopPreHeader && \"Guaranteed by loop-simplify form\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1559, __extension__ __PRETTY_FUNCTION__))
1559 InnerLoopPreHeader && "Guaranteed by loop-simplify form")(static_cast <bool> (OuterLoopPreHeader != OuterLoop->
getHeader() && InnerLoopPreHeader != InnerLoop->getHeader
() && OuterLoopPreHeader && InnerLoopPreHeader
&& "Guaranteed by loop-simplify form") ? void (0) : __assert_fail
("OuterLoopPreHeader != OuterLoop->getHeader() && InnerLoopPreHeader != InnerLoop->getHeader() && OuterLoopPreHeader && InnerLoopPreHeader && \"Guaranteed by loop-simplify form\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1559, __extension__ __PRETTY_FUNCTION__))
;
1560 // Ensure that both preheaders do not contain PHI nodes and have single
1561 // predecessors. This allows us to move them easily. We use
1562 // InsertPreHeaderForLoop to create an 'extra' preheader, if the existing
1563 // preheaders do not satisfy those conditions.
1564 if (isa<PHINode>(OuterLoopPreHeader->begin()) ||
1565 !OuterLoopPreHeader->getUniquePredecessor())
1566 OuterLoopPreHeader =
1567 InsertPreheaderForLoop(OuterLoop, DT, LI, nullptr, true);
1568 if (InnerLoopPreHeader == OuterLoop->getHeader())
1569 InnerLoopPreHeader =
1570 InsertPreheaderForLoop(InnerLoop, DT, LI, nullptr, true);
1571
1572 // Adjust the loop preheader
1573 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1574 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1575 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1576 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1577 BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
1578 BasicBlock *InnerLoopLatchPredecessor =
1579 InnerLoopLatch->getUniquePredecessor();
1580 BasicBlock *InnerLoopLatchSuccessor;
1581 BasicBlock *OuterLoopLatchSuccessor;
1582
1583 BranchInst *OuterLoopLatchBI =
1584 dyn_cast<BranchInst>(OuterLoopLatch->getTerminator());
1585 BranchInst *InnerLoopLatchBI =
1586 dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
1587 BranchInst *OuterLoopHeaderBI =
1588 dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
1589 BranchInst *InnerLoopHeaderBI =
1590 dyn_cast<BranchInst>(InnerLoopHeader->getTerminator());
1591
1592 if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||
1593 !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||
1594 !InnerLoopHeaderBI)
1595 return false;
1596
1597 BranchInst *InnerLoopLatchPredecessorBI =
1598 dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator());
1599 BranchInst *OuterLoopPredecessorBI =
1600 dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator());
1601
1602 if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
1603 return false;
1604 BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
1605 if (!InnerLoopHeaderSuccessor)
1606 return false;
1607
1608 // Adjust Loop Preheader and headers.
1609 // The branches in the outer loop predecessor and the outer loop header can
1610 // be unconditional branches or conditional branches with duplicates. Consider
1611 // this when updating the successors.
1612 updateSuccessor(OuterLoopPredecessorBI, OuterLoopPreHeader,
1613 InnerLoopPreHeader, DTUpdates, /*MustUpdateOnce=*/false);
1614 // The outer loop header might or might not branch to the outer latch.
1615 // We are guaranteed to branch to the inner loop preheader.
1616 if (llvm::is_contained(OuterLoopHeaderBI->successors(), OuterLoopLatch)) {
1617 // In this case the outerLoopHeader should branch to the InnerLoopLatch.
1618 updateSuccessor(OuterLoopHeaderBI, OuterLoopLatch, InnerLoopLatch,
1619 DTUpdates,
1620 /*MustUpdateOnce=*/false);
1621 }
1622 updateSuccessor(OuterLoopHeaderBI, InnerLoopPreHeader,
1623 InnerLoopHeaderSuccessor, DTUpdates,
1624 /*MustUpdateOnce=*/false);
1625
1626 // Adjust reduction PHI's now that the incoming block has changed.
1627 InnerLoopHeaderSuccessor->replacePhiUsesWith(InnerLoopHeader,
1628 OuterLoopHeader);
1629
1630 updateSuccessor(InnerLoopHeaderBI, InnerLoopHeaderSuccessor,
1631 OuterLoopPreHeader, DTUpdates);
1632
1633 // -------------Adjust loop latches-----------
1634 if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
1635 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
1636 else
1637 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
1638
1639 updateSuccessor(InnerLoopLatchPredecessorBI, InnerLoopLatch,
1640 InnerLoopLatchSuccessor, DTUpdates);
1641
1642
1643 if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
1644 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
1645 else
1646 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
1647
1648 updateSuccessor(InnerLoopLatchBI, InnerLoopLatchSuccessor,
1649 OuterLoopLatchSuccessor, DTUpdates);
1650 updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,
1651 DTUpdates);
1652
1653 DT->applyUpdates(DTUpdates);
1654 restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader,
1655 OuterLoopPreHeader);
1656
1657 moveLCSSAPhis(InnerLoopLatchSuccessor, InnerLoopHeader, InnerLoopLatch,
1658 OuterLoopHeader, OuterLoopLatch, InnerLoop->getExitBlock(),
1659 InnerLoop, LI);
1660 // For PHIs in the exit block of the outer loop, outer's latch has been
1661 // replaced by Inners'.
1662 OuterLoopLatchSuccessor->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
1663
1664 auto &OuterInnerReductions = LIL.getOuterInnerReductions();
1665 // Now update the reduction PHIs in the inner and outer loop headers.
1666 SmallVector<PHINode *, 4> InnerLoopPHIs, OuterLoopPHIs;
1667 for (PHINode &PHI : InnerLoopHeader->phis()) {
1668 if (OuterInnerReductions.find(&PHI) == OuterInnerReductions.end())
1669 continue;
1670 InnerLoopPHIs.push_back(cast<PHINode>(&PHI));
1671 }
1672 for (PHINode &PHI : OuterLoopHeader->phis()) {
1673 if (OuterInnerReductions.find(&PHI) == OuterInnerReductions.end())
1674 continue;
1675 OuterLoopPHIs.push_back(cast<PHINode>(&PHI));
1676 }
1677
1678 // Now move the remaining reduction PHIs from outer to inner loop header and
1679 // vice versa. The PHI nodes must be part of a reduction across the inner and
1680 // outer loop and all the remains to do is and updating the incoming blocks.
1681 for (PHINode *PHI : OuterLoopPHIs) {
1682 PHI->moveBefore(InnerLoopHeader->getFirstNonPHI());
1683 assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node")(static_cast <bool> (OuterInnerReductions.count(PHI) &&
"Expected a reduction PHI node") ? void (0) : __assert_fail (
"OuterInnerReductions.count(PHI) && \"Expected a reduction PHI node\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1683, __extension__ __PRETTY_FUNCTION__))
;
1684 }
1685 for (PHINode *PHI : InnerLoopPHIs) {
1686 PHI->moveBefore(OuterLoopHeader->getFirstNonPHI());
1687 assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node")(static_cast <bool> (OuterInnerReductions.count(PHI) &&
"Expected a reduction PHI node") ? void (0) : __assert_fail (
"OuterInnerReductions.count(PHI) && \"Expected a reduction PHI node\""
, "/build/llvm-toolchain-snapshot-13~++20210613111130+5be314f79ba7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp"
, 1687, __extension__ __PRETTY_FUNCTION__))
;
1688 }
1689
1690 // Update the incoming blocks for moved PHI nodes.
1691 OuterLoopHeader->replacePhiUsesWith(InnerLoopPreHeader, OuterLoopPreHeader);
1692 OuterLoopHeader->replacePhiUsesWith(InnerLoopLatch, OuterLoopLatch);
1693 InnerLoopHeader->replacePhiUsesWith(OuterLoopPreHeader, InnerLoopPreHeader);
1694 InnerLoopHeader->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
1695
1696 // Values defined in the outer loop header could be used in the inner loop
1697 // latch. In that case, we need to create LCSSA phis for them, because after
1698 // interchanging they will be defined in the new inner loop and used in the
1699 // new outer loop.
1700 IRBuilder<> Builder(OuterLoopHeader->getContext());
1701 SmallVector<Instruction *, 4> MayNeedLCSSAPhis;
1702 for (Instruction &I :
1703 make_range(OuterLoopHeader->begin(), std::prev(OuterLoopHeader->end())))
1704 MayNeedLCSSAPhis.push_back(&I);
1705 formLCSSAForInstructions(MayNeedLCSSAPhis, *DT, *LI, SE, Builder);
1706
1707 return true;
1708}
1709
1710bool LoopInterchangeTransform::adjustLoopLinks() {
1711 // Adjust all branches in the inner and outer loop.
1712 bool Changed = adjustLoopBranches();
1713 if (Changed) {
1714 // We have interchanged the preheaders so we need to interchange the data in
1715 // the preheaders as well. This is because the content of the inner
1716 // preheader was previously executed inside the outer loop.
1717 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1718 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1719 swapBBContents(OuterLoopPreHeader, InnerLoopPreHeader);
1720 }
1721 return Changed;
1722}
1723
1724/// Main LoopInterchange Pass.
1725struct LoopInterchangeLegacyPass : public LoopPass {
1726 static char ID;
1727
1728 LoopInterchangeLegacyPass() : LoopPass(ID) {
1729 initializeLoopInterchangeLegacyPassPass(*PassRegistry::getPassRegistry());
1730 }
1731
1732 void getAnalysisUsage(AnalysisUsage &AU) const override {
1733 AU.addRequired<DependenceAnalysisWrapperPass>();
1734 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
1735
1736 getLoopAnalysisUsage(AU);
1737 }
1738
1739 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
1740 if (skipLoop(L))
1741 return false;
1742
1743 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1744 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1745 auto *DI = &getAnalysis<DependenceAnalysisWrapperPass>().getDI();
1746 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1747 auto *ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
1748
1749 return LoopInterchange(SE, LI, DI, DT, ORE).run(L);
1750 }
1751};
1752
1753char LoopInterchangeLegacyPass::ID = 0;
1754
1755INITIALIZE_PASS_BEGIN(LoopInterchangeLegacyPass, "loop-interchange",static void *initializeLoopInterchangeLegacyPassPassOnce(PassRegistry
&Registry) {
1756 "Interchanges loops for cache reuse", false, false)static void *initializeLoopInterchangeLegacyPassPassOnce(PassRegistry
&Registry) {
1757INITIALIZE_PASS_DEPENDENCY(LoopPass)initializeLoopPassPass(Registry);
1758INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)initializeDependenceAnalysisWrapperPassPass(Registry);
1759INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)initializeOptimizationRemarkEmitterWrapperPassPass(Registry);
1760
1761INITIALIZE_PASS_END(LoopInterchangeLegacyPass, "loop-interchange",PassInfo *PI = new PassInfo( "Interchanges loops for cache reuse"
, "loop-interchange", &LoopInterchangeLegacyPass::ID, PassInfo
::NormalCtor_t(callDefaultCtor<LoopInterchangeLegacyPass>
), false, false); Registry.registerPass(*PI, true); return PI
; } static llvm::once_flag InitializeLoopInterchangeLegacyPassPassFlag
; void llvm::initializeLoopInterchangeLegacyPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeLoopInterchangeLegacyPassPassFlag
, initializeLoopInterchangeLegacyPassPassOnce, std::ref(Registry
)); }
1762 "Interchanges loops for cache reuse", false, false)PassInfo *PI = new PassInfo( "Interchanges loops for cache reuse"
, "loop-interchange", &LoopInterchangeLegacyPass::ID, PassInfo
::NormalCtor_t(callDefaultCtor<LoopInterchangeLegacyPass>
), false, false); Registry.registerPass(*PI, true); return PI
; } static llvm::once_flag InitializeLoopInterchangeLegacyPassPassFlag
; void llvm::initializeLoopInterchangeLegacyPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeLoopInterchangeLegacyPassPassFlag
, initializeLoopInterchangeLegacyPassPassOnce, std::ref(Registry
)); }
1763
1764Pass *llvm::createLoopInterchangePass() {
1765 return new LoopInterchangeLegacyPass();
1766}
1767
1768PreservedAnalyses LoopInterchangePass::run(LoopNest &LN,
1769 LoopAnalysisManager &AM,
1770 LoopStandardAnalysisResults &AR,
1771 LPMUpdater &U) {
1772 Function &F = *LN.getParent();
1773
1774 DependenceInfo DI(&F, &AR.AA, &AR.SE, &AR.LI);
1775 OptimizationRemarkEmitter ORE(&F);
1776 if (!LoopInterchange(&AR.SE, &AR.LI, &DI, &AR.DT, &ORE).run(LN))
1777 return PreservedAnalyses::all();
1778 return getLoopPassPreservedAnalyses();
1779}