1 /*
2 * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package jdk.nashorn.internal.codegen;
27
28 import java.util.ArrayList;
29 import java.util.HashSet;
30 import java.util.List;
31 import java.util.Set;
32 import jdk.nashorn.internal.codegen.types.Type;
33 import jdk.nashorn.internal.ir.BinaryNode;
34 import jdk.nashorn.internal.ir.Block;
35 import jdk.nashorn.internal.ir.BlockStatement;
36 import jdk.nashorn.internal.ir.CaseNode;
37 import jdk.nashorn.internal.ir.EmptyNode;
38 import jdk.nashorn.internal.ir.Expression;
39 import jdk.nashorn.internal.ir.FunctionNode;
40 import jdk.nashorn.internal.ir.IfNode;
41 import jdk.nashorn.internal.ir.LiteralNode;
42 import jdk.nashorn.internal.ir.LiteralNode.ArrayLiteralNode;
43 import jdk.nashorn.internal.ir.Node;
44 import jdk.nashorn.internal.ir.Statement;
45 import jdk.nashorn.internal.ir.SwitchNode;
46 import jdk.nashorn.internal.ir.TernaryNode;
47 import jdk.nashorn.internal.ir.UnaryNode;
48 import jdk.nashorn.internal.ir.VarNode;
49 import jdk.nashorn.internal.ir.visitor.SimpleNodeVisitor;
50 import jdk.nashorn.internal.runtime.Context;
51 import jdk.nashorn.internal.runtime.JSType;
52 import jdk.nashorn.internal.runtime.ScriptRuntime;
53 import jdk.nashorn.internal.runtime.logging.DebugLogger;
54 import jdk.nashorn.internal.runtime.logging.Loggable;
55 import jdk.nashorn.internal.runtime.logging.Logger;
56
57 /**
58 * Simple constant folding pass, executed before IR is starting to be lowered.
59 */
60 @Logger(name="fold")
61 final class FoldConstants extends SimpleNodeVisitor implements Loggable {
62
63 private final DebugLogger log;
64
65 FoldConstants(final Compiler compiler) {
66 this.log = initLogger(compiler.getContext());
67 }
68
69 @Override
70 public DebugLogger getLogger() {
71 return log;
72 }
73
74 @Override
75 public DebugLogger initLogger(final Context context) {
76 return context.getLogger(this.getClass());
77 }
78
79 @Override
80 public Node leaveUnaryNode(final UnaryNode unaryNode) {
81 final LiteralNode<?> literalNode = new UnaryNodeConstantEvaluator(unaryNode).eval();
82 if (literalNode != null) {
83 log.info("Unary constant folded ", unaryNode, " to ", literalNode);
84 return literalNode;
85 }
86 return unaryNode;
87 }
88
89 @Override
90 public Node leaveBinaryNode(final BinaryNode binaryNode) {
91 final LiteralNode<?> literalNode = new BinaryNodeConstantEvaluator(binaryNode).eval();
92 if (literalNode != null) {
93 log.info("Binary constant folded ", binaryNode, " to ", literalNode);
94 return literalNode;
95 }
96 return binaryNode;
97 }
98
99 @Override
100 public Node leaveFunctionNode(final FunctionNode functionNode) {
101 return functionNode;
102 }
103
104 @Override
105 public Node leaveIfNode(final IfNode ifNode) {
106 final Node test = ifNode.getTest();
107 if (test instanceof LiteralNode.PrimitiveLiteralNode) {
108 final boolean isTrue = ((LiteralNode.PrimitiveLiteralNode<?>)test).isTrue();
109 final Block executed = isTrue ? ifNode.getPass() : ifNode.getFail();
110 final Block dropped = isTrue ? ifNode.getFail() : ifNode.getPass();
111 final List<Statement> statements = new ArrayList<>();
112
113 if (executed != null) {
114 statements.addAll(executed.getStatements()); // Get statements form executed branch
115 }
116 if (dropped != null) {
117 extractVarNodesFromDeadCode(dropped, statements); // Get var-nodes from non-executed branch
118 }
119 if (statements.isEmpty()) {
120 return new EmptyNode(ifNode);
121 }
122 return BlockStatement.createReplacement(ifNode, ifNode.getFinish(), statements);
123 }
124 return ifNode;
125 }
126
127 @Override
128 public Node leaveTernaryNode(final TernaryNode ternaryNode) {
129 final Node test = ternaryNode.getTest();
130 if (test instanceof LiteralNode.PrimitiveLiteralNode) {
131 return (((LiteralNode.PrimitiveLiteralNode<?>)test).isTrue() ? ternaryNode.getTrueExpression() : ternaryNode.getFalseExpression()).getExpression();
132 }
133 return ternaryNode;
134 }
135
136 @Override
137 public Node leaveSwitchNode(final SwitchNode switchNode) {
138 return switchNode.setUniqueInteger(lc, isUniqueIntegerSwitchNode(switchNode));
139 }
140
141 private static boolean isUniqueIntegerSwitchNode(final SwitchNode switchNode) {
142 final Set<Integer> alreadySeen = new HashSet<>();
143 for (final CaseNode caseNode : switchNode.getCases()) {
144 final Expression test = caseNode.getTest();
145 if (test != null && !isUniqueIntegerLiteral(test, alreadySeen)) {
146 return false;
147 }
148 }
149 return true;
150 }
151
152 private static boolean isUniqueIntegerLiteral(final Expression expr, final Set<Integer> alreadySeen) {
153 if (expr instanceof LiteralNode) {
154 final Object value = ((LiteralNode<?>)expr).getValue();
155 if (value instanceof Integer) {
156 return alreadySeen.add((Integer)value);
157 }
158 }
159 return false;
160 }
161
162 /**
163 * Helper class to evaluate constant expressions at compile time This is
164 * also a simplifier used by BinaryNode visits, UnaryNode visits and
165 * conversions.
166 */
167 abstract static class ConstantEvaluator<T extends Node> {
168 protected T parent;
169 protected final long token;
170 protected final int finish;
171
172 protected ConstantEvaluator(final T parent) {
173 this.parent = parent;
174 this.token = parent.getToken();
175 this.finish = parent.getFinish();
176 }
177
178 /**
179 * Returns a literal node that replaces the given parent node, or null if replacement
180 * is impossible
181 * @return the literal node
182 */
183 protected abstract LiteralNode<?> eval();
184 }
185
186 /**
187 * When we eliminate dead code, we must preserve var declarations as they are scoped to the whole
188 * function. This method gathers var nodes from code passed to it, removing their initializers.
189 *
190 * @param deadCodeRoot the root node of eliminated dead code
191 * @param statements a list that will be receiving the var nodes from the dead code, with their
192 * initializers removed.
193 */
194 static void extractVarNodesFromDeadCode(final Node deadCodeRoot, final List<Statement> statements) {
195 deadCodeRoot.accept(new SimpleNodeVisitor() {
196 @Override
197 public boolean enterVarNode(final VarNode varNode) {
198 statements.add(varNode.setInit(null));
199 return false;
200 }
201
202 @Override
203 public boolean enterFunctionNode(final FunctionNode functionNode) {
204 // Don't descend into nested functions
205 return false;
206 }
207 });
208 }
209
210 private static class UnaryNodeConstantEvaluator extends ConstantEvaluator<UnaryNode> {
211 UnaryNodeConstantEvaluator(final UnaryNode parent) {
212 super(parent);
213 }
214
215 @Override
216 protected LiteralNode<?> eval() {
217 final Node rhsNode = parent.getExpression();
218
219 if (!(rhsNode instanceof LiteralNode)) {
220 return null;
221 }
222
223 if (rhsNode instanceof ArrayLiteralNode) {
224 return null;
225 }
226
227 final LiteralNode<?> rhs = (LiteralNode<?>)rhsNode;
228 final Type rhsType = rhs.getType();
229 final boolean rhsInteger = rhsType.isInteger() || rhsType.isBoolean();
230
231 LiteralNode<?> literalNode;
232
233 switch (parent.tokenType()) {
234 case ADD:
235 if (rhsInteger) {
236 literalNode = LiteralNode.newInstance(token, finish, rhs.getInt32());
237 } else if (rhsType.isLong()) {
238 literalNode = LiteralNode.newInstance(token, finish, rhs.getLong());
239 } else {
240 literalNode = LiteralNode.newInstance(token, finish, rhs.getNumber());
241 }
242 break;
243 case SUB:
244 if (rhsInteger && rhs.getInt32() != 0) { // @see test/script/basic/minuszero.js
245 literalNode = LiteralNode.newInstance(token, finish, -rhs.getInt32());
246 } else if (rhsType.isLong() && rhs.getLong() != 0L) {
247 literalNode = LiteralNode.newInstance(token, finish, -rhs.getLong());
248 } else {
249 literalNode = LiteralNode.newInstance(token, finish, -rhs.getNumber());
250 }
251 break;
252 case NOT:
253 literalNode = LiteralNode.newInstance(token, finish, !rhs.getBoolean());
254 break;
255 case BIT_NOT:
256 literalNode = LiteralNode.newInstance(token, finish, ~rhs.getInt32());
257 break;
258 default:
259 return null;
260 }
261
262 return literalNode;
263 }
264 }
265
266 //TODO add AND and OR with one constant parameter (bitwise)
267 private static class BinaryNodeConstantEvaluator extends ConstantEvaluator<BinaryNode> {
268 BinaryNodeConstantEvaluator(final BinaryNode parent) {
269 super(parent);
270 }
271
272 @Override
273 protected LiteralNode<?> eval() {
274 LiteralNode<?> result;
275
276 result = reduceTwoLiterals();
277 if (result != null) {
278 return result;
279 }
280
281 result = reduceOneLiteral();
282 if (result != null) {
283 return result;
284 }
285
286 return null;
287 }
288
289 @SuppressWarnings("static-method")
290 private LiteralNode<?> reduceOneLiteral() {
291 //TODO handle patterns like AND, OR, numeric ops that can be strength reduced but not replaced by a single literal node etc
292 return null;
293 }
294
295 private LiteralNode<?> reduceTwoLiterals() {
296 if (!(parent.lhs() instanceof LiteralNode && parent.rhs() instanceof LiteralNode)) {
297 return null;
298 }
299
300 final LiteralNode<?> lhs = (LiteralNode<?>)parent.lhs();
301 final LiteralNode<?> rhs = (LiteralNode<?>)parent.rhs();
302
303 if (lhs instanceof ArrayLiteralNode || rhs instanceof ArrayLiteralNode) {
304 return null;
305 }
306
307 final Type widest = Type.widest(lhs.getType(), rhs.getType());
308
309 boolean isInteger = widest.isInteger();
310 final double value;
311
312 switch (parent.tokenType()) {
313 case DIV:
314 value = lhs.getNumber() / rhs.getNumber();
315 break;
316 case ADD:
317 if ((lhs.isString() || rhs.isNumeric()) && (rhs.isString() || rhs.isNumeric())) {
318 final Object res = ScriptRuntime.ADD(lhs.getObject(), rhs.getObject());
319 if (res instanceof Number) {
320 value = ((Number)res).doubleValue();
321 break;
322 }
323 assert res instanceof CharSequence : res + " was not a CharSequence, it was a " + res.getClass();
324 return LiteralNode.newInstance(token, finish, res.toString());
325 }
326 return null;
327 case MUL:
328 value = lhs.getNumber() * rhs.getNumber();
329 break;
330 case MOD:
331 value = lhs.getNumber() % rhs.getNumber();
332 break;
333 case SUB:
334 value = lhs.getNumber() - rhs.getNumber();
335 break;
336 case SHR:
337 final long result = JSType.toUint32(lhs.getInt32() >>> rhs.getInt32());
338 return LiteralNode.newInstance(token, finish, JSType.isRepresentableAsInt(result) ? (int) result : (double) result);
339 case SAR:
340 return LiteralNode.newInstance(token, finish, lhs.getInt32() >> rhs.getInt32());
341 case SHL:
342 return LiteralNode.newInstance(token, finish, lhs.getInt32() << rhs.getInt32());
343 case BIT_XOR:
344 return LiteralNode.newInstance(token, finish, lhs.getInt32() ^ rhs.getInt32());
345 case BIT_AND:
346 return LiteralNode.newInstance(token, finish, lhs.getInt32() & rhs.getInt32());
347 case BIT_OR:
348 return LiteralNode.newInstance(token, finish, lhs.getInt32() | rhs.getInt32());
349 case GE:
350 return LiteralNode.newInstance(token, finish, ScriptRuntime.GE(lhs.getObject(), rhs.getObject()));
351 case LE:
352 return LiteralNode.newInstance(token, finish, ScriptRuntime.LE(lhs.getObject(), rhs.getObject()));
353 case GT:
354 return LiteralNode.newInstance(token, finish, ScriptRuntime.GT(lhs.getObject(), rhs.getObject()));
355 case LT:
356 return LiteralNode.newInstance(token, finish, ScriptRuntime.LT(lhs.getObject(), rhs.getObject()));
357 case NE:
358 return LiteralNode.newInstance(token, finish, ScriptRuntime.NE(lhs.getObject(), rhs.getObject()));
359 case NE_STRICT:
360 return LiteralNode.newInstance(token, finish, ScriptRuntime.NE_STRICT(lhs.getObject(), rhs.getObject()));
361 case EQ:
362 return LiteralNode.newInstance(token, finish, ScriptRuntime.EQ(lhs.getObject(), rhs.getObject()));
363 case EQ_STRICT:
364 return LiteralNode.newInstance(token, finish, ScriptRuntime.EQ_STRICT(lhs.getObject(), rhs.getObject()));
365 default:
366 return null;
367 }
368
369 isInteger &= JSType.isStrictlyRepresentableAsInt(value);
370
371 if (isInteger) {
372 return LiteralNode.newInstance(token, finish, (int)value);
373 }
374
375 return LiteralNode.newInstance(token, finish, value);
376 }
377 }
378 }