LoopPass.cpp revision 360784 
1//===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements LoopPass and LPPassManager. All loop optimization
10// and transformation passes are derived from LoopPass. LPPassManager is
11// responsible for managing LoopPasses.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Analysis/LoopPass.h"
16#include "llvm/Analysis/LoopAnalysisManager.h"
17#include "llvm/IR/Dominators.h"
18#include "llvm/IR/IRPrintingPasses.h"
19#include "llvm/IR/LLVMContext.h"
20#include "llvm/IR/OptBisect.h"
21#include "llvm/IR/PassManager.h"
22#include "llvm/IR/PassTimingInfo.h"
23#include "llvm/InitializePasses.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/TimeProfiler.h"
26#include "llvm/Support/Timer.h"
27#include "llvm/Support/raw_ostream.h"
28using namespace llvm;
29
30#define DEBUG_TYPE "loop-pass-manager"
31
32namespace {
33
34/// PrintLoopPass - Print a Function corresponding to a Loop.
35///
36class PrintLoopPassWrapper : public LoopPass {
37  raw_ostream &OS;
38  std::string Banner;
39
40public:
41  static char ID;
42  PrintLoopPassWrapper() : LoopPass(ID), OS(dbgs()) {}
43  PrintLoopPassWrapper(raw_ostream &OS, const std::string &Banner)
44      : LoopPass(ID), OS(OS), Banner(Banner) {}
45
46  void getAnalysisUsage(AnalysisUsage &AU) const override {
47    AU.setPreservesAll();
48  }
49
50  bool runOnLoop(Loop *L, LPPassManager &) override {
51    auto BBI = llvm::find_if(L->blocks(), [](BasicBlock *BB) { return BB; });
52    if (BBI != L->blocks().end() &&
53        isFunctionInPrintList((*BBI)->getParent()->getName())) {
54      printLoop(*L, OS, Banner);
55    }
56    return false;
57  }
58
59  StringRef getPassName() const override { return "Print Loop IR"; }
60};
61
62char PrintLoopPassWrapper::ID = 0;
63}
64
65//===----------------------------------------------------------------------===//
66// LPPassManager
67//
68
69char LPPassManager::ID = 0;
70
71LPPassManager::LPPassManager()
72  : FunctionPass(ID), PMDataManager() {
73  LI = nullptr;
74  CurrentLoop = nullptr;
75}
76
77// Insert loop into loop nest (LoopInfo) and loop queue (LQ).
78void LPPassManager::addLoop(Loop &L) {
79  if (!L.getParentLoop()) {
80    // This is the top level loop.
81    LQ.push_front(&L);
82    return;
83  }
84
85  // Insert L into the loop queue after the parent loop.
86  for (auto I = LQ.begin(), E = LQ.end(); I != E; ++I) {
87    if (*I == L.getParentLoop()) {
88      // deque does not support insert after.
89      ++I;
90      LQ.insert(I, 1, &L);
91      return;
92    }
93  }
94}
95
96/// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
97/// all loop passes.
98void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From,
99                                                  BasicBlock *To, Loop *L) {
100  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
101    LoopPass *LP = getContainedPass(Index);
102    LP->cloneBasicBlockAnalysis(From, To, L);
103  }
104}
105
106/// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes.
107void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) {
108  if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
109    for (Instruction &I : *BB) {
110      deleteSimpleAnalysisValue(&I, L);
111    }
112  }
113  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
114    LoopPass *LP = getContainedPass(Index);
115    LP->deleteAnalysisValue(V, L);
116  }
117}
118
119/// Invoke deleteAnalysisLoop hook for all passes.
120void LPPassManager::deleteSimpleAnalysisLoop(Loop *L) {
121  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
122    LoopPass *LP = getContainedPass(Index);
123    LP->deleteAnalysisLoop(L);
124  }
125}
126
127
128// Recurse through all subloops and all loops  into LQ.
129static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
130  LQ.push_back(L);
131  for (Loop *I : reverse(*L))
132    addLoopIntoQueue(I, LQ);
133}
134
135/// Pass Manager itself does not invalidate any analysis info.
136void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
137  // LPPassManager needs LoopInfo. In the long term LoopInfo class will
138  // become part of LPPassManager.
139  Info.addRequired<LoopInfoWrapperPass>();
140  Info.addRequired<DominatorTreeWrapperPass>();
141  Info.setPreservesAll();
142}
143
144void LPPassManager::markLoopAsDeleted(Loop &L) {
145  assert((&L == CurrentLoop || CurrentLoop->contains(&L)) &&
146         "Must not delete loop outside the current loop tree!");
147  // If this loop appears elsewhere within the queue, we also need to remove it
148  // there. However, we have to be careful to not remove the back of the queue
149  // as that is assumed to match the current loop.
150  assert(LQ.back() == CurrentLoop && "Loop queue back isn't the current loop!");
151  LQ.erase(std::remove(LQ.begin(), LQ.end(), &L), LQ.end());
152
153  if (&L == CurrentLoop) {
154    CurrentLoopDeleted = true;
155    // Add this loop back onto the back of the queue to preserve our invariants.
156    LQ.push_back(&L);
157  }
158}
159
160/// run - Execute all of the passes scheduled for execution.  Keep track of
161/// whether any of the passes modifies the function, and if so, return true.
162bool LPPassManager::runOnFunction(Function &F) {
163  auto &LIWP = getAnalysis<LoopInfoWrapperPass>();
164  LI = &LIWP.getLoopInfo();
165  Module &M = *F.getParent();
166#if 0
167  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
168#endif
169  bool Changed = false;
170
171  // Collect inherited analysis from Module level pass manager.
172  populateInheritedAnalysis(TPM->activeStack);
173
174  // Populate the loop queue in reverse program order. There is no clear need to
175  // process sibling loops in either forward or reverse order. There may be some
176  // advantage in deleting uses in a later loop before optimizing the
177  // definitions in an earlier loop. If we find a clear reason to process in
178  // forward order, then a forward variant of LoopPassManager should be created.
179  //
180  // Note that LoopInfo::iterator visits loops in reverse program
181  // order. Here, reverse_iterator gives us a forward order, and the LoopQueue
182  // reverses the order a third time by popping from the back.
183  for (Loop *L : reverse(*LI))
184    addLoopIntoQueue(L, LQ);
185
186  if (LQ.empty()) // No loops, skip calling finalizers
187    return false;
188
189  // Initialization
190  for (Loop *L : LQ) {
191    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
192      LoopPass *P = getContainedPass(Index);
193      Changed |= P->doInitialization(L, *this);
194    }
195  }
196
197  // Walk Loops
198  unsigned InstrCount, FunctionSize = 0;
199  StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
200  bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
201  // Collect the initial size of the module and the function we're looking at.
202  if (EmitICRemark) {
203    InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
204    FunctionSize = F.getInstructionCount();
205  }
206  while (!LQ.empty()) {
207    CurrentLoopDeleted = false;
208    CurrentLoop = LQ.back();
209
210    // Run all passes on the current Loop.
211    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
212      LoopPass *P = getContainedPass(Index);
213
214      llvm::TimeTraceScope LoopPassScope("RunLoopPass", P->getPassName());
215
216      dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
217                   CurrentLoop->getHeader()->getName());
218      dumpRequiredSet(P);
219
220      initializeAnalysisImpl(P);
221
222      bool LocalChanged = false;
223      {
224        PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
225        TimeRegion PassTimer(getPassTimer(P));
226        LocalChanged = P->runOnLoop(CurrentLoop, *this);
227        Changed |= LocalChanged;
228        if (EmitICRemark) {
229          unsigned NewSize = F.getInstructionCount();
230          // Update the size of the function, emit a remark, and update the
231          // size of the module.
232          if (NewSize != FunctionSize) {
233            int64_t Delta = static_cast<int64_t>(NewSize) -
234                            static_cast<int64_t>(FunctionSize);
235            emitInstrCountChangedRemark(P, M, Delta, InstrCount,
236                                        FunctionToInstrCount, &F);
237            InstrCount = static_cast<int64_t>(InstrCount) + Delta;
238            FunctionSize = NewSize;
239          }
240        }
241      }
242
243      if (LocalChanged)
244        dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,
245                     CurrentLoopDeleted ? "<deleted loop>"
246                                        : CurrentLoop->getName());
247      dumpPreservedSet(P);
248
249      if (CurrentLoopDeleted) {
250        // Notify passes that the loop is being deleted.
251        deleteSimpleAnalysisLoop(CurrentLoop);
252      } else {
253        // Manually check that this loop is still healthy. This is done
254        // instead of relying on LoopInfo::verifyLoop since LoopInfo
255        // is a function pass and it's really expensive to verify every
256        // loop in the function every time. That level of checking can be
257        // enabled with the -verify-loop-info option.
258        {
259          TimeRegion PassTimer(getPassTimer(&LIWP));
260          CurrentLoop->verifyLoop();
261        }
262        // Here we apply same reasoning as in the above case. Only difference
263        // is that LPPassManager might run passes which do not require LCSSA
264        // form (LoopPassPrinter for example). We should skip verification for
265        // such passes.
266        // FIXME: Loop-sink currently break LCSSA. Fix it and reenable the
267        // verification!
268#if 0
269        if (mustPreserveAnalysisID(LCSSAVerificationPass::ID))
270          assert(CurrentLoop->isRecursivelyLCSSAForm(*DT, *LI));
271#endif
272
273        // Then call the regular verifyAnalysis functions.
274        verifyPreservedAnalysis(P);
275
276        F.getContext().yield();
277      }
278
279      removeNotPreservedAnalysis(P);
280      recordAvailableAnalysis(P);
281      removeDeadPasses(P,
282                       CurrentLoopDeleted ? "<deleted>"
283                                          : CurrentLoop->getHeader()->getName(),
284                       ON_LOOP_MSG);
285
286      if (CurrentLoopDeleted)
287        // Do not run other passes on this loop.
288        break;
289    }
290
291    // If the loop was deleted, release all the loop passes. This frees up
292    // some memory, and avoids trouble with the pass manager trying to call
293    // verifyAnalysis on them.
294    if (CurrentLoopDeleted) {
295      for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
296        Pass *P = getContainedPass(Index);
297        freePass(P, "<deleted>", ON_LOOP_MSG);
298      }
299    }
300
301    // Pop the loop from queue after running all passes.
302    LQ.pop_back();
303  }
304
305  // Finalization
306  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
307    LoopPass *P = getContainedPass(Index);
308    Changed |= P->doFinalization();
309  }
310
311  return Changed;
312}
313
314/// Print passes managed by this manager
315void LPPassManager::dumpPassStructure(unsigned Offset) {
316  errs().indent(Offset*2) << "Loop Pass Manager\n";
317  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
318    Pass *P = getContainedPass(Index);
319    P->dumpPassStructure(Offset + 1);
320    dumpLastUses(P, Offset+1);
321  }
322}
323
324
325//===----------------------------------------------------------------------===//
326// LoopPass
327
328Pass *LoopPass::createPrinterPass(raw_ostream &O,
329                                  const std::string &Banner) const {
330  return new PrintLoopPassWrapper(O, Banner);
331}
332
333// Check if this pass is suitable for the current LPPassManager, if
334// available. This pass P is not suitable for a LPPassManager if P
335// is not preserving higher level analysis info used by other
336// LPPassManager passes. In such case, pop LPPassManager from the
337// stack. This will force assignPassManager() to create new
338// LPPassManger as expected.
339void LoopPass::preparePassManager(PMStack &PMS) {
340
341  // Find LPPassManager
342  while (!PMS.empty() &&
343         PMS.top()->getPassManagerType() > PMT_LoopPassManager)
344    PMS.pop();
345
346  // If this pass is destroying high level information that is used
347  // by other passes that are managed by LPM then do not insert
348  // this pass in current LPM. Use new LPPassManager.
349  if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&
350      !PMS.top()->preserveHigherLevelAnalysis(this))
351    PMS.pop();
352}
353
354/// Assign pass manager to manage this pass.
355void LoopPass::assignPassManager(PMStack &PMS,
356                                 PassManagerType PreferredType) {
357  // Find LPPassManager
358  while (!PMS.empty() &&
359         PMS.top()->getPassManagerType() > PMT_LoopPassManager)
360    PMS.pop();
361
362  LPPassManager *LPPM;
363  if (PMS.top()->getPassManagerType() == PMT_LoopPassManager)
364    LPPM = (LPPassManager*)PMS.top();
365  else {
366    // Create new Loop Pass Manager if it does not exist.
367    assert (!PMS.empty() && "Unable to create Loop Pass Manager");
368    PMDataManager *PMD = PMS.top();
369
370    // [1] Create new Loop Pass Manager
371    LPPM = new LPPassManager();
372    LPPM->populateInheritedAnalysis(PMS);
373
374    // [2] Set up new manager's top level manager
375    PMTopLevelManager *TPM = PMD->getTopLevelManager();
376    TPM->addIndirectPassManager(LPPM);
377
378    // [3] Assign manager to manage this new manager. This may create
379    // and push new managers into PMS
380    Pass *P = LPPM->getAsPass();
381    TPM->schedulePass(P);
382
383    // [4] Push new manager into PMS
384    PMS.push(LPPM);
385  }
386
387  LPPM->add(this);
388}
389
390static std::string getDescription(const Loop &L) {
391  return "loop";
392}
393
394bool LoopPass::skipLoop(const Loop *L) const {
395  const Function *F = L->getHeader()->getParent();
396  if (!F)
397    return false;
398  // Check the opt bisect limit.
399  OptPassGate &Gate = F->getContext().getOptPassGate();
400  if (Gate.isEnabled() && !Gate.shouldRunPass(this, getDescription(*L)))
401    return true;
402  // Check for the OptimizeNone attribute.
403  if (F->hasOptNone()) {
404    // FIXME: Report this to dbgs() only once per function.
405    LLVM_DEBUG(dbgs() << "Skipping pass '" << getPassName() << "' in function "
406                      << F->getName() << "\n");
407    // FIXME: Delete loop from pass manager's queue?
408    return true;
409  }
410  return false;
411}
412
413LCSSAVerificationPass::LCSSAVerificationPass() : FunctionPass(ID) {
414  initializeLCSSAVerificationPassPass(*PassRegistry::getPassRegistry());
415}
416
417char LCSSAVerificationPass::ID = 0;
418INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier",
419                false, false)
420