OLD | NEW |
1 //===- subzero/src/IceInst.cpp - High-level instruction implementation ----===// | 1 //===- subzero/src/IceInst.cpp - High-level instruction implementation ----===// |
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 implements the Inst class, primarily the various | 10 // This file implements the Inst class, primarily the various |
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
64 { str } \ | 64 { str } \ |
65 , | 65 , |
66 ICEINSTICMP_TABLE | 66 ICEINSTICMP_TABLE |
67 #undef X | 67 #undef X |
68 }; | 68 }; |
69 | 69 |
70 } // end of anonymous namespace | 70 } // end of anonymous namespace |
71 | 71 |
72 Inst::Inst(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest) | 72 Inst::Inst(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest) |
73 : Kind(Kind), Number(Func->newInstNumber()), Deleted(false), Dead(false), | 73 : Kind(Kind), Number(Func->newInstNumber()), Deleted(false), Dead(false), |
74 HasSideEffects(false), Dest(Dest), MaxSrcs(MaxSrcs), NumSrcs(0), | 74 HasSideEffects(false), IsDestNonKillable(false), Dest(Dest), |
| 75 MaxSrcs(MaxSrcs), NumSrcs(0), |
75 Srcs(Func->allocateArrayOf<Operand *>(MaxSrcs)), LiveRangesEnded(0) {} | 76 Srcs(Func->allocateArrayOf<Operand *>(MaxSrcs)), LiveRangesEnded(0) {} |
76 | 77 |
77 // Assign the instruction a new number. | 78 // Assign the instruction a new number. |
78 void Inst::renumber(Cfg *Func) { | 79 void Inst::renumber(Cfg *Func) { |
79 Number = isDeleted() ? NumberDeleted : Func->newInstNumber(); | 80 Number = isDeleted() ? NumberDeleted : Func->newInstNumber(); |
80 } | 81 } |
81 | 82 |
82 // Delete the instruction if its tentative Dead flag is still set | 83 // Delete the instruction if its tentative Dead flag is still set |
83 // after liveness analysis. | 84 // after liveness analysis. |
84 void Inst::deleteIfDead() { | 85 void Inst::deleteIfDead() { |
(...skipping 19 matching lines...) Expand all Loading... |
104 } | 105 } |
105 Mask >>= 1; | 106 Mask >>= 1; |
106 if (Mask == 0) | 107 if (Mask == 0) |
107 return false; // another early-exit optimization | 108 return false; // another early-exit optimization |
108 } | 109 } |
109 } | 110 } |
110 } | 111 } |
111 return false; | 112 return false; |
112 } | 113 } |
113 | 114 |
114 void Inst::livenessLightweight(Cfg *Func, llvm::BitVector &Live) { | 115 void Inst::livenessLightweight(Cfg *Func, LivenessBV &Live) { |
115 assert(!isDeleted()); | 116 assert(!isDeleted()); |
116 if (llvm::isa<InstFakeKill>(this)) | 117 if (llvm::isa<InstFakeKill>(this)) |
117 return; | 118 return; |
118 resetLastUses(); | 119 resetLastUses(); |
| 120 VariablesMetadata *VMetadata = Func->getVMetadata(); |
119 SizeT VarIndex = 0; | 121 SizeT VarIndex = 0; |
120 for (SizeT I = 0; I < getSrcSize(); ++I) { | 122 for (SizeT I = 0; I < getSrcSize(); ++I) { |
121 Operand *Src = getSrc(I); | 123 Operand *Src = getSrc(I); |
122 SizeT NumVars = Src->getNumVars(); | 124 SizeT NumVars = Src->getNumVars(); |
123 for (SizeT J = 0; J < NumVars; ++J, ++VarIndex) { | 125 for (SizeT J = 0; J < NumVars; ++J, ++VarIndex) { |
124 const Variable *Var = Src->getVar(J); | 126 const Variable *Var = Src->getVar(J); |
125 if (Func->getVMetadata()->isMultiBlock(Var)) | 127 if (VMetadata->isMultiBlock(Var)) |
126 continue; | 128 continue; |
127 SizeT Index = Var->getIndex(); | 129 SizeT Index = Var->getIndex(); |
128 if (Live[Index]) | 130 if (Live[Index]) |
129 continue; | 131 continue; |
130 Live[Index] = true; | 132 Live[Index] = true; |
131 setLastUse(VarIndex); | 133 setLastUse(VarIndex); |
132 } | 134 } |
133 } | 135 } |
134 } | 136 } |
135 | 137 |
136 void Inst::liveness(InstNumberT InstNumber, llvm::BitVector &Live, | 138 void Inst::liveness(InstNumberT InstNumber, LivenessBV &Live, |
137 Liveness *Liveness, const CfgNode *Node) { | 139 Liveness *Liveness, LiveBeginEndMap *LiveBegin, |
| 140 LiveBeginEndMap *LiveEnd) { |
138 assert(!isDeleted()); | 141 assert(!isDeleted()); |
139 if (llvm::isa<InstFakeKill>(this)) | 142 if (llvm::isa<InstFakeKill>(this)) |
140 return; | 143 return; |
141 | 144 |
142 std::vector<InstNumberT> &LiveBegin = Liveness->getLiveBegin(Node); | |
143 std::vector<InstNumberT> &LiveEnd = Liveness->getLiveEnd(Node); | |
144 Dead = false; | 145 Dead = false; |
145 if (Dest) { | 146 if (Dest) { |
146 SizeT VarNum = Liveness->getLiveIndex(Dest); | 147 SizeT VarNum = Liveness->getLiveIndex(Dest->getIndex()); |
147 if (Live[VarNum]) { | 148 if (Live[VarNum]) { |
148 Live[VarNum] = false; | 149 if (!isDestNonKillable()) { |
149 LiveBegin[VarNum] = InstNumber; | 150 Live[VarNum] = false; |
| 151 if (LiveBegin) { |
| 152 LiveBegin->push_back(std::make_pair(VarNum, InstNumber)); |
| 153 } |
| 154 } |
150 } else { | 155 } else { |
151 if (!hasSideEffects()) | 156 if (!hasSideEffects()) |
152 Dead = true; | 157 Dead = true; |
153 } | 158 } |
154 } | 159 } |
155 if (Dead) | 160 if (Dead) |
156 return; | 161 return; |
157 // Phi arguments only get added to Live in the predecessor node, but | 162 // Phi arguments only get added to Live in the predecessor node, but |
158 // we still need to update LiveRangesEnded. | 163 // we still need to update LiveRangesEnded. |
159 bool IsPhi = llvm::isa<InstPhi>(this); | 164 bool IsPhi = llvm::isa<InstPhi>(this); |
160 resetLastUses(); | 165 resetLastUses(); |
161 SizeT VarIndex = 0; | 166 SizeT VarIndex = 0; |
162 for (SizeT I = 0; I < getSrcSize(); ++I) { | 167 for (SizeT I = 0; I < getSrcSize(); ++I) { |
163 Operand *Src = getSrc(I); | 168 Operand *Src = getSrc(I); |
164 SizeT NumVars = Src->getNumVars(); | 169 SizeT NumVars = Src->getNumVars(); |
165 for (SizeT J = 0; J < NumVars; ++J, ++VarIndex) { | 170 for (SizeT J = 0; J < NumVars; ++J, ++VarIndex) { |
166 const Variable *Var = Src->getVar(J); | 171 const Variable *Var = Src->getVar(J); |
167 SizeT VarNum = Liveness->getLiveIndex(Var); | 172 SizeT VarNum = Liveness->getLiveIndex(Var->getIndex()); |
168 if (!Live[VarNum]) { | 173 if (!Live[VarNum]) { |
169 setLastUse(VarIndex); | 174 setLastUse(VarIndex); |
170 if (!IsPhi) { | 175 if (!IsPhi) { |
171 Live[VarNum] = true; | 176 Live[VarNum] = true; |
172 // For a variable in SSA form, its live range can end at | 177 // For a variable in SSA form, its live range can end at |
173 // most once in a basic block. However, after lowering to | 178 // most once in a basic block. However, after lowering to |
174 // two-address instructions, we end up with sequences like | 179 // two-address instructions, we end up with sequences like |
175 // "t=b;t+=c;a=t" where t's live range begins and ends | 180 // "t=b;t+=c;a=t" where t's live range begins and ends |
176 // twice. ICE only allows a variable to have a single | 181 // twice. ICE only allows a variable to have a single |
177 // liveness interval in a basic block (except for blocks | 182 // liveness interval in a basic block (except for blocks |
178 // where a variable is live-in and live-out but there is a | 183 // where a variable is live-in and live-out but there is a |
179 // gap in the middle, and except for the special | 184 // gap in the middle, and except for the special |
180 // InstFakeKill instruction that can appear multiple | 185 // InstFakeKill instruction that can appear multiple |
181 // times in the same block). Therefore, this lowered | 186 // times in the same block). Therefore, this lowered |
182 // sequence needs to represent a single conservative live | 187 // sequence needs to represent a single conservative live |
183 // range for t. Since the instructions are being traversed | 188 // range for t. Since the instructions are being traversed |
184 // backwards, we make sure LiveEnd is only set once by | 189 // backwards, we make sure LiveEnd is only set once by |
185 // setting it only when LiveEnd[VarNum]==0 (sentinel value). | 190 // setting it only when LiveEnd[VarNum]==0 (sentinel value). |
186 // Note that it's OK to set LiveBegin multiple times because | 191 // Note that it's OK to set LiveBegin multiple times because |
187 // of the backwards traversal. | 192 // of the backwards traversal. |
188 if (LiveEnd[VarNum] == 0) { | 193 if (LiveEnd) { |
189 LiveEnd[VarNum] = InstNumber; | 194 // Ideally, we would verify that VarNum wasn't already |
| 195 // added in this block, but this can't be done very |
| 196 // efficiently with LiveEnd as a vector. Instead, |
| 197 // livenessPostprocess() verifies this after the vector |
| 198 // has been sorted. |
| 199 LiveEnd->push_back(std::make_pair(VarNum, InstNumber)); |
190 } | 200 } |
191 } | 201 } |
192 } | 202 } |
193 } | 203 } |
194 } | 204 } |
195 } | 205 } |
196 | 206 |
197 InstAlloca::InstAlloca(Cfg *Func, Operand *ByteCount, uint32_t AlignInBytes, | 207 InstAlloca::InstAlloca(Cfg *Func, Operand *ByteCount, uint32_t AlignInBytes, |
198 Variable *Dest) | 208 Variable *Dest) |
199 : InstHighLevel(Func, Inst::Alloca, 1, Dest), AlignInBytes(AlignInBytes) { | 209 : InstHighLevel(Func, Inst::Alloca, 1, Dest), AlignInBytes(AlignInBytes) { |
(...skipping 113 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
313 if (Labels[I] == Target) | 323 if (Labels[I] == Target) |
314 return getSrc(I); | 324 return getSrc(I); |
315 } | 325 } |
316 llvm_unreachable("Phi target not found"); | 326 llvm_unreachable("Phi target not found"); |
317 return NULL; | 327 return NULL; |
318 } | 328 } |
319 | 329 |
320 // Updates liveness for a particular operand based on the given | 330 // Updates liveness for a particular operand based on the given |
321 // predecessor edge. Doesn't mark the operand as live if the Phi | 331 // predecessor edge. Doesn't mark the operand as live if the Phi |
322 // instruction is dead or deleted. | 332 // instruction is dead or deleted. |
323 void InstPhi::livenessPhiOperand(llvm::BitVector &Live, CfgNode *Target, | 333 void InstPhi::livenessPhiOperand(LivenessBV &Live, CfgNode *Target, |
324 Liveness *Liveness) { | 334 Liveness *Liveness) { |
325 if (isDeleted() || Dead) | 335 if (isDeleted() || Dead) |
326 return; | 336 return; |
327 for (SizeT I = 0; I < getSrcSize(); ++I) { | 337 for (SizeT I = 0; I < getSrcSize(); ++I) { |
328 if (Labels[I] == Target) { | 338 if (Labels[I] == Target) { |
329 if (Variable *Var = llvm::dyn_cast<Variable>(getSrc(I))) { | 339 if (Variable *Var = llvm::dyn_cast<Variable>(getSrc(I))) { |
330 SizeT SrcIndex = Liveness->getLiveIndex(Var); | 340 SizeT SrcIndex = Liveness->getLiveIndex(Var->getIndex()); |
331 if (!Live[SrcIndex]) { | 341 if (!Live[SrcIndex]) { |
332 setLastUse(I); | 342 setLastUse(I); |
333 Live[SrcIndex] = true; | 343 Live[SrcIndex] = true; |
334 } | 344 } |
335 } | 345 } |
336 return; | 346 return; |
337 } | 347 } |
338 } | 348 } |
339 llvm_unreachable("Phi operand not found for specified target node"); | 349 llvm_unreachable("Phi operand not found for specified target node"); |
340 } | 350 } |
(...skipping 400 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
741 dumpSources(Func); | 751 dumpSources(Func); |
742 } | 752 } |
743 | 753 |
744 void InstTarget::dump(const Cfg *Func) const { | 754 void InstTarget::dump(const Cfg *Func) const { |
745 Ostream &Str = Func->getContext()->getStrDump(); | 755 Ostream &Str = Func->getContext()->getStrDump(); |
746 Str << "[TARGET] "; | 756 Str << "[TARGET] "; |
747 Inst::dump(Func); | 757 Inst::dump(Func); |
748 } | 758 } |
749 | 759 |
750 } // end of namespace Ice | 760 } // end of namespace Ice |
OLD | NEW |