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