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