| 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 |