[ThinLTO] Represent relative BF using a scaled representation .

[eraman]

Summary

The current integer representation of relative block frequency prevents
representing relative block frequencies below 1. This change uses a 8 of
the 29 bits to represent the decimal part by using a fixed scale of -8.

[davidxl]

include/llvm/IR/ModuleSummaryIndex.h

63 ↗

(On Diff #135116)

Document that it is RelativeBlockFrequency scaled by 2^8

Also should all the uses of RelBlockFreq scale it back?

65 ↗

(On Diff #135116)

Should this be scaled up too?

86 ↗

(On Diff #135116)

EntryFreq can be zero.

[eraman]

include/llvm/IR/ModuleSummaryIndex.h

63 ↗

(On Diff #135116)

Documented.

Yes, users should scale it back. In a separate patch, I will add a method to get this value as a ScaledNumber or uint64_t so that the users don't have to explicitly scale them

65 ↗

(On Diff #135116)

No, this is just the max value of the digits in the 29 bit bit-field.

86 ↗

(On Diff #135116)

Somehow missed this in refactoring.

[eraman]

Address review comments.

[davidxl]

include/llvm/IR/ModuleSummaryIndex.h

65 ↗

(On Diff #135116)

then the 'min' function here Sum = std::min(Sum, uint64_t(MaxRelBlockFreq)); should use a scaled MaxRelBlockFreq, right?

[eraman]

include/llvm/IR/ModuleSummaryIndex.h

65 ↗

(On Diff #135116)

No. The intent is to use a max of 29 bits including the integer and decimal(fractional) bits. Since I use a scale of 8, 8 bits will be used to represent values below 1 and I can use only 21 bits to represent the integral part.

[davidxl]

LGTM

llvm/trunk/include/llvm/IR/ModuleSummaryIndex.h

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/MathExtras.h"
+#include "llvm/Support/ScaledNumber.h"
 #include <algorithm>
 #include <array>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <map>
 #include <memory>
 #include <set>
enum class HotnessType : uint8_t {
     None = 2,
     Hot = 3,
     Critical = 4
   };
 
   // The size of the bit-field might need to be adjusted if more values are
   // added to HotnessType enum.
   uint32_t Hotness : 3;
+
+  /// The value stored in RelBlockFreq has to be interpreted as the digits of
+  /// a scaled number with a scale of \p -ScaleShift.
   uint32_t RelBlockFreq : 29;
+  static constexpr int32_t ScaleShift = 8;
   static constexpr uint64_t MaxRelBlockFreq = (1 << 29) - 1;
 
   CalleeInfo()
       : Hotness(static_cast<uint32_t>(HotnessType::Unknown)), RelBlockFreq(0) {}
   explicit CalleeInfo(HotnessType Hotness, uint64_t RelBF)
       : Hotness(static_cast<uint32_t>(Hotness)), RelBlockFreq(RelBF) {}
 
   void updateHotness(const HotnessType OtherHotness) {
     Hotness = std::max(Hotness, static_cast<uint32_t>(OtherHotness));
   }
 
   HotnessType getHotness() const { return HotnessType(Hotness); }
 
-  // When there are multiple edges between the same (caller, callee) pair, the
-  // relative block frequencies are summed up.
-  void updateRelBlockFreq(uint64_t RBF) {
-    uint64_t Sum = SaturatingAdd<uint64_t>(RelBlockFreq, RBF);
+  /// Update \p RelBlockFreq from \p BlockFreq and \p EntryFreq
+  ///
+  /// BlockFreq is divided by EntryFreq and added to RelBlockFreq. To represent
+  /// fractional values, the result is represented as a fixed point number with
+  /// scale of -ScaleShift.
+  void updateRelBlockFreq(uint64_t BlockFreq, uint64_t EntryFreq) {
+    if (EntryFreq == 0)
+      return;
+    using Scaled64 = ScaledNumber<uint64_t>;
+    Scaled64 Temp(BlockFreq, ScaleShift);
+    Temp /= Scaled64::get(EntryFreq);
+
+    uint64_t Sum =
+        SaturatingAdd<uint64_t>(Temp.toInt<uint64_t>(), RelBlockFreq);
     Sum = std::min(Sum, uint64_t(MaxRelBlockFreq));
     RelBlockFreq = static_cast<uint32_t>(Sum);
   }
 };
 
 class GlobalValueSummary;
 
 using GlobalValueSummaryList = std::vector<std::unique_ptr<GlobalValueSummary>>;

llvm/trunk/lib/Analysis/ModuleSummaryAnalysis.cpp

for (const Instruction &I : BB) {
         // an alias summary will be created to associate the alias and
         // aliasee.
         auto &ValueInfo = CallGraphEdges[Index.getOrInsertValueInfo(
             cast<GlobalValue>(CalledValue))];
         ValueInfo.updateHotness(Hotness);
         // Add the relative block frequency to CalleeInfo if there is no profile
         // information.
         if (BFI != nullptr && Hotness == CalleeInfo::HotnessType::Unknown) {
-          auto BBFreq = BFI->getBlockFreq(&BB).getFrequency();
-          // FIXME: This might need some scaling to prevent BBFreq values from
-          // being rounded down to 0.
-          auto EntryFreq = BFI->getEntryFreq();
-          // Block frequencies can be directly set for a block and so we need to
-          // handle the case of entry frequency being 0.
-          if (EntryFreq)
-            BBFreq /= EntryFreq;
-          else
-            BBFreq = 0;
-          ValueInfo.updateRelBlockFreq(BBFreq);
+          uint64_t BBFreq = BFI->getBlockFreq(&BB).getFrequency();
+          uint64_t EntryFreq = BFI->getEntryFreq();
+          ValueInfo.updateRelBlockFreq(BBFreq, EntryFreq);
         }
       } else {
         // Skip inline assembly calls.
         if (CI && CI->isInlineAsm())
           continue;
         // Skip direct calls.
         if (!CalledValue || isa<Constant>(CalledValue))
           continue;

llvm/trunk/test/Bitcode/thinlto-function-summary-callgraph-relbf.ll

 ; Test to check the callgraph in summary
 ; RUN: opt -write-relbf-to-summary -module-summary %s -o %t.o
 ; RUN: llvm-bcanalyzer -dump %t.o | FileCheck %s
 
 
 ; CHECK: <SOURCE_FILENAME
 ; CHECK-NEXT: <GLOBALVAR
 ; CHECK-NEXT: <FUNCTION
 ; "func"
 ; CHECK-NEXT: <FUNCTION op0=17 op1=4
 ; CHECK:       <GLOBALVAL_SUMMARY_BLOCK
 ; CHECK-NEXT:    <VERSION
 ; See if the call to func is registered.
-; CHECK-NEXT:    <PERMODULE_RELBF {{.*}} op4=1 {{.*}} op7=1
+; CHECK-NEXT:    <PERMODULE_RELBF {{.*}} op4=1 {{.*}} op7=256
 ; CHECK-NEXT:  </GLOBALVAL_SUMMARY_BLOCK>
 ; CHECK: <STRTAB_BLOCK
 ; CHECK-NEXT: blob data = 'undefinedglobmainfunc{{.*}}'
 
 
 ; ModuleID = 'thinlto-function-summary-callgraph.ll'
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"