BranchProbability.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f 
1//===-------------- lib/Support/BranchProbability.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 Branch Probability class.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Support/BranchProbability.h"
15#include "llvm/Support/Debug.h"
16#include "llvm/Support/Format.h"
17#include "llvm/Support/raw_ostream.h"
18
19using namespace llvm;
20
21raw_ostream &BranchProbability::print(raw_ostream &OS) const {
22  return OS << N << " / " << D << " = "
23            << format("%g%%", ((double)N / D) * 100.0);
24}
25
26void BranchProbability::dump() const { print(dbgs()) << '\n'; }
27
28static uint64_t scale(uint64_t Num, uint32_t N, uint32_t D) {
29  assert(D && "divide by 0");
30
31  // Fast path for multiplying by 1.0.
32  if (!Num || D == N)
33    return Num;
34
35  // Split Num into upper and lower parts to multiply, then recombine.
36  uint64_t ProductHigh = (Num >> 32) * N;
37  uint64_t ProductLow = (Num & UINT32_MAX) * N;
38
39  // Split into 32-bit digits.
40  uint32_t Upper32 = ProductHigh >> 32;
41  uint32_t Lower32 = ProductLow & UINT32_MAX;
42  uint32_t Mid32Partial = ProductHigh & UINT32_MAX;
43  uint32_t Mid32 = Mid32Partial + (ProductLow >> 32);
44
45  // Carry.
46  Upper32 += Mid32 < Mid32Partial;
47
48  // Check for overflow.
49  if (Upper32 >= D)
50    return UINT64_MAX;
51
52  uint64_t Rem = (uint64_t(Upper32) << 32) | Mid32;
53  uint64_t UpperQ = Rem / D;
54
55  // Check for overflow.
56  if (UpperQ > UINT32_MAX)
57    return UINT64_MAX;
58
59  Rem = ((Rem % D) << 32) | Lower32;
60  uint64_t LowerQ = Rem / D;
61  uint64_t Q = (UpperQ << 32) + LowerQ;
62
63  // Check for overflow.
64  return Q < LowerQ ? UINT64_MAX : Q;
65}
66
67uint64_t BranchProbability::scale(uint64_t Num) const {
68  return ::scale(Num, N, D);
69}
70
71uint64_t BranchProbability::scaleByInverse(uint64_t Num) const {
72  return ::scale(Num, D, N);
73}
74