X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveIntervalAnalysis.h;h=a94840e89621a39bdb4a9f16ddd2adbca854769f;hb=5eca075b74d62c621b160aa216b4cd50829a2cc7;hp=32f157f0c1d2b9a17310b2ce6afb3d8638b69363;hpb=a6fb5b54f3a35fdefbb03b9c7be4c6d6d53cdd35;p=oota-llvm.git

diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index 32f157f0c1d..a94840e8962 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -28,10 +28,10 @@
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Allocator.h"
 #include <cmath>
-#include <map>
 
 namespace llvm {
 
+  class AliasAnalysis;
   class LiveVariables;
   class MachineLoopInfo;
   class TargetRegisterInfo;
@@ -54,6 +54,20 @@ namespace llvm {
       return LHS.first < RHS.first;
     }
   };
+  
+  // Provide DenseMapInfo for unsigned.
+  template<>
+  struct DenseMapInfo<unsigned> {
+    static inline unsigned getEmptyKey() { return (unsigned)-1; }
+    static inline unsigned getTombstoneKey() { return (unsigned)-2; }
+    static unsigned getHashValue(const unsigned Val) {
+      return Val * 37;
+    }
+    static bool isEqual(const unsigned LHS, const unsigned RHS) {
+      return LHS == RHS;
+    }
+    static bool isPod() { return true; }
+  };
 
   class LiveIntervals : public MachineFunctionPass {
     MachineFunction* mf_;
@@ -61,6 +75,7 @@ namespace llvm {
     const TargetMachine* tm_;
     const TargetRegisterInfo* tri_;
     const TargetInstrInfo* tii_;
+    AliasAnalysis *aa_;
     LiveVariables* lv_;
 
     /// Special pool allocator for VNInfo's (LiveInterval val#).
@@ -75,13 +90,16 @@ namespace llvm {
     /// and MBB id.
     std::vector<IdxMBBPair> Idx2MBBMap;
 
-    typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
+    /// FunctionSize - The number of instructions present in the function
+    uint64_t FunctionSize;
+
+    typedef DenseMap<MachineInstr*, unsigned> Mi2IndexMap;
     Mi2IndexMap mi2iMap_;
 
     typedef std::vector<MachineInstr*> Index2MiMap;
     Index2MiMap i2miMap_;
 
-    typedef std::map<unsigned, LiveInterval> Reg2IntervalMap;
+    typedef DenseMap<unsigned, LiveInterval*> Reg2IntervalMap;
     Reg2IntervalMap r2iMap_;
 
     BitVector allocatableRegs_;
@@ -136,13 +154,13 @@ namespace llvm {
     LiveInterval &getInterval(unsigned reg) {
       Reg2IntervalMap::iterator I = r2iMap_.find(reg);
       assert(I != r2iMap_.end() && "Interval does not exist for register");
-      return I->second;
+      return *I->second;
     }
 
     const LiveInterval &getInterval(unsigned reg) const {
       Reg2IntervalMap::const_iterator I = r2iMap_.find(reg);
       assert(I != r2iMap_.end() && "Interval does not exist for register");
-      return I->second;
+      return *I->second;
     }
 
     bool hasInterval(unsigned reg) const {
@@ -169,13 +187,18 @@ namespace llvm {
       return MBB2IdxMap[MBBNo].second;
     }
 
-    /// getIntervalSize - get the size of an interval in "units,"
+    /// getScaledIntervalSize - get the size of an interval in "units,"
     /// where every function is composed of one thousand units.  This
     /// measure scales properly with empty index slots in the function.
-    unsigned getScaledIntervalSize(LiveInterval& I) const {
-      // Factor of 250 comes from 1000 units per function divided
-      // by four slots per instruction.
-      return (1000 / InstrSlots::NUM * I.getSize()) / i2miMap_.size();
+    double getScaledIntervalSize(LiveInterval& I) {
+      return (1000.0 / InstrSlots::NUM * I.getSize()) / i2miMap_.size();
+    }
+    
+    /// getApproximateInstructionCount - computes an estimate of the number
+    /// of instructions in a given LiveInterval.
+    unsigned getApproximateInstructionCount(LiveInterval& I) {
+      double IntervalPercentage = getScaledIntervalSize(I) / 1000.0;
+      return (unsigned)(IntervalPercentage * FunctionSize);
     }
 
     /// getMBBFromIndex - given an index in any instruction of an
@@ -217,7 +240,7 @@ namespace llvm {
 
     /// findLiveInMBBs - Given a live range, if the value of the range
     /// is live in any MBB returns true as well as the list of basic blocks
-    /// where the value is live in.
+    /// in which the value is live.
     bool findLiveInMBBs(const LiveRange &LR,
                         SmallVectorImpl<MachineBasicBlock*> &MBBs) const;
 
@@ -226,8 +249,8 @@ namespace llvm {
     LiveInterval &getOrCreateInterval(unsigned reg) {
       Reg2IntervalMap::iterator I = r2iMap_.find(reg);
       if (I == r2iMap_.end())
-        I = r2iMap_.insert(I, std::make_pair(reg, createInterval(reg)));
-      return I->second;
+        I = r2iMap_.insert(std::make_pair(reg, createInterval(reg))).first;
+      return *I->second;
     }
     
     /// addLiveRangeToEndOfBlock - Given a register and an instruction,
@@ -238,7 +261,9 @@ namespace llvm {
     // Interval removal
 
     void removeInterval(unsigned Reg) {
-      r2iMap_.erase(Reg);
+      DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.find(Reg);
+      delete I->second;
+      r2iMap_.erase(I);
     }
 
     /// isRemoved - returns true if the specified machine instr has been
@@ -330,20 +355,20 @@ namespace llvm {
     /// handleVirtualRegisterDef)
     void handleRegisterDef(MachineBasicBlock *MBB,
                            MachineBasicBlock::iterator MI, unsigned MIIdx,
-                           unsigned reg);
+                           MachineOperand& MO, unsigned MOIdx);
 
     /// handleVirtualRegisterDef - update intervals for a virtual
     /// register def
     void handleVirtualRegisterDef(MachineBasicBlock *MBB,
                                   MachineBasicBlock::iterator MI,
-                                  unsigned MIIdx,
-                                  LiveInterval& interval);
+                                  unsigned MIIdx, MachineOperand& MO,
+                                  unsigned MOIdx, LiveInterval& interval);
 
     /// handlePhysicalRegisterDef - update intervals for a physical register
     /// def.
     void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
                                    MachineBasicBlock::iterator mi,
-                                   unsigned MIIdx,
+                                   unsigned MIIdx, MachineOperand& MO,
                                    LiveInterval &interval,
                                    MachineInstr *CopyMI);
 
@@ -408,10 +433,10 @@ namespace llvm {
 
     bool alsoFoldARestore(int Id, int index, unsigned vr,
                           BitVector &RestoreMBBs,
-                          std::map<unsigned,std::vector<SRInfo> >&RestoreIdxes);
+                          DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
     void eraseRestoreInfo(int Id, int index, unsigned vr,
                           BitVector &RestoreMBBs,
-                          std::map<unsigned,std::vector<SRInfo> >&RestoreIdxes);
+                          DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
 
     /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
     /// spilled and create empty intervals for their uses.
@@ -434,7 +459,7 @@ namespace llvm {
         VirtRegMap &vrm, const TargetRegisterClass* rc,
         SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo,
         unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
-        std::map<unsigned,unsigned> &MBBVRegsMap,
+        DenseMap<unsigned,unsigned> &MBBVRegsMap,
         std::vector<LiveInterval*> &NewLIs, float &SSWeight);
     void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
         LiveInterval::Ranges::const_iterator &I,
@@ -443,13 +468,13 @@ namespace llvm {
         VirtRegMap &vrm, const TargetRegisterClass* rc,
         SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo,
         BitVector &SpillMBBs,
-        std::map<unsigned,std::vector<SRInfo> > &SpillIdxes,
+        DenseMap<unsigned,std::vector<SRInfo> > &SpillIdxes,
         BitVector &RestoreMBBs,
-        std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes,
-        std::map<unsigned,unsigned> &MBBVRegsMap,
+        DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes,
+        DenseMap<unsigned,unsigned> &MBBVRegsMap,
         std::vector<LiveInterval*> &NewLIs, float &SSWeight);
 
-    static LiveInterval createInterval(unsigned Reg);
+    static LiveInterval* createInterval(unsigned Reg);
 
     void printRegName(unsigned reg) const;
   };