Coverage Report

Created: 2019-07-24 05:18

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