OLD | NEW |
(Empty) | |
| 1 //===- subzero/src/IceVariableSplitting.cpp - Local variable splitting ----===// |
| 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 //===----------------------------------------------------------------------===// |
| 9 /// |
| 10 /// \file |
| 11 /// \brief Aggressive block-local variable splitting to improve linear-scan |
| 12 /// register allocation. |
| 13 /// |
| 14 //===----------------------------------------------------------------------===// |
| 15 |
| 16 #include "IceVariableSplitting.h" |
| 17 |
| 18 #include "IceCfg.h" |
| 19 #include "IceCfgNode.h" |
| 20 #include "IceClFlags.h" |
| 21 #include "IceInst.h" |
| 22 #include "IceOperand.h" |
| 23 #include "IceTargetLowering.h" |
| 24 |
| 25 namespace Ice { |
| 26 |
| 27 namespace { |
| 28 |
| 29 /// A Variable is "allocable" if it is a register allocation candidate but |
| 30 /// doesn't already have a register. |
| 31 bool isAllocable(const Variable *Var) { |
| 32 if (Var == nullptr) |
| 33 return false; |
| 34 return !Var->hasReg() && Var->mayHaveReg(); |
| 35 } |
| 36 |
| 37 /// A Variable is "inf" if it already has a register or is infinite-weight. |
| 38 bool isInf(const Variable *Var) { |
| 39 if (Var == nullptr) |
| 40 return false; |
| 41 return Var->hasReg() || Var->mustHaveReg(); |
| 42 } |
| 43 |
| 44 /// VariableMap is a simple helper class that keeps track of the latest split |
| 45 /// version of the original Variables, as well as the instruction containing the |
| 46 /// last use of the Variable within the current block. For each entry, the |
| 47 /// Variable is tagged with the CfgNode that it is valid in, so that we don't |
| 48 /// need to clear the entire Map[] vector for each block. |
| 49 class VariableMap { |
| 50 private: |
| 51 VariableMap() = delete; |
| 52 VariableMap(const VariableMap &) = delete; |
| 53 VariableMap &operator=(const VariableMap &) = delete; |
| 54 |
| 55 struct VarInfo { |
| 56 /// MappedVar is the latest mapped/split version of the Variable. |
| 57 Variable *MappedVar = nullptr; |
| 58 /// MappedVarNode is the block in which MappedVar is valid. |
| 59 const CfgNode *MappedVarNode = nullptr; |
| 60 /// LastUseInst is the last instruction in the block that uses the Variable |
| 61 /// as a source operand. |
| 62 const Inst *LastUseInst = nullptr; |
| 63 /// LastUseNode is the block in which LastUseInst is valid. |
| 64 const CfgNode *LastUseNode = nullptr; |
| 65 VarInfo() = default; |
| 66 |
| 67 private: |
| 68 VarInfo(const VarInfo &) = delete; |
| 69 VarInfo &operator=(const VarInfo &) = delete; |
| 70 }; |
| 71 |
| 72 public: |
| 73 explicit VariableMap(Cfg *Func) |
| 74 : Func(Func), NumVars(Func->getNumVariables()), Map(NumVars) {} |
| 75 /// Reset the mappings at the start of a block. |
| 76 void reset(const CfgNode *CurNode) { |
| 77 Node = CurNode; |
| 78 // Do a prepass through all the instructions, marking which instruction is |
| 79 // the last use of each Variable within the block. |
| 80 for (const Inst &Instr : Node->getInsts()) { |
| 81 if (Instr.isDeleted()) |
| 82 continue; |
| 83 for (SizeT i = 0; i < Instr.getSrcSize(); ++i) { |
| 84 if (auto *SrcVar = llvm::dyn_cast<Variable>(Instr.getSrc(i))) { |
| 85 const SizeT VarNum = getVarNum(SrcVar); |
| 86 Map[VarNum].LastUseInst = &Instr; |
| 87 Map[VarNum].LastUseNode = Node; |
| 88 } |
| 89 } |
| 90 } |
| 91 } |
| 92 /// Get Var's current mapping (or Var itself if it has no mapping yet). |
| 93 Variable *get(Variable *Var) const { |
| 94 const SizeT VarNum = getVarNum(Var); |
| 95 Variable *MappedVar = Map[VarNum].MappedVar; |
| 96 if (MappedVar == nullptr) |
| 97 return Var; |
| 98 if (Map[VarNum].MappedVarNode != Node) |
| 99 return Var; |
| 100 return MappedVar; |
| 101 } |
| 102 /// Create a new linked Variable in the LinkedTo chain, and set it as Var's |
| 103 /// latest mapping. |
| 104 Variable *makeLinked(Variable *Var) { |
| 105 Variable *NewVar = Func->makeVariable(Var->getType()); |
| 106 NewVar->setRegClass(Var->getRegClass()); |
| 107 NewVar->setLinkedTo(get(Var)); |
| 108 const SizeT VarNum = getVarNum(Var); |
| 109 Map[VarNum].MappedVar = NewVar; |
| 110 Map[VarNum].MappedVarNode = Node; |
| 111 return NewVar; |
| 112 } |
| 113 /// Given Var that is LinkedTo some other variable, re-splice it into the |
| 114 /// LinkedTo chain so that the chain is ordered by Variable::getIndex(). |
| 115 void spliceBlockLocalLinkedToChain(Variable *Var) { |
| 116 Variable *LinkedTo = Var->getLinkedTo(); |
| 117 assert(LinkedTo != nullptr); |
| 118 assert(Var->getIndex() > LinkedTo->getIndex()); |
| 119 const SizeT VarNum = getVarNum(LinkedTo); |
| 120 Variable *Link = Map[VarNum].MappedVar; |
| 121 if (Link == nullptr || Map[VarNum].MappedVarNode != Node) |
| 122 return; |
| 123 Variable *LinkParent = Link->getLinkedTo(); |
| 124 while (LinkParent != nullptr && LinkParent->getIndex() >= Var->getIndex()) { |
| 125 Link = LinkParent; |
| 126 LinkParent = Link->getLinkedTo(); |
| 127 } |
| 128 Var->setLinkedTo(LinkParent); |
| 129 Link->setLinkedTo(Var); |
| 130 } |
| 131 /// Return whether the given Variable has any uses as a source operand within |
| 132 /// the current block. If it has no source operand uses, but is assigned as a |
| 133 /// dest variable in some instruction in the block, then we needn't bother |
| 134 /// splitting it. |
| 135 bool isDestUsedInBlock(const Variable *Dest) const { |
| 136 return Map[getVarNum(Dest)].LastUseNode == Node; |
| 137 } |
| 138 /// Return whether the given instruction is the last use of the given Variable |
| 139 /// within the current block. If it is, then we needn't bother splitting the |
| 140 /// Variable at this instruction. |
| 141 bool isInstLastUseOfVar(const Variable *Var, const Inst *Instr) { |
| 142 return Map[getVarNum(Var)].LastUseInst == Instr; |
| 143 } |
| 144 |
| 145 private: |
| 146 Cfg *const Func; |
| 147 // NumVars is for the size of the Map array. It can be const because any new |
| 148 // Variables created during the splitting pass don't need to be mapped. |
| 149 const SizeT NumVars; |
| 150 CfgVector<VarInfo> Map; |
| 151 const CfgNode *Node = nullptr; |
| 152 /// Get Var's VarNum, and do some validation. |
| 153 SizeT getVarNum(const Variable *Var) const { |
| 154 const SizeT VarNum = Var->getIndex(); |
| 155 assert(VarNum < NumVars); |
| 156 return VarNum; |
| 157 } |
| 158 }; |
| 159 |
| 160 /// LocalVariableSplitter tracks the necessary splitting state across |
| 161 /// instructions. |
| 162 class LocalVariableSplitter { |
| 163 LocalVariableSplitter() = delete; |
| 164 LocalVariableSplitter(const LocalVariableSplitter &) = delete; |
| 165 LocalVariableSplitter &operator=(const LocalVariableSplitter &) = delete; |
| 166 |
| 167 public: |
| 168 explicit LocalVariableSplitter(Cfg *Func) |
| 169 : Target(Func->getTarget()), VarMap(Func) {} |
| 170 /// setNode() is called before processing the instructions of a block. |
| 171 void setNode(CfgNode *CurNode) { |
| 172 Node = CurNode; |
| 173 VarMap.reset(Node); |
| 174 LinkedToFixups.clear(); |
| 175 } |
| 176 /// finalizeNode() is called after all instructions in the block are |
| 177 /// processed. |
| 178 void finalizeNode() { |
| 179 // Splice in any preexisting LinkedTo links into the single chain. These |
| 180 // are the ones that were recorded during setInst(). |
| 181 for (Variable *Var : LinkedToFixups) { |
| 182 VarMap.spliceBlockLocalLinkedToChain(Var); |
| 183 } |
| 184 } |
| 185 /// setInst() is called before processing the next instruction. The iterators |
| 186 /// are the insertion points for a new instructions, depending on whether the |
| 187 /// new instruction should be inserted before or after the current |
| 188 /// instruction. |
| 189 void setInst(Inst *CurInst, InstList::iterator Cur, InstList::iterator Next) { |
| 190 Instr = CurInst; |
| 191 Dest = Instr->getDest(); |
| 192 IterCur = Cur; |
| 193 IterNext = Next; |
| 194 ShouldSkipRemainingInstructions = false; |
| 195 // Note any preexisting LinkedTo relationships that were created during |
| 196 // target lowering. Record them in LinkedToFixups which is then processed |
| 197 // in finalizeNode(). |
| 198 if (Dest != nullptr && Dest->getLinkedTo() != nullptr) { |
| 199 LinkedToFixups.emplace_back(Dest); |
| 200 } |
| 201 } |
| 202 bool shouldSkipRemainingInstructions() const { |
| 203 return ShouldSkipRemainingInstructions; |
| 204 } |
| 205 bool isUnconditionallyExecuted() const { return WaitingForLabel == nullptr; } |
| 206 |
| 207 /// Note: the handle*() functions return true to indicate that the instruction |
| 208 /// has now been handled and that the instruction loop should continue to the |
| 209 /// next instruction in the block (and return false otherwise). In addition, |
| 210 /// they set the ShouldSkipRemainingInstructions flag to indicate that no more |
| 211 /// instructions in the block should be processed. |
| 212 |
| 213 /// Handle an "unwanted" instruction by returning true; |
| 214 bool handleUnwantedInstruction() { |
| 215 // We can limit the splitting to an arbitrary subset of the instructions, |
| 216 // and still expect correct code. As such, we can do instruction-subset |
| 217 // bisection to help debug any problems in this pass. |
| 218 static constexpr char AnInstructionHasNoName[] = ""; |
| 219 if (!BuildDefs::minimal() && |
| 220 !getFlags().matchSplitInsts(AnInstructionHasNoName, |
| 221 Instr->getNumber())) { |
| 222 return true; |
| 223 } |
| 224 if (!llvm::isa<InstTarget>(Instr)) { |
| 225 // Ignore non-lowered instructions like FakeDef/FakeUse. |
| 226 return true; |
| 227 } |
| 228 return false; |
| 229 } |
| 230 |
| 231 /// Process a potential label instruction. |
| 232 bool handleLabel() { |
| 233 if (!Instr->isLabel()) |
| 234 return false; |
| 235 // A Label instruction shouldn't have any operands, so it can be handled |
| 236 // right here and then move on. |
| 237 assert(Dest == nullptr); |
| 238 assert(Instr->getSrcSize() == 0); |
| 239 if (Instr == WaitingForLabel) { |
| 240 // If we found the forward-branch-target Label instruction we're waiting |
| 241 // for, then clear the WaitingForLabel state. |
| 242 WaitingForLabel = nullptr; |
| 243 } else if (WaitingForLabel == nullptr && WaitingForBranchTo == nullptr) { |
| 244 // If we found a new Label instruction while the WaitingFor* state is |
| 245 // clear, then set things up for this being a backward branch target. |
| 246 WaitingForBranchTo = Instr; |
| 247 } else { |
| 248 // We see something we don't understand, so skip to the next block. |
| 249 ShouldSkipRemainingInstructions = true; |
| 250 } |
| 251 return true; |
| 252 } |
| 253 |
| 254 /// Process a potential intra-block branch instruction. |
| 255 bool handleIntraBlockBranch() { |
| 256 const Inst *Label = Instr->getIntraBlockBranchTarget(); |
| 257 if (Label == nullptr) |
| 258 return false; |
| 259 // An intra-block branch instruction shouldn't have any operands, so it can |
| 260 // be handled right here and then move on. |
| 261 assert(Dest == nullptr); |
| 262 assert(Instr->getSrcSize() == 0); |
| 263 if (WaitingForBranchTo == Label && WaitingForLabel == nullptr) { |
| 264 WaitingForBranchTo = nullptr; |
| 265 } else if (WaitingForBranchTo == nullptr && |
| 266 (WaitingForLabel == nullptr || WaitingForLabel == Label)) { |
| 267 WaitingForLabel = Label; |
| 268 } else { |
| 269 // We see something we don't understand, so skip to the next block. |
| 270 ShouldSkipRemainingInstructions = true; |
| 271 } |
| 272 return true; |
| 273 } |
| 274 |
| 275 /// Specially process a potential "Variable=Variable" assignment instruction, |
| 276 /// when it conforms to certain patterns. |
| 277 bool handleSimpleVarAssign() { |
| 278 if (!Instr->isVarAssign()) |
| 279 return false; |
| 280 const bool DestIsInf = isInf(Dest); |
| 281 const bool DestIsAllocable = isAllocable(Dest); |
| 282 auto *SrcVar = llvm::cast<Variable>(Instr->getSrc(0)); |
| 283 const bool SrcIsInf = isInf(SrcVar); |
| 284 const bool SrcIsAllocable = isAllocable(SrcVar); |
| 285 if (DestIsInf && SrcIsInf) { |
| 286 // The instruction: |
| 287 // t:inf = u:inf |
| 288 // No transformation is needed. |
| 289 return true; |
| 290 } |
| 291 if (DestIsInf && SrcIsAllocable && Dest->getType() == SrcVar->getType()) { |
| 292 // The instruction: |
| 293 // t:inf = v |
| 294 // gets transformed to: |
| 295 // t:inf = v1 |
| 296 // v2 = t:inf |
| 297 // where: |
| 298 // v1 := map[v] |
| 299 // v2 := linkTo(v) |
| 300 // map[v] := v2 |
| 301 // |
| 302 // If both v2 and its linkedToStackRoot get a stack slot, then "v2=t:inf" |
| 303 // is recognized as a redundant assignment and elided. |
| 304 // |
| 305 // Note that if the dest and src types are different, then this is |
| 306 // actually a truncation operation, which would make "v2=t:inf" an invalid |
| 307 // instruction. In this case, the type test will make it fall through to |
| 308 // the general case below. |
| 309 Variable *OldMapped = VarMap.get(SrcVar); |
| 310 Instr->replaceSource(0, OldMapped); |
| 311 if (isUnconditionallyExecuted()) { |
| 312 // Only create new mapping state if the instruction is unconditionally |
| 313 // executed. |
| 314 if (!VarMap.isInstLastUseOfVar(SrcVar, Instr)) { |
| 315 Variable *NewMapped = VarMap.makeLinked(SrcVar); |
| 316 Inst *Mov = Target->createLoweredMove(NewMapped, Dest); |
| 317 Node->getInsts().insert(IterNext, Mov); |
| 318 } |
| 319 } |
| 320 return true; |
| 321 } |
| 322 if (DestIsAllocable && SrcIsInf) { |
| 323 if (!VarMap.isDestUsedInBlock(Dest)) { |
| 324 return true; |
| 325 } |
| 326 // The instruction: |
| 327 // v = t:inf |
| 328 // gets transformed to: |
| 329 // v = t:inf |
| 330 // v2 = t:inf |
| 331 // where: |
| 332 // v2 := linkTo(v) |
| 333 // map[v] := v2 |
| 334 // |
| 335 // If both v2 and v get a stack slot, then "v2=t:inf" is recognized as a |
| 336 // redundant assignment and elided. |
| 337 if (isUnconditionallyExecuted()) { |
| 338 // Only create new mapping state if the instruction is unconditionally |
| 339 // executed. |
| 340 Variable *NewMapped = VarMap.makeLinked(Dest); |
| 341 Inst *Mov = Target->createLoweredMove(NewMapped, SrcVar); |
| 342 Node->getInsts().insert(IterNext, Mov); |
| 343 } else { |
| 344 // For a conditionally executed instruction, add a redefinition of the |
| 345 // original Dest mapping, without creating a new linked variable. |
| 346 Variable *OldMapped = VarMap.get(Dest); |
| 347 Inst *Mov = Target->createLoweredMove(OldMapped, SrcVar); |
| 348 Mov->setDestRedefined(); |
| 349 Node->getInsts().insert(IterNext, Mov); |
| 350 } |
| 351 return true; |
| 352 } |
| 353 assert(!ShouldSkipRemainingInstructions); |
| 354 return false; |
| 355 } |
| 356 |
| 357 /// Process the dest Variable of a Phi instruction. |
| 358 bool handlePhi() { |
| 359 assert(llvm::isa<InstPhi>(Instr)); |
| 360 const bool DestIsAllocable = isAllocable(Dest); |
| 361 if (!DestIsAllocable) |
| 362 return true; |
| 363 if (!VarMap.isDestUsedInBlock(Dest)) |
| 364 return true; |
| 365 Variable *NewMapped = VarMap.makeLinked(Dest); |
| 366 Inst *Mov = Target->createLoweredMove(NewMapped, Dest); |
| 367 Node->getInsts().insert(IterCur, Mov); |
| 368 return true; |
| 369 } |
| 370 |
| 371 /// Process an arbitrary instruction. |
| 372 bool handleGeneralInst() { |
| 373 const bool DestIsAllocable = isAllocable(Dest); |
| 374 // The (non-variable-assignment) instruction: |
| 375 // ... = F(v) |
| 376 // where v is not infinite-weight, gets transformed to: |
| 377 // v2 = v1 |
| 378 // ... = F(v1) |
| 379 // where: |
| 380 // v1 := map[v] |
| 381 // v2 := linkTo(v) |
| 382 // map[v] := v2 |
| 383 // After that, if the "..." dest=u is not infinite-weight, append: |
| 384 // u2 = u |
| 385 // where: |
| 386 // u2 := linkTo(u) |
| 387 // map[u] := u2 |
| 388 for (SizeT i = 0; i < Instr->getSrcSize(); ++i) { |
| 389 // Iterate over the top-level src vars. Don't bother to dig into |
| 390 // e.g. MemOperands because their vars should all be infinite-weight. |
| 391 // (This assumption would need to change if the pass were done |
| 392 // pre-lowering.) |
| 393 if (auto *SrcVar = llvm::dyn_cast<Variable>(Instr->getSrc(i))) { |
| 394 const bool SrcIsAllocable = isAllocable(SrcVar); |
| 395 if (SrcIsAllocable) { |
| 396 Variable *OldMapped = VarMap.get(SrcVar); |
| 397 if (isUnconditionallyExecuted()) { |
| 398 if (!VarMap.isInstLastUseOfVar(SrcVar, Instr)) { |
| 399 Variable *NewMapped = VarMap.makeLinked(SrcVar); |
| 400 Inst *Mov = Target->createLoweredMove(NewMapped, OldMapped); |
| 401 Node->getInsts().insert(IterCur, Mov); |
| 402 } |
| 403 } |
| 404 Instr->replaceSource(i, OldMapped); |
| 405 } |
| 406 } |
| 407 } |
| 408 // Transformation of Dest is the same as the "v=t:inf" case above. |
| 409 if (DestIsAllocable && VarMap.isDestUsedInBlock(Dest)) { |
| 410 if (isUnconditionallyExecuted()) { |
| 411 Variable *NewMapped = VarMap.makeLinked(Dest); |
| 412 Inst *Mov = Target->createLoweredMove(NewMapped, Dest); |
| 413 Node->getInsts().insert(IterNext, Mov); |
| 414 } else { |
| 415 Variable *OldMapped = VarMap.get(Dest); |
| 416 Inst *Mov = Target->createLoweredMove(OldMapped, Dest); |
| 417 Mov->setDestRedefined(); |
| 418 Node->getInsts().insert(IterNext, Mov); |
| 419 } |
| 420 } |
| 421 return true; |
| 422 } |
| 423 |
| 424 private: |
| 425 TargetLowering *Target; |
| 426 CfgNode *Node = nullptr; |
| 427 Inst *Instr = nullptr; |
| 428 Variable *Dest = nullptr; |
| 429 InstList::iterator IterCur; |
| 430 InstList::iterator IterNext; |
| 431 bool ShouldSkipRemainingInstructions = false; |
| 432 VariableMap VarMap; |
| 433 CfgVector<Variable *> LinkedToFixups; |
| 434 /// WaitingForLabel and WaitingForBranchTo are for tracking intra-block |
| 435 /// control flow. |
| 436 const Inst *WaitingForLabel = nullptr; |
| 437 const Inst *WaitingForBranchTo = nullptr; |
| 438 }; |
| 439 |
| 440 } // end of anonymous namespace |
| 441 |
| 442 /// Within each basic block, rewrite Variable references in terms of chained |
| 443 /// copies of the original Variable. For example: |
| 444 /// A = B + C |
| 445 /// might be rewritten as: |
| 446 /// B1 = B |
| 447 /// C1 = C |
| 448 /// A = B + C |
| 449 /// A1 = A |
| 450 /// and then: |
| 451 /// D = A + B |
| 452 /// might be rewritten as: |
| 453 /// A2 = A1 |
| 454 /// B2 = B1 |
| 455 /// D = A1 + B1 |
| 456 /// D1 = D |
| 457 /// |
| 458 /// The purpose is to present the linear-scan register allocator with smaller |
| 459 /// live ranges, to help mitigate its "all or nothing" allocation strategy, |
| 460 /// while counting on its preference mechanism to keep the split versions in the |
| 461 /// same register when possible. |
| 462 /// |
| 463 /// When creating new Variables, A2 is linked to A1 which is linked to A, and |
| 464 /// similar for the other Variable linked-to chains. Rewrites apply only to |
| 465 /// Variables where mayHaveReg() is true. |
| 466 /// |
| 467 /// At code emission time, redundant linked-to stack assignments will be |
| 468 /// recognized and elided. To illustrate using the above example, if A1 gets a |
| 469 /// register but A and A2 are on the stack, the "A2=A1" store instruction is |
| 470 /// redundant since A and A2 share the same stack slot and A1 originated from A. |
| 471 /// |
| 472 /// Simple assignment instructions are rewritten slightly differently, to take |
| 473 /// maximal advantage of Variables known to have registers. |
| 474 /// |
| 475 /// In general, there may be several valid ways to rewrite an instruction: add |
| 476 /// the new assignment instruction either before or after the original |
| 477 /// instruction, and rewrite the original instruction with either the old or the |
| 478 /// new variable mapping. We try to pick a strategy most likely to avoid |
| 479 /// potential performance problems. For example, try to avoid storing to the |
| 480 /// stack and then immediately reloading from the same location. One |
| 481 /// consequence is that code might be generated that loads a register from a |
| 482 /// stack location, followed almost immediately by another use of the same stack |
| 483 /// location, despite its value already being available in a register as a |
| 484 /// result of the first instruction. However, the performance impact here is |
| 485 /// likely to be negligible, and a simple availability peephole optimization |
| 486 /// could clean it up. |
| 487 /// |
| 488 /// This pass potentially adds a lot of new instructions and variables, and as |
| 489 /// such there are compile-time performance concerns, particularly with liveness |
| 490 /// analysis and register allocation. Note that for liveness analysis, the new |
| 491 /// variables have single-block liveness, so they don't increase the size of the |
| 492 /// liveness bit vectors that need to be merged across blocks. As a result, the |
| 493 /// performance impact is likely to be linearly related to the number of new |
| 494 /// instructions, rather than number of new variables times number of blocks |
| 495 /// which would be the case if they were multi-block variables. |
| 496 void splitBlockLocalVariables(Cfg *Func) { |
| 497 if (!getFlags().getSplitLocalVars()) |
| 498 return; |
| 499 TimerMarker _(TimerStack::TT_splitLocalVars, Func); |
| 500 LocalVariableSplitter Splitter(Func); |
| 501 // TODO(stichnot): Fix this mechanism for LinkedTo variables and stack slot |
| 502 // assignment. |
| 503 // |
| 504 // To work around shortcomings with stack frame mapping, we want to arrange |
| 505 // LinkedTo structure such that within one block, the LinkedTo structure |
| 506 // leading to a root forms a list, not a tree. A LinkedTo root can have |
| 507 // multiple children linking to it, but only one per block. Furthermore, |
| 508 // because stack slot mapping processes variables in numerical order, the |
| 509 // LinkedTo chain needs to be ordered such that when A->getLinkedTo() == B, |
| 510 // then A->getIndex() > B->getIndex(). |
| 511 // |
| 512 // To effect this, while processing a block we keep track of preexisting |
| 513 // LinkedTo relationships via the LinkedToFixups vector, and at the end of the |
| 514 // block we splice them in such that the block has a single chain for each |
| 515 // root, ordered by getIndex() value. |
| 516 CfgVector<Variable *> LinkedToFixups; |
| 517 for (CfgNode *Node : Func->getNodes()) { |
| 518 // Clear the VarMap and LinkedToFixups at the start of every block. |
| 519 LinkedToFixups.clear(); |
| 520 Splitter.setNode(Node); |
| 521 auto &Insts = Node->getInsts(); |
| 522 auto Iter = Insts.begin(); |
| 523 auto IterEnd = Insts.end(); |
| 524 // TODO(stichnot): Figure out why Phi processing usually degrades |
| 525 // performance. Disable for now. |
| 526 static constexpr bool ProcessPhis = false; |
| 527 if (ProcessPhis) { |
| 528 for (Inst &Instr : Node->getPhis()) { |
| 529 if (Instr.isDeleted()) |
| 530 continue; |
| 531 Splitter.setInst(&Instr, Iter, Iter); |
| 532 Splitter.handlePhi(); |
| 533 } |
| 534 } |
| 535 InstList::iterator NextIter; |
| 536 for (; Iter != IterEnd && !Splitter.shouldSkipRemainingInstructions(); |
| 537 Iter = NextIter) { |
| 538 NextIter = Iter; |
| 539 ++NextIter; |
| 540 Inst *Instr = iteratorToInst(Iter); |
| 541 if (Instr->isDeleted()) |
| 542 continue; |
| 543 Splitter.setInst(Instr, Iter, NextIter); |
| 544 |
| 545 // Before doing any transformations, take care of the bookkeeping for |
| 546 // intra-block branching. |
| 547 // |
| 548 // This is tricky because the transformation for one instruction may |
| 549 // depend on a transformation for a previous instruction, but if that |
| 550 // previous instruction is not dynamically executed due to intra-block |
| 551 // control flow, it may lead to an inconsistent state and incorrect code. |
| 552 // |
| 553 // We want to handle some simple cases, and reject some others: |
| 554 // |
| 555 // 1. For something like a select instruction, we could have: |
| 556 // test cond |
| 557 // dest = src_false |
| 558 // branch conditionally to label |
| 559 // dest = src_true |
| 560 // label: |
| 561 // |
| 562 // Between the conditional branch and the label, we need to treat dest and |
| 563 // src variables specially, specifically not creating any new state. |
| 564 // |
| 565 // 2. Some 64-bit atomic instructions may be lowered to a loop: |
| 566 // label: |
| 567 // ... |
| 568 // branch conditionally to label |
| 569 // |
| 570 // No special treatment is needed, but it's worth tracking so that case #1 |
| 571 // above can also be handled. |
| 572 // |
| 573 // 3. Advanced switch lowering can create really complex intra-block |
| 574 // control flow, so when we recognize this, we should just stop splitting |
| 575 // for the remainder of the block (which isn't much since a switch |
| 576 // instruction is a terminator). |
| 577 // |
| 578 // 4. Other complex lowering, e.g. an i64 icmp on a 32-bit architecture, |
| 579 // can result in an if/then/else like structure with two labels. One |
| 580 // possibility would be to suspect splitting for the remainder of the |
| 581 // lowered instruction, and then resume for the remainder of the block, |
| 582 // but since we don't have high-level instruction markers, we might as |
| 583 // well just stop splitting for the remainder of the block. |
| 584 if (Splitter.handleLabel()) |
| 585 continue; |
| 586 if (Splitter.handleIntraBlockBranch()) |
| 587 continue; |
| 588 if (Splitter.handleUnwantedInstruction()) |
| 589 continue; |
| 590 |
| 591 // Intra-block bookkeeping is complete, now do the transformations. |
| 592 |
| 593 // Determine the transformation based on the kind of instruction, and |
| 594 // whether its Variables are infinite-weight. New instructions can be |
| 595 // inserted before the current instruction via Iter, or after the current |
| 596 // instruction via NextIter. |
| 597 if (Splitter.handleSimpleVarAssign()) |
| 598 continue; |
| 599 if (Splitter.handleGeneralInst()) |
| 600 continue; |
| 601 } |
| 602 Splitter.finalizeNode(); |
| 603 } |
| 604 |
| 605 Func->dump("After splitting local variables"); |
| 606 } |
| 607 |
| 608 } // end of namespace Ice |
OLD | NEW |