Live interval splitting:

When a live interval is being spilled, rather than creating short, non-spillable
intervals for every def / use, split the interval at BB boundaries. That is, for
every BB where the live interval is defined or used, create a new interval that
covers all the defs and uses in the BB.

This is designed to eliminate one common problem: multiple reloads of the same
value in a single basic block. Note, it does *not* decrease the number of spills
since no copies are inserted so the split intervals are *connected* through
spill and reloads (or rematerialization). The newly created intervals can be
spilled again, in that case, since it does not span multiple basic blocks, it's
spilled in the usual manner. However, it can reuse the same stack slot as the
previously split interval.

This is currently controlled by -split-intervals-at-bb.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@44198 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 19 insertions, 6 deletions

diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index 16dff55..e4582f7 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -32,6 +32,7 @@
 namespace llvm {
 
   class LiveVariables;
+  class LoopInfo;
   class MRegisterInfo;
   class SSARegMap;
   class TargetInstrInfo;
@@ -104,8 +105,8 @@ namespace llvm {
       return getBaseIndex(index) + InstrSlots::STORE;
     }
 
-    static float getSpillWeight(const MachineOperand &mop, unsigned loopDepth) {
-      return (mop.isUse()+mop.isDef()) * powf(10.0F, (float)loopDepth);
+    static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
+      return (isDef + isUse) * powf(10.0F, (float)loopDepth);
     }
 
     typedef Reg2IntervalMap::iterator iterator;
@@ -229,7 +230,8 @@ namespace llvm {
     /// addIntervalsForSpills - Create new intervals for spilled defs / uses of
     /// the given interval.
     std::vector<LiveInterval*>
-      addIntervalsForSpills(const LiveInterval& i, VirtRegMap& vrm);
+    addIntervalsForSpills(const LiveInterval& i,
+                          const LoopInfo *loopInfo, VirtRegMap& vrm);
 
   private:      
     /// computeIntervals - Compute live intervals.
@@ -275,21 +277,32 @@ namespace llvm {
                               MachineInstr *DefMI, unsigned index, unsigned i,
                               bool isSS, int slot, unsigned reg);
 
+    bool anyKillInMBBAfterIdx(const LiveInterval &li,
+                              MachineBasicBlock *MBB, unsigned Idx,
+                              const VNInfo *VNI = NULL) const;
+
+    bool intervalIsInOneMBB(const LiveInterval &li) const;
+
     /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
     /// for addIntervalsForSpills to rewrite uses / defs for the given live range.
-    void rewriteInstructionForSpills(const LiveInterval &li,
+    void rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit,
         unsigned id, unsigned index, unsigned end, MachineInstr *MI,
         MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot,
         bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
         VirtRegMap &vrm, SSARegMap *RegMap, const TargetRegisterClass* rc,
         SmallVector<int, 4> &ReMatIds,
+        unsigned &NewVReg, bool &HasDef, bool &HasUse, const LoopInfo *loopInfo,
+        std::vector<unsigned> &NewVRegs,
         std::vector<LiveInterval*> &NewLIs);
-    void rewriteInstructionsForSpills(const LiveInterval &li,
+    void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
         LiveInterval::Ranges::const_iterator &I,
         MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot,
         bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
         VirtRegMap &vrm, SSARegMap *RegMap, const TargetRegisterClass* rc,
-        SmallVector<int, 4> &ReMatIds,
+        SmallVector<int, 4> &ReMatIds, const LoopInfo *loopInfo,
+        BitVector &SpillMBBs,
+        std::vector<std::pair<int, unsigned> > &SpillIdxes,
+        std::vector<unsigned> &NewVRegs,
         std::vector<LiveInterval*> &NewLIs);
 
     static LiveInterval createInterval(unsigned Reg);