1 // Simple fixed-point representation of fractional costs
2 // Copyright (C) 2021-2022 Free Software Foundation, Inc.
3 //
4 // This file is part of GCC.
5 //
6 // GCC is free software; you can redistribute it and/or modify it under
7 // the terms of the GNU General Public License as published by the Free
8 // Software Foundation; either version 3, or (at your option) any later
9 // version.
10 //
11 // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 // WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 // for more details.
15 //
16 // You should have received a copy of the GNU General Public License
17 // along with GCC; see the file COPYING3. If not see
18 // <http://www.gnu.org/licenses/>.
19
20 // A simple saturating fixed-point type for representing fractional
21 // intermediate results in cost calculations. The input and result
22 // costs are assumed to be uint32_ts. Unlike sreal, the class can
23 // represent most values that we care about exactly (without rounding).
24 // See the comment above the SCALE field for the current set of
25 // exactly-representable reciprocals.
26 class fractional_cost
27 {
28 public:
29 // Construct an object equal to INT_VALUE.
30 constexpr fractional_cost (uint32_t int_value = 0)
m_value(uint64_t (int_value)* SCALE)31 : m_value (uint64_t (int_value) * SCALE) {}
32
33 fractional_cost (uint32_t a, uint32_t b);
34
35 fractional_cost operator+ (const fractional_cost &) const;
36 fractional_cost operator- (const fractional_cost &) const;
37 fractional_cost operator* (uint32_t) const;
38
39 fractional_cost &operator+= (const fractional_cost &);
40 fractional_cost &operator-= (const fractional_cost &);
41 fractional_cost &operator*= (uint32_t);
42
43 bool operator== (const fractional_cost &) const;
44 bool operator!= (const fractional_cost &) const;
45 bool operator< (const fractional_cost &) const;
46 bool operator<= (const fractional_cost &) const;
47 bool operator>= (const fractional_cost &) const;
48 bool operator> (const fractional_cost &) const;
49
50 uint32_t ceil () const;
51
52 static uint32_t scale (uint32_t, fractional_cost, fractional_cost);
53
54 explicit operator bool () const { return m_value != 0; }
55
56 // Convert the value to a double.
as_double()57 double as_double () const { return double (m_value) / SCALE; }
58
59 private:
60 enum raw { RAW };
fractional_cost(uint64_t value,raw)61 constexpr fractional_cost (uint64_t value, raw) : m_value (value) {}
62
63 // A multiple of [1, 16] * 16. This ensures that 1/N is representable
64 // for every possible SVE element count N, or for any "X per cycle"
65 // value N in the range [1, 16].
66 static const uint32_t SCALE = 11531520;
67
68 // The value multiplied by BIAS.
69 uint64_t m_value;
70 };
71
72 // Construct a representation of A / B, rounding up if (contrary to
73 // expectations) we can't represent the value exactly. For now we
74 // treat inexact values as a bug, since all values of B should come
75 // from a small set of values that are known at compile time.
fractional_cost(uint32_t a,uint32_t b)76 inline fractional_cost::fractional_cost (uint32_t a, uint32_t b)
77 : m_value (CEIL (uint64_t (a) * SCALE, uint64_t (b)))
78 {
79 gcc_checking_assert (SCALE % b == 0);
80 }
81
82 inline fractional_cost
83 fractional_cost::operator+ (const fractional_cost &other) const
84 {
85 uint64_t sum = m_value + other.m_value;
86 return { sum >= m_value ? sum : ~uint64_t (0), RAW };
87 }
88
89 inline fractional_cost &
90 fractional_cost::operator+= (const fractional_cost &other)
91 {
92 *this = *this + other;
93 return *this;
94 }
95
96 inline fractional_cost
97 fractional_cost::operator- (const fractional_cost &other) const
98 {
99 uint64_t diff = m_value - other.m_value;
100 return { diff <= m_value ? diff : 0, RAW };
101 }
102
103 inline fractional_cost &
104 fractional_cost::operator-= (const fractional_cost &other)
105 {
106 *this = *this - other;
107 return *this;
108 }
109
110 inline fractional_cost
111 fractional_cost::operator* (uint32_t other) const
112 {
113 if (other == 0)
114 return 0;
115
116 uint64_t max = ~uint64_t (0);
117 return { m_value <= max / other ? m_value * other : max, RAW };
118 }
119
120 inline fractional_cost &
121 fractional_cost::operator*= (uint32_t other)
122 {
123 *this = *this * other;
124 return *this;
125 }
126
127 inline bool
128 fractional_cost::operator== (const fractional_cost &other) const
129 {
130 return m_value == other.m_value;
131 }
132
133 inline bool
134 fractional_cost::operator!= (const fractional_cost &other) const
135 {
136 return m_value != other.m_value;
137 }
138
139 inline bool
140 fractional_cost::operator< (const fractional_cost &other) const
141 {
142 return m_value < other.m_value;
143 }
144
145 inline bool
146 fractional_cost::operator<= (const fractional_cost &other) const
147 {
148 return m_value <= other.m_value;
149 }
150
151 inline bool
152 fractional_cost::operator>= (const fractional_cost &other) const
153 {
154 return m_value >= other.m_value;
155 }
156
157 inline bool
158 fractional_cost::operator> (const fractional_cost &other) const
159 {
160 return m_value > other.m_value;
161 }
162
163 // Round the value up to the nearest integer and saturate to a uint32_t.
164 inline uint32_t
ceil()165 fractional_cost::ceil () const
166 {
167 uint32_t max = ~uint32_t (0);
168 if (m_value <= uint64_t (max - 1) * SCALE)
169 return (m_value + SCALE - 1) / SCALE;
170 return max;
171 }
172
173 // Round (COST * A) / B up to the nearest integer and saturate to a uint32_t.
174 inline uint32_t
scale(uint32_t cost,fractional_cost a,fractional_cost b)175 fractional_cost::scale (uint32_t cost, fractional_cost a, fractional_cost b)
176 {
177 widest_int result = wi::div_ceil (widest_int (cost) * a.m_value,
178 b.m_value, SIGNED);
179 if (result < ~uint32_t (0))
180 return result.to_shwi ();
181 return ~uint32_t (0);
182 }
183
184 inline fractional_cost
185 operator+ (uint32_t a, const fractional_cost &b)
186 {
187 return b.operator+ (a);
188 }
189
190 inline fractional_cost
191 operator- (uint32_t a, const fractional_cost &b)
192 {
193 return fractional_cost (a).operator- (b);
194 }
195
196 inline fractional_cost
197 operator* (uint32_t a, const fractional_cost &b)
198 {
199 return b.operator* (a);
200 }
201
202 inline bool
203 operator== (uint32_t a, const fractional_cost &b)
204 {
205 return b.operator== (a);
206 }
207
208 inline bool
209 operator!= (uint32_t a, const fractional_cost &b)
210 {
211 return b.operator!= (a);
212 }
213
214 inline bool
215 operator< (uint32_t a, const fractional_cost &b)
216 {
217 return b.operator> (a);
218 }
219
220 inline bool
221 operator<= (uint32_t a, const fractional_cost &b)
222 {
223 return b.operator>= (a);
224 }
225
226 inline bool
227 operator>= (uint32_t a, const fractional_cost &b)
228 {
229 return b.operator<= (a);
230 }
231
232 inline bool
233 operator> (uint32_t a, const fractional_cost &b)
234 {
235 return b.operator< (a);
236 }
237