104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick//===- PathProfileVerifier.cpp --------------------------------*- C++ -*---===// 204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// 304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// The LLVM Compiler Infrastructure 404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// 504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// This file is distributed under the University of Illinois Open Source 604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// License. See LICENSE.TXT for details. 704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// 804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick//===----------------------------------------------------------------------===// 904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// 1004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// This verifier derives an edge profile file from current path profile 1104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// information 1204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// 1304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick//===----------------------------------------------------------------------===// 1404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#define DEBUG_TYPE "path-profile-verifier" 1504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 1604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Analysis/Passes.h" 1704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Analysis/PathProfileInfo.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/ProfileInfoTypes.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Pass.h" 2104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Support/CommandLine.h" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/Debug.h" 2304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Support/raw_ostream.h" 2404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include <stdio.h> 2504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 2604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickusing namespace llvm; 2704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 2804317cc618aeae28910916469e074d8ce0fcaa03Andrew Tricknamespace { 2904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick class PathProfileVerifier : public ModulePass { 3004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick private: 3104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick bool runOnModule(Module &M); 3204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 3304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick public: 3404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick static char ID; // Pass identification, replacement for typeid 3504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick PathProfileVerifier() : ModulePass(ID) { 3604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick initializePathProfileVerifierPass(*PassRegistry::getPassRegistry()); 3704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 3804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 3904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 4004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick virtual const char *getPassName() const { 4104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return "Path Profiler Verifier"; 4204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 4304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 4404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // The verifier requires the path profile and edge profile. 4504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick virtual void getAnalysisUsage(AnalysisUsage& AU) const; 4604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick }; 4704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 4804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 4904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickstatic cl::opt<std::string> 5004317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickEdgeProfileFilename("path-profile-verifier-file", 5104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick cl::init("edgefrompath.llvmprof.out"), 5204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick cl::value_desc("filename"), 5304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick cl::desc("Edge profile file generated by -path-profile-verifier"), 5404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick cl::Hidden); 5504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 5604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickchar PathProfileVerifier::ID = 0; 5704317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickINITIALIZE_PASS(PathProfileVerifier, "path-profile-verifier", 5804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick "Compare the path profile derived edge profile against the " 5904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick "edge profile.", true, true) 6004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 6104317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickModulePass *llvm::createPathProfileVerifierPass() { 6204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return new PathProfileVerifier(); 6304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 6404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 6504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// The verifier requires the path profile and edge profile. 6604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid PathProfileVerifier::getAnalysisUsage(AnalysisUsage& AU) const { 6704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick AU.addRequired<PathProfileInfo>(); 6804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick AU.addPreserved<PathProfileInfo>(); 6904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 7004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 7104317cc618aeae28910916469e074d8ce0fcaa03Andrew Tricktypedef std::map<unsigned, unsigned> DuplicateToIndexMap; 7204317cc618aeae28910916469e074d8ce0fcaa03Andrew Tricktypedef std::map<BasicBlock*,DuplicateToIndexMap> BlockToDuplicateMap; 7304317cc618aeae28910916469e074d8ce0fcaa03Andrew Tricktypedef std::map<BasicBlock*,BlockToDuplicateMap> NestedBlockToIndexMap; 7404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 7504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// the verifier iterates through each path to gather the total 7604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// number of edge frequencies 7704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickbool PathProfileVerifier::runOnModule (Module &M) { 7804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick PathProfileInfo& pathProfileInfo = getAnalysis<PathProfileInfo>(); 7904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 8004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // setup a data structure to map path edges which index an 8104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // array of edge counters 8204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick NestedBlockToIndexMap arrayMap; 8304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned i = 0; 8404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 8504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if (F->isDeclaration()) continue; 8604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 8771246fb830eb15cbf6f976de33f623b6bcb27b4bMatt Arsenault arrayMap[(BasicBlock*)0][F->begin()][0] = i++; 8804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 8904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 9004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick TerminatorInst *TI = BB->getTerminator(); 9104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 9204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned duplicate = 0; 9304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BasicBlock* prev = 0; 9404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; 9504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick prev = TI->getSuccessor(s), ++s) { 9604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if (prev == TI->getSuccessor(s)) 9704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick duplicate++; 9804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick else duplicate = 0; 9904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 10004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick arrayMap[BB][TI->getSuccessor(s)][duplicate] = i++; 10104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 10204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 10304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 10404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 10504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick std::vector<unsigned> edgeArray(i); 10604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 10704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // iterate through each path and increment the edge counters as needed 10804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 10904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if (F->isDeclaration()) continue; 11004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 11104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick pathProfileInfo.setCurrentFunction(F); 11204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 11304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick DEBUG(dbgs() << "function '" << F->getName() << "' ran " 11404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick << pathProfileInfo.pathsRun() 11504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick << "/" << pathProfileInfo.getPotentialPathCount() 11604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick << " potential paths\n"); 11704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 11804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick for( ProfilePathIterator nextPath = pathProfileInfo.pathBegin(), 11904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick endPath = pathProfileInfo.pathEnd(); 12004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick nextPath != endPath; nextPath++ ) { 12104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick ProfilePath* currentPath = nextPath->second; 12204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 12304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick ProfilePathEdgeVector* pev = currentPath->getPathEdges(); 12404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick DEBUG(dbgs () << "path #" << currentPath->getNumber() << ": " 12504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick << currentPath->getCount() << "\n"); 1267a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // setup the entry edge (normally path profiling doesn't care about this) 12704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if (currentPath->getFirstBlockInPath() == &F->getEntryBlock()) 12871246fb830eb15cbf6f976de33f623b6bcb27b4bMatt Arsenault edgeArray[arrayMap[(BasicBlock*)0][currentPath->getFirstBlockInPath()][0]] 12904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick += currentPath->getCount(); 13004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 13104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick for( ProfilePathEdgeIterator nextEdge = pev->begin(), 13204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick endEdge = pev->end(); nextEdge != endEdge; nextEdge++ ) { 13304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if (nextEdge != pev->begin()) 13404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick DEBUG(dbgs() << " :: "); 13504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 13604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BasicBlock* source = nextEdge->getSource(); 13704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BasicBlock* target = nextEdge->getTarget(); 13804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned duplicateNumber = nextEdge->getDuplicateNumber(); 139a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer DEBUG(dbgs() << source->getName() << " --{" << duplicateNumber 140a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer << "}--> " << target->getName()); 14104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 14204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Ensure all the referenced edges exist 14304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // TODO: make this a separate function 14404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if( !arrayMap.count(source) ) { 145a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer errs() << " error [" << F->getName() << "()]: source '" 146a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer << source->getName() 14704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick << "' does not exist in the array map.\n"; 14804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } else if( !arrayMap[source].count(target) ) { 149a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer errs() << " error [" << F->getName() << "()]: target '" 150a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer << target->getName() 15104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick << "' does not exist in the array map.\n"; 15204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } else if( !arrayMap[source][target].count(duplicateNumber) ) { 153a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer errs() << " error [" << F->getName() << "()]: edge " 154a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer << source->getName() << " -> " << target->getName() 15504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick << " duplicate number " << duplicateNumber 15604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick << " does not exist in the array map.\n"; 15704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } else { 15804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick edgeArray[arrayMap[source][target][duplicateNumber]] 15904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick += currentPath->getCount(); 16004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 16104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 16204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 16304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick DEBUG(errs() << "\n"); 16404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 16504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick delete pev; 16604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 16704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 16804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 16904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick std::string errorInfo; 17004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick std::string filename = EdgeProfileFilename; 17104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 17204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Open a handle to the file 17304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick FILE* edgeFile = fopen(filename.c_str(),"wb"); 17404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 17504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if (!edgeFile) { 17604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick errs() << "error: unable to open file '" << filename << "' for output.\n"; 17704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return false; 17804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 17904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 18004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick errs() << "Generating edge profile '" << filename << "' ...\n"; 18104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 18204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // write argument info 18304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned type = ArgumentInfo; 18404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned num = pathProfileInfo.argList.size(); 18504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick int zeros = 0; 18604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 18704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick fwrite(&type,sizeof(unsigned),1,edgeFile); 18804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick fwrite(&num,sizeof(unsigned),1,edgeFile); 18904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick fwrite(pathProfileInfo.argList.c_str(),1,num,edgeFile); 19004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if (num&3) 19104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick fwrite(&zeros, 1, 4-(num&3), edgeFile); 19204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 19304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick type = EdgeInfo; 19404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick num = edgeArray.size(); 19504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick fwrite(&type,sizeof(unsigned),1,edgeFile); 19604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick fwrite(&num,sizeof(unsigned),1,edgeFile); 19704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 19804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // write each edge to the file 19904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick for( std::vector<unsigned>::iterator s = edgeArray.begin(), 20004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick e = edgeArray.end(); s != e; s++) 20104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick fwrite(&*s, sizeof (unsigned), 1, edgeFile); 20204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 20304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick fclose (edgeFile); 20404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 20504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return true; 20604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 207