summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Analysis')
-rw-r--r--llvm/lib/Analysis/LiveVar/BBLiveVar.cpp19
-rw-r--r--llvm/lib/Analysis/LiveVar/BBLiveVar.h14
-rw-r--r--llvm/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp80
-rw-r--r--llvm/lib/Analysis/LiveVar/LiveVarSet.cpp37
-rw-r--r--llvm/lib/Analysis/LiveVar/ValueSet.cpp26
5 files changed, 72 insertions, 104 deletions
diff --git a/llvm/lib/Analysis/LiveVar/BBLiveVar.cpp b/llvm/lib/Analysis/LiveVar/BBLiveVar.cpp
index 81bbd387564..bf4af29ff0e 100644
--- a/llvm/lib/Analysis/LiveVar/BBLiveVar.cpp
+++ b/llvm/lib/Analysis/LiveVar/BBLiveVar.cpp
@@ -126,9 +126,8 @@ bool BBLiveVar::applyTransferFunc() {
// IMPORTANT: caller should check whether the OutSet changed
// (else no point in calling)
- LiveVarSet OutMinusDef; // set to hold (Out[B] - Def[B])
- OutMinusDef.setDifference(&OutSet, &DefSet);
- InSetChanged = InSet.setUnion(&OutMinusDef);
+ ValueSet OutMinusDef = set_difference(OutSet, DefSet);
+ InSetChanged = set_union(InSet, OutMinusDef);
OutSetChanged = false; // no change to OutSet since transf func applied
return InSetChanged;
@@ -139,12 +138,12 @@ bool BBLiveVar::applyTransferFunc() {
// calculates Out set using In sets of the predecessors
//-----------------------------------------------------------------------------
-bool BBLiveVar::setPropagate(LiveVarSet *OutSet, const LiveVarSet *InSet,
+bool BBLiveVar::setPropagate(ValueSet *OutSet, const ValueSet *InSet,
const BasicBlock *PredBB) {
bool Changed = false;
// for all all elements in InSet
- for (LiveVarSet::const_iterator InIt = InSet->begin(), InE = InSet->end();
+ for (ValueSet::const_iterator InIt = InSet->begin(), InE = InSet->end();
InIt != InE; ++InIt) {
const BasicBlock *PredBBOfPhiArg = PhiArgMap[*InIt];
@@ -194,14 +193,14 @@ bool BBLiveVar::applyFlowFunc(std::map<const BasicBlock *, BBLiveVar *> &LVMap){
// ----------------- Methods For Debugging (Printing) -----------------
void BBLiveVar::printAllSets() const {
- cerr << " Defs: "; DefSet.printSet(); cerr << "\n";
- cerr << " In: "; InSet.printSet(); cerr << "\n";
- cerr << " Out: "; OutSet.printSet(); cerr << "\n";
+ cerr << " Defs: "; printSet(DefSet); cerr << "\n";
+ cerr << " In: "; printSet(InSet); cerr << "\n";
+ cerr << " Out: "; printSet(OutSet); cerr << "\n";
}
void BBLiveVar::printInOutSets() const {
- cerr << " In: "; InSet.printSet(); cerr << "\n";
- cerr << " Out: "; OutSet.printSet(); cerr << "\n";
+ cerr << " In: "; printSet(InSet); cerr << "\n";
+ cerr << " Out: "; printSet(OutSet); cerr << "\n";
}
diff --git a/llvm/lib/Analysis/LiveVar/BBLiveVar.h b/llvm/lib/Analysis/LiveVar/BBLiveVar.h
index d5c4ccaf7ba..1fc91f13300 100644
--- a/llvm/lib/Analysis/LiveVar/BBLiveVar.h
+++ b/llvm/lib/Analysis/LiveVar/BBLiveVar.h
@@ -7,7 +7,7 @@
#ifndef LIVE_VAR_BB_H
#define LIVE_VAR_BB_H
-#include "llvm/Analysis/LiveVar/LiveVarSet.h"
+#include "llvm/Analysis/LiveVar/ValueSet.h"
#include <map>
class Method;
class BasicBlock;
@@ -17,8 +17,8 @@ class BBLiveVar {
const BasicBlock *BB; // pointer to BasicBlock
unsigned POID; // Post-Order ID
- LiveVarSet DefSet; // Def set for LV analysis
- LiveVarSet InSet, OutSet; // In & Out for LV analysis
+ ValueSet DefSet; // Def set for LV analysis
+ ValueSet InSet, OutSet; // In & Out for LV analysis
bool InSetChanged, OutSetChanged; // set if the InSet/OutSet is modified
// map that contains phi args->BB they came
@@ -26,8 +26,8 @@ class BBLiveVar {
std::map<const Value *, const BasicBlock *> PhiArgMap;
// method to propogate an InSet to OutSet of a predecessor
- bool setPropagate(LiveVarSet *OutSetOfPred,
- const LiveVarSet *InSetOfThisBB,
+ bool setPropagate(ValueSet *OutSetOfPred,
+ const ValueSet *InSetOfThisBB,
const BasicBlock *PredBB);
// To add an operand which is a def
@@ -50,8 +50,8 @@ class BBLiveVar {
// calculates Out set using In sets of the predecessors
bool applyFlowFunc(std::map<const BasicBlock *, BBLiveVar *> &LVMap);
- inline const LiveVarSet *getOutSet() const { return &OutSet; }
- inline const LiveVarSet *getInSet() const { return &InSet; }
+ inline const ValueSet *getOutSet() const { return &OutSet; }
+ inline const ValueSet *getInSet() const { return &InSet; }
void printAllSets() const; // for printing Def/In/Out sets
void printInOutSets() const; // for printing In/Out sets
diff --git a/llvm/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp b/llvm/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp
index cfe0fe4ba02..98d39ec2a6e 100644
--- a/llvm/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp
+++ b/llvm/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp
@@ -1,13 +1,9 @@
-/* Title: MethodLiveVarInfo.cpp
- 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.
-
-*/
-
+//===-- MethodLiveVarInfo.cpp - Live Variable Analysis for a Method -------===//
+//
+// This is the interface to method level live variable information that is
+// provided by live variable analysis.
+//
+//===----------------------------------------------------------------------===//
#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
#include "BBLiveVar.h"
@@ -23,12 +19,12 @@ AnalysisID MethodLiveVarInfo::ID(AnalysisID::create<MethodLiveVarInfo>());
//-----------------------------------------------------------------------------
// gets OutSet of a BB
-const LiveVarSet *MethodLiveVarInfo::getOutSetOfBB(const BasicBlock *BB) const {
+const ValueSet *MethodLiveVarInfo::getOutSetOfBB(const BasicBlock *BB) const {
return BB2BBLVMap.find(BB)->second->getOutSet();
}
// gets InSet of a BB
-const LiveVarSet *MethodLiveVarInfo::getInSetOfBB(const BasicBlock *BB) const {
+const ValueSet *MethodLiveVarInfo::getInSetOfBB(const BasicBlock *BB) const {
return BB2BBLVMap.find(BB)->second->getInSet();
}
@@ -125,16 +121,16 @@ void MethodLiveVarInfo::releaseMemory() {
BB2BBLVMap.clear();
- // Then delete all objects of type LiveVarSet created in calcLiveVarSetsForBB
+ // Then delete all objects of type ValueSet created in calcLiveVarSetsForBB
// and entered into MInst2LVSetBI and MInst2LVSetAI (these are caches
- // to return LiveVarSet's before/after a machine instruction quickly). It
- // is sufficient to free up all LiveVarSet using only one cache since
+ // to return ValueSet's before/after a machine instruction quickly). It
+ // is sufficient to free up all ValueSet using only one cache since
// both caches refer to the same sets
//
- for (std::map<const MachineInstr*, const LiveVarSet*>::iterator
+ for (std::map<const MachineInstr*, const ValueSet*>::iterator
MI = MInst2LVSetBI.begin(),
ME = MInst2LVSetBI.end(); MI != ME; ++MI)
- delete MI->second; // delete all LiveVarSets in MInst2LVSetBI
+ delete MI->second; // delete all ValueSets in MInst2LVSetBI
MInst2LVSetBI.clear();
MInst2LVSetAI.clear();
@@ -158,10 +154,10 @@ void MethodLiveVarInfo::releaseMemory() {
// Gives live variable information before a machine instruction
//-----------------------------------------------------------------------------
-const LiveVarSet *
+const ValueSet *
MethodLiveVarInfo::getLiveVarSetBeforeMInst(const MachineInstr *MInst,
const BasicBlock *BB) {
- if (const LiveVarSet *LVSet = MInst2LVSetBI[MInst]) {
+ if (const ValueSet *LVSet = MInst2LVSetBI[MInst]) {
return LVSet; // if found, just return the set
} else {
calcLiveVarSetsForBB(BB); // else, calc for all instrs in BB
@@ -173,11 +169,11 @@ MethodLiveVarInfo::getLiveVarSetBeforeMInst(const MachineInstr *MInst,
//-----------------------------------------------------------------------------
// Gives live variable information after a machine instruction
//-----------------------------------------------------------------------------
-const LiveVarSet *
+const ValueSet *
MethodLiveVarInfo::getLiveVarSetAfterMInst(const MachineInstr *MI,
const BasicBlock *BB) {
- if (const LiveVarSet *LVSet = MInst2LVSetAI[MI]) {
+ if (const ValueSet *LVSet = MInst2LVSetAI[MI]) {
return LVSet; // if found, just return the set
} else {
calcLiveVarSetsForBB(BB); // else, calc for all instrs in BB
@@ -185,7 +181,37 @@ MethodLiveVarInfo::getLiveVarSetAfterMInst(const MachineInstr *MI,
}
}
+// This function applies a machine instr to a live var set (accepts OutSet) and
+// makes necessary changes to it (produces InSet). Note that two for loops are
+// used to first kill all defs and then to add all uses. This is because there
+// can be instructions like Val = Val + 1 since we allow multipe defs to a
+// machine instruction operand.
+//
+static void applyTranferFuncForMInst(ValueSet &LVS, const MachineInstr *MInst) {
+ for (MachineInstr::val_const_op_iterator OpI(MInst); !OpI.done(); ++OpI) {
+ if (OpI.isDef()) // kill only if this operand is a def
+ LVS.insert(*OpI); // this definition kills any uses
+ }
+
+ // do for implicit operands as well
+ for (unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
+ if (MInst->implicitRefIsDefined(i))
+ LVS.erase(MInst->getImplicitRef(i));
+ }
+ for (MachineInstr::val_const_op_iterator OpI(MInst); !OpI.done(); ++OpI) {
+ if (isa<BasicBlock>(*OpI)) continue; // don't process labels
+
+ if (!OpI.isDef()) // add only if this operand is a use
+ LVS.insert(*OpI); // An operand is a use - so add to use set
+ }
+
+ // do for implicit operands as well
+ for (unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
+ if (!MInst->implicitRefIsDefined(i))
+ LVS.insert(MInst->getImplicitRef(i));
+ }
+}
//-----------------------------------------------------------------------------
// This method calculates the live variable information for all the
@@ -196,9 +222,9 @@ MethodLiveVarInfo::getLiveVarSetAfterMInst(const MachineInstr *MI,
void MethodLiveVarInfo::calcLiveVarSetsForBB(const BasicBlock *BB) {
const MachineCodeForBasicBlock &MIVec = BB->getMachineInstrVec();
- LiveVarSet *CurSet = new LiveVarSet();
- const LiveVarSet *SetAI = getOutSetOfBB(BB); // init SetAI with OutSet
- CurSet->setUnion(SetAI); // CurSet now contains OutSet
+ ValueSet *CurSet = new ValueSet();
+ const ValueSet *SetAI = getOutSetOfBB(BB); // init SetAI with OutSet
+ set_union(*CurSet, *SetAI); // CurSet now contains OutSet
// iterate over all the machine instructions in BB
for (MachineCodeForBasicBlock::const_reverse_iterator MII = MIVec.rbegin(),
@@ -208,9 +234,9 @@ void MethodLiveVarInfo::calcLiveVarSetsForBB(const BasicBlock *BB) {
MInst2LVSetAI[MI] = SetAI; // record in After Inst map
- CurSet->applyTranferFuncForMInst(MI); // apply the transfer Func
- LiveVarSet *NewSet = new LiveVarSet(); // create a new set and
- NewSet->setUnion(CurSet); // copy the set after T/F to it
+ applyTranferFuncForMInst(*CurSet, MI); // apply the transfer Func
+ ValueSet *NewSet = new ValueSet(); // create a new set and
+ set_union(*NewSet, *CurSet); // copy the set after T/F to it
MInst2LVSetBI[MI] = NewSet; // record in Before Inst map
diff --git a/llvm/lib/Analysis/LiveVar/LiveVarSet.cpp b/llvm/lib/Analysis/LiveVar/LiveVarSet.cpp
index 9243d059817..e69de29bb2d 100644
--- a/llvm/lib/Analysis/LiveVar/LiveVarSet.cpp
+++ b/llvm/lib/Analysis/LiveVar/LiveVarSet.cpp
@@ -1,37 +0,0 @@
-#include "llvm/Analysis/LiveVar/LiveVarSet.h"
-#include "llvm/CodeGen/MachineInstr.h"
-#include "llvm/Type.h"
-
-// This function applies a machine instr to a live var set (accepts OutSet) and
-// makes necessary changes to it (produces InSet). Note that two for loops are
-// used to first kill all defs and then to add all uses. This is because there
-// can be instructions like Val = Val + 1 since we allow multipe defs to a
-// machine instruction operand.
-
-
-void LiveVarSet::applyTranferFuncForMInst(const MachineInstr *MInst) {
- for (MachineInstr::val_const_op_iterator OpI(MInst); !OpI.done(); ++OpI) {
- if (OpI.isDef()) // kill only if this operand is a def
- insert(*OpI); // this definition kills any uses
- }
-
- // do for implicit operands as well
- for ( unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
- if (MInst->implicitRefIsDefined(i))
- erase(MInst->getImplicitRef(i));
- }
-
-
- for (MachineInstr::val_const_op_iterator OpI(MInst); !OpI.done(); ++OpI) {
- if ((*OpI)->getType()->isLabelType()) continue; // don't process labels
-
- if (!OpI.isDef()) // add only if this operand is a use
- insert(*OpI); // An operand is a use - so add to use set
- }
-
- // do for implicit operands as well
- for (unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
- if (!MInst->implicitRefIsDefined(i))
- insert(MInst->getImplicitRef(i));
- }
-}
diff --git a/llvm/lib/Analysis/LiveVar/ValueSet.cpp b/llvm/lib/Analysis/LiveVar/ValueSet.cpp
index 431ccc62229..88dd25a0331 100644
--- a/llvm/lib/Analysis/LiveVar/ValueSet.cpp
+++ b/llvm/lib/Analysis/LiveVar/ValueSet.cpp
@@ -15,28 +15,8 @@ ostream &operator<<(ostream &O, RAV V) { // func to print a Value
return O << v << " ";
}
-bool ValueSet::setUnion( const ValueSet *S) {
- bool Changed = false;
-
- for (const_iterator SI = S->begin(), SE = S->end(); SI != SE; ++SI)
- if (insert(*SI).second)
- Changed = true;
-
- return Changed;
-}
-
-void ValueSet::setDifference(const ValueSet *S1, const ValueSet *S2) {
- for (const_iterator SI = S1->begin(), SE = S1->end() ; SI != SE; ++SI)
- if (S2->find(*SI) == S2->end()) // if the element is not in set2
- insert(*SI);
-}
-
-void ValueSet::setSubtract(const ValueSet *S) {
- for (const_iterator SI = S->begin() ; SI != S->end(); ++SI)
- erase(*SI);
-}
-
-void ValueSet::printSet() const {
- for (const_iterator I = begin(), E = end(); I != E; ++I)
+void printSet(const ValueSet &S) {
+ for (ValueSet::const_iterator I = S.begin(), E = S.end(); I != E; ++I)
std::cerr << RAV(*I);
}
+
OpenPOWER on IntegriCloud