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