OLD | NEW |
1 //===- subzero/src/IceOperand.cpp - High-level operand implementation -----===// | 1 //===- subzero/src/IceOperand.cpp - High-level operand 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 /// \file | 10 /// \file |
(...skipping 30 matching lines...) Expand all Loading... |
41 InstNumberT CurrentEnd = Range.back().second; | 41 InstNumberT CurrentEnd = Range.back().second; |
42 assert(Start >= CurrentEnd); | 42 assert(Start >= CurrentEnd); |
43 if (Start == CurrentEnd) { | 43 if (Start == CurrentEnd) { |
44 Range.back().second = End; | 44 Range.back().second = End; |
45 return; | 45 return; |
46 } | 46 } |
47 } | 47 } |
48 Range.push_back(RangeElementType(Start, End)); | 48 Range.push_back(RangeElementType(Start, End)); |
49 } | 49 } |
50 | 50 |
51 // Returns true if this live range ends before Other's live range | 51 // Returns true if this live range ends before Other's live range starts. This |
52 // starts. This means that the highest instruction number in this | 52 // means that the highest instruction number in this live range is less than or |
53 // live range is less than or equal to the lowest instruction number | 53 // equal to the lowest instruction number of the Other live range. |
54 // of the Other live range. | |
55 bool LiveRange::endsBefore(const LiveRange &Other) const { | 54 bool LiveRange::endsBefore(const LiveRange &Other) const { |
56 // Neither range should be empty, but let's be graceful. | 55 // Neither range should be empty, but let's be graceful. |
57 if (Range.empty() || Other.Range.empty()) | 56 if (Range.empty() || Other.Range.empty()) |
58 return true; | 57 return true; |
59 InstNumberT MyEnd = (*Range.rbegin()).second; | 58 InstNumberT MyEnd = (*Range.rbegin()).second; |
60 InstNumberT OtherStart = (*Other.Range.begin()).first; | 59 InstNumberT OtherStart = (*Other.Range.begin()).first; |
61 return MyEnd <= OtherStart; | 60 return MyEnd <= OtherStart; |
62 } | 61 } |
63 | 62 |
64 // Returns true if there is any overlap between the two live ranges. | 63 // Returns true if there is any overlap between the two live ranges. |
(...skipping 22 matching lines...) Expand all Loading... |
87 I != E; ++I) { | 86 I != E; ++I) { |
88 if (OtherBegin < I->first) { | 87 if (OtherBegin < I->first) { |
89 Result = false; | 88 Result = false; |
90 break; | 89 break; |
91 } | 90 } |
92 if (OtherBegin < I->second) { | 91 if (OtherBegin < I->second) { |
93 Result = true; | 92 Result = true; |
94 break; | 93 break; |
95 } | 94 } |
96 } | 95 } |
97 // This is an equivalent but less inefficient implementation. It's | 96 // This is an equivalent but less inefficient implementation. It's expensive |
98 // expensive enough that we wouldn't want to run it under any build, | 97 // enough that we wouldn't want to run it under any build, but it could be |
99 // but it could be enabled if e.g. the LiveRange implementation | 98 // enabled if e.g. the LiveRange implementation changes and extra testing is |
100 // changes and extra testing is needed. | 99 // needed. |
101 if (BuildDefs::extraValidation()) { | 100 if (BuildDefs::extraValidation()) { |
102 LiveRange Temp; | 101 LiveRange Temp; |
103 Temp.addSegment(OtherBegin, OtherBegin + 1); | 102 Temp.addSegment(OtherBegin, OtherBegin + 1); |
104 bool Validation = overlaps(Temp); | 103 bool Validation = overlaps(Temp); |
105 (void)Validation; | 104 (void)Validation; |
106 assert(Result == Validation); | 105 assert(Result == Validation); |
107 } | 106 } |
108 return Result; | 107 return Result; |
109 } | 108 } |
110 | 109 |
111 // Returns true if the live range contains the given instruction | 110 // Returns true if the live range contains the given instruction number. This |
112 // number. This is only used for validating the live range | 111 // is only used for validating the live range calculation. The IsDest argument |
113 // calculation. The IsDest argument indicates whether the Variable | 112 // indicates whether the Variable being tested is used in the Dest position (as |
114 // being tested is used in the Dest position (as opposed to a Src | 113 // opposed to a Src position). |
115 // position). | |
116 bool LiveRange::containsValue(InstNumberT Value, bool IsDest) const { | 114 bool LiveRange::containsValue(InstNumberT Value, bool IsDest) const { |
117 for (const RangeElementType &I : Range) { | 115 for (const RangeElementType &I : Range) { |
118 if (I.first <= Value && | 116 if (I.first <= Value && |
119 (Value < I.second || (!IsDest && Value == I.second))) | 117 (Value < I.second || (!IsDest && Value == I.second))) |
120 return true; | 118 return true; |
121 } | 119 } |
122 return false; | 120 return false; |
123 } | 121 } |
124 | 122 |
125 void LiveRange::trim(InstNumberT Lower) { | 123 void LiveRange::trim(InstNumberT Lower) { |
126 while (TrimmedBegin != Range.end() && TrimmedBegin->second <= Lower) | 124 while (TrimmedBegin != Range.end() && TrimmedBegin->second <= Lower) |
127 ++TrimmedBegin; | 125 ++TrimmedBegin; |
128 } | 126 } |
129 | 127 |
130 IceString Variable::getName(const Cfg *Func) const { | 128 IceString Variable::getName(const Cfg *Func) const { |
131 if (Func && NameIndex >= 0) | 129 if (Func && NameIndex >= 0) |
132 return Func->getIdentifierName(NameIndex); | 130 return Func->getIdentifierName(NameIndex); |
133 return "__" + std::to_string(getIndex()); | 131 return "__" + std::to_string(getIndex()); |
134 } | 132 } |
135 | 133 |
136 Variable *Variable::asType(Type Ty) { | 134 Variable *Variable::asType(Type Ty) { |
137 // Note: This returns a Variable, even if the "this" object is a | 135 // Note: This returns a Variable, even if the "this" object is a subclass of |
138 // subclass of Variable. | 136 // Variable. |
139 if (!BuildDefs::dump() || getType() == Ty) | 137 if (!BuildDefs::dump() || getType() == Ty) |
140 return this; | 138 return this; |
141 Variable *V = new (getCurrentCfgAllocator()->Allocate<Variable>()) | 139 Variable *V = new (getCurrentCfgAllocator()->Allocate<Variable>()) |
142 Variable(kVariable, Ty, Number); | 140 Variable(kVariable, Ty, Number); |
143 V->NameIndex = NameIndex; | 141 V->NameIndex = NameIndex; |
144 V->RegNum = RegNum; | 142 V->RegNum = RegNum; |
145 V->StackOffset = StackOffset; | 143 V->StackOffset = StackOffset; |
146 return V; | 144 return V; |
147 } | 145 } |
148 | 146 |
(...skipping 15 matching lines...) Expand all Loading... |
164 constexpr SizeT MaxShift = sizeof(uint32_t) * CHAR_BIT - 1; | 162 constexpr SizeT MaxShift = sizeof(uint32_t) * CHAR_BIT - 1; |
165 constexpr SizeT MaxLoopNestDepth = MaxShift / LogLoopTripCountEstimate; | 163 constexpr SizeT MaxLoopNestDepth = MaxShift / LogLoopTripCountEstimate; |
166 const uint32_t LoopNestDepth = | 164 const uint32_t LoopNestDepth = |
167 std::min(Node->getLoopNestDepth(), MaxLoopNestDepth); | 165 std::min(Node->getLoopNestDepth(), MaxLoopNestDepth); |
168 const uint32_t ThisUseWeight = uint32_t(1) | 166 const uint32_t ThisUseWeight = uint32_t(1) |
169 << LoopNestDepth * LogLoopTripCountEstimate; | 167 << LoopNestDepth * LogLoopTripCountEstimate; |
170 UseWeight.addWeight(ThisUseWeight); | 168 UseWeight.addWeight(ThisUseWeight); |
171 | 169 |
172 if (MultiBlock == MBS_MultiBlock) | 170 if (MultiBlock == MBS_MultiBlock) |
173 return; | 171 return; |
174 // TODO(stichnot): If the use occurs as a source operand in the | 172 // TODO(stichnot): If the use occurs as a source operand in the first |
175 // first instruction of the block, and its definition is in this | 173 // instruction of the block, and its definition is in this block's only |
176 // block's only predecessor, we might consider not marking this as a | 174 // predecessor, we might consider not marking this as a separate use. This |
177 // separate use. This may also apply if it's the first instruction | 175 // may also apply if it's the first instruction of the block that actually |
178 // of the block that actually uses a Variable. | 176 // uses a Variable. |
179 assert(Node); | 177 assert(Node); |
180 bool MakeMulti = false; | 178 bool MakeMulti = false; |
181 if (IsImplicit) | 179 if (IsImplicit) |
182 MakeMulti = true; | 180 MakeMulti = true; |
183 // A phi source variable conservatively needs to be marked as | 181 // A phi source variable conservatively needs to be marked as multi-block, |
184 // multi-block, even if its definition is in the same block. This | 182 // even if its definition is in the same block. This is because there can be |
185 // is because there can be additional control flow before branching | 183 // additional control flow before branching back to this node, and the |
186 // back to this node, and the variable is live throughout those | 184 // variable is live throughout those nodes. |
187 // nodes. | |
188 if (Instr && llvm::isa<InstPhi>(Instr)) | 185 if (Instr && llvm::isa<InstPhi>(Instr)) |
189 MakeMulti = true; | 186 MakeMulti = true; |
190 | 187 |
191 if (!MakeMulti) { | 188 if (!MakeMulti) { |
192 switch (MultiBlock) { | 189 switch (MultiBlock) { |
193 case MBS_Unknown: | 190 case MBS_Unknown: |
194 MultiBlock = MBS_SingleBlock; | 191 MultiBlock = MBS_SingleBlock; |
195 SingleUseNode = Node; | 192 SingleUseNode = Node; |
196 break; | 193 break; |
197 case MBS_SingleBlock: | 194 case MBS_SingleBlock: |
198 if (SingleUseNode != Node) | 195 if (SingleUseNode != Node) |
199 MakeMulti = true; | 196 MakeMulti = true; |
200 break; | 197 break; |
201 case MBS_MultiBlock: | 198 case MBS_MultiBlock: |
202 break; | 199 break; |
203 } | 200 } |
204 } | 201 } |
205 | 202 |
206 if (MakeMulti) { | 203 if (MakeMulti) { |
207 MultiBlock = MBS_MultiBlock; | 204 MultiBlock = MBS_MultiBlock; |
208 SingleUseNode = nullptr; | 205 SingleUseNode = nullptr; |
209 } | 206 } |
210 } | 207 } |
211 | 208 |
212 void VariableTracking::markDef(MetadataKind TrackingKind, const Inst *Instr, | 209 void VariableTracking::markDef(MetadataKind TrackingKind, const Inst *Instr, |
213 CfgNode *Node) { | 210 CfgNode *Node) { |
214 // TODO(stichnot): If the definition occurs in the last instruction | 211 // TODO(stichnot): If the definition occurs in the last instruction of the |
215 // of the block, consider not marking this as a separate use. But | 212 // block, consider not marking this as a separate use. But be careful not to |
216 // be careful not to omit all uses of the variable if markDef() and | 213 // omit all uses of the variable if markDef() and markUse() both use this |
217 // markUse() both use this optimization. | 214 // optimization. |
218 assert(Node); | 215 assert(Node); |
219 // Verify that instructions are added in increasing order. | 216 // Verify that instructions are added in increasing order. |
220 #ifndef NDEBUG | 217 #ifndef NDEBUG |
221 if (TrackingKind == VMK_All) { | 218 if (TrackingKind == VMK_All) { |
222 const Inst *LastInstruction = | 219 const Inst *LastInstruction = |
223 Definitions.empty() ? FirstOrSingleDefinition : Definitions.back(); | 220 Definitions.empty() ? FirstOrSingleDefinition : Definitions.back(); |
224 assert(LastInstruction == nullptr || | 221 assert(LastInstruction == nullptr || |
225 Instr->getNumber() >= LastInstruction->getNumber()); | 222 Instr->getNumber() >= LastInstruction->getNumber()); |
226 } | 223 } |
227 #endif | 224 #endif |
(...skipping 282 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
510 return Str; | 507 return Str; |
511 if (W.getWeight() == RegWeight::Inf) | 508 if (W.getWeight() == RegWeight::Inf) |
512 Str << "Inf"; | 509 Str << "Inf"; |
513 else | 510 else |
514 Str << W.getWeight(); | 511 Str << W.getWeight(); |
515 return Str; | 512 return Str; |
516 } | 513 } |
517 | 514 |
518 // =========== Immediate Randomization and Pooling routines ============== | 515 // =========== Immediate Randomization and Pooling routines ============== |
519 // Specialization of the template member function for ConstantInteger32 | 516 // Specialization of the template member function for ConstantInteger32 |
520 // TODO(stichnot): try to move this specialization into a target-specific | 517 // TODO(stichnot): try to move this specialization into a target-specific file. |
521 // file. | |
522 template <> | 518 template <> |
523 bool ConstantInteger32::shouldBeRandomizedOrPooled(const GlobalContext *Ctx) { | 519 bool ConstantInteger32::shouldBeRandomizedOrPooled(const GlobalContext *Ctx) { |
524 uint32_t Threshold = Ctx->getFlags().getRandomizeAndPoolImmediatesThreshold(); | 520 uint32_t Threshold = Ctx->getFlags().getRandomizeAndPoolImmediatesThreshold(); |
525 if (Ctx->getFlags().getRandomizeAndPoolImmediatesOption() == RPI_None) | 521 if (Ctx->getFlags().getRandomizeAndPoolImmediatesOption() == RPI_None) |
526 return false; | 522 return false; |
527 if (getType() != IceType_i32 && getType() != IceType_i16 && | 523 if (getType() != IceType_i32 && getType() != IceType_i16 && |
528 getType() != IceType_i8) | 524 getType() != IceType_i8) |
529 return false; | 525 return false; |
530 // The Following checks if the signed representation of Value is between | 526 // The Following checks if the signed representation of Value is between |
531 // -Threshold/2 and +Threshold/2 | 527 // -Threshold/2 and +Threshold/2 |
532 bool largerThanThreshold = Threshold / 2 + Value >= Threshold; | 528 bool largerThanThreshold = Threshold / 2 + Value >= Threshold; |
533 return largerThanThreshold; | 529 return largerThanThreshold; |
534 } | 530 } |
535 | 531 |
536 } // end of namespace Ice | 532 } // end of namespace Ice |
OLD | NEW |