1f289df2d9544bd3a0934651daa20e589544413baAndrew Trick//===-------------- lib/Support/BranchProbability.cpp -----------*- C++ -*-===// 2f289df2d9544bd3a0934651daa20e589544413baAndrew Trick// 3f289df2d9544bd3a0934651daa20e589544413baAndrew Trick// The LLVM Compiler Infrastructure 4f289df2d9544bd3a0934651daa20e589544413baAndrew Trick// 5f289df2d9544bd3a0934651daa20e589544413baAndrew Trick// This file is distributed under the University of Illinois Open Source 6f289df2d9544bd3a0934651daa20e589544413baAndrew Trick// License. See LICENSE.TXT for details. 7f289df2d9544bd3a0934651daa20e589544413baAndrew Trick// 8f289df2d9544bd3a0934651daa20e589544413baAndrew Trick//===----------------------------------------------------------------------===// 9f289df2d9544bd3a0934651daa20e589544413baAndrew Trick// 10f289df2d9544bd3a0934651daa20e589544413baAndrew Trick// This file implements Branch Probability class. 11f289df2d9544bd3a0934651daa20e589544413baAndrew Trick// 12f289df2d9544bd3a0934651daa20e589544413baAndrew Trick//===----------------------------------------------------------------------===// 13f289df2d9544bd3a0934651daa20e589544413baAndrew Trick 14f289df2d9544bd3a0934651daa20e589544413baAndrew Trick#include "llvm/Support/BranchProbability.h" 15f289df2d9544bd3a0934651daa20e589544413baAndrew Trick#include "llvm/Support/Debug.h" 1696f1d854036a13fd370a748a512931bd70d24064Benjamin Kramer#include "llvm/Support/Format.h" 17f289df2d9544bd3a0934651daa20e589544413baAndrew Trick#include "llvm/Support/raw_ostream.h" 18f289df2d9544bd3a0934651daa20e589544413baAndrew Trick 19f289df2d9544bd3a0934651daa20e589544413baAndrew Trickusing namespace llvm; 20f289df2d9544bd3a0934651daa20e589544413baAndrew Trick 21dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesraw_ostream &BranchProbability::print(raw_ostream &OS) const { 22dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return OS << N << " / " << D << " = " 23dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines << format("%g%%", ((double)N / D) * 100.0); 24f289df2d9544bd3a0934651daa20e589544413baAndrew Trick} 25f289df2d9544bd3a0934651daa20e589544413baAndrew Trick 26dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid BranchProbability::dump() const { print(dbgs()) << '\n'; } 27dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 28dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic uint64_t scale(uint64_t Num, uint32_t N, uint32_t D) { 29dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(D && "divide by 0"); 30dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 31dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Fast path for multiplying by 1.0. 32dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Num || D == N) 33dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Num; 34dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 35dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Split Num into upper and lower parts to multiply, then recombine. 36dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines uint64_t ProductHigh = (Num >> 32) * N; 37dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines uint64_t ProductLow = (Num & UINT32_MAX) * N; 38dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 39dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Split into 32-bit digits. 40dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines uint32_t Upper32 = ProductHigh >> 32; 41dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines uint32_t Lower32 = ProductLow & UINT32_MAX; 42dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines uint32_t Mid32Partial = ProductHigh & UINT32_MAX; 43dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines uint32_t Mid32 = Mid32Partial + (ProductLow >> 32); 44dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 45dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Carry. 46dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Upper32 += Mid32 < Mid32Partial; 47f289df2d9544bd3a0934651daa20e589544413baAndrew Trick 48dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Check for overflow. 49dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Upper32 >= D) 50dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return UINT64_MAX; 51dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 52dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines uint64_t Rem = (uint64_t(Upper32) << 32) | Mid32; 53dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines uint64_t UpperQ = Rem / D; 54dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 55dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Check for overflow. 56dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (UpperQ > UINT32_MAX) 57dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return UINT64_MAX; 58dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 59dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Rem = ((Rem % D) << 32) | Lower32; 60dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines uint64_t LowerQ = Rem / D; 61dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines uint64_t Q = (UpperQ << 32) + LowerQ; 62dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 63dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Check for overflow. 64dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Q < LowerQ ? UINT64_MAX : Q; 65dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 66f289df2d9544bd3a0934651daa20e589544413baAndrew Trick 67dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesuint64_t BranchProbability::scale(uint64_t Num) const { 68dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ::scale(Num, N, D); 69f289df2d9544bd3a0934651daa20e589544413baAndrew Trick} 70f289df2d9544bd3a0934651daa20e589544413baAndrew Trick 71dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesuint64_t BranchProbability::scaleByInverse(uint64_t Num) const { 72dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ::scale(Num, D, N); 73f289df2d9544bd3a0934651daa20e589544413baAndrew Trick} 74