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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
|
======================
Live Variable Analysis
======================
1. Introduction
===============
Purpose: This file contains implementation information about live variable
analysis.
Author : Ruchira Sasanka
Date : Dec 8, 2001
2. Entry Point
==============
The class MethodLiveVarInfo (declared in MethodLiveVarInfo.h and implemented in
MethodLiveVarInfo.cpp) is the main entry point of live variable analysis. This
class performs live variable analysis of one method. This class implements
iterative live variable analysis.
3. Usage
========
This class must be used like:
MethodLiveVarInfo MLVI( Mehtod *); // initializes data structures
MLVI.analyze(); // do the actual live variable anal
After the live variable analysis is complete, the user can call methods to get
(1) InSet/OutSet of any BasicBlock:
(a) MethodLiveVarInfo::getOutSetOfBB
(b) MethodLiveVarInfo::getInSetOfBB
(2) Any LiveVarSet before/after a machine instruction in method:
(a) MethodLiveVarInfo::getLiveVarSetBeforeMInst
(b) MethodLiveVarInfo::getLiveVarSetBeforeMInst
See MethodLiveVarInfo.h for interface methods.
Note:
----
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 calculates 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 interface.
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 instruction
}
See buildInterferenceGraph() in ../llvm/lib/CodeGen/RegAlloc/ for the
above example.
4. Input and Preconditions
==========================
Live variable analysis is done using machine instructions. The constructor
to the class takes a pointer to a method, and machine instructions must be
already available for this method before calling the constructor.
The preconditions are:
1. Instruction selection is complete (i.e., machine instructions are
generated) for the method before the live variable analysis
5. Assumptions
==============
1. There may be dummy phi machine instructions in the machine code. The code
works with and without dummy phi instructions (i.e., this code can be
called before or after phi elimination). Currently, it is called without
phi instructions.
2. Only the basic blocks that can be reached by the post-order iterator will
be analyzed (i.e., basic blocks for dead code will not be analyzed). The
live variable sets returned for such basic blocks is not defined.
6. Data Structures, Classes and Main Objects
============================================
LiveVarSet: This class implements a basic live variable set. It contains a
set of Value objects.
BBLiveVar: This class is used to keep live variable information like the inset,
outset, etc. about a basic block. We create one object of this type for each
basic block in the original method in MethodLiveVarInfo::constructBBs(). This
class is declared in BBLiveVar.h
BBToBBLiveVarMapType: This class is used to create a map between the original
basic blocks in the method and new BBLiveVar objects created for each original
basic block. There is only one object of this type called BB2BBLVMap in
class MethodLiveVarInfo.
MInstToLiveVarSetMapType: This class is used to create a map between a machine
instruction and a LiveVarSet before/after that machine instruction. There are
two objects of this type: MInst2LVSetBI and MInst2LVSetAI, declared in
class is declared in BBLiveVar.h. Both these objects are used as caches. When a
user of class MethodLiveVarInfo requests a LiveVarSet before/after a machine'
instruction, these two caches are used to find the those live variable sets
quickly. See MethodLiveVarInfo::calcLiveVarSetsForBB for implementation.
7. Algorithms
=============
7.1 LiveVaraible Analysis Algorithm
------------------------------------
Live variable analysis is done using iterative analysis. The main steps are:
1. Construct BBLiveVar objects for each BasicBlock in the method.
2. While OutSets change
do one pass over the entire CFG
The above algorithm is implemented in:
MethodLiveVarInfo::analyze()
MethodLiveVarInfo::doSingleBackwardPass()
7.2 Algorithm for obtaining LiveVarSets before/after a machine instruction
--------------------------------------------------------------------------
LiveVarSets before/after a machine instruction can be obtained using:
(a) MethodLiveVarInfo::getLiveVarSetBeforeMInst
(b) MethodLiveVarInfo::getLiveVarSetBeforeMInst
The basic algorithm is:
1. When a LiveVarSet before/after a machine instruction is requested, look
in the MInst2LVSetBI/MInst2LVSetAI to see whether a LiveVarSet is
calculated and already entered in the corresponding cache.
If yes,
just return the LiveVarSet from the cache
Else
call MethodLiveVarInfo::calcLiveVarSetsForBB to calculate live variable
sets for ALL machine instructions in a BasicBlock and to enter all
those calculated LiveVarSets in caches ( MInst2LVSetBI/MInst2LVSetAI)
8. Future work
==============
If it is necessary to do live variable analysis using LLVM instructions rather
than using machine instructions, it is easy to modify the existing code to
do so. Current implementation use isDef() to find any MachineOperand is a
definition or a use. We just need to change all the places that check whether
a particular Value is a definition/use with MachineInstr. Instead, we
would check whether an LLVM value is a def/use using LLVM instructions. All
the underlying data structures will remain the same. However, iterators that
go over machine instructions must be changed to the corresponding iterators
that go over the LLVM instructions. The logic to support Phi's in LLVM
instructions is already there. In fact, live variable analysis was first
done using LLVM instructions and later changed to use machine instructions.
Hence, it is quite straightforward to revert it to LLVM instructions if
necessary.
|
