Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1 | //===- subzero/src/IceOperand.cpp - High-level operand implementation -----===// |
| 2 | // |
| 3 | // The Subzero Code Generator |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 9 | /// |
| 10 | /// \file |
| 11 | /// This file implements the Operand class and its target-independent |
| 12 | /// subclasses, primarily for the methods of the Variable class. |
| 13 | /// |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 14 | //===----------------------------------------------------------------------===// |
| 15 | |
John Porto | 67f8de9 | 2015-06-25 10:14:17 -0700 | [diff] [blame] | 16 | #include "IceOperand.h" |
| 17 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 18 | #include "IceCfg.h" |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 19 | #include "IceCfgNode.h" |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 20 | #include "IceInst.h" |
John Porto | ec3f565 | 2015-08-31 15:07:09 -0700 | [diff] [blame] | 21 | #include "IceInstVarIter.h" |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 22 | #include "IceTargetLowering.h" // dumping stack/frame pointer register |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 23 | |
| 24 | namespace Ice { |
| 25 | |
Jim Stichnoth | d2cb436 | 2014-11-20 11:24:42 -0800 | [diff] [blame] | 26 | bool operator==(const RelocatableTuple &A, const RelocatableTuple &B) { |
| 27 | return A.Offset == B.Offset && A.Name == B.Name; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 28 | } |
| 29 | |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 30 | bool operator<(const RegWeight &A, const RegWeight &B) { |
| 31 | return A.getWeight() < B.getWeight(); |
| 32 | } |
| 33 | bool operator<=(const RegWeight &A, const RegWeight &B) { return !(B < A); } |
| 34 | bool operator==(const RegWeight &A, const RegWeight &B) { |
| 35 | return !(B < A) && !(A < B); |
| 36 | } |
| 37 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 38 | void LiveRange::addSegment(InstNumberT Start, InstNumberT End) { |
Jim Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 39 | if (!Range.empty()) { |
| 40 | // Check for merge opportunity. |
| 41 | InstNumberT CurrentEnd = Range.back().second; |
| 42 | assert(Start >= CurrentEnd); |
| 43 | if (Start == CurrentEnd) { |
| 44 | Range.back().second = End; |
| 45 | return; |
| 46 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 47 | } |
| 48 | Range.push_back(RangeElementType(Start, End)); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 49 | } |
| 50 | |
| 51 | // Returns true if this live range ends before Other's live range |
| 52 | // starts. This means that the highest instruction number in this |
| 53 | // live range is less than or equal to the lowest instruction number |
| 54 | // of the Other live range. |
| 55 | bool LiveRange::endsBefore(const LiveRange &Other) const { |
| 56 | // Neither range should be empty, but let's be graceful. |
| 57 | if (Range.empty() || Other.Range.empty()) |
| 58 | return true; |
| 59 | InstNumberT MyEnd = (*Range.rbegin()).second; |
| 60 | InstNumberT OtherStart = (*Other.Range.begin()).first; |
| 61 | return MyEnd <= OtherStart; |
| 62 | } |
| 63 | |
| 64 | // Returns true if there is any overlap between the two live ranges. |
Jim Stichnoth | 037fa1d | 2014-10-07 11:09:33 -0700 | [diff] [blame] | 65 | bool LiveRange::overlaps(const LiveRange &Other, bool UseTrimmed) const { |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 66 | // Do a two-finger walk through the two sorted lists of segments. |
Jim Stichnoth | 037fa1d | 2014-10-07 11:09:33 -0700 | [diff] [blame] | 67 | auto I1 = (UseTrimmed ? TrimmedBegin : Range.begin()), |
| 68 | I2 = (UseTrimmed ? Other.TrimmedBegin : Other.Range.begin()); |
| 69 | auto E1 = Range.end(), E2 = Other.Range.end(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 70 | while (I1 != E1 && I2 != E2) { |
| 71 | if (I1->second <= I2->first) { |
| 72 | ++I1; |
| 73 | continue; |
| 74 | } |
| 75 | if (I2->second <= I1->first) { |
| 76 | ++I2; |
| 77 | continue; |
| 78 | } |
| 79 | return true; |
| 80 | } |
| 81 | return false; |
| 82 | } |
| 83 | |
Jim Stichnoth | 037fa1d | 2014-10-07 11:09:33 -0700 | [diff] [blame] | 84 | bool LiveRange::overlapsInst(InstNumberT OtherBegin, bool UseTrimmed) const { |
Jim Stichnoth | c4554d7 | 2014-09-30 16:49:38 -0700 | [diff] [blame] | 85 | bool Result = false; |
Jim Stichnoth | 037fa1d | 2014-10-07 11:09:33 -0700 | [diff] [blame] | 86 | for (auto I = (UseTrimmed ? TrimmedBegin : Range.begin()), E = Range.end(); |
| 87 | I != E; ++I) { |
| 88 | if (OtherBegin < I->first) { |
Jim Stichnoth | c4554d7 | 2014-09-30 16:49:38 -0700 | [diff] [blame] | 89 | Result = false; |
| 90 | break; |
| 91 | } |
Jim Stichnoth | 037fa1d | 2014-10-07 11:09:33 -0700 | [diff] [blame] | 92 | if (OtherBegin < I->second) { |
Jim Stichnoth | c4554d7 | 2014-09-30 16:49:38 -0700 | [diff] [blame] | 93 | Result = true; |
| 94 | break; |
| 95 | } |
| 96 | } |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 97 | // This is an equivalent but less inefficient implementation. It's |
| 98 | // expensive enough that we wouldn't want to run it under any build, |
| 99 | // but it could be enabled if e.g. the LiveRange implementation |
| 100 | // changes and extra testing is needed. |
| 101 | if (BuildDefs::extraValidation()) { |
| 102 | LiveRange Temp; |
| 103 | Temp.addSegment(OtherBegin, OtherBegin + 1); |
| 104 | bool Validation = overlaps(Temp); |
| 105 | (void)Validation; |
| 106 | assert(Result == Validation); |
| 107 | } |
Jim Stichnoth | c4554d7 | 2014-09-30 16:49:38 -0700 | [diff] [blame] | 108 | return Result; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 109 | } |
| 110 | |
| 111 | // Returns true if the live range contains the given instruction |
| 112 | // number. This is only used for validating the live range |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 113 | // calculation. The IsDest argument indicates whether the Variable |
| 114 | // being tested is used in the Dest position (as opposed to a Src |
| 115 | // position). |
| 116 | bool LiveRange::containsValue(InstNumberT Value, bool IsDest) const { |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 117 | for (const RangeElementType &I : Range) { |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 118 | if (I.first <= Value && |
| 119 | (Value < I.second || (!IsDest && Value == I.second))) |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 120 | return true; |
| 121 | } |
| 122 | return false; |
| 123 | } |
| 124 | |
Jim Stichnoth | 037fa1d | 2014-10-07 11:09:33 -0700 | [diff] [blame] | 125 | void LiveRange::trim(InstNumberT Lower) { |
| 126 | while (TrimmedBegin != Range.end() && TrimmedBegin->second <= Lower) |
| 127 | ++TrimmedBegin; |
| 128 | } |
| 129 | |
Jim Stichnoth | 9a04c07 | 2014-12-11 15:51:42 -0800 | [diff] [blame] | 130 | IceString Variable::getName(const Cfg *Func) const { |
| 131 | if (Func && NameIndex >= 0) |
| 132 | return Func->getIdentifierName(NameIndex); |
Jim Stichnoth | 088b2be | 2014-10-23 12:02:08 -0700 | [diff] [blame] | 133 | return "__" + std::to_string(getIndex()); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 134 | } |
| 135 | |
Jim Stichnoth | 31c9559 | 2014-12-19 12:51:35 -0800 | [diff] [blame] | 136 | Variable *Variable::asType(Type Ty) { |
Jim Stichnoth | 800dab2 | 2014-09-20 12:25:02 -0700 | [diff] [blame] | 137 | // Note: This returns a Variable, even if the "this" object is a |
| 138 | // subclass of Variable. |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 139 | if (!BuildDefs::dump() || getType() == Ty) |
Jim Stichnoth | 31c9559 | 2014-12-19 12:51:35 -0800 | [diff] [blame] | 140 | return this; |
| 141 | Variable *V = new (getCurrentCfgAllocator()->Allocate<Variable>()) |
| 142 | Variable(kVariable, Ty, Number); |
| 143 | V->NameIndex = NameIndex; |
| 144 | V->RegNum = RegNum; |
| 145 | V->StackOffset = StackOffset; |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 146 | return V; |
| 147 | } |
| 148 | |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 149 | RegWeight Variable::getWeight(const Cfg *Func) const { |
| 150 | VariablesMetadata *VMetadata = Func->getVMetadata(); |
Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame^] | 151 | return mustHaveReg() ? RegWeight(RegWeight::Inf) |
| 152 | : mustNotHaveReg() ? RegWeight(RegWeight::Zero) |
| 153 | : VMetadata->getUseWeight(this); |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 154 | } |
| 155 | |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 156 | void VariableTracking::markUse(MetadataKind TrackingKind, const Inst *Instr, |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 157 | CfgNode *Node, bool IsImplicit) { |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 158 | (void)TrackingKind; |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 159 | |
Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame^] | 160 | // Increment the use weight depending on the loop nest depth. The weight is |
| 161 | // exponential in the nest depth as inner loops are expected to be executed |
| 162 | // an exponentially greater number of times. |
| 163 | constexpr uint32_t LogLoopTripCountEstimate = 2; // 2^2 = 4 |
| 164 | constexpr SizeT MaxShift = sizeof(uint32_t) * CHAR_BIT - 1; |
| 165 | constexpr SizeT MaxLoopNestDepth = MaxShift / LogLoopTripCountEstimate; |
| 166 | const uint32_t LoopNestDepth = |
| 167 | std::min(Node->getLoopNestDepth(), MaxLoopNestDepth); |
| 168 | const uint32_t ThisUseWeight = uint32_t(1) |
| 169 | << LoopNestDepth * LogLoopTripCountEstimate; |
| 170 | UseWeight.addWeight(ThisUseWeight); |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 171 | |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 172 | if (MultiBlock == MBS_MultiBlock) |
| 173 | return; |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 174 | // TODO(stichnot): If the use occurs as a source operand in the |
| 175 | // first instruction of the block, and its definition is in this |
| 176 | // block's only predecessor, we might consider not marking this as a |
| 177 | // separate use. This may also apply if it's the first instruction |
| 178 | // of the block that actually uses a Variable. |
| 179 | assert(Node); |
| 180 | bool MakeMulti = false; |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 181 | if (IsImplicit) |
| 182 | MakeMulti = true; |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 183 | // A phi source variable conservatively needs to be marked as |
| 184 | // multi-block, even if its definition is in the same block. This |
| 185 | // is because there can be additional control flow before branching |
| 186 | // back to this node, and the variable is live throughout those |
| 187 | // nodes. |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 188 | if (Instr && llvm::isa<InstPhi>(Instr)) |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 189 | MakeMulti = true; |
| 190 | |
| 191 | if (!MakeMulti) { |
| 192 | switch (MultiBlock) { |
| 193 | case MBS_Unknown: |
| 194 | MultiBlock = MBS_SingleBlock; |
| 195 | SingleUseNode = Node; |
| 196 | break; |
| 197 | case MBS_SingleBlock: |
| 198 | if (SingleUseNode != Node) |
| 199 | MakeMulti = true; |
| 200 | break; |
| 201 | case MBS_MultiBlock: |
| 202 | break; |
| 203 | } |
| 204 | } |
| 205 | |
| 206 | if (MakeMulti) { |
| 207 | MultiBlock = MBS_MultiBlock; |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 208 | SingleUseNode = nullptr; |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 209 | } |
| 210 | } |
| 211 | |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 212 | void VariableTracking::markDef(MetadataKind TrackingKind, const Inst *Instr, |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 213 | CfgNode *Node) { |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 214 | // TODO(stichnot): If the definition occurs in the last instruction |
| 215 | // of the block, consider not marking this as a separate use. But |
| 216 | // be careful not to omit all uses of the variable if markDef() and |
| 217 | // markUse() both use this optimization. |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 218 | assert(Node); |
Jim Stichnoth | dd842db | 2015-01-27 12:53:53 -0800 | [diff] [blame] | 219 | // Verify that instructions are added in increasing order. |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 220 | #ifndef NDEBUG |
| 221 | if (TrackingKind == VMK_All) { |
| 222 | const Inst *LastInstruction = |
| 223 | Definitions.empty() ? FirstOrSingleDefinition : Definitions.back(); |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 224 | assert(LastInstruction == nullptr || |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 225 | Instr->getNumber() >= LastInstruction->getNumber()); |
| 226 | } |
| 227 | #endif |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 228 | constexpr bool IsImplicit = false; |
| 229 | markUse(TrackingKind, Instr, Node, IsImplicit); |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 230 | if (TrackingKind == VMK_Uses) |
| 231 | return; |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 232 | if (FirstOrSingleDefinition == nullptr) |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 233 | FirstOrSingleDefinition = Instr; |
| 234 | else if (TrackingKind == VMK_All) |
| 235 | Definitions.push_back(Instr); |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 236 | switch (MultiDef) { |
| 237 | case MDS_Unknown: |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 238 | assert(SingleDefNode == nullptr); |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 239 | MultiDef = MDS_SingleDef; |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 240 | SingleDefNode = Node; |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 241 | break; |
| 242 | case MDS_SingleDef: |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 243 | assert(SingleDefNode); |
| 244 | if (Node == SingleDefNode) { |
| 245 | MultiDef = MDS_MultiDefSingleBlock; |
| 246 | } else { |
| 247 | MultiDef = MDS_MultiDefMultiBlock; |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 248 | SingleDefNode = nullptr; |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 249 | } |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 250 | break; |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 251 | case MDS_MultiDefSingleBlock: |
| 252 | assert(SingleDefNode); |
| 253 | if (Node != SingleDefNode) { |
| 254 | MultiDef = MDS_MultiDefMultiBlock; |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 255 | SingleDefNode = nullptr; |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 256 | } |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 257 | break; |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 258 | case MDS_MultiDefMultiBlock: |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 259 | assert(SingleDefNode == nullptr); |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 260 | break; |
| 261 | } |
| 262 | } |
| 263 | |
| 264 | const Inst *VariableTracking::getFirstDefinition() const { |
| 265 | switch (MultiDef) { |
| 266 | case MDS_Unknown: |
| 267 | case MDS_MultiDefMultiBlock: |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 268 | return nullptr; |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 269 | case MDS_SingleDef: |
| 270 | case MDS_MultiDefSingleBlock: |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 271 | assert(FirstOrSingleDefinition); |
| 272 | return FirstOrSingleDefinition; |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 273 | } |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 274 | return nullptr; |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 275 | } |
| 276 | |
| 277 | const Inst *VariableTracking::getSingleDefinition() const { |
| 278 | switch (MultiDef) { |
| 279 | case MDS_Unknown: |
| 280 | case MDS_MultiDefMultiBlock: |
| 281 | case MDS_MultiDefSingleBlock: |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 282 | return nullptr; |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 283 | case MDS_SingleDef: |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 284 | assert(FirstOrSingleDefinition); |
| 285 | return FirstOrSingleDefinition; |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 286 | } |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 287 | return nullptr; |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 288 | } |
| 289 | |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 290 | void VariablesMetadata::init(MetadataKind TrackingKind) { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 291 | TimerMarker T(TimerStack::TT_vmetadata, Func); |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 292 | Kind = TrackingKind; |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 293 | Metadata.clear(); |
| 294 | Metadata.resize(Func->getNumVariables()); |
| 295 | |
| 296 | // Mark implicit args as being used in the entry node. |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 297 | for (Variable *Var : Func->getImplicitArgs()) { |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 298 | constexpr Inst *NoInst = nullptr; |
| 299 | CfgNode *EntryNode = Func->getEntryNode(); |
| 300 | constexpr bool IsImplicit = true; |
| 301 | Metadata[Var->getIndex()].markUse(Kind, NoInst, EntryNode, IsImplicit); |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 302 | } |
| 303 | |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 304 | for (CfgNode *Node : Func->getNodes()) |
| 305 | addNode(Node); |
| 306 | } |
| 307 | |
| 308 | void VariablesMetadata::addNode(CfgNode *Node) { |
| 309 | if (Func->getNumVariables() >= Metadata.size()) |
| 310 | Metadata.resize(Func->getNumVariables()); |
| 311 | |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 312 | for (Inst &I : Node->getPhis()) { |
| 313 | if (I.isDeleted()) |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 314 | continue; |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 315 | if (Variable *Dest = I.getDest()) { |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 316 | SizeT DestNum = Dest->getIndex(); |
| 317 | assert(DestNum < Metadata.size()); |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 318 | Metadata[DestNum].markDef(Kind, &I, Node); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 319 | } |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 320 | for (SizeT SrcNum = 0; SrcNum < I.getSrcSize(); ++SrcNum) { |
| 321 | if (const Variable *Var = llvm::dyn_cast<Variable>(I.getSrc(SrcNum))) { |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 322 | SizeT VarNum = Var->getIndex(); |
| 323 | assert(VarNum < Metadata.size()); |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 324 | constexpr bool IsImplicit = false; |
| 325 | Metadata[VarNum].markUse(Kind, &I, Node, IsImplicit); |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 326 | } |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 327 | } |
| 328 | } |
| 329 | |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 330 | for (Inst &I : Node->getInsts()) { |
| 331 | if (I.isDeleted()) |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 332 | continue; |
Jim Stichnoth | bb8b624 | 2014-11-04 09:10:01 -0800 | [diff] [blame] | 333 | // Note: The implicit definitions (and uses) from InstFakeKill are |
| 334 | // deliberately ignored. |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 335 | if (Variable *Dest = I.getDest()) { |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 336 | SizeT DestNum = Dest->getIndex(); |
| 337 | assert(DestNum < Metadata.size()); |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 338 | Metadata[DestNum].markDef(Kind, &I, Node); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 339 | } |
John Porto | ec3f565 | 2015-08-31 15:07:09 -0700 | [diff] [blame] | 340 | FOREACH_VAR_IN_INST(Var, I) { |
| 341 | SizeT VarNum = Var->getIndex(); |
| 342 | assert(VarNum < Metadata.size()); |
| 343 | constexpr bool IsImplicit = false; |
| 344 | Metadata[VarNum].markUse(Kind, &I, Node, IsImplicit); |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 345 | } |
| 346 | } |
| 347 | } |
| 348 | |
| 349 | bool VariablesMetadata::isMultiDef(const Variable *Var) const { |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 350 | assert(Kind != VMK_Uses); |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 351 | if (Var->getIsArg()) |
| 352 | return false; |
| 353 | if (!isTracked(Var)) |
| 354 | return true; // conservative answer |
| 355 | SizeT VarNum = Var->getIndex(); |
| 356 | // Conservatively return true if the state is unknown. |
| 357 | return Metadata[VarNum].getMultiDef() != VariableTracking::MDS_SingleDef; |
| 358 | } |
| 359 | |
| 360 | bool VariablesMetadata::isMultiBlock(const Variable *Var) const { |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 361 | if (Var->getIsArg()) |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 362 | return true; |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 363 | if (!isTracked(Var)) |
| 364 | return true; // conservative answer |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 365 | SizeT VarNum = Var->getIndex(); |
| 366 | // Conservatively return true if the state is unknown. |
| 367 | return Metadata[VarNum].getMultiBlock() != VariableTracking::MBS_SingleBlock; |
| 368 | } |
| 369 | |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 370 | const Inst *VariablesMetadata::getFirstDefinition(const Variable *Var) const { |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 371 | assert(Kind != VMK_Uses); |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 372 | if (!isTracked(Var)) |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 373 | return nullptr; // conservative answer |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 374 | SizeT VarNum = Var->getIndex(); |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 375 | return Metadata[VarNum].getFirstDefinition(); |
| 376 | } |
| 377 | |
| 378 | const Inst *VariablesMetadata::getSingleDefinition(const Variable *Var) const { |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 379 | assert(Kind != VMK_Uses); |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 380 | if (!isTracked(Var)) |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 381 | return nullptr; // conservative answer |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 382 | SizeT VarNum = Var->getIndex(); |
| 383 | return Metadata[VarNum].getSingleDefinition(); |
| 384 | } |
| 385 | |
| 386 | const InstDefList & |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 387 | VariablesMetadata::getLatterDefinitions(const Variable *Var) const { |
| 388 | assert(Kind == VMK_All); |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 389 | if (!isTracked(Var)) |
| 390 | return NoDefinitions; |
| 391 | SizeT VarNum = Var->getIndex(); |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 392 | return Metadata[VarNum].getLatterDefinitions(); |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 393 | } |
| 394 | |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 395 | CfgNode *VariablesMetadata::getLocalUseNode(const Variable *Var) const { |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 396 | if (!isTracked(Var)) |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 397 | return nullptr; // conservative answer |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 398 | SizeT VarNum = Var->getIndex(); |
| 399 | return Metadata[VarNum].getNode(); |
| 400 | } |
| 401 | |
Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame^] | 402 | RegWeight VariablesMetadata::getUseWeight(const Variable *Var) const { |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 403 | if (!isTracked(Var)) |
Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame^] | 404 | return RegWeight(1); // conservative answer |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 405 | SizeT VarNum = Var->getIndex(); |
| 406 | return Metadata[VarNum].getUseWeight(); |
| 407 | } |
| 408 | |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 409 | const InstDefList VariablesMetadata::NoDefinitions; |
| 410 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 411 | // ======================== dump routines ======================== // |
| 412 | |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 413 | void Variable::emit(const Cfg *Func) const { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 414 | if (BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 415 | Func->getTarget()->emitVariable(this); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 416 | } |
| 417 | |
Jim Stichnoth | 2e8bfbb | 2014-09-16 10:16:00 -0700 | [diff] [blame] | 418 | void Variable::dump(const Cfg *Func, Ostream &Str) const { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 419 | if (!BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 420 | return; |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 421 | if (Func == nullptr) { |
Jim Stichnoth | 9a04c07 | 2014-12-11 15:51:42 -0800 | [diff] [blame] | 422 | Str << "%" << getName(Func); |
Jim Stichnoth | 2e8bfbb | 2014-09-16 10:16:00 -0700 | [diff] [blame] | 423 | return; |
| 424 | } |
Jim Stichnoth | fa4efea | 2015-01-27 05:06:03 -0800 | [diff] [blame] | 425 | if (Func->isVerbose(IceV_RegOrigins) || |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 426 | (!hasReg() && !Func->getTarget()->hasComputedFrame())) |
Jim Stichnoth | 9a04c07 | 2014-12-11 15:51:42 -0800 | [diff] [blame] | 427 | Str << "%" << getName(Func); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 428 | if (hasReg()) { |
Jim Stichnoth | fa4efea | 2015-01-27 05:06:03 -0800 | [diff] [blame] | 429 | if (Func->isVerbose(IceV_RegOrigins)) |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 430 | Str << ":"; |
| 431 | Str << Func->getTarget()->getRegName(RegNum, getType()); |
| 432 | } else if (Func->getTarget()->hasComputedFrame()) { |
Jim Stichnoth | fa4efea | 2015-01-27 05:06:03 -0800 | [diff] [blame] | 433 | if (Func->isVerbose(IceV_RegOrigins)) |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 434 | Str << ":"; |
Jan Voung | 28068ad | 2015-07-31 12:58:46 -0700 | [diff] [blame] | 435 | int32_t BaseRegisterNumber = getBaseRegNum(); |
| 436 | if (BaseRegisterNumber == NoRegister) |
| 437 | BaseRegisterNumber = Func->getTarget()->getFrameOrStackReg(); |
Jim Stichnoth | dd842db | 2015-01-27 12:53:53 -0800 | [diff] [blame] | 438 | Str << "[" |
Jan Voung | 28068ad | 2015-07-31 12:58:46 -0700 | [diff] [blame] | 439 | << Func->getTarget()->getRegName(BaseRegisterNumber, IceType_i32); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 440 | int32_t Offset = getStackOffset(); |
| 441 | if (Offset) { |
| 442 | if (Offset > 0) |
| 443 | Str << "+"; |
| 444 | Str << Offset; |
| 445 | } |
| 446 | Str << "]"; |
| 447 | } |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 448 | } |
| 449 | |
Jan Voung | 76bb0be | 2015-05-14 09:26:19 -0700 | [diff] [blame] | 450 | template <> void ConstantInteger32::emit(TargetLowering *Target) const { |
| 451 | Target->emit(this); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 452 | } |
| 453 | |
Jan Voung | 76bb0be | 2015-05-14 09:26:19 -0700 | [diff] [blame] | 454 | template <> void ConstantInteger64::emit(TargetLowering *Target) const { |
| 455 | Target->emit(this); |
| 456 | } |
| 457 | |
| 458 | template <> void ConstantFloat::emit(TargetLowering *Target) const { |
| 459 | Target->emit(this); |
| 460 | } |
| 461 | |
| 462 | template <> void ConstantDouble::emit(TargetLowering *Target) const { |
| 463 | Target->emit(this); |
| 464 | } |
| 465 | |
| 466 | void ConstantRelocatable::emit(TargetLowering *Target) const { |
| 467 | Target->emit(this); |
| 468 | } |
| 469 | |
| 470 | void ConstantRelocatable::emitWithoutPrefix(TargetLowering *Target) const { |
| 471 | Target->emitWithoutPrefix(this); |
Jim Stichnoth | bca2f65 | 2014-11-01 10:13:54 -0700 | [diff] [blame] | 472 | } |
| 473 | |
Karl Schimpf | df6f9d1 | 2014-10-20 14:09:00 -0700 | [diff] [blame] | 474 | void ConstantRelocatable::dump(const Cfg *Func, Ostream &Str) const { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 475 | if (!BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 476 | return; |
Karl Schimpf | df6f9d1 | 2014-10-20 14:09:00 -0700 | [diff] [blame] | 477 | Str << "@"; |
| 478 | if (Func && !SuppressMangling) { |
| 479 | Str << Func->getContext()->mangleName(Name); |
| 480 | } else { |
| 481 | Str << Name; |
| 482 | } |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 483 | if (Offset) |
| 484 | Str << "+" << Offset; |
| 485 | } |
| 486 | |
Jan Voung | 76bb0be | 2015-05-14 09:26:19 -0700 | [diff] [blame] | 487 | void ConstantUndef::emit(TargetLowering *Target) const { Target->emit(this); } |
| 488 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 489 | void LiveRange::dump(Ostream &Str) const { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 490 | if (!BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 491 | return; |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 492 | bool First = true; |
| 493 | for (const RangeElementType &I : Range) { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 494 | if (!First) |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 495 | Str << ", "; |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 496 | First = false; |
| 497 | Str << "[" << I.first << ":" << I.second << ")"; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 498 | } |
| 499 | } |
| 500 | |
| 501 | Ostream &operator<<(Ostream &Str, const LiveRange &L) { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 502 | if (!BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 503 | return Str; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 504 | L.dump(Str); |
| 505 | return Str; |
| 506 | } |
| 507 | |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 508 | Ostream &operator<<(Ostream &Str, const RegWeight &W) { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 509 | if (!BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 510 | return Str; |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 511 | if (W.getWeight() == RegWeight::Inf) |
| 512 | Str << "Inf"; |
| 513 | else |
| 514 | Str << W.getWeight(); |
| 515 | return Str; |
| 516 | } |
| 517 | |
Qining Lu | 253dc8a | 2015-06-22 10:10:23 -0700 | [diff] [blame] | 518 | // =========== Immediate Randomization and Pooling routines ============== |
| 519 | // Specialization of the template member function for ConstantInteger32 |
| 520 | // TODO(stichnot): try to move this specialization into a target-specific |
| 521 | // file. |
| 522 | template <> |
| 523 | bool ConstantInteger32::shouldBeRandomizedOrPooled(const GlobalContext *Ctx) { |
| 524 | uint32_t Threshold = Ctx->getFlags().getRandomizeAndPoolImmediatesThreshold(); |
| 525 | if (Ctx->getFlags().getRandomizeAndPoolImmediatesOption() == RPI_None) |
| 526 | return false; |
| 527 | if (getType() != IceType_i32 && getType() != IceType_i16 && |
| 528 | getType() != IceType_i8) |
| 529 | return false; |
| 530 | // The Following checks if the signed representation of Value is between |
| 531 | // -Threshold/2 and +Threshold/2 |
| 532 | bool largerThanThreshold = Threshold / 2 + Value >= Threshold; |
| 533 | return largerThanThreshold; |
| 534 | } |
| 535 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 536 | } // end of namespace Ice |