1 /*
2 * Copyright (c) 2010, 2015, 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.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package jdk.vm.ci.code;
24
25 import java.util.*;
26
27 import jdk.vm.ci.meta.*;
28
29 /**
30 * Miscellaneous collection of utility methods used by {@code jdk.vm.ci.code} and its clients.
31 */
32 public class CodeUtil {
33
34 public static final String NEW_LINE = String.format("%n");
35
36 public static final int K = 1024;
37 public static final int M = 1024 * 1024;
38
39 public static boolean isOdd(int n) {
40 return (n & 1) == 1;
41 }
42
43 public static boolean isEven(int n) {
44 return (n & 1) == 0;
45 }
46
47 /**
48 * Checks whether the specified integer is a power of two.
49 *
50 * @param val the value to check
51 * @return {@code true} if the value is a power of two; {@code false} otherwise
52 */
53 public static boolean isPowerOf2(int val) {
54 return val > 0 && (val & val - 1) == 0;
55 }
56
57 /**
58 * Checks whether the specified long is a power of two.
59 *
60 * @param val the value to check
61 * @return {@code true} if the value is a power of two; {@code false} otherwise
62 */
63 public static boolean isPowerOf2(long val) {
64 return val > 0 && (val & val - 1) == 0;
65 }
66
67 /**
68 * Computes the log (base 2) of the specified integer, rounding down. (E.g {@code log2(8) = 3},
69 * {@code log2(21) = 4} )
70 *
71 * @param val the value
72 * @return the log base 2 of the value
73 */
74 public static int log2(int val) {
75 assert val > 0;
76 return (Integer.SIZE - 1) - Integer.numberOfLeadingZeros(val);
77 }
78
79 /**
80 * Computes the log (base 2) of the specified long, rounding down. (E.g {@code log2(8) = 3},
81 * {@code log2(21) = 4})
82 *
83 * @param val the value
84 * @return the log base 2 of the value
85 */
86 public static int log2(long val) {
87 assert val > 0;
88 return (Long.SIZE - 1) - Long.numberOfLeadingZeros(val);
89 }
90
91 /**
92 * Narrow an integer value to a given bit width, and return the result as a signed long.
93 *
94 * @param value the value
95 * @param resultBits the result bit width
96 * @return {@code value} interpreted as {@code resultBits} bit number, encoded as signed long
97 */
98 public static long narrow(long value, int resultBits) {
99 long ret = value & mask(resultBits);
100 return signExtend(ret, resultBits);
101 }
102
103 /**
104 * Sign extend an integer.
105 *
106 * @param value the input value
107 * @param inputBits the bit width of the input value
108 * @return a signed long with the same value as the signed {@code inputBits}-bit number
109 * {@code value}
110 */
111 public static long signExtend(long value, int inputBits) {
112 if (inputBits < 64) {
113 if ((value >>> (inputBits - 1) & 1) == 1) {
114 return value | (-1L << inputBits);
115 } else {
116 return value & ~(-1L << inputBits);
117 }
118 } else {
119 return value;
120 }
121 }
122
123 /**
124 * Zero extend an integer.
125 *
126 * @param value the input value
127 * @param inputBits the bit width of the input value
128 * @return an unsigned long with the same value as the unsigned {@code inputBits}-bit number
129 * {@code value}
130 */
131 public static long zeroExtend(long value, int inputBits) {
132 if (inputBits < 64) {
133 return value & ~(-1L << inputBits);
134 } else {
135 return value;
136 }
137 }
138
139 /**
140 * Convert an integer to long.
141 *
142 * @param value the input value
143 * @param inputBits the bit width of the input value
144 * @param unsigned whether the values should be interpreted as signed or unsigned
145 * @return a long with the same value as the {@code inputBits}-bit number {@code value}
146 */
147 public static long convert(long value, int inputBits, boolean unsigned) {
148 if (unsigned) {
149 return zeroExtend(value, inputBits);
150 } else {
151 return signExtend(value, inputBits);
152 }
153 }
154
155 /**
156 * Get a bitmask with the low {@code bits} bit set and the high {@code 64 - bits} bit clear.
157 */
158 public static long mask(int bits) {
159 assert 0 <= bits && bits <= 64;
160 if (bits == 64) {
161 return 0xffffffffffffffffL;
162 } else {
163 return (1L << bits) - 1;
164 }
165 }
166
167 /**
168 * Get the minimum value representable in a {@code bits} bit signed integer.
169 */
170 public static long minValue(int bits) {
171 assert 0 < bits && bits <= 64;
172 return -1L << (bits - 1);
173 }
174
175 /**
176 * Get the maximum value representable in a {@code bits} bit signed integer.
177 */
178 public static long maxValue(int bits) {
179 assert 0 < bits && bits <= 64;
180 return mask(bits - 1);
181 }
182
183 /**
184 * Formats the values in a frame as a tabulated string.
185 *
186 * @param frame
187 * @return the values in {@code frame} as a tabulated string
188 */
189 public static String tabulateValues(BytecodeFrame frame) {
190 int cols = Math.max(frame.numLocals, Math.max(frame.numStack, frame.numLocks));
191 assert cols > 0;
192 ArrayList<Object> cells = new ArrayList<>();
193 cells.add("");
194 for (int i = 0; i < cols; i++) {
195 cells.add(i);
196 }
197 cols++;
198 if (frame.numLocals != 0) {
199 cells.add("locals:");
200 cells.addAll(Arrays.asList(frame.values).subList(0, frame.numLocals));
201 cells.addAll(Collections.nCopies(cols - frame.numLocals - 1, ""));
202 }
203 if (frame.numStack != 0) {
204 cells.add("stack:");
205 cells.addAll(Arrays.asList(frame.values).subList(frame.numLocals, frame.numLocals + frame.numStack));
206 cells.addAll(Collections.nCopies(cols - frame.numStack - 1, ""));
207 }
208 if (frame.numLocks != 0) {
209 cells.add("locks:");
210 cells.addAll(Arrays.asList(frame.values).subList(frame.numLocals + frame.numStack, frame.values.length));
211 cells.addAll(Collections.nCopies(cols - frame.numLocks - 1, ""));
212 }
213 Object[] cellArray = cells.toArray();
214 for (int i = 0; i < cellArray.length; i++) {
215 if ((i % cols) != 0) {
216 cellArray[i] = "|" + cellArray[i];
217 }
218 }
219 return CodeUtil.tabulate(cellArray, cols, 1, 1);
220 }
221
222 /**
223 * Formats a given table as a string. The value of each cell is produced by
224 * {@link String#valueOf(Object)}.
225 *
226 * @param cells the cells of the table in row-major order
227 * @param cols the number of columns per row
228 * @param lpad the number of space padding inserted before each formatted cell value
229 * @param rpad the number of space padding inserted after each formatted cell value
230 * @return a string with one line per row and each column left-aligned
231 */
232 public static String tabulate(Object[] cells, int cols, int lpad, int rpad) {
233 int rows = (cells.length + (cols - 1)) / cols;
234 int[] colWidths = new int[cols];
235 for (int col = 0; col < cols; col++) {
236 for (int row = 0; row < rows; row++) {
237 int index = col + (row * cols);
238 if (index < cells.length) {
239 Object cell = cells[index];
240 colWidths[col] = Math.max(colWidths[col], String.valueOf(cell).length());
241 }
242 }
243 }
244 StringBuilder sb = new StringBuilder();
245 String nl = NEW_LINE;
246 for (int row = 0; row < rows; row++) {
247 for (int col = 0; col < cols; col++) {
248 int index = col + (row * cols);
249 if (index < cells.length) {
250 for (int i = 0; i < lpad; i++) {
251 sb.append(' ');
252 }
253 Object cell = cells[index];
254 String s = String.valueOf(cell);
255 int w = s.length();
256 sb.append(s);
257 while (w < colWidths[col]) {
258 sb.append(' ');
259 w++;
260 }
261 for (int i = 0; i < rpad; i++) {
262 sb.append(' ');
263 }
264 }
265 }
266 sb.append(nl);
267 }
268 return sb.toString();
269 }
270
271 /**
272 * Appends a formatted code position to a {@link StringBuilder}.
273 *
274 * @param sb the {@link StringBuilder} to append to
275 * @param pos the code position to format and append to {@code sb}
276 * @return the value of {@code sb}
277 */
278 public static StringBuilder append(StringBuilder sb, BytecodePosition pos) {
279 MetaUtil.appendLocation(sb.append("at "), pos.getMethod(), pos.getBCI());
280 if (pos.getCaller() != null) {
281 sb.append(NEW_LINE);
282 append(sb, pos.getCaller());
283 }
284 return sb;
285 }
286
287 /**
288 * Appends a formatted frame to a {@link StringBuilder}.
289 *
290 * @param sb the {@link StringBuilder} to append to
291 * @param frame the frame to format and append to {@code sb}
292 * @return the value of {@code sb}
293 */
294 public static StringBuilder append(StringBuilder sb, BytecodeFrame frame) {
295 MetaUtil.appendLocation(sb.append("at "), frame.getMethod(), frame.getBCI());
296 assert sb.charAt(sb.length() - 1) == ']';
297 sb.deleteCharAt(sb.length() - 1);
298 sb.append(", duringCall: ").append(frame.duringCall).append(", rethrow: ").append(frame.rethrowException).append(']');
299 if (frame.values != null && frame.values.length > 0) {
300 sb.append(NEW_LINE);
301 String table = tabulateValues(frame);
302 String[] rows = table.split(NEW_LINE);
303 for (int i = 0; i < rows.length; i++) {
304 String row = rows[i];
305 if (!row.trim().isEmpty()) {
306 sb.append(" ").append(row);
307 if (i != rows.length - 1) {
308 sb.append(NEW_LINE);
309 }
310 }
311 }
312 }
313 if (frame.caller() != null) {
314 sb.append(NEW_LINE);
315 append(sb, frame.caller());
316 } else if (frame.getCaller() != null) {
317 sb.append(NEW_LINE);
318 append(sb, frame.getCaller());
319 }
320 return sb;
321 }
322
323 public interface RefMapFormatter {
324
325 String formatStackSlot(int frameRefMapIndex);
326
327 String formatRegister(int regRefMapIndex);
328 }
329
330 /**
331 * Formats a location in a register reference map.
332 */
333 public static class DefaultRegFormatter implements RefMapFormatter {
334
335 private final Register[] registers;
336
337 public DefaultRegFormatter(Architecture arch) {
338 registers = new Register[arch.getRegisterReferenceMapSize()];
339 for (Register r : arch.getRegisters()) {
340 if (r.getReferenceMapIndex() >= 0) {
341 registers[r.getReferenceMapIndex()] = r;
342 }
343 }
344 }
345
346 public String formatStackSlot(int frameRefMapIndex) {
347 return null;
348 }
349
350 public String formatRegister(int regRefMapIndex) {
351 int i = regRefMapIndex;
352 int idx = 0;
353 while (registers[i] == null) {
354 i--;
355 idx++;
356 }
357 if (idx == 0) {
358 return registers[i].toString();
359 } else {
360 return String.format("%s+%d", registers[i].toString(), idx);
361 }
362 }
363 }
364
365 /**
366 * Formats a location present in a register or frame reference map.
367 */
368 public static class DefaultRefMapFormatter extends DefaultRegFormatter {
369
370 /**
371 * The size of a stack slot.
372 */
373 public final int slotSize;
374
375 /**
376 * The register used as the frame pointer.
377 */
378 public final Register fp;
379
380 /**
381 * The offset (in bytes) from the slot pointed to by {@link #fp} to the slot corresponding
382 * to bit 0 in the frame reference map.
383 */
384 public final int refMapToFPOffset;
385
386 public DefaultRefMapFormatter(Architecture arch, int slotSize, Register fp, int refMapToFPOffset) {
387 super(arch);
388 this.slotSize = slotSize;
389 this.fp = fp;
390 this.refMapToFPOffset = refMapToFPOffset;
391 }
392
393 @Override
394 public String formatStackSlot(int frameRefMapIndex) {
395 int refMapOffset = frameRefMapIndex * slotSize;
396 int fpOffset = refMapOffset + refMapToFPOffset;
397 if (fpOffset >= 0) {
398 return fp + "+" + fpOffset;
399 }
400 return fp.name + fpOffset;
401 }
402 }
403
404 public static class NumberedRefMapFormatter implements RefMapFormatter {
405
406 public String formatStackSlot(int frameRefMapIndex) {
407 return "s" + frameRefMapIndex;
408 }
409
410 public String formatRegister(int regRefMapIndex) {
411 return "r" + regRefMapIndex;
412 }
413 }
414
415 /**
416 * Appends a formatted debug info to a {@link StringBuilder}.
417 *
418 * @param sb the {@link StringBuilder} to append to
419 * @param info the debug info to format and append to {@code sb}
420 * @return the value of {@code sb}
421 */
422 public static StringBuilder append(StringBuilder sb, DebugInfo info, RefMapFormatter formatterArg) {
423 RefMapFormatter formatter = formatterArg;
424 if (formatter == null) {
425 formatter = new NumberedRefMapFormatter();
426 }
427 String nl = NEW_LINE;
428 ReferenceMap refMap = info.getReferenceMap();
429 if (refMap != null) {
430 sb.append(refMap.toString());
431 }
432 RegisterSaveLayout calleeSaveInfo = info.getCalleeSaveInfo();
433 if (calleeSaveInfo != null) {
434 sb.append("callee-save-info:").append(nl);
435 Map<Integer, Register> map = calleeSaveInfo.slotsToRegisters(true);
436 for (Map.Entry<Integer, Register> e : map.entrySet()) {
437 sb.append(" ").append(e.getValue()).append(" -> ").append(formatter.formatStackSlot(e.getKey())).append(nl);
438 }
439 }
440 BytecodeFrame frame = info.frame();
441 if (frame != null) {
442 append(sb, frame);
443 } else if (info.getBytecodePosition() != null) {
444 append(sb, info.getBytecodePosition());
445 }
446 return sb;
447 }
448
449 /**
450 * Create a calling convention from a {@link ResolvedJavaMethod}.
451 */
452 public static CallingConvention getCallingConvention(CodeCacheProvider codeCache, CallingConvention.Type type, ResolvedJavaMethod method, boolean stackOnly) {
453 Signature sig = method.getSignature();
454 JavaType retType = sig.getReturnType(null);
455 int sigCount = sig.getParameterCount(false);
456 JavaType[] argTypes;
457 int argIndex = 0;
458 if (!method.isStatic()) {
459 argTypes = new JavaType[sigCount + 1];
460 argTypes[argIndex++] = method.getDeclaringClass();
461 } else {
462 argTypes = new JavaType[sigCount];
463 }
464 for (int i = 0; i < sigCount; i++) {
465 argTypes[argIndex++] = sig.getParameterType(i, null);
466 }
467
468 RegisterConfig registerConfig = codeCache.getRegisterConfig();
469 return registerConfig.getCallingConvention(type, retType, argTypes, codeCache.getTarget(), stackOnly);
470 }
471 }