contrib/llvm/include/llvm/Analysis/ProfileInfo.h

   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
  32 namespace 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