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