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