| 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 61 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 72 if (!ALLOW_DUMP) | 72 if (!ALLOW_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 (ALLOW_DUMP) | 78 if (ALLOW_DUMP) |
| 79 dump(nullptr, Str); | 79 dump(nullptr, Str); |
| 80 } | 80 } |
| 81 | 81 |
| 82 virtual ~Operand() {} | 82 virtual ~Operand() = default; |
| 83 | 83 |
| 84 protected: | 84 protected: |
| 85 Operand(OperandKind Kind, Type Ty) | 85 Operand(OperandKind Kind, Type Ty) : Ty(Ty), Kind(Kind) {} |
| 86 : Ty(Ty), Kind(Kind), NumVars(0), Vars(nullptr) {} | |
| 87 | 86 |
| 88 const Type Ty; | 87 const Type Ty; |
| 89 const OperandKind Kind; | 88 const OperandKind Kind; |
| 90 // Vars and NumVars are initialized by the derived class. | 89 // Vars and NumVars are initialized by the derived class. |
| 91 SizeT NumVars; | 90 SizeT NumVars = 0; |
| 92 Variable **Vars; | 91 Variable **Vars = nullptr; |
| 93 }; | 92 }; |
| 94 | 93 |
| 95 template <class StreamType> | 94 template <class StreamType> |
| 96 inline StreamType &operator<<(StreamType &Str, const Operand &Op) { | 95 inline StreamType &operator<<(StreamType &Str, const Operand &Op) { |
| 97 Op.dump(Str); | 96 Op.dump(Str); |
| 98 return Str; | 97 return Str; |
| 99 } | 98 } |
| 100 | 99 |
| 101 // Constant is the abstract base class for constants. All | 100 // Constant is the abstract base class for constants. All |
| 102 // constants are allocated from a global arena and are pooled. | 101 // constants are allocated from a global arena and are pooled. |
| (...skipping 207 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 310 ConstantUndef(Type Ty, uint32_t PoolEntryID) | 309 ConstantUndef(Type Ty, uint32_t PoolEntryID) |
| 311 : Constant(kConstUndef, Ty, PoolEntryID) {} | 310 : Constant(kConstUndef, Ty, PoolEntryID) {} |
| 312 ~ConstantUndef() override {} | 311 ~ConstantUndef() override {} |
| 313 }; | 312 }; |
| 314 | 313 |
| 315 // RegWeight is a wrapper for a uint32_t weight value, with a | 314 // RegWeight is a wrapper for a uint32_t weight value, with a |
| 316 // special value that represents infinite weight, and an addWeight() | 315 // special value that represents infinite weight, and an addWeight() |
| 317 // method that ensures that W+infinity=infinity. | 316 // method that ensures that W+infinity=infinity. |
| 318 class RegWeight { | 317 class RegWeight { |
| 319 public: | 318 public: |
| 320 RegWeight() : Weight(0) {} | 319 RegWeight() = default; |
| 321 explicit RegWeight(uint32_t Weight) : Weight(Weight) {} | 320 explicit RegWeight(uint32_t Weight) : Weight(Weight) {} |
| 322 RegWeight(const RegWeight &) = default; | 321 RegWeight(const RegWeight &) = default; |
| 323 RegWeight &operator=(const RegWeight &) = default; | 322 RegWeight &operator=(const RegWeight &) = default; |
| 324 const static uint32_t Inf = ~0; // Force regalloc to give a register | 323 const static uint32_t Inf = ~0; // Force regalloc to give a register |
| 325 const static uint32_t Zero = 0; // Force regalloc NOT to give a register | 324 const static uint32_t Zero = 0; // Force regalloc NOT to give a register |
| 326 void addWeight(uint32_t Delta) { | 325 void addWeight(uint32_t Delta) { |
| 327 if (Delta == Inf) | 326 if (Delta == Inf) |
| 328 Weight = Inf; | 327 Weight = Inf; |
| 329 else if (Weight != Inf) | 328 else if (Weight != Inf) |
| 330 Weight += Delta; | 329 Weight += Delta; |
| 331 } | 330 } |
| 332 void addWeight(const RegWeight &Other) { addWeight(Other.Weight); } | 331 void addWeight(const RegWeight &Other) { addWeight(Other.Weight); } |
| 333 void setWeight(uint32_t Val) { Weight = Val; } | 332 void setWeight(uint32_t Val) { Weight = Val; } |
| 334 uint32_t getWeight() const { return Weight; } | 333 uint32_t getWeight() const { return Weight; } |
| 335 bool isInf() const { return Weight == Inf; } | 334 bool isInf() const { return Weight == Inf; } |
| 336 bool isZero() const { return Weight == Zero; } | 335 bool isZero() const { return Weight == Zero; } |
| 337 | 336 |
| 338 private: | 337 private: |
| 339 uint32_t Weight; | 338 uint32_t Weight = 0; |
| 340 }; | 339 }; |
| 341 Ostream &operator<<(Ostream &Str, const RegWeight &W); | 340 Ostream &operator<<(Ostream &Str, const RegWeight &W); |
| 342 bool operator<(const RegWeight &A, const RegWeight &B); | 341 bool operator<(const RegWeight &A, const RegWeight &B); |
| 343 bool operator<=(const RegWeight &A, const RegWeight &B); | 342 bool operator<=(const RegWeight &A, const RegWeight &B); |
| 344 bool operator==(const RegWeight &A, const RegWeight &B); | 343 bool operator==(const RegWeight &A, const RegWeight &B); |
| 345 | 344 |
| 346 // LiveRange is a set of instruction number intervals representing | 345 // LiveRange is a set of instruction number intervals representing |
| 347 // a variable's live range. Generally there is one interval per basic | 346 // a variable's live range. Generally there is one interval per basic |
| 348 // block where the variable is live, but adjacent intervals get | 347 // block where the variable is live, but adjacent intervals get |
| 349 // coalesced into a single interval. LiveRange also includes a | 348 // coalesced into a single interval. LiveRange also includes a |
| 350 // weight, in case e.g. we want a live range to have higher weight | 349 // weight, in case e.g. we want a live range to have higher weight |
| 351 // inside a loop. | 350 // inside a loop. |
| 352 class LiveRange { | 351 class LiveRange { |
| 353 public: | 352 public: |
| 354 LiveRange() : Weight(0) {} | 353 LiveRange() = default; |
| 355 // Special constructor for building a kill set. The advantage is | 354 // Special constructor for building a kill set. The advantage is |
| 356 // that we can reserve the right amount of space in advance. | 355 // that we can reserve the right amount of space in advance. |
| 357 explicit LiveRange(const std::vector<InstNumberT> &Kills) : Weight(0) { | 356 explicit LiveRange(const std::vector<InstNumberT> &Kills) { |
| 358 Range.reserve(Kills.size()); | 357 Range.reserve(Kills.size()); |
| 359 for (InstNumberT I : Kills) | 358 for (InstNumberT I : Kills) |
| 360 addSegment(I, I); | 359 addSegment(I, I); |
| 361 } | 360 } |
| 362 LiveRange(const LiveRange &) = default; | 361 LiveRange(const LiveRange &) = default; |
| 363 LiveRange &operator=(const LiveRange &) = default; | 362 LiveRange &operator=(const LiveRange &) = default; |
| 364 | 363 |
| 365 void reset() { | 364 void reset() { |
| 366 Range.clear(); | 365 Range.clear(); |
| 367 Weight.setWeight(0); | 366 Weight.setWeight(0); |
| (...skipping 17 matching lines...) Expand all Loading... |
| 385 void setWeight(const RegWeight &NewWeight) { Weight = NewWeight; } | 384 void setWeight(const RegWeight &NewWeight) { Weight = NewWeight; } |
| 386 void addWeight(uint32_t Delta) { Weight.addWeight(Delta); } | 385 void addWeight(uint32_t Delta) { Weight.addWeight(Delta); } |
| 387 void dump(Ostream &Str) const; | 386 void dump(Ostream &Str) const; |
| 388 | 387 |
| 389 private: | 388 private: |
| 390 typedef std::pair<InstNumberT, InstNumberT> RangeElementType; | 389 typedef std::pair<InstNumberT, InstNumberT> RangeElementType; |
| 391 // RangeType is arena-allocated from the Cfg's allocator. | 390 // RangeType is arena-allocated from the Cfg's allocator. |
| 392 typedef std::vector<RangeElementType, CfgLocalAllocator<RangeElementType>> | 391 typedef std::vector<RangeElementType, CfgLocalAllocator<RangeElementType>> |
| 393 RangeType; | 392 RangeType; |
| 394 RangeType Range; | 393 RangeType Range; |
| 395 RegWeight Weight; | 394 RegWeight Weight = RegWeight(0); |
| 396 // TrimmedBegin is an optimization for the overlaps() computation. | 395 // TrimmedBegin is an optimization for the overlaps() computation. |
| 397 // Since the linear-scan algorithm always calls it as overlaps(Cur) | 396 // Since the linear-scan algorithm always calls it as overlaps(Cur) |
| 398 // and Cur advances monotonically according to live range start, we | 397 // and Cur advances monotonically according to live range start, we |
| 399 // can optimize overlaps() by ignoring all segments that end before | 398 // can optimize overlaps() by ignoring all segments that end before |
| 400 // the start of Cur's range. The linear-scan code enables this by | 399 // the start of Cur's range. The linear-scan code enables this by |
| 401 // calling trim() on the ranges of interest as Cur advances. Note | 400 // calling trim() on the ranges of interest as Cur advances. Note |
| 402 // that linear-scan also has to initialize TrimmedBegin at the | 401 // that linear-scan also has to initialize TrimmedBegin at the |
| 403 // beginning by calling untrim(). | 402 // beginning by calling untrim(). |
| 404 RangeType::const_iterator TrimmedBegin; | 403 RangeType::const_iterator TrimmedBegin; |
| 405 }; | 404 }; |
| (...skipping 97 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 503 using Operand::dump; | 502 using Operand::dump; |
| 504 void dump(const Cfg *Func, Ostream &Str) const override; | 503 void dump(const Cfg *Func, Ostream &Str) const override; |
| 505 | 504 |
| 506 static bool classof(const Operand *Operand) { | 505 static bool classof(const Operand *Operand) { |
| 507 OperandKind Kind = Operand->getKind(); | 506 OperandKind Kind = Operand->getKind(); |
| 508 return Kind >= kVariable && Kind <= kVariable_Num; | 507 return Kind >= kVariable && Kind <= kVariable_Num; |
| 509 } | 508 } |
| 510 | 509 |
| 511 protected: | 510 protected: |
| 512 Variable(OperandKind K, Type Ty, SizeT Index) | 511 Variable(OperandKind K, Type Ty, SizeT Index) |
| 513 : Operand(K, Ty), Number(Index), NameIndex(Cfg::IdentifierIndexInvalid), | 512 : Operand(K, Ty), Number(Index) { |
| 514 IsArgument(false), IsImplicitArgument(false), IgnoreLiveness(false), | |
| 515 StackOffset(0), RegNum(NoRegister), RegNumTmp(NoRegister), Weight(1), | |
| 516 LoVar(nullptr), HiVar(nullptr) { | |
| 517 Vars = VarsReal; | 513 Vars = VarsReal; |
| 518 Vars[0] = this; | 514 Vars[0] = this; |
| 519 NumVars = 1; | 515 NumVars = 1; |
| 520 } | 516 } |
| 521 ~Variable() override {} | 517 ~Variable() override {} |
| 522 // Number is unique across all variables, and is used as a | 518 // Number is unique across all variables, and is used as a |
| 523 // (bit)vector index for liveness analysis. | 519 // (bit)vector index for liveness analysis. |
| 524 const SizeT Number; | 520 const SizeT Number; |
| 525 Cfg::IdentifierIndexType NameIndex; | 521 Cfg::IdentifierIndexType NameIndex = Cfg::IdentifierIndexInvalid; |
| 526 bool IsArgument; | 522 bool IsArgument = false; |
| 527 bool IsImplicitArgument; | 523 bool IsImplicitArgument = false; |
| 528 // IgnoreLiveness means that the variable should be ignored when | 524 // IgnoreLiveness means that the variable should be ignored when |
| 529 // constructing and validating live ranges. This is usually | 525 // constructing and validating live ranges. This is usually |
| 530 // reserved for the stack pointer. | 526 // reserved for the stack pointer. |
| 531 bool IgnoreLiveness; | 527 bool IgnoreLiveness = false; |
| 532 // StackOffset is the canonical location on stack (only if | 528 // StackOffset is the canonical location on stack (only if |
| 533 // RegNum==NoRegister || IsArgument). | 529 // RegNum==NoRegister || IsArgument). |
| 534 int32_t StackOffset; | 530 int32_t StackOffset = 0; |
| 535 // RegNum is the allocated register, or NoRegister if it isn't | 531 // RegNum is the allocated register, or NoRegister if it isn't |
| 536 // register-allocated. | 532 // register-allocated. |
| 537 int32_t RegNum; | 533 int32_t RegNum = NoRegister; |
| 538 // RegNumTmp is the tentative assignment during register allocation. | 534 // RegNumTmp is the tentative assignment during register allocation. |
| 539 int32_t RegNumTmp; | 535 int32_t RegNumTmp = NoRegister; |
| 540 RegWeight Weight; // Register allocation priority | 536 RegWeight Weight = RegWeight(1); // Register allocation priority |
| 541 LiveRange Live; | 537 LiveRange Live; |
| 542 // LoVar and HiVar are needed for lowering from 64 to 32 bits. When | 538 // LoVar and HiVar are needed for lowering from 64 to 32 bits. When |
| 543 // lowering from I64 to I32 on a 32-bit architecture, we split the | 539 // lowering from I64 to I32 on a 32-bit architecture, we split the |
| 544 // variable into two machine-size pieces. LoVar is the low-order | 540 // variable into two machine-size pieces. LoVar is the low-order |
| 545 // machine-size portion, and HiVar is the remaining high-order | 541 // machine-size portion, and HiVar is the remaining high-order |
| 546 // portion. TODO: It's wasteful to penalize all variables on all | 542 // portion. TODO: It's wasteful to penalize all variables on all |
| 547 // targets this way; use a sparser representation. It's also | 543 // targets this way; use a sparser representation. It's also |
| 548 // wasteful for a 64-bit target. | 544 // wasteful for a 64-bit target. |
| 549 Variable *LoVar; | 545 Variable *LoVar = nullptr; |
| 550 Variable *HiVar; | 546 Variable *HiVar = nullptr; |
| 551 // VarsReal (and Operand::Vars) are set up such that Vars[0] == | 547 // VarsReal (and Operand::Vars) are set up such that Vars[0] == |
| 552 // this. | 548 // this. |
| 553 Variable *VarsReal[1]; | 549 Variable *VarsReal[1]; |
| 554 }; | 550 }; |
| 555 | 551 |
| 556 enum MetadataKind { | 552 enum MetadataKind { |
| 557 VMK_Uses, // Track only uses, not defs | 553 VMK_Uses, // Track only uses, not defs |
| 558 VMK_SingleDefs, // Track uses+defs, but only record single def | 554 VMK_SingleDefs, // Track uses+defs, but only record single def |
| 559 VMK_All // Track uses+defs, including full def list | 555 VMK_All // Track uses+defs, including full def list |
| 560 }; | 556 }; |
| 561 typedef std::vector<const Inst *, CfgLocalAllocator<const Inst *>> InstDefList; | 557 typedef std::vector<const Inst *, CfgLocalAllocator<const Inst *>> InstDefList; |
| 562 | 558 |
| 563 // VariableTracking tracks the metadata for a single variable. It is | 559 // VariableTracking tracks the metadata for a single variable. It is |
| 564 // only meant to be used internally by VariablesMetadata. | 560 // only meant to be used internally by VariablesMetadata. |
| 565 class VariableTracking { | 561 class VariableTracking { |
| 566 VariableTracking &operator=(const VariableTracking &) = delete; | 562 VariableTracking &operator=(const VariableTracking &) = delete; |
| 567 | 563 |
| 568 public: | 564 public: |
| 569 enum MultiDefState { | 565 enum MultiDefState { |
| 570 // TODO(stichnot): Consider using just a simple counter. | 566 // TODO(stichnot): Consider using just a simple counter. |
| 571 MDS_Unknown, | 567 MDS_Unknown, |
| 572 MDS_SingleDef, | 568 MDS_SingleDef, |
| 573 MDS_MultiDefSingleBlock, | 569 MDS_MultiDefSingleBlock, |
| 574 MDS_MultiDefMultiBlock | 570 MDS_MultiDefMultiBlock |
| 575 }; | 571 }; |
| 576 enum MultiBlockState { MBS_Unknown, MBS_SingleBlock, MBS_MultiBlock }; | 572 enum MultiBlockState { MBS_Unknown, MBS_SingleBlock, MBS_MultiBlock }; |
| 577 VariableTracking() | 573 VariableTracking() = default; |
| 578 : MultiDef(MDS_Unknown), MultiBlock(MBS_Unknown), SingleUseNode(nullptr), | |
| 579 SingleDefNode(nullptr), FirstOrSingleDefinition(nullptr) {} | |
| 580 VariableTracking(const VariableTracking &) = default; | 574 VariableTracking(const VariableTracking &) = default; |
| 581 MultiDefState getMultiDef() const { return MultiDef; } | 575 MultiDefState getMultiDef() const { return MultiDef; } |
| 582 MultiBlockState getMultiBlock() const { return MultiBlock; } | 576 MultiBlockState getMultiBlock() const { return MultiBlock; } |
| 583 const Inst *getFirstDefinition() const; | 577 const Inst *getFirstDefinition() const; |
| 584 const Inst *getSingleDefinition() const; | 578 const Inst *getSingleDefinition() const; |
| 585 const InstDefList &getLatterDefinitions() const { return Definitions; } | 579 const InstDefList &getLatterDefinitions() const { return Definitions; } |
| 586 const CfgNode *getNode() const { return SingleUseNode; } | 580 const CfgNode *getNode() const { return SingleUseNode; } |
| 587 void markUse(MetadataKind TrackingKind, const Inst *Instr, | 581 void markUse(MetadataKind TrackingKind, const Inst *Instr, |
| 588 const CfgNode *Node, bool IsFromDef, bool IsImplicit); | 582 const CfgNode *Node, bool IsFromDef, bool IsImplicit); |
| 589 void markDef(MetadataKind TrackingKind, const Inst *Instr, | 583 void markDef(MetadataKind TrackingKind, const Inst *Instr, |
| 590 const CfgNode *Node); | 584 const CfgNode *Node); |
| 591 | 585 |
| 592 private: | 586 private: |
| 593 MultiDefState MultiDef; | 587 MultiDefState MultiDef = MDS_Unknown; |
| 594 MultiBlockState MultiBlock; | 588 MultiBlockState MultiBlock = MBS_Unknown; |
| 595 const CfgNode *SingleUseNode; | 589 const CfgNode *SingleUseNode = nullptr; |
| 596 const CfgNode *SingleDefNode; | 590 const CfgNode *SingleDefNode = nullptr; |
| 597 // All definitions of the variable are collected here, in increasing | 591 // All definitions of the variable are collected here, in increasing |
| 598 // order of instruction number. | 592 // order of instruction number. |
| 599 InstDefList Definitions; // Only used if Kind==VMK_All | 593 InstDefList Definitions; // Only used if Kind==VMK_All |
| 600 const Inst *FirstOrSingleDefinition; // == Definitions[0] if Kind==VMK_All | 594 const Inst *FirstOrSingleDefinition = |
| 595 nullptr; // Is a copy of Definitions[0] if Kind==VMK_All |
| 601 }; | 596 }; |
| 602 | 597 |
| 603 // VariablesMetadata analyzes and summarizes the metadata for the | 598 // VariablesMetadata analyzes and summarizes the metadata for the |
| 604 // complete set of Variables. | 599 // complete set of Variables. |
| 605 class VariablesMetadata { | 600 class VariablesMetadata { |
| 606 VariablesMetadata() = delete; | 601 VariablesMetadata() = delete; |
| 607 VariablesMetadata(const VariablesMetadata &) = delete; | 602 VariablesMetadata(const VariablesMetadata &) = delete; |
| 608 VariablesMetadata &operator=(const VariablesMetadata &) = delete; | 603 VariablesMetadata &operator=(const VariablesMetadata &) = delete; |
| 609 | 604 |
| 610 public: | 605 public: |
| (...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 655 private: | 650 private: |
| 656 const Cfg *Func; | 651 const Cfg *Func; |
| 657 MetadataKind Kind; | 652 MetadataKind Kind; |
| 658 std::vector<VariableTracking> Metadata; | 653 std::vector<VariableTracking> Metadata; |
| 659 const static InstDefList NoDefinitions; | 654 const static InstDefList NoDefinitions; |
| 660 }; | 655 }; |
| 661 | 656 |
| 662 } // end of namespace Ice | 657 } // end of namespace Ice |
| 663 | 658 |
| 664 #endif // SUBZERO_SRC_ICEOPERAND_H | 659 #endif // SUBZERO_SRC_ICEOPERAND_H |
| OLD | NEW |