001/*
002 * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package jdk.internal.jvmci.code;
024
025import java.util.*;
026
027import jdk.internal.jvmci.meta.*;
028
029/**
030 * Miscellaneous collection of utility methods used by {@code jdk.internal.jvmci.code} and its
031 * clients.
032 */
033public class CodeUtil {
034
035    public static final String NEW_LINE = String.format("%n");
036
037    public static final int K = 1024;
038    public static final int M = 1024 * 1024;
039
040    public static boolean isOdd(int n) {
041        return (n & 1) == 1;
042    }
043
044    public static boolean isEven(int n) {
045        return (n & 1) == 0;
046    }
047
048    /**
049     * Checks whether the specified integer is a power of two.
050     *
051     * @param val the value to check
052     * @return {@code true} if the value is a power of two; {@code false} otherwise
053     */
054    public static boolean isPowerOf2(int val) {
055        return val > 0 && (val & val - 1) == 0;
056    }
057
058    /**
059     * Checks whether the specified long is a power of two.
060     *
061     * @param val the value to check
062     * @return {@code true} if the value is a power of two; {@code false} otherwise
063     */
064    public static boolean isPowerOf2(long val) {
065        return val > 0 && (val & val - 1) == 0;
066    }
067
068    /**
069     * Computes the log (base 2) of the specified integer, rounding down. (E.g {@code log2(8) = 3},
070     * {@code log2(21) = 4} )
071     *
072     * @param val the value
073     * @return the log base 2 of the value
074     */
075    public static int log2(int val) {
076        assert val > 0;
077        return (Integer.SIZE - 1) - Integer.numberOfLeadingZeros(val);
078    }
079
080    /**
081     * Computes the log (base 2) of the specified long, rounding down. (E.g {@code log2(8) = 3},
082     * {@code log2(21) = 4})
083     *
084     * @param val the value
085     * @return the log base 2 of the value
086     */
087    public static int log2(long val) {
088        assert val > 0;
089        return (Long.SIZE - 1) - Long.numberOfLeadingZeros(val);
090    }
091
092    /**
093     * Narrow an integer value to a given bit width, and return the result as a signed long.
094     *
095     * @param value the value
096     * @param resultBits the result bit width
097     * @return {@code value} interpreted as {@code resultBits} bit number, encoded as signed long
098     */
099    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}