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 /// mult96bit - Multiply FREQ by N and store result in W array. 22 void BlockFrequency::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 /// div96bit - Divide 96-bit value stored in W array by D. Return 64-bit frequency. 44 uint64_t BlockFrequency::div96bit(uint64_t W[2], uint32_t D) { 45 uint64_t y = W[0]; 46 uint64_t x = W[1]; 47 48 for (int i = 1; i <= 64; ++i) { 49 uint32_t t = (int)x >> 31; 50 x = (x << 1) | (y >> 63); 51 y = y << 1; 52 if ((x | t) >= D) { 53 x -= D; 54 ++y; 55 } 56 } 57 58 return y; 59 } 60 61 BlockFrequency &BlockFrequency::operator*=(const BranchProbability &Prob) { 62 uint32_t n = Prob.getNumerator(); 63 uint32_t d = Prob.getDenominator(); 64 65 assert(n <= d && "Probability must be less or equal to 1."); 66 67 // If we can overflow use 96-bit operations. 68 if (n > 0 && Frequency > UINT64_MAX / n) { 69 // 96-bit value represented as W[1]:W[0]. 70 uint64_t W[2]; 71 72 // Probability is less or equal to 1 which means that results must fit 73 // 64-bit. 74 mult96bit(Frequency, n, W); 75 Frequency = div96bit(W, d); 76 return *this; 77 } 78 79 Frequency *= n; 80 Frequency /= d; 81 return *this; 82 } 83 84 const BlockFrequency 85 BlockFrequency::operator*(const BranchProbability &Prob) const { 86 BlockFrequency Freq(Frequency); 87 Freq *= Prob; 88 return Freq; 89 } 90 91 BlockFrequency &BlockFrequency::operator+=(const BlockFrequency &Freq) { 92 uint64_t Before = Freq.Frequency; 93 Frequency += Freq.Frequency; 94 95 // If overflow, set frequency to the maximum value. 96 if (Frequency < Before) 97 Frequency = UINT64_MAX; 98 99 return *this; 100 } 101 102 const BlockFrequency 103 BlockFrequency::operator+(const BlockFrequency &Prob) const { 104 BlockFrequency Freq(Frequency); 105 Freq += Prob; 106 return Freq; 107 } 108 109 void BlockFrequency::print(raw_ostream &OS) const { 110 OS << Frequency; 111 } 112 113 namespace llvm { 114 115 raw_ostream &operator<<(raw_ostream &OS, const BlockFrequency &Freq) { 116 Freq.print(OS); 117 return OS; 118 } 119 120 } 121