-
Notifications
You must be signed in to change notification settings - Fork 1.1k
/
LiveVariablesAnalysisEs6.java
394 lines (349 loc) · 12.5 KB
/
LiveVariablesAnalysisEs6.java
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
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
/*
* Copyright 2017 The Closure Compiler Authors.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package com.google.javascript.jscomp;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkState;
import com.google.javascript.jscomp.ControlFlowGraph.Branch;
import com.google.javascript.jscomp.graph.DiGraph.DiGraphEdge;
import com.google.javascript.jscomp.graph.LatticeElement;
import com.google.javascript.rhino.Node;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import javax.annotation.Nullable;
/**
* Compute the "liveness" of all local variables. A variable is "live" at a point of a program if
* the value it is currently holding might be read later. Otherwise, the variable is considered
* "dead" if we know for sure that it will no longer be read. Dead variables are candidates for dead
* assignment elimination and variable name sharing. The worst case safe assumption is to assume
* that all variables are live. In that case, we will have no opportunity for optimizations. This is
* especially the case within a TRY block when an assignment is not guaranteed to take place. We
* bail out by assuming that all variables are live.
*
* <p>Due to the possibility of inner functions and closures, certain "local" variables can escape
* the function. These variables will be considered as global and they can be retrieved with {@link
* #getEscapedLocals()}.
*
* @author simranarora@google.com (Simran Arora)
*/
class LiveVariablesAnalysisEs6
extends DataFlowAnalysis<Node, LiveVariablesAnalysisEs6.LiveVariableLattice> {
static final int MAX_VARIABLES_TO_ANALYZE = 100;
public static final String ARGUMENT_ARRAY_ALIAS = "arguments";
private static class LiveVariableJoinOp implements JoinOp<LiveVariableLattice> {
@Override
public LiveVariableLattice apply(List<LiveVariableLattice> in) {
LiveVariableLattice result = new LiveVariableLattice(in.get(0));
for (int i = 1; i < in.size(); i++) {
result.liveSet.or(in.get(i).liveSet);
}
return result;
}
}
/**
* The lattice that stores the liveness of all local variables at a given point in the program.
* The whole lattice is the power set of all local variables and a variable is live if it is in
* the set.
*/
static class LiveVariableLattice implements LatticeElement {
private final BitSet liveSet;
/** @param numVars Number of all local variables. */
private LiveVariableLattice(int numVars) {
this.liveSet = new BitSet(numVars);
}
private LiveVariableLattice(LiveVariableLattice other) {
checkNotNull(other);
this.liveSet = (BitSet) other.liveSet.clone();
}
@Override
public boolean equals(Object other) {
checkNotNull(other);
return (other instanceof LiveVariableLattice)
&& this.liveSet.equals(((LiveVariableLattice) other).liveSet);
}
// There is only a version of this function with index since var.index will
// return the wrong one. Use an instantiation of
// LiveVariablesAnalysisEs6 and getVarIndex(var) to get the right index.
public boolean isLive(int index) {
return liveSet.get(index);
}
@Override
public String toString() {
return liveSet.toString();
}
@Override
public int hashCode() {
return liveSet.hashCode();
}
}
// The scope of the function that we are analyzing.
private final Scope jsScope;
// The scope of the body of the function that we are analyzing.
private final Scope jsScopeChild;
private final Set<Var> escaped;
// Maps the variable name to it's position
// in this jsScope were we to combine the function and function body scopes. The Integer
// represents the equivalent of the variable index property within a scope
private final Map<String, Integer> scopeVariables;
/**
* ******************************************************* Live Variables Analysis using the ES6
* scope creator. Based on our preconditions, the child scope will only be passed in if the
* jsScope is function scope.
*
* @param cfg
* @param jsScope
* @param jsScopeChild used if jsScope is function scope in order to pass along function body
* @param compiler
* @param scopeCreator Es6 Scope creator
*/
LiveVariablesAnalysisEs6(
ControlFlowGraph<Node> cfg,
Scope jsScope,
@Nullable Scope jsScopeChild,
AbstractCompiler compiler,
Es6SyntacticScopeCreator scopeCreator) {
super(cfg, new LiveVariableJoinOp());
this.jsScope = jsScope;
this.jsScopeChild = jsScopeChild;
this.escaped = new HashSet<>();
this.scopeVariables = new HashMap<>();
computeEscaped(jsScope, jsScopeChild, escaped, compiler, scopeCreator);
addScopeVariables();
}
/**
* Parameters belong to the function scope, but variables defined in the function body belong to
* the function body scope. Assign a unique index to each variable, regardless of which scope it's
* in.
*/
private void addScopeVariables() {
int num = 0;
if (jsScope.isFunctionScope()) {
for (Var v : jsScope.getVarIterable()) {
scopeVariables.put(v.getName(), num);
num++;
}
if (jsScopeChild != null) {
for (Var v : jsScopeChild.getVarIterable()) {
// add the hoisted variables from this child scope
if ((v.isLet() || v.isConst()) && !jsScope.isFunctionScope()) {
continue;
}
scopeVariables.put(v.getName(), num);
num++;
}
}
} else {
if (jsScope.isFunctionBlockScope()) {
for (Var v : jsScope.getParent().getVarIterable()) {
scopeVariables.put(v.getName(), num);
num++;
}
}
for (Var v : jsScope.getVarIterable()) {
scopeVariables.put(v.getName(), num);
num++;
}
}
}
public Set<? extends Var> getEscapedLocals() {
return escaped;
}
public int getVarIndex(String var) {
return scopeVariables.get(var);
}
@Override
boolean isForward() {
return false;
}
@Override
LiveVariableLattice createEntryLattice() {
return new LiveVariableLattice(jsScope.getVarCount());
}
@Override
LiveVariableLattice createInitialEstimateLattice() {
return new LiveVariableLattice(jsScope.getVarCount());
}
@Override
LiveVariableLattice flowThrough(Node node, LiveVariableLattice input) {
final BitSet gen = new BitSet(input.liveSet.size());
final BitSet kill = new BitSet(input.liveSet.size());
// Make kills conditional if the node can end abruptly by an exception.
boolean conditional = false;
List<DiGraphEdge<Node, Branch>> edgeList = getCfg().getOutEdges(node);
for (DiGraphEdge<Node, Branch> edge : edgeList) {
if (Branch.ON_EX.equals(edge.getValue())) {
conditional = true;
}
}
computeGenKill(node, gen, kill, conditional);
LiveVariableLattice result = new LiveVariableLattice(input);
// L_in = L_out - Kill + Gen
result.liveSet.andNot(kill);
result.liveSet.or(gen);
return result;
}
/**
* Computes the GEN and KILL set.
*
* @param n Root node.
* @param gen Local variables that are live because of the instruction at {@code n} will be added
* to this set.
* @param kill Local variables that are killed because of the instruction at {@code n} will be
* added to this set.
* @param conditional {@code true} if any assignments encountered are conditionally executed.
* These assignments might not kill a variable.
*/
private void computeGenKill(Node n, BitSet gen, BitSet kill, boolean conditional) {
switch (n.getToken()) {
case SCRIPT:
case ROOT:
case FUNCTION:
case BLOCK:
return;
case WHILE:
case DO:
case IF:
case FOR:
computeGenKill(NodeUtil.getConditionExpression(n), gen, kill, conditional);
return;
case FOR_OF:
case FOR_IN:
{
// for (x in y) {...}
Node lhs = n.getFirstChild();
if (NodeUtil.isNameDeclaration(lhs)) {
// for (var x in y) {...}
lhs = lhs.getLastChild();
}
if (lhs.isName()) {
addToSetIfLocal(lhs, kill);
addToSetIfLocal(lhs, gen);
} else {
computeGenKill(lhs, gen, kill, conditional);
}
// rhs is executed only once so we don't go into it every loop.
return;
}
case LET:
case CONST:
case VAR:
for (Node c = n.getFirstChild(); c != null; c = c.getNext()) {
if (c.hasChildren()) {
computeGenKill(c.getFirstChild(), gen, kill, conditional);
if (!conditional) {
addToSetIfLocal(c, kill);
}
}
}
return;
case AND:
case OR:
computeGenKill(n.getFirstChild(), gen, kill, conditional);
// May short circuit.
computeGenKill(n.getLastChild(), gen, kill, true);
return;
case HOOK:
computeGenKill(n.getFirstChild(), gen, kill, conditional);
// Assume both sides are conditional.
computeGenKill(n.getSecondChild(), gen, kill, true);
computeGenKill(n.getLastChild(), gen, kill, true);
return;
case NAME:
if (isArgumentsName(n)) {
markAllParametersEscaped();
} else {
addToSetIfLocal(n, gen);
}
return;
default:
if (NodeUtil.isAssignmentOp(n) && n.getFirstChild().isName()) {
Node lhs = n.getFirstChild();
if (!conditional) {
addToSetIfLocal(lhs, kill);
}
if (!n.isAssign()) {
// assignments such as a += 1 reads a.
addToSetIfLocal(lhs, gen);
}
computeGenKill(lhs.getNext(), gen, kill, conditional);
} else {
for (Node c = n.getFirstChild(); c != null; c = c.getNext()) {
computeGenKill(c, gen, kill, conditional);
}
}
return;
}
}
private void addToSetIfLocal(Node node, BitSet set) {
checkState(node.isName(), node);
String name = node.getString();
boolean local;
// add to the local set if the variable is declared in the function or function body because
// ES6 separates the scope but hoists variables to the function scope
if (jsScope.isFunctionBlockScope()) {
local = jsScope.isDeclaredInFunctionBlockOrParameter(name);
} else {
local = jsScope.isDeclared(name, false);
}
if (local) {
Var var = jsScope.getVar(name);
if (!escaped.contains(var)) {
set.set(getVarIndex(var.getName()));
}
} else if (jsScopeChild != null && jsScope.isFunctionScope()) {
if (!jsScopeChild.isDeclared(name, false)) {
return;
} else {
Var var = jsScopeChild.getVar(name);
if (!escaped.contains(var)) {
set.set(getVarIndex(var.getName()));
}
}
}
}
/**
* Give up computing liveness of formal parameter by putting all the parameter names in the
* escaped set.
*/
void markAllParametersEscaped() {
if (jsScope.isFunctionScope()) {
Node paramList = NodeUtil.getFunctionParameters(jsScope.getRootNode());
for (Node arg = paramList.getFirstChild(); arg != null; arg = arg.getNext()) {
escaped.add(jsScope.getVar(arg.getString()));
}
} else {
Node enclosingFunction = NodeUtil.getEnclosingFunction(jsScope.getRootNode());
Node paramList = NodeUtil.getFunctionParameters(enclosingFunction);
for (Node arg = paramList.getFirstChild(); arg != null; arg = arg.getNext()) {
escaped.add(jsScope.getVar(arg.getString()));
}
}
}
private boolean isArgumentsName(Node n) {
boolean childDeclared;
if (jsScopeChild != null) {
childDeclared = jsScopeChild.isDeclared(ARGUMENT_ARRAY_ALIAS, false);
} else {
childDeclared = true;
}
return n.isName()
&& n.getString().equals(ARGUMENT_ARRAY_ALIAS)
&& (!jsScope.isDeclared(ARGUMENT_ARRAY_ALIAS, false) || !childDeclared);
}
}