+ raw_ostream &operator<<(raw_ostream &OS, const LiveRange::Segment &S);
+
+ inline bool operator<(SlotIndex V, const LiveRange::Segment &S) {
+ return V < S.start;
+ }
+
+ inline bool operator<(const LiveRange::Segment &S, SlotIndex V) {
+ return S.start < V;
+ }
+
+ /// Helper class for performant LiveRange bulk updates.
+ ///
+ /// Calling LiveRange::addSegment() repeatedly can be expensive on large
+ /// live ranges because segments after the insertion point may need to be
+ /// shifted. The LiveRangeUpdater class can defer the shifting when adding
+ /// many segments in order.
+ ///
+ /// The LiveRange will be in an invalid state until flush() is called.
+ class LiveRangeUpdater {
+ LiveRange *LR;
+ SlotIndex LastStart;
+ LiveRange::iterator WriteI;
+ LiveRange::iterator ReadI;
+ SmallVector<LiveRange::Segment, 16> Spills;
+ void mergeSpills();
+
+ public:
+ /// Create a LiveRangeUpdater for adding segments to LR.
+ /// LR will temporarily be in an invalid state until flush() is called.
+ LiveRangeUpdater(LiveRange *lr = 0) : LR(lr) {}
+
+ ~LiveRangeUpdater() { flush(); }
+
+ /// Add a segment to LR and coalesce when possible, just like
+ /// LR.addSegment(). Segments should be added in increasing start order for
+ /// best performance.
+ void add(LiveRange::Segment);
+
+ void add(SlotIndex Start, SlotIndex End, VNInfo *VNI) {
+ add(LiveRange::Segment(Start, End, VNI));
+ }
+
+ /// Return true if the LR is currently in an invalid state, and flush()
+ /// needs to be called.
+ bool isDirty() const { return LastStart.isValid(); }
+
+ /// Flush the updater state to LR so it is valid and contains all added
+ /// segments.
+ void flush();
+
+ /// Select a different destination live range.
+ void setDest(LiveRange *lr) {
+ if (LR != lr && isDirty())
+ flush();
+ LR = lr;
+ }
+
+ /// Get the current destination live range.
+ LiveRange *getDest() const { return LR; }
+
+ void dump() const;
+ void print(raw_ostream&) const;
+ };
+
+ inline raw_ostream &operator<<(raw_ostream &OS, const LiveRangeUpdater &X) {
+ X.print(OS);
+ return OS;
+ }
+
+ /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a
+ /// LiveInterval into equivalence clases of connected components. A
+ /// LiveInterval that has multiple connected components can be broken into
+ /// multiple LiveIntervals.
+ ///
+ /// Given a LiveInterval that may have multiple connected components, run:
+ ///
+ /// unsigned numComps = ConEQ.Classify(LI);
+ /// if (numComps > 1) {
+ /// // allocate numComps-1 new LiveIntervals into LIS[1..]
+ /// ConEQ.Distribute(LIS);
+ /// }
+
+ class ConnectedVNInfoEqClasses {
+ LiveIntervals &LIS;
+ IntEqClasses EqClass;
+
+ // Note that values a and b are connected.
+ void Connect(unsigned a, unsigned b);
+
+ unsigned Renumber();
+
+ public:
+ explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {}
+
+ /// Classify - Classify the values in LI into connected components.
+ /// Return the number of connected components.
+ unsigned Classify(const LiveInterval *LI);
+
+ /// getEqClass - Classify creates equivalence classes numbered 0..N. Return
+ /// the equivalence class assigned the VNI.
+ unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; }
+
+ /// Distribute - Distribute values in LIV[0] into a separate LiveInterval
+ /// for each connected component. LIV must have a LiveInterval for each
+ /// connected component. The LiveIntervals in Liv[1..] must be empty.
+ /// Instructions using LIV[0] are rewritten.
+ void Distribute(LiveInterval *LIV[], MachineRegisterInfo &MRI);
+
+ };
+
+}