From ec2bc645053e9051ada01fac6a555df17a85c91d Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Fri, 23 Jul 2004 08:24:23 +0000 Subject: [PATCH] Improve comments a bit Use an explicit LiveRange class to represent ranges instead of an std::pair. This is a minor cleanup, but is really intended to make a future patch simpler and less invasive. Alkis, could you please take a look at LiveInterval::liveAt? I suspect that you can add an operator<(unsigned) to LiveRange, allowing us to speed up the upper_bound call by quite a bit (this would also apply to other callers of upper/lower_bound). I would do it myself, but I still don't understand that crazy liveAt function, despite the comment. :) Basically I would like to see this: LiveRange dummy(index, index+1); Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), dummy); Turn into: Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), index); git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15130 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveIntervalAnalysis.h | 33 +++++-- lib/CodeGen/LiveIntervalAnalysis.cpp | 95 ++++++++++----------- lib/CodeGen/LiveIntervalAnalysis.h | 33 +++++-- 3 files changed, 101 insertions(+), 60 deletions(-) diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index a78aed186f4..a70deffdc16 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -29,9 +29,29 @@ namespace llvm { class MRegisterInfo; class VirtRegMap; + /// LiveRange structure - This represents a simple register range in the + /// program, with an inclusive start point and an exclusive end point. + /// These ranges are rendered as [start,end). + struct LiveRange { + unsigned start; // Start point of the interval (inclusive) + unsigned end; // End point of the interval (exclusive) + LiveRange(unsigned S, unsigned E) : start(S), end(E) { + assert(S < E && "Cannot create empty or backwards range"); + } + + bool operator<(const LiveRange &LR) const { + return start < LR.start || (start == LR.start && end < LR.end); + } + bool operator==(const LiveRange &LR) const { + return start == LR.start && end == LR.end; + } + private: + LiveRange(); // DO NOT IMPLEMENT + }; + std::ostream& operator<<(std::ostream& os, const LiveRange &LR); + struct LiveInterval { - typedef std::pair Range; - typedef std::vector Ranges; + typedef std::vector Ranges; unsigned reg; // the register of this interval float weight; // weight of this interval: // (number of uses *10^loopDepth) @@ -44,14 +64,17 @@ namespace llvm { bool spilled() const; + /// start - Return the lowest numbered slot covered by interval. unsigned start() const { assert(!empty() && "empty interval for register"); - return ranges.front().first; + return ranges.front().start; } + /// end - return the maximum point of the interval of the whole, + /// exclusive. unsigned end() const { assert(!empty() && "empty interval for register"); - return ranges.back().second; + return ranges.back().end; } bool expiredAt(unsigned index) const { @@ -62,7 +85,7 @@ namespace llvm { bool overlaps(const LiveInterval& other) const; - void addRange(unsigned start, unsigned end); + void addRange(LiveRange R); void join(const LiveInterval& other); diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 4e5b1804475..d59c114808c 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -194,8 +194,8 @@ std::vector LiveIntervals::addIntervalsForSpills( for (LiveInterval::Ranges::const_iterator i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { - unsigned index = getBaseIndex(i->first); - unsigned end = getBaseIndex(i->second-1) + InstrSlots::NUM; + unsigned index = getBaseIndex(i->start); + unsigned end = getBaseIndex(i->end-1) + InstrSlots::NUM; for (; index != end; index += InstrSlots::NUM) { // skip deleted instructions while (index != end && !getInstructionFromIndex(index)) @@ -250,7 +250,7 @@ std::vector LiveIntervals::addIntervalsForSpills( // the spill weight is now infinity as it // cannot be spilled again nI.weight = HUGE_VAL; - nI.addRange(start, end); + nI.addRange(LiveRange(start, end)); added.push_back(&nI); // update live variables lv_->addVirtualRegisterKilled(nReg, mi); @@ -308,7 +308,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, if (killIdx > defIndex) { assert(vi.AliveBlocks.empty() && "Shouldn't be alive across any blocks!"); - interval.addRange(defIndex, killIdx); + interval.addRange(LiveRange(defIndex, killIdx)); DEBUG(std::cerr << "\n"); return; } @@ -318,8 +318,9 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, // of the defining block, potentially live across some blocks, then is // live into some number of blocks, but gets killed. Start by adding a // range that goes from this definition to the end of the defining block. - interval.addRange(defIndex, - getInstructionIndex(&mbb->back()) + InstrSlots::NUM); + interval.addRange(LiveRange(defIndex, + getInstructionIndex(&mbb->back()) + + InstrSlots::NUM)); // Iterate over all of the blocks that the variable is completely // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the @@ -328,9 +329,9 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, if (vi.AliveBlocks[i]) { MachineBasicBlock* mbb = mf_->getBlockNumbered(i); if (!mbb->empty()) { - interval.addRange( + interval.addRange(LiveRange( getInstructionIndex(&mbb->front()), - getInstructionIndex(&mbb->back()) + InstrSlots::NUM); + getInstructionIndex(&mbb->back()) + InstrSlots::NUM)); } } } @@ -339,8 +340,9 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, // block to the 'use' slot of the killing instruction. for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { MachineInstr *Kill = vi.Kills[i]; - interval.addRange(getInstructionIndex(Kill->getParent()->begin()), - getUseIndex(getInstructionIndex(Kill))+1); + interval.addRange(LiveRange( + getInstructionIndex(Kill->getParent()->begin()), + getUseIndex(getInstructionIndex(Kill))+1)); } } else { @@ -357,8 +359,8 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, // the defined value will be live until the end of the basic block it // is defined in. unsigned defIndex = getDefIndex(getInstructionIndex(mi)); - interval.addRange(defIndex, - getInstructionIndex(&mbb->back()) + InstrSlots::NUM); + interval.addRange(LiveRange(defIndex, + getInstructionIndex(&mbb->back()) +InstrSlots::NUM)); } interval.isDefinedOnce = false; } @@ -410,7 +412,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, exit: assert(start < end && "did not find end of interval?"); - interval.addRange(start, end); + interval.addRange(LiveRange(start, end)); DEBUG(std::cerr << '\n'); } @@ -682,7 +684,7 @@ bool LiveInterval::spilled() const // bool LiveInterval::liveAt(unsigned index) const { - Range dummy(index, index+1); + LiveRange dummy(index, index+1); Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), dummy); @@ -690,7 +692,7 @@ bool LiveInterval::liveAt(unsigned index) const return false; --r; - return index >= r->first && index < r->second; + return index >= r->start && index < r->end; } // An example for overlaps(): @@ -713,50 +715,39 @@ bool LiveInterval::overlaps(const LiveInterval& other) const Ranges::const_iterator ie = ranges.end(); Ranges::const_iterator j = other.ranges.begin(); Ranges::const_iterator je = other.ranges.end(); - if (i->first < j->first) { + if (i->start < j->start) { i = std::upper_bound(i, ie, *j); if (i != ranges.begin()) --i; } - else if (j->first < i->first) { + else if (j->start < i->start) { j = std::upper_bound(j, je, *i); if (j != other.ranges.begin()) --j; } while (i != ie && j != je) { - if (i->first == j->first) { + if (i->start == j->start) return true; - } - else { - if (i->first > j->first) { - swap(i, j); - swap(ie, je); - } - assert(i->first < j->first); - if (i->second > j->first) { - return true; - } - else { - ++i; - } + if (i->start > j->start) { + swap(i, j); + swap(ie, je); } + assert(i->start < j->start); + + if (i->end > j->start) + return true; + ++i; } return false; } -void LiveInterval::addRange(unsigned start, unsigned end) -{ - assert(start < end && "Invalid range to add!"); - DEBUG(std::cerr << " +[" << start << ',' << end << ")"); - //assert(start < end && "invalid range?"); - Range range = std::make_pair(start, end); +void LiveInterval::addRange(LiveRange LR) { + DEBUG(std::cerr << " +" << LR); Ranges::iterator it = - ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range), - range); + ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), LR), LR); - it = mergeRangesForward(it); - it = mergeRangesBackward(it); + mergeRangesBackward(mergeRangesForward(it)); } void LiveInterval::join(const LiveInterval& other) @@ -779,9 +770,9 @@ mergeRangesForward(Ranges::iterator it) { Ranges::iterator n; while ((n = next(it)) != ranges.end()) { - if (n->first > it->second) + if (n->start > it->end) break; - it->second = std::max(it->second, n->second); + it->end = std::max(it->end, n->end); n = ranges.erase(n); } return it; @@ -792,17 +783,22 @@ mergeRangesBackward(Ranges::iterator it) { while (it != ranges.begin()) { Ranges::iterator p = prior(it); - if (it->first > p->second) + if (it->start > p->end) break; - it->first = std::min(it->first, p->first); - it->second = std::max(it->second, p->second); + it->start = std::min(it->start, p->start); + it->end = std::max(it->end, p->end); it = ranges.erase(p); } return it; } +std::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) { + return os << "[" << LR.start << "," << LR.end << ")"; +} + + std::ostream& llvm::operator<<(std::ostream& os, const LiveInterval& li) { os << "%reg" << li.reg << ',' << li.weight; @@ -810,9 +806,8 @@ std::ostream& llvm::operator<<(std::ostream& os, const LiveInterval& li) return os << "EMPTY"; os << " = "; - for (LiveInterval::Ranges::const_iterator - i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { - os << "[" << i->first << "," << i->second << ")"; - } + for (LiveInterval::Ranges::const_iterator i = li.ranges.begin(), + e = li.ranges.end(); i != e; ++i) + os << *i; return os; } diff --git a/lib/CodeGen/LiveIntervalAnalysis.h b/lib/CodeGen/LiveIntervalAnalysis.h index a78aed186f4..a70deffdc16 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.h +++ b/lib/CodeGen/LiveIntervalAnalysis.h @@ -29,9 +29,29 @@ namespace llvm { class MRegisterInfo; class VirtRegMap; + /// LiveRange structure - This represents a simple register range in the + /// program, with an inclusive start point and an exclusive end point. + /// These ranges are rendered as [start,end). + struct LiveRange { + unsigned start; // Start point of the interval (inclusive) + unsigned end; // End point of the interval (exclusive) + LiveRange(unsigned S, unsigned E) : start(S), end(E) { + assert(S < E && "Cannot create empty or backwards range"); + } + + bool operator<(const LiveRange &LR) const { + return start < LR.start || (start == LR.start && end < LR.end); + } + bool operator==(const LiveRange &LR) const { + return start == LR.start && end == LR.end; + } + private: + LiveRange(); // DO NOT IMPLEMENT + }; + std::ostream& operator<<(std::ostream& os, const LiveRange &LR); + struct LiveInterval { - typedef std::pair Range; - typedef std::vector Ranges; + typedef std::vector Ranges; unsigned reg; // the register of this interval float weight; // weight of this interval: // (number of uses *10^loopDepth) @@ -44,14 +64,17 @@ namespace llvm { bool spilled() const; + /// start - Return the lowest numbered slot covered by interval. unsigned start() const { assert(!empty() && "empty interval for register"); - return ranges.front().first; + return ranges.front().start; } + /// end - return the maximum point of the interval of the whole, + /// exclusive. unsigned end() const { assert(!empty() && "empty interval for register"); - return ranges.back().second; + return ranges.back().end; } bool expiredAt(unsigned index) const { @@ -62,7 +85,7 @@ namespace llvm { bool overlaps(const LiveInterval& other) const; - void addRange(unsigned start, unsigned end); + void addRange(LiveRange R); void join(const LiveInterval& other); -- 2.34.1