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