blob: 7562382858d8117fe6f052c77ada8b68a25951df [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
65 // situation where Func==NULL.
66 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)
75 dump(NULL, Str);
76 }
Jim Stichnothf7c9a142014-04-29 10:52:43 -070077
78 // Query whether this object was allocated in isolation, or added to
79 // some higher-level pool. This determines whether a containing
80 // object's destructor should delete this object. Generally,
81 // constants are pooled globally, variables are pooled per-CFG, and
82 // target-specific operands are not pooled.
83 virtual bool isPooled() const { return false; }
84
85 virtual ~Operand() {}
86
87protected:
88 Operand(OperandKind Kind, Type Ty)
89 : Ty(Ty), Kind(Kind), NumVars(0), Vars(NULL) {}
90
91 const Type Ty;
92 const OperandKind Kind;
93 // Vars and NumVars are initialized by the derived class.
94 SizeT NumVars;
95 Variable **Vars;
Jim Stichnothf7c9a142014-04-29 10:52:43 -070096};
97
Karl Schimpf97501832014-09-16 13:35:32 -070098template<class StreamType>
99inline StreamType &operator<<(StreamType &Str, const Operand &Op) {
100 Op.dump(Str);
101 return Str;
102}
103
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700104// Constant is the abstract base class for constants. All
105// constants are allocated from a global arena and are pooled.
106class Constant : public Operand {
Jim Stichnoth7b451a92014-10-15 14:39:23 -0700107 Constant(const Constant &) = delete;
108 Constant &operator=(const Constant &) = delete;
109
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700110public:
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700111 uint32_t getPoolEntryID() const { return PoolEntryID; }
Jim Stichnoth2e8bfbb2014-09-16 10:16:00 -0700112 using Operand::dump;
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700113 void emit(const Cfg *Func) const override { emit(Func->getContext()); }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700114 virtual void emit(GlobalContext *Ctx) const = 0;
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700115 void dump(const Cfg *Func, Ostream &Str) const = 0;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700116
117 static bool classof(const Operand *Operand) {
118 OperandKind Kind = Operand->getKind();
119 return Kind >= kConst_Base && Kind <= kConst_Num;
120 }
121
122protected:
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700123 Constant(OperandKind Kind, Type Ty, uint32_t PoolEntryID)
124 : Operand(Kind, Ty), PoolEntryID(PoolEntryID) {
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700125 Vars = NULL;
126 NumVars = 0;
127 }
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700128 ~Constant() override {}
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700129 // PoolEntryID is an integer that uniquely identifies the constant
130 // within its constant pool. It is used for building the constant
131 // pool in the object code and for referencing its entries.
132 const uint32_t PoolEntryID;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700133};
134
135// ConstantPrimitive<> wraps a primitive type.
136template <typename T, Operand::OperandKind K>
137class ConstantPrimitive : public Constant {
Jim Stichnoth7b451a92014-10-15 14:39:23 -0700138 ConstantPrimitive(const ConstantPrimitive &) = delete;
139 ConstantPrimitive &operator=(const ConstantPrimitive &) = delete;
140
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700141public:
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700142 static ConstantPrimitive *create(GlobalContext *Ctx, Type Ty, T Value,
143 uint32_t PoolEntryID) {
Karl Schimpf6fcbddd2014-11-06 09:49:24 -0800144 assert(!Ctx->isIRGenerationDisabled() &&
145 "Attempt to build primitive constant when IR generation disabled");
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700146 return new (Ctx->allocate<ConstantPrimitive>())
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700147 ConstantPrimitive(Ty, Value, PoolEntryID);
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700148 }
149 T getValue() const { return Value; }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700150 using Constant::emit;
Matt Wala928f1292014-07-07 16:50:46 -0700151 // The target needs to implement this for each ConstantPrimitive
152 // specialization.
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700153 void emit(GlobalContext *Ctx) const override;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700154 using Constant::dump;
Karl Schimpfb6c96af2014-11-17 10:58:39 -0800155 void dump(const Cfg *, Ostream &Str) const override {
156 if (ALLOW_DUMP)
157 Str << getValue();
158 }
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700159
160 static bool classof(const Operand *Operand) {
161 return Operand->getKind() == K;
162 }
163
164private:
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700165 ConstantPrimitive(Type Ty, T Value, uint32_t PoolEntryID)
166 : Constant(K, Ty, PoolEntryID), Value(Value) {}
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700167 ~ConstantPrimitive() override {}
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700168 const T Value;
169};
170
Jim Stichnothd2cb4362014-11-20 11:24:42 -0800171typedef ConstantPrimitive<int32_t, Operand::kConstInteger32> ConstantInteger32;
172typedef ConstantPrimitive<int64_t, Operand::kConstInteger64> ConstantInteger64;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700173typedef ConstantPrimitive<float, Operand::kConstFloat> ConstantFloat;
174typedef ConstantPrimitive<double, Operand::kConstDouble> ConstantDouble;
175
Jan Voungbc004632014-09-16 15:09:10 -0700176template <> inline void ConstantInteger32::dump(const Cfg *, Ostream &Str) const {
Karl Schimpfb6c96af2014-11-17 10:58:39 -0800177 if (!ALLOW_DUMP)
178 return;
Jim Stichnothcabfa302014-09-03 15:19:12 -0700179 if (getType() == IceType_i1)
180 Str << (getValue() ? "true" : "false");
181 else
Jan Voungbc004632014-09-16 15:09:10 -0700182 Str << static_cast<int32_t>(getValue());
183}
184
185template <> inline void ConstantInteger64::dump(const Cfg *, Ostream &Str) const {
Karl Schimpfb6c96af2014-11-17 10:58:39 -0800186 if (!ALLOW_DUMP)
187 return;
Jan Voungbc004632014-09-16 15:09:10 -0700188 assert(getType() == IceType_i64);
189 Str << static_cast<int64_t>(getValue());
Jim Stichnothcabfa302014-09-03 15:19:12 -0700190}
191
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700192// RelocatableTuple bundles the parameters that are used to
193// construct an ConstantRelocatable. It is done this way so that
194// ConstantRelocatable can fit into the global constant pool
195// template mechanism.
196class RelocatableTuple {
Jim Stichnoth0795ba02014-10-01 14:23:01 -0700197 RelocatableTuple &operator=(const RelocatableTuple &) = delete;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700198
199public:
Jan Voungfe14fb82014-10-13 15:56:32 -0700200 RelocatableTuple(const RelocOffsetT Offset, const IceString &Name,
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700201 bool SuppressMangling)
202 : Offset(Offset), Name(Name), SuppressMangling(SuppressMangling) {}
Jim Stichnothd2cb4362014-11-20 11:24:42 -0800203 RelocatableTuple(const RelocatableTuple &) = default;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700204
Jan Voungfe14fb82014-10-13 15:56:32 -0700205 const RelocOffsetT Offset;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700206 const IceString Name;
207 bool SuppressMangling;
208};
209
Jim Stichnothd2cb4362014-11-20 11:24:42 -0800210bool operator==(const RelocatableTuple &A, const RelocatableTuple &B);
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700211
212// ConstantRelocatable represents a symbolic constant combined with
213// a fixed offset.
214class ConstantRelocatable : public Constant {
Jim Stichnoth7b451a92014-10-15 14:39:23 -0700215 ConstantRelocatable(const ConstantRelocatable &) = delete;
216 ConstantRelocatable &operator=(const ConstantRelocatable &) = delete;
217
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700218public:
219 static ConstantRelocatable *create(GlobalContext *Ctx, Type Ty,
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700220 const RelocatableTuple &Tuple,
221 uint32_t PoolEntryID) {
Karl Schimpf6fcbddd2014-11-06 09:49:24 -0800222 assert(!Ctx->isIRGenerationDisabled() &&
223 "Attempt to build relocatable constant when IR generation disabled");
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700224 return new (Ctx->allocate<ConstantRelocatable>()) ConstantRelocatable(
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700225 Ty, Tuple.Offset, Tuple.Name, Tuple.SuppressMangling, PoolEntryID);
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700226 }
Jan Voungfe14fb82014-10-13 15:56:32 -0700227
228 RelocOffsetT getOffset() const { return Offset; }
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700229 IceString getName() const { return Name; }
230 void setSuppressMangling(bool Value) { SuppressMangling = Value; }
231 bool getSuppressMangling() const { return SuppressMangling; }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700232 using Constant::emit;
233 using Constant::dump;
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700234 void emit(GlobalContext *Ctx) const override;
Jim Stichnothbca2f652014-11-01 10:13:54 -0700235 void emitWithoutDollar(GlobalContext *Ctx) const;
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700236 void dump(const Cfg *Func, Ostream &Str) const override;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700237
238 static bool classof(const Operand *Operand) {
239 OperandKind Kind = Operand->getKind();
240 return Kind == kConstRelocatable;
241 }
242
243private:
Jan Voungfe14fb82014-10-13 15:56:32 -0700244 ConstantRelocatable(Type Ty, RelocOffsetT Offset, const IceString &Name,
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700245 bool SuppressMangling, uint32_t PoolEntryID)
246 : Constant(kConstRelocatable, Ty, PoolEntryID), Offset(Offset),
247 Name(Name), SuppressMangling(SuppressMangling) {}
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700248 ~ConstantRelocatable() override {}
Jan Voungfe14fb82014-10-13 15:56:32 -0700249 const RelocOffsetT Offset; // fixed offset to add
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700250 const IceString Name; // optional for debug/dump
251 bool SuppressMangling;
252};
253
Matt Walad8f4a7d2014-06-18 09:55:03 -0700254// ConstantUndef represents an unspecified bit pattern. Although it is
255// legal to lower ConstantUndef to any value, backends should try to
256// make code generation deterministic by lowering ConstantUndefs to 0.
257class ConstantUndef : public Constant {
Jim Stichnoth7b451a92014-10-15 14:39:23 -0700258 ConstantUndef(const ConstantUndef &) = delete;
259 ConstantUndef &operator=(const ConstantUndef &) = delete;
260
Matt Walad8f4a7d2014-06-18 09:55:03 -0700261public:
262 static ConstantUndef *create(GlobalContext *Ctx, Type Ty,
263 uint32_t PoolEntryID) {
Karl Schimpf6fcbddd2014-11-06 09:49:24 -0800264 assert(!Ctx->isIRGenerationDisabled() &&
265 "Attempt to build undefined constant when IR generation disabled");
Matt Walad8f4a7d2014-06-18 09:55:03 -0700266 return new (Ctx->allocate<ConstantUndef>()) ConstantUndef(Ty, PoolEntryID);
267 }
268
269 using Constant::emit;
Jim Stichnoth2e8bfbb2014-09-16 10:16:00 -0700270 using Constant::dump;
Matt Walae3777672014-07-31 09:06:17 -0700271 // The target needs to implement this.
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700272 void emit(GlobalContext *Ctx) const override;
Karl Schimpfb6c96af2014-11-17 10:58:39 -0800273 void dump(const Cfg *, Ostream &Str) const override {
274 if (ALLOW_DUMP)
275 Str << "undef";
276 }
Matt Walad8f4a7d2014-06-18 09:55:03 -0700277
278 static bool classof(const Operand *Operand) {
279 return Operand->getKind() == kConstUndef;
280 }
281
282private:
283 ConstantUndef(Type Ty, uint32_t PoolEntryID)
284 : Constant(kConstUndef, Ty, PoolEntryID) {}
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700285 ~ConstantUndef() override {}
Matt Walad8f4a7d2014-06-18 09:55:03 -0700286};
287
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700288// RegWeight is a wrapper for a uint32_t weight value, with a
289// special value that represents infinite weight, and an addWeight()
290// method that ensures that W+infinity=infinity.
291class RegWeight {
Jim Stichnoth7b451a92014-10-15 14:39:23 -0700292 // RegWeight(const RegWeight &) = delete;
293 // RegWeight &operator=(const RegWeight &) = delete;
294
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700295public:
296 RegWeight() : Weight(0) {}
297 RegWeight(uint32_t Weight) : Weight(Weight) {}
298 const static uint32_t Inf = ~0; // Force regalloc to give a register
299 const static uint32_t Zero = 0; // Force regalloc NOT to give a register
300 void addWeight(uint32_t Delta) {
301 if (Delta == Inf)
302 Weight = Inf;
303 else if (Weight != Inf)
304 Weight += Delta;
305 }
306 void addWeight(const RegWeight &Other) { addWeight(Other.Weight); }
307 void setWeight(uint32_t Val) { Weight = Val; }
308 uint32_t getWeight() const { return Weight; }
309 bool isInf() const { return Weight == Inf; }
310
311private:
312 uint32_t Weight;
313};
314Ostream &operator<<(Ostream &Str, const RegWeight &W);
315bool operator<(const RegWeight &A, const RegWeight &B);
316bool operator<=(const RegWeight &A, const RegWeight &B);
317bool operator==(const RegWeight &A, const RegWeight &B);
318
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700319// LiveRange is a set of instruction number intervals representing
320// a variable's live range. Generally there is one interval per basic
321// block where the variable is live, but adjacent intervals get
322// coalesced into a single interval. LiveRange also includes a
323// weight, in case e.g. we want a live range to have higher weight
324// inside a loop.
325class LiveRange {
326public:
Jim Stichnoth87ff3a12014-11-14 10:27:29 -0800327 LiveRange() : Weight(0) {}
Jim Stichnoth2a7fcbb2014-12-04 11:45:03 -0800328 // Special constructor for building a kill set. The advantage is
329 // that we can reserve the right amount of space in advance.
330 LiveRange(const std::vector<InstNumberT> &Kills) : Weight(0) {
331 Range.reserve(Kills.size());
332 for (InstNumberT I : Kills)
333 addSegment(I, I);
334 }
Jim Stichnoth87ff3a12014-11-14 10:27:29 -0800335 LiveRange(const LiveRange &) = default;
336 LiveRange &operator=(const LiveRange &) = default;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700337
338 void reset() {
339 Range.clear();
340 Weight.setWeight(0);
Jim Stichnoth037fa1d2014-10-07 11:09:33 -0700341 untrim();
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700342 }
343 void addSegment(InstNumberT Start, InstNumberT End);
344
345 bool endsBefore(const LiveRange &Other) const;
Jim Stichnoth037fa1d2014-10-07 11:09:33 -0700346 bool overlaps(const LiveRange &Other, bool UseTrimmed = false) const;
347 bool overlapsInst(InstNumberT OtherBegin, bool UseTrimmed = false) const;
Jim Stichnoth47752552014-10-13 17:15:08 -0700348 bool containsValue(InstNumberT Value, bool IsDest) const;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700349 bool isEmpty() const { return Range.empty(); }
350 InstNumberT getStart() const {
351 return Range.empty() ? -1 : Range.begin()->first;
352 }
353
Jim Stichnoth037fa1d2014-10-07 11:09:33 -0700354 void untrim() { TrimmedBegin = Range.begin(); }
355 void trim(InstNumberT Lower);
356
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700357 RegWeight getWeight() const { return Weight; }
358 void setWeight(const RegWeight &NewWeight) { Weight = NewWeight; }
359 void addWeight(uint32_t Delta) { Weight.addWeight(Delta); }
360 void dump(Ostream &Str) const;
361
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700362private:
363 typedef std::pair<InstNumberT, InstNumberT> RangeElementType;
Jim Stichnoth31c95592014-12-19 12:51:35 -0800364 // RangeType is arena-allocated from the Cfg's allocator.
365 typedef std::vector<RangeElementType, CfgLocalAllocator<RangeElementType>>
366 RangeType;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700367 RangeType Range;
368 RegWeight Weight;
Jim Stichnoth037fa1d2014-10-07 11:09:33 -0700369 // TrimmedBegin is an optimization for the overlaps() computation.
370 // Since the linear-scan algorithm always calls it as overlaps(Cur)
371 // and Cur advances monotonically according to live range start, we
372 // can optimize overlaps() by ignoring all segments that end before
373 // the start of Cur's range. The linear-scan code enables this by
374 // calling trim() on the ranges of interest as Cur advances. Note
375 // that linear-scan also has to initialize TrimmedBegin at the
376 // beginning by calling untrim().
377 RangeType::const_iterator TrimmedBegin;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700378};
379
380Ostream &operator<<(Ostream &Str, const LiveRange &L);
381
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700382// Variable represents an operand that is register-allocated or
383// stack-allocated. If it is register-allocated, it will ultimately
384// have a non-negative RegNum field.
385class Variable : public Operand {
Jim Stichnoth0795ba02014-10-01 14:23:01 -0700386 Variable(const Variable &) = delete;
387 Variable &operator=(const Variable &) = delete;
Jim Stichnoth800dab22014-09-20 12:25:02 -0700388
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700389public:
Jim Stichnoth9a04c072014-12-11 15:51:42 -0800390 static Variable *create(Cfg *Func, Type Ty, SizeT Index) {
391 return new (Func->allocate<Variable>()) Variable(kVariable, Ty, Index);
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700392 }
393
394 SizeT getIndex() const { return Number; }
Jim Stichnoth9a04c072014-12-11 15:51:42 -0800395 IceString getName(const Cfg *Func) const;
396 void setName(Cfg *Func, const IceString &NewName) {
Karl Schimpfc132b762014-09-11 09:43:47 -0700397 // Make sure that the name can only be set once.
Jim Stichnoth9a04c072014-12-11 15:51:42 -0800398 assert(NameIndex == Cfg::IdentifierIndexInvalid);
399 if (!NewName.empty())
400 NameIndex = Func->addIdentifierName(NewName);
Karl Schimpfc132b762014-09-11 09:43:47 -0700401 }
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700402
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700403 bool getIsArg() const { return IsArgument; }
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700404 void setIsArg(bool Val = true) { IsArgument = Val; }
405 bool getIsImplicitArg() const { return IsImplicitArgument; }
406 void setIsImplicitArg(bool Val = true) { IsImplicitArgument = Val; }
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700407
Jim Stichnoth47752552014-10-13 17:15:08 -0700408 void setIgnoreLiveness() { IgnoreLiveness = true; }
409 bool getIgnoreLiveness() const { return IgnoreLiveness; }
410
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700411 int32_t getStackOffset() const { return StackOffset; }
412 void setStackOffset(int32_t Offset) { StackOffset = Offset; }
413
414 static const int32_t NoRegister = -1;
415 bool hasReg() const { return getRegNum() != NoRegister; }
416 int32_t getRegNum() const { return RegNum; }
417 void setRegNum(int32_t NewRegNum) {
418 // Regnum shouldn't be set more than once.
419 assert(!hasReg() || RegNum == NewRegNum);
420 RegNum = NewRegNum;
421 }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700422 bool hasRegTmp() const { return getRegNumTmp() != NoRegister; }
423 int32_t getRegNumTmp() const { return RegNumTmp; }
424 void setRegNumTmp(int32_t NewRegNum) { RegNumTmp = NewRegNum; }
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700425
426 RegWeight getWeight() const { return Weight; }
427 void setWeight(uint32_t NewWeight) { Weight = NewWeight; }
428 void setWeightInfinite() { Weight = RegWeight::Inf; }
429
Jim Stichnoth5ce0abb2014-10-15 10:16:54 -0700430 LiveRange &getLiveRange() { return Live; }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700431 const LiveRange &getLiveRange() const { return Live; }
432 void setLiveRange(const LiveRange &Range) { Live = Range; }
433 void resetLiveRange() { Live.reset(); }
434 void addLiveRange(InstNumberT Start, InstNumberT End, uint32_t WeightDelta) {
435 assert(WeightDelta != RegWeight::Inf);
436 Live.addSegment(Start, End);
437 if (Weight.isInf())
438 Live.setWeight(RegWeight::Inf);
439 else
440 Live.addWeight(WeightDelta * Weight.getWeight());
441 }
442 void setLiveRangeInfiniteWeight() { Live.setWeight(RegWeight::Inf); }
Jim Stichnoth037fa1d2014-10-07 11:09:33 -0700443 void trimLiveRange(InstNumberT Start) { Live.trim(Start); }
444 void untrimLiveRange() { Live.untrim(); }
Jim Stichnoth5ce0abb2014-10-15 10:16:54 -0700445 bool rangeEndsBefore(const Variable *Other) const {
446 return Live.endsBefore(Other->Live);
447 }
448 bool rangeOverlaps(const Variable *Other) const {
449 const bool UseTrimmed = true;
450 return Live.overlaps(Other->Live, UseTrimmed);
451 }
452 bool rangeOverlapsStart(const Variable *Other) const {
453 const bool UseTrimmed = true;
454 return Live.overlapsInst(Other->Live.getStart(), UseTrimmed);
455 }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700456
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700457 Variable *getLo() const { return LoVar; }
458 Variable *getHi() const { return HiVar; }
459 void setLoHi(Variable *Lo, Variable *Hi) {
460 assert(LoVar == NULL);
461 assert(HiVar == NULL);
462 LoVar = Lo;
463 HiVar = Hi;
464 }
465 // Creates a temporary copy of the variable with a different type.
466 // Used primarily for syntactic correctness of textual assembly
467 // emission. Note that only basic information is copied, in
Jim Stichnoth31c95592014-12-19 12:51:35 -0800468 // particular not IsArgument, IsImplicitArgument, IgnoreLiveness,
469 // RegNumTmp, Weight, Live, LoVar, HiVar, VarsReal.
470 Variable *asType(Type Ty);
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700471
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700472 void emit(const Cfg *Func) const override;
Jim Stichnoth2e8bfbb2014-09-16 10:16:00 -0700473 using Operand::dump;
Jim Stichnothb56c8f42014-09-26 09:28:46 -0700474 void dump(const Cfg *Func, Ostream &Str) const override;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700475
476 static bool classof(const Operand *Operand) {
Jim Stichnoth800dab22014-09-20 12:25:02 -0700477 OperandKind Kind = Operand->getKind();
478 return Kind >= kVariable && Kind <= kVariable_Num;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700479 }
480
Jim Stichnoth800dab22014-09-20 12:25:02 -0700481protected:
Jim Stichnoth9a04c072014-12-11 15:51:42 -0800482 Variable(OperandKind K, Type Ty, SizeT Index)
483 : Operand(K, Ty), Number(Index), NameIndex(Cfg::IdentifierIndexInvalid),
484 IsArgument(false), IsImplicitArgument(false), IgnoreLiveness(false),
485 StackOffset(0), RegNum(NoRegister), RegNumTmp(NoRegister), Weight(1),
486 LoVar(NULL), HiVar(NULL) {
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700487 Vars = VarsReal;
488 Vars[0] = this;
489 NumVars = 1;
490 }
Jim Stichnoth31c95592014-12-19 12:51:35 -0800491 ~Variable() override {}
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700492 // Number is unique across all variables, and is used as a
493 // (bit)vector index for liveness analysis.
494 const SizeT Number;
Jim Stichnoth9a04c072014-12-11 15:51:42 -0800495 Cfg::IdentifierIndexType NameIndex;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700496 bool IsArgument;
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700497 bool IsImplicitArgument;
Jim Stichnoth47752552014-10-13 17:15:08 -0700498 // IgnoreLiveness means that the variable should be ignored when
499 // constructing and validating live ranges. This is usually
500 // reserved for the stack pointer.
501 bool IgnoreLiveness;
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700502 // StackOffset is the canonical location on stack (only if
Jim Stichnothad403532014-09-25 12:44:17 -0700503 // RegNum==NoRegister || IsArgument).
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700504 int32_t StackOffset;
505 // RegNum is the allocated register, or NoRegister if it isn't
506 // register-allocated.
507 int32_t RegNum;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700508 // RegNumTmp is the tentative assignment during register allocation.
509 int32_t RegNumTmp;
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700510 RegWeight Weight; // Register allocation priority
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700511 LiveRange Live;
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700512 // LoVar and HiVar are needed for lowering from 64 to 32 bits. When
513 // lowering from I64 to I32 on a 32-bit architecture, we split the
514 // variable into two machine-size pieces. LoVar is the low-order
515 // machine-size portion, and HiVar is the remaining high-order
516 // portion. TODO: It's wasteful to penalize all variables on all
517 // targets this way; use a sparser representation. It's also
518 // wasteful for a 64-bit target.
519 Variable *LoVar;
520 Variable *HiVar;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700521 // VarsReal (and Operand::Vars) are set up such that Vars[0] ==
522 // this.
523 Variable *VarsReal[1];
524};
525
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700526enum MetadataKind {
527 VMK_Uses, // Track only uses, not defs
528 VMK_SingleDefs, // Track uses+defs, but only record single def
529 VMK_All // Track uses+defs, including full def list
530};
Jim Stichnothad403532014-09-25 12:44:17 -0700531typedef std::vector<const Inst *> InstDefList;
532
533// VariableTracking tracks the metadata for a single variable. It is
534// only meant to be used internally by VariablesMetadata.
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700535class VariableTracking {
Jim Stichnoth7b451a92014-10-15 14:39:23 -0700536 // VariableTracking(const VariableTracking &) = delete;
537 VariableTracking &operator=(const VariableTracking &) = delete;
538
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700539public:
540 enum MultiDefState {
541 // TODO(stichnot): Consider using just a simple counter.
542 MDS_Unknown,
543 MDS_SingleDef,
Jim Stichnothad403532014-09-25 12:44:17 -0700544 MDS_MultiDefSingleBlock,
545 MDS_MultiDefMultiBlock
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700546 };
547 enum MultiBlockState {
548 MBS_Unknown,
549 MBS_SingleBlock,
550 MBS_MultiBlock
551 };
552 VariableTracking()
553 : MultiDef(MDS_Unknown), MultiBlock(MBS_Unknown), SingleUseNode(NULL),
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700554 SingleDefNode(NULL), FirstOrSingleDefinition(NULL) {}
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700555 MultiDefState getMultiDef() const { return MultiDef; }
556 MultiBlockState getMultiBlock() const { return MultiBlock; }
Jim Stichnothad403532014-09-25 12:44:17 -0700557 const Inst *getFirstDefinition() const;
558 const Inst *getSingleDefinition() const;
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700559 const InstDefList &getLatterDefinitions() const { return Definitions; }
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700560 const CfgNode *getNode() const { return SingleUseNode; }
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700561 void markUse(MetadataKind TrackingKind, const Inst *Instr,
562 const CfgNode *Node, bool IsFromDef, bool IsImplicit);
563 void markDef(MetadataKind TrackingKind, const Inst *Instr,
564 const CfgNode *Node);
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700565
566private:
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700567 MultiDefState MultiDef;
568 MultiBlockState MultiBlock;
569 const CfgNode *SingleUseNode;
Jim Stichnothad403532014-09-25 12:44:17 -0700570 const CfgNode *SingleDefNode;
Jim Stichnoth037fa1d2014-10-07 11:09:33 -0700571 // All definitions of the variable are collected here, in increasing
572 // order of instruction number.
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700573 InstDefList Definitions; // Only used if Kind==VMK_All
574 const Inst *FirstOrSingleDefinition; // == Definitions[0] if Kind==VMK_All
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700575};
576
577// VariablesMetadata analyzes and summarizes the metadata for the
578// complete set of Variables.
579class VariablesMetadata {
Jim Stichnoth7b451a92014-10-15 14:39:23 -0700580 VariablesMetadata(const VariablesMetadata &) = delete;
581 VariablesMetadata &operator=(const VariablesMetadata &) = delete;
582
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700583public:
584 VariablesMetadata(const Cfg *Func) : Func(Func) {}
Jim Stichnothad403532014-09-25 12:44:17 -0700585 // Initialize the state by traversing all instructions/variables in
586 // the CFG.
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700587 void init(MetadataKind TrackingKind);
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700588 // Add a single node. This is called by init(), and can be called
589 // incrementally from elsewhere, e.g. after edge-splitting.
590 void addNode(CfgNode *Node);
Jim Stichnothad403532014-09-25 12:44:17 -0700591 // Returns whether the given Variable is tracked in this object. It
592 // should only return false if changes were made to the CFG after
593 // running init(), in which case the state is stale and the results
594 // shouldn't be trusted (but it may be OK e.g. for dumping).
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700595 bool isTracked(const Variable *Var) const {
596 return Var->getIndex() < Metadata.size();
597 }
Jim Stichnothad403532014-09-25 12:44:17 -0700598
599 // Returns whether the given Variable has multiple definitions.
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700600 bool isMultiDef(const Variable *Var) const;
Jim Stichnothad403532014-09-25 12:44:17 -0700601 // Returns the first definition instruction of the given Variable.
602 // This is only valid for variables whose definitions are all within
603 // the same block, e.g. T after the lowered sequence "T=B; T+=C;
604 // A=T", for which getFirstDefinition(T) would return the "T=B"
605 // instruction. For variables with definitions span multiple
606 // blocks, NULL is returned.
607 const Inst *getFirstDefinition(const Variable *Var) const;
608 // Returns the definition instruction of the given Variable, when
609 // the variable has exactly one definition. Otherwise, NULL is
610 // returned.
611 const Inst *getSingleDefinition(const Variable *Var) const;
612 // Returns the list of all definition instructions of the given
613 // Variable.
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700614 const InstDefList &getLatterDefinitions(const Variable *Var) const;
Jim Stichnothad403532014-09-25 12:44:17 -0700615
616 // Returns whether the given Variable is live across multiple
617 // blocks. Mainly, this is used to partition Variables into
618 // single-block versus multi-block sets for leveraging sparsity in
619 // liveness analysis, and for implementing simple stack slot
620 // coalescing. As a special case, function arguments are always
621 // considered multi-block because they are live coming into the
622 // entry block.
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700623 bool isMultiBlock(const Variable *Var) const;
Jim Stichnothad403532014-09-25 12:44:17 -0700624 // Returns the node that the given Variable is used in, assuming
625 // isMultiBlock() returns false. Otherwise, NULL is returned.
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700626 const CfgNode *getLocalUseNode(const Variable *Var) const;
627
628private:
629 const Cfg *Func;
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700630 MetadataKind Kind;
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700631 std::vector<VariableTracking> Metadata;
Jim Stichnothad403532014-09-25 12:44:17 -0700632 const static InstDefList NoDefinitions;
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700633};
634
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700635} // end of namespace Ice
636
637#endif // SUBZERO_SRC_ICEOPERAND_H