1//===- llvm/Analysis/ProfileInfo.h - Profile Info Interface -----*- C++ -*-===//
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 defines the generic ProfileInfo interface, which is used as the
11// common interface used by all clients of profiling information, and
12// implemented either by making static guestimations, or by actually reading in
13// profiling information gathered by running the program.
14//
15// Note that to be useful, all profile-based optimizations should preserve
16// ProfileInfo, which requires that they notify it when changes to the CFG are
17// made. (This is not implemented yet.)
18//
19//===----------------------------------------------------------------------===//
20
21#ifndef LLVM_ANALYSIS_PROFILEINFO_H
22#define LLVM_ANALYSIS_PROFILEINFO_H
23
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/Format.h"
26#include "llvm/Support/raw_ostream.h"
27#include <cassert>
28#include <string>
29#include <map>
30#include <set>
31
32namespace llvm {
33  class Pass;
34  class raw_ostream;
35
36  class BasicBlock;
37  class Function;
38  class MachineBasicBlock;
39  class MachineFunction;
40
41  // Helper for dumping edges to dbgs().
42  raw_ostream& operator<<(raw_ostream &O, std::pair<const BasicBlock *, const BasicBlock *> E);
43  raw_ostream& operator<<(raw_ostream &O, std::pair<const MachineBasicBlock *, const MachineBasicBlock *> E);
44
45  raw_ostream& operator<<(raw_ostream &O, const BasicBlock *BB);
46  raw_ostream& operator<<(raw_ostream &O, const MachineBasicBlock *MBB);
47
48  raw_ostream& operator<<(raw_ostream &O, const Function *F);
49  raw_ostream& operator<<(raw_ostream &O, const MachineFunction *MF);
50
51  /// ProfileInfo Class - This class holds and maintains profiling
52  /// information for some unit of code.
53  template<class FType, class BType>
54  class ProfileInfoT {
55  public:
56    // Types for handling profiling information.
57    typedef std::pair<const BType*, const BType*> Edge;
58    typedef std::pair<Edge, double> EdgeWeight;
59    typedef std::map<Edge, double> EdgeWeights;
60    typedef std::map<const BType*, double> BlockCounts;
61    typedef std::map<const BType*, const BType*> Path;
62
63  protected:
64    // EdgeInformation - Count the number of times a transition between two
65    // blocks is executed. As a special case, we also hold an edge from the
66    // null BasicBlock to the entry block to indicate how many times the
67    // function was entered.
68    std::map<const FType*, EdgeWeights> EdgeInformation;
69
70    // BlockInformation - Count the number of times a block is executed.
71    std::map<const FType*, BlockCounts> BlockInformation;
72
73    // FunctionInformation - Count the number of times a function is executed.
74    std::map<const FType*, double> FunctionInformation;
75
76    ProfileInfoT<MachineFunction, MachineBasicBlock> *MachineProfile;
77  public:
78    static char ID; // Class identification, replacement for typeinfo
79    ProfileInfoT();
80    ~ProfileInfoT();  // We want to be subclassed
81
82    // MissingValue - The value that is returned for execution counts in case
83    // no value is available.
84    static const double MissingValue;
85
86    // getFunction() - Returns the Function for an Edge, checking for validity.
87    static const FType* getFunction(Edge e) {
88      if (e.first) {
89        return e.first->getParent();
90      } else if (e.second) {
91        return e.second->getParent();
92      }
93      assert(0 && "Invalid ProfileInfo::Edge");
94      return (const FType*)0;
95    }
96
97    // getEdge() - Creates an Edge from two BasicBlocks.
98    static Edge getEdge(const BType *Src, const BType *Dest) {
99      return std::make_pair(Src, Dest);
100    }
101
102    //===------------------------------------------------------------------===//
103    /// Profile Information Queries
104    ///
105    double getExecutionCount(const FType *F);
106
107    double getExecutionCount(const BType *BB);
108
109    void setExecutionCount(const BType *BB, double w);
110
111    void addExecutionCount(const BType *BB, double w);
112
113    double getEdgeWeight(Edge e) const {
114      typename std::map<const FType*, EdgeWeights>::const_iterator J =
115        EdgeInformation.find(getFunction(e));
116      if (J == EdgeInformation.end()) return MissingValue;
117
118      typename EdgeWeights::const_iterator I = J->second.find(e);
119      if (I == J->second.end()) return MissingValue;
120
121      return I->second;
122    }
123
124    void setEdgeWeight(Edge e, double w) {
125      DEBUG_WITH_TYPE("profile-info",
126            dbgs() << "Creating Edge " << e
127                   << " (weight: " << format("%.20g",w) << ")\n");
128      EdgeInformation[getFunction(e)][e] = w;
129    }
130
131    void addEdgeWeight(Edge e, double w);
132
133    EdgeWeights &getEdgeWeights (const FType *F) {
134      return EdgeInformation[F];
135    }
136
137    //===------------------------------------------------------------------===//
138    /// Analysis Update Methods
139    ///
140    void removeBlock(const BType *BB);
141
142    void removeEdge(Edge e);
143
144    void replaceEdge(const Edge &, const Edge &);
145
146    enum GetPathMode {
147      GetPathToExit = 1,
148      GetPathToValue = 2,
149      GetPathToDest = 4,
150      GetPathWithNewEdges = 8
151    };
152
153    const BType *GetPath(const BType *Src, const BType *Dest,
154                              Path &P, unsigned Mode);
155
156    void divertFlow(const Edge &, const Edge &);
157
158    void splitEdge(const BType *FirstBB, const BType *SecondBB,
159                   const BType *NewBB, bool MergeIdenticalEdges = false);
160
161    void splitBlock(const BType *Old, const BType* New);
162
163    void splitBlock(const BType *BB, const BType* NewBB,
164                    BType *const *Preds, unsigned NumPreds);
165
166    void replaceAllUses(const BType *RmBB, const BType *DestBB);
167
168    void transfer(const FType *Old, const FType *New);
169
170    void repair(const FType *F);
171
172    void dump(FType *F = 0, bool real = true) {
173      dbgs() << "**** This is ProfileInfo " << this << " speaking:\n";
174      if (!real) {
175        typename std::set<const FType*> Functions;
176
177        dbgs() << "Functions: \n";
178        if (F) {
179          dbgs() << F << "@" << format("%p", F) << ": " << format("%.20g",getExecutionCount(F)) << "\n";
180          Functions.insert(F);
181        } else {
182          for (typename std::map<const FType*, double>::iterator fi = FunctionInformation.begin(),
183               fe = FunctionInformation.end(); fi != fe; ++fi) {
184            dbgs() << fi->first << "@" << format("%p",fi->first) << ": " << format("%.20g",fi->second) << "\n";
185            Functions.insert(fi->first);
186          }
187        }
188
189        for (typename std::set<const FType*>::iterator FI = Functions.begin(), FE = Functions.end();
190             FI != FE; ++FI) {
191          const FType *F = *FI;
192          typename std::map<const FType*, BlockCounts>::iterator bwi = BlockInformation.find(F);
193          dbgs() << "BasicBlocks for Function " << F << ":\n";
194          for (typename BlockCounts::const_iterator bi = bwi->second.begin(), be = bwi->second.end(); bi != be; ++bi) {
195            dbgs() << bi->first << "@" << format("%p", bi->first) << ": " << format("%.20g",bi->second) << "\n";
196          }
197        }
198
199        for (typename std::set<const FType*>::iterator FI = Functions.begin(), FE = Functions.end();
200             FI != FE; ++FI) {
201          typename std::map<const FType*, EdgeWeights>::iterator ei = EdgeInformation.find(*FI);
202          dbgs() << "Edges for Function " << ei->first << ":\n";
203          for (typename EdgeWeights::iterator ewi = ei->second.begin(), ewe = ei->second.end();
204               ewi != ewe; ++ewi) {
205            dbgs() << ewi->first << ": " << format("%.20g",ewi->second) << "\n";
206          }
207        }
208      } else {
209        assert(F && "No function given, this is not supported!");
210        dbgs() << "Functions: \n";
211        dbgs() << F << "@" << format("%p", F) << ": " << format("%.20g",getExecutionCount(F)) << "\n";
212
213        dbgs() << "BasicBlocks for Function " << F << ":\n";
214        for (typename FType::const_iterator BI = F->begin(), BE = F->end();
215             BI != BE; ++BI) {
216          const BType *BB = &(*BI);
217          dbgs() << BB << "@" << format("%p", BB) << ": " << format("%.20g",getExecutionCount(BB)) << "\n";
218        }
219      }
220      dbgs() << "**** ProfileInfo " << this << ", over and out.\n";
221    }
222
223    bool CalculateMissingEdge(const BType *BB, Edge &removed, bool assumeEmptyExit = false);
224
225    bool EstimateMissingEdges(const BType *BB);
226
227    ProfileInfoT<MachineFunction, MachineBasicBlock> *MI() {
228      if (MachineProfile == 0)
229        MachineProfile = new ProfileInfoT<MachineFunction, MachineBasicBlock>();
230      return MachineProfile;
231    }
232
233    bool hasMI() const {
234      return (MachineProfile != 0);
235    }
236  };
237
238  typedef ProfileInfoT<Function, BasicBlock> ProfileInfo;
239  typedef ProfileInfoT<MachineFunction, MachineBasicBlock> MachineProfileInfo;
240
241  /// createProfileLoaderPass - This function returns a Pass that loads the
242  /// profiling information for the module from the specified filename, making
243  /// it available to the optimizers.
244  Pass *createProfileLoaderPass(const std::string &Filename);
245
246} // End llvm namespace
247
248#endif
249