1563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo//===- SampleProfile.cpp - Incorporate sample profiles into the IR --------===// 2563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// 3563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// The LLVM Compiler Infrastructure 4563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// 5563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// This file is distributed under the University of Illinois Open Source 6563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// License. See LICENSE.TXT for details. 7563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// 8563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo//===----------------------------------------------------------------------===// 9563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// 10563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// This file implements the SampleProfileLoader transformation. This pass 11563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// reads a profile file generated by a sampling profiler (e.g. Linux Perf - 12563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// http://perf.wiki.kernel.org/) and generates IR metadata to reflect the 13563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// profile information in the given profile. 14563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// 15563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// This pass generates branch weight annotations on the IR: 16563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// 17563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// - prof: Represents branch weights. This annotation is added to branches 18563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// to indicate the weights of each edge coming out of the branch. 19563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// The weight of each edge is the weight of the target block for 20563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// that edge. The weight of a block B is computed as the maximum 21563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// number of samples found in B. 22563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// 23563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo//===----------------------------------------------------------------------===// 24563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 2536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Transforms/Scalar.h" 26563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo#include "llvm/ADT/DenseMap.h" 2736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/SmallPtrSet.h" 2836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/SmallSet.h" 29563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo#include "llvm/ADT/StringMap.h" 30563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo#include "llvm/ADT/StringRef.h" 3136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Analysis/LoopInfo.h" 3236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Analysis/PostDominators.h" 33563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo#include "llvm/IR/Constants.h" 3436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/DebugInfo.h" 3536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/DiagnosticInfo.h" 3636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 37563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo#include "llvm/IR/Function.h" 3836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/InstIterator.h" 39563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo#include "llvm/IR/Instructions.h" 40563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo#include "llvm/IR/LLVMContext.h" 41563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo#include "llvm/IR/MDBuilder.h" 4236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Metadata.h" 43563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo#include "llvm/IR/Module.h" 44563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo#include "llvm/Pass.h" 45563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo#include "llvm/Support/CommandLine.h" 46563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo#include "llvm/Support/Debug.h" 4736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/LineIterator.h" 48563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo#include "llvm/Support/MemoryBuffer.h" 49563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo#include "llvm/Support/Regex.h" 50563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo#include "llvm/Support/raw_ostream.h" 5136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include <cctype> 52563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 53563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillousing namespace llvm; 54563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 55dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "sample-profile" 56dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 57563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// Command line option to specify the file to read samples from. This is 58563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo// mainly used for debugging. 59563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillostatic cl::opt<std::string> SampleProfileFile( 60563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo "sample-profile-file", cl::init(""), cl::value_desc("filename"), 61563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo cl::desc("Profile file loaded by -sample-profile"), cl::Hidden); 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic cl::opt<unsigned> SampleProfileMaxPropagateIterations( 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "sample-profile-max-propagate-iterations", cl::init(100), 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines cl::desc("Maximum number of iterations to go through when propagating " 6536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "sample block/edge weights through the CFG.")); 66563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 67563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillonamespace { 6836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Represents the relative location of an instruction. 6936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 7036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Instruction locations are specified by the line offset from the 7136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// beginning of the function (marked by the line where the function 7236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// header is) and the discriminator value within that line. 7336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 7436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// The discriminator value is useful to distinguish instructions 7536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// that are on the same line but belong to different basic blocks 7636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// (e.g., the two post-increment instructions in "if (p) x++; else y++;"). 7736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstruct InstructionLocation { 7836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines InstructionLocation(int L, unsigned D) : LineOffset(L), Discriminator(D) {} 7936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines int LineOffset; 8036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned Discriminator; 8136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 8236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 8336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 8436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesnamespace llvm { 8536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestemplate <> struct DenseMapInfo<InstructionLocation> { 8636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef DenseMapInfo<int> OffsetInfo; 8736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef DenseMapInfo<unsigned> DiscriminatorInfo; 8836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static inline InstructionLocation getEmptyKey() { 8936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return InstructionLocation(OffsetInfo::getEmptyKey(), 9036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DiscriminatorInfo::getEmptyKey()); 9136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 9236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static inline InstructionLocation getTombstoneKey() { 9336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return InstructionLocation(OffsetInfo::getTombstoneKey(), 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DiscriminatorInfo::getTombstoneKey()); 9536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 9636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static inline unsigned getHashValue(InstructionLocation Val) { 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return DenseMapInfo<std::pair<int, unsigned>>::getHashValue( 9836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::pair<int, unsigned>(Val.LineOffset, Val.Discriminator)); 9936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 10036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static inline bool isEqual(InstructionLocation LHS, InstructionLocation RHS) { 10136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return LHS.LineOffset == RHS.LineOffset && 10236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LHS.Discriminator == RHS.Discriminator; 10336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 10436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 10536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 10636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 10736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesnamespace { 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestypedef DenseMap<InstructionLocation, unsigned> BodySampleMap; 10936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestypedef DenseMap<BasicBlock *, unsigned> BlockWeightMap; 11036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestypedef DenseMap<BasicBlock *, BasicBlock *> EquivalenceClassMap; 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestypedef std::pair<BasicBlock *, BasicBlock *> Edge; 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestypedef DenseMap<Edge, unsigned> EdgeWeightMap; 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestypedef DenseMap<BasicBlock *, SmallVector<BasicBlock *, 8>> BlockEdgeMap; 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 11536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Representation of the runtime profile for a function. 11636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 11736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// This data structure contains the runtime profile for a given 11836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// function. It contains the total number of samples collected 11936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// in the function and a map of samples collected in every statement. 12036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesclass SampleFunctionProfile { 12136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinespublic: 12236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SampleFunctionProfile() 123dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : TotalSamples(0), TotalHeadSamples(0), HeaderLineno(0), DT(nullptr), 124dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PDT(nullptr), LI(nullptr), Ctx(nullptr) {} 12536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 12636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getFunctionLoc(Function &F); 12736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool emitAnnotations(Function &F, DominatorTree *DomTree, 12836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PostDominatorTree *PostDomTree, LoopInfo *Loops); 12936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getInstWeight(Instruction &I); 13036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getBlockWeight(BasicBlock *B); 13136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void addTotalSamples(unsigned Num) { TotalSamples += Num; } 13236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void addHeadSamples(unsigned Num) { TotalHeadSamples += Num; } 13336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void addBodySamples(int LineOffset, unsigned Discriminator, unsigned Num) { 13436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(LineOffset >= 0); 13536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BodySamples[InstructionLocation(LineOffset, Discriminator)] += Num; 13636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 13736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void print(raw_ostream &OS); 13836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void printEdgeWeight(raw_ostream &OS, Edge E); 13936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void printBlockWeight(raw_ostream &OS, BasicBlock *BB); 14036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void printBlockEquivalence(raw_ostream &OS, BasicBlock *BB); 14136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool computeBlockWeights(Function &F); 14236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void findEquivalenceClasses(Function &F); 14336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void findEquivalencesFor(BasicBlock *BB1, 14436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<BasicBlock *, 8> Descendants, 14536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTreeBase<BasicBlock> *DomTree); 14636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void propagateWeights(Function &F); 14736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge); 14836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void buildEdges(Function &F); 14936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool propagateThroughEdges(Function &F); 15036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool empty() { return BodySamples.empty(); } 15136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 15236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesprotected: 15336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Total number of samples collected inside this function. 15436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// 15536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Samples are cumulative, they include all the samples collected 15636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// inside this function and all its inlined callees. 15736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned TotalSamples; 15836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 15936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Total number of samples collected at the head of the function. 16036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// FIXME: Use head samples to estimate a cold/hot attribute for the function. 16136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned TotalHeadSamples; 16236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 16336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Line number for the function header. Used to compute relative 16436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// line numbers from the absolute line LOCs found in instruction locations. 16536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// The relative line numbers are needed to address the samples from the 16636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// profile file. 16736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned HeaderLineno; 16836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 16936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Map line offsets to collected samples. 17036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// 17136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Each entry in this map contains the number of samples 17236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// collected at the corresponding line offset. All line locations 17336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// are an offset from the start of the function. 17436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BodySampleMap BodySamples; 17536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 17636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Map basic blocks to their computed weights. 17736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// 17836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// The weight of a basic block is defined to be the maximum 17936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// of all the instruction weights in that block. 18036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BlockWeightMap BlockWeights; 18136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 18236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Map edges to their computed weights. 18336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// 18436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Edge weights are computed by propagating basic block weights in 18536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// SampleProfile::propagateWeights. 18636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines EdgeWeightMap EdgeWeights; 18736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 18836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Set of visited blocks during propagation. 18936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallPtrSet<BasicBlock *, 128> VisitedBlocks; 19036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 19136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Set of visited edges during propagation. 19236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallSet<Edge, 128> VisitedEdges; 19336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 19436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Equivalence classes for block weights. 19536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// 19636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Two blocks BB1 and BB2 are in the same equivalence class if they 19736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// dominate and post-dominate each other, and they are in the same loop 19836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// nest. When this happens, the two blocks are guaranteed to execute 19936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// the same number of times. 20036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines EquivalenceClassMap EquivalenceClass; 20136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 20236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Dominance, post-dominance and loop information. 20336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree *DT; 20436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PostDominatorTree *PDT; 20536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LoopInfo *LI; 20636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 20736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Predecessors for each basic block in the CFG. 20836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BlockEdgeMap Predecessors; 20936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 21036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Successors for each basic block in the CFG. 21136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BlockEdgeMap Successors; 21236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 21336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief LLVM context holding the debug data we need. 21436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LLVMContext *Ctx; 21536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 21636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 217563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// \brief Sample-based profile reader. 218563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 219563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// Each profile contains sample counts for all the functions 220563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// executed. Inside each function, statements are annotated with the 221563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// collected samples on all the instructions associated with that 222563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// statement. 223563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 224563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// For this to produce meaningful data, the program needs to be 225563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// compiled with some debug information (at minimum, line numbers: 226563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// -gline-tables-only). Otherwise, it will be impossible to match IR 227563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// instructions to the line numbers collected by the profiler. 228563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 229563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// From the profile file, we are interested in collecting the 230563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// following information: 231563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 232563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// * A list of functions included in the profile (mangled names). 233563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 234563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// * For each function F: 235563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 1. The total number of samples collected in F. 236563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 237563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 2. The samples collected at each line in F. To provide some 238563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// protection against source code shuffling, line numbers should 239563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// be relative to the start of the function. 24036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesclass SampleModuleProfile { 241563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillopublic: 24236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SampleModuleProfile(const Module &M, StringRef F) 24336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines : Profiles(0), Filename(F), M(M) {} 244563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 2454223b9601058369536caa1d15c9c19bc7c5a3706Alexey Samsonov void dump(); 24636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool loadText(); 2474223b9601058369536caa1d15c9c19bc7c5a3706Alexey Samsonov void loadNative() { llvm_unreachable("not implemented"); } 248563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo void printFunctionProfile(raw_ostream &OS, StringRef FName); 249563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo void dumpFunctionProfile(StringRef FName); 25036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SampleFunctionProfile &getProfile(const Function &F) { 25136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Profiles[F.getName()]; 25236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 253563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 25436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Report a parse error message. 25536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void reportParseError(int64_t LineNumber, Twine Msg) const { 25636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DiagnosticInfoSampleProfile Diag(Filename.data(), LineNumber, Msg); 25736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines M.getContext().diagnose(Diag); 25836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 259563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 26036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesprotected: 261563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo /// \brief Map every function to its associated profile. 262563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo /// 263563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo /// The profile of every function executed at runtime is collected 26436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// in the structure SampleFunctionProfile. This maps function objects 265563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo /// to their corresponding profiles. 26636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines StringMap<SampleFunctionProfile> Profiles; 267563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 268563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo /// \brief Path name to the file holding the profile data. 269563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo /// 270563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo /// The format of this file is defined by each profiler 271563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo /// independently. If possible, the profiler should have a text 272563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo /// version of the profile format to be used in constructing test 273563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo /// cases and debugging. 274563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo StringRef Filename; 275563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 27636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Module being compiled. Used mainly to access the current 27736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// LLVM context for diagnostics. 27836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const Module &M; 279563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo}; 280563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 281563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// \brief Sample profile pass. 282563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 283563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// This pass reads profile data from the file specified by 284563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// -sample-profile-file and annotates every affected function with the 285563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// profile information found in that file. 286563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novilloclass SampleProfileLoader : public FunctionPass { 287563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillopublic: 288563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo // Class identification, replacement for typeinfo 289563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo static char ID; 290563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 291563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo SampleProfileLoader(StringRef Name = SampleProfileFile) 29236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines : FunctionPass(ID), Profiler(), Filename(Name), ProfileIsValid(false) { 293563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo initializeSampleProfileLoaderPass(*PassRegistry::getPassRegistry()); 294563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo } 295563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 29636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool doInitialization(Module &M) override; 297563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 298563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo void dump() { Profiler->dump(); } 299563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 30036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const char *getPassName() const override { return "Sample profile pass"; } 301563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 30236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 303563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 30436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 305563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo AU.setPreservesCFG(); 30636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addRequired<LoopInfo>(); 30736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addRequired<DominatorTreeWrapperPass>(); 30836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addRequired<PostDominatorTree>(); 309563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo } 310563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 311563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novilloprotected: 312563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo /// \brief Profile reader object. 31336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::unique_ptr<SampleModuleProfile> Profiler; 314563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 315563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo /// \brief Name of the profile file to load. 316563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo StringRef Filename; 31736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 318dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// \brief Flag indicating whether the profile input loaded successfully. 31936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool ProfileIsValid; 320563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo}; 321563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo} 322563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 32336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Print this function profile on stream \p OS. 324563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 325563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// \param OS Stream to emit the output to. 32636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid SampleFunctionProfile::print(raw_ostream &OS) { 32736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OS << TotalSamples << ", " << TotalHeadSamples << ", " << BodySamples.size() 328563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo << " sampled lines\n"; 32936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (BodySampleMap::const_iterator SI = BodySamples.begin(), 33036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SE = BodySamples.end(); 331563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo SI != SE; ++SI) 33236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OS << "\tline offset: " << SI->first.LineOffset 33336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << ", discriminator: " << SI->first.Discriminator 334563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo << ", number of samples: " << SI->second << "\n"; 335563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo OS << "\n"; 336563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo} 337563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 33836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Print the weight of edge \p E on stream \p OS. 33936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 34036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param OS Stream to emit the output to. 34136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param E Edge to print. 34236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid SampleFunctionProfile::printEdgeWeight(raw_ostream &OS, Edge E) { 34336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OS << "weight[" << E.first->getName() << "->" << E.second->getName() 34436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << "]: " << EdgeWeights[E] << "\n"; 34536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 34636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 34736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Print the equivalence class of block \p BB on stream \p OS. 34836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 34936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param OS Stream to emit the output to. 35036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param BB Block to print. 35136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid SampleFunctionProfile::printBlockEquivalence(raw_ostream &OS, 35236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *BB) { 35336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *Equiv = EquivalenceClass[BB]; 35436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OS << "equivalence[" << BB->getName() 35536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << "]: " << ((Equiv) ? EquivalenceClass[BB]->getName() : "NONE") << "\n"; 35636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 35736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 35836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Print the weight of block \p BB on stream \p OS. 35936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 36036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param OS Stream to emit the output to. 36136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param BB Block to print. 36236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid SampleFunctionProfile::printBlockWeight(raw_ostream &OS, BasicBlock *BB) { 36336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OS << "weight[" << BB->getName() << "]: " << BlockWeights[BB] << "\n"; 36436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 36536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 36636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Print the function profile for \p FName on stream \p OS. 36736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 36836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param OS Stream to emit the output to. 36936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param FName Name of the function to print. 37036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid SampleModuleProfile::printFunctionProfile(raw_ostream &OS, 37136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines StringRef FName) { 37236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OS << "Function: " << FName << ":\n"; 37336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Profiles[FName].print(OS); 37436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 37536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 376563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// \brief Dump the function profile for \p FName. 377563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 378563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// \param FName Name of the function to print. 37936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid SampleModuleProfile::dumpFunctionProfile(StringRef FName) { 380563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo printFunctionProfile(dbgs(), FName); 381563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo} 382563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 383563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// \brief Dump all the function profiles found. 38436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid SampleModuleProfile::dump() { 38536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (StringMap<SampleFunctionProfile>::const_iterator I = Profiles.begin(), 38636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines E = Profiles.end(); 387563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo I != E; ++I) 388563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo dumpFunctionProfile(I->getKey()); 389563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo} 390563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 391563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// \brief Load samples from a text file. 392563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 39336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// The file contains a list of samples for every function executed at 39436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// runtime. Each function profile has the following format: 395563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 39636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// function1:total_samples:total_head_samples 39736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// offset1[.discriminator]: number_of_samples [fn1:num fn2:num ... ] 39836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// offset2[.discriminator]: number_of_samples [fn3:num fn4:num ... ] 399563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// ... 40036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// offsetN[.discriminator]: number_of_samples [fn5:num fn6:num ... ] 401563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 402563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// Function names must be mangled in order for the profile loader to 40336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// match them in the current translation unit. The two numbers in the 40436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// function header specify how many total samples were accumulated in 40536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// the function (first number), and the total number of samples accumulated 40636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// at the prologue of the function (second number). This head sample 40736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// count provides an indicator of how frequent is the function invoked. 40836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 40936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Each sampled line may contain several items. Some are optional 41036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// (marked below): 41136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 41236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// a- Source line offset. This number represents the line number 41336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// in the function where the sample was collected. The line number 41436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// is always relative to the line where symbol of the function 41536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// is defined. So, if the function has its header at line 280, 41636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// the offset 13 is at line 293 in the file. 41736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 41836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// b- [OPTIONAL] Discriminator. This is used if the sampled program 41936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// was compiled with DWARF discriminator support 42036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// (http://wiki.dwarfstd.org/index.php?title=Path_Discriminators) 42136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 42236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// c- Number of samples. This is the number of samples collected by 42336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// the profiler at this source location. 42436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 42536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// d- [OPTIONAL] Potential call targets and samples. If present, this 42636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// line contains a call instruction. This models both direct and 42736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// indirect calls. Each called target is listed together with the 42836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// number of samples. For example, 42936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 43036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 130: 7 foo:3 bar:2 baz:7 43136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 43236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// The above means that at relative line offset 130 there is a 43336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// call instruction that calls one of foo(), bar() and baz(). With 43436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// baz() being the relatively more frequent call target. 43536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 43636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// FIXME: This is currently unhandled, but it has a lot of 43736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// potential for aiding the inliner. 43836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 439563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 440563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// Since this is a flat profile, a function that shows up more than 441563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// once gets all its samples aggregated across all its instances. 44236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 44336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// FIXME: flat profiles are too imprecise to provide good optimization 44436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// opportunities. Convert them to context-sensitive profile. 445563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 446563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// This textual representation is useful to generate unit tests and 447563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// for debugging purposes, but it should not be used to generate 448563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// profiles for large programs, as the representation is extremely 449563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// inefficient. 45036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 45136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \returns true if the file was loaded successfully, false otherwise. 45236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool SampleModuleProfile::loadText() { 453cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ErrorOr<std::unique_ptr<MemoryBuffer>> BufferOrErr = 454cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines MemoryBuffer::getFile(Filename); 455cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (std::error_code EC = BufferOrErr.getError()) { 45636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::string Msg(EC.message()); 45736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines M.getContext().diagnose(DiagnosticInfoSampleProfile(Filename.data(), Msg)); 45836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 459563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo } 460cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines std::unique_ptr<MemoryBuffer> Buffer = std::move(BufferOrErr.get()); 46136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines line_iterator LineIt(*Buffer, '#'); 462563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 463563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo // Read the profile of each function. Since each function may be 464563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo // mentioned more than once, and we are collecting flat profiles, 465563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo // accumulate samples as we parse them. 46636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Regex HeadRE("^([^0-9].*):([0-9]+):([0-9]+)$"); 46736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Regex LineSample("^([0-9]+)\\.?([0-9]+)?: ([0-9]+)(.*)$"); 46836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines while (!LineIt.is_at_eof()) { 46936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Read the header of each function. 47036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 47136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Note that for function identifiers we are actually expecting 47236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // mangled names, but we may not always get them. This happens when 47336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // the compiler decides not to emit the function (e.g., it was inlined 47436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // and removed). In this case, the binary will not have the linkage 47536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // name for the function, so the profiler will emit the function's 47636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // unmangled name, which may contain characters like ':' and '>' in its 47736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // name (member functions, templates, etc). 47836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 47936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // The only requirement we place on the identifier, then, is that it 48036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // should not begin with a number. 48136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<StringRef, 3> Matches; 48236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!HeadRE.match(*LineIt, &Matches)) { 48336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines reportParseError(LineIt.line_number(), 48436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "Expected 'mangled_name:NUM:NUM', found " + *LineIt); 48536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 48636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 48736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(Matches.size() == 4); 488563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo StringRef FName = Matches[1]; 48936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned NumSamples, NumHeadSamples; 490563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo Matches[2].getAsInteger(10, NumSamples); 491563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo Matches[3].getAsInteger(10, NumHeadSamples); 49236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Profiles[FName] = SampleFunctionProfile(); 49336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SampleFunctionProfile &FProfile = Profiles[FName]; 49436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FProfile.addTotalSamples(NumSamples); 49536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FProfile.addHeadSamples(NumHeadSamples); 49636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ++LineIt; 49736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 49836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Now read the body. The body of the function ends when we reach 49936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // EOF or when we see the start of the next function. 50036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines while (!LineIt.is_at_eof() && isdigit((*LineIt)[0])) { 50136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!LineSample.match(*LineIt, &Matches)) { 50236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines reportParseError( 50336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LineIt.line_number(), 50436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "Expected 'NUM[.NUM]: NUM[ mangled_name:NUM]*', found " + *LineIt); 50536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 50636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 50736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(Matches.size() == 5); 50836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned LineOffset, NumSamples, Discriminator = 0; 509563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo Matches[1].getAsInteger(10, LineOffset); 51036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Matches[2] != "") 51136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Matches[2].getAsInteger(10, Discriminator); 51236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Matches[3].getAsInteger(10, NumSamples); 51336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 51436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // FIXME: Handle called targets (in Matches[4]). 515563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 51636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // When dealing with instruction weights, we use the value 51736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // zero to indicate the absence of a sample. If we read an 51836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // actual zero from the profile file, return it as 1 to 51936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // avoid the confusion later on. 52036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (NumSamples == 0) 52136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NumSamples = 1; 52236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FProfile.addBodySamples(LineOffset, Discriminator, NumSamples); 52336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ++LineIt; 52436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 525563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo } 52636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 52736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 528563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo} 529563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 530563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// \brief Get the weight for an instruction. 531563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 532563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// The "weight" of an instruction \p Inst is the number of samples 533563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// collected on that instruction at runtime. To retrieve it, we 534563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// need to compute the line number of \p Inst relative to the start of its 53536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// function. We use HeaderLineno to compute the offset. We then 53636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// look up the samples collected for \p Inst using BodySamples. 537563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 538563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// \param Inst Instruction to query. 539563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 540563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// \returns The profiled weight of I. 54136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesunsigned SampleFunctionProfile::getInstWeight(Instruction &Inst) { 54236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DebugLoc DLoc = Inst.getDebugLoc(); 54336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned Lineno = DLoc.getLine(); 54436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Lineno < HeaderLineno) 54536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return 0; 54636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 54736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DILocation DIL(DLoc.getAsMDNode(*Ctx)); 54836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines int LOffset = Lineno - HeaderLineno; 54936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned Discriminator = DIL.getDiscriminator(); 55036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned Weight = 55136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BodySamples.lookup(InstructionLocation(LOffset, Discriminator)); 55236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << " " << Lineno << "." << Discriminator << ":" << Inst 55336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << " (line offset: " << LOffset << "." << Discriminator 55436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << " - weight: " << Weight << ")\n"); 55536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Weight; 556563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo} 557563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 558563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// \brief Compute the weight of a basic block. 559563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 560563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// The weight of basic block \p B is the maximum weight of all the 56136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// instructions in B. The weight of \p B is computed and cached in 56236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// the BlockWeights map. 563563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 564563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// \param B The basic block to query. 565563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 566563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// \returns The computed weight of B. 56736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesunsigned SampleFunctionProfile::getBlockWeight(BasicBlock *B) { 568563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo // If we've computed B's weight before, return it. 569563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo std::pair<BlockWeightMap::iterator, bool> Entry = 57036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BlockWeights.insert(std::make_pair(B, 0)); 571563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo if (!Entry.second) 572563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo return Entry.first->second; 573563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 574563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo // Otherwise, compute and cache B's weight. 57536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned Weight = 0; 576563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo for (BasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) { 57736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned InstWeight = getInstWeight(*I); 578563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo if (InstWeight > Weight) 579563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo Weight = InstWeight; 580563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo } 581563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo Entry.first->second = Weight; 582563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo return Weight; 583563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo} 584563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 58536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Compute and store the weights of every basic block. 586563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 58736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// This populates the BlockWeights map by computing 58836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// the weights of every basic block in the CFG. 589563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 59036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param F The function to query. 59136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool SampleFunctionProfile::computeBlockWeights(Function &F) { 59236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool Changed = false; 59336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Block weights\n"); 59436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Function::iterator B = F.begin(), E = F.end(); B != E; ++B) { 59536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned Weight = getBlockWeight(B); 59636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Changed |= (Weight > 0); 59736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(printBlockWeight(dbgs(), B)); 59836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 59936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 60036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Changed; 60136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 60236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 60336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Find equivalence classes for the given block. 604563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 60536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// This finds all the blocks that are guaranteed to execute the same 60636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// number of times as \p BB1. To do this, it traverses all the the 60736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// descendants of \p BB1 in the dominator or post-dominator tree. 60836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 60936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// A block BB2 will be in the same equivalence class as \p BB1 if 61036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// the following holds: 61136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 61236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 1- \p BB1 is a descendant of BB2 in the opposite tree. So, if BB2 61336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// is a descendant of \p BB1 in the dominator tree, then BB2 should 61436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// dominate BB1 in the post-dominator tree. 61536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 61636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 2- Both BB2 and \p BB1 must be in the same loop. 61736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 61836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// For every block BB2 that meets those two requirements, we set BB2's 61936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// equivalence class to \p BB1. 62036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 62136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param BB1 Block to check. 62236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param Descendants Descendants of \p BB1 in either the dom or pdom tree. 62336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param DomTree Opposite dominator tree. If \p Descendants is filled 62436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// with blocks from \p BB1's dominator tree, then 62536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// this is the post-dominator tree, and vice versa. 62636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid SampleFunctionProfile::findEquivalencesFor( 62736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *BB1, SmallVector<BasicBlock *, 8> Descendants, 62836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTreeBase<BasicBlock> *DomTree) { 62936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (SmallVectorImpl<BasicBlock *>::iterator I = Descendants.begin(), 63036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines E = Descendants.end(); 63136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines I != E; ++I) { 63236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *BB2 = *I; 63336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool IsDomParent = DomTree->dominates(BB2, BB1); 63436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2); 63536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (BB1 != BB2 && VisitedBlocks.insert(BB2) && IsDomParent && 63636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines IsInSameLoop) { 63736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines EquivalenceClass[BB2] = BB1; 63836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 63936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If BB2 is heavier than BB1, make BB2 have the same weight 64036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // as BB1. 64136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 64236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Note that we don't worry about the opposite situation here 64336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // (when BB2 is lighter than BB1). We will deal with this 64436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // during the propagation phase. Right now, we just want to 64536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // make sure that BB1 has the largest weight of all the 64636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // members of its equivalence set. 64736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned &BB1Weight = BlockWeights[BB1]; 64836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned &BB2Weight = BlockWeights[BB2]; 64936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BB1Weight = std::max(BB1Weight, BB2Weight); 65036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 65136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 65236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 65336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 65436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Find equivalence classes. 65536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 65636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Since samples may be missing from blocks, we can fill in the gaps by setting 65736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// the weights of all the blocks in the same equivalence class to the same 65836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// weight. To compute the concept of equivalence, we use dominance and loop 65936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// information. Two blocks B1 and B2 are in the same equivalence class if B1 66036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// dominates B2, B2 post-dominates B1 and both are in the same loop. 661563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// 662563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo/// \param F The function to query. 66336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid SampleFunctionProfile::findEquivalenceClasses(Function &F) { 66436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<BasicBlock *, 8> DominatedBBs; 66536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "\nBlock equivalence classes\n"); 66636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Find equivalence sets based on dominance and post-dominance information. 66736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Function::iterator B = F.begin(), E = F.end(); B != E; ++B) { 66836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *BB1 = B; 66936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 67036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Compute BB1's equivalence class once. 67136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (EquivalenceClass.count(BB1)) { 67236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(printBlockEquivalence(dbgs(), BB1)); 67336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 67436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 67536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 67636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // By default, blocks are in their own equivalence class. 67736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines EquivalenceClass[BB1] = BB1; 67836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 67936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Traverse all the blocks dominated by BB1. We are looking for 68036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // every basic block BB2 such that: 68136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 68236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 1- BB1 dominates BB2. 68336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 2- BB2 post-dominates BB1. 68436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 3- BB1 and BB2 are in the same loop nest. 68536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 68636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If all those conditions hold, it means that BB2 is executed 68736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // as many times as BB1, so they are placed in the same equivalence 68836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // class by making BB2's equivalence class be BB1. 68936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatedBBs.clear(); 69036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DT->getDescendants(BB1, DominatedBBs); 69136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines findEquivalencesFor(BB1, DominatedBBs, PDT->DT); 69236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 69336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Repeat the same logic for all the blocks post-dominated by BB1. 69436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // We are looking for every basic block BB2 such that: 69536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 69636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 1- BB1 post-dominates BB2. 69736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 2- BB2 dominates BB1. 69836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 3- BB1 and BB2 are in the same loop nest. 69936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 70036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If all those conditions hold, BB2's equivalence class is BB1. 70136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatedBBs.clear(); 70236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PDT->getDescendants(BB1, DominatedBBs); 70336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines findEquivalencesFor(BB1, DominatedBBs, DT); 70436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 70536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(printBlockEquivalence(dbgs(), BB1)); 70636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 70736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 70836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Assign weights to equivalence classes. 70936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 71036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // All the basic blocks in the same equivalence class will execute 71136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // the same number of times. Since we know that the head block in 71236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // each equivalence class has the largest weight, assign that weight 71336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // to all the blocks in that equivalence class. 71436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "\nAssign the same weight to all blocks in the same class\n"); 71536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Function::iterator B = F.begin(), E = F.end(); B != E; ++B) { 71636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *BB = B; 71736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *EquivBB = EquivalenceClass[BB]; 71836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (BB != EquivBB) 71936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BlockWeights[BB] = BlockWeights[EquivBB]; 72036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(printBlockWeight(dbgs(), BB)); 72136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 72236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 72336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 72436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Visit the given edge to decide if it has a valid weight. 72536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 72636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// If \p E has not been visited before, we copy to \p UnknownEdge 72736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// and increment the count of unknown edges. 72836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 72936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param E Edge to visit. 73036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param NumUnknownEdges Current number of unknown edges. 73136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param UnknownEdge Set if E has not been visited before. 73236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 73336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \returns E's weight, if known. Otherwise, return 0. 73436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesunsigned SampleFunctionProfile::visitEdge(Edge E, unsigned *NumUnknownEdges, 73536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Edge *UnknownEdge) { 73636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!VisitedEdges.count(E)) { 73736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (*NumUnknownEdges)++; 73836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines *UnknownEdge = E; 73936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return 0; 74036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 74136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 74236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return EdgeWeights[E]; 74336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 74436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 74536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Propagate weights through incoming/outgoing edges. 74636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 74736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// If the weight of a basic block is known, and there is only one edge 74836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// with an unknown weight, we can calculate the weight of that edge. 74936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 75036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Similarly, if all the edges have a known count, we can calculate the 75136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// count of the basic block, if needed. 75236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 75336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param F Function to process. 75436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 75536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \returns True if new weights were assigned to edges or blocks. 75636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool SampleFunctionProfile::propagateThroughEdges(Function &F) { 757563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo bool Changed = false; 75836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "\nPropagation through edges\n"); 75936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Function::iterator BI = F.begin(), EI = F.end(); BI != EI; ++BI) { 76036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *BB = BI; 76136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 76236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Visit all the predecessor and successor edges to determine 76336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // which ones have a weight assigned already. Note that it doesn't 76436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // matter that we only keep track of a single unknown edge. The 76536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // only case we are interested in handling is when only a single 76636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // edge is unknown (see setEdgeOrBlockWeight). 76736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (unsigned i = 0; i < 2; i++) { 76836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned TotalWeight = 0; 76936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned NumUnknownEdges = 0; 77036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Edge UnknownEdge, SelfReferentialEdge; 77136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 77236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (i == 0) { 77336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // First, visit all predecessor edges. 77436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (size_t I = 0; I < Predecessors[BB].size(); I++) { 77536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Edge E = std::make_pair(Predecessors[BB][I], BB); 77636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines TotalWeight += visitEdge(E, &NumUnknownEdges, &UnknownEdge); 77736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (E.first == E.second) 77836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SelfReferentialEdge = E; 77936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 78036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else { 78136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // On the second round, visit all successor edges. 78236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (size_t I = 0; I < Successors[BB].size(); I++) { 78336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Edge E = std::make_pair(BB, Successors[BB][I]); 78436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines TotalWeight += visitEdge(E, &NumUnknownEdges, &UnknownEdge); 78536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 78636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 78736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 78836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // After visiting all the edges, there are three cases that we 78936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // can handle immediately: 79036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 79136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // - All the edge weights are known (i.e., NumUnknownEdges == 0). 79236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // In this case, we simply check that the sum of all the edges 79336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // is the same as BB's weight. If not, we change BB's weight 79436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // to match. Additionally, if BB had not been visited before, 79536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // we mark it visited. 79636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 79736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // - Only one edge is unknown and BB has already been visited. 79836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // In this case, we can compute the weight of the edge by 79936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // subtracting the total block weight from all the known 80036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // edge weights. If the edges weight more than BB, then the 80136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // edge of the last remaining edge is set to zero. 80236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 80336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // - There exists a self-referential edge and the weight of BB is 80436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // known. In this case, this edge can be based on BB's weight. 80536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // We add up all the other known edges and set the weight on 80636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // the self-referential edge as we did in the previous case. 80736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 80836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // In any other case, we must continue iterating. Eventually, 80936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // all edges will get a weight, or iteration will stop when 81036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // it reaches SampleProfileMaxPropagateIterations. 81136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (NumUnknownEdges <= 1) { 81236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned &BBWeight = BlockWeights[BB]; 81336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (NumUnknownEdges == 0) { 81436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If we already know the weight of all edges, the weight of the 81536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // basic block can be computed. It should be no larger than the sum 81636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // of all edge weights. 81736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (TotalWeight > BBWeight) { 81836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BBWeight = TotalWeight; 81936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Changed = true; 82036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "All edge weights for " << BB->getName() 82136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << " known. Set weight for block: "; 82236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines printBlockWeight(dbgs(), BB);); 82336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 82436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (VisitedBlocks.insert(BB)) 82536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Changed = true; 82636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else if (NumUnknownEdges == 1 && VisitedBlocks.count(BB)) { 82736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If there is a single unknown edge and the block has been 82836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // visited, then we can compute E's weight. 82936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (BBWeight >= TotalWeight) 83036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines EdgeWeights[UnknownEdge] = BBWeight - TotalWeight; 83136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines else 83236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines EdgeWeights[UnknownEdge] = 0; 83336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines VisitedEdges.insert(UnknownEdge); 83436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Changed = true; 83536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Set weight for edge: "; 83636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines printEdgeWeight(dbgs(), UnknownEdge)); 83736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 83836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else if (SelfReferentialEdge.first && VisitedBlocks.count(BB)) { 83936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned &BBWeight = BlockWeights[BB]; 84036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // We have a self-referential edge and the weight of BB is known. 84136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (BBWeight >= TotalWeight) 84236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight; 84336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines else 84436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines EdgeWeights[SelfReferentialEdge] = 0; 84536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines VisitedEdges.insert(SelfReferentialEdge); 84636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Changed = true; 84736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Set self-referential edge weight to: "; 84836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines printEdgeWeight(dbgs(), SelfReferentialEdge)); 84936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 85036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 85136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 85236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 85336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Changed; 85436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 85536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 85636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Build in/out edge lists for each basic block in the CFG. 85736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 85836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// We are interested in unique edges. If a block B1 has multiple 85936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// edges to another block B2, we only add a single B1->B2 edge. 86036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid SampleFunctionProfile::buildEdges(Function &F) { 86136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 86236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *B1 = I; 863563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 86436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Add predecessors for B1. 86536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallPtrSet<BasicBlock *, 16> Visited; 86636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!Predecessors[B1].empty()) 86736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines llvm_unreachable("Found a stale predecessors list in a basic block."); 86836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (pred_iterator PI = pred_begin(B1), PE = pred_end(B1); PI != PE; ++PI) { 86936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *B2 = *PI; 87036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Visited.insert(B2)) 87136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Predecessors[B1].push_back(B2); 87236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 87336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 87436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Add successors for B1. 87536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Visited.clear(); 87636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!Successors[B1].empty()) 87736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines llvm_unreachable("Found a stale successors list in a basic block."); 87836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (succ_iterator SI = succ_begin(B1), SE = succ_end(B1); SI != SE; ++SI) { 87936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *B2 = *SI; 88036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Visited.insert(B2)) 88136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Successors[B1].push_back(B2); 88236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 88336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 88436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 88536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 88636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Propagate weights into edges 88736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 88836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// The following rules are applied to every block B in the CFG: 88936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 89036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// - If B has a single predecessor/successor, then the weight 89136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// of that edge is the weight of the block. 89236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 89336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// - If all incoming or outgoing edges are known except one, and the 89436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// weight of the block is already known, the weight of the unknown 89536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// edge will be the weight of the block minus the sum of all the known 89636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// edges. If the sum of all the known edges is larger than B's weight, 89736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// we set the unknown edge weight to zero. 89836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 89936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// - If there is a self-referential edge, and the weight of the block is 90036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// known, the weight for that edge is set to the weight of the block 90136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// minus the weight of the other incoming edges to that block (if 90236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// known). 90336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid SampleFunctionProfile::propagateWeights(Function &F) { 90436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool Changed = true; 90536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned i = 0; 90636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 90736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Before propagation starts, build, for each block, a list of 90836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // unique predecessors and successors. This is necessary to handle 90936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // identical edges in multiway branches. Since we visit all blocks and all 91036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // edges of the CFG, it is cleaner to build these lists once at the start 91136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // of the pass. 91236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines buildEdges(F); 913563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 91436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Propagate until we converge or we go past the iteration limit. 91536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines while (Changed && i++ < SampleProfileMaxPropagateIterations) { 91636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Changed = propagateThroughEdges(F); 91736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 91836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 91936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Generate MD_prof metadata for every branch instruction using the 92036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // edge weights computed during propagation. 92136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "\nPropagation complete. Setting branch weights\n"); 92236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MDBuilder MDB(F.getContext()); 923563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 924563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo BasicBlock *B = I; 925563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo TerminatorInst *TI = B->getTerminator(); 926563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo if (TI->getNumSuccessors() == 1) 927563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo continue; 928563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI)) 929563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo continue; 930563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 93136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "\nGetting weights for branch at line " 93236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << TI->getDebugLoc().getLine() << ".\n"); 93336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<unsigned, 4> Weights; 93436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool AllWeightsZero = true; 93536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (unsigned I = 0; I < TI->getNumSuccessors(); ++I) { 936563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo BasicBlock *Succ = TI->getSuccessor(I); 93736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Edge E = std::make_pair(B, Succ); 93836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned Weight = EdgeWeights[E]; 93936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "\t"; printEdgeWeight(dbgs(), E)); 940563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo Weights.push_back(Weight); 94136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Weight != 0) 94236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AllWeightsZero = false; 943563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo } 944563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 94536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Only set weights if there is at least one non-zero weight. 94636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // In any other case, let the analyzer set weights. 94736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!AllWeightsZero) { 94836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "SUCCESS. Found non-zero weights.\n"); 94936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines TI->setMetadata(llvm::LLVMContext::MD_prof, 95036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MDB.createBranchWeights(Weights)); 95136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else { 95236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "SKIPPED. All branch weights are zero.\n"); 95336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 954563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo } 95536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 956563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 95736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Get the line number for the function header. 95836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 95936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// This looks up function \p F in the current compilation unit and 96036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// retrieves the line number where the function is defined. This is 96136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// line 0 for all the samples read from the profile file. Every line 96236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// number is relative to this line. 96336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 96436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param F Function object to query. 96536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 96636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \returns the line number where \p F is defined. If it returns 0, 96736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// it means that there is no debug information available for \p F. 96836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesunsigned SampleFunctionProfile::getFunctionLoc(Function &F) { 96936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NamedMDNode *CUNodes = F.getParent()->getNamedMetadata("llvm.dbg.cu"); 97036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (CUNodes) { 97136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (unsigned I = 0, E1 = CUNodes->getNumOperands(); I != E1; ++I) { 97236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DICompileUnit CU(CUNodes->getOperand(I)); 97336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DIArray Subprograms = CU.getSubprograms(); 97436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (unsigned J = 0, E2 = Subprograms.getNumElements(); J != E2; ++J) { 97536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DISubprogram Subprogram(Subprograms.getElement(J)); 97636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Subprogram.describes(&F)) 97736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Subprogram.getLineNumber(); 97836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 97936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 98036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 98136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 98236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines F.getContext().diagnose(DiagnosticInfoSampleProfile( 98336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "No debug information found in function " + F.getName())); 98436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return 0; 985563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo} 986563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 98736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Generate branch weight metadata for all branches in \p F. 98836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 98936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Branch weights are computed out of instruction samples using a 99036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// propagation heuristic. Propagation proceeds in 3 phases: 99136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 99236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 1- Assignment of block weights. All the basic blocks in the function 99336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// are initial assigned the same weight as their most frequently 99436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// executed instruction. 99536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 99636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 2- Creation of equivalence classes. Since samples may be missing from 99736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// blocks, we can fill in the gaps by setting the weights of all the 99836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// blocks in the same equivalence class to the same weight. To compute 99936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// the concept of equivalence, we use dominance and loop information. 100036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Two blocks B1 and B2 are in the same equivalence class if B1 100136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// dominates B2, B2 post-dominates B1 and both are in the same loop. 100236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 100336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 3- Propagation of block weights into edges. This uses a simple 100436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// propagation heuristic. The following rules are applied to every 100536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// block B in the CFG: 100636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 100736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// - If B has a single predecessor/successor, then the weight 100836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// of that edge is the weight of the block. 100936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 101036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// - If all the edges are known except one, and the weight of the 101136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// block is already known, the weight of the unknown edge will 101236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// be the weight of the block minus the sum of all the known 101336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// edges. If the sum of all the known edges is larger than B's weight, 101436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// we set the unknown edge weight to zero. 101536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 101636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// - If there is a self-referential edge, and the weight of the block is 101736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// known, the weight for that edge is set to the weight of the block 101836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// minus the weight of the other incoming edges to that block (if 101936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// known). 102036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 102136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Since this propagation is not guaranteed to finalize for every CFG, we 102236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// only allow it to proceed for a limited number of iterations (controlled 102336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// by -sample-profile-max-propagate-iterations). 102436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 102536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// FIXME: Try to replace this propagation heuristic with a scheme 102636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// that is guaranteed to finalize. A work-list approach similar to 102736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// the standard value propagation algorithm used by SSA-CCP might 102836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// work here. 102936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 103036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Once all the branch weights are computed, we emit the MD_prof 103136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// metadata on B using the computed values for each of its branches. 103236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 103336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param F The function to query. 103436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 103536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \returns true if \p F was modified. Returns false, otherwise. 103636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool SampleFunctionProfile::emitAnnotations(Function &F, DominatorTree *DomTree, 103736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PostDominatorTree *PostDomTree, 103836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LoopInfo *Loops) { 103936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool Changed = false; 1040563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 104136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Initialize invariants used during computation and propagation. 104236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines HeaderLineno = getFunctionLoc(F); 104336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (HeaderLineno == 0) 104436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 104536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 104636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Line number for the first instruction in " << F.getName() 104736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << ": " << HeaderLineno << "\n"); 104836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DT = DomTree; 104936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PDT = PostDomTree; 105036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LI = Loops; 105136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Ctx = &F.getParent()->getContext(); 105236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 105336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Compute basic block weights. 105436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Changed |= computeBlockWeights(F); 105536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 105636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Changed) { 105736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Find equivalence classes. 105836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines findEquivalenceClasses(F); 105936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 106036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Propagate weights to all edges. 106136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines propagateWeights(F); 106236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 106336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 106436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Changed; 1065563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo} 1066563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 106736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hineschar SampleProfileLoader::ID = 0; 106836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_BEGIN(SampleProfileLoader, "sample-profile", 106936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "Sample Profile loader", false, false) 107036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 107136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_DEPENDENCY(PostDominatorTree) 107236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_DEPENDENCY(LoopInfo) 107336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_DEPENDENCY(AddDiscriminators) 107436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_END(SampleProfileLoader, "sample-profile", 107536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "Sample Profile loader", false, false) 107636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1077563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillobool SampleProfileLoader::doInitialization(Module &M) { 107836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Profiler.reset(new SampleModuleProfile(M, Filename)); 107936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ProfileIsValid = Profiler->loadText(); 1080563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo return true; 1081563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo} 1082563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 1083563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego NovilloFunctionPass *llvm::createSampleProfileLoaderPass() { 1084563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo return new SampleProfileLoader(SampleProfileFile); 1085563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo} 1086563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo 1087563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego NovilloFunctionPass *llvm::createSampleProfileLoaderPass(StringRef Name) { 1088563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo return new SampleProfileLoader(Name); 1089563b29f8db68275407ffcd2a9a5f0ba77ee5e899Diego Novillo} 109036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 109136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool SampleProfileLoader::runOnFunction(Function &F) { 109236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!ProfileIsValid) 109336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 109436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 109536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PostDominatorTree *PDT = &getAnalysis<PostDominatorTree>(); 109636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LoopInfo *LI = &getAnalysis<LoopInfo>(); 109736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SampleFunctionProfile &FunctionProfile = Profiler->getProfile(F); 109836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!FunctionProfile.empty()) 109936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return FunctionProfile.emitAnnotations(F, DT, PDT, LI); 110036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 110136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 1102