LV info on machine instructions

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

4 files changed, 93 insertions, 62 deletions

diff --git a/include/llvm/Analysis/LiveVar/FunctionLiveVarInfo.h b/include/llvm/Analysis/LiveVar/FunctionLiveVarInfo.h
index 206fef8..c148d0c 100644
--- a/include/llvm/Analysis/LiveVar/FunctionLiveVarInfo.h
+++ b/include/llvm/Analysis/LiveVar/FunctionLiveVarInfo.h
@@ -3,36 +3,48 @@
    Date:    Jun 30, 01
    Purpose: 
 
-   This is the interface for live variable info of a method that is required by 
-   any other part of the compiler
+   This is the interface for live variable info of a method that is required 
+   by any other part of the compiler
 
-   It should be called like:
+   It must be called like:
 
        MethodLiveVarInfo MLVI( Mehtod *);  // initializes data structures
-       MLVI.analyze();                    // do the actural live variable anal
+       MLVI.analyze();                     // do the actural live variable anal
 
  After the analysis, getInSetOfBB or getOutSetofBB can be called to get 
- live var info of a BB
+ live var info of a BB.
 
- The live var set before an instruction can be constructed in several ways:
+ The live var set before an instruction can be obtained in 2 ways:
 
- 1. Use the OutSet and applyTranferFuncForInst(const Instruction *const Inst) 
+ 1. Use the method getLiveVarSetAfterInst(Instruction *) to get the LV Info 
+    just after an instruction. (also exists getLiveVarSetBeforeInst(..))
+
+    This function caluclates the LV info for a BB only once and caches that 
+    info. If the cache does not contain the LV info of the instruction, it 
+    calculates the LV info for the whole BB and caches them.
+
+    Getting liveVar info this way uses more memory since, LV info should be 
+    cached. However, if you need LV info of nearly all the instructions of a
+    BB, this is the best and simplest interfrace.
+
+
+ 2. Use the OutSet and applyTranferFuncForInst(const Instruction *const Inst) 
     declared in LiveVarSet and  traverse the instructions of a basic block in 
     reverse (using const_reverse_iterator in the BB class). 
 
-    This is the most efficient method if you need LV info for several (all) 
-    instructions in a BasicBlock. An example is given below:
+    This is the most memory efficient method if you need LV info for 
+    only several instructions in a BasicBlock. An example is given below:
 
 
     LiveVarSet LVSet;  // this will be the set used to traverse through each BB
 
-                   // Initialize LVSet so that it is the same as OutSet of the BB
+    // Initialize LVSet so that it is the same as OutSet of the BB
     LVSet.setUnion( LVI->getOutSetOfBB( *BBI ) );  
  
     BasicBlock::InstListType::const_reverse_iterator 
-      InstIterator = InstListInBB.rbegin();  // get the reverse it for inst in BB
+      InstIterator = InstListInBB.rbegin(); // get the rev iter for inst in BB
 
-                            // iterate over all the instructions in BB in reverse
+      // iterate over all the instructions in BB in reverse
     for( ; InstIterator != InstListInBB.rend(); InstIterator++) {  
 
       //...... all  code here which uses LVSet ........
@@ -45,28 +57,16 @@
     See buildInterferenceGraph() for the above example.
 
 
- 2. Use the function getLiveVarSetBeforeInst(Instruction *) to get the LV Info 
-    just before an instruction.
-
-    This function caluclates the LV info for a BB only once and caches that 
-    info. If the cache does not contain the LV info of the instruction, it 
-    calculates the LV info for the whole BB and caches them.
-
-    Getting liveVar info this way uses more memory since, LV info should be 
-    cached.
-
-
- **BUGS: Cannot be called on a method prototype because the BB front() 
-   iterator causes a seg fault in CFG.h (Chris will fix this)
-   So, currently, DO NOT call this for method prototypes. 
-
 */
 
 
 #ifndef METH_LIVE_VAR_INFO_H
 #define METH_LIVE_VAR_INFO_H
 
-        // for printing out debug messages
+// set DEBUG_LV for printing out debug messages
+// if DEBUG_LV is 1 normal output messages
+// if DEBUG_LV is 2 extensive debug info for each instr
+
 #define DEBUG_LV (1)
 
 #include "LiveVarSet.h"
@@ -82,38 +82,65 @@
 class MethodLiveVarInfo
 {
  private:
-  const Method *Meth;   // Live var anal is done on this method 
-                        // set by constructor
 
-  BBToBBLiveVarMapType  BB2BBLVMap;  // A map betwn the BasicBlock and BBLiveVar
+  // Live var anal is done on this method - set by constructor
+  const Method *const Meth;   
+
+  // A map betwn the BasicBlock and BBLiveVar
+  BBToBBLiveVarMapType  BB2BBLVMap;  
+
+  // Machine Instr to LiveVarSet Map for providing LVset BEFORE each inst
+  MInstToLiveVarSetMapType MInst2LVSetBI; 
+
+  // Machine Instr to LiveVarSet Map for providing LVset AFTER each inst
+  MInstToLiveVarSetMapType MInst2LVSetAI; 
 
-  InstToLiveVarSetMapType Inst2LVSetMap; // Instruction to LiveVarSet Map 
-                                         //- for providing LV info for each inst
+  // True if the analyze() method has been called. This is checked when
+  // getInSet/OutSet is called to prevent calling those methods before analyze
+  bool HasAnalyzed;
 
-  void constructBBs();          // constructs BBLiveVars and init Def and In sets
-  bool  doSingleBackwardPass(); // do one backward pass over the CFG
 
+  // --------- private methods -----------------------------------------
+
+  // constructs BBLiveVars and init Def and In sets
+  void constructBBs();      
+    
+  // do one backward pass over the CFG
+  bool  doSingleBackwardPass(); 
+
+  // calculates live var sets for instructions in a BB
+  void calcLiveVarSetsForBB(const BasicBlock *const BB);
   
 
  public:
-  MethodLiveVarInfo(Method *const Meth);    // constructor 
+  MethodLiveVarInfo(const Method *const Meth);    // constructor 
 
-  ~MethodLiveVarInfo();                     // destructor
+  ~MethodLiveVarInfo();                           // destructor
 
-  void analyze();             // performs a liver var analysis of a single method
+  // performs a liver var analysis of a single method
+  void analyze();            
 
-                                                           // gets OutSet of a BB
-  inline const LiveVarSet *getOutSetOfBB( const BasicBlock *const BB)  const {   
+  // gets OutSet of a BB
+  inline const LiveVarSet *getOutSetOfBB( const BasicBlock *const BB) const { 
+    assert( HasAnalyzed && "call analyze() before calling this" );
     return (   (* (BB2BBLVMap.find(BB)) ).second  )->getOutSet();
   }
 
-                                                            // gets InSet of a BB
+  // gets InSet of a BB
   inline const LiveVarSet *getInSetOfBB( const BasicBlock *const BB)  const { 
+    assert( HasAnalyzed && "call analyze() before calling this" );
     return (   (* (BB2BBLVMap.find(BB)) ).second  )->getInSet();
   }
-                                   // gets the Live var set before an instruction
-  const LiveVarSet * 
-    MethodLiveVarInfo::getLiveVarSetBeforeInst(const Instruction *const Inst);
+
+  // gets the Live var set BEFORE an instruction
+  const LiveVarSet * getLiveVarSetBeforeMInst(const MachineInstr *const Inst,
+					      const BasicBlock *const CurBB);
+
+  // gets the Live var set AFTER an instruction
+  const LiveVarSet * getLiveVarSetAfterMInst(const MachineInstr *const MInst,
+					     const BasicBlock *const CurBB);
+
+
 
  
 };
diff --git a/include/llvm/Analysis/LiveVar/LiveVarMap.h b/include/llvm/Analysis/LiveVar/LiveVarMap.h
index a7f1ccd..bc00d4f 100644
--- a/include/llvm/Analysis/LiveVar/LiveVarMap.h
+++ b/include/llvm/Analysis/LiveVar/LiveVarMap.h
@@ -1,4 +1,4 @@
-/* Title:   ValueSet.h
+/* Title:   LiveVarMap.h
    Author:  Ruchira Sasanka
    Date:    Jun 30, 01
    Purpose: This file contains the class for a map between the BasicBlock class
@@ -18,8 +18,8 @@ class BasicBlock;
 class BBLiveVar;
 
 
-struct hashFuncInst {        // sturcture containing the hash function for Inst
-  inline size_t operator () (const Instruction *val) const { 
+struct hashFuncMInst {  // sturcture containing the hash function for MInst
+  inline size_t operator () (const MachineInstr *val) const { 
     return (size_t) val;  
   }
 };
@@ -37,8 +37,8 @@ struct hashFuncBB {          // sturcture containing the hash function for BB
 typedef hash_map<const BasicBlock *,  
 		 BBLiveVar *, hashFuncBB > BBToBBLiveVarMapType;
 
-typedef hash_map<const Instruction *,  const LiveVarSet *, 
-		 hashFuncInst> InstToLiveVarSetMapType;
+typedef hash_map<const MachineInstr *,  const LiveVarSet *, 
+		 hashFuncMInst> MInstToLiveVarSetMapType;
 
 
 #endif
diff --git a/include/llvm/Analysis/LiveVar/LiveVarSet.h b/include/llvm/Analysis/LiveVar/LiveVarSet.h
index 37d0d21..17524fc 100644
--- a/include/llvm/Analysis/LiveVar/LiveVarSet.h
+++ b/include/llvm/Analysis/LiveVar/LiveVarSet.h
@@ -1,4 +1,4 @@
-/* Title:   ValueSet.h
+/* Title:   LiveVarSet.h
    Author:  Ruchira Sasanka
    Date:    Jun 30, 01
    Purpose: Contains the class definition of LiveVarSet which is used for
@@ -16,8 +16,12 @@ class LiveVarSet : public ValueSet
 {
 
  public:
-  void applyTranferFuncForInst(const Instruction *const Inst); 
-  
+
+  // This function applies a machine instr to a live var set (accepts OutSet)
+  // and makes necessary changes to it (produces InSet).
+
+  void applyTranferFuncForMInst(const MachineInstr *const MInst);
+
 };
 
 
diff --git a/include/llvm/Analysis/LiveVar/ValueSet.h b/include/llvm/Analysis/LiveVar/ValueSet.h
index 02d3906..2b564b4 100644
--- a/include/llvm/Analysis/LiveVar/ValueSet.h
+++ b/include/llvm/Analysis/LiveVar/ValueSet.h
@@ -2,7 +2,7 @@
    Author:  Ruchira Sasanka
    Date:    Jun 30, 01
    Purpose: Contains a mathematical set of Values. LiveVarSet is derived from
-            this. Contains both class and method definitions
+            this. Contains both class and method definitions.
 */
 
 #ifndef VALUE_SET_H
@@ -20,14 +20,14 @@
 
 //------------------------ Support functions ---------------------------------
 
-struct hashFuncValue {                // sturcture containing the hash function. 
+struct hashFuncValue {                  // sturcture containing the hash func
   inline size_t operator () (const Value *const val) const 
   { return (size_t) val;  }
 };
 
 
 
-//------------------- Class Definition for ValueSet ----------------------------
+//------------------- Class Definition for ValueSet --------------------------
 
 void printValue( const Value *const v);  // func to print a Value 
 
@@ -37,21 +37,21 @@ class ValueSet : public hash_set<const Value *,  hashFuncValue >
 {
  
  public:
-  ValueSet();   // constructor
+  ValueSet();                           // constructor
 
   inline void add(const Value *const  val) 
-    { assert( val ); insert(val);}           // for adding a live variable to set
+    { assert( val ); insert(val);}      // for adding a live variable to set
 
   inline void remove(const Value *const  val) 
-    { assert( val ); erase(val); }       // for removing a live variable from set
+    { assert( val ); erase(val); }      // for removing a live var from set
 
-  bool setUnion( const ValueSet *const set1);    // for performing two set unions
-  void setSubtract( const ValueSet *const set1); // for performing set difference
+  bool setUnion( const ValueSet *const set1);     // for performing set union
+  void setSubtract( const ValueSet *const set1);  // for performing set diff
 
-                                                 // for performing set difference
+ 
   void setDifference( const ValueSet *const set1, const ValueSet *const set2); 
  
-  void printSet() const;  // for printing a live variable set
+  void printSet() const;                // for printing a live variable set
 };