1 //===---- llvm/Support/Discriminator.h -- Discriminator Utils ---*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the constants and utility functions for discriminators.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_SUPPORT_DISCRIMINATOR_H
14 #define LLVM_SUPPORT_DISCRIMINATOR_H
15 
16 #include "llvm/Support/Error.h"
17 #include <assert.h>
18 
19 // Utility functions for encoding / decoding discriminators.
20 /// With a given unsigned int \p U, use up to 13 bits to represent it.
21 /// old_bit 1~5  --> new_bit 1~5
22 /// old_bit 6~12 --> new_bit 7~13
23 /// new_bit_6 is 0 if higher bits (7~13) are all 0
24 static inline unsigned getPrefixEncodingFromUnsigned(unsigned U) {
25   U &= 0xfff;
26   return U > 0x1f ? (((U & 0xfe0) << 1) | (U & 0x1f) | 0x20) : U;
27 }
28 
29 /// Reverse transformation as getPrefixEncodingFromUnsigned.
30 static inline unsigned getUnsignedFromPrefixEncoding(unsigned U) {
31   if (U & 1)
32     return 0;
33   U >>= 1;
34   return (U & 0x20) ? (((U >> 1) & 0xfe0) | (U & 0x1f)) : (U & 0x1f);
35 }
36 
37 /// Returns the next component stored in discriminator.
38 static inline unsigned getNextComponentInDiscriminator(unsigned D) {
39   if ((D & 1) == 0)
40     return D >> ((D & 0x40) ? 14 : 7);
41   else
42     return D >> 1;
43 }
44 
45 static inline unsigned encodeComponent(unsigned C) {
46   return (C == 0) ? 1U : (getPrefixEncodingFromUnsigned(C) << 1);
47 }
48 
49 static inline unsigned encodingBits(unsigned C) {
50   return (C == 0) ? 1 : (C > 0x1f ? 14 : 7);
51 }
52 
53 // Some constants used in FS Discriminators.
54 //
55 namespace llvm {
56 namespace sampleprof {
57 enum FSDiscriminatorPass {
58   Base = 0,
59   Pass0 = 0,
60   Pass1 = 1,
61   Pass2 = 2,
62   Pass3 = 3,
63   Pass4 = 4,
64   PassLast = 4,
65 };
66 } // namespace sampleprof
67 
68 // The number of bits reserved for the base discrimininator. The base
69 // discriminaitor starts from bit 0.
70 static const unsigned BaseDiscriminatorBitWidth = 8;
71 
72 // The number of bits reserved for each FS discriminator pass.
73 static const unsigned FSDiscriminatorBitWidth = 6;
74 
75 // Return the number of FS passes, excluding the pass adding the base
76 // discriminators.
77 // The number of passes for FS discriminators. Note that the total
78 // number of discriminaitor bits, i.e.
79 // BaseDiscriminatorBitWidth
80 //  + FSDiscriminatorBitWidth * getNumFSPasses()
81 // needs to fit in an unsigned int type.
82 static inline unsigned getNumFSPasses() {
83   return static_cast<unsigned>(sampleprof::FSDiscriminatorPass::PassLast);
84 }
85 
86 // Return the ending bit for FSPass P.
87 static inline unsigned getFSPassBitEnd(sampleprof::FSDiscriminatorPass P) {
88   unsigned I = static_cast<unsigned>(P);
89   assert(I <= getNumFSPasses() && "Invalid FS discriminator pass number.");
90   return BaseDiscriminatorBitWidth + I * FSDiscriminatorBitWidth - 1;
91 }
92 
93 // Return the begining bit for FSPass P.
94 static inline unsigned getFSPassBitBegin(sampleprof::FSDiscriminatorPass P) {
95   if (P == sampleprof::FSDiscriminatorPass::Base)
96     return 0;
97   unsigned I = static_cast<unsigned>(P);
98   assert(I <= getNumFSPasses() && "Invalid FS discriminator pass number.");
99   return getFSPassBitEnd(static_cast<sampleprof::FSDiscriminatorPass>(I - 1)) +
100          1;
101 }
102 
103 // Return the beginning bit for the last FSPass.
104 static inline int getLastFSPassBitBegin() {
105   return getFSPassBitBegin(
106       static_cast<sampleprof::FSDiscriminatorPass>(getNumFSPasses()));
107 }
108 
109 // Return the ending bit for the last FSPass.
110 static inline unsigned getLastFSPassBitEnd() {
111   return getFSPassBitEnd(
112       static_cast<sampleprof::FSDiscriminatorPass>(getNumFSPasses()));
113 }
114 
115 // Return the beginning bit for the base (first) FSPass.
116 static inline unsigned getBaseFSBitBegin() { return 0; }
117 
118 // Return the ending bit for the base (first) FSPass.
119 static inline unsigned getBaseFSBitEnd() {
120   return BaseDiscriminatorBitWidth - 1;
121 }
122 
123 // Set bits in range of [0 .. n] to 1. Used in FS Discriminators.
124 static inline unsigned getN1Bits(int N) {
125   // Work around the g++ bug that folding "(1U << (N + 1)) - 1" to 0.
126   if (N == 31)
127     return 0xFFFFFFFF;
128   assert((N < 32) && "N is invalid");
129   return (1U << (N + 1)) - 1;
130 }
131 
132 } // namespace llvm
133 
134 #endif /* LLVM_SUPPORT_DISCRIMINATOR_H */
135