OLD | NEW |
1 //===- subzero/src/IceCfgNode.cpp - Basic block (node) implementation -----===// | 1 //===- subzero/src/IceCfgNode.cpp - Basic block (node) 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 112 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
123 // example, | 123 // example, |
124 // a=phi(...) | 124 // a=phi(...) |
125 // changes to | 125 // changes to |
126 // "a_phi=phi(...); a=a_phi". | 126 // "a_phi=phi(...); a=a_phi". |
127 // | 127 // |
128 // This is in preparation for part 2 which deletes the Phi instructions and | 128 // This is in preparation for part 2 which deletes the Phi instructions and |
129 // appends assignment instructions to predecessor blocks. Note that this | 129 // appends assignment instructions to predecessor blocks. Note that this |
130 // transformation preserves SSA form. | 130 // transformation preserves SSA form. |
131 void CfgNode::placePhiLoads() { | 131 void CfgNode::placePhiLoads() { |
132 for (Inst &I : Phis) { | 132 for (Inst &I : Phis) { |
133 auto Phi = llvm::dyn_cast<InstPhi>(&I); | 133 auto *Phi = llvm::dyn_cast<InstPhi>(&I); |
134 Insts.insert(Insts.begin(), Phi->lower(Func)); | 134 Insts.insert(Insts.begin(), Phi->lower(Func)); |
135 } | 135 } |
136 } | 136 } |
137 | 137 |
138 // This does part 2 of Phi lowering. For each Phi instruction at each out-edge, | 138 // This does part 2 of Phi lowering. For each Phi instruction at each out-edge, |
139 // create a corresponding assignment instruction, and add all the assignments | 139 // create a corresponding assignment instruction, and add all the assignments |
140 // near the end of this block. They need to be added before any branch | 140 // near the end of this block. They need to be added before any branch |
141 // instruction, and also if the block ends with a compare instruction followed | 141 // instruction, and also if the block ends with a compare instruction followed |
142 // by a branch instruction that we may want to fuse, it's better to insert the | 142 // by a branch instruction that we may want to fuse, it's better to insert the |
143 // new assignments before the compare instruction. The | 143 // new assignments before the compare instruction. The |
(...skipping 71 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
215 ++InsertionPoint; | 215 ++InsertionPoint; |
216 } | 216 } |
217 } | 217 } |
218 } | 218 } |
219 } | 219 } |
220 | 220 |
221 // Consider every out-edge. | 221 // Consider every out-edge. |
222 for (CfgNode *Succ : OutEdges) { | 222 for (CfgNode *Succ : OutEdges) { |
223 // Consider every Phi instruction at the out-edge. | 223 // Consider every Phi instruction at the out-edge. |
224 for (Inst &I : Succ->Phis) { | 224 for (Inst &I : Succ->Phis) { |
225 auto Phi = llvm::dyn_cast<InstPhi>(&I); | 225 auto *Phi = llvm::dyn_cast<InstPhi>(&I); |
226 Operand *Operand = Phi->getOperandForTarget(this); | 226 Operand *Operand = Phi->getOperandForTarget(this); |
227 assert(Operand); | 227 assert(Operand); |
228 Variable *Dest = I.getDest(); | 228 Variable *Dest = I.getDest(); |
229 assert(Dest); | 229 assert(Dest); |
230 InstAssign *NewInst = InstAssign::create(Func, Dest, Operand); | 230 InstAssign *NewInst = InstAssign::create(Func, Dest, Operand); |
231 if (CmpInstDest == Operand) | 231 if (CmpInstDest == Operand) |
232 Insts.insert(SafeInsertionPoint, NewInst); | 232 Insts.insert(SafeInsertionPoint, NewInst); |
233 else | 233 else |
234 Insts.insert(InsertionPoint, NewInst); | 234 Insts.insert(InsertionPoint, NewInst); |
235 } | 235 } |
(...skipping 60 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
296 return NewNode; | 296 return NewNode; |
297 } | 297 } |
298 | 298 |
299 namespace { | 299 namespace { |
300 | 300 |
301 // Helper function used by advancedPhiLowering(). | 301 // Helper function used by advancedPhiLowering(). |
302 bool sameVarOrReg(TargetLowering *Target, const Variable *Var1, | 302 bool sameVarOrReg(TargetLowering *Target, const Variable *Var1, |
303 const Operand *Opnd) { | 303 const Operand *Opnd) { |
304 if (Var1 == Opnd) | 304 if (Var1 == Opnd) |
305 return true; | 305 return true; |
306 const auto Var2 = llvm::dyn_cast<Variable>(Opnd); | 306 const auto *Var2 = llvm::dyn_cast<Variable>(Opnd); |
307 if (Var2 == nullptr) | 307 if (Var2 == nullptr) |
308 return false; | 308 return false; |
309 | 309 |
310 // If either operand lacks a register, they cannot be the same. | 310 // If either operand lacks a register, they cannot be the same. |
311 if (!Var1->hasReg()) | 311 if (!Var1->hasReg()) |
312 return false; | 312 return false; |
313 if (!Var2->hasReg()) | 313 if (!Var2->hasReg()) |
314 return false; | 314 return false; |
315 | 315 |
316 int32_t RegNum1 = Var1->getRegNum(); | 316 int32_t RegNum1 = Var1->getRegNum(); |
(...skipping 135 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
452 constexpr int32_t WeightSrcIsReg = 2; | 452 constexpr int32_t WeightSrcIsReg = 2; |
453 // Prefer Dest not as a register because the register stays free longer. | 453 // Prefer Dest not as a register because the register stays free longer. |
454 constexpr int32_t WeightDestNotReg = 1; | 454 constexpr int32_t WeightDestNotReg = 1; |
455 | 455 |
456 for (size_t I = 0; I < NumPhis; ++I) { | 456 for (size_t I = 0; I < NumPhis; ++I) { |
457 if (Desc[I].Processed) | 457 if (Desc[I].Processed) |
458 continue; | 458 continue; |
459 int32_t Weight = 0; | 459 int32_t Weight = 0; |
460 if (Desc[I].NumPred == 0) | 460 if (Desc[I].NumPred == 0) |
461 Weight += WeightNoPreds; | 461 Weight += WeightNoPreds; |
462 if (auto Var = llvm::dyn_cast<Variable>(Desc[I].Src)) | 462 if (auto *Var = llvm::dyn_cast<Variable>(Desc[I].Src)) |
463 if (Var->hasReg()) | 463 if (Var->hasReg()) |
464 Weight += WeightSrcIsReg; | 464 Weight += WeightSrcIsReg; |
465 if (!Desc[I].Dest->hasReg()) | 465 if (!Desc[I].Dest->hasReg()) |
466 Weight += WeightDestNotReg; | 466 Weight += WeightDestNotReg; |
467 Desc[I].Weight = Weight; | 467 Desc[I].Weight = Weight; |
468 } | 468 } |
469 | 469 |
470 // Repeatedly choose and process the best candidate in the topological | 470 // Repeatedly choose and process the best candidate in the topological |
471 // sort, until no candidates remain. This implementation is O(N^2) where N | 471 // sort, until no candidates remain. This implementation is O(N^2) where N |
472 // is the number of Phi instructions, but with a small constant factor | 472 // is the number of Phi instructions, but with a small constant factor |
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
510 Found = true; | 510 Found = true; |
511 } | 511 } |
512 } | 512 } |
513 assert(Found); | 513 assert(Found); |
514 } | 514 } |
515 // Now that a cycle (if any) has been broken, create the actual | 515 // Now that a cycle (if any) has been broken, create the actual |
516 // assignment. | 516 // assignment. |
517 Split->appendInst(InstAssign::create(Func, Dest, Src)); | 517 Split->appendInst(InstAssign::create(Func, Dest, Src)); |
518 // Update NumPred for all Phi assignments using this Phi's Src as their | 518 // Update NumPred for all Phi assignments using this Phi's Src as their |
519 // Dest variable. Also update Weight if NumPred dropped from 1 to 0. | 519 // Dest variable. Also update Weight if NumPred dropped from 1 to 0. |
520 if (auto Var = llvm::dyn_cast<Variable>(Src)) { | 520 if (auto *Var = llvm::dyn_cast<Variable>(Src)) { |
521 for (size_t I = 0; I < NumPhis; ++I) { | 521 for (size_t I = 0; I < NumPhis; ++I) { |
522 if (Desc[I].Processed) | 522 if (Desc[I].Processed) |
523 continue; | 523 continue; |
524 if (sameVarOrReg(Target, Var, Desc[I].Dest)) { | 524 if (sameVarOrReg(Target, Var, Desc[I].Dest)) { |
525 if (--Desc[I].NumPred == 0) | 525 if (--Desc[I].NumPred == 0) |
526 Desc[I].Weight += WeightNoPreds; | 526 Desc[I].Weight += WeightNoPreds; |
527 } | 527 } |
528 } | 528 } |
529 } | 529 } |
530 Desc[BestIndex].Processed = true; | 530 Desc[BestIndex].Processed = true; |
(...skipping 96 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
627 LiveBegin->reserve(getInstCountEstimate()); | 627 LiveBegin->reserve(getInstCountEstimate()); |
628 LiveEnd->reserve(getInstCountEstimate()); | 628 LiveEnd->reserve(getInstCountEstimate()); |
629 } | 629 } |
630 // Initialize Live to be the union of all successors' LiveIn. | 630 // Initialize Live to be the union of all successors' LiveIn. |
631 for (CfgNode *Succ : OutEdges) { | 631 for (CfgNode *Succ : OutEdges) { |
632 Live |= Liveness->getLiveIn(Succ); | 632 Live |= Liveness->getLiveIn(Succ); |
633 // Mark corresponding argument of phis in successor as live. | 633 // Mark corresponding argument of phis in successor as live. |
634 for (Inst &I : Succ->Phis) { | 634 for (Inst &I : Succ->Phis) { |
635 if (I.isDeleted()) | 635 if (I.isDeleted()) |
636 continue; | 636 continue; |
637 auto Phi = llvm::dyn_cast<InstPhi>(&I); | 637 auto *Phi = llvm::dyn_cast<InstPhi>(&I); |
638 Phi->livenessPhiOperand(Live, this, Liveness); | 638 Phi->livenessPhiOperand(Live, this, Liveness); |
639 } | 639 } |
640 } | 640 } |
641 Liveness->getLiveOut(this) = Live; | 641 Liveness->getLiveOut(this) = Live; |
642 | 642 |
643 // Process regular instructions in reverse order. | 643 // Process regular instructions in reverse order. |
644 for (Inst &I : reverse_range(Insts)) { | 644 for (Inst &I : reverse_range(Insts)) { |
645 if (I.isDeleted()) | 645 if (I.isDeleted()) |
646 continue; | 646 continue; |
647 I.liveness(I.getNumber(), Live, Liveness, LiveBegin, LiveEnd); | 647 I.liveness(I.getNumber(), Live, Liveness, LiveBegin, LiveEnd); |
(...skipping 744 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1392 InstIntrinsicCall *Inst = InstIntrinsicCall::create( | 1392 InstIntrinsicCall *Inst = InstIntrinsicCall::create( |
1393 Func, 5, Func->makeVariable(IceType_i64), RMWI64Name, Info->Info); | 1393 Func, 5, Func->makeVariable(IceType_i64), RMWI64Name, Info->Info); |
1394 Inst->addArg(AtomicRMWOp); | 1394 Inst->addArg(AtomicRMWOp); |
1395 Inst->addArg(Counter); | 1395 Inst->addArg(Counter); |
1396 Inst->addArg(One); | 1396 Inst->addArg(One); |
1397 Inst->addArg(OrderAcquireRelease); | 1397 Inst->addArg(OrderAcquireRelease); |
1398 Insts.push_front(Inst); | 1398 Insts.push_front(Inst); |
1399 } | 1399 } |
1400 | 1400 |
1401 } // end of namespace Ice | 1401 } // end of namespace Ice |
OLD | NEW |