LLVM  16.0.0git
InstructionCost.h
Go to the documentation of this file.
1 //===- InstructionCost.h ----------------------------------------*- 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 /// \file
9 /// This file defines an InstructionCost class that is used when calculating
10 /// the cost of an instruction, or a group of instructions. In addition to a
11 /// numeric value representing the cost the class also contains a state that
12 /// can be used to encode particular properties, such as a cost being invalid.
13 /// Operations on InstructionCost implement saturation arithmetic, so that
14 /// accumulating costs on large cost-values don't overflow.
15 ///
16 //===----------------------------------------------------------------------===//
17 
18 #ifndef LLVM_SUPPORT_INSTRUCTIONCOST_H
19 #define LLVM_SUPPORT_INSTRUCTIONCOST_H
20 
21 #include "llvm/ADT/Optional.h"
23 #include <limits>
24 #include <optional>
25 
26 namespace llvm {
27 
28 class raw_ostream;
29 
31 public:
32  using CostType = int64_t;
33 
34  /// CostState describes the state of a cost.
35  enum CostState {
36  Valid, /// < The cost value represents a valid cost, even when the
37  /// cost-value is large.
38  Invalid /// < Invalid indicates there is no way to represent the cost as a
39  /// numeric value. This state exists to represent a possible issue,
40  /// e.g. if the cost-model knows the operation cannot be expanded
41  /// into a valid code-sequence by the code-generator. While some
42  /// passes may assert that the calculated cost must be valid, it is
43  /// up to individual passes how to interpret an Invalid cost. For
44  /// example, a transformation pass could choose not to perform a
45  /// transformation if the resulting cost would end up Invalid.
46  /// Because some passes may assert a cost is Valid, it is not
47  /// recommended to use Invalid costs to model 'Unknown'.
48  /// Note that Invalid is semantically different from a (very) high,
49  /// but valid cost, which intentionally indicates no issue, but
50  /// rather a strong preference not to select a certain operation.
51  };
52 
53 private:
54  CostType Value = 0;
55  CostState State = Valid;
56 
57  void propagateState(const InstructionCost &RHS) {
58  if (RHS.State == Invalid)
59  State = Invalid;
60  }
61 
62  static CostType getMaxValue() { return std::numeric_limits<CostType>::max(); }
63  static CostType getMinValue() { return std::numeric_limits<CostType>::min(); }
64 
65 public:
66  // A default constructed InstructionCost is a valid zero cost
67  InstructionCost() = default;
68 
69  InstructionCost(CostState) = delete;
70  InstructionCost(CostType Val) : Value(Val), State(Valid) {}
71 
72  static InstructionCost getMax() { return getMaxValue(); }
73  static InstructionCost getMin() { return getMinValue(); }
75  InstructionCost Tmp(Val);
76  Tmp.setInvalid();
77  return Tmp;
78  }
79 
80  bool isValid() const { return State == Valid; }
81  void setValid() { State = Valid; }
82  void setInvalid() { State = Invalid; }
83  CostState getState() const { return State; }
84 
85  /// This function is intended to be used as sparingly as possible, since the
86  /// class provides the full range of operator support required for arithmetic
87  /// and comparisons.
88  std::optional<CostType> getValue() const {
89  if (isValid())
90  return Value;
91  return None;
92  }
93 
94  /// For all of the arithmetic operators provided here any invalid state is
95  /// perpetuated and cannot be removed. Once a cost becomes invalid it stays
96  /// invalid, and it also inherits any invalid state from the RHS.
97  /// Arithmetic work on the actual values is implemented with saturation,
98  /// to avoid overflow when using more extreme cost values.
99 
101  propagateState(RHS);
102 
103  // Saturating addition.
105  if (AddOverflow(Value, RHS.Value, Result))
106  Result = RHS.Value > 0 ? getMaxValue() : getMinValue();
107 
108  Value = Result;
109  return *this;
110  }
111 
113  InstructionCost RHS2(RHS);
114  *this += RHS2;
115  return *this;
116  }
117 
119  propagateState(RHS);
120 
121  // Saturating subtract.
123  if (SubOverflow(Value, RHS.Value, Result))
124  Result = RHS.Value > 0 ? getMinValue() : getMaxValue();
125  Value = Result;
126  return *this;
127  }
128 
130  InstructionCost RHS2(RHS);
131  *this -= RHS2;
132  return *this;
133  }
134 
136  propagateState(RHS);
137 
138  // Saturating multiply.
140  if (MulOverflow(Value, RHS.Value, Result)) {
141  if ((Value > 0 && RHS.Value > 0) || (Value < 0 && RHS.Value < 0))
142  Result = getMaxValue();
143  else
144  Result = getMinValue();
145  }
146 
147  Value = Result;
148  return *this;
149  }
150 
152  InstructionCost RHS2(RHS);
153  *this *= RHS2;
154  return *this;
155  }
156 
158  propagateState(RHS);
159  Value /= RHS.Value;
160  return *this;
161  }
162 
164  InstructionCost RHS2(RHS);
165  *this /= RHS2;
166  return *this;
167  }
168 
170  *this += 1;
171  return *this;
172  }
173 
175  InstructionCost Copy = *this;
176  ++*this;
177  return Copy;
178  }
179 
181  *this -= 1;
182  return *this;
183  }
184 
186  InstructionCost Copy = *this;
187  --*this;
188  return Copy;
189  }
190 
191  /// For the comparison operators we have chosen to use lexicographical
192  /// ordering where valid costs are always considered to be less than invalid
193  /// costs. This avoids having to add asserts to the comparison operators that
194  /// the states are valid and users can test for validity of the cost
195  /// explicitly.
196  bool operator<(const InstructionCost &RHS) const {
197  if (State != RHS.State)
198  return State < RHS.State;
199  return Value < RHS.Value;
200  }
201 
202  // Implement in terms of operator< to ensure that the two comparisons stay in
203  // sync
204  bool operator==(const InstructionCost &RHS) const {
205  return !(*this < RHS) && !(RHS < *this);
206  }
207 
208  bool operator!=(const InstructionCost &RHS) const { return !(*this == RHS); }
209 
210  bool operator==(const CostType RHS) const {
211  InstructionCost RHS2(RHS);
212  return *this == RHS2;
213  }
214 
215  bool operator!=(const CostType RHS) const { return !(*this == RHS); }
216 
217  bool operator>(const InstructionCost &RHS) const { return RHS < *this; }
218 
219  bool operator<=(const InstructionCost &RHS) const { return !(RHS < *this); }
220 
221  bool operator>=(const InstructionCost &RHS) const { return !(*this < RHS); }
222 
223  bool operator<(const CostType RHS) const {
224  InstructionCost RHS2(RHS);
225  return *this < RHS2;
226  }
227 
228  bool operator>(const CostType RHS) const {
229  InstructionCost RHS2(RHS);
230  return *this > RHS2;
231  }
232 
233  bool operator<=(const CostType RHS) const {
234  InstructionCost RHS2(RHS);
235  return *this <= RHS2;
236  }
237 
238  bool operator>=(const CostType RHS) const {
239  InstructionCost RHS2(RHS);
240  return *this >= RHS2;
241  }
242 
243  void print(raw_ostream &OS) const;
244 
245  template <class Function>
246  auto map(const Function &F) const -> InstructionCost {
247  if (isValid())
248  return F(Value);
249  return getInvalid();
250  }
251 };
252 
254  const InstructionCost &RHS) {
255  InstructionCost LHS2(LHS);
256  LHS2 += RHS;
257  return LHS2;
258 }
259 
261  const InstructionCost &RHS) {
262  InstructionCost LHS2(LHS);
263  LHS2 -= RHS;
264  return LHS2;
265 }
266 
268  const InstructionCost &RHS) {
269  InstructionCost LHS2(LHS);
270  LHS2 *= RHS;
271  return LHS2;
272 }
273 
275  const InstructionCost &RHS) {
276  InstructionCost LHS2(LHS);
277  LHS2 /= RHS;
278  return LHS2;
279 }
280 
282  V.print(OS);
283  return OS;
284 }
285 
286 } // namespace llvm
287 
288 #endif
llvm::InstructionCost::operator>
bool operator>(const InstructionCost &RHS) const
Definition: InstructionCost.h:217
llvm::InstructionCost
Definition: InstructionCost.h:30
llvm::InstructionCost::operator+=
InstructionCost & operator+=(const CostType RHS)
Definition: InstructionCost.h:112
MathExtras.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Optional.h
llvm::InstructionCost::operator>=
bool operator>=(const CostType RHS) const
Definition: InstructionCost.h:238
llvm::InstructionCost::map
auto map(const Function &F) const -> InstructionCost
Definition: InstructionCost.h:246
llvm::InstructionCost::CostState
CostState
CostState describes the state of a cost.
Definition: InstructionCost.h:35
llvm::InstructionCost::operator++
InstructionCost & operator++()
Definition: InstructionCost.h:169
llvm::Function
Definition: Function.h:60
llvm::InstructionCost::InstructionCost
InstructionCost()=default
llvm::InstructionCost::operator<=
bool operator<=(const InstructionCost &RHS) const
Definition: InstructionCost.h:219
llvm::InstructionCost::operator>
bool operator>(const CostType RHS) const
Definition: InstructionCost.h:228
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::InstructionCost::operator<=
bool operator<=(const CostType RHS) const
Definition: InstructionCost.h:233
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::InstructionCost::print
void print(raw_ostream &OS) const
Definition: InstructionCost.cpp:19
F
#define F(x, y, z)
Definition: MD5.cpp:55
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::InstructionCost::operator--
InstructionCost & operator--()
Definition: InstructionCost.h:180
llvm::InstructionCost::operator/=
InstructionCost & operator/=(const InstructionCost &RHS)
Definition: InstructionCost.h:157
llvm::InstructionCost::operator<
bool operator<(const CostType RHS) const
Definition: InstructionCost.h:223
llvm::operator/
InstructionCost operator/(const InstructionCost &LHS, const InstructionCost &RHS)
Definition: InstructionCost.h:274
llvm::operator-
APInt operator-(APInt)
Definition: APInt.h:2087
llvm::InstructionCost::operator+=
InstructionCost & operator+=(const InstructionCost &RHS)
For all of the arithmetic operators provided here any invalid state is perpetuated and cannot be remo...
Definition: InstructionCost.h:100
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::InstructionCost::operator==
bool operator==(const CostType RHS) const
Definition: InstructionCost.h:210
llvm::InstructionCost::operator!=
bool operator!=(const InstructionCost &RHS) const
Definition: InstructionCost.h:208
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:291
llvm::AddOverflow
std::enable_if_t< std::is_signed< T >::value, T > AddOverflow(T X, T Y, T &Result)
Add two signed integers, computing the two's complement truncated result, returning true if overflow ...
Definition: MathExtras.h:825
llvm::InstructionCost::setInvalid
void setInvalid()
Definition: InstructionCost.h:82
llvm::InstructionCost::operator<
bool operator<(const InstructionCost &RHS) const
For the comparison operators we have chosen to use lexicographical ordering where valid costs are alw...
Definition: InstructionCost.h:196
llvm::InstructionCost::getValue
std::optional< CostType > getValue() const
This function is intended to be used as sparingly as possible, since the class provides the full rang...
Definition: InstructionCost.h:88
llvm::operator+
APInt operator+(APInt a, const APInt &b)
Definition: APInt.h:2092
llvm::InstructionCost::operator!=
bool operator!=(const CostType RHS) const
Definition: InstructionCost.h:215
llvm::operator*
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2134
llvm::InstructionCost::operator--
InstructionCost operator--(int)
Definition: InstructionCost.h:185
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::InstructionCost::getMin
static InstructionCost getMin()
Definition: InstructionCost.h:73
llvm::InstructionCost::operator*=
InstructionCost & operator*=(const InstructionCost &RHS)
Definition: InstructionCost.h:135
llvm::InstructionCost::operator-=
InstructionCost & operator-=(const CostType RHS)
Definition: InstructionCost.h:129
llvm::InstructionCost::operator-=
InstructionCost & operator-=(const InstructionCost &RHS)
Definition: InstructionCost.h:118
llvm::InstructionCost::isValid
bool isValid() const
Definition: InstructionCost.h:80
llvm::None
constexpr std::nullopt_t None
Definition: None.h:27
llvm::InstructionCost::getMax
static InstructionCost getMax()
Definition: InstructionCost.h:72
llvm::InstructionCost::setValid
void setValid()
Definition: InstructionCost.h:81
llvm::MulOverflow
std::enable_if_t< std::is_signed< T >::value, T > MulOverflow(T X, T Y, T &Result)
Multiply two signed integers, computing the two's complement truncated result, returning true if an o...
Definition: MathExtras.h:877
llvm::InstructionCost::operator==
bool operator==(const InstructionCost &RHS) const
Definition: InstructionCost.h:204
llvm::SubOverflow
std::enable_if_t< std::is_signed< T >::value, T > SubOverflow(T X, T Y, T &Result)
Subtract two signed integers, computing the two's complement truncated result, returning true if an o...
Definition: MathExtras.h:851
llvm::InstructionCost::getInvalid
static InstructionCost getInvalid(CostType Val=0)
Definition: InstructionCost.h:74
llvm::InstructionCost::operator++
InstructionCost operator++(int)
Definition: InstructionCost.h:174
llvm::InstructionCost::Invalid
@ Invalid
< The cost value represents a valid cost, even when the cost-value is large.
Definition: InstructionCost.h:38
llvm::InstructionCost::CostType
int64_t CostType
Definition: InstructionCost.h:32
llvm::InstructionCost::getState
CostState getState() const
Definition: InstructionCost.h:83
llvm::InstructionCost::operator>=
bool operator>=(const InstructionCost &RHS) const
Definition: InstructionCost.h:221
llvm::InstructionCost::operator/=
InstructionCost & operator/=(const CostType RHS)
Definition: InstructionCost.h:163
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::InstructionCost::InstructionCost
InstructionCost(CostType Val)
Definition: InstructionCost.h:70
llvm::InstructionCost::Valid
@ Valid
Definition: InstructionCost.h:36
llvm::InstructionCost::operator*=
InstructionCost & operator*=(const CostType RHS)
Definition: InstructionCost.h:151