Deleted Added
sdiff udiff text old ( 199481 ) new ( 199511 )
full compact
LiveIntervalAnalysis.cpp (199481) LiveIntervalAnalysis.cpp (199511)
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
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
62STATISTIC(numIntervals , "Number of original intervals");
63STATISTIC(numFolds , "Number of loads/stores folded into instructions");
64STATISTIC(numSplits , "Number of intervals split");
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");
66
67char LiveIntervals::ID = 0;
68static RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
69
70void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
71 AU.setPreservesCFG();
72 AU.addRequired<AliasAnalysis>();
73 AU.addPreserved<AliasAnalysis>();

--- 17 unchanged lines hidden (view full) ---

91
92void LiveIntervals::releaseMemory() {
93 // Free the live intervals themselves.
94 for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(),
95 E = r2iMap_.end(); I != E; ++I)
96 delete I->second;
97
98 r2iMap_.clear();
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();
100
101 // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
102 VNInfoAllocator.Reset();
103 while (!CloneMIs.empty()) {
104 MachineInstr *MI = CloneMIs.back();
105 CloneMIs.pop_back();
106 mf_->DeleteMachineInstr(MI);
107 }

--- 8 unchanged lines hidden (view full) ---

116 tri_ = tm_->getRegisterInfo();
117 tii_ = tm_->getInstrInfo();
118 aa_ = &getAnalysis<AliasAnalysis>();
119 lv_ = &getAnalysis<LiveVariables>();
120 indexes_ = &getAnalysis<SlotIndexes>();
121 allocatableRegs_ = tri_->getAllocatableSet(fn);
122
123 computeIntervals();
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();
125
126 numIntervals += getNumIntervals();
127
128 DEBUG(dump());
129 return true;
130}
131
132/// print - Implement the dump method.

--- 271 unchanged lines hidden (view full) ---

404 } else {
405 // Otherwise, this must be because of phi elimination. If this is the
406 // first redefinition of the vreg that we have seen, go back and change
407 // the live range in the PHI block to be a different value number.
408 if (interval.containsOneValue()) {
409 // Remove the old range that we now know has an incorrect number.
410 VNInfo *VNI = interval.getValNumInfo(0);
411 MachineInstr *Killer = vi.Kills[0];
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);
413 SlotIndex Start = getMBBStartIdx(Killer->getParent());
414 SlotIndex End = getInstructionIndex(Killer).getDefIndex();
415 DEBUG({
416 errs() << " Removing [" << Start << "," << End << "] from: ";
417 interval.print(errs(), tri_);
418 errs() << "\n";
419 });
420 interval.removeRange(Start, End);

--- 227 unchanged lines hidden (view full) ---

648 vni->setIsPHIDef(true);
649 LiveRange LR(start, end, vni);
650
651 interval.addRange(LR);
652 LR.valno->addKill(end);
653 DEBUG(errs() << " +" << LR << '\n');
654}
655
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
783/// computeIntervals - computes the live intervals for virtual
784/// registers. for some ordering of the machine instructions [1,N] a
785/// live interval is an interval [i, j) where 1 <= i <= j < N for
786/// which a variable is live
787void LiveIntervals::computeIntervals() {
788 DEBUG(errs() << "********** COMPUTING LIVE INTERVALS **********\n"
789 << "********** Function: "
790 << ((Value*)mf_->getFunction())->getName() << '\n');

--- 1411 unchanged lines hidden --- 		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 ---