blob: 3bbc0e36cc97a3f4b8a5c450540b1f0bef743258 [file] [log] [blame]
Jim Stichnothf7c9a142014-04-29 10:52:43 -07001//===- 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//===----------------------------------------------------------------------===//
9//
10// This file declares the Operand class and its target-independent
11// subclasses. The main classes are Variable, which represents an
12// LLVM variable that is either register- or stack-allocated, and the
13// Constant hierarchy, which represents integer, floating-point,
14// and/or symbolic constants.
15//
16//===----------------------------------------------------------------------===//
17
18#ifndef SUBZERO_SRC_ICEOPERAND_H
19#define SUBZERO_SRC_ICEOPERAND_H
20
Jan Voungfe14fb82014-10-13 15:56:32 -070021#include "IceCfg.h"
Jim Stichnothf7c9a142014-04-29 10:52:43 -070022#include "IceDefs.h"
Jan Voungfe14fb82014-10-13 15:56:32 -070023#include "IceGlobalContext.h"
Jim Stichnothf7c9a142014-04-29 10:52:43 -070024#include "IceTypes.h"
25
26namespace Ice {
27
28class Operand {
Jim Stichnoth7b451a92014-10-15 14:39:23 -070029 Operand(const Operand &) = delete;
30 Operand &operator=(const Operand &) = delete;
31
Jim Stichnothf7c9a142014-04-29 10:52:43 -070032public:
Jim Stichnoth800dab22014-09-20 12:25:02 -070033 static const size_t MaxTargetKinds = 10;
Jim Stichnothf7c9a142014-04-29 10:52:43 -070034 enum OperandKind {
35 kConst_Base,
Jan Voungbc004632014-09-16 15:09:10 -070036 kConstInteger32,
37 kConstInteger64,
Jim Stichnothf7c9a142014-04-29 10:52:43 -070038 kConstFloat,
39 kConstDouble,
40 kConstRelocatable,
Matt Walad8f4a7d2014-06-18 09:55:03 -070041 kConstUndef,
Jim Stichnoth800dab22014-09-20 12:25:02 -070042 kConst_Target, // leave space for target-specific constant kinds
43 kConst_Num = kConst_Target + MaxTargetKinds,
Jim Stichnothf7c9a142014-04-29 10:52:43 -070044 kVariable,
Jim Stichnoth800dab22014-09-20 12:25:02 -070045 kVariable_Target, // leave space for target-specific variable kinds
46 kVariable_Num = kVariable_Target + MaxTargetKinds,
Jim Stichnothf7c9a142014-04-29 10:52:43 -070047 // Target-specific operand classes use kTarget as the starting
48 // point for their Kind enum space.
49 kTarget
50 };
51 OperandKind getKind() const { return Kind; }
52 Type getType() const { return Ty; }
53
54 // Every Operand keeps an array of the Variables referenced in
55 // the operand. This is so that the liveness operations can get
56 // quick access to the variables of interest, without having to dig
57 // so far into the operand.
58 SizeT getNumVars() const { return NumVars; }
59 Variable *getVar(SizeT I) const {
60 assert(I < getNumVars());
61 return Vars[I];
62 }
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -070063 virtual void emit(const Cfg *Func) const = 0;
Jim Stichnoth2e8bfbb2014-09-16 10:16:00 -070064 // The dump(Func,Str) implementation must be sure to handle the
Jim Stichnothae953202014-12-20 06:17:49 -080065 // situation where Func==nullptr.
Jim Stichnoth2e8bfbb2014-09-16 10:16:00 -070066 virtual void dump(const Cfg *Func, Ostream &Str) const = 0;
67 void dump(const Cfg *Func) const {
Karl Schimpfb6c96af2014-11-17 10:58:39 -080068 if (!ALLOW_DUMP)
69 return;
Jim Stichnoth2e8bfbb2014-09-16 10:16:00 -070070 assert(Func);
71 dump(Func, Func->getContext()->getStrDump());
72 }
Karl Schimpfb6c96af2014-11-17 10:58:39 -080073 void dump(Ostream &Str) const {
74 if (ALLOW_DUMP)
Jim Stichnothae953202014-12-20 06:17:49 -080075 dump(nullptr, Str);
Karl Schimpfb6c96af2014-11-17 10:58:39 -080076 }
Jim Stichnothf7c9a142014-04-29 10:52:43 -070077
Jim Stichnothf7c9a142014-04-29 10:52:43 -070078 virtual ~Operand() {}
79
80protected:
81 Operand(OperandKind Kind, Type Ty)
Jim Stichnothae953202014-12-20 06:17:49 -080082 : Ty(Ty), Kind(Kind), NumVars(0), Vars(nullptr) {}
Jim Stichnothf7c9a142014-04-29 10:52:43 -070083
84 const Type Ty;
85 const OperandKind Kind;
86 // Vars and NumVars are initialized by the derived class.
87 SizeT NumVars;
88 Variable **Vars;
Jim Stichnothf7c9a142014-04-29 10:52:43 -070089};
90
Karl Schimpf97501832014-09-16 13:35:32 -070091template<class StreamType>
92inline StreamType &operator<<(StreamType &Str, const Operand &Op) {
93 Op.dump(Str);
94 return Str;
95}
96
Jim Stichnothf7c9a142014-04-29 10:52:43 -070097// Constant is the abstract base class for constants. All
98// constants are allocated from a global arena and are pooled.
99class Constant : public Operand {
Jim Stichnoth7b451a92014-10-15 14:39:23 -0700100 Constant(const Constant &) = delete;
101 Constant &operator=(const Constant &) = delete;
102
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700103public:
Jan Voung1d62cf02015-01-09 14:57:32 -0800104 void emitPoolLabel(Ostream &Str) const {
105 Str << ".L$" << getType() << "$" << PoolEntryID;
106 }
Jim Stichnoth2e8bfbb2014-09-16 10:16:00 -0700107 using Operand::dump;
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700108 void emit(const Cfg *Func) const override { emit(Func->getContext()); }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700109 virtual void emit(GlobalContext *Ctx) const = 0;
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700110 void dump(const Cfg *Func, Ostream &Str) const = 0;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700111
112 static bool classof(const Operand *Operand) {
113 OperandKind Kind = Operand->getKind();
114 return Kind >= kConst_Base && Kind <= kConst_Num;
115 }
116
117protected:
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700118 Constant(OperandKind Kind, Type Ty, uint32_t PoolEntryID)
119 : Operand(Kind, Ty), PoolEntryID(PoolEntryID) {
Jim Stichnothae953202014-12-20 06:17:49 -0800120 Vars = nullptr;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700121 NumVars = 0;
122 }
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700123 ~Constant() override {}
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700124 // PoolEntryID is an integer that uniquely identifies the constant
125 // within its constant pool. It is used for building the constant
126 // pool in the object code and for referencing its entries.
127 const uint32_t PoolEntryID;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700128};
129
130// ConstantPrimitive<> wraps a primitive type.
131template <typename T, Operand::OperandKind K>
132class ConstantPrimitive : public Constant {
Jim Stichnoth7b451a92014-10-15 14:39:23 -0700133 ConstantPrimitive(const ConstantPrimitive &) = delete;
134 ConstantPrimitive &operator=(const ConstantPrimitive &) = delete;
135
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700136public:
Jan Voung91a3e2c2015-01-09 13:01:42 -0800137 typedef T PrimType;
138
139 static ConstantPrimitive *create(GlobalContext *Ctx, Type Ty, PrimType Value,
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700140 uint32_t PoolEntryID) {
Karl Schimpf6fcbddd2014-11-06 09:49:24 -0800141 assert(!Ctx->isIRGenerationDisabled() &&
142 "Attempt to build primitive constant when IR generation disabled");
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700143 return new (Ctx->allocate<ConstantPrimitive>())
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700144 ConstantPrimitive(Ty, Value, PoolEntryID);
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700145 }
Jan Voung91a3e2c2015-01-09 13:01:42 -0800146 PrimType getValue() const { return Value; }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700147 using Constant::emit;
Matt Wala928f1292014-07-07 16:50:46 -0700148 // The target needs to implement this for each ConstantPrimitive
149 // specialization.
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700150 void emit(GlobalContext *Ctx) const override;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700151 using Constant::dump;
Karl Schimpfb6c96af2014-11-17 10:58:39 -0800152 void dump(const Cfg *, Ostream &Str) const override {
153 if (ALLOW_DUMP)
154 Str << getValue();
155 }
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700156
157 static bool classof(const Operand *Operand) {
158 return Operand->getKind() == K;
159 }
160
161private:
Jan Voung91a3e2c2015-01-09 13:01:42 -0800162 ConstantPrimitive(Type Ty, PrimType Value, uint32_t PoolEntryID)
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700163 : Constant(K, Ty, PoolEntryID), Value(Value) {}
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700164 ~ConstantPrimitive() override {}
Jan Voung91a3e2c2015-01-09 13:01:42 -0800165 const PrimType Value;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700166};
167
Jim Stichnothd2cb4362014-11-20 11:24:42 -0800168typedef ConstantPrimitive<int32_t, Operand::kConstInteger32> ConstantInteger32;
169typedef ConstantPrimitive<int64_t, Operand::kConstInteger64> ConstantInteger64;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700170typedef ConstantPrimitive<float, Operand::kConstFloat> ConstantFloat;
171typedef ConstantPrimitive<double, Operand::kConstDouble> ConstantDouble;
172
Jan Voungbc004632014-09-16 15:09:10 -0700173template <> inline void ConstantInteger32::dump(const Cfg *, Ostream &Str) const {
Karl Schimpfb6c96af2014-11-17 10:58:39 -0800174 if (!ALLOW_DUMP)
175 return;
Jim Stichnothcabfa302014-09-03 15:19:12 -0700176 if (getType() == IceType_i1)
177 Str << (getValue() ? "true" : "false");
178 else
Jan Voungbc004632014-09-16 15:09:10 -0700179 Str << static_cast<int32_t>(getValue());
180}
181
182template <> inline void ConstantInteger64::dump(const Cfg *, Ostream &Str) const {
Karl Schimpfb6c96af2014-11-17 10:58:39 -0800183 if (!ALLOW_DUMP)
184 return;
Jan Voungbc004632014-09-16 15:09:10 -0700185 assert(getType() == IceType_i64);
186 Str << static_cast<int64_t>(getValue());
Jim Stichnothcabfa302014-09-03 15:19:12 -0700187}
188
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700189// RelocatableTuple bundles the parameters that are used to
190// construct an ConstantRelocatable. It is done this way so that
191// ConstantRelocatable can fit into the global constant pool
192// template mechanism.
193class RelocatableTuple {
Jim Stichnoth0795ba02014-10-01 14:23:01 -0700194 RelocatableTuple &operator=(const RelocatableTuple &) = delete;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700195
196public:
Jan Voungfe14fb82014-10-13 15:56:32 -0700197 RelocatableTuple(const RelocOffsetT Offset, const IceString &Name,
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700198 bool SuppressMangling)
199 : Offset(Offset), Name(Name), SuppressMangling(SuppressMangling) {}
Jim Stichnothd2cb4362014-11-20 11:24:42 -0800200 RelocatableTuple(const RelocatableTuple &) = default;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700201
Jan Voungfe14fb82014-10-13 15:56:32 -0700202 const RelocOffsetT Offset;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700203 const IceString Name;
204 bool SuppressMangling;
205};
206
Jim Stichnothd2cb4362014-11-20 11:24:42 -0800207bool operator==(const RelocatableTuple &A, const RelocatableTuple &B);
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700208
209// ConstantRelocatable represents a symbolic constant combined with
210// a fixed offset.
211class ConstantRelocatable : public Constant {
Jim Stichnoth7b451a92014-10-15 14:39:23 -0700212 ConstantRelocatable(const ConstantRelocatable &) = delete;
213 ConstantRelocatable &operator=(const ConstantRelocatable &) = delete;
214
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700215public:
216 static ConstantRelocatable *create(GlobalContext *Ctx, Type Ty,
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700217 const RelocatableTuple &Tuple,
218 uint32_t PoolEntryID) {
Karl Schimpf6fcbddd2014-11-06 09:49:24 -0800219 assert(!Ctx->isIRGenerationDisabled() &&
220 "Attempt to build relocatable constant when IR generation disabled");
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700221 return new (Ctx->allocate<ConstantRelocatable>()) ConstantRelocatable(
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700222 Ty, Tuple.Offset, Tuple.Name, Tuple.SuppressMangling, PoolEntryID);
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700223 }
Jan Voungfe14fb82014-10-13 15:56:32 -0700224
225 RelocOffsetT getOffset() const { return Offset; }
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700226 IceString getName() const { return Name; }
227 void setSuppressMangling(bool Value) { SuppressMangling = Value; }
228 bool getSuppressMangling() const { return SuppressMangling; }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700229 using Constant::emit;
230 using Constant::dump;
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700231 void emit(GlobalContext *Ctx) const override;
Jim Stichnothbca2f652014-11-01 10:13:54 -0700232 void emitWithoutDollar(GlobalContext *Ctx) const;
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700233 void dump(const Cfg *Func, Ostream &Str) const override;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700234
235 static bool classof(const Operand *Operand) {
236 OperandKind Kind = Operand->getKind();
237 return Kind == kConstRelocatable;
238 }
239
240private:
Jan Voungfe14fb82014-10-13 15:56:32 -0700241 ConstantRelocatable(Type Ty, RelocOffsetT Offset, const IceString &Name,
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700242 bool SuppressMangling, uint32_t PoolEntryID)
243 : Constant(kConstRelocatable, Ty, PoolEntryID), Offset(Offset),
244 Name(Name), SuppressMangling(SuppressMangling) {}
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700245 ~ConstantRelocatable() override {}
Jan Voungfe14fb82014-10-13 15:56:32 -0700246 const RelocOffsetT Offset; // fixed offset to add
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700247 const IceString Name; // optional for debug/dump
248 bool SuppressMangling;
249};
250
Matt Walad8f4a7d2014-06-18 09:55:03 -0700251// ConstantUndef represents an unspecified bit pattern. Although it is
252// legal to lower ConstantUndef to any value, backends should try to
253// make code generation deterministic by lowering ConstantUndefs to 0.
254class ConstantUndef : public Constant {
Jim Stichnoth7b451a92014-10-15 14:39:23 -0700255 ConstantUndef(const ConstantUndef &) = delete;
256 ConstantUndef &operator=(const ConstantUndef &) = delete;
257
Matt Walad8f4a7d2014-06-18 09:55:03 -0700258public:
259 static ConstantUndef *create(GlobalContext *Ctx, Type Ty,
260 uint32_t PoolEntryID) {
Karl Schimpf6fcbddd2014-11-06 09:49:24 -0800261 assert(!Ctx->isIRGenerationDisabled() &&
262 "Attempt to build undefined constant when IR generation disabled");
Matt Walad8f4a7d2014-06-18 09:55:03 -0700263 return new (Ctx->allocate<ConstantUndef>()) ConstantUndef(Ty, PoolEntryID);
264 }
265
266 using Constant::emit;
Jim Stichnoth2e8bfbb2014-09-16 10:16:00 -0700267 using Constant::dump;
Matt Walae3777672014-07-31 09:06:17 -0700268 // The target needs to implement this.
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700269 void emit(GlobalContext *Ctx) const override;
Karl Schimpfb6c96af2014-11-17 10:58:39 -0800270 void dump(const Cfg *, Ostream &Str) const override {
271 if (ALLOW_DUMP)
272 Str << "undef";
273 }
Matt Walad8f4a7d2014-06-18 09:55:03 -0700274
275 static bool classof(const Operand *Operand) {
276 return Operand->getKind() == kConstUndef;
277 }
278
279private:
280 ConstantUndef(Type Ty, uint32_t PoolEntryID)
281 : Constant(kConstUndef, Ty, PoolEntryID) {}
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700282 ~ConstantUndef() override {}
Matt Walad8f4a7d2014-06-18 09:55:03 -0700283};
284
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700285// RegWeight is a wrapper for a uint32_t weight value, with a
286// special value that represents infinite weight, and an addWeight()
287// method that ensures that W+infinity=infinity.
288class RegWeight {
Jim Stichnoth7b451a92014-10-15 14:39:23 -0700289
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700290public:
291 RegWeight() : Weight(0) {}
292 RegWeight(uint32_t Weight) : Weight(Weight) {}
Jim Stichnoth7e571362015-01-09 11:43:26 -0800293 RegWeight(const RegWeight &) = default;
294 RegWeight &operator=(const RegWeight &) = default;
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700295 const static uint32_t Inf = ~0; // Force regalloc to give a register
296 const static uint32_t Zero = 0; // Force regalloc NOT to give a register
297 void addWeight(uint32_t Delta) {
298 if (Delta == Inf)
299 Weight = Inf;
300 else if (Weight != Inf)
301 Weight += Delta;
302 }
303 void addWeight(const RegWeight &Other) { addWeight(Other.Weight); }
304 void setWeight(uint32_t Val) { Weight = Val; }
305 uint32_t getWeight() const { return Weight; }
306 bool isInf() const { return Weight == Inf; }
307
308private:
309 uint32_t Weight;
310};
311Ostream &operator<<(Ostream &Str, const RegWeight &W);
312bool operator<(const RegWeight &A, const RegWeight &B);
313bool operator<=(const RegWeight &A, const RegWeight &B);
314bool operator==(const RegWeight &A, const RegWeight &B);
315
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700316// LiveRange is a set of instruction number intervals representing
317// a variable's live range. Generally there is one interval per basic
318// block where the variable is live, but adjacent intervals get
319// coalesced into a single interval. LiveRange also includes a
320// weight, in case e.g. we want a live range to have higher weight
321// inside a loop.
322class LiveRange {
323public:
Jim Stichnoth87ff3a12014-11-14 10:27:29 -0800324 LiveRange() : Weight(0) {}
Jim Stichnoth2a7fcbb2014-12-04 11:45:03 -0800325 // Special constructor for building a kill set. The advantage is
326 // that we can reserve the right amount of space in advance.
327 LiveRange(const std::vector<InstNumberT> &Kills) : Weight(0) {
328 Range.reserve(Kills.size());
329 for (InstNumberT I : Kills)
330 addSegment(I, I);
331 }
Jim Stichnoth87ff3a12014-11-14 10:27:29 -0800332 LiveRange(const LiveRange &) = default;
333 LiveRange &operator=(const LiveRange &) = default;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700334
335 void reset() {
336 Range.clear();
337 Weight.setWeight(0);
Jim Stichnoth037fa1d2014-10-07 11:09:33 -0700338 untrim();
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700339 }
340 void addSegment(InstNumberT Start, InstNumberT End);
341
342 bool endsBefore(const LiveRange &Other) const;
Jim Stichnoth037fa1d2014-10-07 11:09:33 -0700343 bool overlaps(const LiveRange &Other, bool UseTrimmed = false) const;
344 bool overlapsInst(InstNumberT OtherBegin, bool UseTrimmed = false) const;
Jim Stichnoth47752552014-10-13 17:15:08 -0700345 bool containsValue(InstNumberT Value, bool IsDest) const;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700346 bool isEmpty() const { return Range.empty(); }
347 InstNumberT getStart() const {
348 return Range.empty() ? -1 : Range.begin()->first;
349 }
350
Jim Stichnoth037fa1d2014-10-07 11:09:33 -0700351 void untrim() { TrimmedBegin = Range.begin(); }
352 void trim(InstNumberT Lower);
353
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700354 RegWeight getWeight() const { return Weight; }
355 void setWeight(const RegWeight &NewWeight) { Weight = NewWeight; }
356 void addWeight(uint32_t Delta) { Weight.addWeight(Delta); }
357 void dump(Ostream &Str) const;
358
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700359private:
360 typedef std::pair<InstNumberT, InstNumberT> RangeElementType;
Jim Stichnoth31c95592014-12-19 12:51:35 -0800361 // RangeType is arena-allocated from the Cfg's allocator.
362 typedef std::vector<RangeElementType, CfgLocalAllocator<RangeElementType>>
363 RangeType;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700364 RangeType Range;
365 RegWeight Weight;
Jim Stichnoth037fa1d2014-10-07 11:09:33 -0700366 // TrimmedBegin is an optimization for the overlaps() computation.
367 // Since the linear-scan algorithm always calls it as overlaps(Cur)
368 // and Cur advances monotonically according to live range start, we
369 // can optimize overlaps() by ignoring all segments that end before
370 // the start of Cur's range. The linear-scan code enables this by
371 // calling trim() on the ranges of interest as Cur advances. Note
372 // that linear-scan also has to initialize TrimmedBegin at the
373 // beginning by calling untrim().
374 RangeType::const_iterator TrimmedBegin;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700375};
376
377Ostream &operator<<(Ostream &Str, const LiveRange &L);
378
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700379// Variable represents an operand that is register-allocated or
380// stack-allocated. If it is register-allocated, it will ultimately
381// have a non-negative RegNum field.
382class Variable : public Operand {
Jim Stichnoth0795ba02014-10-01 14:23:01 -0700383 Variable(const Variable &) = delete;
384 Variable &operator=(const Variable &) = delete;
Jim Stichnoth800dab22014-09-20 12:25:02 -0700385
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700386public:
Jim Stichnoth9a04c072014-12-11 15:51:42 -0800387 static Variable *create(Cfg *Func, Type Ty, SizeT Index) {
388 return new (Func->allocate<Variable>()) Variable(kVariable, Ty, Index);
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700389 }
390
391 SizeT getIndex() const { return Number; }
Jim Stichnoth9a04c072014-12-11 15:51:42 -0800392 IceString getName(const Cfg *Func) const;
393 void setName(Cfg *Func, const IceString &NewName) {
Karl Schimpfc132b762014-09-11 09:43:47 -0700394 // Make sure that the name can only be set once.
Jim Stichnoth9a04c072014-12-11 15:51:42 -0800395 assert(NameIndex == Cfg::IdentifierIndexInvalid);
396 if (!NewName.empty())
397 NameIndex = Func->addIdentifierName(NewName);
Karl Schimpfc132b762014-09-11 09:43:47 -0700398 }
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700399
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700400 bool getIsArg() const { return IsArgument; }
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700401 void setIsArg(bool Val = true) { IsArgument = Val; }
402 bool getIsImplicitArg() const { return IsImplicitArgument; }
403 void setIsImplicitArg(bool Val = true) { IsImplicitArgument = Val; }
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700404
Jim Stichnoth47752552014-10-13 17:15:08 -0700405 void setIgnoreLiveness() { IgnoreLiveness = true; }
406 bool getIgnoreLiveness() const { return IgnoreLiveness; }
407
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700408 int32_t getStackOffset() const { return StackOffset; }
409 void setStackOffset(int32_t Offset) { StackOffset = Offset; }
410
411 static const int32_t NoRegister = -1;
412 bool hasReg() const { return getRegNum() != NoRegister; }
413 int32_t getRegNum() const { return RegNum; }
414 void setRegNum(int32_t NewRegNum) {
415 // Regnum shouldn't be set more than once.
416 assert(!hasReg() || RegNum == NewRegNum);
417 RegNum = NewRegNum;
418 }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700419 bool hasRegTmp() const { return getRegNumTmp() != NoRegister; }
420 int32_t getRegNumTmp() const { return RegNumTmp; }
421 void setRegNumTmp(int32_t NewRegNum) { RegNumTmp = NewRegNum; }
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700422
423 RegWeight getWeight() const { return Weight; }
424 void setWeight(uint32_t NewWeight) { Weight = NewWeight; }
425 void setWeightInfinite() { Weight = RegWeight::Inf; }
426
Jim Stichnoth5ce0abb2014-10-15 10:16:54 -0700427 LiveRange &getLiveRange() { return Live; }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700428 const LiveRange &getLiveRange() const { return Live; }
429 void setLiveRange(const LiveRange &Range) { Live = Range; }
430 void resetLiveRange() { Live.reset(); }
431 void addLiveRange(InstNumberT Start, InstNumberT End, uint32_t WeightDelta) {
432 assert(WeightDelta != RegWeight::Inf);
433 Live.addSegment(Start, End);
434 if (Weight.isInf())
435 Live.setWeight(RegWeight::Inf);
436 else
437 Live.addWeight(WeightDelta * Weight.getWeight());
438 }
439 void setLiveRangeInfiniteWeight() { Live.setWeight(RegWeight::Inf); }
Jim Stichnoth037fa1d2014-10-07 11:09:33 -0700440 void trimLiveRange(InstNumberT Start) { Live.trim(Start); }
441 void untrimLiveRange() { Live.untrim(); }
Jim Stichnoth5ce0abb2014-10-15 10:16:54 -0700442 bool rangeEndsBefore(const Variable *Other) const {
443 return Live.endsBefore(Other->Live);
444 }
445 bool rangeOverlaps(const Variable *Other) const {
446 const bool UseTrimmed = true;
447 return Live.overlaps(Other->Live, UseTrimmed);
448 }
449 bool rangeOverlapsStart(const Variable *Other) const {
450 const bool UseTrimmed = true;
451 return Live.overlapsInst(Other->Live.getStart(), UseTrimmed);
452 }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700453
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700454 Variable *getLo() const { return LoVar; }
455 Variable *getHi() const { return HiVar; }
456 void setLoHi(Variable *Lo, Variable *Hi) {
Jim Stichnothae953202014-12-20 06:17:49 -0800457 assert(LoVar == nullptr);
458 assert(HiVar == nullptr);
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700459 LoVar = Lo;
460 HiVar = Hi;
461 }
462 // Creates a temporary copy of the variable with a different type.
463 // Used primarily for syntactic correctness of textual assembly
464 // emission. Note that only basic information is copied, in
Jim Stichnoth31c95592014-12-19 12:51:35 -0800465 // particular not IsArgument, IsImplicitArgument, IgnoreLiveness,
466 // RegNumTmp, Weight, Live, LoVar, HiVar, VarsReal.
467 Variable *asType(Type Ty);
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700468
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700469 void emit(const Cfg *Func) const override;
Jim Stichnoth2e8bfbb2014-09-16 10:16:00 -0700470 using Operand::dump;
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700471 void dump(const Cfg *Func, Ostream &Str) const override;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700472
473 static bool classof(const Operand *Operand) {
Jim Stichnoth800dab22014-09-20 12:25:02 -0700474 OperandKind Kind = Operand->getKind();
475 return Kind >= kVariable && Kind <= kVariable_Num;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700476 }
477
Jim Stichnoth800dab22014-09-20 12:25:02 -0700478protected:
Jim Stichnoth9a04c072014-12-11 15:51:42 -0800479 Variable(OperandKind K, Type Ty, SizeT Index)
480 : Operand(K, Ty), Number(Index), NameIndex(Cfg::IdentifierIndexInvalid),
481 IsArgument(false), IsImplicitArgument(false), IgnoreLiveness(false),
482 StackOffset(0), RegNum(NoRegister), RegNumTmp(NoRegister), Weight(1),
Jim Stichnothae953202014-12-20 06:17:49 -0800483 LoVar(nullptr), HiVar(nullptr) {
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700484 Vars = VarsReal;
485 Vars[0] = this;
486 NumVars = 1;
487 }
Jim Stichnoth31c95592014-12-19 12:51:35 -0800488 ~Variable() override {}
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700489 // Number is unique across all variables, and is used as a
490 // (bit)vector index for liveness analysis.
491 const SizeT Number;
Jim Stichnoth9a04c072014-12-11 15:51:42 -0800492 Cfg::IdentifierIndexType NameIndex;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700493 bool IsArgument;
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700494 bool IsImplicitArgument;
Jim Stichnoth47752552014-10-13 17:15:08 -0700495 // IgnoreLiveness means that the variable should be ignored when
496 // constructing and validating live ranges. This is usually
497 // reserved for the stack pointer.
498 bool IgnoreLiveness;
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700499 // StackOffset is the canonical location on stack (only if
Jim Stichnothad403532014-09-25 12:44:17 -0700500 // RegNum==NoRegister || IsArgument).
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700501 int32_t StackOffset;
502 // RegNum is the allocated register, or NoRegister if it isn't
503 // register-allocated.
504 int32_t RegNum;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700505 // RegNumTmp is the tentative assignment during register allocation.
506 int32_t RegNumTmp;
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700507 RegWeight Weight; // Register allocation priority
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700508 LiveRange Live;
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700509 // LoVar and HiVar are needed for lowering from 64 to 32 bits. When
510 // lowering from I64 to I32 on a 32-bit architecture, we split the
511 // variable into two machine-size pieces. LoVar is the low-order
512 // machine-size portion, and HiVar is the remaining high-order
513 // portion. TODO: It's wasteful to penalize all variables on all
514 // targets this way; use a sparser representation. It's also
515 // wasteful for a 64-bit target.
516 Variable *LoVar;
517 Variable *HiVar;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700518 // VarsReal (and Operand::Vars) are set up such that Vars[0] ==
519 // this.
520 Variable *VarsReal[1];
521};
522
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700523enum MetadataKind {
524 VMK_Uses, // Track only uses, not defs
525 VMK_SingleDefs, // Track uses+defs, but only record single def
526 VMK_All // Track uses+defs, including full def list
527};
Jim Stichnothe4a8f402015-01-20 12:52:51 -0800528typedef std::vector<const Inst *, CfgLocalAllocator<const Inst *>> InstDefList;
Jim Stichnothad403532014-09-25 12:44:17 -0700529
530// VariableTracking tracks the metadata for a single variable. It is
531// only meant to be used internally by VariablesMetadata.
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700532class VariableTracking {
Jim Stichnoth7b451a92014-10-15 14:39:23 -0700533 VariableTracking &operator=(const VariableTracking &) = delete;
534
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700535public:
536 enum MultiDefState {
537 // TODO(stichnot): Consider using just a simple counter.
538 MDS_Unknown,
539 MDS_SingleDef,
Jim Stichnothad403532014-09-25 12:44:17 -0700540 MDS_MultiDefSingleBlock,
541 MDS_MultiDefMultiBlock
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700542 };
543 enum MultiBlockState {
544 MBS_Unknown,
545 MBS_SingleBlock,
546 MBS_MultiBlock
547 };
548 VariableTracking()
Jim Stichnothae953202014-12-20 06:17:49 -0800549 : MultiDef(MDS_Unknown), MultiBlock(MBS_Unknown), SingleUseNode(nullptr),
550 SingleDefNode(nullptr), FirstOrSingleDefinition(nullptr) {}
Jim Stichnoth7e571362015-01-09 11:43:26 -0800551 VariableTracking(const VariableTracking &) = default;
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700552 MultiDefState getMultiDef() const { return MultiDef; }
553 MultiBlockState getMultiBlock() const { return MultiBlock; }
Jim Stichnothad403532014-09-25 12:44:17 -0700554 const Inst *getFirstDefinition() const;
555 const Inst *getSingleDefinition() const;
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700556 const InstDefList &getLatterDefinitions() const { return Definitions; }
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700557 const CfgNode *getNode() const { return SingleUseNode; }
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700558 void markUse(MetadataKind TrackingKind, const Inst *Instr,
559 const CfgNode *Node, bool IsFromDef, bool IsImplicit);
560 void markDef(MetadataKind TrackingKind, const Inst *Instr,
561 const CfgNode *Node);
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700562
563private:
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700564 MultiDefState MultiDef;
565 MultiBlockState MultiBlock;
566 const CfgNode *SingleUseNode;
Jim Stichnothad403532014-09-25 12:44:17 -0700567 const CfgNode *SingleDefNode;
Jim Stichnoth037fa1d2014-10-07 11:09:33 -0700568 // All definitions of the variable are collected here, in increasing
569 // order of instruction number.
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700570 InstDefList Definitions; // Only used if Kind==VMK_All
571 const Inst *FirstOrSingleDefinition; // == Definitions[0] if Kind==VMK_All
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700572};
573
574// VariablesMetadata analyzes and summarizes the metadata for the
575// complete set of Variables.
576class VariablesMetadata {
Jim Stichnoth7b451a92014-10-15 14:39:23 -0700577 VariablesMetadata(const VariablesMetadata &) = delete;
578 VariablesMetadata &operator=(const VariablesMetadata &) = delete;
579
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700580public:
581 VariablesMetadata(const Cfg *Func) : Func(Func) {}
Jim Stichnothad403532014-09-25 12:44:17 -0700582 // Initialize the state by traversing all instructions/variables in
583 // the CFG.
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700584 void init(MetadataKind TrackingKind);
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700585 // Add a single node. This is called by init(), and can be called
586 // incrementally from elsewhere, e.g. after edge-splitting.
587 void addNode(CfgNode *Node);
Jim Stichnothad403532014-09-25 12:44:17 -0700588 // Returns whether the given Variable is tracked in this object. It
589 // should only return false if changes were made to the CFG after
590 // running init(), in which case the state is stale and the results
591 // shouldn't be trusted (but it may be OK e.g. for dumping).
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700592 bool isTracked(const Variable *Var) const {
593 return Var->getIndex() < Metadata.size();
594 }
Jim Stichnothad403532014-09-25 12:44:17 -0700595
596 // Returns whether the given Variable has multiple definitions.
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700597 bool isMultiDef(const Variable *Var) const;
Jim Stichnothad403532014-09-25 12:44:17 -0700598 // Returns the first definition instruction of the given Variable.
599 // This is only valid for variables whose definitions are all within
600 // the same block, e.g. T after the lowered sequence "T=B; T+=C;
601 // A=T", for which getFirstDefinition(T) would return the "T=B"
602 // instruction. For variables with definitions span multiple
Jim Stichnothae953202014-12-20 06:17:49 -0800603 // blocks, nullptr is returned.
Jim Stichnothad403532014-09-25 12:44:17 -0700604 const Inst *getFirstDefinition(const Variable *Var) const;
605 // Returns the definition instruction of the given Variable, when
Jim Stichnothae953202014-12-20 06:17:49 -0800606 // the variable has exactly one definition. Otherwise, nullptr is
Jim Stichnothad403532014-09-25 12:44:17 -0700607 // returned.
608 const Inst *getSingleDefinition(const Variable *Var) const;
609 // Returns the list of all definition instructions of the given
610 // Variable.
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700611 const InstDefList &getLatterDefinitions(const Variable *Var) const;
Jim Stichnothad403532014-09-25 12:44:17 -0700612
613 // Returns whether the given Variable is live across multiple
614 // blocks. Mainly, this is used to partition Variables into
615 // single-block versus multi-block sets for leveraging sparsity in
616 // liveness analysis, and for implementing simple stack slot
617 // coalescing. As a special case, function arguments are always
618 // considered multi-block because they are live coming into the
619 // entry block.
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700620 bool isMultiBlock(const Variable *Var) const;
Jim Stichnothad403532014-09-25 12:44:17 -0700621 // Returns the node that the given Variable is used in, assuming
Jim Stichnothae953202014-12-20 06:17:49 -0800622 // isMultiBlock() returns false. Otherwise, nullptr is returned.
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700623 const CfgNode *getLocalUseNode(const Variable *Var) const;
624
625private:
626 const Cfg *Func;
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700627 MetadataKind Kind;
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700628 std::vector<VariableTracking> Metadata;
Jim Stichnothad403532014-09-25 12:44:17 -0700629 const static InstDefList NoDefinitions;
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700630};
631
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700632} // end of namespace Ice
633
634#endif // SUBZERO_SRC_ICEOPERAND_H