blob: 73e51e5138387d8c1cbcf76159db5d5bf75c894a [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
21#include "IceDefs.h"
22#include "IceTypes.h"
23
24namespace Ice {
25
26class Operand {
27public:
28 enum OperandKind {
29 kConst_Base,
30 kConstInteger,
31 kConstFloat,
32 kConstDouble,
33 kConstRelocatable,
Matt Walad8f4a7d2014-06-18 09:55:03 -070034 kConstUndef,
Jim Stichnothf7c9a142014-04-29 10:52:43 -070035 kConst_Num,
36 kVariable,
37 // Target-specific operand classes use kTarget as the starting
38 // point for their Kind enum space.
39 kTarget
40 };
41 OperandKind getKind() const { return Kind; }
42 Type getType() const { return Ty; }
43
44 // Every Operand keeps an array of the Variables referenced in
45 // the operand. This is so that the liveness operations can get
46 // quick access to the variables of interest, without having to dig
47 // so far into the operand.
48 SizeT getNumVars() const { return NumVars; }
49 Variable *getVar(SizeT I) const {
50 assert(I < getNumVars());
51 return Vars[I];
52 }
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -070053 virtual void emit(const Cfg *Func) const = 0;
Jim Stichnothf7c9a142014-04-29 10:52:43 -070054 virtual void dump(const Cfg *Func) const = 0;
55
56 // Query whether this object was allocated in isolation, or added to
57 // some higher-level pool. This determines whether a containing
58 // object's destructor should delete this object. Generally,
59 // constants are pooled globally, variables are pooled per-CFG, and
60 // target-specific operands are not pooled.
61 virtual bool isPooled() const { return false; }
62
63 virtual ~Operand() {}
64
65protected:
66 Operand(OperandKind Kind, Type Ty)
67 : Ty(Ty), Kind(Kind), NumVars(0), Vars(NULL) {}
68
69 const Type Ty;
70 const OperandKind Kind;
71 // Vars and NumVars are initialized by the derived class.
72 SizeT NumVars;
73 Variable **Vars;
74
75private:
76 Operand(const Operand &) LLVM_DELETED_FUNCTION;
77 Operand &operator=(const Operand &) LLVM_DELETED_FUNCTION;
78};
79
80// Constant is the abstract base class for constants. All
81// constants are allocated from a global arena and are pooled.
82class Constant : public Operand {
83public:
Jim Stichnothf61d5b22014-05-23 13:31:24 -070084 uint32_t getPoolEntryID() const { return PoolEntryID; }
Jim Stichnothd97c7df2014-06-04 11:57:08 -070085 virtual void emit(const Cfg *Func) const { emit(Func->getContext()); }
86 virtual void dump(const Cfg *Func) const { dump(Func->getContext()); }
87 virtual void emit(GlobalContext *Ctx) const = 0;
88 virtual void dump(GlobalContext *Ctx) const = 0;
Jim Stichnothf7c9a142014-04-29 10:52:43 -070089
90 static bool classof(const Operand *Operand) {
91 OperandKind Kind = Operand->getKind();
92 return Kind >= kConst_Base && Kind <= kConst_Num;
93 }
94
95protected:
Jim Stichnothf61d5b22014-05-23 13:31:24 -070096 Constant(OperandKind Kind, Type Ty, uint32_t PoolEntryID)
97 : Operand(Kind, Ty), PoolEntryID(PoolEntryID) {
Jim Stichnothf7c9a142014-04-29 10:52:43 -070098 Vars = NULL;
99 NumVars = 0;
100 }
101 virtual ~Constant() {}
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700102 // PoolEntryID is an integer that uniquely identifies the constant
103 // within its constant pool. It is used for building the constant
104 // pool in the object code and for referencing its entries.
105 const uint32_t PoolEntryID;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700106
107private:
108 Constant(const Constant &) LLVM_DELETED_FUNCTION;
109 Constant &operator=(const Constant &) LLVM_DELETED_FUNCTION;
110};
111
112// ConstantPrimitive<> wraps a primitive type.
113template <typename T, Operand::OperandKind K>
114class ConstantPrimitive : public Constant {
115public:
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700116 static ConstantPrimitive *create(GlobalContext *Ctx, Type Ty, T Value,
117 uint32_t PoolEntryID) {
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700118 return new (Ctx->allocate<ConstantPrimitive>())
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700119 ConstantPrimitive(Ty, Value, PoolEntryID);
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700120 }
121 T getValue() const { return Value; }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700122 using Constant::emit;
Matt Wala928f1292014-07-07 16:50:46 -0700123 // The target needs to implement this for each ConstantPrimitive
124 // specialization.
125 virtual void emit(GlobalContext *Ctx) const;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700126 using Constant::dump;
127 virtual void dump(GlobalContext *Ctx) const {
128 Ostream &Str = Ctx->getStrDump();
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700129 Str << getValue();
130 }
131
132 static bool classof(const Operand *Operand) {
133 return Operand->getKind() == K;
134 }
135
136private:
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700137 ConstantPrimitive(Type Ty, T Value, uint32_t PoolEntryID)
138 : Constant(K, Ty, PoolEntryID), Value(Value) {}
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700139 ConstantPrimitive(const ConstantPrimitive &) LLVM_DELETED_FUNCTION;
140 ConstantPrimitive &operator=(const ConstantPrimitive &) LLVM_DELETED_FUNCTION;
141 virtual ~ConstantPrimitive() {}
142 const T Value;
143};
144
145typedef ConstantPrimitive<uint64_t, Operand::kConstInteger> ConstantInteger;
146typedef ConstantPrimitive<float, Operand::kConstFloat> ConstantFloat;
147typedef ConstantPrimitive<double, Operand::kConstDouble> ConstantDouble;
148
149// RelocatableTuple bundles the parameters that are used to
150// construct an ConstantRelocatable. It is done this way so that
151// ConstantRelocatable can fit into the global constant pool
152// template mechanism.
153class RelocatableTuple {
154 RelocatableTuple &operator=(const RelocatableTuple &) LLVM_DELETED_FUNCTION;
155
156public:
157 RelocatableTuple(const int64_t Offset, const IceString &Name,
158 bool SuppressMangling)
159 : Offset(Offset), Name(Name), SuppressMangling(SuppressMangling) {}
160 RelocatableTuple(const RelocatableTuple &Other)
161 : Offset(Other.Offset), Name(Other.Name),
162 SuppressMangling(Other.SuppressMangling) {}
163
164 const int64_t Offset;
165 const IceString Name;
166 bool SuppressMangling;
167};
168
169bool operator<(const RelocatableTuple &A, const RelocatableTuple &B);
170
171// ConstantRelocatable represents a symbolic constant combined with
172// a fixed offset.
173class ConstantRelocatable : public Constant {
174public:
175 static ConstantRelocatable *create(GlobalContext *Ctx, Type Ty,
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700176 const RelocatableTuple &Tuple,
177 uint32_t PoolEntryID) {
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700178 return new (Ctx->allocate<ConstantRelocatable>()) ConstantRelocatable(
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700179 Ty, Tuple.Offset, Tuple.Name, Tuple.SuppressMangling, PoolEntryID);
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700180 }
181 int64_t getOffset() const { return Offset; }
182 IceString getName() const { return Name; }
183 void setSuppressMangling(bool Value) { SuppressMangling = Value; }
184 bool getSuppressMangling() const { return SuppressMangling; }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700185 using Constant::emit;
186 using Constant::dump;
187 virtual void emit(GlobalContext *Ctx) const;
188 virtual void dump(GlobalContext *Ctx) const;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700189
190 static bool classof(const Operand *Operand) {
191 OperandKind Kind = Operand->getKind();
192 return Kind == kConstRelocatable;
193 }
194
195private:
196 ConstantRelocatable(Type Ty, int64_t Offset, const IceString &Name,
Jim Stichnothf61d5b22014-05-23 13:31:24 -0700197 bool SuppressMangling, uint32_t PoolEntryID)
198 : Constant(kConstRelocatable, Ty, PoolEntryID), Offset(Offset),
199 Name(Name), SuppressMangling(SuppressMangling) {}
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700200 ConstantRelocatable(const ConstantRelocatable &) LLVM_DELETED_FUNCTION;
201 ConstantRelocatable &
202 operator=(const ConstantRelocatable &) LLVM_DELETED_FUNCTION;
203 virtual ~ConstantRelocatable() {}
204 const int64_t Offset; // fixed offset to add
205 const IceString Name; // optional for debug/dump
206 bool SuppressMangling;
207};
208
Matt Walad8f4a7d2014-06-18 09:55:03 -0700209// ConstantUndef represents an unspecified bit pattern. Although it is
210// legal to lower ConstantUndef to any value, backends should try to
211// make code generation deterministic by lowering ConstantUndefs to 0.
212class ConstantUndef : public Constant {
213public:
214 static ConstantUndef *create(GlobalContext *Ctx, Type Ty,
215 uint32_t PoolEntryID) {
216 return new (Ctx->allocate<ConstantUndef>()) ConstantUndef(Ty, PoolEntryID);
217 }
218
219 using Constant::emit;
Matt Walae3777672014-07-31 09:06:17 -0700220 // The target needs to implement this.
221 virtual void emit(GlobalContext *Ctx) const;
Matt Walad8f4a7d2014-06-18 09:55:03 -0700222
223 using Constant::dump;
224 virtual void dump(GlobalContext *Ctx) const {
225 Ostream &Str = Ctx->getStrEmit();
226 Str << "undef";
227 }
228
229 static bool classof(const Operand *Operand) {
230 return Operand->getKind() == kConstUndef;
231 }
232
233private:
234 ConstantUndef(Type Ty, uint32_t PoolEntryID)
235 : Constant(kConstUndef, Ty, PoolEntryID) {}
236 ConstantUndef(const ConstantUndef &) LLVM_DELETED_FUNCTION;
237 ConstantUndef &operator=(const ConstantUndef &) LLVM_DELETED_FUNCTION;
238 virtual ~ConstantUndef() {}
239};
240
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700241// RegWeight is a wrapper for a uint32_t weight value, with a
242// special value that represents infinite weight, and an addWeight()
243// method that ensures that W+infinity=infinity.
244class RegWeight {
245public:
246 RegWeight() : Weight(0) {}
247 RegWeight(uint32_t Weight) : Weight(Weight) {}
248 const static uint32_t Inf = ~0; // Force regalloc to give a register
249 const static uint32_t Zero = 0; // Force regalloc NOT to give a register
250 void addWeight(uint32_t Delta) {
251 if (Delta == Inf)
252 Weight = Inf;
253 else if (Weight != Inf)
254 Weight += Delta;
255 }
256 void addWeight(const RegWeight &Other) { addWeight(Other.Weight); }
257 void setWeight(uint32_t Val) { Weight = Val; }
258 uint32_t getWeight() const { return Weight; }
259 bool isInf() const { return Weight == Inf; }
260
261private:
262 uint32_t Weight;
263};
264Ostream &operator<<(Ostream &Str, const RegWeight &W);
265bool operator<(const RegWeight &A, const RegWeight &B);
266bool operator<=(const RegWeight &A, const RegWeight &B);
267bool operator==(const RegWeight &A, const RegWeight &B);
268
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700269// LiveRange is a set of instruction number intervals representing
270// a variable's live range. Generally there is one interval per basic
271// block where the variable is live, but adjacent intervals get
272// coalesced into a single interval. LiveRange also includes a
273// weight, in case e.g. we want a live range to have higher weight
274// inside a loop.
275class LiveRange {
276public:
277 LiveRange() : Weight(0) {}
278
279 void reset() {
280 Range.clear();
281 Weight.setWeight(0);
282 }
283 void addSegment(InstNumberT Start, InstNumberT End);
284
285 bool endsBefore(const LiveRange &Other) const;
286 bool overlaps(const LiveRange &Other) const;
287 bool overlaps(InstNumberT OtherBegin) const;
288 bool containsValue(InstNumberT Value) const;
289 bool isEmpty() const { return Range.empty(); }
290 InstNumberT getStart() const {
291 return Range.empty() ? -1 : Range.begin()->first;
292 }
293
294 RegWeight getWeight() const { return Weight; }
295 void setWeight(const RegWeight &NewWeight) { Weight = NewWeight; }
296 void addWeight(uint32_t Delta) { Weight.addWeight(Delta); }
297 void dump(Ostream &Str) const;
298
299 // Defining USE_SET uses std::set to hold the segments instead of
300 // std::list. Using std::list will be slightly faster, but is more
301 // restrictive because new segments cannot be added in the middle.
302
303 //#define USE_SET
304
305private:
306 typedef std::pair<InstNumberT, InstNumberT> RangeElementType;
307#ifdef USE_SET
308 typedef std::set<RangeElementType> RangeType;
309#else
310 typedef std::list<RangeElementType> RangeType;
311#endif
312 RangeType Range;
313 RegWeight Weight;
314};
315
316Ostream &operator<<(Ostream &Str, const LiveRange &L);
317
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700318// Variable represents an operand that is register-allocated or
319// stack-allocated. If it is register-allocated, it will ultimately
320// have a non-negative RegNum field.
321class Variable : public Operand {
322public:
323 static Variable *create(Cfg *Func, Type Ty, const CfgNode *Node, SizeT Index,
324 const IceString &Name) {
325 return new (Func->allocate<Variable>()) Variable(Ty, Node, Index, Name);
326 }
327
328 SizeT getIndex() const { return Number; }
329 IceString getName() const;
330
331 Inst *getDefinition() const { return DefInst; }
332 void setDefinition(Inst *Inst, const CfgNode *Node);
333 void replaceDefinition(Inst *Inst, const CfgNode *Node);
334
335 const CfgNode *getLocalUseNode() const { return DefNode; }
336 bool isMultiblockLife() const { return (DefNode == NULL); }
337 void setUse(const Inst *Inst, const CfgNode *Node);
338
339 bool getIsArg() const { return IsArgument; }
Matt Wala45a06232014-07-09 16:33:22 -0700340 void setIsArg(Cfg *Func, bool IsArg = true);
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700341
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700342 int32_t getStackOffset() const { return StackOffset; }
343 void setStackOffset(int32_t Offset) { StackOffset = Offset; }
344
345 static const int32_t NoRegister = -1;
346 bool hasReg() const { return getRegNum() != NoRegister; }
347 int32_t getRegNum() const { return RegNum; }
348 void setRegNum(int32_t NewRegNum) {
349 // Regnum shouldn't be set more than once.
350 assert(!hasReg() || RegNum == NewRegNum);
351 RegNum = NewRegNum;
352 }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700353 bool hasRegTmp() const { return getRegNumTmp() != NoRegister; }
354 int32_t getRegNumTmp() const { return RegNumTmp; }
355 void setRegNumTmp(int32_t NewRegNum) { RegNumTmp = NewRegNum; }
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700356
357 RegWeight getWeight() const { return Weight; }
358 void setWeight(uint32_t NewWeight) { Weight = NewWeight; }
359 void setWeightInfinite() { Weight = RegWeight::Inf; }
360
361 Variable *getPreferredRegister() const { return RegisterPreference; }
362 bool getRegisterOverlap() const { return AllowRegisterOverlap; }
363 void setPreferredRegister(Variable *Prefer, bool Overlap) {
364 RegisterPreference = Prefer;
365 AllowRegisterOverlap = Overlap;
366 }
367
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700368 const LiveRange &getLiveRange() const { return Live; }
369 void setLiveRange(const LiveRange &Range) { Live = Range; }
370 void resetLiveRange() { Live.reset(); }
371 void addLiveRange(InstNumberT Start, InstNumberT End, uint32_t WeightDelta) {
372 assert(WeightDelta != RegWeight::Inf);
373 Live.addSegment(Start, End);
374 if (Weight.isInf())
375 Live.setWeight(RegWeight::Inf);
376 else
377 Live.addWeight(WeightDelta * Weight.getWeight());
378 }
379 void setLiveRangeInfiniteWeight() { Live.setWeight(RegWeight::Inf); }
380
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700381 Variable *getLo() const { return LoVar; }
382 Variable *getHi() const { return HiVar; }
383 void setLoHi(Variable *Lo, Variable *Hi) {
384 assert(LoVar == NULL);
385 assert(HiVar == NULL);
386 LoVar = Lo;
387 HiVar = Hi;
388 }
389 // Creates a temporary copy of the variable with a different type.
390 // Used primarily for syntactic correctness of textual assembly
391 // emission. Note that only basic information is copied, in
392 // particular not DefInst, IsArgument, Weight, RegisterPreference,
393 // AllowRegisterOverlap, LoVar, HiVar, VarsReal.
394 Variable asType(Type Ty);
395
396 virtual void emit(const Cfg *Func) const;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700397 virtual void dump(const Cfg *Func) const;
398
399 static bool classof(const Operand *Operand) {
400 return Operand->getKind() == kVariable;
401 }
402
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700403 // The destructor is public because of the asType() method.
404 virtual ~Variable() {}
405
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700406private:
407 Variable(Type Ty, const CfgNode *Node, SizeT Index, const IceString &Name)
408 : Operand(kVariable, Ty), Number(Index), Name(Name), DefInst(NULL),
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700409 DefNode(Node), IsArgument(false), StackOffset(0), RegNum(NoRegister),
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700410 RegNumTmp(NoRegister), Weight(1), RegisterPreference(NULL),
411 AllowRegisterOverlap(false), LoVar(NULL), HiVar(NULL) {
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700412 Vars = VarsReal;
413 Vars[0] = this;
414 NumVars = 1;
415 }
416 Variable(const Variable &) LLVM_DELETED_FUNCTION;
417 Variable &operator=(const Variable &) LLVM_DELETED_FUNCTION;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700418 // Number is unique across all variables, and is used as a
419 // (bit)vector index for liveness analysis.
420 const SizeT Number;
421 // Name is optional.
422 const IceString Name;
423 // DefInst is the instruction that produces this variable as its
424 // dest.
425 Inst *DefInst;
426 // DefNode is the node where this variable was produced, and is
427 // reset to NULL if it is used outside that node. This is used for
428 // detecting isMultiblockLife(). TODO: Collapse this to a single
429 // bit and use a separate pass to calculate the values across the
430 // Cfg. This saves space in the Variable, and removes the fragility
431 // of incrementally computing and maintaining the information.
432 const CfgNode *DefNode;
433 bool IsArgument;
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700434 // StackOffset is the canonical location on stack (only if
435 // RegNum<0 || IsArgument).
436 int32_t StackOffset;
437 // RegNum is the allocated register, or NoRegister if it isn't
438 // register-allocated.
439 int32_t RegNum;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700440 // RegNumTmp is the tentative assignment during register allocation.
441 int32_t RegNumTmp;
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700442 RegWeight Weight; // Register allocation priority
443 // RegisterPreference says that if possible, the register allocator
444 // should prefer the register that was assigned to this linked
445 // variable. It also allows a spill slot to share its stack
446 // location with another variable, if that variable does not get
447 // register-allocated and therefore has a stack location.
448 Variable *RegisterPreference;
449 // AllowRegisterOverlap says that it is OK to honor
450 // RegisterPreference and "share" a register even if the two live
451 // ranges overlap.
452 bool AllowRegisterOverlap;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700453 LiveRange Live;
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700454 // LoVar and HiVar are needed for lowering from 64 to 32 bits. When
455 // lowering from I64 to I32 on a 32-bit architecture, we split the
456 // variable into two machine-size pieces. LoVar is the low-order
457 // machine-size portion, and HiVar is the remaining high-order
458 // portion. TODO: It's wasteful to penalize all variables on all
459 // targets this way; use a sparser representation. It's also
460 // wasteful for a 64-bit target.
461 Variable *LoVar;
462 Variable *HiVar;
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700463 // VarsReal (and Operand::Vars) are set up such that Vars[0] ==
464 // this.
465 Variable *VarsReal[1];
466};
467
468} // end of namespace Ice
469
470#endif // SUBZERO_SRC_ICEOPERAND_H