From fd9533b4a35983d38804349efca8116788b311d9 Mon Sep 17 00:00:00 2001 From: Jakub Staszak Date: Thu, 23 Jun 2011 21:56:59 +0000 Subject: [PATCH] Missing files for the BlockFrequency analysis added. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133767 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/BlockFrequency.h | 53 +++++ include/llvm/Analysis/BlockFrequencyImpl.h | 336 +++++++++++++++++++++++++++++ lib/Analysis/BlockFrequency.cpp | 59 +++++ 3 files changed, 448 insertions(+) create mode 100644 include/llvm/Analysis/BlockFrequency.h create mode 100644 include/llvm/Analysis/BlockFrequencyImpl.h create mode 100644 lib/Analysis/BlockFrequency.cpp diff --git a/include/llvm/Analysis/BlockFrequency.h b/include/llvm/Analysis/BlockFrequency.h new file mode 100644 index 00000000000..c4b1e087a0b --- /dev/null +++ b/include/llvm/Analysis/BlockFrequency.h @@ -0,0 +1,53 @@ +//========-------- BlockFrequency.h - Block Frequency Analysis -------========// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Loops should be simplified before this analysis. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_BLOCKFREQUENCY_H +#define LLVM_ANALYSIS_BLOCKFREQUENCY_H + +#include "llvm/Pass.h" +#include + +namespace llvm { + +class BranchProbabilityInfo; +template +class BlockFrequencyImpl; + +/// BlockFrequency pass uses BlockFrequencyImpl implementation to estimate +/// IR basic block frequencies. +class BlockFrequency : public FunctionPass { + + BlockFrequencyImpl *BFI; + +public: + static char ID; + + BlockFrequency(); + + ~BlockFrequency(); + + void getAnalysisUsage(AnalysisUsage &AU) const; + + bool runOnFunction(Function &F); + + /// getblockFreq - Return block frequency. Never return 0, value must be + /// positive. Please note that initial frequency is equal to 1024. It means + /// that we should not rely on the value itself, but only on the comparison to + /// the other block frequencies. We do this to avoid using of the floating + /// points. + uint32_t getBlockFreq(BasicBlock *BB); +}; + +} + +#endif diff --git a/include/llvm/Analysis/BlockFrequencyImpl.h b/include/llvm/Analysis/BlockFrequencyImpl.h new file mode 100644 index 00000000000..7447e80a319 --- /dev/null +++ b/include/llvm/Analysis/BlockFrequencyImpl.h @@ -0,0 +1,336 @@ +//===---- BlockFrequencyImpl.h - Machine Block Frequency Implementation ---===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Shared implementation of BlockFrequency for IR and Machine Instructions. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_BLOCKFREQUENCYIMPL_H +#define LLVM_ANALYSIS_BLOCKFREQUENCYIMPL_H + +#include "llvm/BasicBlock.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/Support/BranchProbability.h" +#include "llvm/Support/Debug.h" +#include +#include +#include + +namespace llvm { + + +class BlockFrequency; +/// BlockFrequencyImpl implements block frequency algorithm for IR and +/// Machine Instructions. Algorithm starts with value 1024 (START_FREQ) +/// for the entry block and then propagates frequencies using branch weights +/// from (Machine)BranchProbabilityInfo. LoopInfo is not required because +/// algorithm can find "backedges" by itself. +template +class BlockFrequencyImpl { + + DenseMap Freqs; + + BlockProbInfoT *BPI; + + FunctionT *Fn; + + typedef GraphTraits< Inverse > GT; + + static const uint32_t START_FREQ = 1024; + + std::string getBlockName(BasicBlock *BB) const { + return BB->getNameStr(); + } + + std::string getBlockName(MachineBasicBlock *MBB) const { + std::stringstream ss; + ss << "BB#" << MBB->getNumber(); + const BasicBlock *BB = MBB->getBasicBlock(); + + if (BB) + ss << " derived from LLVM BB " << BB->getNameStr(); + + return ss.str(); + } + + void setBlockFreq(BlockT *BB, uint32_t Freq) { + Freqs[BB] = Freq; + DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") = " << Freq << "\n"); + } + + /// getEdgeFreq - Return edge frequency based on SRC frequency and Src -> Dst + /// edge probability. + uint32_t getEdgeFreq(BlockT *Src, BlockT *Dst) const { + BranchProbability Prob = BPI->getEdgeProbability(Src, Dst); + uint64_t N = Prob.getNumerator(); + uint64_t D = Prob.getDenominator(); + uint64_t Res = (N * getBlockFreq(Src)) / D; + + assert(Res <= UINT32_MAX); + return (uint32_t) Res; + } + + /// incBlockFreq - Increase BB block frequency by FREQ. + /// + void incBlockFreq(BlockT *BB, uint32_t Freq) { + Freqs[BB] += Freq; + DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") += " << Freq + << " --> " << Freqs[BB] << "\n"); + } + + /// divBlockFreq - Divide BB block frequency by PROB. If Prob = 0 do nothing. + /// + void divBlockFreq(BlockT *BB, BranchProbability Prob) { + uint64_t N = Prob.getNumerator(); + assert(N && "Illegal division by zero!"); + uint64_t D = Prob.getDenominator(); + uint64_t Freq = (Freqs[BB] * D) / N; + + // Should we assert it? + if (Freq > UINT32_MAX) + Freq = UINT32_MAX; + + Freqs[BB] = (uint32_t) Freq; + DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") /= (" << Prob + << ") --> " << Freqs[BB] << "\n"); + } + + // All blocks in postorder. + std::vector POT; + + // Map Block -> Position in reverse-postorder list. + DenseMap RPO; + + // Cycle Probability for each bloch. + DenseMap CycleProb; + + // (reverse-)postorder traversal iterators. + typedef typename std::vector::iterator pot_iterator; + typedef typename std::vector::reverse_iterator rpot_iterator; + + pot_iterator pot_begin() { return POT.begin(); } + pot_iterator pot_end() { return POT.end(); } + + rpot_iterator rpot_begin() { return POT.rbegin(); } + rpot_iterator rpot_end() { return POT.rend(); } + + rpot_iterator rpot_at(BlockT *BB) { + rpot_iterator I = rpot_begin(); + unsigned idx = RPO[BB]; + assert(idx); + std::advance(I, idx - 1); + + assert(*I == BB); + return I; + } + + + /// isReachable - Returns if BB block is reachable from the entry. + /// + bool isReachable(BlockT *BB) { + return RPO.count(BB); + } + + /// isBackedge - Return if edge Src -> Dst is a backedge. + /// + bool isBackedge(BlockT *Src, BlockT *Dst) { + assert(isReachable(Src)); + assert(isReachable(Dst)); + + unsigned a = RPO[Src]; + unsigned b = RPO[Dst]; + + return a > b; + } + + /// getSingleBlockPred - return single BB block predecessor or NULL if + /// BB has none or more predecessors. + BlockT *getSingleBlockPred(BlockT *BB) { + typename GT::ChildIteratorType + PI = GraphTraits< Inverse >::child_begin(BB), + PE = GraphTraits< Inverse >::child_end(BB); + + if (PI == PE) + return 0; + + BlockT *Pred = *PI; + + ++PI; + if (PI != PE) + return 0; + + return Pred; + } + + void doBlock(BlockT *BB, BlockT *LoopHead, + SmallPtrSet &BlocksInLoop) { + + DEBUG(dbgs() << "doBlock(" << getBlockName(BB) << ")\n"); + setBlockFreq(BB, 0); + + if (BB == LoopHead) { + setBlockFreq(BB, START_FREQ); + return; + } + + if(BlockT *Pred = getSingleBlockPred(BB)) { + if (BlocksInLoop.count(Pred)) + setBlockFreq(BB, getEdgeFreq(Pred, BB)); + // TODO: else? irreducible, ignore it for now. + return; + } + + bool isInLoop = false; + bool isLoopHead = false; + + for (typename GT::ChildIteratorType + PI = GraphTraits< Inverse >::child_begin(BB), + PE = GraphTraits< Inverse >::child_end(BB); + PI != PE; ++PI) { + BlockT *Pred = *PI; + + if (isReachable(Pred) && isBackedge(Pred, BB)) { + isLoopHead = true; + } else if (BlocksInLoop.count(Pred)) { + incBlockFreq(BB, getEdgeFreq(Pred, BB)); + isInLoop = true; + } + // TODO: else? irreducible. + } + + if (!isInLoop) + return; + + if (!isLoopHead) + return; + + assert(START_FREQ >= CycleProb[BB]); + divBlockFreq(BB, BranchProbability(START_FREQ - CycleProb[BB], START_FREQ)); + } + + /// doLoop - Propagate block frequency down throught the loop. + void doLoop(BlockT *Head, BlockT *Tail) { + DEBUG(dbgs() << "doLoop(" << getBlockName(Head) << ", " + << getBlockName(Tail) << ")\n"); + + SmallPtrSet BlocksInLoop; + + for (rpot_iterator I = rpot_at(Head), E = rpot_end(); I != E; ++I) { + BlockT *BB = *I; + doBlock(BB, Head, BlocksInLoop); + + BlocksInLoop.insert(BB); + } + + // Compute loop's cyclic probability using backedges probabilities. + for (typename GT::ChildIteratorType + PI = GraphTraits< Inverse >::child_begin(Head), + PE = GraphTraits< Inverse >::child_end(Head); + PI != PE; ++PI) { + BlockT *Pred = *PI; + assert(Pred); + if (isReachable(Pred) && isBackedge(Pred, Head)) { + BranchProbability Prob = BPI->getBackEdgeProbability(Pred, Head); + uint64_t N = Prob.getNumerator(); + uint64_t D = Prob.getDenominator(); + uint64_t Res = (N * START_FREQ) / D; + + // CycleProb[Head] += getEdgeFreq(Pred, Head); + assert(Res <= UINT32_MAX); + CycleProb[Head] += (uint32_t) Res; + } + } + } + + + friend class BlockFrequency; + + void doFunction(FunctionT *fn, BlockProbInfoT *bpi) { + Fn = fn; + BPI = bpi; + + // Clear everything. + RPO.clear(); + POT.clear(); + CycleProb.clear(); + Freqs.clear(); + + BlockT *EntryBlock = fn->begin(); + + copy(po_begin(EntryBlock), po_end(EntryBlock), back_inserter(POT)); + + unsigned RPOidx = 0; + for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) { + BlockT *BB = *I; + RPO[BB] = ++RPOidx; + DEBUG(dbgs() << "RPO[" << getBlockName(BB) << "] = " << RPO[BB] << "\n"); + } + + // Travel over all blocks in postorder. + for (pot_iterator I = pot_begin(), E = pot_end(); I != E; ++I) { + BlockT *BB = *I; + BlockT *LastTail = 0; + DEBUG(dbgs() << "POT: " << getBlockName(BB) << "\n"); + + for (typename GT::ChildIteratorType + PI = GraphTraits< Inverse >::child_begin(BB), + PE = GraphTraits< Inverse >::child_end(BB); + PI != PE; ++PI) { + + BlockT *Pred = *PI; + if (isReachable(Pred) && isBackedge(Pred, BB) + && (!LastTail || RPO[Pred] > RPO[LastTail])) + LastTail = Pred; + } + + if (LastTail) + doLoop(BB, LastTail); + } + + // At the end assume the whole function as a loop, and travel over it once + // again. + doLoop(*(rpot_begin()), *(pot_begin())); + } + +public: + /// getBlockFreq - Return block frequency. Never return 0, value must be + /// positive. + uint32_t getBlockFreq(BlockT *BB) const { + typename DenseMap::const_iterator I = Freqs.find(BB); + if (I != Freqs.end()) + return I->second ? I->second : 1; + return 1; + } + + void print(raw_ostream &OS) const { + OS << "\n\n---- Block Freqs ----\n"; + for (typename FunctionT::iterator I = Fn->begin(), E = Fn->end(); I != E;) { + BlockT *BB = I++; + OS << " " << getBlockName(BB) << " = " << getBlockFreq(BB) << "\n"; + + for (typename GraphTraits::ChildIteratorType + SI = GraphTraits::child_begin(BB), + SE = GraphTraits::child_end(BB); SI != SE; ++SI) { + BlockT *Succ = *SI; + OS << " " << getBlockName(BB) << " -> " << getBlockName(Succ) + << " = " << getEdgeFreq(BB, Succ) << "\n"; + } + } + } + + void dump() const { + print(dbgs()); + } +}; + +} + +#endif diff --git a/lib/Analysis/BlockFrequency.cpp b/lib/Analysis/BlockFrequency.cpp new file mode 100644 index 00000000000..4b86d1db1f0 --- /dev/null +++ b/lib/Analysis/BlockFrequency.cpp @@ -0,0 +1,59 @@ +//=======-------- BlockFrequency.cpp - Block Frequency Analysis -------=======// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Loops should be simplified before this analysis. +// +//===----------------------------------------------------------------------===// + +#include "llvm/InitializePasses.h" +#include "llvm/Analysis/BlockFrequencyImpl.h" +#include "llvm/Analysis/BlockFrequency.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/Passes.h" +#include "llvm/Analysis/BranchProbabilityInfo.h" + +using namespace llvm; + +INITIALIZE_PASS_BEGIN(BlockFrequency, "block-freq", "Block Frequency Analysis", + true, true) +INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfo) +INITIALIZE_PASS_END(BlockFrequency, "block-freq", "Block Frequency Analysis", + true, true) + +char BlockFrequency::ID = 0; + + +BlockFrequency::BlockFrequency() : FunctionPass(ID) { + initializeBlockFrequencyPass(*PassRegistry::getPassRegistry()); + BFI = new BlockFrequencyImpl(); +} + +BlockFrequency::~BlockFrequency() { + delete BFI; +} + +void BlockFrequency::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + AU.setPreservesAll(); +} + +bool BlockFrequency::runOnFunction(Function &F) { + BranchProbabilityInfo &BPI = getAnalysis(); + BFI->doFunction(&F, &BPI); + return false; +} + +/// getblockFreq - Return block frequency. Never return 0, value must be +/// positive. Please note that initial frequency is equal to 1024. It means that +/// we should not rely on the value itself, but only on the comparison to the +/// other block frequencies. We do this to avoid using of floating points. +/// +uint32_t BlockFrequency::getBlockFreq(BasicBlock *BB) { + return BFI->getBlockFreq(BB); +} -- 2.11.0