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. Return 64-bit frequency. 46 uint64_t div96bit(uint64_t W[2], uint32_t D) { 47 uint64_t y = W[0]; 48 uint64_t x = W[1]; 49 int i; 50 51 for (i = 1; 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 + 1); 62 } 63 64 } 65 66 67 BlockFrequency &BlockFrequency::operator*=(const BranchProbability &Prob) { 68 if (Frequency == 0) 69 return *this; 70 71 uint32_t n = Prob.getNumerator(); 72 uint32_t d = Prob.getDenominator(); 73 74 assert(n <= d && "Probability must be less or equal to 1."); 75 76 // Calculate Frequency * n. 77 uint64_t mulLo = (Frequency & UINT32_MAX) * n; 78 uint64_t mulHi = (Frequency >> 32) * n; 79 uint64_t mulRes = (mulHi << 32) + mulLo; 80 81 // If there was overflow use 96-bit operations. 82 if (mulHi > UINT32_MAX || mulRes < mulLo) { 83 // 96-bit value represented as W[1]:W[0]. 84 uint64_t W[2]; 85 86 // Probability is less or equal to 1 which means that results must fit 87 // 64-bit. 88 mult96bit(Frequency, n, W); 89 Frequency = div96bit(W, d); 90 } else { 91 // Fast case. 92 Frequency = mulRes / d; 93 } 94 95 // Limit the result to 1; 0 is a sentinel value. This keeps BlockFrequencyInfo 96 // from getting stuck at zero frequencies just because a value became too 97 // small to be represented as a BlockFrequency. 98 Frequency = (n == 0 || Frequency != 0) ? Frequency : 1; 99 return *this; 100 } 101 102 const BlockFrequency 103 BlockFrequency::operator*(const BranchProbability &Prob) const { 104 BlockFrequency Freq(Frequency); 105 Freq *= Prob; 106 return Freq; 107 } 108 109 BlockFrequency &BlockFrequency::operator+=(const BlockFrequency &Freq) { 110 uint64_t Before = Freq.Frequency; 111 Frequency += Freq.Frequency; 112 113 // If overflow, set frequency to the maximum value. 114 if (Frequency < Before) 115 Frequency = UINT64_MAX; 116 117 return *this; 118 } 119 120 const BlockFrequency 121 BlockFrequency::operator+(const BlockFrequency &Prob) const { 122 BlockFrequency Freq(Frequency); 123 Freq += Prob; 124 return Freq; 125 } 126 127 void BlockFrequency::print(raw_ostream &OS) const { 128 OS << Frequency; 129 } 130 131 namespace llvm { 132 133 raw_ostream &operator<<(raw_ostream &OS, const BlockFrequency &Freq) { 134 Freq.print(OS); 135 return OS; 136 } 137 138 } 139