BlockFrequency.cpp revision 234353
1226584Sdim//====--------------- lib/Support/BlockFrequency.cpp -----------*- C++ -*-====// 2226584Sdim// 3226584Sdim// The LLVM Compiler Infrastructure 4226584Sdim// 5226584Sdim// This file is distributed under the University of Illinois Open Source 6226584Sdim// License. See LICENSE.TXT for details. 7226584Sdim// 8226584Sdim//===----------------------------------------------------------------------===// 9226584Sdim// 10226584Sdim// This file implements Block Frequency class. 11226584Sdim// 12226584Sdim//===----------------------------------------------------------------------===// 13226584Sdim 14226584Sdim#include "llvm/Support/BranchProbability.h" 15226584Sdim#include "llvm/Support/BlockFrequency.h" 16226584Sdim#include "llvm/Support/raw_ostream.h" 17226584Sdim#include <cassert> 18226584Sdim 19226584Sdimusing namespace llvm; 20226584Sdim 21226584Sdimnamespace { 22226584Sdim 23226584Sdim/// mult96bit - Multiply FREQ by N and store result in W array. 24226584Sdimvoid mult96bit(uint64_t freq, uint32_t N, uint64_t W[2]) { 25226584Sdim uint64_t u0 = freq & UINT32_MAX; 26226584Sdim uint64_t u1 = freq >> 32; 27226584Sdim 28226584Sdim // Represent 96-bit value as w[2]:w[1]:w[0]; 29226584Sdim uint32_t w[3] = { 0, 0, 0 }; 30226584Sdim 31226584Sdim uint64_t t = u0 * N; 32226584Sdim uint64_t k = t >> 32; 33226584Sdim w[0] = t; 34226584Sdim t = u1 * N + k; 35226584Sdim w[1] = t; 36226584Sdim w[2] = t >> 32; 37226584Sdim 38226584Sdim // W[1] - higher bits. 39226584Sdim // W[0] - lower bits. 40226584Sdim W[0] = w[0] + ((uint64_t) w[1] << 32); 41226584Sdim W[1] = w[2]; 42226584Sdim} 43226584Sdim 44226584Sdim 45226584Sdim/// div96bit - Divide 96-bit value stored in W array by D. Return 64-bit frequency. 46226584Sdimuint64_t div96bit(uint64_t W[2], uint32_t D) { 47226584Sdim uint64_t y = W[0]; 48226584Sdim uint64_t x = W[1]; 49226584Sdim int i; 50226584Sdim 51226584Sdim for (i = 1; i <= 64 && x; ++i) { 52226584Sdim uint32_t t = (int)x >> 31; 53226584Sdim x = (x << 1) | (y >> 63); 54226584Sdim y = y << 1; 55226584Sdim if ((x | t) >= D) { 56226584Sdim x -= D; 57226584Sdim ++y; 58226584Sdim } 59226584Sdim } 60226584Sdim 61226584Sdim return y << (64 - i + 1); 62226584Sdim} 63226584Sdim 64226584Sdim} 65226584Sdim 66226584Sdim 67226584SdimBlockFrequency &BlockFrequency::operator*=(const BranchProbability &Prob) { 68226584Sdim uint32_t n = Prob.getNumerator(); 69226584Sdim uint32_t d = Prob.getDenominator(); 70226584Sdim 71226584Sdim assert(n <= d && "Probability must be less or equal to 1."); 72226584Sdim 73234353Sdim // Calculate Frequency * n. 74234353Sdim uint64_t mulLo = (Frequency & UINT32_MAX) * n; 75234353Sdim uint64_t mulHi = (Frequency >> 32) * n; 76234353Sdim uint64_t mulRes = (mulHi << 32) + mulLo; 77234353Sdim 78234353Sdim // If there was overflow use 96-bit operations. 79234353Sdim if (mulHi > UINT32_MAX || mulRes < mulLo) { 80226584Sdim // 96-bit value represented as W[1]:W[0]. 81226584Sdim uint64_t W[2]; 82226584Sdim 83226584Sdim // Probability is less or equal to 1 which means that results must fit 84226584Sdim // 64-bit. 85226584Sdim mult96bit(Frequency, n, W); 86226584Sdim Frequency = div96bit(W, d); 87226584Sdim return *this; 88226584Sdim } 89226584Sdim 90234353Sdim Frequency = mulRes / d; 91226584Sdim return *this; 92226584Sdim} 93226584Sdim 94226584Sdimconst BlockFrequency 95226584SdimBlockFrequency::operator*(const BranchProbability &Prob) const { 96226584Sdim BlockFrequency Freq(Frequency); 97226584Sdim Freq *= Prob; 98226584Sdim return Freq; 99226584Sdim} 100226584Sdim 101226584SdimBlockFrequency &BlockFrequency::operator+=(const BlockFrequency &Freq) { 102226584Sdim uint64_t Before = Freq.Frequency; 103226584Sdim Frequency += Freq.Frequency; 104226584Sdim 105226584Sdim // If overflow, set frequency to the maximum value. 106226584Sdim if (Frequency < Before) 107226584Sdim Frequency = UINT64_MAX; 108226584Sdim 109226584Sdim return *this; 110226584Sdim} 111226584Sdim 112226584Sdimconst BlockFrequency 113226584SdimBlockFrequency::operator+(const BlockFrequency &Prob) const { 114226584Sdim BlockFrequency Freq(Frequency); 115226584Sdim Freq += Prob; 116226584Sdim return Freq; 117226584Sdim} 118226584Sdim 119226584Sdimvoid BlockFrequency::print(raw_ostream &OS) const { 120226584Sdim OS << Frequency; 121226584Sdim} 122226584Sdim 123226584Sdimnamespace llvm { 124226584Sdim 125226584Sdimraw_ostream &operator<<(raw_ostream &OS, const BlockFrequency &Freq) { 126226584Sdim Freq.print(OS); 127226584Sdim return OS; 128226584Sdim} 129226584Sdim 130226584Sdim} 131