OLD | NEW |
1 //===- subzero/src/IceInst.h - High-level instructions ----------*- C++ -*-===// | 1 //===- subzero/src/IceInst.h - High-level instructions ----------*- 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 Inst class and its target-independent | 10 // This file declares the Inst class and its target-independent |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
49 Store, | 49 Store, |
50 Switch, | 50 Switch, |
51 FakeDef, // not part of LLVM/PNaCl bitcode | 51 FakeDef, // not part of LLVM/PNaCl bitcode |
52 FakeUse, // not part of LLVM/PNaCl bitcode | 52 FakeUse, // not part of LLVM/PNaCl bitcode |
53 FakeKill, // not part of LLVM/PNaCl bitcode | 53 FakeKill, // not part of LLVM/PNaCl bitcode |
54 Target // target-specific low-level ICE | 54 Target // target-specific low-level ICE |
55 // Anything >= Target is an InstTarget subclass. | 55 // Anything >= Target is an InstTarget subclass. |
56 }; | 56 }; |
57 InstKind getKind() const { return Kind; } | 57 InstKind getKind() const { return Kind; } |
58 | 58 |
59 int32_t getNumber() const { return Number; } | 59 InstNumberT getNumber() const { return Number; } |
| 60 void renumber(Cfg *Func); |
| 61 static const InstNumberT NumberDeleted = -1; |
| 62 static const InstNumberT NumberSentinel = 0; |
60 | 63 |
61 bool isDeleted() const { return Deleted; } | 64 bool isDeleted() const { return Deleted; } |
62 void setDeleted() { Deleted = true; } | 65 void setDeleted() { Deleted = true; } |
| 66 void deleteIfDead(); |
63 | 67 |
64 bool hasSideEffects() const { return HasSideEffects; } | 68 bool hasSideEffects() const { return HasSideEffects; } |
65 | 69 |
66 Variable *getDest() const { return Dest; } | 70 Variable *getDest() const { return Dest; } |
67 | 71 |
68 SizeT getSrcSize() const { return NumSrcs; } | 72 SizeT getSrcSize() const { return NumSrcs; } |
69 Operand *getSrc(SizeT I) const { | 73 Operand *getSrc(SizeT I) const { |
70 assert(I < getSrcSize()); | 74 assert(I < getSrcSize()); |
71 return Srcs[I]; | 75 return Srcs[I]; |
72 } | 76 } |
73 | 77 |
| 78 bool isLastUse(const Operand *Src) const; |
| 79 |
74 // Returns a list of out-edges corresponding to a terminator | 80 // Returns a list of out-edges corresponding to a terminator |
75 // instruction, which is the last instruction of the block. | 81 // instruction, which is the last instruction of the block. |
76 virtual NodeList getTerminatorEdges() const { | 82 virtual NodeList getTerminatorEdges() const { |
77 // All valid terminator instructions override this method. For | 83 // All valid terminator instructions override this method. For |
78 // the default implementation, we assert in case some CfgNode | 84 // the default implementation, we assert in case some CfgNode |
79 // is constructed without a terminator instruction at the end. | 85 // is constructed without a terminator instruction at the end. |
80 llvm_unreachable( | 86 llvm_unreachable( |
81 "getTerminatorEdges() called on a non-terminator instruction"); | 87 "getTerminatorEdges() called on a non-terminator instruction"); |
82 return NodeList(); | 88 return NodeList(); |
83 } | 89 } |
84 | 90 |
85 // Updates the status of the Variables contained within the | 91 // Updates the status of the Variables contained within the |
86 // instruction. In particular, it marks where the Dest variable is | 92 // instruction. In particular, it marks where the Dest variable is |
87 // first assigned, and it tracks whether variables are live across | 93 // first assigned, and it tracks whether variables are live across |
88 // basic blocks, i.e. used in a different block from their definition. | 94 // basic blocks, i.e. used in a different block from their definition. |
89 void updateVars(CfgNode *Node); | 95 void updateVars(CfgNode *Node); |
90 | 96 |
| 97 void livenessLightweight(llvm::BitVector &Live); |
| 98 void liveness(InstNumberT InstNumber, llvm::BitVector &Live, |
| 99 Liveness *Liveness, const CfgNode *Node); |
91 virtual void emit(const Cfg *Func) const; | 100 virtual void emit(const Cfg *Func) const; |
92 virtual void dump(const Cfg *Func) const; | 101 virtual void dump(const Cfg *Func) const; |
| 102 virtual void dumpExtras(const Cfg *Func) const; |
93 void dumpDecorated(const Cfg *Func) const; | 103 void dumpDecorated(const Cfg *Func) const; |
94 void emitSources(const Cfg *Func) const; | 104 void emitSources(const Cfg *Func) const; |
95 void dumpSources(const Cfg *Func) const; | 105 void dumpSources(const Cfg *Func) const; |
96 void dumpDest(const Cfg *Func) const; | 106 void dumpDest(const Cfg *Func) const; |
97 virtual bool isRedundantAssign() const { return false; } | 107 virtual bool isRedundantAssign() const { return false; } |
98 | 108 |
99 virtual ~Inst() {} | 109 virtual ~Inst() {} |
100 | 110 |
101 protected: | 111 protected: |
102 Inst(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest); | 112 Inst(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest); |
103 void addSource(Operand *Src) { | 113 void addSource(Operand *Src) { |
104 assert(Src); | 114 assert(Src); |
105 assert(NumSrcs < MaxSrcs); | 115 assert(NumSrcs < MaxSrcs); |
106 Srcs[NumSrcs++] = Src; | 116 Srcs[NumSrcs++] = Src; |
107 } | 117 } |
| 118 void setLastUse(SizeT VarIndex) { |
| 119 if (VarIndex < CHAR_BIT * sizeof(LiveRangesEnded)) |
| 120 LiveRangesEnded |= (((LREndedBits)1u) << VarIndex); |
| 121 } |
| 122 void resetLastUses() { LiveRangesEnded = 0; } |
108 // The destroy() method lets the instruction cleanly release any | 123 // The destroy() method lets the instruction cleanly release any |
109 // memory that was allocated via the Cfg's allocator. | 124 // memory that was allocated via the Cfg's allocator. |
110 virtual void destroy(Cfg *Func) { Func->deallocateArrayOf<Operand *>(Srcs); } | 125 virtual void destroy(Cfg *Func) { Func->deallocateArrayOf<Operand *>(Srcs); } |
111 | 126 |
112 const InstKind Kind; | 127 const InstKind Kind; |
113 // Number is the instruction number for describing live ranges. | 128 // Number is the instruction number for describing live ranges. |
114 int32_t Number; | 129 InstNumberT Number; |
115 // Deleted means irrevocably deleted. | 130 // Deleted means irrevocably deleted. |
116 bool Deleted; | 131 bool Deleted; |
| 132 // Dead means pending deletion after liveness analysis converges. |
| 133 bool Dead; |
117 // HasSideEffects means the instruction is something like a function | 134 // HasSideEffects means the instruction is something like a function |
118 // call or a volatile load that can't be removed even if its Dest | 135 // call or a volatile load that can't be removed even if its Dest |
119 // variable is not live. | 136 // variable is not live. |
120 bool HasSideEffects; | 137 bool HasSideEffects; |
121 | 138 |
122 Variable *Dest; | 139 Variable *Dest; |
123 const SizeT MaxSrcs; // only used for assert | 140 const SizeT MaxSrcs; // only used for assert |
124 SizeT NumSrcs; | 141 SizeT NumSrcs; |
125 Operand **Srcs; | 142 Operand **Srcs; |
126 | 143 |
| 144 // LiveRangesEnded marks which Variables' live ranges end in this |
| 145 // instruction. An instruction can have an arbitrary number of |
| 146 // source operands (e.g. a call instruction), and each source |
| 147 // operand can contain 0 or 1 Variable (and target-specific operands |
| 148 // could contain more than 1 Variable). All the variables in an |
| 149 // instruction are conceptually flattened and each variable is |
| 150 // mapped to one bit position of the LiveRangesEnded bit vector. |
| 151 // Only the first CHAR_BIT * sizeof(LREndedBits) variables are |
| 152 // tracked this way. |
| 153 typedef uint32_t LREndedBits; // only first 32 src operands tracked, sorry |
| 154 LREndedBits LiveRangesEnded; |
| 155 |
127 private: | 156 private: |
128 Inst(const Inst &) LLVM_DELETED_FUNCTION; | 157 Inst(const Inst &) LLVM_DELETED_FUNCTION; |
129 Inst &operator=(const Inst &) LLVM_DELETED_FUNCTION; | 158 Inst &operator=(const Inst &) LLVM_DELETED_FUNCTION; |
130 }; | 159 }; |
131 | 160 |
132 // Alloca instruction. This captures the size in bytes as getSrc(0), | 161 // Alloca instruction. This captures the size in bytes as getSrc(0), |
133 // and the required alignment in bytes. The alignment must be either | 162 // and the required alignment in bytes. The alignment must be either |
134 // 0 (no alignment required) or a power of 2. | 163 // 0 (no alignment required) or a power of 2. |
135 class InstAlloca : public Inst { | 164 class InstAlloca : public Inst { |
136 public: | 165 public: |
(...skipping 249 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
386 | 415 |
387 // Phi instruction. For incoming edge I, the node is Labels[I] and | 416 // Phi instruction. For incoming edge I, the node is Labels[I] and |
388 // the Phi source operand is getSrc(I). | 417 // the Phi source operand is getSrc(I). |
389 class InstPhi : public Inst { | 418 class InstPhi : public Inst { |
390 public: | 419 public: |
391 static InstPhi *create(Cfg *Func, SizeT MaxSrcs, Variable *Dest) { | 420 static InstPhi *create(Cfg *Func, SizeT MaxSrcs, Variable *Dest) { |
392 return new (Func->allocateInst<InstPhi>()) InstPhi(Func, MaxSrcs, Dest); | 421 return new (Func->allocateInst<InstPhi>()) InstPhi(Func, MaxSrcs, Dest); |
393 } | 422 } |
394 void addArgument(Operand *Source, CfgNode *Label); | 423 void addArgument(Operand *Source, CfgNode *Label); |
395 Operand *getOperandForTarget(CfgNode *Target) const; | 424 Operand *getOperandForTarget(CfgNode *Target) const; |
| 425 void livenessPhiOperand(llvm::BitVector &Live, CfgNode *Target, |
| 426 Liveness *Liveness); |
396 Inst *lower(Cfg *Func, CfgNode *Node); | 427 Inst *lower(Cfg *Func, CfgNode *Node); |
397 virtual void dump(const Cfg *Func) const; | 428 virtual void dump(const Cfg *Func) const; |
398 static bool classof(const Inst *Inst) { return Inst->getKind() == Phi; } | 429 static bool classof(const Inst *Inst) { return Inst->getKind() == Phi; } |
399 | 430 |
400 private: | 431 private: |
401 InstPhi(Cfg *Func, SizeT MaxSrcs, Variable *Dest); | 432 InstPhi(Cfg *Func, SizeT MaxSrcs, Variable *Dest); |
402 InstPhi(const InstPhi &) LLVM_DELETED_FUNCTION; | 433 InstPhi(const InstPhi &) LLVM_DELETED_FUNCTION; |
403 InstPhi &operator=(const InstPhi &) LLVM_DELETED_FUNCTION; | 434 InstPhi &operator=(const InstPhi &) LLVM_DELETED_FUNCTION; |
404 virtual void destroy(Cfg *Func) { | 435 virtual void destroy(Cfg *Func) { |
405 Func->deallocateArrayOf<CfgNode *>(Labels); | 436 Func->deallocateArrayOf<CfgNode *>(Labels); |
(...skipping 213 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
619 // This instruction is ignored if Linked->isDeleted() is true. | 650 // This instruction is ignored if Linked->isDeleted() is true. |
620 const Inst *Linked; | 651 const Inst *Linked; |
621 }; | 652 }; |
622 | 653 |
623 // The Target instruction is the base class for all target-specific | 654 // The Target instruction is the base class for all target-specific |
624 // instructions. | 655 // instructions. |
625 class InstTarget : public Inst { | 656 class InstTarget : public Inst { |
626 public: | 657 public: |
627 virtual void emit(const Cfg *Func) const = 0; | 658 virtual void emit(const Cfg *Func) const = 0; |
628 virtual void dump(const Cfg *Func) const; | 659 virtual void dump(const Cfg *Func) const; |
| 660 virtual void dumpExtras(const Cfg *Func) const; |
629 static bool classof(const Inst *Inst) { return Inst->getKind() >= Target; } | 661 static bool classof(const Inst *Inst) { return Inst->getKind() >= Target; } |
630 | 662 |
631 protected: | 663 protected: |
632 InstTarget(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest) | 664 InstTarget(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest) |
633 : Inst(Func, Kind, MaxSrcs, Dest) { | 665 : Inst(Func, Kind, MaxSrcs, Dest) { |
634 assert(Kind >= Target); | 666 assert(Kind >= Target); |
635 } | 667 } |
636 InstTarget(const InstTarget &) LLVM_DELETED_FUNCTION; | 668 InstTarget(const InstTarget &) LLVM_DELETED_FUNCTION; |
637 InstTarget &operator=(const InstTarget &) LLVM_DELETED_FUNCTION; | 669 InstTarget &operator=(const InstTarget &) LLVM_DELETED_FUNCTION; |
638 virtual ~InstTarget() {} | 670 virtual ~InstTarget() {} |
639 }; | 671 }; |
640 | 672 |
641 } // end of namespace Ice | 673 } // end of namespace Ice |
642 | 674 |
643 #endif // SUBZERO_SRC_ICEINST_H | 675 #endif // SUBZERO_SRC_ICEINST_H |
OLD | NEW |