summaryrefslogtreecommitdiff
path: root/include/llvm/PassManagers.h
blob: 385d6e1b55a1632ea9d7b545d105068c4232cead (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
//===- llvm/PassManagers.h - Pass Infrastructure classes  -------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file declares the LLVM Pass Manager infrastructure.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_PASSMANAGERS_H
#define LLVM_PASSMANAGERS_H

#include "llvm/Pass.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/DenseMap.h"
#include <vector>
#include <map>

//===----------------------------------------------------------------------===//
// Overview:
// The Pass Manager Infrastructure manages passes. It's responsibilities are:
//
//   o Manage optimization pass execution order
//   o Make required Analysis information available before pass P is run
//   o Release memory occupied by dead passes
//   o If Analysis information is dirtied by a pass then regenerate Analysis
//     information before it is consumed by another pass.
//
// Pass Manager Infrastructure uses multiple pass managers.  They are
// PassManager, FunctionPassManager, MPPassManager, FPPassManager, BBPassManager.
// This class hierarchy uses multiple inheritance but pass managers do not
// derive from another pass manager.
//
// PassManager and FunctionPassManager are two top-level pass manager that
// represents the external interface of this entire pass manager infrastucture.
//
// Important classes :
//
// [o] class PMTopLevelManager;
//
// Two top level managers, PassManager and FunctionPassManager, derive from
// PMTopLevelManager. PMTopLevelManager manages information used by top level
// managers such as last user info.
//
// [o] class PMDataManager;
//
// PMDataManager manages information, e.g. list of available analysis info,
// used by a pass manager to manage execution order of passes. It also provides
// a place to implement common pass manager APIs. All pass managers derive from
// PMDataManager.
//
// [o] class BBPassManager : public FunctionPass, public PMDataManager;
//
// BBPassManager manages BasicBlockPasses.
//
// [o] class FunctionPassManager;
//
// This is a external interface used by JIT to manage FunctionPasses. This
// interface relies on FunctionPassManagerImpl to do all the tasks.
//
// [o] class FunctionPassManagerImpl : public ModulePass, PMDataManager,
//                                     public PMTopLevelManager;
//
// FunctionPassManagerImpl is a top level manager. It manages FPPassManagers
//
// [o] class FPPassManager : public ModulePass, public PMDataManager;
//
// FPPassManager manages FunctionPasses and BBPassManagers
//
// [o] class MPPassManager : public Pass, public PMDataManager;
//
// MPPassManager manages ModulePasses and FPPassManagers
//
// [o] class PassManager;
//
// This is a external interface used by various tools to manages passes. It
// relies on PassManagerImpl to do all the tasks.
//
// [o] class PassManagerImpl : public Pass, public PMDataManager,
//                             public PMTopLevelManager
//
// PassManagerImpl is a top level pass manager responsible for managing
// MPPassManagers.
//===----------------------------------------------------------------------===//

#include "llvm/Support/PrettyStackTrace.h"

namespace llvm {
  class Module;
  class Pass;
  class StringRef;
  class Value;
  class Timer;
  class PMDataManager;

// enums for debugging strings
enum PassDebuggingString {
  EXECUTION_MSG, // "Executing Pass '"
  MODIFICATION_MSG, // "' Made Modification '"
  FREEING_MSG, // " Freeing Pass '"
  ON_BASICBLOCK_MSG, // "'  on BasicBlock '" + PassName + "'...\n"
  ON_FUNCTION_MSG, // "' on Function '" + FunctionName + "'...\n"
  ON_MODULE_MSG, // "' on Module '" + ModuleName + "'...\n"
  ON_REGION_MSG, // " 'on Region ...\n'"
  ON_LOOP_MSG, // " 'on Loop ...\n'"
  ON_CG_MSG // "' on Call Graph ...\n'"
};

/// PassManagerPrettyStackEntry - This is used to print informative information
/// about what pass is running when/if a stack trace is generated.
class PassManagerPrettyStackEntry : public PrettyStackTraceEntry {
  Pass *P;
  Value *V;
  Module *M;
public:
  explicit PassManagerPrettyStackEntry(Pass *p)
    : P(p), V(0), M(0) {}  // When P is releaseMemory'd.
  PassManagerPrettyStackEntry(Pass *p, Value &v)
    : P(p), V(&v), M(0) {} // When P is run on V
  PassManagerPrettyStackEntry(Pass *p, Module &m)
    : P(p), V(0), M(&m) {} // When P is run on M

  /// print - Emit information about this stack frame to OS.
  virtual void print(raw_ostream &OS) const;
};


//===----------------------------------------------------------------------===//
// PMStack
//
/// PMStack - This class implements a stack data structure of PMDataManager
/// pointers.
///
/// Top level pass managers (see PassManager.cpp) maintain active Pass Managers
/// using PMStack. Each Pass implements assignPassManager() to connect itself
/// with appropriate manager. assignPassManager() walks PMStack to find
/// suitable manager.
class PMStack {
public:
  typedef std::vector<PMDataManager *>::const_reverse_iterator iterator;
  iterator begin() const { return S.rbegin(); }
  iterator end() const { return S.rend(); }

  void pop();
  PMDataManager *top() const { return S.back(); }
  void push(PMDataManager *PM);
  bool empty() const { return S.empty(); }

  void dump() const;

private:
  std::vector<PMDataManager *> S;
};


//===----------------------------------------------------------------------===//
// PMTopLevelManager
//
/// PMTopLevelManager manages LastUser info and collects common APIs used by
/// top level pass managers.
class PMTopLevelManager {
protected:
  explicit PMTopLevelManager(PMDataManager *PMDM);

  unsigned getNumContainedManagers() const {
    return (unsigned)PassManagers.size();
  }

  void initializeAllAnalysisInfo();

private:
  virtual PMDataManager *getAsPMDataManager() = 0;
  virtual PassManagerType getTopLevelPassManagerType() = 0;

public:
  /// Schedule pass P for execution. Make sure that passes required by
  /// P are run before P is run. Update analysis info maintained by
  /// the manager. Remove dead passes. This is a recursive function.
  void schedulePass(Pass *P);

  /// Set pass P as the last user of the given analysis passes.
  void setLastUser(ArrayRef<Pass*> AnalysisPasses, Pass *P);

  /// Collect passes whose last user is P
  void collectLastUses(SmallVectorImpl<Pass *> &LastUses, Pass *P);

  /// Find the pass that implements Analysis AID. Search immutable
  /// passes and all pass managers. If desired pass is not found
  /// then return NULL.
  Pass *findAnalysisPass(AnalysisID AID);

  /// Find analysis usage information for the pass P.
  AnalysisUsage *findAnalysisUsage(Pass *P);

  virtual ~PMTopLevelManager();

  /// Add immutable pass and initialize it.
  inline void addImmutablePass(ImmutablePass *P) {
    P->initializePass();
    ImmutablePasses.push_back(P);
  }

  inline SmallVectorImpl<ImmutablePass *>& getImmutablePasses() {
    return ImmutablePasses;
  }

  void addPassManager(PMDataManager *Manager) {
    PassManagers.push_back(Manager);
  }

  // Add Manager into the list of managers that are not directly
  // maintained by this top level pass manager
  inline void addIndirectPassManager(PMDataManager *Manager) {
    IndirectPassManagers.push_back(Manager);
  }

  // Print passes managed by this top level manager.
  void dumpPasses() const;
  void dumpArguments() const;

  // Active Pass Managers
  PMStack activeStack;

protected:

  /// Collection of pass managers
  SmallVector<PMDataManager *, 8> PassManagers;

private:

  /// Collection of pass managers that are not directly maintained
  /// by this pass manager
  SmallVector<PMDataManager *, 8> IndirectPassManagers;

  // Map to keep track of last user of the analysis pass.
  // LastUser->second is the last user of Lastuser->first.
  DenseMap<Pass *, Pass *> LastUser;

  // Map to keep track of passes that are last used by a pass.
  // This inverse map is initialized at PM->run() based on
  // LastUser map.
  DenseMap<Pass *, SmallPtrSet<Pass *, 8> > InversedLastUser;

  /// Immutable passes are managed by top level manager.
  SmallVector<ImmutablePass *, 8> ImmutablePasses;

  DenseMap<Pass *, AnalysisUsage *> AnUsageMap;
};



//===----------------------------------------------------------------------===//
// PMDataManager

/// PMDataManager provides the common place to manage the analysis data
/// used by pass managers.
class PMDataManager {
public:

  explicit PMDataManager() : TPM(NULL), Depth(0) {
    initializeAnalysisInfo();
  }

  virtual ~PMDataManager();

  virtual Pass *getAsPass() = 0;

  /// Augment AvailableAnalysis by adding analysis made available by pass P.
  void recordAvailableAnalysis(Pass *P);

  /// verifyPreservedAnalysis -- Verify analysis presreved by pass P.
  void verifyPreservedAnalysis(Pass *P);

  /// Remove Analysis that is not preserved by the pass
  void removeNotPreservedAnalysis(Pass *P);

  /// Remove dead passes used by P.
  void removeDeadPasses(Pass *P, StringRef Msg,
                        enum PassDebuggingString);

  /// Remove P.
  void freePass(Pass *P, StringRef Msg,
                enum PassDebuggingString);

  /// Add pass P into the PassVector. Update
  /// AvailableAnalysis appropriately if ProcessAnalysis is true.
  void add(Pass *P, bool ProcessAnalysis = true);

  /// Add RequiredPass into list of lower level passes required by pass P.
  /// RequiredPass is run on the fly by Pass Manager when P requests it
  /// through getAnalysis interface.
  virtual void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass);

  virtual Pass *getOnTheFlyPass(Pass *P, AnalysisID PI, Function &F);

  /// Initialize available analysis information.
  void initializeAnalysisInfo() {
    AvailableAnalysis.clear();
    for (unsigned i = 0; i < PMT_Last; ++i)
      InheritedAnalysis[i] = NULL;
  }

  // Return true if P preserves high level analysis used by other
  // passes that are managed by this manager.
  bool preserveHigherLevelAnalysis(Pass *P);


  /// Populate RequiredPasses with analysis pass that are required by
  /// pass P and are available. Populate ReqPassNotAvailable with analysis
  /// pass that are required by pass P but are not available.
  void collectRequiredAnalysis(SmallVectorImpl<Pass *> &RequiredPasses,
                               SmallVectorImpl<AnalysisID> &ReqPassNotAvailable,
                               Pass *P);

  /// All Required analyses should be available to the pass as it runs!  Here
  /// we fill in the AnalysisImpls member of the pass so that it can
  /// successfully use the getAnalysis() method to retrieve the
  /// implementations it needs.
  void initializeAnalysisImpl(Pass *P);

  /// Find the pass that implements Analysis AID. If desired pass is not found
  /// then return NULL.
  Pass *findAnalysisPass(AnalysisID AID, bool Direction);

  // Access toplevel manager
  PMTopLevelManager *getTopLevelManager() { return TPM; }
  void setTopLevelManager(PMTopLevelManager *T) { TPM = T; }

  unsigned getDepth() const { return Depth; }
  void setDepth(unsigned newDepth) { Depth = newDepth; }

  // Print routines used by debug-pass
  void dumpLastUses(Pass *P, unsigned Offset) const;
  void dumpPassArguments() const;
  void dumpPassInfo(Pass *P, enum PassDebuggingString S1,
                    enum PassDebuggingString S2, StringRef Msg);
  void dumpRequiredSet(const Pass *P) const;
  void dumpPreservedSet(const Pass *P) const;

  unsigned getNumContainedPasses() const {
    return (unsigned)PassVector.size();
  }

  virtual PassManagerType getPassManagerType() const {
    assert ( 0 && "Invalid use of getPassManagerType");
    return PMT_Unknown;
  }

  std::map<AnalysisID, Pass*> *getAvailableAnalysis() {
    return &AvailableAnalysis;
  }

  // Collect AvailableAnalysis from all the active Pass Managers.
  void populateInheritedAnalysis(PMStack &PMS) {
    unsigned Index = 0;
    for (PMStack::iterator I = PMS.begin(), E = PMS.end();
         I != E; ++I)
      InheritedAnalysis[Index++] = (*I)->getAvailableAnalysis();
  }

protected:

  // Top level manager.
  PMTopLevelManager *TPM;

  // Collection of pass that are managed by this manager
  SmallVector<Pass *, 16> PassVector;

  // Collection of Analysis provided by Parent pass manager and
  // used by current pass manager. At at time there can not be more
  // then PMT_Last active pass mangers.
  std::map<AnalysisID, Pass *> *InheritedAnalysis[PMT_Last];


  /// isPassDebuggingExecutionsOrMore - Return true if -debug-pass=Executions
  /// or higher is specified.
  bool isPassDebuggingExecutionsOrMore() const;

private:
  void dumpAnalysisUsage(StringRef Msg, const Pass *P,
                         const AnalysisUsage::VectorType &Set) const;

  // Set of available Analysis. This information is used while scheduling
  // pass. If a pass requires an analysis which is not available then
  // the required analysis pass is scheduled to run before the pass itself is
  // scheduled to run.
  std::map<AnalysisID, Pass*> AvailableAnalysis;

  // Collection of higher level analysis used by the pass managed by
  // this manager.
  SmallVector<Pass *, 8> HigherLevelAnalysis;

  unsigned Depth;
};

//===----------------------------------------------------------------------===//
// FPPassManager
//
/// FPPassManager manages BBPassManagers and FunctionPasses.
/// It batches all function passes and basic block pass managers together and
/// sequence them to process one function at a time before processing next
/// function.
class FPPassManager : public ModulePass, public PMDataManager {
public:
  static char ID;
  explicit FPPassManager()
  : ModulePass(ID), PMDataManager() { }

  /// run - Execute all of the passes scheduled for execution.  Keep track of
  /// whether any of the passes modifies the module, and if so, return true.
  bool runOnFunction(Function &F);
  bool runOnModule(Module &M);

  /// cleanup - After running all passes, clean up pass manager cache.
  void cleanup();

  /// doInitialization - Overrides ModulePass doInitialization for global
  /// initialization tasks
  ///
  using ModulePass::doInitialization;

  /// doInitialization - Run all of the initializers for the function passes.
  ///
  bool doInitialization(Module &M);

  /// doFinalization - Overrides ModulePass doFinalization for global
  /// finalization tasks
  /// 
  using ModulePass::doFinalization;
  
  /// doFinalization - Run all of the finalizers for the function passes.
  ///
  bool doFinalization(Module &M);

  virtual PMDataManager *getAsPMDataManager() { return this; }
  virtual Pass *getAsPass() { return this; }

  /// Pass Manager itself does not invalidate any analysis info.
  void getAnalysisUsage(AnalysisUsage &Info) const {
    Info.setPreservesAll();
  }

  // Print passes managed by this manager
  void dumpPassStructure(unsigned Offset);

  virtual const char *getPassName() const {
    return "Function Pass Manager";
  }

  FunctionPass *getContainedPass(unsigned N) {
    assert ( N < PassVector.size() && "Pass number out of range!");
    FunctionPass *FP = static_cast<FunctionPass *>(PassVector[N]);
    return FP;
  }

  virtual PassManagerType getPassManagerType() const {
    return PMT_FunctionPassManager;
  }

protected:
  // FIXME: due to limitation in AddressSanitizer
  bool RunFinalization;
};

Timer *getPassTimer(Pass *);

}

#endif