blob: aeb7f9184c55d139ddbbb2369d8b2eec01eaeef2 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
#include "llvm/Analysis/LiveVar/BBLiveVar.h"
/********************* Implementation **************************************/
BBLiveVar::BBLiveVar( const BasicBlock* baseBB, unsigned int RdfoId)
: DefSet(), InSet(), OutSet(), PhiArgMap() {
BaseBB = baseBB;
InSetChanged = OutSetChanged = false;
POId = RdfoId;
}
void BBLiveVar::calcDefUseSets() // caluculates def and use sets for each BB
{
// instructions in basic block
const BasicBlock::InstListType& InstListInBB = BaseBB->getInstList();
BasicBlock::InstListType::const_reverse_iterator
InstIterator = InstListInBB.rbegin(); // get the iterator for instructions
// iterate over all the instructions in BB
for( ; InstIterator != InstListInBB.rend(); InstIterator++) {
const Instruction * Inst = *InstIterator; // Inst is the current instr
assert(Inst);
if( Inst->isDefinition() ) { // add to Defs only if this instr is a def
DefSet.add( Inst ); // nstruction is a def - so add to def set
InSet.remove( Inst); // this definition kills any uses
InSetChanged = true;
//cout << " adding inst to def "; printValue( Inst ); cout << endl;
}
Instruction::op_const_iterator
OpI = Inst->op_begin(); // get iterator for operands
bool IsPhi=( Inst->getOpcode() == Instruction::PHINode ); // Is this a phi
for(int OpNum=0 ; OpI != Inst->op_end() ; OpI++) { // iterate over operands
if ( ((*OpI)->getType())->isLabelType() )
continue; // don't process labels
InSet.add( *OpI ); // An operand is a use - so add to use set
OutSet.remove( *OpI ); // remove if there is a definition below this use
if( IsPhi ) { // for a phi node
// put args into the PhiArgMap
PhiArgMap[ *OpI ] = ((PHINode *) Inst )->getIncomingBlock( OpNum++ );
assert( PhiArgMap[ *OpI ] );
//cout << " Phi operand "; printValue( *OpI );
//cout << " came from BB "; printValue(PhiArgMap[*OpI]); cout<<endl;
}
InSetChanged = true;
//cout << " adding operand to use "; printValue( *OpI ); cout << endl;
}
}
}
bool BBLiveVar::applyTransferFunc() // calculates the InSet in terms of OutSet
{
// 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 );
OutSetChanged = false; // no change to OutSet since transfer func applied
return InSetChanged;
}
// calculates Out set using In sets of the predecessors
bool BBLiveVar::setPropagate( LiveVarSet *const OutSet,
const LiveVarSet *const InSet,
const BasicBlock *const PredBB) {
LiveVarSet::const_iterator InIt;
pair<LiveVarSet::iterator, bool> result;
bool changed = false;
const BasicBlock *PredBBOfPhiArg;
// for all all elements in InSet
for( InIt = InSet->begin() ; InIt != InSet->end(); InIt++) {
PredBBOfPhiArg = PhiArgMap[ *InIt ];
// if this var is not a phi arg or it came from this BB
if( !PredBBOfPhiArg || PredBBOfPhiArg == PredBB) {
result = OutSet->insert( *InIt ); // insert to this set
if( result.second == true) changed = true;
}
}
return changed;
}
// propogates in set to OutSets of PREDECESSORs
bool BBLiveVar::applyFlowFunc(BBToBBLiveVarMapType LVMap)
{
// IMPORTANT: caller should check whether inset changed
// (else no point in calling)
bool needAnotherIt= false; // did this BB change any OutSets of pred.s
// whose POId is lower
cfg::pred_const_iterator PredBBI = cfg::pred_begin(BaseBB);
for( ; PredBBI != cfg::pred_end(BaseBB) ; PredBBI++) {
assert( *PredBBI ); // assert that the predecessor is valid
BBLiveVar *PredLVBB = LVMap[*PredBBI];
// do set union
if( setPropagate( &(PredLVBB->OutSet), &InSet, *PredBBI ) == true) {
PredLVBB->OutSetChanged = true;
if( PredLVBB->getPOId() <= POId) // if the predec POId is lower than mine
needAnotherIt = true;
}
} // for
return needAnotherIt;
}
/* ----------------- Methods For Debugging (Printing) ----------------- */
void BBLiveVar::printAllSets() const
{
cout << "Defs: "; DefSet.printSet(); cout << endl;
cout << "In: "; InSet.printSet(); cout << endl;
cout << "Out: "; OutSet.printSet(); cout << endl;
}
void BBLiveVar::printInOutSets() const
{
cout << "In: "; InSet.printSet(); cout << endl;
cout << "Out: "; OutSet.printSet(); cout << endl;
}
|
