1//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===//
--- 39 unchanged lines hidden (view full) ---
48 49// Hidden options for help debugging. 50static cl::opt<bool> DisableReMat("disable-rematerialization", 51 cl::init(false), cl::Hidden); 52 53static cl::opt<bool> EnableFastSpilling("fast-spill", 54 cl::init(false), cl::Hidden); 55
|
56static cl::opt<bool> EarlyCoalescing("early-coalescing",
57 cl::init(false), cl::Hidden);
58
59static cl::opt<int> CoalescingLimit("early-coalescing-limit",
60 cl::init(-1), cl::Hidden);
61
|
56STATISTIC(numIntervals , "Number of original intervals"); 57STATISTIC(numFolds , "Number of loads/stores folded into instructions"); 58STATISTIC(numSplits , "Number of intervals split");
|
65STATISTIC(numCoalescing, "Number of early coalescing performed");
|
59 60char LiveIntervals::ID = 0; 61static RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 62 63void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 64 AU.setPreservesCFG(); 65 AU.addRequired<AliasAnalysis>(); 66 AU.addPreserved<AliasAnalysis>();
--- 17 unchanged lines hidden (view full) ---
84 85void LiveIntervals::releaseMemory() { 86 // Free the live intervals themselves. 87 for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(), 88 E = r2iMap_.end(); I != E; ++I) 89 delete I->second; 90 91 r2iMap_.clear();
|
99 phiJoinCopies.clear();
|
92 93 // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 94 VNInfoAllocator.Reset(); 95 while (!CloneMIs.empty()) { 96 MachineInstr *MI = CloneMIs.back(); 97 CloneMIs.pop_back(); 98 mf_->DeleteMachineInstr(MI); 99 }
--- 8 unchanged lines hidden (view full) ---
108 tri_ = tm_->getRegisterInfo(); 109 tii_ = tm_->getInstrInfo(); 110 aa_ = &getAnalysis<AliasAnalysis>(); 111 lv_ = &getAnalysis<LiveVariables>(); 112 indexes_ = &getAnalysis<SlotIndexes>(); 113 allocatableRegs_ = tri_->getAllocatableSet(fn); 114 115 computeIntervals();
|
124 performEarlyCoalescing();
|
116 117 numIntervals += getNumIntervals(); 118 119 DEBUG(dump()); 120 return true; 121} 122 123/// print - Implement the dump method.
--- 271 unchanged lines hidden (view full) ---
395 } else { 396 // Otherwise, this must be because of phi elimination. If this is the 397 // first redefinition of the vreg that we have seen, go back and change 398 // the live range in the PHI block to be a different value number. 399 if (interval.containsOneValue()) { 400 // Remove the old range that we now know has an incorrect number. 401 VNInfo *VNI = interval.getValNumInfo(0); 402 MachineInstr *Killer = vi.Kills[0];
|
412 phiJoinCopies.push_back(Killer);
|
403 SlotIndex Start = getMBBStartIdx(Killer->getParent()); 404 SlotIndex End = getInstructionIndex(Killer).getDefIndex(); 405 DEBUG({ 406 errs() << " Removing [" << Start << "," << End << "] from: "; 407 interval.print(errs(), tri_); 408 errs() << "\n"; 409 }); 410 interval.removeRange(Start, End);
--- 227 unchanged lines hidden (view full) ---
638 vni->setIsPHIDef(true); 639 LiveRange LR(start, end, vni); 640 641 interval.addRange(LR); 642 LR.valno->addKill(end); 643 DEBUG(errs() << " +" << LR << '\n'); 644} 645
|
656bool LiveIntervals::
657isSafeAndProfitableToCoalesce(LiveInterval &DstInt,
658 LiveInterval &SrcInt,
659 SmallVector<MachineInstr*,16> &IdentCopies,
660 SmallVector<MachineInstr*,16> &OtherCopies) {
661 unsigned NumIdent = 0;
662 for (MachineRegisterInfo::def_iterator ri = mri_->def_begin(SrcInt.reg),
663 re = mri_->def_end(); ri != re; ++ri) {
664 MachineInstr *MI = &*ri;
665 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
666 if (!tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
667 return false;
668 if (SrcReg != DstInt.reg) {
669 // Non-identity copy - we cannot handle overlapping intervals
670 if (DstInt.liveAt(getInstructionIndex(MI)))
671 return false;
672 OtherCopies.push_back(MI);
673 } else {
674 IdentCopies.push_back(MI);
675 ++NumIdent;
676 }
677 }
678
679 return IdentCopies.size() > OtherCopies.size();
680}
681
682void LiveIntervals::performEarlyCoalescing() {
683 if (!EarlyCoalescing)
684 return;
685
686 /// Perform early coalescing: eliminate copies which feed into phi joins
687 /// and whose sources are defined by the phi joins.
688 for (unsigned i = 0, e = phiJoinCopies.size(); i != e; ++i) {
689 MachineInstr *Join = phiJoinCopies[i];
690 if (CoalescingLimit != -1 && (int)numCoalescing == CoalescingLimit)
691 break;
692
693 unsigned PHISrc, PHIDst, SrcSubReg, DstSubReg;
694 bool isMove= tii_->isMoveInstr(*Join, PHISrc, PHIDst, SrcSubReg, DstSubReg);
695#ifndef NDEBUG
696 assert(isMove && "PHI join instruction must be a move!");
697#else
698 isMove = isMove;
699#endif
700
701 LiveInterval &DstInt = getInterval(PHIDst);
702 LiveInterval &SrcInt = getInterval(PHISrc);
703 SmallVector<MachineInstr*, 16> IdentCopies;
704 SmallVector<MachineInstr*, 16> OtherCopies;
705 if (!isSafeAndProfitableToCoalesce(DstInt, SrcInt,
706 IdentCopies, OtherCopies))
707 continue;
708
709 DEBUG(errs() << "PHI Join: " << *Join);
710 assert(DstInt.containsOneValue() && "PHI join should have just one val#!");
711 assert(std::distance(mri_->use_begin(PHISrc), mri_->use_end()) == 1 &&
712 "PHI join src should not be used elsewhere");
713 VNInfo *VNI = DstInt.getValNumInfo(0);
714
715 // Change the non-identity copies to directly target the phi destination.
716 for (unsigned i = 0, e = OtherCopies.size(); i != e; ++i) {
717 MachineInstr *PHICopy = OtherCopies[i];
718 SlotIndex MIIndex = getInstructionIndex(PHICopy);
719 DEBUG(errs() << "Moving: " << MIIndex << ' ' << *PHICopy);
720 SlotIndex DefIndex = MIIndex.getDefIndex();
721 LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex);
722 SlotIndex StartIndex = SLR->start;
723 SlotIndex EndIndex = SLR->end;
724
725 // Delete val# defined by the now identity copy and add the range from
726 // beginning of the mbb to the end of the range.
727 SrcInt.removeValNo(SLR->valno);
728 DEBUG(errs() << " added range [" << StartIndex << ','
729 << EndIndex << "] to reg" << DstInt.reg << '\n');
730 assert (!DstInt.liveAt(StartIndex) && "Cannot coalesce when dst live!");
731 VNInfo *NewVNI = DstInt.getNextValue(DefIndex, PHICopy, true,
732 VNInfoAllocator);
733 NewVNI->setHasPHIKill(true);
734 DstInt.addRange(LiveRange(StartIndex, EndIndex, NewVNI));
735 for (unsigned j = 0, ee = PHICopy->getNumOperands(); j != ee; ++j) {
736 MachineOperand &MO = PHICopy->getOperand(j);
737 if (!MO.isReg() || MO.getReg() != PHISrc)
738 continue;
739 MO.setReg(PHIDst);
740 }
741 }
742
743 // Now let's eliminate all the would-be identity copies.
744 for (unsigned i = 0, e = IdentCopies.size(); i != e; ++i) {
745 MachineInstr *PHICopy = IdentCopies[i];
746 DEBUG(errs() << "Coalescing: " << *PHICopy);
747
748 SlotIndex MIIndex = getInstructionIndex(PHICopy);
749 SlotIndex DefIndex = MIIndex.getDefIndex();
750 LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex);
751 SlotIndex StartIndex = SLR->start;
752 SlotIndex EndIndex = SLR->end;
753
754 // Delete val# defined by the now identity copy and add the range from
755 // beginning of the mbb to the end of the range.
756 SrcInt.removeValNo(SLR->valno);
757 RemoveMachineInstrFromMaps(PHICopy);
758 PHICopy->eraseFromParent();
759 DEBUG(errs() << " added range [" << StartIndex << ','
760 << EndIndex << "] to reg" << DstInt.reg << '\n');
761 DstInt.addRange(LiveRange(StartIndex, EndIndex, VNI));
762 }
763
764 // Remove the phi join and update the phi block liveness.
765 SlotIndex MIIndex = getInstructionIndex(Join);
766 SlotIndex UseIndex = MIIndex.getUseIndex();
767 SlotIndex DefIndex = MIIndex.getDefIndex();
768 LiveRange *SLR = SrcInt.getLiveRangeContaining(UseIndex);
769 LiveRange *DLR = DstInt.getLiveRangeContaining(DefIndex);
770 DLR->valno->setCopy(0);
771 DLR->valno->setIsDefAccurate(false);
772 DstInt.addRange(LiveRange(SLR->start, SLR->end, DLR->valno));
773 SrcInt.removeRange(SLR->start, SLR->end);
774 assert(SrcInt.empty());
775 removeInterval(PHISrc);
776 RemoveMachineInstrFromMaps(Join);
777 Join->eraseFromParent();
778
779 ++numCoalescing;
780 }
781}
782
|
646/// computeIntervals - computes the live intervals for virtual 647/// registers. for some ordering of the machine instructions [1,N] a 648/// live interval is an interval [i, j) where 1 <= i <= j < N for 649/// which a variable is live 650void LiveIntervals::computeIntervals() { 651 DEBUG(errs() << "********** COMPUTING LIVE INTERVALS **********\n" 652 << "********** Function: " 653 << ((Value*)mf_->getFunction())->getName() << '\n');
--- 1411 unchanged lines hidden --- |