From dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8 Mon Sep 17 00:00:00 2001 From: Alkis Evlogimenos Date: Thu, 18 Dec 2003 08:48:48 +0000 Subject: [PATCH] Handle multiple virtual register definitions gracefully. Move some of the longer LiveIntervals::Interval method out of the header and add debug information to them. Fix bug and simplify range merging code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10509 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveIntervalAnalysis.h | 51 +-------- include/llvm/CodeGen/LiveIntervals.h | 51 +-------- lib/CodeGen/LiveIntervalAnalysis.cpp | 118 +++++++++++--------- lib/CodeGen/LiveIntervalAnalysis.h | 51 +-------- 4 files changed, 79 insertions(+), 192 deletions(-) diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 2be89fda5bd..54b5ca3fee3 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -59,55 +59,12 @@ namespace llvm { return end() <= index; } - bool overlaps(unsigned index) const { - for (Ranges::const_iterator - i = ranges.begin(), e = ranges.end(); i != e; ++i) { - if (index >= i->first && index < i->second) { - return true; - } - } - return false; - } - - void addRange(unsigned start, unsigned end) { - Range range = std::make_pair(start, end); - Ranges::iterator it = - std::lower_bound(ranges.begin(), ranges.end(), range); - - if (it == ranges.end()) { - it = ranges.insert(it, range); - goto exit; - } - - assert(range.first <= it->first && "got wrong iterator?"); - // merge ranges if necesary - if (range.first < it->first) { - if (range.second >= it->first) { - it->first = range.first; - } - else { - it = ranges.insert(it, range); - assert(it != ranges.end() && "wtf?"); - goto exit; - } - } - - exit: - mergeRangesIfNecessary(it); - } + void addRange(unsigned start, unsigned end); private: - void mergeRangesIfNecessary(Ranges::iterator it) { - while (it != ranges.begin()) { - Ranges::iterator prev = it - 1; - if (prev->second < it->first) { - break; - } - prev->second = it->second; - ranges.erase(it); - it = prev; - } - } + void mergeRangesForward(Ranges::iterator it); + + void mergeRangesBackward(Ranges::iterator it); }; struct StartPointComp { diff --git a/include/llvm/CodeGen/LiveIntervals.h b/include/llvm/CodeGen/LiveIntervals.h index 2be89fda5bd..54b5ca3fee3 100644 --- a/include/llvm/CodeGen/LiveIntervals.h +++ b/include/llvm/CodeGen/LiveIntervals.h @@ -59,55 +59,12 @@ namespace llvm { return end() <= index; } - bool overlaps(unsigned index) const { - for (Ranges::const_iterator - i = ranges.begin(), e = ranges.end(); i != e; ++i) { - if (index >= i->first && index < i->second) { - return true; - } - } - return false; - } - - void addRange(unsigned start, unsigned end) { - Range range = std::make_pair(start, end); - Ranges::iterator it = - std::lower_bound(ranges.begin(), ranges.end(), range); - - if (it == ranges.end()) { - it = ranges.insert(it, range); - goto exit; - } - - assert(range.first <= it->first && "got wrong iterator?"); - // merge ranges if necesary - if (range.first < it->first) { - if (range.second >= it->first) { - it->first = range.first; - } - else { - it = ranges.insert(it, range); - assert(it != ranges.end() && "wtf?"); - goto exit; - } - } - - exit: - mergeRangesIfNecessary(it); - } + void addRange(unsigned start, unsigned end); private: - void mergeRangesIfNecessary(Ranges::iterator it) { - while (it != ranges.begin()) { - Ranges::iterator prev = it - 1; - if (prev->second < it->first) { - break; - } - prev->second = it->second; - ranges.erase(it); - it = prev; - } - } + void mergeRangesForward(Ranges::iterator it); + + void mergeRangesBackward(Ranges::iterator it); }; struct StartPointComp { diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 2bd9fabb81e..564d9cd384a 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -122,60 +122,46 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, LiveVariables::VarInfo& vi = lv_->getVarInfo(reg); + Interval* interval = 0; Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); - // handle multiple definition case (machine instructions violating - // ssa after phi-elimination - if (r2iit != r2iMap_.end()) { - unsigned ii = r2iit->second; - Interval& interval = intervals_[ii]; - unsigned end = getInstructionIndex(mbb->back()) + 1; - DEBUG(std::cerr << "\t\t\t\tadding range: [" - << instrIndex << ',' << end << "]\n"); - interval.addRange(instrIndex, end); - DEBUG(std::cerr << "\t\t\t\t" << interval << '\n'); - } - else { + if (r2iit == r2iMap_.end()) { // add new interval intervals_.push_back(Interval(reg)); - Interval& interval = intervals_.back(); // update interval index for this register r2iMap_[reg] = intervals_.size() - 1; + interval = &intervals_.back(); + } + else { + interval = &intervals_[r2iit->second]; + } - for (MbbIndex2MbbMap::iterator - it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); - it != itEnd; ++it) { - unsigned liveBlockIndex = it->first; - MachineBasicBlock* liveBlock = it->second; - if (liveBlockIndex < vi.AliveBlocks.size() && - vi.AliveBlocks[liveBlockIndex]) { - unsigned start = getInstructionIndex(liveBlock->front()); - unsigned end = getInstructionIndex(liveBlock->back()) + 1; - DEBUG(std::cerr << "\t\t\t\tadding range: [" - << start << ',' << end << "]\n"); - interval.addRange(start, end); - } - } - - bool killedInDefiningBasicBlock = false; - for (int i = 0, e = vi.Kills.size(); i != e; ++i) { - MachineBasicBlock* killerBlock = vi.Kills[i].first; - MachineInstr* killerInstr = vi.Kills[i].second; - killedInDefiningBasicBlock |= mbb == killerBlock; - unsigned start = (mbb == killerBlock ? - instrIndex : - getInstructionIndex(killerBlock->front())); - unsigned end = getInstructionIndex(killerInstr) + 1; - DEBUG(std::cerr << "\t\t\t\tadding range: [" - << start << ',' << end << "]\n"); - interval.addRange(start, end); + for (MbbIndex2MbbMap::iterator + it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); + it != itEnd; ++it) { + unsigned liveBlockIndex = it->first; + MachineBasicBlock* liveBlock = it->second; + if (liveBlockIndex < vi.AliveBlocks.size() && + vi.AliveBlocks[liveBlockIndex]) { + unsigned start = getInstructionIndex(liveBlock->front()); + unsigned end = getInstructionIndex(liveBlock->back()) + 1; + interval->addRange(start, end); } + } - if (!killedInDefiningBasicBlock) { - unsigned end = getInstructionIndex(mbb->back()) + 1; - interval.addRange(instrIndex, end); - } + bool killedInDefiningBasicBlock = false; + for (int i = 0, e = vi.Kills.size(); i != e; ++i) { + MachineBasicBlock* killerBlock = vi.Kills[i].first; + MachineInstr* killerInstr = vi.Kills[i].second; + killedInDefiningBasicBlock |= mbb == killerBlock; + unsigned start = (mbb == killerBlock ? + instrIndex : + getInstructionIndex(killerBlock->front())); + unsigned end = getInstructionIndex(killerInstr) + 1; + } - DEBUG(std::cerr << "\t\t\t\t" << interval << '\n'); + if (!killedInDefiningBasicBlock) { + unsigned end = getInstructionIndex(mbb->back()) + 1; + interval->addRange(instrIndex, end); } } @@ -220,20 +206,14 @@ exit: if (r2iit != r2iMap_.end()) { unsigned ii = r2iit->second; Interval& interval = intervals_[ii]; - DEBUG(std::cerr << "\t\t\t\tadding range: [" - << start << ',' << end << "]\n"); interval.addRange(start, end); - DEBUG(std::cerr << "\t\t\t\t" << interval << '\n'); } else { intervals_.push_back(Interval(reg)); Interval& interval = intervals_.back(); // update interval index for this register r2iMap_[reg] = intervals_.size() - 1; - DEBUG(std::cerr << "\t\t\t\tadding range: [" - << start << ',' << end << "]\n"); interval.addRange(start, end); - DEBUG(std::cerr << "\t\t\t\t" << interval << '\n'); } } @@ -310,6 +290,42 @@ void LiveIntervals::computeIntervals() std::ostream_iterator(std::cerr, "\n"))); } +void LiveIntervals::Interval::addRange(unsigned start, unsigned end) +{ + DEBUG(std::cerr << "\t\t\t\tadding range: [" << start <<','<< end << "]\n"); + //assert(start < end && "invalid range?"); + Range range = std::make_pair(start, end); + Ranges::iterator it = + ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range), + range); + + DEBUG(std::cerr << "\t\t\t\tbefore merge forward: " << *this << '\n'); + mergeRangesForward(it); + DEBUG(std::cerr << "\t\t\t\tbefore merge backward: " << *this << '\n'); + mergeRangesBackward(it); + DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); +} + +void LiveIntervals::Interval::mergeRangesForward(Ranges::iterator it) +{ + for (Ranges::iterator next = it + 1; + next != ranges.end() && it->second >= next->first; ) { + it->second = std::max(it->second, next->second); + next = ranges.erase(next); + } +} + +void LiveIntervals::Interval::mergeRangesBackward(Ranges::iterator it) +{ + for (Ranges::iterator prev = it - 1; + it != ranges.begin() && it->first <= prev->second; ) { + it->first = std::min(it->first, prev->first); + it->second = std::max(it->second, prev->second); + it = ranges.erase(prev); + prev = it - 1; + } +} + std::ostream& llvm::operator<<(std::ostream& os, const LiveIntervals::Interval& li) { diff --git a/lib/CodeGen/LiveIntervalAnalysis.h b/lib/CodeGen/LiveIntervalAnalysis.h index 2be89fda5bd..54b5ca3fee3 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.h +++ b/lib/CodeGen/LiveIntervalAnalysis.h @@ -59,55 +59,12 @@ namespace llvm { return end() <= index; } - bool overlaps(unsigned index) const { - for (Ranges::const_iterator - i = ranges.begin(), e = ranges.end(); i != e; ++i) { - if (index >= i->first && index < i->second) { - return true; - } - } - return false; - } - - void addRange(unsigned start, unsigned end) { - Range range = std::make_pair(start, end); - Ranges::iterator it = - std::lower_bound(ranges.begin(), ranges.end(), range); - - if (it == ranges.end()) { - it = ranges.insert(it, range); - goto exit; - } - - assert(range.first <= it->first && "got wrong iterator?"); - // merge ranges if necesary - if (range.first < it->first) { - if (range.second >= it->first) { - it->first = range.first; - } - else { - it = ranges.insert(it, range); - assert(it != ranges.end() && "wtf?"); - goto exit; - } - } - - exit: - mergeRangesIfNecessary(it); - } + void addRange(unsigned start, unsigned end); private: - void mergeRangesIfNecessary(Ranges::iterator it) { - while (it != ranges.begin()) { - Ranges::iterator prev = it - 1; - if (prev->second < it->first) { - break; - } - prev->second = it->second; - ranges.erase(it); - it = prev; - } - } + void mergeRangesForward(Ranges::iterator it); + + void mergeRangesBackward(Ranges::iterator it); }; struct StartPointComp { -- 2.34.1