119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===---- BlockFrequencyImpl.h - Machine Block Frequency Implementation ---===// 219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The LLVM Compiler Infrastructure 419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file is distributed under the University of Illinois Open Source 619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// License. See LICENSE.TXT for details. 719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Shared implementation of BlockFrequency for IR and Machine Instructions. 1119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 1319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#ifndef LLVM_ANALYSIS_BLOCKFREQUENCYIMPL_H 1519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#define LLVM_ANALYSIS_BLOCKFREQUENCYIMPL_H 1619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/BasicBlock.h" 1819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/DenseMap.h" 1919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/PostOrderIterator.h" 2019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineBasicBlock.h" 2119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineFunction.h" 2219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/BlockFrequency.h" 2319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/BranchProbability.h" 2419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/Debug.h" 2519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/raw_ostream.h" 2619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include <vector> 2719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include <sstream> 2819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include <string> 2919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace llvm { 3119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass BlockFrequencyInfo; 3419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass MachineBlockFrequencyInfo; 3519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// BlockFrequencyImpl implements block frequency algorithm for IR and 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Machine Instructions. Algorithm starts with value 1024 (START_FREQ) 3819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// for the entry block and then propagates frequencies using branch weights 3919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// from (Machine)BranchProbabilityInfo. LoopInfo is not required because 4019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// algorithm can find "backedges" by itself. 4119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate<class BlockT, class FunctionT, class BlockProbInfoT> 4219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass BlockFrequencyImpl { 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DenseMap<BlockT *, BlockFrequency> Freqs; 4519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockProbInfoT *BPI; 4719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman FunctionT *Fn; 4919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef GraphTraits< Inverse<BlockT *> > GT; 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const uint32_t EntryFreq; 5319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::string getBlockName(BasicBlock *BB) const { 5519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return BB->getNameStr(); 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 5719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::string getBlockName(MachineBasicBlock *MBB) const { 5919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::stringstream ss; 6019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ss << "BB#" << MBB->getNumber(); 6119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const BasicBlock *BB = MBB->getBasicBlock()) 6319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ss << " derived from LLVM BB " << BB->getNameStr(); 6419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return ss.str(); 6619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 6719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void setBlockFreq(BlockT *BB, BlockFrequency Freq) { 6919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Freqs[BB] = Freq; 7019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") = " << Freq << "\n"); 7119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 7219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// getEdgeFreq - Return edge frequency based on SRC frequency and Src -> Dst 7419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// edge probability. 7519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockFrequency getEdgeFreq(BlockT *Src, BlockT *Dst) const { 7619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BranchProbability Prob = BPI->getEdgeProbability(Src, Dst); 7719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return getBlockFreq(Src) * Prob; 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 7919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 8019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// incBlockFreq - Increase BB block frequency by FREQ. 8119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 8219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void incBlockFreq(BlockT *BB, BlockFrequency Freq) { 8319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Freqs[BB] += Freq; 8419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") += " << Freq 8519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << " --> " << Freqs[BB] << "\n"); 8619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 8719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 8819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// divBlockFreq - Divide BB block frequency by PROB. If Prob = 0 do nothing. 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 9019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void divBlockFreq(BlockT *BB, BranchProbability Prob) { 9119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint64_t N = Prob.getNumerator(); 9219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(N && "Illegal division by zero!"); 9319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint64_t D = Prob.getDenominator(); 9419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint64_t Freq = (Freqs[BB].getFrequency() * D) / N; 9519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Should we assert it? 9719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Freq > UINT32_MAX) 9819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Freq = UINT32_MAX; 9919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Freqs[BB] = BlockFrequency(Freq); 10119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") /= (" << Prob 10219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << ") --> " << Freqs[BB] << "\n"); 10319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 10419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // All blocks in postorder. 10619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::vector<BlockT *> POT; 10719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Map Block -> Position in reverse-postorder list. 10919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DenseMap<BlockT *, unsigned> RPO; 11019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Cycle Probability for each bloch. 11219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DenseMap<BlockT *, uint32_t> CycleProb; 11319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // (reverse-)postorder traversal iterators. 11519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef typename std::vector<BlockT *>::iterator pot_iterator; 11619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef typename std::vector<BlockT *>::reverse_iterator rpot_iterator; 11719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman pot_iterator pot_begin() { return POT.begin(); } 11919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman pot_iterator pot_end() { return POT.end(); } 12019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rpot_iterator rpot_begin() { return POT.rbegin(); } 12219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rpot_iterator rpot_end() { return POT.rend(); } 12319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rpot_iterator rpot_at(BlockT *BB) { 12519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rpot_iterator I = rpot_begin(); 12619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned idx = RPO[BB]; 12719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(idx); 12819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::advance(I, idx - 1); 12919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(*I == BB); 13119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return I; 13219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 13319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// isReachable - Returns if BB block is reachable from the entry. 13619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 13719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isReachable(BlockT *BB) { 13819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return RPO.count(BB); 13919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 14019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// isBackedge - Return if edge Src -> Dst is a backedge. 14219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 14319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isBackedge(BlockT *Src, BlockT *Dst) { 14419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(isReachable(Src)); 14519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(isReachable(Dst)); 14619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned a = RPO[Src]; 14819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned b = RPO[Dst]; 14919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return a >= b; 15119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 15219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// getSingleBlockPred - return single BB block predecessor or NULL if 15419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// BB has none or more predecessors. 15519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockT *getSingleBlockPred(BlockT *BB) { 15619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typename GT::ChildIteratorType 15719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB), 15819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PE = GraphTraits< Inverse<BlockT *> >::child_end(BB); 15919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (PI == PE) 16119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return 0; 16219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockT *Pred = *PI; 16419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++PI; 16619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (PI != PE) 16719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return 0; 16819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Pred; 17019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 17119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 17219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void doBlock(BlockT *BB, BlockT *LoopHead, 17319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallPtrSet<BlockT *, 8> &BlocksInLoop) { 17419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 17519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "doBlock(" << getBlockName(BB) << ")\n"); 17619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setBlockFreq(BB, 0); 17719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 17819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BB == LoopHead) { 17919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setBlockFreq(BB, EntryFreq); 18019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 18119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 18219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 18319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if(BlockT *Pred = getSingleBlockPred(BB)) { 18419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BlocksInLoop.count(Pred)) 18519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setBlockFreq(BB, getEdgeFreq(Pred, BB)); 18619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // TODO: else? irreducible, ignore it for now. 18719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 18819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 18919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isInLoop = false; 19119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isLoopHead = false; 19219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (typename GT::ChildIteratorType 19419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB), 19519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PE = GraphTraits< Inverse<BlockT *> >::child_end(BB); 19619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PI != PE; ++PI) { 19719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockT *Pred = *PI; 19819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isReachable(Pred) && isBackedge(Pred, BB)) { 20019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isLoopHead = true; 20119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (BlocksInLoop.count(Pred)) { 20219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman incBlockFreq(BB, getEdgeFreq(Pred, BB)); 20319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isInLoop = true; 20419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 20519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // TODO: else? irreducible. 20619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 20719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 20819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!isInLoop) 20919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 21019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 21119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!isLoopHead) 21219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 21319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 21419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(EntryFreq >= CycleProb[BB]); 21519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint32_t CProb = CycleProb[BB]; 21619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint32_t Numerator = EntryFreq - CProb ? EntryFreq - CProb : 1; 21719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman divBlockFreq(BB, BranchProbability(Numerator, EntryFreq)); 21819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 21919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 22019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// doLoop - Propagate block frequency down throught the loop. 22119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void doLoop(BlockT *Head, BlockT *Tail) { 22219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "doLoop(" << getBlockName(Head) << ", " 22319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << getBlockName(Tail) << ")\n"); 22419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 22519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallPtrSet<BlockT *, 8> BlocksInLoop; 22619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 22719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (rpot_iterator I = rpot_at(Head), E = rpot_at(Tail); ; ++I) { 22819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockT *BB = *I; 22919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman doBlock(BB, Head, BlocksInLoop); 23019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 23119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlocksInLoop.insert(BB); 23219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I == E) 23319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 23419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 23519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 23619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Compute loop's cyclic probability using backedges probabilities. 23719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (typename GT::ChildIteratorType 23819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PI = GraphTraits< Inverse<BlockT *> >::child_begin(Head), 23919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PE = GraphTraits< Inverse<BlockT *> >::child_end(Head); 24019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PI != PE; ++PI) { 24119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockT *Pred = *PI; 24219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(Pred); 24319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isReachable(Pred) && isBackedge(Pred, Head)) { 24419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint64_t N = getEdgeFreq(Pred, Head).getFrequency(); 24519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint64_t D = getBlockFreq(Head).getFrequency(); 24619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(N <= EntryFreq && "Backedge frequency must be <= EntryFreq!"); 24719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint64_t Res = (N * EntryFreq) / D; 24819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 24919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(Res <= UINT32_MAX); 25019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CycleProb[Head] += (uint32_t) Res; 25119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << " CycleProb[" << getBlockName(Head) << "] += " << Res 25219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << " --> " << CycleProb[Head] << "\n"); 25319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 25419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 25519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 25619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 25719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman friend class BlockFrequencyInfo; 25819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman friend class MachineBlockFrequencyInfo; 25919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 26019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockFrequencyImpl() : EntryFreq(BlockFrequency::getEntryFrequency()) { } 26119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 26219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void doFunction(FunctionT *fn, BlockProbInfoT *bpi) { 26319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Fn = fn; 26419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BPI = bpi; 26519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 26619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Clear everything. 26719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RPO.clear(); 26819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman POT.clear(); 26919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CycleProb.clear(); 27019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Freqs.clear(); 27119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 27219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockT *EntryBlock = fn->begin(); 27319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 27419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman copy(po_begin(EntryBlock), po_end(EntryBlock), back_inserter(POT)); 27519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 27619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned RPOidx = 0; 27719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) { 27819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockT *BB = *I; 27919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RPO[BB] = ++RPOidx; 28019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "RPO[" << getBlockName(BB) << "] = " << RPO[BB] << "\n"); 28119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 28219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 28319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Travel over all blocks in postorder. 28419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (pot_iterator I = pot_begin(), E = pot_end(); I != E; ++I) { 28519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockT *BB = *I; 28619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockT *LastTail = 0; 28719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "POT: " << getBlockName(BB) << "\n"); 28819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 28919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (typename GT::ChildIteratorType 29019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB), 29119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PE = GraphTraits< Inverse<BlockT *> >::child_end(BB); 29219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PI != PE; ++PI) { 29319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 29419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockT *Pred = *PI; 29519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isReachable(Pred) && isBackedge(Pred, BB) 29619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman && (!LastTail || RPO[Pred] > RPO[LastTail])) 29719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LastTail = Pred; 29819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 29919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LastTail) 30119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman doLoop(BB, LastTail); 30219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 30319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // At the end assume the whole function as a loop, and travel over it once 30519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // again. 30619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman doLoop(*(rpot_begin()), *(pot_begin())); 30719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 30819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanpublic: 31019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// getBlockFreq - Return block frequency. Return 0 if we don't have it. 31119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockFrequency getBlockFreq(BlockT *BB) const { 31219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typename DenseMap<BlockT *, BlockFrequency>::const_iterator I = Freqs.find(BB); 31319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I != Freqs.end()) 31419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return I->second; 31519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return 0; 31619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 31719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 31819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void print(raw_ostream &OS) const { 31919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << "\n\n---- Block Freqs ----\n"; 32019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (typename FunctionT::iterator I = Fn->begin(), E = Fn->end(); I != E;) { 32119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockT *BB = I++; 32219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << " " << getBlockName(BB) << " = " << getBlockFreq(BB) << "\n"; 32319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 32419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (typename GraphTraits<BlockT *>::ChildIteratorType 32519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SI = GraphTraits<BlockT *>::child_begin(BB), 32619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SE = GraphTraits<BlockT *>::child_end(BB); SI != SE; ++SI) { 32719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockT *Succ = *SI; 32819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << " " << getBlockName(BB) << " -> " << getBlockName(Succ) 32919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << " = " << getEdgeFreq(BB, Succ) << "\n"; 33019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 33119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 33219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 33319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 33419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void dump() const { 33519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman print(dbgs()); 33619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 33719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 33819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 33919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 34019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 34119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#endif 342