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. getFunction(Edge e)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. getEdge(const BType * Src,const BType * Dest)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 getEdgeWeight(Edge e)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 setEdgeWeight(Edge e,double w)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 getEdgeWeights(const FType * F)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 MI()227 ProfileInfoT<MachineFunction, MachineBasicBlock> *MI() { 228 if (MachineProfile == 0) 229 MachineProfile = new ProfileInfoT<MachineFunction, MachineBasicBlock>(); 230 return MachineProfile; 231 } 232 hasMI()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