aboutsummaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
Diffstat (limited to 'include')
-rw-r--r--include/llvm/Analysis/LiveVar/FunctionLiveVarInfo.h129
-rw-r--r--include/llvm/Analysis/LiveVar/LiveVarMap.h46
-rw-r--r--include/llvm/Analysis/LiveVar/LiveVarSet.h26
-rw-r--r--include/llvm/Analysis/LiveVar/ValueSet.h62
-rw-r--r--include/llvm/CodeGen/FunctionLiveVarInfo.h129
-rw-r--r--include/llvm/CodeGen/ValueSet.h62
6 files changed, 454 insertions, 0 deletions
diff --git a/include/llvm/Analysis/LiveVar/FunctionLiveVarInfo.h b/include/llvm/Analysis/LiveVar/FunctionLiveVarInfo.h
new file mode 100644
index 0000000000..206fef8e3e
--- /dev/null
+++ b/include/llvm/Analysis/LiveVar/FunctionLiveVarInfo.h
@@ -0,0 +1,129 @@
+/* Title: MethodLiveVarInfo.h
+ Author: Ruchira Sasanka
+ 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
+
+ It should be called like:
+
+ MethodLiveVarInfo MLVI( Mehtod *); // initializes data structures
+ 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
+
+ The live var set before an instruction can be constructed in several ways:
+
+ 1. 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:
+
+
+ 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
+ LVSet.setUnion( LVI->getOutSetOfBB( *BBI ) );
+
+ BasicBlock::InstListType::const_reverse_iterator
+ InstIterator = InstListInBB.rbegin(); // get the reverse it for inst in BB
+
+ // iterate over all the instructions in BB in reverse
+ for( ; InstIterator != InstListInBB.rend(); InstIterator++) {
+
+ //...... all code here which uses LVSet ........
+
+ LVSet.applyTranferFuncForInst(*InstIterator);
+
+ // Now LVSet contains live vars ABOVE the current instrution
+ }
+
+ 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
+#define DEBUG_LV (1)
+
+#include "LiveVarSet.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Instruction.h"
+#include "llvm/Method.h"
+#include "llvm/CFG.h"
+
+#include "LiveVarMap.h"
+#include "BBLiveVar.h"
+
+
+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
+
+ InstToLiveVarSetMapType Inst2LVSetMap; // Instruction to LiveVarSet Map
+ //- for providing LV info for each inst
+
+ void constructBBs(); // constructs BBLiveVars and init Def and In sets
+ bool doSingleBackwardPass(); // do one backward pass over the CFG
+
+
+
+ public:
+ MethodLiveVarInfo(Method *const Meth); // constructor
+
+ ~MethodLiveVarInfo(); // destructor
+
+ void analyze(); // performs a liver var analysis of a single method
+
+ // gets OutSet of a BB
+ inline const LiveVarSet *getOutSetOfBB( const BasicBlock *const BB) const {
+ return ( (* (BB2BBLVMap.find(BB)) ).second )->getOutSet();
+ }
+
+ // gets InSet of a BB
+ inline const LiveVarSet *getInSetOfBB( const BasicBlock *const BB) const {
+ return ( (* (BB2BBLVMap.find(BB)) ).second )->getInSet();
+ }
+ // gets the Live var set before an instruction
+ const LiveVarSet *
+ MethodLiveVarInfo::getLiveVarSetBeforeInst(const Instruction *const Inst);
+
+
+};
+
+
+
+
+
+#endif
+
+
+
+
diff --git a/include/llvm/Analysis/LiveVar/LiveVarMap.h b/include/llvm/Analysis/LiveVar/LiveVarMap.h
new file mode 100644
index 0000000000..a7f1ccd6fd
--- /dev/null
+++ b/include/llvm/Analysis/LiveVar/LiveVarMap.h
@@ -0,0 +1,46 @@
+/* Title: ValueSet.h
+ Author: Ruchira Sasanka
+ Date: Jun 30, 01
+ Purpose: This file contains the class for a map between the BasicBlock class
+ and the BBLiveVar class, which is a wrapper class of BasicBlock
+ used for the live variable analysis. The reverse mapping can
+ be found in the BBLiveVar class (It has a pointer to the
+ corresponding BasicBlock)
+*/
+
+
+#ifndef LIVE_VAR_MAP_H
+#define LIVE_VAR_MAP_H
+
+#include <hash_map>
+
+class BasicBlock;
+class BBLiveVar;
+
+
+struct hashFuncInst { // sturcture containing the hash function for Inst
+ inline size_t operator () (const Instruction *val) const {
+ return (size_t) val;
+ }
+};
+
+
+struct hashFuncBB { // sturcture containing the hash function for BB
+ inline size_t operator () (const BasicBlock *val) const {
+ return (size_t) val;
+ }
+};
+
+
+
+
+typedef hash_map<const BasicBlock *,
+ BBLiveVar *, hashFuncBB > BBToBBLiveVarMapType;
+
+typedef hash_map<const Instruction *, const LiveVarSet *,
+ hashFuncInst> InstToLiveVarSetMapType;
+
+
+#endif
+
+
diff --git a/include/llvm/Analysis/LiveVar/LiveVarSet.h b/include/llvm/Analysis/LiveVar/LiveVarSet.h
new file mode 100644
index 0000000000..37d0d21547
--- /dev/null
+++ b/include/llvm/Analysis/LiveVar/LiveVarSet.h
@@ -0,0 +1,26 @@
+/* Title: ValueSet.h
+ Author: Ruchira Sasanka
+ Date: Jun 30, 01
+ Purpose: Contains the class definition of LiveVarSet which is used for
+ live variable analysis.
+*/
+
+#ifndef LIVE_VAR_SET_H
+#define LIVE_VAR_SET_H
+
+#include "ValueSet.h"
+#include "llvm/Instruction.h"
+#include "llvm/Type.h"
+
+class LiveVarSet : public ValueSet
+{
+
+ public:
+ void applyTranferFuncForInst(const Instruction *const Inst);
+
+};
+
+
+#endif
+
+
diff --git a/include/llvm/Analysis/LiveVar/ValueSet.h b/include/llvm/Analysis/LiveVar/ValueSet.h
new file mode 100644
index 0000000000..02d3906178
--- /dev/null
+++ b/include/llvm/Analysis/LiveVar/ValueSet.h
@@ -0,0 +1,62 @@
+/* Title: ValueSet.h
+ 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
+*/
+
+#ifndef VALUE_SET_H
+#define VALUE_SET_H
+
+#include <stdlib.h>
+
+#include <hash_set>
+#include <algorithm>
+#include <fstream>
+#include <iostream>
+
+#include "llvm/Value.h"
+
+
+//------------------------ Support functions ---------------------------------
+
+struct hashFuncValue { // sturcture containing the hash function.
+ inline size_t operator () (const Value *const val) const
+ { return (size_t) val; }
+};
+
+
+
+//------------------- Class Definition for ValueSet ----------------------------
+
+void printValue( const Value *const v); // func to print a Value
+
+
+
+class ValueSet : public hash_set<const Value *, hashFuncValue >
+{
+
+ public:
+ ValueSet(); // constructor
+
+ inline void add(const Value *const val)
+ { 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
+
+ bool setUnion( const ValueSet *const set1); // for performing two set unions
+ void setSubtract( const ValueSet *const set1); // for performing set difference
+
+ // for performing set difference
+ void setDifference( const ValueSet *const set1, const ValueSet *const set2);
+
+ void printSet() const; // for printing a live variable set
+};
+
+
+
+
+
+
+#endif
diff --git a/include/llvm/CodeGen/FunctionLiveVarInfo.h b/include/llvm/CodeGen/FunctionLiveVarInfo.h
new file mode 100644
index 0000000000..206fef8e3e
--- /dev/null
+++ b/include/llvm/CodeGen/FunctionLiveVarInfo.h
@@ -0,0 +1,129 @@
+/* Title: MethodLiveVarInfo.h
+ Author: Ruchira Sasanka
+ 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
+
+ It should be called like:
+
+ MethodLiveVarInfo MLVI( Mehtod *); // initializes data structures
+ 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
+
+ The live var set before an instruction can be constructed in several ways:
+
+ 1. 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:
+
+
+ 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
+ LVSet.setUnion( LVI->getOutSetOfBB( *BBI ) );
+
+ BasicBlock::InstListType::const_reverse_iterator
+ InstIterator = InstListInBB.rbegin(); // get the reverse it for inst in BB
+
+ // iterate over all the instructions in BB in reverse
+ for( ; InstIterator != InstListInBB.rend(); InstIterator++) {
+
+ //...... all code here which uses LVSet ........
+
+ LVSet.applyTranferFuncForInst(*InstIterator);
+
+ // Now LVSet contains live vars ABOVE the current instrution
+ }
+
+ 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
+#define DEBUG_LV (1)
+
+#include "LiveVarSet.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Instruction.h"
+#include "llvm/Method.h"
+#include "llvm/CFG.h"
+
+#include "LiveVarMap.h"
+#include "BBLiveVar.h"
+
+
+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
+
+ InstToLiveVarSetMapType Inst2LVSetMap; // Instruction to LiveVarSet Map
+ //- for providing LV info for each inst
+
+ void constructBBs(); // constructs BBLiveVars and init Def and In sets
+ bool doSingleBackwardPass(); // do one backward pass over the CFG
+
+
+
+ public:
+ MethodLiveVarInfo(Method *const Meth); // constructor
+
+ ~MethodLiveVarInfo(); // destructor
+
+ void analyze(); // performs a liver var analysis of a single method
+
+ // gets OutSet of a BB
+ inline const LiveVarSet *getOutSetOfBB( const BasicBlock *const BB) const {
+ return ( (* (BB2BBLVMap.find(BB)) ).second )->getOutSet();
+ }
+
+ // gets InSet of a BB
+ inline const LiveVarSet *getInSetOfBB( const BasicBlock *const BB) const {
+ return ( (* (BB2BBLVMap.find(BB)) ).second )->getInSet();
+ }
+ // gets the Live var set before an instruction
+ const LiveVarSet *
+ MethodLiveVarInfo::getLiveVarSetBeforeInst(const Instruction *const Inst);
+
+
+};
+
+
+
+
+
+#endif
+
+
+
+
diff --git a/include/llvm/CodeGen/ValueSet.h b/include/llvm/CodeGen/ValueSet.h
new file mode 100644
index 0000000000..02d3906178
--- /dev/null
+++ b/include/llvm/CodeGen/ValueSet.h
@@ -0,0 +1,62 @@
+/* Title: ValueSet.h
+ 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
+*/
+
+#ifndef VALUE_SET_H
+#define VALUE_SET_H
+
+#include <stdlib.h>
+
+#include <hash_set>
+#include <algorithm>
+#include <fstream>
+#include <iostream>
+
+#include "llvm/Value.h"
+
+
+//------------------------ Support functions ---------------------------------
+
+struct hashFuncValue { // sturcture containing the hash function.
+ inline size_t operator () (const Value *const val) const
+ { return (size_t) val; }
+};
+
+
+
+//------------------- Class Definition for ValueSet ----------------------------
+
+void printValue( const Value *const v); // func to print a Value
+
+
+
+class ValueSet : public hash_set<const Value *, hashFuncValue >
+{
+
+ public:
+ ValueSet(); // constructor
+
+ inline void add(const Value *const val)
+ { 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
+
+ bool setUnion( const ValueSet *const set1); // for performing two set unions
+ void setSubtract( const ValueSet *const set1); // for performing set difference
+
+ // for performing set difference
+ void setDifference( const ValueSet *const set1, const ValueSet *const set2);
+
+ void printSet() const; // for printing a live variable set
+};
+
+
+
+
+
+
+#endif
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-08-04 03:19:46 +0000