Bug Summary

File:lib/Transforms/Scalar/LoopInterchange.cpp
Location:line 875, column 5
Description:Value stored to 'InnerLoopPreHeader' is never read

Annotated Source Code

1//===- LoopInterchange.cpp - Loop interchange pass------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This Pass handles loop interchange transform.
11// This pass interchanges loops to provide a more cache-friendly memory access
12// patterns.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/Analysis/AliasAnalysis.h"
18#include "llvm/Analysis/AliasSetTracker.h"
19#include "llvm/Analysis/AssumptionCache.h"
20#include "llvm/Analysis/BlockFrequencyInfo.h"
21#include "llvm/Analysis/CodeMetrics.h"
22#include "llvm/Analysis/DependenceAnalysis.h"
23#include "llvm/Analysis/LoopInfo.h"
24#include "llvm/Analysis/LoopIterator.h"
25#include "llvm/Analysis/LoopPass.h"
26#include "llvm/Analysis/ScalarEvolution.h"
27#include "llvm/Analysis/ScalarEvolutionExpander.h"
28#include "llvm/Analysis/ScalarEvolutionExpressions.h"
29#include "llvm/Analysis/TargetTransformInfo.h"
30#include "llvm/Analysis/ValueTracking.h"
31#include "llvm/IR/Dominators.h"
32#include "llvm/IR/Function.h"
33#include "llvm/IR/IRBuilder.h"
34#include "llvm/IR/InstIterator.h"
35#include "llvm/IR/IntrinsicInst.h"
36#include "llvm/IR/Module.h"
37#include "llvm/Pass.h"
38#include "llvm/Support/Debug.h"
39#include "llvm/Support/raw_ostream.h"
40#include "llvm/Transforms/Scalar.h"
41#include "llvm/Transforms/Utils/BasicBlockUtils.h"
42#include "llvm/Transforms/Utils/LoopUtils.h"
43#include "llvm/Transforms/Utils/SSAUpdater.h"
44using namespace llvm;
45
46#define DEBUG_TYPE"loop-interchange" "loop-interchange"
47
48namespace {
49
50typedef SmallVector<Loop *, 8> LoopVector;
51
52// TODO: Check if we can use a sparse matrix here.
53typedef std::vector<std::vector<char>> CharMatrix;
54
55// Maximum number of dependencies that can be handled in the dependency matrix.
56static const unsigned MaxMemInstrCount = 100;
57
58// Maximum loop depth supported.
59static const unsigned MaxLoopNestDepth = 10;
60
61struct LoopInterchange;
62
63#ifdef DUMP_DEP_MATRICIES
64void printDepMatrix(CharMatrix &DepMatrix) {
65 for (auto I = DepMatrix.begin(), E = DepMatrix.end(); I != E; ++I) {
66 std::vector<char> Vec = *I;
67 for (auto II = Vec.begin(), EE = Vec.end(); II != EE; ++II)
68 DEBUG(dbgs() << *II << " ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << *II << " "; } }
while (0);
69 DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "\n"; } } while (0);
70 }
71}
72#endif
73
74static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
75 Loop *L, DependenceAnalysis *DA) {
76 typedef SmallVector<Value *, 16> ValueVector;
77 ValueVector MemInstr;
78
79 if (Level > MaxLoopNestDepth) {
80 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 (0)
81 << MaxLoopNestDepth << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Cannot handle loops of depth greater than "
<< MaxLoopNestDepth << "\n"; } } while (0);
82 return false;
83 }
84
85 // For each block.
86 for (Loop::block_iterator BB = L->block_begin(), BE = L->block_end();
87 BB != BE; ++BB) {
88 // Scan the BB and collect legal loads and stores.
89 for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E;
90 ++I) {
91 Instruction *Ins = dyn_cast<Instruction>(I);
92 if (!Ins)
93 return false;
94 LoadInst *Ld = dyn_cast<LoadInst>(I);
95 StoreInst *St = dyn_cast<StoreInst>(I);
96 if (!St && !Ld)
97 continue;
98 if (Ld && !Ld->isSimple())
99 return false;
100 if (St && !St->isSimple())
101 return false;
102 MemInstr.push_back(&*I);
103 }
104 }
105
106 DEBUG(dbgs() << "Found " << MemInstr.size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Found " << MemInstr
.size() << " Loads and Stores to analyze\n"; } } while (
0)
107 << " 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 (
0);
108
109 ValueVector::iterator I, IE, J, JE;
110
111 for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
112 for (J = I, JE = MemInstr.end(); J != JE; ++J) {
113 std::vector<char> Dep;
114 Instruction *Src = dyn_cast<Instruction>(*I);
115 Instruction *Des = dyn_cast<Instruction>(*J);
116 if (Src == Des)
117 continue;
118 if (isa<LoadInst>(Src) && isa<LoadInst>(Des))
119 continue;
120 if (auto D = DA->depends(Src, Des, true)) {
121 DEBUG(dbgs() << "Found Dependency between Src=" << Src << " Des=" << Desdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Found Dependency between Src="
<< Src << " Des=" << Des << "\n"; } }
while (0)
122 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Found Dependency between Src="
<< Src << " Des=" << Des << "\n"; } }
while (0);
123 if (D->isFlow()) {
124 // TODO: Handle Flow dependence.Check if it is sufficient to populate
125 // the Dependence Matrix with the direction reversed.
126 DEBUG(dbgs() << "Flow dependence not handled")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Flow dependence not handled"
; } } while (0);
127 return false;
128 }
129 if (D->isAnti()) {
130 DEBUG(dbgs() << "Found Anti dependence \n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Found Anti dependence \n"
; } } while (0);
131 unsigned Levels = D->getLevels();
132 char Direction;
133 for (unsigned II = 1; II <= Levels; ++II) {
134 const SCEV *Distance = D->getDistance(II);
135 const SCEVConstant *SCEVConst =
136 dyn_cast_or_null<SCEVConstant>(Distance);
137 if (SCEVConst) {
138 const ConstantInt *CI = SCEVConst->getValue();
139 if (CI->isNegative())
140 Direction = '<';
141 else if (CI->isZero())
142 Direction = '=';
143 else
144 Direction = '>';
145 Dep.push_back(Direction);
146 } else if (D->isScalar(II)) {
147 Direction = 'S';
148 Dep.push_back(Direction);
149 } else {
150 unsigned Dir = D->getDirection(II);
151 if (Dir == Dependence::DVEntry::LT ||
152 Dir == Dependence::DVEntry::LE)
153 Direction = '<';
154 else if (Dir == Dependence::DVEntry::GT ||
155 Dir == Dependence::DVEntry::GE)
156 Direction = '>';
157 else if (Dir == Dependence::DVEntry::EQ)
158 Direction = '=';
159 else
160 Direction = '*';
161 Dep.push_back(Direction);
162 }
163 }
164 while (Dep.size() != Level) {
165 Dep.push_back('I');
166 }
167
168 DepMatrix.push_back(Dep);
169 if (DepMatrix.size() > MaxMemInstrCount) {
170 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 (0)
171 << " dependencies inside loop\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Cannot handle more than "
<< MaxMemInstrCount << " dependencies inside loop\n"
; } } while (0);
172 return false;
173 }
174 }
175 }
176 }
177 }
178
179 // We don't have a DepMatrix to check legality return false.
180 if (DepMatrix.size() == 0)
181 return false;
182 return true;
183}
184
185// A loop is moved from index 'from' to an index 'to'. Update the Dependence
186// matrix by exchanging the two columns.
187static void interChangeDepedencies(CharMatrix &DepMatrix, unsigned FromIndx,
188 unsigned ToIndx) {
189 unsigned numRows = DepMatrix.size();
190 for (unsigned i = 0; i < numRows; ++i) {
191 char TmpVal = DepMatrix[i][ToIndx];
192 DepMatrix[i][ToIndx] = DepMatrix[i][FromIndx];
193 DepMatrix[i][FromIndx] = TmpVal;
194 }
195}
196
197// Checks if outermost non '=','S'or'I' dependence in the dependence matrix is
198// '>'
199static bool isOuterMostDepPositive(CharMatrix &DepMatrix, unsigned Row,
200 unsigned Column) {
201 for (unsigned i = 0; i <= Column; ++i) {
202 if (DepMatrix[Row][i] == '<')
203 return false;
204 if (DepMatrix[Row][i] == '>')
205 return true;
206 }
207 // All dependencies were '=','S' or 'I'
208 return false;
209}
210
211// Checks if no dependence exist in the dependency matrix in Row before Column.
212static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row,
213 unsigned Column) {
214 for (unsigned i = 0; i < Column; ++i) {
215 if (DepMatrix[Row][i] != '=' || DepMatrix[Row][i] != 'S' ||
216 DepMatrix[Row][i] != 'I')
217 return false;
218 }
219 return true;
220}
221
222static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row,
223 unsigned OuterLoopId, char InnerDep,
224 char OuterDep) {
225
226 if (isOuterMostDepPositive(DepMatrix, Row, OuterLoopId))
227 return false;
228
229 if (InnerDep == OuterDep)
230 return true;
231
232 // It is legal to interchange if and only if after interchange no row has a
233 // '>' direction as the leftmost non-'='.
234
235 if (InnerDep == '=' || InnerDep == 'S' || InnerDep == 'I')
236 return true;
237
238 if (InnerDep == '<')
239 return true;
240
241 if (InnerDep == '>') {
242 // If OuterLoopId represents outermost loop then interchanging will make the
243 // 1st dependency as '>'
244 if (OuterLoopId == 0)
245 return false;
246
247 // If all dependencies before OuterloopId are '=','S'or 'I'. Then
248 // interchanging will result in this row having an outermost non '='
249 // dependency of '>'
250 if (!containsNoDependence(DepMatrix, Row, OuterLoopId))
251 return true;
252 }
253
254 return false;
255}
256
257// Checks if it is legal to interchange 2 loops.
258// [Theorem] A permutation of the loops in a perfect nest is legal if and only
259// if
260// the direction matrix, after the same permutation is applied to its columns,
261// has no ">" direction as the leftmost non-"=" direction in any row.
262static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,
263 unsigned InnerLoopId,
264 unsigned OuterLoopId) {
265
266 unsigned NumRows = DepMatrix.size();
267 // For each row check if it is valid to interchange.
268 for (unsigned Row = 0; Row < NumRows; ++Row) {
269 char InnerDep = DepMatrix[Row][InnerLoopId];
270 char OuterDep = DepMatrix[Row][OuterLoopId];
271 if (InnerDep == '*' || OuterDep == '*')
272 return false;
273 else if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep,
274 OuterDep))
275 return false;
276 }
277 return true;
278}
279
280static void populateWorklist(Loop &L, SmallVector<LoopVector, 8> &V) {
281
282 DEBUG(dbgs() << "Calling populateWorklist called\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Calling populateWorklist called\n"
; } } while (0);
283 LoopVector LoopList;
284 Loop *CurrentLoop = &L;
285 const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
286 while (!Vec->empty()) {
287 // The current loop has multiple subloops in it hence it is not tightly
288 // nested.
289 // Discard all loops above it added into Worklist.
290 if (Vec->size() != 1) {
291 LoopList.clear();
292 return;
293 }
294 LoopList.push_back(CurrentLoop);
295 CurrentLoop = Vec->front();
296 Vec = &CurrentLoop->getSubLoops();
297 }
298 LoopList.push_back(CurrentLoop);
299 V.push_back(std::move(LoopList));
300}
301
302static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) {
303 PHINode *InnerIndexVar = L->getCanonicalInductionVariable();
304 if (InnerIndexVar)
305 return InnerIndexVar;
306 if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr)
307 return nullptr;
308 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
309 PHINode *PhiVar = cast<PHINode>(I);
310 Type *PhiTy = PhiVar->getType();
311 if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
312 !PhiTy->isPointerTy())
313 return nullptr;
314 const SCEVAddRecExpr *AddRec =
315 dyn_cast<SCEVAddRecExpr>(SE->getSCEV(PhiVar));
316 if (!AddRec || !AddRec->isAffine())
317 continue;
318 const SCEV *Step = AddRec->getStepRecurrence(*SE);
319 const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
320 if (!C)
321 continue;
322 // Found the induction variable.
323 // FIXME: Handle loops with more than one induction variable. Note that,
324 // currently, legality makes sure we have only one induction variable.
325 return PhiVar;
326 }
327 return nullptr;
328}
329
330/// LoopInterchangeLegality checks if it is legal to interchange the loop.
331class LoopInterchangeLegality {
332public:
333 LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
334 LoopInterchange *Pass)
335 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), CurrentPass(Pass),
336 InnerLoopHasReduction(false) {}
337
338 /// Check if the loops can be interchanged.
339 bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
340 CharMatrix &DepMatrix);
341 /// Check if the loop structure is understood. We do not handle triangular
342 /// loops for now.
343 bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
344
345 bool currentLimitations();
346
347 bool hasInnerLoopReduction() { return InnerLoopHasReduction; }
348
349private:
350 bool tightlyNested(Loop *Outer, Loop *Inner);
351 bool containsUnsafeInstructionsInHeader(BasicBlock *BB);
352 bool areAllUsesReductions(Instruction *Ins, Loop *L);
353 bool containsUnsafeInstructionsInLatch(BasicBlock *BB);
354 bool findInductionAndReductions(Loop *L,
355 SmallVector<PHINode *, 8> &Inductions,
356 SmallVector<PHINode *, 8> &Reductions);
357 Loop *OuterLoop;
358 Loop *InnerLoop;
359
360 /// Scev analysis.
361 ScalarEvolution *SE;
362 LoopInterchange *CurrentPass;
363
364 bool InnerLoopHasReduction;
365};
366
367/// LoopInterchangeProfitability checks if it is profitable to interchange the
368/// loop.
369class LoopInterchangeProfitability {
370public:
371 LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE)
372 : OuterLoop(Outer), InnerLoop(Inner), SE(SE) {}
373
374 /// Check if the loop interchange is profitable.
375 bool isProfitable(unsigned InnerLoopId, unsigned OuterLoopId,
376 CharMatrix &DepMatrix);
377
378private:
379 int getInstrOrderCost();
380
381 Loop *OuterLoop;
382 Loop *InnerLoop;
383
384 /// Scev analysis.
385 ScalarEvolution *SE;
386};
387
388/// LoopInterchangeTransform interchanges the loop.
389class LoopInterchangeTransform {
390public:
391 LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
392 LoopInfo *LI, DominatorTree *DT,
393 LoopInterchange *Pass, BasicBlock *LoopNestExit,
394 bool InnerLoopContainsReductions)
395 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
396 LoopExit(LoopNestExit),
397 InnerLoopHasReduction(InnerLoopContainsReductions) {}
398
399 /// Interchange OuterLoop and InnerLoop.
400 bool transform();
401 void restructureLoops(Loop *InnerLoop, Loop *OuterLoop);
402 void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
403
404private:
405 void splitInnerLoopLatch(Instruction *);
406 void splitOuterLoopLatch();
407 void splitInnerLoopHeader();
408 bool adjustLoopLinks();
409 void adjustLoopPreheaders();
410 void adjustOuterLoopPreheader();
411 void adjustInnerLoopPreheader();
412 bool adjustLoopBranches();
413 void updateIncomingBlock(BasicBlock *CurrBlock, BasicBlock *OldPred,
414 BasicBlock *NewPred);
415
416 Loop *OuterLoop;
417 Loop *InnerLoop;
418
419 /// Scev analysis.
420 ScalarEvolution *SE;
421 LoopInfo *LI;
422 DominatorTree *DT;
423 BasicBlock *LoopExit;
424 bool InnerLoopHasReduction;
425};
426
427// Main LoopInterchange Pass.
428struct LoopInterchange : public FunctionPass {
429 static char ID;
430 ScalarEvolution *SE;
431 LoopInfo *LI;
432 DependenceAnalysis *DA;
433 DominatorTree *DT;
434 LoopInterchange()
435 : FunctionPass(ID), SE(nullptr), LI(nullptr), DA(nullptr), DT(nullptr) {
436 initializeLoopInterchangePass(*PassRegistry::getPassRegistry());
437 }
438
439 void getAnalysisUsage(AnalysisUsage &AU) const override {
440 AU.addRequired<ScalarEvolutionWrapperPass>();
441 AU.addRequired<AAResultsWrapperPass>();
442 AU.addRequired<DominatorTreeWrapperPass>();
443 AU.addRequired<LoopInfoWrapperPass>();
444 AU.addRequired<DependenceAnalysis>();
445 AU.addRequiredID(LoopSimplifyID);
446 AU.addRequiredID(LCSSAID);
447 }
448
449 bool runOnFunction(Function &F) override {
450 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
451 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
452 DA = &getAnalysis<DependenceAnalysis>();
453 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
454 DT = DTWP ? &DTWP->getDomTree() : nullptr;
455 // Build up a worklist of loop pairs to analyze.
456 SmallVector<LoopVector, 8> Worklist;
457
458 for (Loop *L : *LI)
459 populateWorklist(*L, Worklist);
460
461 DEBUG(dbgs() << "Worklist size = " << Worklist.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Worklist size = " <<
Worklist.size() << "\n"; } } while (0);
462 bool Changed = true;
463 while (!Worklist.empty()) {
464 LoopVector LoopList = Worklist.pop_back_val();
465 Changed = processLoopList(LoopList, F);
466 }
467 return Changed;
468 }
469
470 bool isComputableLoopNest(LoopVector LoopList) {
471 for (auto I = LoopList.begin(), E = LoopList.end(); I != E; ++I) {
472 Loop *L = *I;
473 const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
474 if (ExitCountOuter == SE->getCouldNotCompute()) {
475 DEBUG(dbgs() << "Couldn't compute Backedge count\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Couldn't compute Backedge count\n"
; } } while (0);
476 return false;
477 }
478 if (L->getNumBackEdges() != 1) {
479 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 (0);
480 return false;
481 }
482 if (!L->getExitingBlock()) {
483 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 (0);
484 return false;
485 }
486 }
487 return true;
488 }
489
490 unsigned selectLoopForInterchange(LoopVector LoopList) {
491 // TODO: Add a better heuristic to select the loop to be interchanged based
492 // on the dependence matrix. Currently we select the innermost loop.
493 return LoopList.size() - 1;
494 }
495
496 bool processLoopList(LoopVector LoopList, Function &F) {
497
498 bool Changed = false;
499 CharMatrix DependencyMatrix;
500 if (LoopList.size() < 2) {
501 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 (0);
502 return false;
503 }
504 if (!isComputableLoopNest(LoopList)) {
505 DEBUG(dbgs() << "Not vaild loop candidate for interchange\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Not vaild loop candidate for interchange\n"
; } } while (0);
506 return false;
507 }
508 Loop *OuterMostLoop = *(LoopList.begin());
509
510 DEBUG(dbgs() << "Processing LoopList of size = " << LoopList.size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Processing LoopList of size = "
<< LoopList.size() << "\n"; } } while (0)
511 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Processing LoopList of size = "
<< LoopList.size() << "\n"; } } while (0);
512
513 if (!populateDependencyMatrix(DependencyMatrix, LoopList.size(),
514 OuterMostLoop, DA)) {
515 DEBUG(dbgs() << "Populating Dependency matrix failed\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Populating Dependency matrix failed\n"
; } } while (0);
516 return false;
517 }
518#ifdef DUMP_DEP_MATRICIES
519 DEBUG(dbgs() << "Dependence before inter change \n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Dependence before inter change \n"
; } } while (0);
520 printDepMatrix(DependencyMatrix);
521#endif
522
523 BasicBlock *OuterMostLoopLatch = OuterMostLoop->getLoopLatch();
524 BranchInst *OuterMostLoopLatchBI =
525 dyn_cast<BranchInst>(OuterMostLoopLatch->getTerminator());
526 if (!OuterMostLoopLatchBI)
527 return false;
528
529 // Since we currently do not handle LCSSA PHI's any failure in loop
530 // condition will now branch to LoopNestExit.
531 // TODO: This should be removed once we handle LCSSA PHI nodes.
532
533 // Get the Outermost loop exit.
534 BasicBlock *LoopNestExit;
535 if (OuterMostLoopLatchBI->getSuccessor(0) == OuterMostLoop->getHeader())
536 LoopNestExit = OuterMostLoopLatchBI->getSuccessor(1);
537 else
538 LoopNestExit = OuterMostLoopLatchBI->getSuccessor(0);
539
540 if (isa<PHINode>(LoopNestExit->begin())) {
541 DEBUG(dbgs() << "PHI Nodes in loop nest exit is not handled for now "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "PHI Nodes in loop nest exit is not handled for now "
"since on failure all loops branch to loop nest exit.\n"; } }
while (0)
542 "since on failure all loops branch to loop nest exit.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "PHI Nodes in loop nest exit is not handled for now "
"since on failure all loops branch to loop nest exit.\n"; } }
while (0);
543 return false;
544 }
545
546 unsigned SelecLoopId = selectLoopForInterchange(LoopList);
547 // Move the selected loop outwards to the best possible position.
548 for (unsigned i = SelecLoopId; i > 0; i--) {
549 bool Interchanged =
550 processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix);
551 if (!Interchanged)
552 return Changed;
553 // Loops interchanged reflect the same in LoopList
554 std::swap(LoopList[i - 1], LoopList[i]);
555
556 // Update the DependencyMatrix
557 interChangeDepedencies(DependencyMatrix, i, i - 1);
558 DT->recalculate(F);
559#ifdef DUMP_DEP_MATRICIES
560 DEBUG(dbgs() << "Dependence after inter change \n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Dependence after inter change \n"
; } } while (0);
561 printDepMatrix(DependencyMatrix);
562#endif
563 Changed |= Interchanged;
564 }
565 return Changed;
566 }
567
568 bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
569 unsigned OuterLoopId, BasicBlock *LoopNestExit,
570 std::vector<std::vector<char>> &DependencyMatrix) {
571
572 DEBUG(dbgs() << "Processing Innder Loop Id = " << InnerLoopIddo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Processing Innder Loop Id = "
<< InnerLoopId << " and OuterLoopId = " <<
OuterLoopId << "\n"; } } while (0)
573 << " and OuterLoopId = " << OuterLoopId << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Processing Innder Loop Id = "
<< InnerLoopId << " and OuterLoopId = " <<
OuterLoopId << "\n"; } } while (0);
574 Loop *InnerLoop = LoopList[InnerLoopId];
575 Loop *OuterLoop = LoopList[OuterLoopId];
576
577 LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, this);
578 if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
579 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 (0);
580 return false;
581 }
582 DEBUG(dbgs() << "Loops are legal to interchange\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops are legal to interchange\n"
; } } while (0);
583 LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE);
584 if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
585 DEBUG(dbgs() << "Interchanging Loops not profitable\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Interchanging Loops not profitable\n"
; } } while (0);
586 return false;
587 }
588
589 LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, this,
590 LoopNestExit, LIL.hasInnerLoopReduction());
591 LIT.transform();
592 DEBUG(dbgs() << "Loops interchanged\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops interchanged\n"
; } } while (0);
593 return true;
594 }
595};
596
597} // end of namespace
598bool LoopInterchangeLegality::areAllUsesReductions(Instruction *Ins, Loop *L) {
599 return !std::any_of(Ins->user_begin(), Ins->user_end(), [=](User *U) -> bool {
600 PHINode *UserIns = dyn_cast<PHINode>(U);
601 RecurrenceDescriptor RD;
602 return !UserIns || !RecurrenceDescriptor::isReductionPHI(UserIns, L, RD);
603 });
604}
605
606bool LoopInterchangeLegality::containsUnsafeInstructionsInHeader(
607 BasicBlock *BB) {
608 for (auto I = BB->begin(), E = BB->end(); I != E; ++I) {
609 // Load corresponding to reduction PHI's are safe while concluding if
610 // tightly nested.
611 if (LoadInst *L = dyn_cast<LoadInst>(I)) {
612 if (!areAllUsesReductions(L, InnerLoop))
613 return true;
614 } else if (I->mayHaveSideEffects() || I->mayReadFromMemory())
615 return true;
616 }
617 return false;
618}
619
620bool LoopInterchangeLegality::containsUnsafeInstructionsInLatch(
621 BasicBlock *BB) {
622 for (auto I = BB->begin(), E = BB->end(); I != E; ++I) {
623 // Stores corresponding to reductions are safe while concluding if tightly
624 // nested.
625 if (StoreInst *L = dyn_cast<StoreInst>(I)) {
626 PHINode *PHI = dyn_cast<PHINode>(L->getOperand(0));
627 if (!PHI)
628 return true;
629 } else if (I->mayHaveSideEffects() || I->mayReadFromMemory())
630 return true;
631 }
632 return false;
633}
634
635bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
636 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
637 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
638 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
639
640 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 (0);
641
642 // A perfectly nested loop will not have any branch in between the outer and
643 // inner block i.e. outer header will branch to either inner preheader and
644 // outerloop latch.
645 BranchInst *outerLoopHeaderBI =
646 dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
647 if (!outerLoopHeaderBI)
648 return false;
649 unsigned num = outerLoopHeaderBI->getNumSuccessors();
650 for (unsigned i = 0; i < num; i++) {
651 if (outerLoopHeaderBI->getSuccessor(i) != InnerLoopPreHeader &&
652 outerLoopHeaderBI->getSuccessor(i) != OuterLoopLatch)
653 return false;
654 }
655
656 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 (0);
657 // We do not have any basic block in between now make sure the outer header
658 // and outer loop latch doesn't contain any unsafe instructions.
659 if (containsUnsafeInstructionsInHeader(OuterLoopHeader) ||
660 containsUnsafeInstructionsInLatch(OuterLoopLatch))
661 return false;
662
663 DEBUG(dbgs() << "Loops are perfectly nested \n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops are perfectly nested \n"
; } } while (0);
664 // We have a perfect loop nest.
665 return true;
666}
667
668
669bool LoopInterchangeLegality::isLoopStructureUnderstood(
670 PHINode *InnerInduction) {
671
672 unsigned Num = InnerInduction->getNumOperands();
673 BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
674 for (unsigned i = 0; i < Num; ++i) {
675 Value *Val = InnerInduction->getOperand(i);
676 if (isa<Constant>(Val))
677 continue;
678 Instruction *I = dyn_cast<Instruction>(Val);
679 if (!I)
680 return false;
681 // TODO: Handle triangular loops.
682 // e.g. for(int i=0;i<N;i++)
683 // for(int j=i;j<N;j++)
684 unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
685 if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
686 InnerLoopPreheader &&
687 !OuterLoop->isLoopInvariant(I)) {
688 return false;
689 }
690 }
691 return true;
692}
693
694bool LoopInterchangeLegality::findInductionAndReductions(
695 Loop *L, SmallVector<PHINode *, 8> &Inductions,
696 SmallVector<PHINode *, 8> &Reductions) {
697 if (!L->getLoopLatch() || !L->getLoopPredecessor())
698 return false;
699 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
700 RecurrenceDescriptor RD;
701 InductionDescriptor ID;
702 PHINode *PHI = cast<PHINode>(I);
703 if (InductionDescriptor::isInductionPHI(PHI, SE, ID))
704 Inductions.push_back(PHI);
705 else if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD))
706 Reductions.push_back(PHI);
707 else {
708 DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Failed to recognize PHI as an induction or reduction.\n"
; } } while (0)
709 dbgs() << "Failed to recognize PHI as an induction or reduction.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Failed to recognize PHI as an induction or reduction.\n"
; } } while (0);
710 return false;
711 }
712 }
713 return true;
714}
715
716static bool containsSafePHI(BasicBlock *Block, bool isOuterLoopExitBlock) {
717 for (auto I = Block->begin(); isa<PHINode>(I); ++I) {
718 PHINode *PHI = cast<PHINode>(I);
719 // Reduction lcssa phi will have only 1 incoming block that from loop latch.
720 if (PHI->getNumIncomingValues() > 1)
721 return false;
722 Instruction *Ins = dyn_cast<Instruction>(PHI->getIncomingValue(0));
723 if (!Ins)
724 return false;
725 // Incoming value for lcssa phi's in outer loop exit can only be inner loop
726 // exits lcssa phi else it would not be tightly nested.
727 if (!isa<PHINode>(Ins) && isOuterLoopExitBlock)
728 return false;
729 }
730 return true;
731}
732
733static BasicBlock *getLoopLatchExitBlock(BasicBlock *LatchBlock,
734 BasicBlock *LoopHeader) {
735 if (BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator())) {
736 unsigned Num = BI->getNumSuccessors();
737 assert(Num == 2)((Num == 2) ? static_cast<void> (0) : __assert_fail ("Num == 2"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn255637/lib/Transforms/Scalar/LoopInterchange.cpp"
, 737, __PRETTY_FUNCTION__));
738 for (unsigned i = 0; i < Num; ++i) {
739 if (BI->getSuccessor(i) == LoopHeader)
740 continue;
741 return BI->getSuccessor(i);
742 }
743 }
744 return nullptr;
745}
746
747// This function indicates the current limitations in the transform as a result
748// of which we do not proceed.
749bool LoopInterchangeLegality::currentLimitations() {
750
751 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
752 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
753 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
754 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
755 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
756
757 PHINode *InnerInductionVar;
758 SmallVector<PHINode *, 8> Inductions;
759 SmallVector<PHINode *, 8> Reductions;
760 if (!findInductionAndReductions(InnerLoop, Inductions, Reductions))
761 return true;
762
763 // TODO: Currently we handle only loops with 1 induction variable.
764 if (Inductions.size() != 1) {
765 DEBUG(dbgs() << "We currently only support loops with 1 induction variable."do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "We currently only support loops with 1 induction variable."
<< "Failed to interchange due to current limitation\n"
; } } while (0)
766 << "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 (0);
767 return true;
768 }
769 if (Reductions.size() > 0)
770 InnerLoopHasReduction = true;
771
772 InnerInductionVar = Inductions.pop_back_val();
773 Reductions.clear();
774 if (!findInductionAndReductions(OuterLoop, Inductions, Reductions))
775 return true;
776
777 // Outer loop cannot have reduction because then loops will not be tightly
778 // nested.
779 if (!Reductions.empty())
780 return true;
781 // TODO: Currently we handle only loops with 1 induction variable.
782 if (Inductions.size() != 1)
783 return true;
784
785 // TODO: Triangular loops are not handled for now.
786 if (!isLoopStructureUnderstood(InnerInductionVar)) {
787 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 (0);
788 return true;
789 }
790
791 // TODO: We only handle LCSSA PHI's corresponding to reduction for now.
792 BasicBlock *LoopExitBlock =
793 getLoopLatchExitBlock(OuterLoopLatch, OuterLoopHeader);
794 if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, true))
795 return true;
796
797 LoopExitBlock = getLoopLatchExitBlock(InnerLoopLatch, InnerLoopHeader);
798 if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, false))
799 return true;
800
801 // TODO: Current limitation: Since we split the inner loop latch at the point
802 // were induction variable is incremented (induction.next); We cannot have
803 // more than 1 user of induction.next since it would result in broken code
804 // after split.
805 // e.g.
806 // for(i=0;i<N;i++) {
807 // for(j = 0;j<M;j++) {
808 // A[j+1][i+2] = A[j][i]+k;
809 // }
810 // }
811 bool FoundInduction = false;
812 Instruction *InnerIndexVarInc = nullptr;
813 if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader)
814 InnerIndexVarInc =
815 dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1));
816 else
817 InnerIndexVarInc =
818 dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0));
819
820 if (!InnerIndexVarInc)
821 return true;
822
823 // Since we split the inner loop latch on this induction variable. Make sure
824 // we do not have any instruction between the induction variable and branch
825 // instruction.
826
827 for (auto I = InnerLoopLatch->rbegin(), E = InnerLoopLatch->rend();
828 I != E && !FoundInduction; ++I) {
829 if (isa<BranchInst>(*I) || isa<CmpInst>(*I) || isa<TruncInst>(*I))
830 continue;
831 const Instruction &Ins = *I;
832 // We found an instruction. If this is not induction variable then it is not
833 // safe to split this loop latch.
834 if (!Ins.isIdenticalTo(InnerIndexVarInc))
835 return true;
836 else
837 FoundInduction = true;
838 }
839 // The loop latch ended and we didn't find the induction variable return as
840 // current limitation.
841 if (!FoundInduction)
842 return true;
843
844 return false;
845}
846
847bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
848 unsigned OuterLoopId,
849 CharMatrix &DepMatrix) {
850
851 if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
852 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 (0)
853 << "and OuterLoopId = " << OuterLoopIddo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Failed interchange InnerLoopId = "
<< InnerLoopId << "and OuterLoopId = " << OuterLoopId
<< "due to dependence\n"; } } while (0)
854 << "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 (0);
855 return false;
856 }
857
858 // Create unique Preheaders if we already do not have one.
859 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
860 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
861
862 // Create a unique outer preheader -
863 // 1) If OuterLoop preheader is not present.
864 // 2) If OuterLoop Preheader is same as OuterLoop Header
865 // 3) If OuterLoop Preheader is same as Header of the previous loop.
866 // 4) If OuterLoop Preheader is Entry node.
867 if (!OuterLoopPreHeader || OuterLoopPreHeader == OuterLoop->getHeader() ||
868 isa<PHINode>(OuterLoopPreHeader->begin()) ||
869 !OuterLoopPreHeader->getUniquePredecessor()) {
870 OuterLoopPreHeader = InsertPreheaderForLoop(OuterLoop, CurrentPass);
871 }
872
873 if (!InnerLoopPreHeader || InnerLoopPreHeader == InnerLoop->getHeader() ||
874 InnerLoopPreHeader == OuterLoop->getHeader()) {
875 InnerLoopPreHeader = InsertPreheaderForLoop(InnerLoop, CurrentPass);
Value stored to 'InnerLoopPreHeader' is never read
876 }
877
878 // TODO: The loops could not be interchanged due to current limitations in the
879 // transform module.
880 if (currentLimitations()) {
881 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 (0);
882 return false;
883 }
884
885 // Check if the loops are tightly nested.
886 if (!tightlyNested(OuterLoop, InnerLoop)) {
887 DEBUG(dbgs() << "Loops not tightly nested\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Loops not tightly nested\n"
; } } while (0);
888 return false;
889 }
890
891 return true;
892}
893
894int LoopInterchangeProfitability::getInstrOrderCost() {
895 unsigned GoodOrder, BadOrder;
896 BadOrder = GoodOrder = 0;
897 for (auto BI = InnerLoop->block_begin(), BE = InnerLoop->block_end();
898 BI != BE; ++BI) {
899 for (auto I = (*BI)->begin(), E = (*BI)->end(); I != E; ++I) {
900 const Instruction &Ins = *I;
901 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) {
902 unsigned NumOp = GEP->getNumOperands();
903 bool FoundInnerInduction = false;
904 bool FoundOuterInduction = false;
905 for (unsigned i = 0; i < NumOp; ++i) {
906 const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i));
907 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal);
908 if (!AR)
909 continue;
910
911 // If we find the inner induction after an outer induction e.g.
912 // for(int i=0;i<N;i++)
913 // for(int j=0;j<N;j++)
914 // A[i][j] = A[i-1][j-1]+k;
915 // then it is a good order.
916 if (AR->getLoop() == InnerLoop) {
917 // We found an InnerLoop induction after OuterLoop induction. It is
918 // a good order.
919 FoundInnerInduction = true;
920 if (FoundOuterInduction) {
921 GoodOrder++;
922 break;
923 }
924 }
925 // If we find the outer induction after an inner induction e.g.
926 // for(int i=0;i<N;i++)
927 // for(int j=0;j<N;j++)
928 // A[j][i] = A[j-1][i-1]+k;
929 // then it is a bad order.
930 if (AR->getLoop() == OuterLoop) {
931 // We found an OuterLoop induction after InnerLoop induction. It is
932 // a bad order.
933 FoundOuterInduction = true;
934 if (FoundInnerInduction) {
935 BadOrder++;
936 break;
937 }
938 }
939 }
940 }
941 }
942 }
943 return GoodOrder - BadOrder;
944}
945
946static bool isProfitabileForVectorization(unsigned InnerLoopId,
947 unsigned OuterLoopId,
948 CharMatrix &DepMatrix) {
949 // TODO: Improve this heuristic to catch more cases.
950 // If the inner loop is loop independent or doesn't carry any dependency it is
951 // profitable to move this to outer position.
952 unsigned Row = DepMatrix.size();
953 for (unsigned i = 0; i < Row; ++i) {
954 if (DepMatrix[i][InnerLoopId] != 'S' && DepMatrix[i][InnerLoopId] != 'I')
955 return false;
956 // TODO: We need to improve this heuristic.
957 if (DepMatrix[i][OuterLoopId] != '=')
958 return false;
959 }
960 // If outer loop has dependence and inner loop is loop independent then it is
961 // profitable to interchange to enable parallelism.
962 return true;
963}
964
965bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId,
966 unsigned OuterLoopId,
967 CharMatrix &DepMatrix) {
968
969 // TODO: Add better profitability checks.
970 // e.g
971 // 1) Construct dependency matrix and move the one with no loop carried dep
972 // inside to enable vectorization.
973
974 // This is rough cost estimation algorithm. It counts the good and bad order
975 // of induction variables in the instruction and allows reordering if number
976 // of bad orders is more than good.
977 int Cost = 0;
978 Cost += getInstrOrderCost();
979 DEBUG(dbgs() << "Cost = " << Cost << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Cost = " << Cost
<< "\n"; } } while (0);
980 if (Cost < 0)
981 return true;
982
983 // It is not profitable as per current cache profitability model. But check if
984 // we can move this loop outside to improve parallelism.
985 bool ImprovesPar =
986 isProfitabileForVectorization(InnerLoopId, OuterLoopId, DepMatrix);
987 return ImprovesPar;
988}
989
990void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
991 Loop *InnerLoop) {
992 for (Loop::iterator I = OuterLoop->begin(), E = OuterLoop->end(); I != E;
993 ++I) {
994 if (*I == InnerLoop) {
995 OuterLoop->removeChildLoop(I);
996 return;
997 }
998 }
999 llvm_unreachable("Couldn't find loop")::llvm::llvm_unreachable_internal("Couldn't find loop", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn255637/lib/Transforms/Scalar/LoopInterchange.cpp"
, 999);
1000}
1001
1002void LoopInterchangeTransform::restructureLoops(Loop *InnerLoop,
1003 Loop *OuterLoop) {
1004 Loop *OuterLoopParent = OuterLoop->getParentLoop();
1005 if (OuterLoopParent) {
1006 // Remove the loop from its parent loop.
1007 removeChildLoop(OuterLoopParent, OuterLoop);
1008 removeChildLoop(OuterLoop, InnerLoop);
1009 OuterLoopParent->addChildLoop(InnerLoop);
1010 } else {
1011 removeChildLoop(OuterLoop, InnerLoop);
1012 LI->changeTopLevelLoop(OuterLoop, InnerLoop);
1013 }
1014
1015 while (!InnerLoop->empty())
1016 OuterLoop->addChildLoop(InnerLoop->removeChildLoop(InnerLoop->begin()));
1017
1018 InnerLoop->addChildLoop(OuterLoop);
1019}
1020
1021bool LoopInterchangeTransform::transform() {
1022
1023 DEBUG(dbgs() << "transform\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "transform\n"; } } while
(0);
1024 bool Transformed = false;
1025 Instruction *InnerIndexVar;
1026
1027 if (InnerLoop->getSubLoops().size() == 0) {
1028 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1029 DEBUG(dbgs() << "Calling Split Inner Loop\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Calling Split Inner Loop\n"
; } } while (0);
1030 PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
1031 if (!InductionPHI) {
1032 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 (0);
1033 return false;
1034 }
1035
1036 if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
1037 InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
1038 else
1039 InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
1040
1041 //
1042 // Split at the place were the induction variable is
1043 // incremented/decremented.
1044 // TODO: This splitting logic may not work always. Fix this.
1045 splitInnerLoopLatch(InnerIndexVar);
1046 DEBUG(dbgs() << "splitInnerLoopLatch Done\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "splitInnerLoopLatch Done\n"
; } } while (0);
1047
1048 // Splits the inner loops phi nodes out into a separate basic block.
1049 splitInnerLoopHeader();
1050 DEBUG(dbgs() << "splitInnerLoopHeader Done\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "splitInnerLoopHeader Done\n"
; } } while (0);
1051 }
1052
1053 Transformed |= adjustLoopLinks();
1054 if (!Transformed) {
1055 DEBUG(dbgs() << "adjustLoopLinks Failed\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "adjustLoopLinks Failed\n"
; } } while (0);
1056 return false;
1057 }
1058
1059 restructureLoops(InnerLoop, OuterLoop);
1060 return true;
1061}
1062
1063void LoopInterchangeTransform::splitInnerLoopLatch(Instruction *Inc) {
1064 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1065 BasicBlock *InnerLoopLatchPred = InnerLoopLatch;
1066 InnerLoopLatch = SplitBlock(InnerLoopLatchPred, Inc, DT, LI);
1067}
1068
1069void LoopInterchangeTransform::splitOuterLoopLatch() {
1070 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1071 BasicBlock *OuterLatchLcssaPhiBlock = OuterLoopLatch;
1072 OuterLoopLatch = SplitBlock(OuterLatchLcssaPhiBlock,
1073 OuterLoopLatch->getFirstNonPHI(), DT, LI);
1074}
1075
1076void LoopInterchangeTransform::splitInnerLoopHeader() {
1077
1078 // Split the inner loop header out. Here make sure that the reduction PHI's
1079 // stay in the innerloop body.
1080 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1081 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1082 if (InnerLoopHasReduction) {
1083 // FIXME: Check if the induction PHI will always be the first PHI.
1084 BasicBlock *New = InnerLoopHeader->splitBasicBlock(
1085 ++(InnerLoopHeader->begin()), InnerLoopHeader->getName() + ".split");
1086 if (LI)
1087 if (Loop *L = LI->getLoopFor(InnerLoopHeader))
1088 L->addBasicBlockToLoop(New, *LI);
1089
1090 // Adjust Reduction PHI's in the block.
1091 SmallVector<PHINode *, 8> PHIVec;
1092 for (auto I = New->begin(); isa<PHINode>(I); ++I) {
1093 PHINode *PHI = dyn_cast<PHINode>(I);
1094 Value *V = PHI->getIncomingValueForBlock(InnerLoopPreHeader);
1095 PHI->replaceAllUsesWith(V);
1096 PHIVec.push_back((PHI));
1097 }
1098 for (auto I = PHIVec.begin(), E = PHIVec.end(); I != E; ++I) {
1099 PHINode *P = *I;
1100 P->eraseFromParent();
1101 }
1102 } else {
1103 SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI);
1104 }
1105
1106 DEBUG(dbgs() << "Output of splitInnerLoopHeader InnerLoopHeaderSucc & "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Output of splitInnerLoopHeader InnerLoopHeaderSucc & "
"InnerLoopHeader \n"; } } while (0)
1107 "InnerLoopHeader \n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "Output of splitInnerLoopHeader InnerLoopHeaderSucc & "
"InnerLoopHeader \n"; } } while (0);
1108}
1109
1110/// \brief Move all instructions except the terminator from FromBB right before
1111/// InsertBefore
1112static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
1113 auto &ToList = InsertBefore->getParent()->getInstList();
1114 auto &FromList = FromBB->getInstList();
1115
1116 ToList.splice(InsertBefore->getIterator(), FromList, FromList.begin(),
1117 FromBB->getTerminator()->getIterator());
1118}
1119
1120void LoopInterchangeTransform::adjustOuterLoopPreheader() {
1121 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1122 BasicBlock *InnerPreHeader = InnerLoop->getLoopPreheader();
1123
1124 moveBBContents(OuterLoopPreHeader, InnerPreHeader->getTerminator());
1125}
1126
1127void LoopInterchangeTransform::adjustInnerLoopPreheader() {
1128 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1129 BasicBlock *OuterHeader = OuterLoop->getHeader();
1130
1131 moveBBContents(InnerLoopPreHeader, OuterHeader->getTerminator());
1132}
1133
1134void LoopInterchangeTransform::updateIncomingBlock(BasicBlock *CurrBlock,
1135 BasicBlock *OldPred,
1136 BasicBlock *NewPred) {
1137 for (auto I = CurrBlock->begin(); isa<PHINode>(I); ++I) {
1138 PHINode *PHI = cast<PHINode>(I);
1139 unsigned Num = PHI->getNumIncomingValues();
1140 for (unsigned i = 0; i < Num; ++i) {
1141 if (PHI->getIncomingBlock(i) == OldPred)
1142 PHI->setIncomingBlock(i, NewPred);
1143 }
1144 }
1145}
1146
1147bool LoopInterchangeTransform::adjustLoopBranches() {
1148
1149 DEBUG(dbgs() << "adjustLoopBranches called\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-interchange")) { dbgs() << "adjustLoopBranches called\n"
; } } while (0);
1150 // Adjust the loop preheader
1151 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1152 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1153 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1154 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1155 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1156 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1157 BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
1158 BasicBlock *InnerLoopLatchPredecessor =
1159 InnerLoopLatch->getUniquePredecessor();
1160 BasicBlock *InnerLoopLatchSuccessor;
1161 BasicBlock *OuterLoopLatchSuccessor;
1162
1163 BranchInst *OuterLoopLatchBI =
1164 dyn_cast<BranchInst>(OuterLoopLatch->getTerminator());
1165 BranchInst *InnerLoopLatchBI =
1166 dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
1167 BranchInst *OuterLoopHeaderBI =
1168 dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
1169 BranchInst *InnerLoopHeaderBI =
1170 dyn_cast<BranchInst>(InnerLoopHeader->getTerminator());
1171
1172 if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||
1173 !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||
1174 !InnerLoopHeaderBI)
1175 return false;
1176
1177 BranchInst *InnerLoopLatchPredecessorBI =
1178 dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator());
1179 BranchInst *OuterLoopPredecessorBI =
1180 dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator());
1181
1182 if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
1183 return false;
1184 BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
1185 if (!InnerLoopHeaderSuccessor)
1186 return false;
1187
1188 // Adjust Loop Preheader and headers
1189
1190 unsigned NumSucc = OuterLoopPredecessorBI->getNumSuccessors();
1191 for (unsigned i = 0; i < NumSucc; ++i) {
1192 if (OuterLoopPredecessorBI->getSuccessor(i) == OuterLoopPreHeader)
1193 OuterLoopPredecessorBI->setSuccessor(i, InnerLoopPreHeader);
1194 }
1195
1196 NumSucc = OuterLoopHeaderBI->getNumSuccessors();
1197 for (unsigned i = 0; i < NumSucc; ++i) {
1198 if (OuterLoopHeaderBI->getSuccessor(i) == OuterLoopLatch)
1199 OuterLoopHeaderBI->setSuccessor(i, LoopExit);
1200 else if (OuterLoopHeaderBI->getSuccessor(i) == InnerLoopPreHeader)
1201 OuterLoopHeaderBI->setSuccessor(i, InnerLoopHeaderSuccessor);
1202 }
1203
1204 // Adjust reduction PHI's now that the incoming block has changed.
1205 updateIncomingBlock(InnerLoopHeaderSuccessor, InnerLoopHeader,
1206 OuterLoopHeader);
1207
1208 BranchInst::Create(OuterLoopPreHeader, InnerLoopHeaderBI);
1209 InnerLoopHeaderBI->eraseFromParent();
1210
1211 // -------------Adjust loop latches-----------
1212 if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
1213 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
1214 else
1215 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
1216
1217 NumSucc = InnerLoopLatchPredecessorBI->getNumSuccessors();
1218 for (unsigned i = 0; i < NumSucc; ++i) {
1219 if (InnerLoopLatchPredecessorBI->getSuccessor(i) == InnerLoopLatch)
1220 InnerLoopLatchPredecessorBI->setSuccessor(i, InnerLoopLatchSuccessor);
1221 }
1222
1223 // Adjust PHI nodes in InnerLoopLatchSuccessor. Update all uses of PHI with
1224 // the value and remove this PHI node from inner loop.
1225 SmallVector<PHINode *, 8> LcssaVec;
1226 for (auto I = InnerLoopLatchSuccessor->begin(); isa<PHINode>(I); ++I) {
1227 PHINode *LcssaPhi = cast<PHINode>(I);
1228 LcssaVec.push_back(LcssaPhi);
1229 }
1230 for (auto I = LcssaVec.begin(), E = LcssaVec.end(); I != E; ++I) {
1231 PHINode *P = *I;
1232 Value *Incoming = P->getIncomingValueForBlock(InnerLoopLatch);
1233 P->replaceAllUsesWith(Incoming);
1234 P->eraseFromParent();
1235 }
1236
1237 if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
1238 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
1239 else
1240 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
1241
1242 if (InnerLoopLatchBI->getSuccessor(1) == InnerLoopLatchSuccessor)
1243 InnerLoopLatchBI->setSuccessor(1, OuterLoopLatchSuccessor);
1244 else
1245 InnerLoopLatchBI->setSuccessor(0, OuterLoopLatchSuccessor);
1246
1247 updateIncomingBlock(OuterLoopLatchSuccessor, OuterLoopLatch, InnerLoopLatch);
1248
1249 if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopLatchSuccessor) {
1250 OuterLoopLatchBI->setSuccessor(0, InnerLoopLatch);
1251 } else {
1252 OuterLoopLatchBI->setSuccessor(1, InnerLoopLatch);
1253 }
1254
1255 return true;
1256}
1257void LoopInterchangeTransform::adjustLoopPreheaders() {
1258
1259 // We have interchanged the preheaders so we need to interchange the data in
1260 // the preheader as well.
1261 // This is because the content of inner preheader was previously executed
1262 // inside the outer loop.
1263 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1264 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1265 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1266 BranchInst *InnerTermBI =
1267 cast<BranchInst>(InnerLoopPreHeader->getTerminator());
1268
1269 // These instructions should now be executed inside the loop.
1270 // Move instruction into a new block after outer header.
1271 moveBBContents(InnerLoopPreHeader, OuterLoopHeader->getTerminator());
1272 // These instructions were not executed previously in the loop so move them to
1273 // the older inner loop preheader.
1274 moveBBContents(OuterLoopPreHeader, InnerTermBI);
1275}
1276
1277bool LoopInterchangeTransform::adjustLoopLinks() {
1278
1279 // Adjust all branches in the inner and outer loop.
1280 bool Changed = adjustLoopBranches();
1281 if (Changed)
1282 adjustLoopPreheaders();
1283 return Changed;
1284}
1285
1286char LoopInterchange::ID = 0;
1287INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",static void* initializeLoopInterchangePassOnce(PassRegistry &
Registry) {
1288 "Interchanges loops for cache reuse", false, false)static void* initializeLoopInterchangePassOnce(PassRegistry &
Registry) {
1289INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
1290INITIALIZE_PASS_DEPENDENCY(DependenceAnalysis)initializeDependenceAnalysisPass(Registry);
1291INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
1292INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)initializeScalarEvolutionWrapperPassPass(Registry);
1293INITIALIZE_PASS_DEPENDENCY(LoopSimplify)initializeLoopSimplifyPass(Registry);
1294INITIALIZE_PASS_DEPENDENCY(LCSSA)initializeLCSSAPass(Registry);
1295INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)initializeLoopInfoWrapperPassPass(Registry);
1296
1297INITIALIZE_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; } void llvm::initializeLoopInterchangePass
(PassRegistry &Registry) { static volatile sys::cas_flag initialized
= 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized
, 1, 0); if (old_val == 0) { initializeLoopInterchangePassOnce
(Registry); sys::MemoryFence(); ; ; initialized = 2; ; } else
{ sys::cas_flag tmp = initialized; sys::MemoryFence(); while
(tmp != 2) { tmp = initialized; sys::MemoryFence(); } } ; }
1298 "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; } void llvm::initializeLoopInterchangePass
(PassRegistry &Registry) { static volatile sys::cas_flag initialized
= 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized
, 1, 0); if (old_val == 0) { initializeLoopInterchangePassOnce
(Registry); sys::MemoryFence(); ; ; initialized = 2; ; } else
{ sys::cas_flag tmp = initialized; sys::MemoryFence(); while
(tmp != 2) { tmp = initialized; sys::MemoryFence(); } } ; }
1299
1300Pass *llvm::createLoopInterchangePass() { return new LoopInterchange(); }