1//===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===//
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 file implements LoopPass and LPPassManager. All loop optimization
11// and transformation passes are derived from LoopPass. LPPassManager is
12// responsible for managing LoopPasses.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/Analysis/LoopPass.h"
17#include "llvm/IR/IRPrintingPasses.h"
18#include "llvm/IR/LLVMContext.h"
19#include "llvm/IR/PassManager.h"
20#include "llvm/Support/Debug.h"
21#include "llvm/Support/Timer.h"
22#include "llvm/Support/raw_ostream.h"
23using namespace llvm;
24
25#define DEBUG_TYPE "loop-pass-manager"
26
27namespace {
28
29/// PrintLoopPass - Print a Function corresponding to a Loop.
30///
31class PrintLoopPassWrapper : public LoopPass {
32  PrintLoopPass P;
33
34public:
35  static char ID;
36  PrintLoopPassWrapper() : LoopPass(ID) {}
37  PrintLoopPassWrapper(raw_ostream &OS, const std::string &Banner)
38      : LoopPass(ID), P(OS, Banner) {}
39
40  void getAnalysisUsage(AnalysisUsage &AU) const override {
41    AU.setPreservesAll();
42  }
43
44  bool runOnLoop(Loop *L, LPPassManager &) override {
45    P.run(*L);
46    return false;
47  }
48};
49
50char PrintLoopPassWrapper::ID = 0;
51}
52
53//===----------------------------------------------------------------------===//
54// LPPassManager
55//
56
57char LPPassManager::ID = 0;
58
59LPPassManager::LPPassManager()
60  : FunctionPass(ID), PMDataManager() {
61  LI = nullptr;
62  CurrentLoop = nullptr;
63}
64
65// Inset loop into loop nest (LoopInfo) and loop queue (LQ).
66Loop &LPPassManager::addLoop(Loop *ParentLoop) {
67  // Create a new loop. LI will take ownership.
68  Loop *L = new Loop();
69
70  // Insert into the loop nest and the loop queue.
71  if (!ParentLoop) {
72    // This is the top level loop.
73    LI->addTopLevelLoop(L);
74    LQ.push_front(L);
75    return *L;
76  }
77
78  ParentLoop->addChildLoop(L);
79  // Insert L into the loop queue after the parent loop.
80  for (auto I = LQ.begin(), E = LQ.end(); I != E; ++I) {
81    if (*I == L->getParentLoop()) {
82      // deque does not support insert after.
83      ++I;
84      LQ.insert(I, 1, L);
85      break;
86    }
87  }
88  return *L;
89}
90
91/// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
92/// all loop passes.
93void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From,
94                                                  BasicBlock *To, Loop *L) {
95  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
96    LoopPass *LP = getContainedPass(Index);
97    LP->cloneBasicBlockAnalysis(From, To, L);
98  }
99}
100
101/// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes.
102void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) {
103  if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
104    for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;
105         ++BI) {
106      Instruction &I = *BI;
107      deleteSimpleAnalysisValue(&I, L);
108    }
109  }
110  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
111    LoopPass *LP = getContainedPass(Index);
112    LP->deleteAnalysisValue(V, L);
113  }
114}
115
116/// Invoke deleteAnalysisLoop hook for all passes.
117void LPPassManager::deleteSimpleAnalysisLoop(Loop *L) {
118  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
119    LoopPass *LP = getContainedPass(Index);
120    LP->deleteAnalysisLoop(L);
121  }
122}
123
124
125// Recurse through all subloops and all loops  into LQ.
126static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
127  LQ.push_back(L);
128  for (Loop::reverse_iterator I = L->rbegin(), E = L->rend(); I != E; ++I)
129    addLoopIntoQueue(*I, LQ);
130}
131
132/// Pass Manager itself does not invalidate any analysis info.
133void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
134  // LPPassManager needs LoopInfo. In the long term LoopInfo class will
135  // become part of LPPassManager.
136  Info.addRequired<LoopInfoWrapperPass>();
137  Info.setPreservesAll();
138}
139
140/// run - Execute all of the passes scheduled for execution.  Keep track of
141/// whether any of the passes modifies the function, and if so, return true.
142bool LPPassManager::runOnFunction(Function &F) {
143  auto &LIWP = getAnalysis<LoopInfoWrapperPass>();
144  LI = &LIWP.getLoopInfo();
145  bool Changed = false;
146
147  // Collect inherited analysis from Module level pass manager.
148  populateInheritedAnalysis(TPM->activeStack);
149
150  // Populate the loop queue in reverse program order. There is no clear need to
151  // process sibling loops in either forward or reverse order. There may be some
152  // advantage in deleting uses in a later loop before optimizing the
153  // definitions in an earlier loop. If we find a clear reason to process in
154  // forward order, then a forward variant of LoopPassManager should be created.
155  //
156  // Note that LoopInfo::iterator visits loops in reverse program
157  // order. Here, reverse_iterator gives us a forward order, and the LoopQueue
158  // reverses the order a third time by popping from the back.
159  for (LoopInfo::reverse_iterator I = LI->rbegin(), E = LI->rend(); I != E; ++I)
160    addLoopIntoQueue(*I, LQ);
161
162  if (LQ.empty()) // No loops, skip calling finalizers
163    return false;
164
165  // Initialization
166  for (std::deque<Loop *>::const_iterator I = LQ.begin(), E = LQ.end();
167       I != E; ++I) {
168    Loop *L = *I;
169    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
170      LoopPass *P = getContainedPass(Index);
171      Changed |= P->doInitialization(L, *this);
172    }
173  }
174
175  // Walk Loops
176  while (!LQ.empty()) {
177
178    CurrentLoop = LQ.back();
179    // Run all passes on the current Loop.
180    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
181      LoopPass *P = getContainedPass(Index);
182
183      dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
184                   CurrentLoop->getHeader()->getName());
185      dumpRequiredSet(P);
186
187      initializeAnalysisImpl(P);
188
189      {
190        PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
191        TimeRegion PassTimer(getPassTimer(P));
192
193        Changed |= P->runOnLoop(CurrentLoop, *this);
194      }
195
196      if (Changed)
197        dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,
198                     CurrentLoop->isUnloop()
199                         ? "<deleted>"
200                         : CurrentLoop->getHeader()->getName());
201      dumpPreservedSet(P);
202
203      if (CurrentLoop->isUnloop()) {
204        // Notify passes that the loop is being deleted.
205        deleteSimpleAnalysisLoop(CurrentLoop);
206      } else {
207        // Manually check that this loop is still healthy. This is done
208        // instead of relying on LoopInfo::verifyLoop since LoopInfo
209        // is a function pass and it's really expensive to verify every
210        // loop in the function every time. That level of checking can be
211        // enabled with the -verify-loop-info option.
212        {
213          TimeRegion PassTimer(getPassTimer(&LIWP));
214          CurrentLoop->verifyLoop();
215        }
216
217        // Then call the regular verifyAnalysis functions.
218        verifyPreservedAnalysis(P);
219
220        F.getContext().yield();
221      }
222
223      removeNotPreservedAnalysis(P);
224      recordAvailableAnalysis(P);
225      removeDeadPasses(P, CurrentLoop->isUnloop()
226                              ? "<deleted>"
227                              : CurrentLoop->getHeader()->getName(),
228                       ON_LOOP_MSG);
229
230      if (CurrentLoop->isUnloop())
231        // Do not run other passes on this loop.
232        break;
233    }
234
235    // If the loop was deleted, release all the loop passes. This frees up
236    // some memory, and avoids trouble with the pass manager trying to call
237    // verifyAnalysis on them.
238    if (CurrentLoop->isUnloop()) {
239      for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
240        Pass *P = getContainedPass(Index);
241        freePass(P, "<deleted>", ON_LOOP_MSG);
242      }
243      delete CurrentLoop;
244    }
245
246    // Pop the loop from queue after running all passes.
247    LQ.pop_back();
248  }
249
250  // Finalization
251  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
252    LoopPass *P = getContainedPass(Index);
253    Changed |= P->doFinalization();
254  }
255
256  return Changed;
257}
258
259/// Print passes managed by this manager
260void LPPassManager::dumpPassStructure(unsigned Offset) {
261  errs().indent(Offset*2) << "Loop Pass Manager\n";
262  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
263    Pass *P = getContainedPass(Index);
264    P->dumpPassStructure(Offset + 1);
265    dumpLastUses(P, Offset+1);
266  }
267}
268
269
270//===----------------------------------------------------------------------===//
271// LoopPass
272
273Pass *LoopPass::createPrinterPass(raw_ostream &O,
274                                  const std::string &Banner) const {
275  return new PrintLoopPassWrapper(O, Banner);
276}
277
278// Check if this pass is suitable for the current LPPassManager, if
279// available. This pass P is not suitable for a LPPassManager if P
280// is not preserving higher level analysis info used by other
281// LPPassManager passes. In such case, pop LPPassManager from the
282// stack. This will force assignPassManager() to create new
283// LPPassManger as expected.
284void LoopPass::preparePassManager(PMStack &PMS) {
285
286  // Find LPPassManager
287  while (!PMS.empty() &&
288         PMS.top()->getPassManagerType() > PMT_LoopPassManager)
289    PMS.pop();
290
291  // If this pass is destroying high level information that is used
292  // by other passes that are managed by LPM then do not insert
293  // this pass in current LPM. Use new LPPassManager.
294  if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&
295      !PMS.top()->preserveHigherLevelAnalysis(this))
296    PMS.pop();
297}
298
299/// Assign pass manager to manage this pass.
300void LoopPass::assignPassManager(PMStack &PMS,
301                                 PassManagerType PreferredType) {
302  // Find LPPassManager
303  while (!PMS.empty() &&
304         PMS.top()->getPassManagerType() > PMT_LoopPassManager)
305    PMS.pop();
306
307  LPPassManager *LPPM;
308  if (PMS.top()->getPassManagerType() == PMT_LoopPassManager)
309    LPPM = (LPPassManager*)PMS.top();
310  else {
311    // Create new Loop Pass Manager if it does not exist.
312    assert (!PMS.empty() && "Unable to create Loop Pass Manager");
313    PMDataManager *PMD = PMS.top();
314
315    // [1] Create new Loop Pass Manager
316    LPPM = new LPPassManager();
317    LPPM->populateInheritedAnalysis(PMS);
318
319    // [2] Set up new manager's top level manager
320    PMTopLevelManager *TPM = PMD->getTopLevelManager();
321    TPM->addIndirectPassManager(LPPM);
322
323    // [3] Assign manager to manage this new manager. This may create
324    // and push new managers into PMS
325    Pass *P = LPPM->getAsPass();
326    TPM->schedulePass(P);
327
328    // [4] Push new manager into PMS
329    PMS.push(LPPM);
330  }
331
332  LPPM->add(this);
333}
334
335// Containing function has Attribute::OptimizeNone and transformation
336// passes should skip it.
337bool LoopPass::skipOptnoneFunction(const Loop *L) const {
338  const Function *F = L->getHeader()->getParent();
339  if (F && F->hasFnAttribute(Attribute::OptimizeNone)) {
340    // FIXME: Report this to dbgs() only once per function.
341    DEBUG(dbgs() << "Skipping pass '" << getPassName()
342          << "' in function " << F->getName() << "\n");
343    // FIXME: Delete loop from pass manager's queue?
344    return true;
345  }
346  return false;
347}
348