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 package jdk.nashorn.internal.codegen;
26
27 import java.io.Serializable;
28 import java.util.ArrayList;
29 import java.util.Arrays;
30 import java.util.BitSet;
31 import java.util.Iterator;
32 import java.util.List;
33 import java.util.ListIterator;
34 import jdk.nashorn.internal.codegen.types.Type;
35
36 /**
37 * Abstraction for labels, separating a label from the underlying
38 * byte code emitter. Also augmenting label with e.g. a name
39 * for easier debugging and reading code
40 *
41 * see -Dnashorn.codegen.debug, --log=codegen
42 */
43 public final class Label implements Serializable {
44 private static final long serialVersionUID = 1L;
45
46 //byte code generation evaluation type stack for consistency check
47 //and correct opcode selection. one per label as a label may be a
48 //join point
49 static final class Stack implements Cloneable {
50 static final int NON_LOAD = -1;
51
52 Type[] data;
53 int[] localLoads;
54 int sp;
55
56 List<Type> localVariableTypes;
57 int firstTemp; // index of the first temporary local variable
58 // Bitmap marking last slot belonging to a single symbol.
59 BitSet symbolBoundary;
60
61 Stack() {
62 data = new Type[8];
63 localLoads = new int[8];
64 localVariableTypes = new ArrayList<>(8);
65 symbolBoundary = new BitSet();
66 }
67
68 boolean isEmpty() {
69 return sp == 0;
70 }
71
72 int size() {
73 return sp;
74 }
75
76 void clear() {
77 sp = 0;
78 }
79
80 void push(final Type type) {
81 if (data.length == sp) {
82 final Type[] newData = new Type[sp * 2];
83 final int[] newLocalLoad = new int[sp * 2];
84 System.arraycopy(data, 0, newData, 0, sp);
85 System.arraycopy(localLoads, 0, newLocalLoad, 0, sp);
86 data = newData;
87 localLoads = newLocalLoad;
88 }
89 data[sp] = type;
90 localLoads[sp] = NON_LOAD;
91 sp++;
92 }
93
94 Type peek() {
95 return peek(0);
96 }
97
98 Type peek(final int n) {
99 final int pos = sp - 1 - n;
100 return pos < 0 ? null : data[pos];
101 }
102
103 /**
104 * Retrieve the top <code>count</code> types on the stack without modifying it.
105 *
106 * @param count number of types to return
107 * @return array of Types
108 */
109 Type[] getTopTypes(final int count) {
110 final Type[] topTypes = new Type[count];
111 System.arraycopy(data, sp - count, topTypes, 0, count);
112 return topTypes;
113 }
114
115 int[] getLocalLoads(final int from, final int to) {
116 final int count = to - from;
117 final int[] topLocalLoads = new int[count];
118 System.arraycopy(localLoads, from, topLocalLoads, 0, count);
119 return topLocalLoads;
120 }
121
122 /**
123 * Returns the number of used local variable slots, including all live stack-store temporaries.
124 * @return the number of used local variable slots, including all live stack-store temporaries.
125 */
126 int getUsedSlotsWithLiveTemporaries() {
127 // There are at least as many as are declared by the current blocks.
128 int usedSlots = firstTemp;
129 // Look at every load on the stack, and bump the number of used slots up by the temporaries seen there.
130 for(int i = sp; i-->0;) {
131 final int slot = localLoads[i];
132 if(slot != Label.Stack.NON_LOAD) {
133 final int afterSlot = slot + localVariableTypes.get(slot).getSlots();
134 if(afterSlot > usedSlots) {
135 usedSlots = afterSlot;
136 }
137 }
138 }
139 return usedSlots;
140 }
141
142 /**
143 *
144 * @param joinOrigin the stack from the other branch.
145 */
146 void joinFrom(final Stack joinOrigin, final boolean breakTarget) {
147 assert isStackCompatible(joinOrigin);
148 if(breakTarget) {
149 // As we're joining labels that can jump across block boundaries, the number of local variables can
150 // differ, and we should always respect the one having less variables.
151 firstTemp = Math.min(firstTemp, joinOrigin.firstTemp);
152 } else {
153 assert firstTemp == joinOrigin.firstTemp;
154 }
155 final int[] otherLoads = joinOrigin.localLoads;
156 int firstDeadTemp = firstTemp;
157 for(int i = 0; i < sp; ++i) {
158 final int localLoad = localLoads[i];
159 if(localLoad != otherLoads[i]) {
160 localLoads[i] = NON_LOAD;
161 } else if(localLoad >= firstDeadTemp) {
162 firstDeadTemp = localLoad + localVariableTypes.get(localLoad).getSlots();
163 }
164 }
165 // Eliminate dead temporaries
166 undefineLocalVariables(firstDeadTemp, false);
167 assert isVariablePartitioningEqual(joinOrigin, firstDeadTemp);
168 mergeVariableTypes(joinOrigin, firstDeadTemp);
169 }
170
171 private void mergeVariableTypes(final Stack joinOrigin, final int toSlot) {
172 final ListIterator<Type> it1 = localVariableTypes.listIterator();
173 final Iterator<Type> it2 = joinOrigin.localVariableTypes.iterator();
174
175 for(int i = 0; i < toSlot; ++i) {
176 final Type thisType = it1.next();
177 final Type otherType = it2.next();
178 if(otherType == Type.UNKNOWN) {
179 // Variables that are <unknown> on the other branch will become <unknown> here too.
180 it1.set(Type.UNKNOWN);
181 } else if (thisType != otherType) {
182 if(thisType.isObject() && otherType.isObject()) {
183 // different object types are merged into Object.
184 // TODO: maybe find most common superclass?
185 it1.set(Type.OBJECT);
186 } else {
187 assert thisType == Type.UNKNOWN;
188 }
189 }
190 }
191 }
192
193 void joinFromTry(final Stack joinOrigin) {
194 // As we're joining labels that can jump across block boundaries, the number of local variables can
195 // differ, and we should always respect the one having less variables.
196 firstTemp = Math.min(firstTemp, joinOrigin.firstTemp);
197 assert isVariablePartitioningEqual(joinOrigin, firstTemp);
198 mergeVariableTypes(joinOrigin, firstTemp);
199 }
200
201 private int getFirstDeadLocal(final List<Type> types) {
202 int i = types.size();
203 for(final ListIterator<Type> it = types.listIterator(i);
204 it.hasPrevious() && it.previous() == Type.UNKNOWN;
205 --i) {
206 // no body
207 }
208
209 // Respect symbol boundaries; we never chop off half a symbol's storage
210 while(!symbolBoundary.get(i - 1)) {
211 ++i;
212 }
213 return i;
214 }
215
216 private boolean isStackCompatible(final Stack other) {
217 if (sp != other.sp) {
218 return false;
219 }
220 for (int i = 0; i < sp; i++) {
221 if (!data[i].isEquivalentTo(other.data[i])) {
222 return false;
223 }
224 }
225 return true;
226 }
227
228 private boolean isVariablePartitioningEqual(final Stack other, final int toSlot) {
229 // No difference in the symbol boundaries before the toSlot
230 final BitSet diff = other.getSymbolBoundaryCopy();
231 diff.xor(symbolBoundary);
232 return diff.previousSetBit(toSlot - 1) == -1;
233 }
234
235 void markDeadLocalVariables(final int fromSlot, final int slotCount) {
236 final int localCount = localVariableTypes.size();
237 if(fromSlot >= localCount) {
238 return;
239 }
240 final int toSlot = Math.min(fromSlot + slotCount, localCount);
241 invalidateLocalLoadsOnStack(fromSlot, toSlot);
242 for(int i = fromSlot; i < toSlot; ++i) {
243 localVariableTypes.set(i, Type.UNKNOWN);
244 }
245 }
246
247 @SuppressWarnings("unchecked")
248 List<Type> getLocalVariableTypesCopy() {
249 return (List<Type>)((ArrayList<Type>)localVariableTypes).clone();
250 }
251
252 BitSet getSymbolBoundaryCopy() {
253 return (BitSet)symbolBoundary.clone();
254 }
255
256 /**
257 * Returns a list of local variable slot types, but for those symbols that have multiple values, only the slot
258 * holding the widest type is marked as live.
259 * @return a list of widest local variable slot types.
260 */
261 List<Type> getWidestLiveLocals(final List<Type> lvarTypes) {
262 final List<Type> widestLiveLocals = new ArrayList<>(lvarTypes);
263 boolean keepNextValue = true;
264 final int size = widestLiveLocals.size();
265 for(int i = size - 1; i-- > 0;) {
266 if(symbolBoundary.get(i)) {
267 keepNextValue = true;
268 }
269 final Type t = widestLiveLocals.get(i);
270 if(t != Type.UNKNOWN) {
271 if(keepNextValue) {
272 if(t != Type.SLOT_2) {
273 keepNextValue = false;
274 }
275 } else {
276 widestLiveLocals.set(i, Type.UNKNOWN);
277 }
278 }
279 }
280 widestLiveLocals.subList(Math.max(getFirstDeadLocal(widestLiveLocals), firstTemp), widestLiveLocals.size()).clear();
281 return widestLiveLocals;
282 }
283
284 String markSymbolBoundariesInLvarTypesDescriptor(final String lvarDescriptor) {
285 final char[] chars = lvarDescriptor.toCharArray();
286 int j = 0;
287 for(int i = 0; i < chars.length; ++i) {
288 final char c = chars[i];
289 final int nextj = j + CodeGeneratorLexicalContext.getTypeForSlotDescriptor(c).getSlots();
290 if(!symbolBoundary.get(nextj - 1)) {
291 chars[i] = Character.toLowerCase(c);
292 }
293 j = nextj;
294 }
295 return new String(chars);
296 }
297
298 Type pop() {
299 assert sp > 0;
300 return data[--sp];
301 }
302
303 @Override
304 public Stack clone() {
305 try {
306 final Stack clone = (Stack)super.clone();
307 clone.data = data.clone();
308 clone.localLoads = localLoads.clone();
309 clone.symbolBoundary = getSymbolBoundaryCopy();
310 clone.localVariableTypes = getLocalVariableTypesCopy();
311 return clone;
312 } catch(final CloneNotSupportedException e) {
313 throw new AssertionError("", e);
314 }
315 }
316
317 private Stack cloneWithEmptyStack() {
318 final Stack stack = clone();
319 stack.sp = 0;
320 return stack;
321 }
322
323 int getTopLocalLoad() {
324 return localLoads[sp - 1];
325 }
326
327 void markLocalLoad(final int slot) {
328 localLoads[sp - 1] = slot;
329 }
330
331 /**
332 * Performs various bookeeping when a value is stored in a local variable slot.
333 * @param slot the slot written to
334 * @param onlySymbolLiveValue if true, this is the symbol's only live value, and other values of the symbol
335 * should be marked dead
336 * @param type the type written to the slot
337 */
338 void onLocalStore(final Type type, final int slot, final boolean onlySymbolLiveValue) {
339 if(onlySymbolLiveValue) {
340 final int fromSlot = slot == 0 ? 0 : (symbolBoundary.previousSetBit(slot - 1) + 1);
341 final int toSlot = symbolBoundary.nextSetBit(slot) + 1;
342 for(int i = fromSlot; i < toSlot; ++i) {
343 localVariableTypes.set(i, Type.UNKNOWN);
344 }
345 invalidateLocalLoadsOnStack(fromSlot, toSlot);
346 } else {
347 invalidateLocalLoadsOnStack(slot, slot + type.getSlots());
348 }
349
350 localVariableTypes.set(slot, type);
351 if(type.isCategory2()) {
352 localVariableTypes.set(slot + 1, Type.SLOT_2);
353 }
354 }
355
356 /**
357 * Given a slot range, invalidate knowledge about local loads on stack from these slots (because they're being
358 * killed).
359 * @param fromSlot first slot, inclusive.
360 * @param toSlot last slot, exclusive.
361 */
362 private void invalidateLocalLoadsOnStack(final int fromSlot, final int toSlot) {
363 for(int i = 0; i < sp; ++i) {
364 final int localLoad = localLoads[i];
365 if(localLoad >= fromSlot && localLoad < toSlot) {
366 localLoads[i] = NON_LOAD;
367 }
368 }
369 }
370
371 /**
372 * Marks a range of slots as belonging to a defined local variable. The slots will start out with no live value
373 * in them.
374 * @param fromSlot first slot, inclusive.
375 * @param toSlot last slot, exclusive.
376 */
377 void defineBlockLocalVariable(final int fromSlot, final int toSlot) {
378 defineLocalVariable(fromSlot, toSlot);
379 assert firstTemp < toSlot;
380 firstTemp = toSlot;
381 }
382
383 /**
384 * Defines a new temporary local variable and returns its allocated index.
385 * @param width the required width (in slots) for the new variable.
386 * @return the bytecode slot index where the newly allocated local begins.
387 */
388 int defineTemporaryLocalVariable(final int width) {
389 final int fromSlot = getUsedSlotsWithLiveTemporaries();
390 defineLocalVariable(fromSlot, fromSlot + width);
391 return fromSlot;
392 }
393
394 /**
395 * Marks a range of slots as belonging to a defined temporary local variable. The slots will start out with no
396 * live value in them.
397 * @param fromSlot first slot, inclusive.
398 * @param toSlot last slot, exclusive.
399 */
400 void defineTemporaryLocalVariable(final int fromSlot, final int toSlot) {
401 defineLocalVariable(fromSlot, toSlot);
402 }
403
404 private void defineLocalVariable(final int fromSlot, final int toSlot) {
405 assert !hasLoadsOnStack(fromSlot, toSlot);
406 assert fromSlot < toSlot;
407 symbolBoundary.clear(fromSlot, toSlot - 1);
408 symbolBoundary.set(toSlot - 1);
409 final int lastExisting = Math.min(toSlot, localVariableTypes.size());
410 for(int i = fromSlot; i < lastExisting; ++i) {
411 localVariableTypes.set(i, Type.UNKNOWN);
412 }
413 for(int i = lastExisting; i < toSlot; ++i) {
414 localVariableTypes.add(i, Type.UNKNOWN);
415 }
416 }
417
418 /**
419 * Undefines all local variables past the specified slot.
420 * @param fromSlot the first slot to be undefined
421 * @param canTruncateSymbol if false, the fromSlot must be either the first slot of a symbol, or the first slot
422 * after the last symbol. If true, the fromSlot can be in the middle of the storage area for a symbol. This
423 * should be used with care - it is only meant for use in optimism exception handlers.
424 */
425 void undefineLocalVariables(final int fromSlot, final boolean canTruncateSymbol) {
426 final int lvarCount = localVariableTypes.size();
427 assert lvarCount == symbolBoundary.length();
428 assert !hasLoadsOnStack(fromSlot, lvarCount);
429 if(canTruncateSymbol) {
430 if(fromSlot > 0) {
431 symbolBoundary.set(fromSlot - 1);
432 }
433 } else {
434 assert fromSlot == 0 || symbolBoundary.get(fromSlot - 1);
435 }
436 if(fromSlot < lvarCount) {
437 symbolBoundary.clear(fromSlot, lvarCount);
438 localVariableTypes.subList(fromSlot, lvarCount).clear();
439 }
440 firstTemp = Math.min(fromSlot, firstTemp);
441 assert symbolBoundary.length() == localVariableTypes.size();
442 assert symbolBoundary.length() == fromSlot;
443 }
444
445 private void markAsOptimisticCatchHandler(final int liveLocalCount) {
446 // Live temporaries that are no longer on stack are undefined
447 undefineLocalVariables(liveLocalCount, true);
448 // Temporaries are promoted
449 firstTemp = liveLocalCount;
450 // No trailing undefined values
451 localVariableTypes.subList(firstTemp, localVariableTypes.size()).clear();
452 assert symbolBoundary.length() == firstTemp;
453 // Generalize all reference types to Object, and promote boolean to int
454 for(final ListIterator<Type> it = localVariableTypes.listIterator(); it.hasNext();) {
455 final Type type = it.next();
456 if(type == Type.BOOLEAN) {
457 it.set(Type.INT);
458 } else if(type.isObject() && type != Type.OBJECT) {
459 it.set(Type.OBJECT);
460 }
461 }
462 }
463
464 /**
465 * Returns true if any loads on the stack come from the specified slot range.
466 * @param fromSlot start of the range (inclusive)
467 * @param toSlot end of the range (exclusive)
468 * @return true if any loads on the stack come from the specified slot range.
469 */
470 boolean hasLoadsOnStack(final int fromSlot, final int toSlot) {
471 for(int i = 0; i < sp; ++i) {
472 final int load = localLoads[i];
473 if(load >= fromSlot && load < toSlot) {
474 return true;
475 }
476 }
477 return false;
478 }
479
480 @Override
481 public String toString() {
482 return "stack=" + Arrays.toString(Arrays.copyOf(data, sp))
483 + ", symbolBoundaries=" + String.valueOf(symbolBoundary)
484 + ", firstTemp=" + firstTemp
485 + ", localTypes=" + String.valueOf(localVariableTypes)
486 ;
487 }
488 }
489
490 /** Next id for debugging purposes, remove if footprint becomes unmanageable */
491 private static int nextId = 0;
492
493 /** Name of this label */
494 private final String name;
495
496 /** Type stack at this label */
497 private transient Label.Stack stack;
498
499 /** ASM representation of this label */
500 private transient jdk.internal.org.objectweb.asm.Label label;
501
502 /** Id for debugging purposes, remove if footprint becomes unmanageable */
503 private final int id;
504
505 /** Is this label reachable (anything ever jumped to it)? */
506 private transient boolean reachable;
507
508 private transient boolean breakTarget;
509
510 /**
511 * Constructor
512 *
513 * @param name name of this label
514 */
515 public Label(final String name) {
516 super();
517 this.name = name;
518 this.id = nextId++;
519 }
520
521 /**
522 * Copy constructor
523 *
524 * @param label a label to clone
525 */
526 public Label(final Label label) {
527 super();
528 this.name = label.name;
529 this.id = label.id;
530 }
531
532 jdk.internal.org.objectweb.asm.Label getLabel() {
533 if (this.label == null) {
534 this.label = new jdk.internal.org.objectweb.asm.Label();
535 }
536 return label;
537 }
538
539 Label.Stack getStack() {
540 return stack;
541 }
542
543 void joinFrom(final Label.Stack joinOrigin) {
544 this.reachable = true;
545 if(stack == null) {
546 stack = joinOrigin.clone();
547 } else {
548 stack.joinFrom(joinOrigin, breakTarget);
549 }
550 }
551
552 void joinFromTry(final Label.Stack joinOrigin, final boolean isOptimismHandler) {
553 this.reachable = true;
554 if (stack == null) {
555 if(!isOptimismHandler) {
556 stack = joinOrigin.cloneWithEmptyStack();
557 // Optimism handler needs temporaries to remain live, others don't.
558 stack.undefineLocalVariables(stack.firstTemp, false);
559 }
560 } else {
561 assert !isOptimismHandler;
562 stack.joinFromTry(joinOrigin);
563 }
564 }
565
566 void markAsBreakTarget() {
567 breakTarget = true;
568 }
569
570 boolean isBreakTarget() {
571 return breakTarget;
572 }
573
574 void onCatch() {
575 if(stack != null) {
576 stack = stack.cloneWithEmptyStack();
577 }
578 }
579 void markAsOptimisticCatchHandler(final Label.Stack currentStack, final int liveLocalCount) {
580 stack = currentStack.cloneWithEmptyStack();
581 stack.markAsOptimisticCatchHandler(liveLocalCount);
582 }
583
584 void markAsOptimisticContinuationHandlerFor(final Label afterConsumeStackLabel) {
585 stack = afterConsumeStackLabel.stack.cloneWithEmptyStack();
586 }
587
588 boolean isReachable() {
589 return reachable;
590 }
591
592 boolean isAfter(final Label other) {
593 return label.getOffset() > other.label.getOffset();
594 }
595
596 private String str;
597
598 @Override
599 public String toString() {
600 if (str == null) {
601 str = name + '_' + id;
602 }
603 return str;
604 }
605 }