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 is really a 64-bit division. 51 if (!x) 52 return y / D; 53 54 // This long division algorithm automatically saturates on overflow. 55 for (i = 0; i < 64 && x; ++i) { 56 uint32_t t = -((x >> 31) & 1); // Splat bit 31 to bits 0-31. 57 x = (x << 1) | (y >> 63); 58 y = y << 1; 59 if ((x | t) >= D) { 60 x -= D; 61 ++y; 62 } 63 } 64 65 return y << (64 - i); 66 } 67 68 69 void BlockFrequency::scale(uint32_t N, uint32_t D) { 70 assert(D != 0 && "Division by zero"); 71 72 // Calculate Frequency * N. 73 uint64_t MulLo = (Frequency & UINT32_MAX) * N; 74 uint64_t MulHi = (Frequency >> 32) * N; 75 uint64_t MulRes = (MulHi << 32) + MulLo; 76 77 // If the product fits in 64 bits, just use built-in division. 78 if (MulHi <= UINT32_MAX && MulRes <= MulLo) { 79 Frequency = MulRes / D; 80 return; 81 } 82 83 // Product overflowed, use 96-bit operations. 84 // 96-bit value represented as W[1]:W[0]. 85 uint64_t W[2]; 86 mult96bit(Frequency, N, W); 87 Frequency = div96bit(W, D); 88 return; 89 } 90 91 BlockFrequency &BlockFrequency::operator*=(const BranchProbability &Prob) { 92 scale(Prob.getNumerator(), Prob.getDenominator()); 93 return *this; 94 } 95 96 const BlockFrequency 97 BlockFrequency::operator*(const BranchProbability &Prob) const { 98 BlockFrequency Freq(Frequency); 99 Freq *= Prob; 100 return Freq; 101 } 102 103 BlockFrequency &BlockFrequency::operator/=(const BranchProbability &Prob) { 104 scale(Prob.getDenominator(), Prob.getNumerator()); 105 return *this; 106 } 107 108 BlockFrequency BlockFrequency::operator/(const BranchProbability &Prob) const { 109 BlockFrequency Freq(Frequency); 110 Freq /= Prob; 111 return Freq; 112 } 113 114 BlockFrequency &BlockFrequency::operator+=(const BlockFrequency &Freq) { 115 uint64_t Before = Freq.Frequency; 116 Frequency += Freq.Frequency; 117 118 // If overflow, set frequency to the maximum value. 119 if (Frequency < Before) 120 Frequency = UINT64_MAX; 121 122 return *this; 123 } 124 125 const BlockFrequency 126 BlockFrequency::operator+(const BlockFrequency &Prob) const { 127 BlockFrequency Freq(Frequency); 128 Freq += Prob; 129 return Freq; 130 } 131 132 void BlockFrequency::print(raw_ostream &OS) const { 133 // Convert fixed-point number to decimal. 134 OS << Frequency / getEntryFrequency() << "."; 135 uint64_t Rem = Frequency % getEntryFrequency(); 136 uint64_t Eps = 1; 137 do { 138 Rem *= 10; 139 Eps *= 10; 140 OS << Rem / getEntryFrequency(); 141 Rem = Rem % getEntryFrequency(); 142 } while (Rem >= Eps/2); 143 } 144 145 namespace llvm { 146 147 raw_ostream &operator<<(raw_ostream &OS, const BlockFrequency &Freq) { 148 Freq.print(OS); 149 return OS; 150 } 151 152 } 153