Chromium Code Reviews| OLD | NEW |
|---|---|
| 1 //===- subzero/src/IceOperand.h - High-level operands -----------*- C++ -*-===// | 1 //===- subzero/src/IceOperand.h - High-level operands -----------*- C++ -*-===// |
| 2 // | 2 // |
| 3 // The Subzero Code Generator | 3 // The Subzero Code Generator |
| 4 // | 4 // |
| 5 // This file is distributed under the University of Illinois Open Source | 5 // This file is distributed under the University of Illinois Open Source |
| 6 // License. See LICENSE.TXT for details. | 6 // License. See LICENSE.TXT for details. |
| 7 // | 7 // |
| 8 //===----------------------------------------------------------------------===// | 8 //===----------------------------------------------------------------------===// |
| 9 // | 9 // |
| 10 // This file declares the Operand class and its target-independent | 10 // This file declares the Operand class and its target-independent |
| (...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 48 // Target-specific operand classes use kTarget as the starting | 48 // Target-specific operand classes use kTarget as the starting |
| 49 // point for their Kind enum space. Note that the value-spaces are shared | 49 // point for their Kind enum space. Note that the value-spaces are shared |
| 50 // across targets. To avoid confusion over the definition of shared | 50 // across targets. To avoid confusion over the definition of shared |
| 51 // values, an object specific to one target should never be passed | 51 // values, an object specific to one target should never be passed |
| 52 // to a different target. | 52 // to a different target. |
| 53 kTarget | 53 kTarget |
| 54 }; | 54 }; |
| 55 OperandKind getKind() const { return Kind; } | 55 OperandKind getKind() const { return Kind; } |
| 56 Type getType() const { return Ty; } | 56 Type getType() const { return Ty; } |
| 57 | 57 |
| 58 // Every Operand keeps an array of the Variables referenced in | 58 /// Every Operand keeps an array of the Variables referenced in |
| 59 // the operand. This is so that the liveness operations can get | 59 /// the operand. This is so that the liveness operations can get |
| 60 // quick access to the variables of interest, without having to dig | 60 /// quick access to the variables of interest, without having to dig |
| 61 // so far into the operand. | 61 /// so far into the operand. |
| 62 SizeT getNumVars() const { return NumVars; } | 62 SizeT getNumVars() const { return NumVars; } |
| 63 Variable *getVar(SizeT I) const { | 63 Variable *getVar(SizeT I) const { |
| 64 assert(I < getNumVars()); | 64 assert(I < getNumVars()); |
| 65 return Vars[I]; | 65 return Vars[I]; |
| 66 } | 66 } |
| 67 virtual void emit(const Cfg *Func) const = 0; | 67 virtual void emit(const Cfg *Func) const = 0; |
| 68 // The dump(Func,Str) implementation must be sure to handle the | 68 /// The dump(Func,Str) implementation must be sure to handle the |
| 69 // situation where Func==nullptr. | 69 /// situation where Func==nullptr. |
|
Karl
2015/07/06 18:08:48
Bundle this comment with next several dump methods
ascull
2015/07/06 19:29:09
Done.
| |
| 70 virtual void dump(const Cfg *Func, Ostream &Str) const = 0; | 70 virtual void dump(const Cfg *Func, Ostream &Str) const = 0; |
| 71 void dump(const Cfg *Func) const { | 71 void dump(const Cfg *Func) const { |
| 72 if (!BuildDefs::dump()) | 72 if (!BuildDefs::dump()) |
| 73 return; | 73 return; |
| 74 assert(Func); | 74 assert(Func); |
| 75 dump(Func, Func->getContext()->getStrDump()); | 75 dump(Func, Func->getContext()->getStrDump()); |
| 76 } | 76 } |
| 77 void dump(Ostream &Str) const { | 77 void dump(Ostream &Str) const { |
| 78 if (BuildDefs::dump()) | 78 if (BuildDefs::dump()) |
| 79 dump(nullptr, Str); | 79 dump(nullptr, Str); |
| 80 } | 80 } |
| 81 | 81 |
| 82 protected: | 82 protected: |
| 83 Operand(OperandKind Kind, Type Ty) : Ty(Ty), Kind(Kind) {} | 83 Operand(OperandKind Kind, Type Ty) : Ty(Ty), Kind(Kind) {} |
| 84 virtual ~Operand() = default; | 84 virtual ~Operand() = default; |
| 85 | 85 |
| 86 const Type Ty; | 86 const Type Ty; |
| 87 const OperandKind Kind; | 87 const OperandKind Kind; |
| 88 // Vars and NumVars are initialized by the derived class. | 88 /// Vars and NumVars are initialized by the derived class. |
| 89 SizeT NumVars = 0; | 89 SizeT NumVars = 0; |
| 90 Variable **Vars = nullptr; | 90 Variable **Vars = nullptr; |
| 91 }; | 91 }; |
| 92 | 92 |
| 93 template <class StreamType> | 93 template <class StreamType> |
| 94 inline StreamType &operator<<(StreamType &Str, const Operand &Op) { | 94 inline StreamType &operator<<(StreamType &Str, const Operand &Op) { |
| 95 Op.dump(Str); | 95 Op.dump(Str); |
| 96 return Str; | 96 return Str; |
| 97 } | 97 } |
| 98 | 98 |
| 99 // Constant is the abstract base class for constants. All | 99 /// Constant is the abstract base class for constants. All |
| 100 // constants are allocated from a global arena and are pooled. | 100 /// constants are allocated from a global arena and are pooled. |
| 101 class Constant : public Operand { | 101 class Constant : public Operand { |
| 102 Constant() = delete; | 102 Constant() = delete; |
| 103 Constant(const Constant &) = delete; | 103 Constant(const Constant &) = delete; |
| 104 Constant &operator=(const Constant &) = delete; | 104 Constant &operator=(const Constant &) = delete; |
| 105 | 105 |
| 106 public: | 106 public: |
| 107 void emitPoolLabel(Ostream &Str) const { | 107 void emitPoolLabel(Ostream &Str) const { |
| 108 Str << ".L$" << getType() << "$" << PoolEntryID; | 108 Str << ".L$" << getType() << "$" << PoolEntryID; |
| 109 } | 109 } |
| 110 void emit(const Cfg *Func) const override { emit(Func->getTarget()); } | 110 void emit(const Cfg *Func) const override { emit(Func->getTarget()); } |
| 111 virtual void emit(TargetLowering *Target) const = 0; | 111 virtual void emit(TargetLowering *Target) const = 0; |
| 112 | 112 |
| 113 static bool classof(const Operand *Operand) { | 113 static bool classof(const Operand *Operand) { |
| 114 OperandKind Kind = Operand->getKind(); | 114 OperandKind Kind = Operand->getKind(); |
| 115 return Kind >= kConst_Base && Kind <= kConst_Num; | 115 return Kind >= kConst_Base && Kind <= kConst_Num; |
| 116 } | 116 } |
| 117 | 117 |
| 118 // Judge if this given immediate should be randomized or pooled | 118 /// Judge if this given immediate should be randomized or pooled |
| 119 // By default should return false, only constant integers should | 119 /// By default should return false, only constant integers should |
| 120 // truly go through this method. | 120 /// truly go through this method. |
| 121 virtual bool shouldBeRandomizedOrPooled(const GlobalContext *Ctx) { | 121 virtual bool shouldBeRandomizedOrPooled(const GlobalContext *Ctx) { |
| 122 (void)Ctx; | 122 (void)Ctx; |
| 123 return false; | 123 return false; |
| 124 } | 124 } |
| 125 | 125 |
| 126 void setShouldBePooled(bool R) { shouldBePooled = R; } | 126 void setShouldBePooled(bool R) { shouldBePooled = R; } |
| 127 | 127 |
| 128 bool getShouldBePooled() const { return shouldBePooled; } | 128 bool getShouldBePooled() const { return shouldBePooled; } |
| 129 | 129 |
| 130 protected: | 130 protected: |
| 131 Constant(OperandKind Kind, Type Ty, uint32_t PoolEntryID) | 131 Constant(OperandKind Kind, Type Ty, uint32_t PoolEntryID) |
| 132 : Operand(Kind, Ty), PoolEntryID(PoolEntryID), shouldBePooled(false) { | 132 : Operand(Kind, Ty), PoolEntryID(PoolEntryID), shouldBePooled(false) { |
| 133 Vars = nullptr; | 133 Vars = nullptr; |
| 134 NumVars = 0; | 134 NumVars = 0; |
| 135 } | 135 } |
| 136 // PoolEntryID is an integer that uniquely identifies the constant | 136 /// PoolEntryID is an integer that uniquely identifies the constant |
| 137 // within its constant pool. It is used for building the constant | 137 /// within its constant pool. It is used for building the constant |
| 138 // pool in the object code and for referencing its entries. | 138 /// pool in the object code and for referencing its entries. |
| 139 const uint32_t PoolEntryID; | 139 const uint32_t PoolEntryID; |
| 140 // Whether we should pool this constant. Usually Float/Double and pooled | 140 /// Whether we should pool this constant. Usually Float/Double and pooled |
| 141 // Integers should be flagged true. | 141 /// Integers should be flagged true. |
| 142 bool shouldBePooled; | 142 bool shouldBePooled; |
| 143 }; | 143 }; |
| 144 | 144 |
| 145 // ConstantPrimitive<> wraps a primitive type. | 145 /// ConstantPrimitive<> wraps a primitive type. |
| 146 template <typename T, Operand::OperandKind K> | 146 template <typename T, Operand::OperandKind K> |
| 147 class ConstantPrimitive : public Constant { | 147 class ConstantPrimitive : public Constant { |
| 148 ConstantPrimitive() = delete; | 148 ConstantPrimitive() = delete; |
| 149 ConstantPrimitive(const ConstantPrimitive &) = delete; | 149 ConstantPrimitive(const ConstantPrimitive &) = delete; |
| 150 ConstantPrimitive &operator=(const ConstantPrimitive &) = delete; | 150 ConstantPrimitive &operator=(const ConstantPrimitive &) = delete; |
| 151 | 151 |
| 152 public: | 152 public: |
| 153 typedef T PrimType; | 153 typedef T PrimType; |
| 154 | 154 |
| 155 static ConstantPrimitive *create(GlobalContext *Ctx, Type Ty, PrimType Value, | 155 static ConstantPrimitive *create(GlobalContext *Ctx, Type Ty, PrimType Value, |
| (...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 191 template <> | 191 template <> |
| 192 inline void ConstantInteger32::dump(const Cfg *, Ostream &Str) const { | 192 inline void ConstantInteger32::dump(const Cfg *, Ostream &Str) const { |
| 193 if (!BuildDefs::dump()) | 193 if (!BuildDefs::dump()) |
| 194 return; | 194 return; |
| 195 if (getType() == IceType_i1) | 195 if (getType() == IceType_i1) |
| 196 Str << (getValue() ? "true" : "false"); | 196 Str << (getValue() ? "true" : "false"); |
| 197 else | 197 else |
| 198 Str << static_cast<int32_t>(getValue()); | 198 Str << static_cast<int32_t>(getValue()); |
| 199 } | 199 } |
| 200 | 200 |
| 201 // Specialization of the template member function for ConstantInteger32 | 201 /// Specialization of the template member function for ConstantInteger32 |
| 202 template <> | 202 template <> |
| 203 bool ConstantInteger32::shouldBeRandomizedOrPooled(const GlobalContext *Ctx); | 203 bool ConstantInteger32::shouldBeRandomizedOrPooled(const GlobalContext *Ctx); |
| 204 | 204 |
| 205 template <> | 205 template <> |
| 206 inline void ConstantInteger64::dump(const Cfg *, Ostream &Str) const { | 206 inline void ConstantInteger64::dump(const Cfg *, Ostream &Str) const { |
| 207 if (!BuildDefs::dump()) | 207 if (!BuildDefs::dump()) |
| 208 return; | 208 return; |
| 209 assert(getType() == IceType_i64); | 209 assert(getType() == IceType_i64); |
| 210 Str << static_cast<int64_t>(getValue()); | 210 Str << static_cast<int64_t>(getValue()); |
| 211 } | 211 } |
| 212 | 212 |
| 213 // RelocatableTuple bundles the parameters that are used to | 213 /// RelocatableTuple bundles the parameters that are used to |
| 214 // construct an ConstantRelocatable. It is done this way so that | 214 /// construct an ConstantRelocatable. It is done this way so that |
| 215 // ConstantRelocatable can fit into the global constant pool | 215 /// ConstantRelocatable can fit into the global constant pool |
| 216 // template mechanism. | 216 /// template mechanism. |
| 217 class RelocatableTuple { | 217 class RelocatableTuple { |
| 218 RelocatableTuple() = delete; | 218 RelocatableTuple() = delete; |
| 219 RelocatableTuple &operator=(const RelocatableTuple &) = delete; | 219 RelocatableTuple &operator=(const RelocatableTuple &) = delete; |
| 220 | 220 |
| 221 public: | 221 public: |
| 222 RelocatableTuple(const RelocOffsetT Offset, const IceString &Name, | 222 RelocatableTuple(const RelocOffsetT Offset, const IceString &Name, |
| 223 bool SuppressMangling) | 223 bool SuppressMangling) |
| 224 : Offset(Offset), Name(Name), SuppressMangling(SuppressMangling) {} | 224 : Offset(Offset), Name(Name), SuppressMangling(SuppressMangling) {} |
| 225 RelocatableTuple(const RelocatableTuple &) = default; | 225 RelocatableTuple(const RelocatableTuple &) = default; |
| 226 | 226 |
| 227 const RelocOffsetT Offset; | 227 const RelocOffsetT Offset; |
| 228 const IceString Name; | 228 const IceString Name; |
| 229 bool SuppressMangling; | 229 bool SuppressMangling; |
| 230 }; | 230 }; |
| 231 | 231 |
| 232 bool operator==(const RelocatableTuple &A, const RelocatableTuple &B); | 232 bool operator==(const RelocatableTuple &A, const RelocatableTuple &B); |
| 233 | 233 |
| 234 // ConstantRelocatable represents a symbolic constant combined with | 234 /// ConstantRelocatable represents a symbolic constant combined with |
| 235 // a fixed offset. | 235 /// a fixed offset. |
| 236 class ConstantRelocatable : public Constant { | 236 class ConstantRelocatable : public Constant { |
| 237 ConstantRelocatable() = delete; | 237 ConstantRelocatable() = delete; |
| 238 ConstantRelocatable(const ConstantRelocatable &) = delete; | 238 ConstantRelocatable(const ConstantRelocatable &) = delete; |
| 239 ConstantRelocatable &operator=(const ConstantRelocatable &) = delete; | 239 ConstantRelocatable &operator=(const ConstantRelocatable &) = delete; |
| 240 | 240 |
| 241 public: | 241 public: |
| 242 static ConstantRelocatable *create(GlobalContext *Ctx, Type Ty, | 242 static ConstantRelocatable *create(GlobalContext *Ctx, Type Ty, |
| 243 const RelocatableTuple &Tuple, | 243 const RelocatableTuple &Tuple, |
| 244 uint32_t PoolEntryID) { | 244 uint32_t PoolEntryID) { |
| 245 assert(!Ctx->isIRGenerationDisabled() && | 245 assert(!Ctx->isIRGenerationDisabled() && |
| (...skipping 15 matching lines...) Expand all Loading... | |
| 261 static bool classof(const Operand *Operand) { | 261 static bool classof(const Operand *Operand) { |
| 262 OperandKind Kind = Operand->getKind(); | 262 OperandKind Kind = Operand->getKind(); |
| 263 return Kind == kConstRelocatable; | 263 return Kind == kConstRelocatable; |
| 264 } | 264 } |
| 265 | 265 |
| 266 private: | 266 private: |
| 267 ConstantRelocatable(Type Ty, RelocOffsetT Offset, const IceString &Name, | 267 ConstantRelocatable(Type Ty, RelocOffsetT Offset, const IceString &Name, |
| 268 bool SuppressMangling, uint32_t PoolEntryID) | 268 bool SuppressMangling, uint32_t PoolEntryID) |
| 269 : Constant(kConstRelocatable, Ty, PoolEntryID), Offset(Offset), | 269 : Constant(kConstRelocatable, Ty, PoolEntryID), Offset(Offset), |
| 270 Name(Name), SuppressMangling(SuppressMangling) {} | 270 Name(Name), SuppressMangling(SuppressMangling) {} |
| 271 const RelocOffsetT Offset; // fixed offset to add | 271 const RelocOffsetT Offset; /// fixed offset to add |
| 272 const IceString Name; // optional for debug/dump | 272 const IceString Name; /// optional for debug/dump |
| 273 bool SuppressMangling; | 273 bool SuppressMangling; |
| 274 }; | 274 }; |
| 275 | 275 |
| 276 // ConstantUndef represents an unspecified bit pattern. Although it is | 276 /// ConstantUndef represents an unspecified bit pattern. Although it is |
| 277 // legal to lower ConstantUndef to any value, backends should try to | 277 /// legal to lower ConstantUndef to any value, backends should try to |
| 278 // make code generation deterministic by lowering ConstantUndefs to 0. | 278 /// make code generation deterministic by lowering ConstantUndefs to 0. |
| 279 class ConstantUndef : public Constant { | 279 class ConstantUndef : public Constant { |
| 280 ConstantUndef() = delete; | 280 ConstantUndef() = delete; |
| 281 ConstantUndef(const ConstantUndef &) = delete; | 281 ConstantUndef(const ConstantUndef &) = delete; |
| 282 ConstantUndef &operator=(const ConstantUndef &) = delete; | 282 ConstantUndef &operator=(const ConstantUndef &) = delete; |
| 283 | 283 |
| 284 public: | 284 public: |
| 285 static ConstantUndef *create(GlobalContext *Ctx, Type Ty, | 285 static ConstantUndef *create(GlobalContext *Ctx, Type Ty, |
| 286 uint32_t PoolEntryID) { | 286 uint32_t PoolEntryID) { |
| 287 assert(!Ctx->isIRGenerationDisabled() && | 287 assert(!Ctx->isIRGenerationDisabled() && |
| 288 "Attempt to build undefined constant when IR generation disabled"); | 288 "Attempt to build undefined constant when IR generation disabled"); |
| (...skipping 10 matching lines...) Expand all Loading... | |
| 299 | 299 |
| 300 static bool classof(const Operand *Operand) { | 300 static bool classof(const Operand *Operand) { |
| 301 return Operand->getKind() == kConstUndef; | 301 return Operand->getKind() == kConstUndef; |
| 302 } | 302 } |
| 303 | 303 |
| 304 private: | 304 private: |
| 305 ConstantUndef(Type Ty, uint32_t PoolEntryID) | 305 ConstantUndef(Type Ty, uint32_t PoolEntryID) |
| 306 : Constant(kConstUndef, Ty, PoolEntryID) {} | 306 : Constant(kConstUndef, Ty, PoolEntryID) {} |
| 307 }; | 307 }; |
| 308 | 308 |
| 309 // RegWeight is a wrapper for a uint32_t weight value, with a | 309 /// RegWeight is a wrapper for a uint32_t weight value, with a |
| 310 // special value that represents infinite weight, and an addWeight() | 310 /// special value that represents infinite weight, and an addWeight() |
| 311 // method that ensures that W+infinity=infinity. | 311 /// method that ensures that W+infinity=infinity. |
| 312 class RegWeight { | 312 class RegWeight { |
| 313 public: | 313 public: |
| 314 RegWeight() = default; | 314 RegWeight() = default; |
| 315 explicit RegWeight(uint32_t Weight) : Weight(Weight) {} | 315 explicit RegWeight(uint32_t Weight) : Weight(Weight) {} |
| 316 RegWeight(const RegWeight &) = default; | 316 RegWeight(const RegWeight &) = default; |
| 317 RegWeight &operator=(const RegWeight &) = default; | 317 RegWeight &operator=(const RegWeight &) = default; |
| 318 const static uint32_t Inf = ~0; // Force regalloc to give a register | 318 const static uint32_t Inf = ~0; /// Force regalloc to give a register |
| 319 const static uint32_t Zero = 0; // Force regalloc NOT to give a register | 319 const static uint32_t Zero = 0; /// Force regalloc NOT to give a register |
| 320 void addWeight(uint32_t Delta) { | 320 void addWeight(uint32_t Delta) { |
| 321 if (Delta == Inf) | 321 if (Delta == Inf) |
| 322 Weight = Inf; | 322 Weight = Inf; |
| 323 else if (Weight != Inf) | 323 else if (Weight != Inf) |
| 324 Weight += Delta; | 324 Weight += Delta; |
| 325 } | 325 } |
| 326 void addWeight(const RegWeight &Other) { addWeight(Other.Weight); } | 326 void addWeight(const RegWeight &Other) { addWeight(Other.Weight); } |
| 327 void setWeight(uint32_t Val) { Weight = Val; } | 327 void setWeight(uint32_t Val) { Weight = Val; } |
| 328 uint32_t getWeight() const { return Weight; } | 328 uint32_t getWeight() const { return Weight; } |
| 329 bool isInf() const { return Weight == Inf; } | 329 bool isInf() const { return Weight == Inf; } |
| 330 bool isZero() const { return Weight == Zero; } | 330 bool isZero() const { return Weight == Zero; } |
| 331 | 331 |
| 332 private: | 332 private: |
| 333 uint32_t Weight = 0; | 333 uint32_t Weight = 0; |
| 334 }; | 334 }; |
| 335 Ostream &operator<<(Ostream &Str, const RegWeight &W); | 335 Ostream &operator<<(Ostream &Str, const RegWeight &W); |
| 336 bool operator<(const RegWeight &A, const RegWeight &B); | 336 bool operator<(const RegWeight &A, const RegWeight &B); |
| 337 bool operator<=(const RegWeight &A, const RegWeight &B); | 337 bool operator<=(const RegWeight &A, const RegWeight &B); |
| 338 bool operator==(const RegWeight &A, const RegWeight &B); | 338 bool operator==(const RegWeight &A, const RegWeight &B); |
| 339 | 339 |
| 340 // LiveRange is a set of instruction number intervals representing | 340 /// LiveRange is a set of instruction number intervals representing |
| 341 // a variable's live range. Generally there is one interval per basic | 341 /// a variable's live range. Generally there is one interval per basic |
| 342 // block where the variable is live, but adjacent intervals get | 342 /// block where the variable is live, but adjacent intervals get |
| 343 // coalesced into a single interval. LiveRange also includes a | 343 /// coalesced into a single interval. LiveRange also includes a |
| 344 // weight, in case e.g. we want a live range to have higher weight | 344 /// weight, in case e.g. we want a live range to have higher weight |
| 345 // inside a loop. | 345 /// inside a loop. |
| 346 class LiveRange { | 346 class LiveRange { |
| 347 public: | 347 public: |
| 348 LiveRange() = default; | 348 LiveRange() = default; |
| 349 // Special constructor for building a kill set. The advantage is | 349 /// Special constructor for building a kill set. The advantage is |
| 350 // that we can reserve the right amount of space in advance. | 350 /// that we can reserve the right amount of space in advance. |
| 351 explicit LiveRange(const std::vector<InstNumberT> &Kills) { | 351 explicit LiveRange(const std::vector<InstNumberT> &Kills) { |
| 352 Range.reserve(Kills.size()); | 352 Range.reserve(Kills.size()); |
| 353 for (InstNumberT I : Kills) | 353 for (InstNumberT I : Kills) |
| 354 addSegment(I, I); | 354 addSegment(I, I); |
| 355 } | 355 } |
| 356 LiveRange(const LiveRange &) = default; | 356 LiveRange(const LiveRange &) = default; |
| 357 LiveRange &operator=(const LiveRange &) = default; | 357 LiveRange &operator=(const LiveRange &) = default; |
| 358 | 358 |
| 359 void reset() { | 359 void reset() { |
| 360 Range.clear(); | 360 Range.clear(); |
| (...skipping 14 matching lines...) Expand all Loading... | |
| 375 void untrim() { TrimmedBegin = Range.begin(); } | 375 void untrim() { TrimmedBegin = Range.begin(); } |
| 376 void trim(InstNumberT Lower); | 376 void trim(InstNumberT Lower); |
| 377 | 377 |
| 378 RegWeight getWeight() const { return Weight; } | 378 RegWeight getWeight() const { return Weight; } |
| 379 void setWeight(const RegWeight &NewWeight) { Weight = NewWeight; } | 379 void setWeight(const RegWeight &NewWeight) { Weight = NewWeight; } |
| 380 void addWeight(uint32_t Delta) { Weight.addWeight(Delta); } | 380 void addWeight(uint32_t Delta) { Weight.addWeight(Delta); } |
| 381 void dump(Ostream &Str) const; | 381 void dump(Ostream &Str) const; |
| 382 | 382 |
| 383 private: | 383 private: |
| 384 typedef std::pair<InstNumberT, InstNumberT> RangeElementType; | 384 typedef std::pair<InstNumberT, InstNumberT> RangeElementType; |
| 385 // RangeType is arena-allocated from the Cfg's allocator. | 385 /// RangeType is arena-allocated from the Cfg's allocator. |
| 386 typedef std::vector<RangeElementType, CfgLocalAllocator<RangeElementType>> | 386 typedef std::vector<RangeElementType, CfgLocalAllocator<RangeElementType>> |
| 387 RangeType; | 387 RangeType; |
| 388 RangeType Range; | 388 RangeType Range; |
| 389 RegWeight Weight = RegWeight(0); | 389 RegWeight Weight = RegWeight(0); |
| 390 // TrimmedBegin is an optimization for the overlaps() computation. | 390 /// TrimmedBegin is an optimization for the overlaps() computation. |
| 391 // Since the linear-scan algorithm always calls it as overlaps(Cur) | 391 /// Since the linear-scan algorithm always calls it as overlaps(Cur) |
| 392 // and Cur advances monotonically according to live range start, we | 392 /// and Cur advances monotonically according to live range start, we |
| 393 // can optimize overlaps() by ignoring all segments that end before | 393 /// can optimize overlaps() by ignoring all segments that end before |
| 394 // the start of Cur's range. The linear-scan code enables this by | 394 /// the start of Cur's range. The linear-scan code enables this by |
| 395 // calling trim() on the ranges of interest as Cur advances. Note | 395 /// calling trim() on the ranges of interest as Cur advances. Note |
| 396 // that linear-scan also has to initialize TrimmedBegin at the | 396 /// that linear-scan also has to initialize TrimmedBegin at the |
| 397 // beginning by calling untrim(). | 397 /// beginning by calling untrim(). |
| 398 RangeType::const_iterator TrimmedBegin; | 398 RangeType::const_iterator TrimmedBegin; |
| 399 }; | 399 }; |
| 400 | 400 |
| 401 Ostream &operator<<(Ostream &Str, const LiveRange &L); | 401 Ostream &operator<<(Ostream &Str, const LiveRange &L); |
| 402 | 402 |
| 403 // Variable represents an operand that is register-allocated or | 403 /// Variable represents an operand that is register-allocated or |
| 404 // stack-allocated. If it is register-allocated, it will ultimately | 404 /// stack-allocated. If it is register-allocated, it will ultimately |
| 405 // have a non-negative RegNum field. | 405 /// have a non-negative RegNum field. |
| 406 class Variable : public Operand { | 406 class Variable : public Operand { |
| 407 Variable() = delete; | 407 Variable() = delete; |
| 408 Variable(const Variable &) = delete; | 408 Variable(const Variable &) = delete; |
| 409 Variable &operator=(const Variable &) = delete; | 409 Variable &operator=(const Variable &) = delete; |
| 410 | 410 |
| 411 public: | 411 public: |
| 412 static Variable *create(Cfg *Func, Type Ty, SizeT Index) { | 412 static Variable *create(Cfg *Func, Type Ty, SizeT Index) { |
| 413 return new (Func->allocate<Variable>()) Variable(kVariable, Ty, Index); | 413 return new (Func->allocate<Variable>()) Variable(kVariable, Ty, Index); |
| 414 } | 414 } |
| 415 | 415 |
| (...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 479 } | 479 } |
| 480 | 480 |
| 481 Variable *getLo() const { return LoVar; } | 481 Variable *getLo() const { return LoVar; } |
| 482 Variable *getHi() const { return HiVar; } | 482 Variable *getHi() const { return HiVar; } |
| 483 void setLoHi(Variable *Lo, Variable *Hi) { | 483 void setLoHi(Variable *Lo, Variable *Hi) { |
| 484 assert(LoVar == nullptr); | 484 assert(LoVar == nullptr); |
| 485 assert(HiVar == nullptr); | 485 assert(HiVar == nullptr); |
| 486 LoVar = Lo; | 486 LoVar = Lo; |
| 487 HiVar = Hi; | 487 HiVar = Hi; |
| 488 } | 488 } |
| 489 // Creates a temporary copy of the variable with a different type. | 489 /// Creates a temporary copy of the variable with a different type. |
| 490 // Used primarily for syntactic correctness of textual assembly | 490 /// Used primarily for syntactic correctness of textual assembly |
| 491 // emission. Note that only basic information is copied, in | 491 /// emission. Note that only basic information is copied, in |
| 492 // particular not IsArgument, IsImplicitArgument, IgnoreLiveness, | 492 /// particular not IsArgument, IsImplicitArgument, IgnoreLiveness, |
| 493 // RegNumTmp, Weight, Live, LoVar, HiVar, VarsReal. | 493 /// RegNumTmp, Weight, Live, LoVar, HiVar, VarsReal. |
| 494 Variable *asType(Type Ty); | 494 Variable *asType(Type Ty); |
| 495 | 495 |
| 496 void emit(const Cfg *Func) const override; | 496 void emit(const Cfg *Func) const override; |
| 497 using Operand::dump; | 497 using Operand::dump; |
| 498 void dump(const Cfg *Func, Ostream &Str) const override; | 498 void dump(const Cfg *Func, Ostream &Str) const override; |
| 499 | 499 |
| 500 static bool classof(const Operand *Operand) { | 500 static bool classof(const Operand *Operand) { |
| 501 OperandKind Kind = Operand->getKind(); | 501 OperandKind Kind = Operand->getKind(); |
| 502 return Kind >= kVariable && Kind <= kVariable_Num; | 502 return Kind >= kVariable && Kind <= kVariable_Num; |
| 503 } | 503 } |
| 504 | 504 |
| 505 protected: | 505 protected: |
| 506 Variable(OperandKind K, Type Ty, SizeT Index) | 506 Variable(OperandKind K, Type Ty, SizeT Index) |
| 507 : Operand(K, Ty), Number(Index) { | 507 : Operand(K, Ty), Number(Index) { |
| 508 Vars = VarsReal; | 508 Vars = VarsReal; |
| 509 Vars[0] = this; | 509 Vars[0] = this; |
| 510 NumVars = 1; | 510 NumVars = 1; |
| 511 } | 511 } |
| 512 // Number is unique across all variables, and is used as a | 512 /// Number is unique across all variables, and is used as a |
| 513 // (bit)vector index for liveness analysis. | 513 /// (bit)vector index for liveness analysis. |
| 514 const SizeT Number; | 514 const SizeT Number; |
| 515 Cfg::IdentifierIndexType NameIndex = Cfg::IdentifierIndexInvalid; | 515 Cfg::IdentifierIndexType NameIndex = Cfg::IdentifierIndexInvalid; |
| 516 bool IsArgument = false; | 516 bool IsArgument = false; |
| 517 bool IsImplicitArgument = false; | 517 bool IsImplicitArgument = false; |
| 518 // IgnoreLiveness means that the variable should be ignored when | 518 /// IgnoreLiveness means that the variable should be ignored when |
| 519 // constructing and validating live ranges. This is usually | 519 /// constructing and validating live ranges. This is usually |
| 520 // reserved for the stack pointer. | 520 /// reserved for the stack pointer. |
| 521 bool IgnoreLiveness = false; | 521 bool IgnoreLiveness = false; |
| 522 // StackOffset is the canonical location on stack (only if | 522 /// StackOffset is the canonical location on stack (only if |
| 523 // RegNum==NoRegister || IsArgument). | 523 /// RegNum==NoRegister || IsArgument). |
| 524 int32_t StackOffset = 0; | 524 int32_t StackOffset = 0; |
| 525 // RegNum is the allocated register, or NoRegister if it isn't | 525 /// RegNum is the allocated register, or NoRegister if it isn't |
| 526 // register-allocated. | 526 /// register-allocated. |
| 527 int32_t RegNum = NoRegister; | 527 int32_t RegNum = NoRegister; |
| 528 // RegNumTmp is the tentative assignment during register allocation. | 528 /// RegNumTmp is the tentative assignment during register allocation. |
| 529 int32_t RegNumTmp = NoRegister; | 529 int32_t RegNumTmp = NoRegister; |
| 530 RegWeight Weight = RegWeight(1); // Register allocation priority | 530 RegWeight Weight = RegWeight(1); // Register allocation priority |
| 531 LiveRange Live; | 531 LiveRange Live; |
| 532 // LoVar and HiVar are needed for lowering from 64 to 32 bits. When | 532 // LoVar and HiVar are needed for lowering from 64 to 32 bits. When |
| 533 // lowering from I64 to I32 on a 32-bit architecture, we split the | 533 // lowering from I64 to I32 on a 32-bit architecture, we split the |
| 534 // variable into two machine-size pieces. LoVar is the low-order | 534 // variable into two machine-size pieces. LoVar is the low-order |
| 535 // machine-size portion, and HiVar is the remaining high-order | 535 // machine-size portion, and HiVar is the remaining high-order |
| 536 // portion. TODO: It's wasteful to penalize all variables on all | 536 // portion. TODO: It's wasteful to penalize all variables on all |
| 537 // targets this way; use a sparser representation. It's also | 537 // targets this way; use a sparser representation. It's also |
| 538 // wasteful for a 64-bit target. | 538 // wasteful for a 64-bit target. |
| 539 Variable *LoVar = nullptr; | 539 Variable *LoVar = nullptr; |
| 540 Variable *HiVar = nullptr; | 540 Variable *HiVar = nullptr; |
| 541 // VarsReal (and Operand::Vars) are set up such that Vars[0] == | 541 /// VarsReal (and Operand::Vars) are set up such that Vars[0] == |
| 542 // this. | 542 /// this. |
| 543 Variable *VarsReal[1]; | 543 Variable *VarsReal[1]; |
| 544 }; | 544 }; |
| 545 | 545 |
| 546 enum MetadataKind { | 546 enum MetadataKind { |
| 547 VMK_Uses, // Track only uses, not defs | 547 VMK_Uses, /// Track only uses, not defs |
| 548 VMK_SingleDefs, // Track uses+defs, but only record single def | 548 VMK_SingleDefs, /// Track uses+defs, but only record single def |
| 549 VMK_All // Track uses+defs, including full def list | 549 VMK_All /// Track uses+defs, including full def list |
| 550 }; | 550 }; |
| 551 typedef std::vector<const Inst *, CfgLocalAllocator<const Inst *>> InstDefList; | 551 typedef std::vector<const Inst *, CfgLocalAllocator<const Inst *>> InstDefList; |
| 552 | 552 |
| 553 // VariableTracking tracks the metadata for a single variable. It is | 553 /// VariableTracking tracks the metadata for a single variable. It is |
| 554 // only meant to be used internally by VariablesMetadata. | 554 /// only meant to be used internally by VariablesMetadata. |
| 555 class VariableTracking { | 555 class VariableTracking { |
| 556 VariableTracking &operator=(const VariableTracking &) = delete; | 556 VariableTracking &operator=(const VariableTracking &) = delete; |
| 557 | 557 |
| 558 public: | 558 public: |
| 559 enum MultiDefState { | 559 enum MultiDefState { |
| 560 // TODO(stichnot): Consider using just a simple counter. | 560 // TODO(stichnot): Consider using just a simple counter. |
| 561 MDS_Unknown, | 561 MDS_Unknown, |
| 562 MDS_SingleDef, | 562 MDS_SingleDef, |
| 563 MDS_MultiDefSingleBlock, | 563 MDS_MultiDefSingleBlock, |
| 564 MDS_MultiDefMultiBlock | 564 MDS_MultiDefMultiBlock |
| (...skipping 10 matching lines...) Expand all Loading... | |
| 575 void markUse(MetadataKind TrackingKind, const Inst *Instr, | 575 void markUse(MetadataKind TrackingKind, const Inst *Instr, |
| 576 const CfgNode *Node, bool IsFromDef, bool IsImplicit); | 576 const CfgNode *Node, bool IsFromDef, bool IsImplicit); |
| 577 void markDef(MetadataKind TrackingKind, const Inst *Instr, | 577 void markDef(MetadataKind TrackingKind, const Inst *Instr, |
| 578 const CfgNode *Node); | 578 const CfgNode *Node); |
| 579 | 579 |
| 580 private: | 580 private: |
| 581 MultiDefState MultiDef = MDS_Unknown; | 581 MultiDefState MultiDef = MDS_Unknown; |
| 582 MultiBlockState MultiBlock = MBS_Unknown; | 582 MultiBlockState MultiBlock = MBS_Unknown; |
| 583 const CfgNode *SingleUseNode = nullptr; | 583 const CfgNode *SingleUseNode = nullptr; |
| 584 const CfgNode *SingleDefNode = nullptr; | 584 const CfgNode *SingleDefNode = nullptr; |
| 585 // All definitions of the variable are collected here, in increasing | 585 /// All definitions of the variable are collected here, in increasing |
| 586 // order of instruction number. | 586 /// order of instruction number. |
| 587 InstDefList Definitions; // Only used if Kind==VMK_All | 587 InstDefList Definitions; /// Only used if Kind==VMK_All |
| 588 const Inst *FirstOrSingleDefinition = | 588 const Inst *FirstOrSingleDefinition = |
| 589 nullptr; // Is a copy of Definitions[0] if Kind==VMK_All | 589 nullptr; /// Is a copy of Definitions[0] if Kind==VMK_All |
| 590 }; | 590 }; |
| 591 | 591 |
| 592 // VariablesMetadata analyzes and summarizes the metadata for the | 592 /// VariablesMetadata analyzes and summarizes the metadata for the |
| 593 // complete set of Variables. | 593 /// complete set of Variables. |
| 594 class VariablesMetadata { | 594 class VariablesMetadata { |
| 595 VariablesMetadata() = delete; | 595 VariablesMetadata() = delete; |
| 596 VariablesMetadata(const VariablesMetadata &) = delete; | 596 VariablesMetadata(const VariablesMetadata &) = delete; |
| 597 VariablesMetadata &operator=(const VariablesMetadata &) = delete; | 597 VariablesMetadata &operator=(const VariablesMetadata &) = delete; |
| 598 | 598 |
| 599 public: | 599 public: |
| 600 explicit VariablesMetadata(const Cfg *Func) : Func(Func) {} | 600 explicit VariablesMetadata(const Cfg *Func) : Func(Func) {} |
| 601 // Initialize the state by traversing all instructions/variables in | 601 /// Initialize the state by traversing all instructions/variables in |
| 602 // the CFG. | 602 /// the CFG. |
| 603 void init(MetadataKind TrackingKind); | 603 void init(MetadataKind TrackingKind); |
| 604 // Add a single node. This is called by init(), and can be called | 604 /// Add a single node. This is called by init(), and can be called |
| 605 // incrementally from elsewhere, e.g. after edge-splitting. | 605 /// incrementally from elsewhere, e.g. after edge-splitting. |
| 606 void addNode(CfgNode *Node); | 606 void addNode(CfgNode *Node); |
| 607 // Returns whether the given Variable is tracked in this object. It | 607 /// Returns whether the given Variable is tracked in this object. It |
| 608 // should only return false if changes were made to the CFG after | 608 /// should only return false if changes were made to the CFG after |
| 609 // running init(), in which case the state is stale and the results | 609 /// running init(), in which case the state is stale and the results |
| 610 // shouldn't be trusted (but it may be OK e.g. for dumping). | 610 /// shouldn't be trusted (but it may be OK e.g. for dumping). |
| 611 bool isTracked(const Variable *Var) const { | 611 bool isTracked(const Variable *Var) const { |
| 612 return Var->getIndex() < Metadata.size(); | 612 return Var->getIndex() < Metadata.size(); |
| 613 } | 613 } |
| 614 | 614 |
| 615 // Returns whether the given Variable has multiple definitions. | 615 /// Returns whether the given Variable has multiple definitions. |
| 616 bool isMultiDef(const Variable *Var) const; | 616 bool isMultiDef(const Variable *Var) const; |
| 617 // Returns the first definition instruction of the given Variable. | 617 /// Returns the first definition instruction of the given Variable. |
| 618 // This is only valid for variables whose definitions are all within | 618 /// This is only valid for variables whose definitions are all within |
| 619 // the same block, e.g. T after the lowered sequence "T=B; T+=C; | 619 /// the same block, e.g. T after the lowered sequence "T=B; T+=C; |
| 620 // A=T", for which getFirstDefinition(T) would return the "T=B" | 620 /// A=T", for which getFirstDefinition(T) would return the "T=B" |
| 621 // instruction. For variables with definitions span multiple | 621 /// instruction. For variables with definitions span multiple |
| 622 // blocks, nullptr is returned. | 622 /// blocks, nullptr is returned. |
| 623 const Inst *getFirstDefinition(const Variable *Var) const; | 623 const Inst *getFirstDefinition(const Variable *Var) const; |
| 624 // Returns the definition instruction of the given Variable, when | 624 /// Returns the definition instruction of the given Variable, when |
| 625 // the variable has exactly one definition. Otherwise, nullptr is | 625 /// the variable has exactly one definition. Otherwise, nullptr is |
| 626 // returned. | 626 /// returned. |
| 627 const Inst *getSingleDefinition(const Variable *Var) const; | 627 const Inst *getSingleDefinition(const Variable *Var) const; |
| 628 // Returns the list of all definition instructions of the given | 628 /// Returns the list of all definition instructions of the given |
| 629 // Variable. | 629 /// Variable. |
| 630 const InstDefList &getLatterDefinitions(const Variable *Var) const; | 630 const InstDefList &getLatterDefinitions(const Variable *Var) const; |
| 631 | 631 |
| 632 // Returns whether the given Variable is live across multiple | 632 /// Returns whether the given Variable is live across multiple |
| 633 // blocks. Mainly, this is used to partition Variables into | 633 /// blocks. Mainly, this is used to partition Variables into |
| 634 // single-block versus multi-block sets for leveraging sparsity in | 634 /// single-block versus multi-block sets for leveraging sparsity in |
| 635 // liveness analysis, and for implementing simple stack slot | 635 /// liveness analysis, and for implementing simple stack slot |
| 636 // coalescing. As a special case, function arguments are always | 636 /// coalescing. As a special case, function arguments are always |
| 637 // considered multi-block because they are live coming into the | 637 /// considered multi-block because they are live coming into the |
| 638 // entry block. | 638 /// entry block. |
| 639 bool isMultiBlock(const Variable *Var) const; | 639 bool isMultiBlock(const Variable *Var) const; |
| 640 // Returns the node that the given Variable is used in, assuming | 640 /// Returns the node that the given Variable is used in, assuming |
| 641 // isMultiBlock() returns false. Otherwise, nullptr is returned. | 641 /// isMultiBlock() returns false. Otherwise, nullptr is returned. |
| 642 const CfgNode *getLocalUseNode(const Variable *Var) const; | 642 const CfgNode *getLocalUseNode(const Variable *Var) const; |
| 643 | 643 |
| 644 private: | 644 private: |
| 645 const Cfg *Func; | 645 const Cfg *Func; |
| 646 MetadataKind Kind; | 646 MetadataKind Kind; |
| 647 std::vector<VariableTracking> Metadata; | 647 std::vector<VariableTracking> Metadata; |
| 648 const static InstDefList NoDefinitions; | 648 const static InstDefList NoDefinitions; |
| 649 }; | 649 }; |
| 650 | 650 |
| 651 } // end of namespace Ice | 651 } // end of namespace Ice |
| 652 | 652 |
| 653 #endif // SUBZERO_SRC_ICEOPERAND_H | 653 #endif // SUBZERO_SRC_ICEOPERAND_H |
| OLD | NEW |