Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1 | //===- subzero/src/IceOperand.h - High-level operands -----------*- C++ -*-===// |
| 2 | // |
| 3 | // The Subzero Code Generator |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 9 | /// |
| 10 | /// \file |
Jim Stichnoth | 92a6e5b | 2015-12-02 16:52:44 -0800 | [diff] [blame] | 11 | /// \brief Declares the Operand class and its target-independent subclasses. |
| 12 | /// |
Andrew Scull | 6ef7949 | 2015-09-09 15:50:42 -0700 | [diff] [blame] | 13 | /// The main classes are Variable, which represents an LLVM variable that is |
| 14 | /// either register- or stack-allocated, and the Constant hierarchy, which |
| 15 | /// represents integer, floating-point, and/or symbolic constants. |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 16 | /// |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 17 | //===----------------------------------------------------------------------===// |
| 18 | |
| 19 | #ifndef SUBZERO_SRC_ICEOPERAND_H |
| 20 | #define SUBZERO_SRC_ICEOPERAND_H |
| 21 | |
| 22 | #include "IceDefs.h" |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 23 | #include "IceCfg.h" |
Jan Voung | fe14fb8 | 2014-10-13 15:56:32 -0700 | [diff] [blame] | 24 | #include "IceGlobalContext.h" |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 25 | #include "IceStringPool.h" |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 26 | #include "IceTypes.h" |
| 27 | |
Nicolas Capens | 4d70802 | 2016-09-07 15:03:32 -0400 | [diff] [blame^] | 28 | #include "llvm/Support/ErrorHandling.h" |
Jim Stichnoth | b36757e | 2015-10-05 13:55:11 -0700 | [diff] [blame] | 29 | #include "llvm/Support/Format.h" |
| 30 | |
John Porto | 27fddcc | 2016-02-02 15:06:09 -0800 | [diff] [blame] | 31 | #include <limits> |
Jim Stichnoth | 9f9aa2c | 2016-03-07 08:25:24 -0800 | [diff] [blame] | 32 | #include <type_traits> |
John Porto | 27fddcc | 2016-02-02 15:06:09 -0800 | [diff] [blame] | 33 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 34 | namespace Ice { |
| 35 | |
| 36 | class Operand { |
Jim Stichnoth | c6ead20 | 2015-02-24 09:30:30 -0800 | [diff] [blame] | 37 | Operand() = delete; |
Jim Stichnoth | 7b451a9 | 2014-10-15 14:39:23 -0700 | [diff] [blame] | 38 | Operand(const Operand &) = delete; |
| 39 | Operand &operator=(const Operand &) = delete; |
| 40 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 41 | public: |
Andrew Scull | 6ef7949 | 2015-09-09 15:50:42 -0700 | [diff] [blame] | 42 | static constexpr size_t MaxTargetKinds = 10; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 43 | enum OperandKind { |
| 44 | kConst_Base, |
Jan Voung | bc00463 | 2014-09-16 15:09:10 -0700 | [diff] [blame] | 45 | kConstInteger32, |
| 46 | kConstInteger64, |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 47 | kConstFloat, |
| 48 | kConstDouble, |
| 49 | kConstRelocatable, |
Matt Wala | d8f4a7d | 2014-06-18 09:55:03 -0700 | [diff] [blame] | 50 | kConstUndef, |
Jim Stichnoth | 800dab2 | 2014-09-20 12:25:02 -0700 | [diff] [blame] | 51 | kConst_Target, // leave space for target-specific constant kinds |
Andrew Scull | 6ef7949 | 2015-09-09 15:50:42 -0700 | [diff] [blame] | 52 | kConst_Max = kConst_Target + MaxTargetKinds, |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 53 | kVariable, |
Andrew Scull | 6d47bcd | 2015-09-17 17:10:05 -0700 | [diff] [blame] | 54 | kVariable64On32, |
Eric Holk | 80ee5b3 | 2016-05-06 14:28:04 -0700 | [diff] [blame] | 55 | kVariableBoolean, |
Jim Stichnoth | 800dab2 | 2014-09-20 12:25:02 -0700 | [diff] [blame] | 56 | kVariable_Target, // leave space for target-specific variable kinds |
Andrew Scull | 6ef7949 | 2015-09-09 15:50:42 -0700 | [diff] [blame] | 57 | kVariable_Max = kVariable_Target + MaxTargetKinds, |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 58 | // Target-specific operand classes use kTarget as the starting point for |
| 59 | // their Kind enum space. Note that the value-spaces are shared across |
| 60 | // targets. To avoid confusion over the definition of shared values, an |
| 61 | // object specific to one target should never be passed to a different |
| 62 | // target. |
Andrew Scull | 6ef7949 | 2015-09-09 15:50:42 -0700 | [diff] [blame] | 63 | kTarget, |
| 64 | kTarget_Max = std::numeric_limits<uint8_t>::max(), |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 65 | }; |
Andrew Scull | 6ef7949 | 2015-09-09 15:50:42 -0700 | [diff] [blame] | 66 | static_assert(kTarget <= kTarget_Max, "Must not be above max."); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 67 | OperandKind getKind() const { return Kind; } |
| 68 | Type getType() const { return Ty; } |
| 69 | |
Andrew Scull | 6ef7949 | 2015-09-09 15:50:42 -0700 | [diff] [blame] | 70 | /// Every Operand keeps an array of the Variables referenced in the operand. |
| 71 | /// This is so that the liveness operations can get quick access to the |
| 72 | /// variables of interest, without having to dig so far into the operand. |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 73 | SizeT getNumVars() const { return NumVars; } |
| 74 | Variable *getVar(SizeT I) const { |
| 75 | assert(I < getNumVars()); |
| 76 | return Vars[I]; |
| 77 | } |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 78 | virtual void emit(const Cfg *Func) const = 0; |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 79 | |
| 80 | /// \name Dumping functions. |
| 81 | /// @{ |
| 82 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 83 | /// The dump(Func,Str) implementation must be sure to handle the situation |
| 84 | /// where Func==nullptr. |
Jim Stichnoth | 2e8bfbb | 2014-09-16 10:16:00 -0700 | [diff] [blame] | 85 | virtual void dump(const Cfg *Func, Ostream &Str) const = 0; |
| 86 | void dump(const Cfg *Func) const { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 87 | if (!BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 88 | return; |
Jim Stichnoth | 2e8bfbb | 2014-09-16 10:16:00 -0700 | [diff] [blame] | 89 | assert(Func); |
| 90 | dump(Func, Func->getContext()->getStrDump()); |
| 91 | } |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 92 | void dump(Ostream &Str) const { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 93 | if (BuildDefs::dump()) |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 94 | dump(nullptr, Str); |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 95 | } |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 96 | /// @} |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 97 | |
Sean Klein | fc707ff | 2016-02-29 16:44:07 -0800 | [diff] [blame] | 98 | virtual ~Operand() = default; |
Andrew Scull | 00741a0 | 2015-09-16 19:04:09 -0700 | [diff] [blame] | 99 | |
Eric Holk | 80ee5b3 | 2016-05-06 14:28:04 -0700 | [diff] [blame] | 100 | virtual Variable *asBoolean() { return nullptr; } |
| 101 | |
Manasij Mukherjee | 032c315 | 2016-05-24 14:25:04 -0700 | [diff] [blame] | 102 | virtual SizeT hashValue() const { |
| 103 | llvm::report_fatal_error("Tried to hash unsupported operand type : " + |
| 104 | std::to_string(Kind)); |
| 105 | return 0; |
| 106 | } |
| 107 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 108 | protected: |
Andrew Scull | 6ef7949 | 2015-09-09 15:50:42 -0700 | [diff] [blame] | 109 | Operand(OperandKind Kind, Type Ty) : Ty(Ty), Kind(Kind) { |
| 110 | // It is undefined behavior to have a larger value in the enum |
| 111 | assert(Kind <= kTarget_Max); |
| 112 | } |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 113 | |
| 114 | const Type Ty; |
| 115 | const OperandKind Kind; |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 116 | /// Vars and NumVars are initialized by the derived class. |
Jim Stichnoth | eafb56c | 2015-06-22 10:35:22 -0700 | [diff] [blame] | 117 | SizeT NumVars = 0; |
| 118 | Variable **Vars = nullptr; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 119 | }; |
| 120 | |
Jim Stichnoth | dd842db | 2015-01-27 12:53:53 -0800 | [diff] [blame] | 121 | template <class StreamType> |
Karl Schimpf | 9750183 | 2014-09-16 13:35:32 -0700 | [diff] [blame] | 122 | inline StreamType &operator<<(StreamType &Str, const Operand &Op) { |
| 123 | Op.dump(Str); |
| 124 | return Str; |
| 125 | } |
| 126 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 127 | /// Constant is the abstract base class for constants. All constants are |
| 128 | /// allocated from a global arena and are pooled. |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 129 | class Constant : public Operand { |
Jim Stichnoth | c6ead20 | 2015-02-24 09:30:30 -0800 | [diff] [blame] | 130 | Constant() = delete; |
Jim Stichnoth | 7b451a9 | 2014-10-15 14:39:23 -0700 | [diff] [blame] | 131 | Constant(const Constant &) = delete; |
| 132 | Constant &operator=(const Constant &) = delete; |
| 133 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 134 | public: |
Jim Stichnoth | 9f9aa2c | 2016-03-07 08:25:24 -0800 | [diff] [blame] | 135 | // Declare the lookup counter to take minimal space in a non-DUMP build. |
| 136 | using CounterType = |
| 137 | std::conditional<BuildDefs::dump(), uint64_t, uint8_t>::type; |
Jan Voung | 76bb0be | 2015-05-14 09:26:19 -0700 | [diff] [blame] | 138 | void emit(const Cfg *Func) const override { emit(Func->getTarget()); } |
| 139 | virtual void emit(TargetLowering *Target) const = 0; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 140 | |
| 141 | static bool classof(const Operand *Operand) { |
| 142 | OperandKind Kind = Operand->getKind(); |
Andrew Scull | 6ef7949 | 2015-09-09 15:50:42 -0700 | [diff] [blame] | 143 | return Kind >= kConst_Base && Kind <= kConst_Max; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 144 | } |
| 145 | |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 146 | const GlobalString getLabelName() const { return LabelName; } |
| 147 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 148 | /// Judge if this given immediate should be randomized or pooled By default |
| 149 | /// should return false, only constant integers should truly go through this |
| 150 | /// method. |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 151 | virtual bool shouldBeRandomizedOrPooled() const { return false; } |
Qining Lu | 253dc8a | 2015-06-22 10:10:23 -0700 | [diff] [blame] | 152 | |
Jim Stichnoth | 9f9aa2c | 2016-03-07 08:25:24 -0800 | [diff] [blame] | 153 | bool getShouldBePooled() const { return ShouldBePooled; } |
Qining Lu | 253dc8a | 2015-06-22 10:10:23 -0700 | [diff] [blame] | 154 | |
Jim Stichnoth | 9f9aa2c | 2016-03-07 08:25:24 -0800 | [diff] [blame] | 155 | // This should be thread-safe because the constant pool lock is acquired |
| 156 | // before the method is invoked. |
| 157 | void updateLookupCount() { |
| 158 | if (!BuildDefs::dump()) |
| 159 | return; |
| 160 | ++LookupCount; |
| 161 | } |
| 162 | CounterType getLookupCount() const { return LookupCount; } |
Manasij Mukherjee | 032c315 | 2016-05-24 14:25:04 -0700 | [diff] [blame] | 163 | SizeT hashValue() const override { return 0; } |
Qining Lu | 253dc8a | 2015-06-22 10:10:23 -0700 | [diff] [blame] | 164 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 165 | protected: |
Jim Stichnoth | 9f9aa2c | 2016-03-07 08:25:24 -0800 | [diff] [blame] | 166 | Constant(OperandKind Kind, Type Ty) : Operand(Kind, Ty) { |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 167 | Vars = nullptr; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 168 | NumVars = 0; |
| 169 | } |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 170 | /// Set the ShouldBePooled field to the proper value after the object is fully |
| 171 | /// initialized. |
| 172 | void initShouldBePooled(); |
| 173 | GlobalString LabelName; |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 174 | /// Whether we should pool this constant. Usually Float/Double and pooled |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 175 | /// Integers should be flagged true. Ideally this field would be const, but |
| 176 | /// it needs to be initialized only after the subclass is fully constructed. |
Jim Stichnoth | 9f9aa2c | 2016-03-07 08:25:24 -0800 | [diff] [blame] | 177 | bool ShouldBePooled = false; |
| 178 | /// Note: If ShouldBePooled is ever removed from the base class, we will want |
| 179 | /// to completely disable LookupCount in a non-DUMP build to save space. |
| 180 | CounterType LookupCount = 0; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 181 | }; |
| 182 | |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 183 | /// ConstantPrimitive<> wraps a primitive type. |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 184 | template <typename T, Operand::OperandKind K> |
| 185 | class ConstantPrimitive : public Constant { |
Jim Stichnoth | c6ead20 | 2015-02-24 09:30:30 -0800 | [diff] [blame] | 186 | ConstantPrimitive() = delete; |
Jim Stichnoth | 7b451a9 | 2014-10-15 14:39:23 -0700 | [diff] [blame] | 187 | ConstantPrimitive(const ConstantPrimitive &) = delete; |
| 188 | ConstantPrimitive &operator=(const ConstantPrimitive &) = delete; |
| 189 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 190 | public: |
Andrew Scull | 8072bae | 2015-09-14 16:01:26 -0700 | [diff] [blame] | 191 | using PrimType = T; |
Jan Voung | 91a3e2c | 2015-01-09 13:01:42 -0800 | [diff] [blame] | 192 | |
Jim Stichnoth | b36757e | 2015-10-05 13:55:11 -0700 | [diff] [blame] | 193 | static ConstantPrimitive *create(GlobalContext *Ctx, Type Ty, |
| 194 | PrimType Value) { |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 195 | auto *Const = |
| 196 | new (Ctx->allocate<ConstantPrimitive>()) ConstantPrimitive(Ty, Value); |
| 197 | Const->initShouldBePooled(); |
| 198 | if (Const->getShouldBePooled()) |
| 199 | Const->initName(Ctx); |
| 200 | return Const; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 201 | } |
Jan Voung | 91a3e2c | 2015-01-09 13:01:42 -0800 | [diff] [blame] | 202 | PrimType getValue() const { return Value; } |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 203 | using Constant::emit; |
| 204 | void emit(TargetLowering *Target) const final; |
| 205 | using Constant::dump; |
| 206 | void dump(const Cfg *, Ostream &Str) const override { |
| 207 | if (BuildDefs::dump()) |
| 208 | Str << getValue(); |
| 209 | } |
| 210 | |
| 211 | static bool classof(const Operand *Operand) { |
| 212 | return Operand->getKind() == K; |
| 213 | } |
| 214 | |
Sagar Thakur | e160ed9 | 2016-05-30 07:54:47 -0700 | [diff] [blame] | 215 | SizeT hashValue() const override { return std::hash<PrimType>()(Value); } |
Manasij Mukherjee | 032c315 | 2016-05-24 14:25:04 -0700 | [diff] [blame] | 216 | |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 217 | virtual bool shouldBeRandomizedOrPooled() const override { return false; } |
| 218 | |
| 219 | private: |
| 220 | ConstantPrimitive(Type Ty, PrimType Value) : Constant(K, Ty), Value(Value) {} |
| 221 | |
| 222 | void initName(GlobalContext *Ctx) { |
| 223 | std::string Buffer; |
| 224 | llvm::raw_string_ostream Str(Buffer); |
Jim Stichnoth | e922c23 | 2016-04-09 08:54:20 -0700 | [diff] [blame] | 225 | constexpr bool IsCompact = !BuildDefs::dump(); |
| 226 | if (IsCompact) { |
| 227 | switch (getType()) { |
| 228 | case IceType_f32: |
| 229 | Str << "$F"; |
| 230 | break; |
| 231 | case IceType_f64: |
| 232 | Str << "$D"; |
| 233 | break; |
| 234 | default: |
| 235 | // For constant pooling diversification |
| 236 | Str << ".L$" << getType() << "$"; |
| 237 | break; |
| 238 | } |
| 239 | } else { |
| 240 | Str << ".L$" << getType() << "$"; |
| 241 | } |
Jim Stichnoth | b36757e | 2015-10-05 13:55:11 -0700 | [diff] [blame] | 242 | // Print hex characters byte by byte, starting from the most significant |
| 243 | // byte. NOTE: This ordering assumes Subzero runs on a little-endian |
| 244 | // platform. That means the possibility of different label names depending |
| 245 | // on the endian-ness of the platform where Subzero runs. |
| 246 | for (unsigned i = 0; i < sizeof(Value); ++i) { |
| 247 | constexpr unsigned HexWidthChars = 2; |
| 248 | unsigned Offset = sizeof(Value) - 1 - i; |
| 249 | Str << llvm::format_hex_no_prefix( |
| 250 | *(Offset + (const unsigned char *)&Value), HexWidthChars); |
| 251 | } |
| 252 | // For a floating-point value in DecorateAsm mode, also append the value in |
| 253 | // human-readable sprintf form, changing '+' to 'p' and '-' to 'm' to |
| 254 | // maintain valid asm labels. |
Jim Stichnoth | e922c23 | 2016-04-09 08:54:20 -0700 | [diff] [blame] | 255 | if (BuildDefs::dump() && std::is_floating_point<PrimType>::value && |
Karl Schimpf | d469994 | 2016-04-02 09:55:31 -0700 | [diff] [blame] | 256 | getFlags().getDecorateAsm()) { |
Jim Stichnoth | b36757e | 2015-10-05 13:55:11 -0700 | [diff] [blame] | 257 | char Buf[30]; |
| 258 | snprintf(Buf, llvm::array_lengthof(Buf), "$%g", (double)Value); |
| 259 | for (unsigned i = 0; i < llvm::array_lengthof(Buf) && Buf[i]; ++i) { |
| 260 | if (Buf[i] == '-') |
| 261 | Buf[i] = 'm'; |
| 262 | else if (Buf[i] == '+') |
| 263 | Buf[i] = 'p'; |
| 264 | } |
| 265 | Str << Buf; |
| 266 | } |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 267 | LabelName = GlobalString::createWithString(Ctx, Str.str()); |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 268 | } |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 269 | |
Jan Voung | 91a3e2c | 2015-01-09 13:01:42 -0800 | [diff] [blame] | 270 | const PrimType Value; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 271 | }; |
| 272 | |
Andrew Scull | 8072bae | 2015-09-14 16:01:26 -0700 | [diff] [blame] | 273 | using ConstantInteger32 = ConstantPrimitive<int32_t, Operand::kConstInteger32>; |
| 274 | using ConstantInteger64 = ConstantPrimitive<int64_t, Operand::kConstInteger64>; |
| 275 | using ConstantFloat = ConstantPrimitive<float, Operand::kConstFloat>; |
| 276 | using ConstantDouble = ConstantPrimitive<double, Operand::kConstDouble>; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 277 | |
Jim Stichnoth | dd842db | 2015-01-27 12:53:53 -0800 | [diff] [blame] | 278 | template <> |
| 279 | inline void ConstantInteger32::dump(const Cfg *, Ostream &Str) const { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 280 | if (!BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 281 | return; |
Jim Stichnoth | cabfa30 | 2014-09-03 15:19:12 -0700 | [diff] [blame] | 282 | if (getType() == IceType_i1) |
| 283 | Str << (getValue() ? "true" : "false"); |
| 284 | else |
Jan Voung | bc00463 | 2014-09-16 15:09:10 -0700 | [diff] [blame] | 285 | Str << static_cast<int32_t>(getValue()); |
| 286 | } |
| 287 | |
Nicolas Capens | ef9d004 | 2016-09-02 07:05:50 -0400 | [diff] [blame] | 288 | // =========== Immediate Randomization and Pooling routines ============== |
| 289 | // Specialization of the template member function for ConstantInteger32 |
| 290 | // TODO(stichnot): try to move this specialization into a target-specific file. |
| 291 | template <> inline bool ConstantInteger32::shouldBeRandomizedOrPooled() const { |
| 292 | uint32_t Threshold = getFlags().getRandomizeAndPoolImmediatesThreshold(); |
| 293 | if (getFlags().getRandomizeAndPoolImmediatesOption() == RPI_None) |
| 294 | return false; |
| 295 | if (getType() != IceType_i32 && getType() != IceType_i16 && |
| 296 | getType() != IceType_i8) |
| 297 | return false; |
| 298 | // The Following checks if the signed representation of Value is between |
| 299 | // -Threshold/2 and +Threshold/2 |
| 300 | bool largerThanThreshold = Threshold / 2 + Value >= Threshold; |
| 301 | return largerThanThreshold; |
| 302 | } |
Qining Lu | 253dc8a | 2015-06-22 10:10:23 -0700 | [diff] [blame] | 303 | |
Jim Stichnoth | dd842db | 2015-01-27 12:53:53 -0800 | [diff] [blame] | 304 | template <> |
| 305 | inline void ConstantInteger64::dump(const Cfg *, Ostream &Str) const { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 306 | if (!BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 307 | return; |
Jan Voung | bc00463 | 2014-09-16 15:09:10 -0700 | [diff] [blame] | 308 | assert(getType() == IceType_i64); |
| 309 | Str << static_cast<int64_t>(getValue()); |
Jim Stichnoth | cabfa30 | 2014-09-03 15:19:12 -0700 | [diff] [blame] | 310 | } |
| 311 | |
John Porto | 27fddcc | 2016-02-02 15:06:09 -0800 | [diff] [blame] | 312 | /// RelocOffset allows symbolic references in ConstantRelocatables' offsets, |
| 313 | /// e.g., 8 + LabelOffset, where label offset is the location (code or data) |
| 314 | /// of a Label that is only determinable during ELF emission. |
| 315 | class RelocOffset final { |
| 316 | RelocOffset(const RelocOffset &) = delete; |
| 317 | RelocOffset &operator=(const RelocOffset &) = delete; |
| 318 | |
| 319 | public: |
Jim Stichnoth | 3e32400 | 2016-03-08 16:18:40 -0800 | [diff] [blame] | 320 | template <typename T> static RelocOffset *create(T *AllocOwner) { |
| 321 | return new (AllocOwner->template allocate<RelocOffset>()) RelocOffset(); |
John Porto | 27fddcc | 2016-02-02 15:06:09 -0800 | [diff] [blame] | 322 | } |
| 323 | |
| 324 | static RelocOffset *create(GlobalContext *Ctx, RelocOffsetT Value) { |
| 325 | return new (Ctx->allocate<RelocOffset>()) RelocOffset(Value); |
| 326 | } |
| 327 | |
John Porto | 6e8d3fa | 2016-02-04 10:35:20 -0800 | [diff] [blame] | 328 | void setSubtract(bool Value) { Subtract = Value; } |
John Porto | 27fddcc | 2016-02-02 15:06:09 -0800 | [diff] [blame] | 329 | bool hasOffset() const { return HasOffset; } |
| 330 | |
| 331 | RelocOffsetT getOffset() const { |
| 332 | assert(HasOffset); |
| 333 | return Offset; |
| 334 | } |
| 335 | |
| 336 | void setOffset(const RelocOffsetT Value) { |
| 337 | assert(!HasOffset); |
John Porto | 6e8d3fa | 2016-02-04 10:35:20 -0800 | [diff] [blame] | 338 | if (Subtract) { |
| 339 | assert(Value != std::numeric_limits<RelocOffsetT>::lowest()); |
| 340 | Offset = -Value; |
| 341 | } else { |
| 342 | Offset = Value; |
| 343 | } |
John Porto | 27fddcc | 2016-02-02 15:06:09 -0800 | [diff] [blame] | 344 | HasOffset = true; |
| 345 | } |
| 346 | |
| 347 | private: |
| 348 | RelocOffset() = default; |
| 349 | explicit RelocOffset(RelocOffsetT Offset) { setOffset(Offset); } |
| 350 | |
John Porto | 6e8d3fa | 2016-02-04 10:35:20 -0800 | [diff] [blame] | 351 | bool Subtract = false; |
John Porto | 27fddcc | 2016-02-02 15:06:09 -0800 | [diff] [blame] | 352 | bool HasOffset = false; |
| 353 | RelocOffsetT Offset; |
| 354 | }; |
| 355 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 356 | /// RelocatableTuple bundles the parameters that are used to construct an |
| 357 | /// ConstantRelocatable. It is done this way so that ConstantRelocatable can fit |
| 358 | /// into the global constant pool template mechanism. |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 359 | class RelocatableTuple { |
Jim Stichnoth | c6ead20 | 2015-02-24 09:30:30 -0800 | [diff] [blame] | 360 | RelocatableTuple() = delete; |
Jim Stichnoth | 0795ba0 | 2014-10-01 14:23:01 -0700 | [diff] [blame] | 361 | RelocatableTuple &operator=(const RelocatableTuple &) = delete; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 362 | |
| 363 | public: |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 364 | RelocatableTuple(const RelocOffsetT Offset, |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 365 | const RelocOffsetArray &OffsetExpr, GlobalString Name) |
Jim Stichnoth | 98ba006 | 2016-03-07 09:26:22 -0800 | [diff] [blame] | 366 | : Offset(Offset), OffsetExpr(OffsetExpr), Name(Name) {} |
John Porto | 27fddcc | 2016-02-02 15:06:09 -0800 | [diff] [blame] | 367 | |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 368 | RelocatableTuple(const RelocOffsetT Offset, |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 369 | const RelocOffsetArray &OffsetExpr, GlobalString Name, |
| 370 | const std::string &EmitString) |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 371 | : Offset(Offset), OffsetExpr(OffsetExpr), Name(Name), |
Jim Stichnoth | 98ba006 | 2016-03-07 09:26:22 -0800 | [diff] [blame] | 372 | EmitString(EmitString) {} |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 373 | |
Jim Stichnoth | d2cb436 | 2014-11-20 11:24:42 -0800 | [diff] [blame] | 374 | RelocatableTuple(const RelocatableTuple &) = default; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 375 | |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 376 | const RelocOffsetT Offset; |
John Porto | 27fddcc | 2016-02-02 15:06:09 -0800 | [diff] [blame] | 377 | const RelocOffsetArray OffsetExpr; |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 378 | const GlobalString Name; |
| 379 | const std::string EmitString; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 380 | }; |
| 381 | |
Jim Stichnoth | d2cb436 | 2014-11-20 11:24:42 -0800 | [diff] [blame] | 382 | bool operator==(const RelocatableTuple &A, const RelocatableTuple &B); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 383 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 384 | /// ConstantRelocatable represents a symbolic constant combined with a fixed |
| 385 | /// offset. |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 386 | class ConstantRelocatable : public Constant { |
Jim Stichnoth | c6ead20 | 2015-02-24 09:30:30 -0800 | [diff] [blame] | 387 | ConstantRelocatable() = delete; |
Jim Stichnoth | 7b451a9 | 2014-10-15 14:39:23 -0700 | [diff] [blame] | 388 | ConstantRelocatable(const ConstantRelocatable &) = delete; |
| 389 | ConstantRelocatable &operator=(const ConstantRelocatable &) = delete; |
| 390 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 391 | public: |
Jim Stichnoth | 3e32400 | 2016-03-08 16:18:40 -0800 | [diff] [blame] | 392 | template <typename T> |
| 393 | static ConstantRelocatable *create(T *AllocOwner, Type Ty, |
Jim Stichnoth | b36757e | 2015-10-05 13:55:11 -0700 | [diff] [blame] | 394 | const RelocatableTuple &Tuple) { |
Jim Stichnoth | 3e32400 | 2016-03-08 16:18:40 -0800 | [diff] [blame] | 395 | return new (AllocOwner->template allocate<ConstantRelocatable>()) |
| 396 | ConstantRelocatable(Ty, Tuple.Offset, Tuple.OffsetExpr, Tuple.Name, |
| 397 | Tuple.EmitString); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 398 | } |
Jan Voung | fe14fb8 | 2014-10-13 15:56:32 -0700 | [diff] [blame] | 399 | |
John Porto | 27fddcc | 2016-02-02 15:06:09 -0800 | [diff] [blame] | 400 | RelocOffsetT getOffset() const { |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 401 | RelocOffsetT Ret = Offset; |
John Porto | 27fddcc | 2016-02-02 15:06:09 -0800 | [diff] [blame] | 402 | for (const auto *const OffsetReloc : OffsetExpr) { |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 403 | Ret += OffsetReloc->getOffset(); |
John Porto | 27fddcc | 2016-02-02 15:06:09 -0800 | [diff] [blame] | 404 | } |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 405 | return Ret; |
John Porto | 27fddcc | 2016-02-02 15:06:09 -0800 | [diff] [blame] | 406 | } |
| 407 | |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 408 | const std::string &getEmitString() const { return EmitString; } |
John Porto | 27fddcc | 2016-02-02 15:06:09 -0800 | [diff] [blame] | 409 | |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 410 | GlobalString getName() const { return Name; } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 411 | using Constant::emit; |
Jan Voung | 76bb0be | 2015-05-14 09:26:19 -0700 | [diff] [blame] | 412 | void emit(TargetLowering *Target) const final; |
Jim Stichnoth | 8ff4b28 | 2016-01-04 15:39:06 -0800 | [diff] [blame] | 413 | void emitWithoutPrefix(const TargetLowering *Target, |
| 414 | const char *Suffix = "") const; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 415 | using Constant::dump; |
Jim Stichnoth | b56c8f4 | 2014-09-26 09:28:46 -0700 | [diff] [blame] | 416 | void dump(const Cfg *Func, Ostream &Str) const override; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 417 | |
| 418 | static bool classof(const Operand *Operand) { |
| 419 | OperandKind Kind = Operand->getKind(); |
| 420 | return Kind == kConstRelocatable; |
| 421 | } |
| 422 | |
| 423 | private: |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 424 | ConstantRelocatable(Type Ty, const RelocOffsetT Offset, |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 425 | const RelocOffsetArray &OffsetExpr, GlobalString Name, |
| 426 | const std::string &EmitString) |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 427 | : Constant(kConstRelocatable, Ty), Offset(Offset), OffsetExpr(OffsetExpr), |
Jim Stichnoth | 98ba006 | 2016-03-07 09:26:22 -0800 | [diff] [blame] | 428 | Name(Name), EmitString(EmitString) {} |
John Porto | 27fddcc | 2016-02-02 15:06:09 -0800 | [diff] [blame] | 429 | |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 430 | const RelocOffsetT Offset; /// fixed, known offset to add |
| 431 | const RelocOffsetArray OffsetExpr; /// fixed, unknown offset to add |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 432 | const GlobalString Name; /// optional for debug/dump |
| 433 | const std::string EmitString; /// optional for textual emission |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 434 | }; |
| 435 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 436 | /// ConstantUndef represents an unspecified bit pattern. Although it is legal to |
| 437 | /// lower ConstantUndef to any value, backends should try to make code |
| 438 | /// generation deterministic by lowering ConstantUndefs to 0. |
Matt Wala | d8f4a7d | 2014-06-18 09:55:03 -0700 | [diff] [blame] | 439 | class ConstantUndef : public Constant { |
Jim Stichnoth | c6ead20 | 2015-02-24 09:30:30 -0800 | [diff] [blame] | 440 | ConstantUndef() = delete; |
Jim Stichnoth | 7b451a9 | 2014-10-15 14:39:23 -0700 | [diff] [blame] | 441 | ConstantUndef(const ConstantUndef &) = delete; |
| 442 | ConstantUndef &operator=(const ConstantUndef &) = delete; |
| 443 | |
Matt Wala | d8f4a7d | 2014-06-18 09:55:03 -0700 | [diff] [blame] | 444 | public: |
Jim Stichnoth | b36757e | 2015-10-05 13:55:11 -0700 | [diff] [blame] | 445 | static ConstantUndef *create(GlobalContext *Ctx, Type Ty) { |
Jim Stichnoth | b36757e | 2015-10-05 13:55:11 -0700 | [diff] [blame] | 446 | return new (Ctx->allocate<ConstantUndef>()) ConstantUndef(Ty); |
Matt Wala | d8f4a7d | 2014-06-18 09:55:03 -0700 | [diff] [blame] | 447 | } |
| 448 | |
| 449 | using Constant::emit; |
Jan Voung | 76bb0be | 2015-05-14 09:26:19 -0700 | [diff] [blame] | 450 | void emit(TargetLowering *Target) const final; |
Jim Stichnoth | 2e8bfbb | 2014-09-16 10:16:00 -0700 | [diff] [blame] | 451 | using Constant::dump; |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 452 | void dump(const Cfg *, Ostream &Str) const override { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 453 | if (BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 454 | Str << "undef"; |
| 455 | } |
Matt Wala | d8f4a7d | 2014-06-18 09:55:03 -0700 | [diff] [blame] | 456 | |
| 457 | static bool classof(const Operand *Operand) { |
| 458 | return Operand->getKind() == kConstUndef; |
| 459 | } |
| 460 | |
| 461 | private: |
Jim Stichnoth | b36757e | 2015-10-05 13:55:11 -0700 | [diff] [blame] | 462 | ConstantUndef(Type Ty) : Constant(kConstUndef, Ty) {} |
Matt Wala | d8f4a7d | 2014-06-18 09:55:03 -0700 | [diff] [blame] | 463 | }; |
| 464 | |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 465 | /// RegNumT is for holding target-specific register numbers, plus the sentinel |
Reed Kotler | 5fa0a5f | 2016-02-15 20:01:24 -0800 | [diff] [blame] | 466 | /// value if no register is assigned. Its public ctor allows direct use of enum |
| 467 | /// values, such as RegNumT(Reg_eax), but not things like RegNumT(Reg_eax+1). |
| 468 | /// This is to try to prevent inappropriate assumptions about enum ordering. If |
| 469 | /// needed, the fromInt() method can be used, such as when a RegNumT is based |
| 470 | /// on a bitvector index. |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 471 | class RegNumT { |
| 472 | public: |
| 473 | using BaseType = uint32_t; |
| 474 | RegNumT() = default; |
| 475 | RegNumT(const RegNumT &) = default; |
| 476 | template <typename AnyEnum> |
| 477 | RegNumT(AnyEnum Value, |
| 478 | typename std::enable_if<std::is_enum<AnyEnum>::value, int>::type = 0) |
| 479 | : Value(Value) { |
| 480 | validate(Value); |
| 481 | } |
| 482 | RegNumT &operator=(const RegNumT &) = default; |
| 483 | operator unsigned() const { return Value; } |
| 484 | /// Asserts that the register is valid, i.e. not NoRegisterValue. Note that |
| 485 | /// the ctor already does the target-specific limit check. |
| 486 | void assertIsValid() const { assert(Value != NoRegisterValue); } |
| 487 | static RegNumT fromInt(BaseType Value) { return RegNumT(Value); } |
| 488 | /// Marks cases that inappropriately add/subtract RegNumT values, and |
| 489 | /// therefore need to be fixed because they make assumptions about register |
| 490 | /// enum value ordering. TODO(stichnot): Remove fixme() as soon as all |
| 491 | /// current uses are fixed/removed. |
| 492 | static RegNumT fixme(BaseType Value) { return RegNumT(Value); } |
| 493 | /// The target's staticInit() method should call setLimit() to register the |
| 494 | /// upper bound of allowable values. |
| 495 | static void setLimit(BaseType Value) { |
| 496 | // Make sure it's only called once. |
| 497 | assert(Limit == 0); |
| 498 | assert(Value != 0); |
| 499 | Limit = Value; |
| 500 | } |
| 501 | // Define NoRegisterValue as an enum value so that it can be used as an |
| 502 | // argument for the public ctor if desired. |
| 503 | enum { NoRegisterValue = std::numeric_limits<BaseType>::max() }; |
Reed Kotler | 5fa0a5f | 2016-02-15 20:01:24 -0800 | [diff] [blame] | 504 | |
| 505 | bool hasValue() const { return Value != NoRegisterValue; } |
| 506 | bool hasNoValue() const { return !hasValue(); } |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 507 | |
| 508 | private: |
| 509 | BaseType Value = NoRegisterValue; |
| 510 | static BaseType Limit; |
| 511 | /// Private ctor called only by fromInt() and fixme(). |
| 512 | RegNumT(BaseType Value) : Value(Value) { validate(Value); } |
| 513 | /// The ctor calls this to validate against the target-supplied limit. |
| 514 | static void validate(BaseType Value) { |
| 515 | (void)Value; |
| 516 | assert(Value == NoRegisterValue || Value < Limit); |
| 517 | } |
| 518 | /// Disallow operators that inappropriately make assumptions about register |
| 519 | /// enum value ordering. |
| 520 | bool operator<(const RegNumT &) = delete; |
| 521 | bool operator<=(const RegNumT &) = delete; |
| 522 | bool operator>(const RegNumT &) = delete; |
| 523 | bool operator>=(const RegNumT &) = delete; |
| 524 | }; |
| 525 | |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 526 | /// RegNumBVIter wraps SmallBitVector so that instead of this pattern: |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 527 | /// |
| 528 | /// for (int i = V.find_first(); i != -1; i = V.find_next(i)) { |
| 529 | /// RegNumT RegNum = RegNumT::fromInt(i); |
| 530 | /// ... |
| 531 | /// } |
| 532 | /// |
| 533 | /// this cleaner pattern can be used: |
| 534 | /// |
| 535 | /// for (RegNumT RegNum : RegNumBVIter(V)) { |
| 536 | /// ... |
| 537 | /// } |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 538 | template <class B> class RegNumBVIterImpl { |
| 539 | using T = B; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 540 | static constexpr int Sentinel = -1; |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 541 | RegNumBVIterImpl() = delete; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 542 | |
| 543 | public: |
| 544 | class Iterator { |
| 545 | Iterator() = delete; |
| 546 | Iterator &operator=(const Iterator &) = delete; |
| 547 | |
| 548 | public: |
| 549 | explicit Iterator(const T &V) : V(V), Current(V.find_first()) {} |
| 550 | Iterator(const T &V, int Value) : V(V), Current(Value) {} |
| 551 | Iterator(const Iterator &) = default; |
| 552 | RegNumT operator*() { |
| 553 | assert(Current != Sentinel); |
| 554 | return RegNumT::fromInt(Current); |
| 555 | } |
| 556 | Iterator &operator++() { |
| 557 | assert(Current != Sentinel); |
| 558 | Current = V.find_next(Current); |
| 559 | return *this; |
| 560 | } |
| 561 | bool operator!=(Iterator &Other) { return Current != Other.Current; } |
| 562 | |
| 563 | private: |
| 564 | const T &V; |
| 565 | int Current; |
| 566 | }; |
| 567 | |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 568 | RegNumBVIterImpl(const RegNumBVIterImpl &) = default; |
| 569 | RegNumBVIterImpl &operator=(const RegNumBVIterImpl &) = delete; |
| 570 | explicit RegNumBVIterImpl(const T &V) : V(V) {} |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 571 | Iterator begin() { return Iterator(V); } |
| 572 | Iterator end() { return Iterator(V, Sentinel); } |
| 573 | |
| 574 | private: |
| 575 | const T &V; |
| 576 | }; |
| 577 | |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 578 | template <class B> RegNumBVIterImpl<B> RegNumBVIter(const B &BV) { |
| 579 | return RegNumBVIterImpl<B>(BV); |
| 580 | } |
| 581 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 582 | /// RegWeight is a wrapper for a uint32_t weight value, with a special value |
| 583 | /// that represents infinite weight, and an addWeight() method that ensures that |
| 584 | /// W+infinity=infinity. |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 585 | class RegWeight { |
| 586 | public: |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 587 | using BaseType = uint32_t; |
Jim Stichnoth | eafb56c | 2015-06-22 10:35:22 -0700 | [diff] [blame] | 588 | RegWeight() = default; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 589 | explicit RegWeight(BaseType Weight) : Weight(Weight) {} |
Jim Stichnoth | 7e57136 | 2015-01-09 11:43:26 -0800 | [diff] [blame] | 590 | RegWeight(const RegWeight &) = default; |
| 591 | RegWeight &operator=(const RegWeight &) = default; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 592 | constexpr static BaseType Inf = ~0; /// Force regalloc to give a register |
| 593 | constexpr static BaseType Zero = 0; /// Force regalloc NOT to give a register |
| 594 | constexpr static BaseType Max = Inf - 1; /// Max natural weight. |
| 595 | void addWeight(BaseType Delta) { |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 596 | if (Delta == Inf) |
| 597 | Weight = Inf; |
| 598 | else if (Weight != Inf) |
Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame] | 599 | if (Utils::add_overflow(Weight, Delta, &Weight) || Weight == Inf) |
| 600 | Weight = Max; |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 601 | } |
| 602 | void addWeight(const RegWeight &Other) { addWeight(Other.Weight); } |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 603 | void setWeight(BaseType Val) { Weight = Val; } |
| 604 | BaseType getWeight() const { return Weight; } |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 605 | |
| 606 | private: |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 607 | BaseType Weight = 0; |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 608 | }; |
| 609 | Ostream &operator<<(Ostream &Str, const RegWeight &W); |
| 610 | bool operator<(const RegWeight &A, const RegWeight &B); |
| 611 | bool operator<=(const RegWeight &A, const RegWeight &B); |
| 612 | bool operator==(const RegWeight &A, const RegWeight &B); |
| 613 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 614 | /// LiveRange is a set of instruction number intervals representing a variable's |
| 615 | /// live range. Generally there is one interval per basic block where the |
| 616 | /// variable is live, but adjacent intervals get coalesced into a single |
| 617 | /// interval. |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 618 | class LiveRange { |
| 619 | public: |
Manasij Mukherjee | 7cd926d | 2016-08-04 12:33:23 -0700 | [diff] [blame] | 620 | using RangeElementType = std::pair<InstNumberT, InstNumberT>; |
| 621 | /// RangeType is arena-allocated from the Cfg's allocator. |
| 622 | using RangeType = CfgVector<RangeElementType>; |
Jim Stichnoth | eafb56c | 2015-06-22 10:35:22 -0700 | [diff] [blame] | 623 | LiveRange() = default; |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 624 | /// Special constructor for building a kill set. The advantage is that we can |
| 625 | /// reserve the right amount of space in advance. |
Andrew Scull | 00741a0 | 2015-09-16 19:04:09 -0700 | [diff] [blame] | 626 | explicit LiveRange(const CfgVector<InstNumberT> &Kills) { |
Jim Stichnoth | 2a7fcbb | 2014-12-04 11:45:03 -0800 | [diff] [blame] | 627 | Range.reserve(Kills.size()); |
| 628 | for (InstNumberT I : Kills) |
| 629 | addSegment(I, I); |
| 630 | } |
Jim Stichnoth | 87ff3a1 | 2014-11-14 10:27:29 -0800 | [diff] [blame] | 631 | LiveRange(const LiveRange &) = default; |
| 632 | LiveRange &operator=(const LiveRange &) = default; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 633 | |
| 634 | void reset() { |
| 635 | Range.clear(); |
Jim Stichnoth | 037fa1d | 2014-10-07 11:09:33 -0700 | [diff] [blame] | 636 | untrim(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 637 | } |
Manasij Mukherjee | 7cd926d | 2016-08-04 12:33:23 -0700 | [diff] [blame] | 638 | void addSegment(InstNumberT Start, InstNumberT End, CfgNode *Node = nullptr); |
| 639 | void addSegment(RangeElementType Segment, CfgNode *Node = nullptr) { |
| 640 | addSegment(Segment.first, Segment.second, Node); |
| 641 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 642 | |
| 643 | bool endsBefore(const LiveRange &Other) const; |
Jim Stichnoth | 037fa1d | 2014-10-07 11:09:33 -0700 | [diff] [blame] | 644 | bool overlaps(const LiveRange &Other, bool UseTrimmed = false) const; |
| 645 | bool overlapsInst(InstNumberT OtherBegin, bool UseTrimmed = false) const; |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 646 | bool containsValue(InstNumberT Value, bool IsDest) const; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 647 | bool isEmpty() const { return Range.empty(); } |
| 648 | InstNumberT getStart() const { |
| 649 | return Range.empty() ? -1 : Range.begin()->first; |
| 650 | } |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 651 | InstNumberT getEnd() const { |
| 652 | return Range.empty() ? -1 : Range.rbegin()->second; |
| 653 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 654 | |
Jim Stichnoth | 037fa1d | 2014-10-07 11:09:33 -0700 | [diff] [blame] | 655 | void untrim() { TrimmedBegin = Range.begin(); } |
| 656 | void trim(InstNumberT Lower); |
| 657 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 658 | void dump(Ostream &Str) const; |
| 659 | |
Manasij Mukherjee | 7cd926d | 2016-08-04 12:33:23 -0700 | [diff] [blame] | 660 | SizeT getNumSegments() const { return Range.size(); } |
| 661 | |
| 662 | const RangeType &getSegments() const { return Range; } |
| 663 | CfgNode *getNodeForSegment(InstNumberT Begin) { |
| 664 | auto Iter = NodeMap.find(Begin); |
| 665 | assert(Iter != NodeMap.end()); |
| 666 | return Iter->second; |
| 667 | } |
| 668 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 669 | private: |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 670 | RangeType Range; |
Manasij Mukherjee | 7cd926d | 2016-08-04 12:33:23 -0700 | [diff] [blame] | 671 | CfgUnorderedMap<InstNumberT, CfgNode *> NodeMap; |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 672 | /// TrimmedBegin is an optimization for the overlaps() computation. Since the |
| 673 | /// linear-scan algorithm always calls it as overlaps(Cur) and Cur advances |
| 674 | /// monotonically according to live range start, we can optimize overlaps() by |
| 675 | /// ignoring all segments that end before the start of Cur's range. The |
| 676 | /// linear-scan code enables this by calling trim() on the ranges of interest |
| 677 | /// as Cur advances. Note that linear-scan also has to initialize TrimmedBegin |
| 678 | /// at the beginning by calling untrim(). |
Jim Stichnoth | 037fa1d | 2014-10-07 11:09:33 -0700 | [diff] [blame] | 679 | RangeType::const_iterator TrimmedBegin; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 680 | }; |
| 681 | |
| 682 | Ostream &operator<<(Ostream &Str, const LiveRange &L); |
| 683 | |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 684 | /// Variable represents an operand that is register-allocated or |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 685 | /// stack-allocated. If it is register-allocated, it will ultimately have a |
Jim Stichnoth | e343e06 | 2016-06-28 21:40:33 -0700 | [diff] [blame] | 686 | /// valid RegNum field. |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 687 | class Variable : public Operand { |
Jim Stichnoth | c6ead20 | 2015-02-24 09:30:30 -0800 | [diff] [blame] | 688 | Variable() = delete; |
Jim Stichnoth | 0795ba0 | 2014-10-01 14:23:01 -0700 | [diff] [blame] | 689 | Variable(const Variable &) = delete; |
| 690 | Variable &operator=(const Variable &) = delete; |
Jim Stichnoth | 800dab2 | 2014-09-20 12:25:02 -0700 | [diff] [blame] | 691 | |
Andrew Scull | 6d47bcd | 2015-09-17 17:10:05 -0700 | [diff] [blame] | 692 | enum RegRequirement : uint8_t { |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 693 | RR_MayHaveRegister, |
| 694 | RR_MustHaveRegister, |
| 695 | RR_MustNotHaveRegister, |
| 696 | }; |
| 697 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 698 | public: |
Jim Stichnoth | 9a04c07 | 2014-12-11 15:51:42 -0800 | [diff] [blame] | 699 | static Variable *create(Cfg *Func, Type Ty, SizeT Index) { |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 700 | return new (Func->allocate<Variable>()) |
| 701 | Variable(Func, kVariable, Ty, Index); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 702 | } |
| 703 | |
| 704 | SizeT getIndex() const { return Number; } |
Jim Stichnoth | a91c341 | 2016-04-05 15:31:43 -0700 | [diff] [blame] | 705 | std::string getName() const { |
| 706 | if (Name.hasStdString()) |
| 707 | return Name.toString(); |
| 708 | return "__" + std::to_string(getIndex()); |
| 709 | } |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 710 | virtual void setName(const Cfg *Func, const std::string &NewName) { |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 711 | if (NewName.empty()) |
| 712 | return; |
| 713 | Name = VariableString::createWithString(Func, NewName); |
Karl Schimpf | c132b76 | 2014-09-11 09:43:47 -0700 | [diff] [blame] | 714 | } |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 715 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 716 | bool getIsArg() const { return IsArgument; } |
Andrew Scull | 6d47bcd | 2015-09-17 17:10:05 -0700 | [diff] [blame] | 717 | virtual void setIsArg(bool Val = true) { IsArgument = Val; } |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 718 | bool getIsImplicitArg() const { return IsImplicitArgument; } |
| 719 | void setIsImplicitArg(bool Val = true) { IsImplicitArgument = Val; } |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 720 | |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 721 | void setIgnoreLiveness() { IgnoreLiveness = true; } |
Jim Stichnoth | cc89c95 | 2016-03-31 11:55:23 -0700 | [diff] [blame] | 722 | bool getIgnoreLiveness() const { |
| 723 | return IgnoreLiveness || IsRematerializable; |
| 724 | } |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 725 | |
Jim Stichnoth | b9a8472 | 2016-08-01 13:18:36 -0700 | [diff] [blame] | 726 | /// Returns true if the variable either has a definite stack offset, or has |
| 727 | /// the UndeterminedStackOffset such that it is guaranteed to have a definite |
| 728 | /// stack offset at emission time. |
Jim Stichnoth | fe62f0a | 2016-07-10 05:13:18 -0700 | [diff] [blame] | 729 | bool hasStackOffset() const { return StackOffset != InvalidStackOffset; } |
Jim Stichnoth | b9a8472 | 2016-08-01 13:18:36 -0700 | [diff] [blame] | 730 | /// Returns true if the variable has a stack offset that is known at this |
| 731 | /// time. |
| 732 | bool hasKnownStackOffset() const { |
| 733 | return StackOffset != InvalidStackOffset && |
| 734 | StackOffset != UndeterminedStackOffset; |
| 735 | } |
Jim Stichnoth | fe62f0a | 2016-07-10 05:13:18 -0700 | [diff] [blame] | 736 | int32_t getStackOffset() const { |
Jim Stichnoth | b9a8472 | 2016-08-01 13:18:36 -0700 | [diff] [blame] | 737 | assert(hasKnownStackOffset()); |
Jim Stichnoth | fe62f0a | 2016-07-10 05:13:18 -0700 | [diff] [blame] | 738 | return StackOffset; |
| 739 | } |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 740 | void setStackOffset(int32_t Offset) { StackOffset = Offset; } |
Jim Stichnoth | b9a8472 | 2016-08-01 13:18:36 -0700 | [diff] [blame] | 741 | /// Set a "placeholder" stack offset before its actual offset has been |
| 742 | /// determined. |
| 743 | void setHasStackOffset() { |
| 744 | if (!hasStackOffset()) |
| 745 | StackOffset = UndeterminedStackOffset; |
| 746 | } |
Jim Stichnoth | 238b4c1 | 2015-10-01 07:46:38 -0700 | [diff] [blame] | 747 | /// Returns the variable's stack offset in symbolic form, to improve |
| 748 | /// readability in DecorateAsm mode. |
Jim Stichnoth | a91c341 | 2016-04-05 15:31:43 -0700 | [diff] [blame] | 749 | std::string getSymbolicStackOffset() const { |
Jim Stichnoth | 98ba006 | 2016-03-07 09:26:22 -0800 | [diff] [blame] | 750 | if (!BuildDefs::dump()) |
| 751 | return ""; |
Jim Stichnoth | 00b9edb | 2016-06-25 10:14:39 -0700 | [diff] [blame] | 752 | return ".L$lv$" + getName(); |
Jim Stichnoth | 238b4c1 | 2015-10-01 07:46:38 -0700 | [diff] [blame] | 753 | } |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 754 | |
Reed Kotler | 5fa0a5f | 2016-02-15 20:01:24 -0800 | [diff] [blame] | 755 | bool hasReg() const { return getRegNum().hasValue(); } |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 756 | RegNumT getRegNum() const { return RegNum; } |
| 757 | void setRegNum(RegNumT NewRegNum) { |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 758 | // Regnum shouldn't be set more than once. |
| 759 | assert(!hasReg() || RegNum == NewRegNum); |
| 760 | RegNum = NewRegNum; |
| 761 | } |
Reed Kotler | 5fa0a5f | 2016-02-15 20:01:24 -0800 | [diff] [blame] | 762 | bool hasRegTmp() const { return getRegNumTmp().hasValue(); } |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 763 | RegNumT getRegNumTmp() const { return RegNumTmp; } |
| 764 | void setRegNumTmp(RegNumT NewRegNum) { RegNumTmp = NewRegNum; } |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 765 | |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 766 | RegWeight getWeight(const Cfg *Func) const; |
| 767 | |
| 768 | void setMustHaveReg() { RegRequirement = RR_MustHaveRegister; } |
| 769 | bool mustHaveReg() const { return RegRequirement == RR_MustHaveRegister; } |
| 770 | void setMustNotHaveReg() { RegRequirement = RR_MustNotHaveRegister; } |
| 771 | bool mustNotHaveReg() const { |
| 772 | return RegRequirement == RR_MustNotHaveRegister; |
| 773 | } |
Jim Stichnoth | b9a8472 | 2016-08-01 13:18:36 -0700 | [diff] [blame] | 774 | bool mayHaveReg() const { return RegRequirement == RR_MayHaveRegister; } |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 775 | void setRematerializable(RegNumT NewRegNum, int32_t NewOffset) { |
David Sehr | 4318a41 | 2015-11-11 15:01:55 -0800 | [diff] [blame] | 776 | IsRematerializable = true; |
| 777 | setRegNum(NewRegNum); |
| 778 | setStackOffset(NewOffset); |
| 779 | setMustHaveReg(); |
| 780 | } |
| 781 | bool isRematerializable() const { return IsRematerializable; } |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 782 | |
Jim Stichnoth | c59288b | 2015-11-09 11:38:40 -0800 | [diff] [blame] | 783 | void setRegClass(uint8_t RC) { RegisterClass = static_cast<RegClass>(RC); } |
| 784 | RegClass getRegClass() const { return RegisterClass; } |
| 785 | |
Jim Stichnoth | 5ce0abb | 2014-10-15 10:16:54 -0700 | [diff] [blame] | 786 | LiveRange &getLiveRange() { return Live; } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 787 | const LiveRange &getLiveRange() const { return Live; } |
| 788 | void setLiveRange(const LiveRange &Range) { Live = Range; } |
| 789 | void resetLiveRange() { Live.reset(); } |
Manasij Mukherjee | 7cd926d | 2016-08-04 12:33:23 -0700 | [diff] [blame] | 790 | void addLiveRange(InstNumberT Start, InstNumberT End, |
| 791 | CfgNode *Node = nullptr) { |
Jim Stichnoth | f9df452 | 2015-08-06 17:50:14 -0700 | [diff] [blame] | 792 | assert(!getIgnoreLiveness()); |
Manasij Mukherjee | 7cd926d | 2016-08-04 12:33:23 -0700 | [diff] [blame] | 793 | Live.addSegment(Start, End, Node); |
Jim Stichnoth | c6ead20 | 2015-02-24 09:30:30 -0800 | [diff] [blame] | 794 | } |
Jim Stichnoth | 037fa1d | 2014-10-07 11:09:33 -0700 | [diff] [blame] | 795 | void trimLiveRange(InstNumberT Start) { Live.trim(Start); } |
| 796 | void untrimLiveRange() { Live.untrim(); } |
Jim Stichnoth | 5ce0abb | 2014-10-15 10:16:54 -0700 | [diff] [blame] | 797 | bool rangeEndsBefore(const Variable *Other) const { |
| 798 | return Live.endsBefore(Other->Live); |
| 799 | } |
| 800 | bool rangeOverlaps(const Variable *Other) const { |
Jim Stichnoth | 5bff61c | 2015-10-28 09:26:00 -0700 | [diff] [blame] | 801 | constexpr bool UseTrimmed = true; |
Jim Stichnoth | 5ce0abb | 2014-10-15 10:16:54 -0700 | [diff] [blame] | 802 | return Live.overlaps(Other->Live, UseTrimmed); |
| 803 | } |
| 804 | bool rangeOverlapsStart(const Variable *Other) const { |
Jim Stichnoth | 5bff61c | 2015-10-28 09:26:00 -0700 | [diff] [blame] | 805 | constexpr bool UseTrimmed = true; |
Jim Stichnoth | 5ce0abb | 2014-10-15 10:16:54 -0700 | [diff] [blame] | 806 | return Live.overlapsInst(Other->Live.getStart(), UseTrimmed); |
| 807 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 808 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 809 | /// Creates a temporary copy of the variable with a different type. Used |
| 810 | /// primarily for syntactic correctness of textual assembly emission. Note |
| 811 | /// that only basic information is copied, in particular not IsArgument, |
| 812 | /// IsImplicitArgument, IgnoreLiveness, RegNumTmp, Live, LoVar, HiVar, |
Reed Kotler | 5fa0a5f | 2016-02-15 20:01:24 -0800 | [diff] [blame] | 813 | /// VarsReal. If NewRegNum.hasValue(), then that register assignment is made |
Jim Stichnoth | 5bff61c | 2015-10-28 09:26:00 -0700 | [diff] [blame] | 814 | /// instead of copying the existing assignment. |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 815 | const Variable *asType(const Cfg *Func, Type Ty, RegNumT NewRegNum) const; |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 816 | |
Jim Stichnoth | b56c8f4 | 2014-09-26 09:28:46 -0700 | [diff] [blame] | 817 | void emit(const Cfg *Func) const override; |
Jim Stichnoth | 2e8bfbb | 2014-09-16 10:16:00 -0700 | [diff] [blame] | 818 | using Operand::dump; |
Jim Stichnoth | b56c8f4 | 2014-09-26 09:28:46 -0700 | [diff] [blame] | 819 | void dump(const Cfg *Func, Ostream &Str) const override; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 820 | |
Jan Voung | 28068ad | 2015-07-31 12:58:46 -0700 | [diff] [blame] | 821 | /// Return reg num of base register, if different from stack/frame register. |
Reed Kotler | 5fa0a5f | 2016-02-15 20:01:24 -0800 | [diff] [blame] | 822 | virtual RegNumT getBaseRegNum() const { return RegNumT(); } |
Jan Voung | 28068ad | 2015-07-31 12:58:46 -0700 | [diff] [blame] | 823 | |
Jim Stichnoth | fe62f0a | 2016-07-10 05:13:18 -0700 | [diff] [blame] | 824 | /// Access the LinkedTo field. |
| 825 | void setLinkedTo(Variable *Var) { LinkedTo = Var; } |
| 826 | Variable *getLinkedTo() const { return LinkedTo; } |
| 827 | /// Follow the LinkedTo chain up to the furthest ancestor. |
| 828 | Variable *getLinkedToRoot() const { |
| 829 | Variable *Root = LinkedTo; |
| 830 | if (Root == nullptr) |
| 831 | return nullptr; |
| 832 | while (Root->LinkedTo != nullptr) |
| 833 | Root = Root->LinkedTo; |
| 834 | return Root; |
Jim Stichnoth | e343e06 | 2016-06-28 21:40:33 -0700 | [diff] [blame] | 835 | } |
Jim Stichnoth | b9a8472 | 2016-08-01 13:18:36 -0700 | [diff] [blame] | 836 | /// Follow the LinkedTo chain up to the furthest stack-allocated ancestor. |
| 837 | /// This is only certain to be accurate after register allocation and stack |
| 838 | /// slot assignment have completed. |
| 839 | Variable *getLinkedToStackRoot() const { |
| 840 | Variable *FurthestStackVar = nullptr; |
| 841 | for (Variable *Root = LinkedTo; Root != nullptr; Root = Root->LinkedTo) { |
| 842 | if (!Root->hasReg() && Root->hasStackOffset()) { |
| 843 | FurthestStackVar = Root; |
| 844 | } |
| 845 | } |
| 846 | return FurthestStackVar; |
| 847 | } |
Jim Stichnoth | e343e06 | 2016-06-28 21:40:33 -0700 | [diff] [blame] | 848 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 849 | static bool classof(const Operand *Operand) { |
Jim Stichnoth | 800dab2 | 2014-09-20 12:25:02 -0700 | [diff] [blame] | 850 | OperandKind Kind = Operand->getKind(); |
Andrew Scull | 6ef7949 | 2015-09-09 15:50:42 -0700 | [diff] [blame] | 851 | return Kind >= kVariable && Kind <= kVariable_Max; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 852 | } |
| 853 | |
Sagar Thakur | e160ed9 | 2016-05-30 07:54:47 -0700 | [diff] [blame] | 854 | SizeT hashValue() const override { return std::hash<SizeT>()(getIndex()); } |
Manasij Mukherjee | 032c315 | 2016-05-24 14:25:04 -0700 | [diff] [blame] | 855 | |
Jim Stichnoth | 800dab2 | 2014-09-20 12:25:02 -0700 | [diff] [blame] | 856 | protected: |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 857 | Variable(const Cfg *Func, OperandKind K, Type Ty, SizeT Index) |
Jim Stichnoth | c59288b | 2015-11-09 11:38:40 -0800 | [diff] [blame] | 858 | : Operand(K, Ty), Number(Index), |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 859 | Name(VariableString::createWithoutString(Func)), |
Jim Stichnoth | c59288b | 2015-11-09 11:38:40 -0800 | [diff] [blame] | 860 | RegisterClass(static_cast<RegClass>(Ty)) { |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 861 | Vars = VarsReal; |
| 862 | Vars[0] = this; |
| 863 | NumVars = 1; |
| 864 | } |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 865 | /// Number is unique across all variables, and is used as a (bit)vector index |
| 866 | /// for liveness analysis. |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 867 | const SizeT Number; |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 868 | VariableString Name; |
Jim Stichnoth | eafb56c | 2015-06-22 10:35:22 -0700 | [diff] [blame] | 869 | bool IsArgument = false; |
| 870 | bool IsImplicitArgument = false; |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 871 | /// IgnoreLiveness means that the variable should be ignored when constructing |
| 872 | /// and validating live ranges. This is usually reserved for the stack |
Jim Stichnoth | 6966055 | 2015-09-18 06:41:02 -0700 | [diff] [blame] | 873 | /// pointer and other physical registers specifically referenced by name. |
Jim Stichnoth | eafb56c | 2015-06-22 10:35:22 -0700 | [diff] [blame] | 874 | bool IgnoreLiveness = false; |
David Sehr | 4318a41 | 2015-11-11 15:01:55 -0800 | [diff] [blame] | 875 | // If IsRematerializable, RegNum keeps track of which register (stack or frame |
| 876 | // pointer), and StackOffset is the known offset from that register. |
| 877 | bool IsRematerializable = false; |
Andrew Scull | 6d47bcd | 2015-09-17 17:10:05 -0700 | [diff] [blame] | 878 | RegRequirement RegRequirement = RR_MayHaveRegister; |
Jim Stichnoth | c59288b | 2015-11-09 11:38:40 -0800 | [diff] [blame] | 879 | RegClass RegisterClass; |
Reed Kotler | 5fa0a5f | 2016-02-15 20:01:24 -0800 | [diff] [blame] | 880 | /// RegNum is the allocated register, (as long as RegNum.hasValue() is true). |
| 881 | RegNumT RegNum; |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 882 | /// RegNumTmp is the tentative assignment during register allocation. |
Reed Kotler | 5fa0a5f | 2016-02-15 20:01:24 -0800 | [diff] [blame] | 883 | RegNumT RegNumTmp; |
Jim Stichnoth | b9a8472 | 2016-08-01 13:18:36 -0700 | [diff] [blame] | 884 | static constexpr int32_t InvalidStackOffset = |
| 885 | std::numeric_limits<int32_t>::min(); |
| 886 | static constexpr int32_t UndeterminedStackOffset = |
| 887 | 1 + std::numeric_limits<int32_t>::min(); |
Andrew Scull | 6d47bcd | 2015-09-17 17:10:05 -0700 | [diff] [blame] | 888 | /// StackOffset is the canonical location on stack (only if |
Reed Kotler | 5fa0a5f | 2016-02-15 20:01:24 -0800 | [diff] [blame] | 889 | /// RegNum.hasNoValue() || IsArgument). |
Jim Stichnoth | fe62f0a | 2016-07-10 05:13:18 -0700 | [diff] [blame] | 890 | int32_t StackOffset = InvalidStackOffset; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 891 | LiveRange Live; |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 892 | /// VarsReal (and Operand::Vars) are set up such that Vars[0] == this. |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 893 | Variable *VarsReal[1]; |
Jim Stichnoth | e343e06 | 2016-06-28 21:40:33 -0700 | [diff] [blame] | 894 | /// This Variable may be "linked" to another Variable, such that if neither |
| 895 | /// Variable gets a register, they are guaranteed to share a stack location. |
Jim Stichnoth | fe62f0a | 2016-07-10 05:13:18 -0700 | [diff] [blame] | 896 | Variable *LinkedTo = nullptr; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 897 | }; |
| 898 | |
Andrew Scull | 6d47bcd | 2015-09-17 17:10:05 -0700 | [diff] [blame] | 899 | // Variable64On32 represents a 64-bit variable on a 32-bit architecture. In |
| 900 | // this situation the variable must be split into a low and a high word. |
| 901 | class Variable64On32 : public Variable { |
| 902 | Variable64On32() = delete; |
| 903 | Variable64On32(const Variable64On32 &) = delete; |
| 904 | Variable64On32 &operator=(const Variable64On32 &) = delete; |
| 905 | |
| 906 | public: |
| 907 | static Variable64On32 *create(Cfg *Func, Type Ty, SizeT Index) { |
John Porto | a83bfde | 2015-09-18 08:43:02 -0700 | [diff] [blame] | 908 | return new (Func->allocate<Variable64On32>()) |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 909 | Variable64On32(Func, kVariable64On32, Ty, Index); |
Andrew Scull | 6d47bcd | 2015-09-17 17:10:05 -0700 | [diff] [blame] | 910 | } |
| 911 | |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 912 | void setName(const Cfg *Func, const std::string &NewName) override { |
Andrew Scull | 6d47bcd | 2015-09-17 17:10:05 -0700 | [diff] [blame] | 913 | Variable::setName(Func, NewName); |
| 914 | if (LoVar && HiVar) { |
Jim Stichnoth | a91c341 | 2016-04-05 15:31:43 -0700 | [diff] [blame] | 915 | LoVar->setName(Func, getName() + "__lo"); |
| 916 | HiVar->setName(Func, getName() + "__hi"); |
Andrew Scull | 6d47bcd | 2015-09-17 17:10:05 -0700 | [diff] [blame] | 917 | } |
| 918 | } |
| 919 | |
| 920 | void setIsArg(bool Val = true) override { |
| 921 | Variable::setIsArg(Val); |
| 922 | if (LoVar && HiVar) { |
| 923 | LoVar->setIsArg(Val); |
| 924 | HiVar->setIsArg(Val); |
| 925 | } |
| 926 | } |
| 927 | |
| 928 | Variable *getLo() const { |
| 929 | assert(LoVar != nullptr); |
| 930 | return LoVar; |
| 931 | } |
| 932 | Variable *getHi() const { |
| 933 | assert(HiVar != nullptr); |
| 934 | return HiVar; |
| 935 | } |
| 936 | |
| 937 | void initHiLo(Cfg *Func) { |
| 938 | assert(LoVar == nullptr); |
| 939 | assert(HiVar == nullptr); |
| 940 | LoVar = Func->makeVariable(IceType_i32); |
| 941 | HiVar = Func->makeVariable(IceType_i32); |
| 942 | LoVar->setIsArg(getIsArg()); |
| 943 | HiVar->setIsArg(getIsArg()); |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 944 | if (BuildDefs::dump()) { |
Jim Stichnoth | a91c341 | 2016-04-05 15:31:43 -0700 | [diff] [blame] | 945 | LoVar->setName(Func, getName() + "__lo"); |
| 946 | HiVar->setName(Func, getName() + "__hi"); |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 947 | } |
Andrew Scull | 6d47bcd | 2015-09-17 17:10:05 -0700 | [diff] [blame] | 948 | } |
| 949 | |
| 950 | static bool classof(const Operand *Operand) { |
| 951 | OperandKind Kind = Operand->getKind(); |
| 952 | return Kind == kVariable64On32; |
| 953 | } |
| 954 | |
| 955 | protected: |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 956 | Variable64On32(const Cfg *Func, OperandKind K, Type Ty, SizeT Index) |
| 957 | : Variable(Func, K, Ty, Index) { |
Andrew Scull | 6d47bcd | 2015-09-17 17:10:05 -0700 | [diff] [blame] | 958 | assert(typeWidthInBytes(Ty) == 8); |
| 959 | } |
| 960 | |
| 961 | Variable *LoVar = nullptr; |
| 962 | Variable *HiVar = nullptr; |
| 963 | }; |
| 964 | |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 965 | enum MetadataKind { |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 966 | VMK_Uses, /// Track only uses, not defs |
| 967 | VMK_SingleDefs, /// Track uses+defs, but only record single def |
| 968 | VMK_All /// Track uses+defs, including full def list |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 969 | }; |
Andrew Scull | 00741a0 | 2015-09-16 19:04:09 -0700 | [diff] [blame] | 970 | using InstDefList = CfgVector<const Inst *>; |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 971 | |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 972 | /// VariableTracking tracks the metadata for a single variable. It is |
| 973 | /// only meant to be used internally by VariablesMetadata. |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 974 | class VariableTracking { |
| 975 | public: |
| 976 | enum MultiDefState { |
| 977 | // TODO(stichnot): Consider using just a simple counter. |
| 978 | MDS_Unknown, |
| 979 | MDS_SingleDef, |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 980 | MDS_MultiDefSingleBlock, |
| 981 | MDS_MultiDefMultiBlock |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 982 | }; |
Jim Stichnoth | cc89c95 | 2016-03-31 11:55:23 -0700 | [diff] [blame] | 983 | enum MultiBlockState { |
| 984 | MBS_Unknown, // Not yet initialized, so be conservative |
| 985 | MBS_NoUses, // Known to have no uses |
| 986 | MBS_SingleBlock, // All uses in are in a single block |
| 987 | MBS_MultiBlock // Several uses across several blocks |
| 988 | }; |
Jim Stichnoth | eafb56c | 2015-06-22 10:35:22 -0700 | [diff] [blame] | 989 | VariableTracking() = default; |
Jim Stichnoth | 7e57136 | 2015-01-09 11:43:26 -0800 | [diff] [blame] | 990 | VariableTracking(const VariableTracking &) = default; |
Jim Stichnoth | cc89c95 | 2016-03-31 11:55:23 -0700 | [diff] [blame] | 991 | VariableTracking &operator=(const VariableTracking &) = default; |
| 992 | VariableTracking(MultiBlockState MultiBlock) : MultiBlock(MultiBlock) {} |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 993 | MultiDefState getMultiDef() const { return MultiDef; } |
| 994 | MultiBlockState getMultiBlock() const { return MultiBlock; } |
Jim Stichnoth | 48e3ae5 | 2015-10-01 13:33:35 -0700 | [diff] [blame] | 995 | const Inst *getFirstDefinitionSingleBlock() const; |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 996 | const Inst *getSingleDefinition() const; |
Jim Stichnoth | 48e3ae5 | 2015-10-01 13:33:35 -0700 | [diff] [blame] | 997 | const Inst *getFirstDefinition() const; |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 998 | const InstDefList &getLatterDefinitions() const { return Definitions; } |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 999 | CfgNode *getNode() const { return SingleUseNode; } |
Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame] | 1000 | RegWeight getUseWeight() const { return UseWeight; } |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 1001 | void markUse(MetadataKind TrackingKind, const Inst *Instr, CfgNode *Node, |
| 1002 | bool IsImplicit); |
| 1003 | void markDef(MetadataKind TrackingKind, const Inst *Instr, CfgNode *Node); |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 1004 | |
| 1005 | private: |
Jim Stichnoth | eafb56c | 2015-06-22 10:35:22 -0700 | [diff] [blame] | 1006 | MultiDefState MultiDef = MDS_Unknown; |
| 1007 | MultiBlockState MultiBlock = MBS_Unknown; |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 1008 | CfgNode *SingleUseNode = nullptr; |
| 1009 | CfgNode *SingleDefNode = nullptr; |
Jim Stichnoth | 48e3ae5 | 2015-10-01 13:33:35 -0700 | [diff] [blame] | 1010 | /// All definitions of the variable are collected in Definitions[] (except for |
| 1011 | /// the earliest definition), in increasing order of instruction number. |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 1012 | InstDefList Definitions; /// Only used if Kind==VMK_All |
Jim Stichnoth | 48e3ae5 | 2015-10-01 13:33:35 -0700 | [diff] [blame] | 1013 | const Inst *FirstOrSingleDefinition = nullptr; |
Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame] | 1014 | RegWeight UseWeight; |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 1015 | }; |
| 1016 | |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 1017 | /// VariablesMetadata analyzes and summarizes the metadata for the complete set |
| 1018 | /// of Variables. |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 1019 | class VariablesMetadata { |
Jim Stichnoth | c6ead20 | 2015-02-24 09:30:30 -0800 | [diff] [blame] | 1020 | VariablesMetadata() = delete; |
Jim Stichnoth | 7b451a9 | 2014-10-15 14:39:23 -0700 | [diff] [blame] | 1021 | VariablesMetadata(const VariablesMetadata &) = delete; |
| 1022 | VariablesMetadata &operator=(const VariablesMetadata &) = delete; |
| 1023 | |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 1024 | public: |
Jim Stichnoth | c6ead20 | 2015-02-24 09:30:30 -0800 | [diff] [blame] | 1025 | explicit VariablesMetadata(const Cfg *Func) : Func(Func) {} |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1026 | /// Initialize the state by traversing all instructions/variables in the CFG. |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 1027 | void init(MetadataKind TrackingKind); |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1028 | /// Add a single node. This is called by init(), and can be called |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 1029 | /// incrementally from elsewhere, e.g. after edge-splitting. |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 1030 | void addNode(CfgNode *Node); |
Jim Stichnoth | 48e3ae5 | 2015-10-01 13:33:35 -0700 | [diff] [blame] | 1031 | MetadataKind getKind() const { return Kind; } |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1032 | /// Returns whether the given Variable is tracked in this object. It should |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 1033 | /// only return false if changes were made to the CFG after running init(), in |
| 1034 | /// which case the state is stale and the results shouldn't be trusted (but it |
| 1035 | /// may be OK e.g. for dumping). |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 1036 | bool isTracked(const Variable *Var) const { |
| 1037 | return Var->getIndex() < Metadata.size(); |
| 1038 | } |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 1039 | |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 1040 | /// Returns whether the given Variable has multiple definitions. |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 1041 | bool isMultiDef(const Variable *Var) const; |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1042 | /// Returns the first definition instruction of the given Variable. This is |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 1043 | /// only valid for variables whose definitions are all within the same block, |
| 1044 | /// e.g. T after the lowered sequence "T=B; T+=C; A=T", for which |
Jim Stichnoth | 48e3ae5 | 2015-10-01 13:33:35 -0700 | [diff] [blame] | 1045 | /// getFirstDefinitionSingleBlock(T) would return the "T=B" instruction. For |
| 1046 | /// variables with definitions span multiple blocks, nullptr is returned. |
| 1047 | const Inst *getFirstDefinitionSingleBlock(const Variable *Var) const; |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1048 | /// Returns the definition instruction of the given Variable, when the |
| 1049 | /// variable has exactly one definition. Otherwise, nullptr is returned. |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 1050 | const Inst *getSingleDefinition(const Variable *Var) const; |
Jim Stichnoth | 48e3ae5 | 2015-10-01 13:33:35 -0700 | [diff] [blame] | 1051 | /// getFirstDefinition() and getLatterDefinitions() are used together to |
| 1052 | /// return the complete set of instructions that define the given Variable, |
| 1053 | /// regardless of whether the definitions are within the same block (in |
| 1054 | /// contrast to getFirstDefinitionSingleBlock). |
| 1055 | const Inst *getFirstDefinition(const Variable *Var) const; |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 1056 | const InstDefList &getLatterDefinitions(const Variable *Var) const; |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 1057 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1058 | /// Returns whether the given Variable is live across multiple blocks. Mainly, |
| 1059 | /// this is used to partition Variables into single-block versus multi-block |
| 1060 | /// sets for leveraging sparsity in liveness analysis, and for implementing |
| 1061 | /// simple stack slot coalescing. As a special case, function arguments are |
| 1062 | /// always considered multi-block because they are live coming into the entry |
| 1063 | /// block. |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 1064 | bool isMultiBlock(const Variable *Var) const; |
Jim Stichnoth | cc89c95 | 2016-03-31 11:55:23 -0700 | [diff] [blame] | 1065 | bool isSingleBlock(const Variable *Var) const; |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 1066 | /// Returns the node that the given Variable is used in, assuming |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1067 | /// isMultiBlock() returns false. Otherwise, nullptr is returned. |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 1068 | CfgNode *getLocalUseNode(const Variable *Var) const; |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 1069 | |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 1070 | /// Returns the total use weight computed as the sum of uses multiplied by a |
| 1071 | /// loop nest depth factor for each use. |
Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame] | 1072 | RegWeight getUseWeight(const Variable *Var) const; |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 1073 | |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 1074 | private: |
| 1075 | const Cfg *Func; |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 1076 | MetadataKind Kind; |
Andrew Scull | 00741a0 | 2015-09-16 19:04:09 -0700 | [diff] [blame] | 1077 | CfgVector<VariableTracking> Metadata; |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 1078 | const static InstDefList NoDefinitions; |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 1079 | }; |
| 1080 | |
Eric Holk | 80ee5b3 | 2016-05-06 14:28:04 -0700 | [diff] [blame] | 1081 | /// BooleanVariable represents a variable that was the zero-extended result of a |
| 1082 | /// comparison. It maintains a pointer to its original i1 source so that the |
| 1083 | /// WASM frontend can avoid adding needless comparisons. |
| 1084 | class BooleanVariable : public Variable { |
| 1085 | BooleanVariable() = delete; |
| 1086 | BooleanVariable(const BooleanVariable &) = delete; |
| 1087 | BooleanVariable &operator=(const BooleanVariable &) = delete; |
| 1088 | |
| 1089 | BooleanVariable(const Cfg *Func, OperandKind K, Type Ty, SizeT Index) |
| 1090 | : Variable(Func, K, Ty, Index) {} |
| 1091 | |
| 1092 | public: |
| 1093 | static BooleanVariable *create(Cfg *Func, Type Ty, SizeT Index) { |
| 1094 | return new (Func->allocate<BooleanVariable>()) |
| 1095 | BooleanVariable(Func, kVariable, Ty, Index); |
| 1096 | } |
| 1097 | |
| 1098 | virtual Variable *asBoolean() { return BoolSource; } |
| 1099 | |
| 1100 | void setBoolSource(Variable *Src) { BoolSource = Src; } |
| 1101 | |
| 1102 | static bool classof(const Operand *Operand) { |
| 1103 | return Operand->getKind() == kVariableBoolean; |
| 1104 | } |
| 1105 | |
| 1106 | private: |
| 1107 | Variable *BoolSource = nullptr; |
| 1108 | }; |
| 1109 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1110 | } // end of namespace Ice |
| 1111 | |
| 1112 | #endif // SUBZERO_SRC_ICEOPERAND_H |