1 //====--------------- lib/Support/BlockFrequency.cpp -----------*- C++ -*-====// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements Block Frequency class. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Support/BranchProbability.h" 15 #include "llvm/Support/BlockFrequency.h" 16 #include "llvm/Support/raw_ostream.h" 17 #include <cassert> 18 19 using namespace llvm; 20 21 namespace { 22 23 /// mult96bit - Multiply FREQ by N and store result in W array. 24 void mult96bit(uint64_t freq, uint32_t N, uint64_t W[2]) { 25 uint64_t u0 = freq & UINT32_MAX; 26 uint64_t u1 = freq >> 32; 27 28 // Represent 96-bit value as w[2]:w[1]:w[0]; 29 uint32_t w[3] = { 0, 0, 0 }; 30 31 uint64_t t = u0 * N; 32 uint64_t k = t >> 32; 33 w[0] = t; 34 t = u1 * N + k; 35 w[1] = t; 36 w[2] = t >> 32; 37 38 // W[1] - higher bits. 39 // W[0] - lower bits. 40 W[0] = w[0] + ((uint64_t) w[1] << 32); 41 W[1] = w[2]; 42 } 43 44 45 /// div96bit - Divide 96-bit value stored in W array by D. 46 /// Return 64-bit quotient, saturated to UINT64_MAX on overflow. 47 uint64_t div96bit(uint64_t W[2], uint32_t D) { 48 uint64_t y = W[0]; 49 uint64_t x = W[1]; 50 int i; 51 52 // This long division algorithm automatically saturates on overflow. 53 for (i = 1; i <= 64 && x; ++i) { 54 uint32_t t = (int)x >> 31; 55 x = (x << 1) | (y >> 63); 56 y = y << 1; 57 if ((x | t) >= D) { 58 x -= D; 59 ++y; 60 } 61 } 62 63 return y << (64 - i + 1); 64 } 65 66 } 67 68 void BlockFrequency::scale(uint32_t N, uint32_t D) { 69 assert(D != 0 && "Division by zero"); 70 71 // Calculate Frequency * N. 72 uint64_t MulLo = (Frequency & UINT32_MAX) * N; 73 uint64_t MulHi = (Frequency >> 32) * N; 74 uint64_t MulRes = (MulHi << 32) + MulLo; 75 76 // If the product fits in 64 bits, just use built-in division. 77 if (MulHi <= UINT32_MAX && MulRes <= MulLo) { 78 Frequency = MulRes / D; 79 return; 80 } 81 82 // Product overflowed, use 96-bit operations. 83 // 96-bit value represented as W[1]:W[0]. 84 uint64_t W[2]; 85 mult96bit(Frequency, N, W); 86 Frequency = div96bit(W, D); 87 return; 88 } 89 90 BlockFrequency &BlockFrequency::operator*=(const BranchProbability &Prob) { 91 scale(Prob.getNumerator(), Prob.getDenominator()); 92 return *this; 93 } 94 95 const BlockFrequency 96 BlockFrequency::operator*(const BranchProbability &Prob) const { 97 BlockFrequency Freq(Frequency); 98 Freq *= Prob; 99 return Freq; 100 } 101 102 BlockFrequency &BlockFrequency::operator/=(const BranchProbability &Prob) { 103 scale(Prob.getDenominator(), Prob.getNumerator()); 104 return *this; 105 } 106 107 BlockFrequency BlockFrequency::operator/(const BranchProbability &Prob) const { 108 BlockFrequency Freq(Frequency); 109 Freq /= Prob; 110 return Freq; 111 } 112 113 BlockFrequency &BlockFrequency::operator+=(const BlockFrequency &Freq) { 114 uint64_t Before = Freq.Frequency; 115 Frequency += Freq.Frequency; 116 117 // If overflow, set frequency to the maximum value. 118 if (Frequency < Before) 119 Frequency = UINT64_MAX; 120 121 return *this; 122 } 123 124 const BlockFrequency 125 BlockFrequency::operator+(const BlockFrequency &Prob) const { 126 BlockFrequency Freq(Frequency); 127 Freq += Prob; 128 return Freq; 129 } 130 131 void BlockFrequency::print(raw_ostream &OS) const { 132 // Convert fixed-point number to decimal. 133 OS << Frequency / getEntryFrequency() << "."; 134 uint64_t Rem = Frequency % getEntryFrequency(); 135 uint64_t Eps = 1; 136 do { 137 Rem *= 10; 138 Eps *= 10; 139 OS << Rem / getEntryFrequency(); 140 Rem = Rem % getEntryFrequency(); 141 } while (Rem >= Eps/2); 142 } 143 144 namespace llvm { 145 146 raw_ostream &operator<<(raw_ostream &OS, const BlockFrequency &Freq) { 147 Freq.print(OS); 148 return OS; 149 } 150 151 } 152