Home | History | Annotate | Download | only in Support 
      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   uint32_t n = Prob.getNumerator();
     69   uint32_t d = Prob.getDenominator();
     70 
     71   assert(n <= d && "Probability must be less or equal to 1.");
     72 
     73   // If we can overflow use 96-bit operations.
     74   if (n > 0 && Frequency > UINT64_MAX / n) {
     75     // 96-bit value represented as W[1]:W[0].
     76     uint64_t W[2];
     77 
     78     // Probability is less or equal to 1 which means that results must fit
     79     // 64-bit.
     80     mult96bit(Frequency, n, W);
     81     Frequency = div96bit(W, d);
     82     return *this;
     83   }
     84 
     85   Frequency *= n;
     86   Frequency /= d;
     87   return *this;
     88 }
     89 
     90 const BlockFrequency
     91 BlockFrequency::operator*(const BranchProbability &Prob) const {
     92   BlockFrequency Freq(Frequency);
     93   Freq *= Prob;
     94   return Freq;
     95 }
     96 
     97 BlockFrequency &BlockFrequency::operator+=(const BlockFrequency &Freq) {
     98   uint64_t Before = Freq.Frequency;
     99   Frequency += Freq.Frequency;
    100 
    101   // If overflow, set frequency to the maximum value.
    102   if (Frequency < Before)
    103     Frequency = UINT64_MAX;
    104 
    105   return *this;
    106 }
    107 
    108 const BlockFrequency
    109 BlockFrequency::operator+(const BlockFrequency &Prob) const {
    110   BlockFrequency Freq(Frequency);
    111   Freq += Prob;
    112   return Freq;
    113 }
    114 
    115 void BlockFrequency::print(raw_ostream &OS) const {
    116   OS << Frequency;
    117 }
    118 
    119 namespace llvm {
    120 
    121 raw_ostream &operator<<(raw_ostream &OS, const BlockFrequency &Freq) {
    122   Freq.print(OS);
    123   return OS;
    124 }
    125 
    126 }
    127