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
|
/* Title: MethodLiveVarInfo.h -*- C++ -*-
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 must 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 obtained in 2 ways:
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 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
LVSet.setUnion( LVI->getOutSetOfBB( *BBI ) );
BasicBlock::InstListType::const_reverse_iterator
InstIterator = InstListInBB.rbegin(); // get the rev iter 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.
*/
#ifndef METH_LIVE_VAR_INFO_H
#define METH_LIVE_VAR_INFO_H
#include "llvm/Pass.h"
#include "llvm/Analysis/LiveVar/ValueSet.h"
#include "Support/CommandLine.h"
class BBLiveVar;
class MachineInstr;
enum LiveVarDebugLevel_t {
LV_DEBUG_None,
LV_DEBUG_Normal,
LV_DEBUG_Instr,
LV_DEBUG_Verbose
};
extern cl::Enum<LiveVarDebugLevel_t> DEBUG_LV;
class MethodLiveVarInfo : public MethodPass {
// Machine Instr to LiveVarSet Map for providing LVset BEFORE each inst
std::map<const MachineInstr *, const ValueSet *> MInst2LVSetBI;
// Machine Instr to LiveVarSet Map for providing LVset AFTER each inst
std::map<const MachineInstr *, const ValueSet *> MInst2LVSetAI;
// Stored Method that the data is computed with respect to
const Method *M;
// --------- private methods -----------------------------------------
// constructs BBLiveVars and init Def and In sets
void constructBBs(const Method *M);
// do one backward pass over the CFG
bool doSingleBackwardPass(const Method *M, unsigned int iter);
// calculates live var sets for instructions in a BB
void calcLiveVarSetsForBB(const BasicBlock *BB);
public:
static AnalysisID ID; // We are an analysis, we must have an ID
MethodLiveVarInfo(AnalysisID id = ID) { assert(id == ID); }
// --------- Implement the MethodPass interface ----------------------
// runOnMethod - Perform analysis, update internal data structures.
virtual bool runOnMethod(Method *M);
// releaseMemory - After LiveVariable analysis has been used, forget!
virtual void releaseMemory();
// getAnalysisUsageInfo - Provide self!
virtual void getAnalysisUsageInfo(AnalysisSet &Required,
AnalysisSet &Destroyed,
AnalysisSet &Provided) {
Provided.push_back(ID);
}
// --------- Functions to access analysis results -------------------
// gets OutSet of a BB
const ValueSet &getOutSetOfBB(const BasicBlock *BB) const;
// gets InSet of a BB
const ValueSet &getInSetOfBB(const BasicBlock *BB) const;
// gets the Live var set BEFORE an instruction
const ValueSet &getLiveVarSetBeforeMInst(const MachineInstr *MI,
const BasicBlock *BB);
// gets the Live var set AFTER an instruction
const ValueSet &getLiveVarSetAfterMInst(const MachineInstr *MI,
const BasicBlock *BB);
};
#endif
|
