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