lib/Support/BlockFrequency.cpp

   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 }