OLD | NEW |
1 //===- subzero/src/IceTargetLowering.cpp - Basic lowering implementation --===// | 1 //===- subzero/src/IceTargetLowering.cpp - Basic lowering 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 |
11 /// \brief Implements the skeleton of the TargetLowering class. | 11 /// \brief Implements the skeleton of the TargetLowering class. |
12 /// | 12 /// |
13 /// Specifically this invokes the appropriate lowering method for a given | 13 /// Specifically this invokes the appropriate lowering method for a given |
14 /// instruction kind and driving global register allocation. It also implements | 14 /// instruction kind and driving global register allocation. It also implements |
15 /// the non-deleted instruction iteration in LoweringContext. | 15 /// the non-deleted instruction iteration in LoweringContext. |
16 /// | 16 /// |
17 //===----------------------------------------------------------------------===// | 17 //===----------------------------------------------------------------------===// |
18 | 18 |
19 #include "IceTargetLowering.h" | 19 #include "IceTargetLowering.h" |
20 | 20 |
21 #include "IceBitVector.h" | 21 #include "IceBitVector.h" |
22 #include "IceCfg.h" // setError() | 22 #include "IceCfg.h" // setError() |
23 #include "IceCfgNode.h" | 23 #include "IceCfgNode.h" |
24 #include "IceGlobalContext.h" | 24 #include "IceGlobalContext.h" |
25 #include "IceGlobalInits.h" | 25 #include "IceGlobalInits.h" |
26 #include "IceInstVarIter.h" | 26 #include "IceInstVarIter.h" |
| 27 #include "IceLiveness.h" |
27 #include "IceOperand.h" | 28 #include "IceOperand.h" |
28 #include "IceRegAlloc.h" | 29 #include "IceRegAlloc.h" |
29 | 30 |
30 #include <string> | 31 #include <string> |
31 #include <vector> | 32 #include <vector> |
32 | 33 |
33 #define TARGET_LOWERING_CLASS_FOR(t) Target_##t | 34 #define TARGET_LOWERING_CLASS_FOR(t) Target_##t |
34 | 35 |
35 // We prevent target-specific implementation details from leaking outside their | 36 // We prevent target-specific implementation details from leaking outside their |
36 // implementations by forbidding #include of target-specific header files | 37 // implementations by forbidding #include of target-specific header files |
(...skipping 467 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
504 LinearScan.scan(RegMask, getFlags().getRandomizeRegisterAllocation()); | 505 LinearScan.scan(RegMask, getFlags().getRandomizeRegisterAllocation()); |
505 if (!LinearScan.hasEvictions()) | 506 if (!LinearScan.hasEvictions()) |
506 Repeat = false; | 507 Repeat = false; |
507 Kind = RAK_SecondChance; | 508 Kind = RAK_SecondChance; |
508 } while (Repeat); | 509 } while (Repeat); |
509 // TODO(stichnot): Run the register allocator one more time to do stack slot | 510 // TODO(stichnot): Run the register allocator one more time to do stack slot |
510 // coalescing. The idea would be to initialize the Unhandled list with the | 511 // coalescing. The idea would be to initialize the Unhandled list with the |
511 // set of Variables that have no register and a non-empty live range, and | 512 // set of Variables that have no register and a non-empty live range, and |
512 // model an infinite number of registers. Maybe use the register aliasing | 513 // model an infinite number of registers. Maybe use the register aliasing |
513 // mechanism to get better packing of narrower slots. | 514 // mechanism to get better packing of narrower slots. |
| 515 if (getFlags().getSplitGlobalVars()) |
| 516 postRegallocSplitting(RegMask); |
| 517 } |
| 518 |
| 519 namespace { |
| 520 CfgVector<Inst *> getInstructionsInRange(CfgNode *Node, InstNumberT Start, |
| 521 InstNumberT End) { |
| 522 CfgVector<Inst *> Result; |
| 523 bool Started = false; |
| 524 auto Process = [&](InstList &Insts) { |
| 525 for (auto &Instr : Insts) { |
| 526 if (Instr.isDeleted()) { |
| 527 continue; |
| 528 } |
| 529 if (Instr.getNumber() == Start) { |
| 530 Started = true; |
| 531 } |
| 532 if (Started) { |
| 533 Result.emplace_back(&Instr); |
| 534 } |
| 535 if (Instr.getNumber() == End) { |
| 536 break; |
| 537 } |
| 538 } |
| 539 }; |
| 540 Process(Node->getPhis()); |
| 541 Process(Node->getInsts()); |
| 542 // TODO(manasijm): Investigate why checking >= End significantly changes |
| 543 // output. Should not happen when renumbering produces monotonically |
| 544 // increasing instruction numbers and live ranges begin and end on non-deleted |
| 545 // instructions. |
| 546 return Result; |
| 547 } |
| 548 } |
| 549 |
| 550 void TargetLowering::postRegallocSplitting(const SmallBitVector &RegMask) { |
| 551 // Splits the live ranges of global(/multi block) variables and runs the |
| 552 // register allocator to find registers for as many of the new variables as |
| 553 // possible. |
| 554 // TODO(manasijm): Merge the small liveranges back into multi-block ones when |
| 555 // the variables get the same register. This will reduce the amount of new |
| 556 // instructions inserted. This might involve a full dataflow analysis. |
| 557 // Also, modify the preference mechanism in the register allocator to match. |
| 558 |
| 559 TimerMarker _(TimerStack::TT_splitGlobalVars, Func); |
| 560 CfgSet<Variable *> SplitCandidates; |
| 561 |
| 562 // Find variables that do not have registers but are allowed to. Also skip |
| 563 // variables with single segment live ranges as they are not split further in |
| 564 // this function. |
| 565 for (Variable *Var : Func->getVariables()) { |
| 566 if (!Var->mustNotHaveReg() && !Var->hasReg()) { |
| 567 if (Var->getLiveRange().getNumSegments() > 1) |
| 568 SplitCandidates.insert(Var); |
| 569 } |
| 570 } |
| 571 if (SplitCandidates.empty()) |
| 572 return; |
| 573 |
| 574 CfgSet<Variable *> ExtraVars; |
| 575 |
| 576 struct UseInfo { |
| 577 Variable *Replacing = nullptr; |
| 578 Inst *FirstUse = nullptr; |
| 579 Inst *LastDef = nullptr; |
| 580 SizeT UseCount = 0; |
| 581 }; |
| 582 CfgUnorderedMap<Variable *, UseInfo> VarInfo; |
| 583 // Split the live ranges of the viable variables by node. |
| 584 // Compute metadata (UseInfo) for each of the resulting variables. |
| 585 for (auto *Var : SplitCandidates) { |
| 586 for (auto &Segment : Var->getLiveRange().getSegments()) { |
| 587 UseInfo Info; |
| 588 Info.Replacing = Var; |
| 589 auto *Node = Var->getLiveRange().getNodeForSegment(Segment.first); |
| 590 |
| 591 for (auto *Instr : |
| 592 getInstructionsInRange(Node, Segment.first, Segment.second)) { |
| 593 for (SizeT i = 0; i < Instr->getSrcSize(); ++i) { |
| 594 // It's safe to iterate over the top-level src operands rather than |
| 595 // using FOREACH_VAR_IN_INST(), because any variables inside e.g. |
| 596 // mem operands should already have registers. |
| 597 if (auto *Var = llvm::dyn_cast<Variable>(Instr->getSrc(i))) { |
| 598 if (Var == Info.Replacing) { |
| 599 if (Info.FirstUse == nullptr && !llvm::isa<InstPhi>(Instr)) { |
| 600 Info.FirstUse = Instr; |
| 601 } |
| 602 Info.UseCount++; |
| 603 } |
| 604 } |
| 605 } |
| 606 if (Instr->getDest() == Info.Replacing && !llvm::isa<InstPhi>(Instr)) { |
| 607 Info.LastDef = Instr; |
| 608 } |
| 609 } |
| 610 |
| 611 static constexpr SizeT MinUseThreshold = 3; |
| 612 // Skip if variable has less than `MinUseThreshold` uses in the segment. |
| 613 if (Info.UseCount < MinUseThreshold) |
| 614 continue; |
| 615 |
| 616 if (!Info.FirstUse && !Info.LastDef) { |
| 617 continue; |
| 618 } |
| 619 |
| 620 LiveRange LR; |
| 621 LR.addSegment(Segment); |
| 622 Variable *NewVar = Func->makeVariable(Var->getType()); |
| 623 |
| 624 NewVar->setLiveRange(LR); |
| 625 |
| 626 VarInfo[NewVar] = Info; |
| 627 |
| 628 ExtraVars.insert(NewVar); |
| 629 } |
| 630 } |
| 631 // Run the register allocator with all these new variables included |
| 632 LinearScan RegAlloc(Func); |
| 633 RegAlloc.init(RAK_Global, SplitCandidates); |
| 634 RegAlloc.scan(RegMask, getFlags().getRandomizeRegisterAllocation()); |
| 635 |
| 636 // Modify the Cfg to use the new variables that now have registers. |
| 637 for (auto *ExtraVar : ExtraVars) { |
| 638 if (!ExtraVar->hasReg()) { |
| 639 continue; |
| 640 } |
| 641 |
| 642 auto &Info = VarInfo[ExtraVar]; |
| 643 |
| 644 assert(ExtraVar->getLiveRange().getSegments().size() == 1); |
| 645 auto Segment = ExtraVar->getLiveRange().getSegments()[0]; |
| 646 |
| 647 auto *Node = |
| 648 Info.Replacing->getLiveRange().getNodeForSegment(Segment.first); |
| 649 |
| 650 auto RelevantInsts = |
| 651 getInstructionsInRange(Node, Segment.first, Segment.second); |
| 652 |
| 653 if (RelevantInsts.empty()) |
| 654 continue; |
| 655 |
| 656 // Replace old variables |
| 657 for (auto *Instr : RelevantInsts) { |
| 658 if (llvm::isa<InstPhi>(Instr)) |
| 659 continue; |
| 660 // TODO(manasijm): Figure out how to safely enable replacing phi dest |
| 661 // variables. The issue is that we can not insert low level mov |
| 662 // instructions into the PhiList. |
| 663 for (SizeT i = 0; i < Instr->getSrcSize(); ++i) { |
| 664 // FOREACH_VAR_IN_INST() not needed. Same logic as above. |
| 665 if (auto *Var = llvm::dyn_cast<Variable>(Instr->getSrc(i))) { |
| 666 if (Var == Info.Replacing) { |
| 667 Instr->replaceSource(i, ExtraVar); |
| 668 } |
| 669 } |
| 670 } |
| 671 if (Instr->getDest() == Info.Replacing) { |
| 672 Instr->replaceDest(ExtraVar); |
| 673 } |
| 674 } |
| 675 |
| 676 assert(Info.FirstUse != Info.LastDef); |
| 677 assert(Info.FirstUse || Info.LastDef); |
| 678 |
| 679 // Insert spill code |
| 680 if (Info.FirstUse != nullptr) { |
| 681 auto *NewInst = |
| 682 Func->getTarget()->createLoweredMove(ExtraVar, Info.Replacing); |
| 683 Node->getInsts().insert(instToIterator(Info.FirstUse), NewInst); |
| 684 } |
| 685 if (Info.LastDef != nullptr) { |
| 686 auto *NewInst = |
| 687 Func->getTarget()->createLoweredMove(Info.Replacing, ExtraVar); |
| 688 Node->getInsts().insertAfter(instToIterator(Info.LastDef), NewInst); |
| 689 } |
| 690 } |
514 } | 691 } |
515 | 692 |
516 void TargetLowering::markRedefinitions() { | 693 void TargetLowering::markRedefinitions() { |
517 // Find (non-SSA) instructions where the Dest variable appears in some source | 694 // Find (non-SSA) instructions where the Dest variable appears in some source |
518 // operand, and set the IsDestRedefined flag to keep liveness analysis | 695 // operand, and set the IsDestRedefined flag to keep liveness analysis |
519 // consistent. | 696 // consistent. |
520 for (auto Instr = Context.getCur(), E = Context.getNext(); Instr != E; | 697 for (auto Instr = Context.getCur(), E = Context.getNext(); Instr != E; |
521 ++Instr) { | 698 ++Instr) { |
522 if (Instr->isDeleted()) | 699 if (Instr->isDeleted()) |
523 continue; | 700 continue; |
(...skipping 414 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
938 case TARGET_LOWERING_CLASS_FOR(X): \ | 1115 case TARGET_LOWERING_CLASS_FOR(X): \ |
939 return ::X::createTargetHeaderLowering(Ctx); | 1116 return ::X::createTargetHeaderLowering(Ctx); |
940 #include "SZTargets.def" | 1117 #include "SZTargets.def" |
941 #undef SUBZERO_TARGET | 1118 #undef SUBZERO_TARGET |
942 } | 1119 } |
943 } | 1120 } |
944 | 1121 |
945 TargetHeaderLowering::~TargetHeaderLowering() = default; | 1122 TargetHeaderLowering::~TargetHeaderLowering() = default; |
946 | 1123 |
947 } // end of namespace Ice | 1124 } // end of namespace Ice |
OLD | NEW |