Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

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