2668N/A/*
2668N/A * Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved.
2668N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
2668N/A *
2668N/A * This code is free software; you can redistribute it and/or modify it
2668N/A * under the terms of the GNU General Public License version 2 only, as
2668N/A * published by the Free Software Foundation. Oracle designates this
2668N/A * particular file as subject to the "Classpath" exception as provided
2668N/A * by Oracle in the LICENSE file that accompanied this code.
2668N/A *
2668N/A * This code is distributed in the hope that it will be useful, but WITHOUT
2668N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
2668N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
2668N/A * version 2 for more details (a copy is included in the LICENSE file that
2668N/A * accompanied this code).
2668N/A *
2668N/A * You should have received a copy of the GNU General Public License version
2668N/A * 2 along with this work; if not, write to the Free Software Foundation,
2668N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
2668N/A *
2668N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
2668N/A * or visit www.oracle.com if you need additional information or have any
2668N/A * questions.
2668N/A */
2668N/Apackage xmlkit; // -*- mode: java; indent-tabs-mode: nil -*-
2668N/A
2668N/Aimport xmlkit.XMLKit.Element;
2668N/Aimport java.util.HashMap;
2668N/A/*
2668N/A * @author jrose
2668N/A */
2668N/Aabstract class InstructionAssembler extends InstructionSyntax {
2668N/A
2668N/A InstructionAssembler() {
2668N/A }
2668N/A
2668N/A public static String assemble(Element instructions, String pcAttrName,
2668N/A ClassSyntax.GetCPIndex getCPI) {
2668N/A int insCount = instructions.size();
2668N/A Element[] insElems = new Element[insCount];
2668N/A int[] elemToIndexMap;
2668N/A int[] insLocs;
2668N/A byte[] ops = new byte[insCount];
2668N/A int[] operands = new int[insCount];
2668N/A boolean[] isWide = new boolean[insCount];
2668N/A int[] branches;
2668N/A int[] branchInsLocs;
2668N/A HashMap<String, String> labels = new HashMap<String, String>();
2668N/A
2668N/A final int WIDE = 0xc4;
2668N/A final int GOTO = 0xa7;
2668N/A final int GOTO_W = 0xc8;
2668N/A final int GOTO_LEN = 3;
2668N/A final int GOTO_W_LEN = 5;
2668N/A assert ("wide".equals(bcNames[WIDE]));
2668N/A assert ("goto".equals(bcNames[GOTO]));
2668N/A assert ("goto_w".equals(bcNames[GOTO_W]));
2668N/A assert (bcFormats[GOTO].length() == GOTO_LEN);
2668N/A assert (bcFormats[GOTO_W].length() == GOTO_W_LEN);
2668N/A
2668N/A // Unpack instructions into temp. arrays, and find branches and labels.
2668N/A {
2668N/A elemToIndexMap = (pcAttrName != null) ? new int[insCount] : null;
2668N/A int[] buffer = operands;
2668N/A int id = 0;
2668N/A int branchCount = 0;
2668N/A for (int i = 0; i < insCount; i++) {
2668N/A Element ins = (Element) instructions.get(i);
2668N/A if (elemToIndexMap != null) {
2668N/A elemToIndexMap[i] = (ins.getAttr(pcAttrName) != null ? id : -1);
2668N/A }
2668N/A String lab = ins.getAttr("pc");
2668N/A if (lab != null) {
2668N/A labels.put(lab, String.valueOf(id));
2668N/A }
2668N/A int op = opCode(ins.getName());
2668N/A if (op < 0) {
2668N/A assert (ins.getAttr(pcAttrName) != null
2668N/A || ins.getName().equals("label"));
2668N/A continue; // delete PC holder element
2668N/A }
2668N/A if (op == WIDE) { //0xc4
2668N/A isWide[id] = true; // force wide format
2668N/A continue;
2668N/A }
2668N/A if (bcFormats[op].indexOf('o') >= 0) {
2668N/A buffer[branchCount++] = id;
2668N/A }
2668N/A if (bcFormats[op] == bcWideFormats[op]) {
2668N/A isWide[id] = false;
2668N/A }
2668N/A insElems[id] = ins;
2668N/A ops[id] = (byte) op;
2668N/A id++;
2668N/A }
2668N/A insCount = id; // maybe we deleted some wide prefixes, etc.
2668N/A branches = new int[branchCount + 1];
2668N/A System.arraycopy(buffer, 0, branches, 0, branchCount);
2668N/A branches[branchCount] = -1; // sentinel
2668N/A }
2668N/A
2668N/A // Compute instruction sizes. These sizes are final,
2668N/A // except for branch instructions, which may need lengthening.
2668N/A // Some instructions (ldc, bipush, iload, iinc) are automagically widened.
2668N/A insLocs = new int[insCount + 1];
2668N/A int loc = 0;
2668N/A for (int bn = 0, id = 0; id < insCount; id++) {
2668N/A insLocs[id] = loc;
2668N/A Element ins = insElems[id];
2668N/A int op = ops[id] & 0xFF;
2668N/A String format = opFormat(op, isWide[id]);
2668N/A // Make sure operands fit within the given format.
2668N/A for (int j = 1, jlimit = format.length(); j < jlimit; j++) {
2668N/A char fc = format.charAt(j);
2668N/A int x = 0;
2668N/A switch (fc) {
2668N/A case 'l':
2668N/A x = (int) ins.getAttrLong("loc");
2668N/A assert (x >= 0);
2668N/A if (x > 0xFF && !isWide[id]) {
2668N/A isWide[id] = true;
2668N/A format = opFormat(op, isWide[id]);
2668N/A }
2668N/A assert (x <= 0xFFFF);
2668N/A break;
2668N/A case 'k':
2668N/A char fc2 = format.charAt(Math.min(j + 1, format.length() - 1));
2668N/A x = getCPIndex(ins, fc2, getCPI);
2668N/A if (x > 0xFF && j == jlimit - 1) {
2668N/A assert (op == 0x12); //ldc
2668N/A ops[id] = (byte) (op = 0x13); //ldc_w
2668N/A format = opFormat(op);
2668N/A }
2668N/A assert (x <= 0xFFFF);
2668N/A j++; // skip type-of-constant marker
2668N/A break;
2668N/A case 'x':
2668N/A x = (int) ins.getAttrLong("num");
2668N/A assert (x >= 0 && x <= ((j == jlimit - 1) ? 0xFF : 0xFFFF));
2668N/A break;
2668N/A case 's':
2668N/A x = (int) ins.getAttrLong("num");
2668N/A if (x != (byte) x && j == jlimit - 1) {
2668N/A switch (op) {
2668N/A case 0x10: //bipush
2668N/A ops[id] = (byte) (op = 0x11); //sipush
2668N/A break;
2668N/A case 0x84: //iinc
2668N/A isWide[id] = true;
2668N/A format = opFormat(op, isWide[id]);
2668N/A break;
2668N/A default:
2668N/A assert (false); // cannot lengthen
2668N/A }
2668N/A }
2668N/A // unsign the value now, to make later steps clearer
2668N/A if (j == jlimit - 1) {
2668N/A assert (x == (byte) x);
2668N/A x = x & 0xFF;
2668N/A } else {
2668N/A assert (x == (short) x);
2668N/A x = x & 0xFFFF;
2668N/A }
2668N/A break;
2668N/A case 'o':
2668N/A assert (branches[bn] == id);
2668N/A bn++;
2668N/A // make local copies of the branches, and fix up labels
2668N/A insElems[id] = ins = new Element(ins);
2668N/A String newLab = labels.get(ins.getAttr("lab"));
2668N/A assert (newLab != null);
2668N/A ins.setAttr("lab", newLab);
2668N/A int prevCas = 0;
2668N/A int k = 0;
2668N/A for (Element cas : ins.elements()) {
2668N/A assert (cas.getName().equals("Case"));
2668N/A ins.set(k++, cas = new Element(cas));
2668N/A newLab = labels.get(cas.getAttr("lab"));
2668N/A assert (newLab != null);
2668N/A cas.setAttr("lab", newLab);
2668N/A int thisCas = (int) cas.getAttrLong("num");
2668N/A assert (op == 0xab
2668N/A || op == 0xaa && (k == 0 || thisCas == prevCas + 1));
2668N/A prevCas = thisCas;
2668N/A }
2668N/A break;
2668N/A case 't':
2668N/A // switch table is represented as Switch.Case sub-elements
2668N/A break;
2668N/A default:
2668N/A assert (false);
2668N/A }
2668N/A operands[id] = x; // record operand (last if there are 2)
2668N/A // skip redundant chars
2668N/A while (j + 1 < jlimit && format.charAt(j + 1) == fc) {
2668N/A ++j;
2668N/A }
2668N/A }
2668N/A
2668N/A switch (op) {
2668N/A case 0xaa: //tableswitch
2668N/A loc = switchBase(loc);
2668N/A loc += 4 * (3 + ins.size());
2668N/A break;
2668N/A case 0xab: //lookupswitch
2668N/A loc = switchBase(loc);
2668N/A loc += 4 * (2 + 2 * ins.size());
2668N/A break;
2668N/A default:
2668N/A if (isWide[id]) {
2668N/A loc++; // 'wide' opcode prefix
2668N/A }
2668N/A loc += format.length();
2668N/A break;
2668N/A }
2668N/A }
2668N/A insLocs[insCount] = loc;
2668N/A
2668N/A // compute branch offsets, and see if any branches need expansion
2668N/A for (int maxTries = 9, tries = 0;; ++tries) {
2668N/A boolean overflowing = false;
2668N/A boolean[] branchExpansions = null;
2668N/A for (int bn = 0; bn < branches.length - 1; bn++) {
2668N/A int id = branches[bn];
2668N/A Element ins = insElems[id];
2668N/A int insSize = insLocs[id + 1] - insLocs[id];
2668N/A int origin = insLocs[id];
2668N/A int target = insLocs[(int) ins.getAttrLong("lab")];
2668N/A int offset = target - origin;
2668N/A operands[id] = offset;
2668N/A //System.out.println("branch id="+id+" len="+insSize+" to="+target+" offset="+offset);
2668N/A assert (insSize == GOTO_LEN || insSize == GOTO_W_LEN || ins.getName().indexOf("switch") > 0);
2668N/A boolean thisOverflow = (insSize == GOTO_LEN && (offset != (short) offset));
2668N/A if (thisOverflow && !overflowing) {
2668N/A overflowing = true;
2668N/A branchExpansions = new boolean[branches.length];
2668N/A }
2668N/A if (thisOverflow || tries == maxTries - 1) {
2668N/A // lengthen the branch
2668N/A assert (!(thisOverflow && isWide[id]));
2668N/A isWide[id] = true;
2668N/A branchExpansions[bn] = true;
2668N/A }
2668N/A }
2668N/A if (!overflowing) {
2668N/A break; // done, usually on first try
2668N/A }
2668N/A assert (tries <= maxTries);
2668N/A
2668N/A // Walk over all instructions, expanding branches and updating locations.
2668N/A int fixup = 0;
2668N/A for (int bn = 0, id = 0; id < insCount; id++) {
2668N/A insLocs[id] += fixup;
2668N/A if (branches[bn] == id) {
2668N/A int op = ops[id] & 0xFF;
2668N/A int wop;
2668N/A boolean invert;
2668N/A if (branchExpansions[bn]) {
2668N/A switch (op) {
2668N/A case GOTO: //0xa7
2668N/A wop = GOTO_W; //0xc8
2668N/A invert = false;
2668N/A break;
2668N/A case 0xa8: //jsr
2668N/A wop = 0xc9; //jsr_w
2668N/A invert = false;
2668N/A break;
2668N/A default:
2668N/A wop = invertBranchOp(op);
2668N/A invert = true;
2668N/A break;
2668N/A }
2668N/A assert (op != wop);
2668N/A ops[id] = (byte) wop;
2668N/A isWide[id] = invert;
2668N/A if (invert) {
2668N/A fixup += GOTO_W_LEN; //branch around a wide goto
2668N/A } else {
2668N/A fixup += (GOTO_W_LEN - GOTO_LEN);
2668N/A }
2668N/A // done expanding: ops and isWide reflect the decision
2668N/A }
2668N/A bn++;
2668N/A }
2668N/A }
2668N/A insLocs[insCount] += fixup;
2668N/A }
2668N/A // we know the layout now
2668N/A
2668N/A // notify the caller of offsets, if requested
2668N/A if (elemToIndexMap != null) {
2668N/A for (int i = 0; i < elemToIndexMap.length; i++) {
2668N/A int id = elemToIndexMap[i];
2668N/A if (id >= 0) {
2668N/A Element ins = (Element) instructions.get(i);
2668N/A ins.setAttr(pcAttrName, "" + insLocs[id]);
2668N/A }
2668N/A }
2668N/A elemToIndexMap = null; // release the pointer
2668N/A }
2668N/A
2668N/A // output the bytes
2668N/A StringBuffer sbuf = new StringBuffer(insLocs[insCount]);
2668N/A for (int bn = 0, id = 0; id < insCount; id++) {
2668N/A //System.out.println("output id="+id+" loc="+insLocs[id]+" len="+(insLocs[id+1]-insLocs[id])+" #sbuf="+sbuf.length());
2668N/A assert (sbuf.length() == insLocs[id]);
2668N/A Element ins;
2668N/A int pc = insLocs[id];
2668N/A int nextpc = insLocs[id + 1];
2668N/A int op = ops[id] & 0xFF;
2668N/A int opnd = operands[id];
2668N/A String format;
2668N/A if (branches[bn] == id) {
2668N/A bn++;
2668N/A sbuf.append((char) op);
2668N/A if (isWide[id]) {
2668N/A // emit <ifop lab=1f> <goto_w target> <label pc=1f>
2668N/A int target = pc + opnd;
2668N/A putInt(sbuf, nextpc - pc, -2);
2668N/A assert (sbuf.length() == pc + GOTO_LEN);
2668N/A sbuf.append((char) GOTO_W);
2668N/A putInt(sbuf, target - (pc + GOTO_LEN), 4);
2668N/A } else if (op == 0xaa || //tableswitch
2668N/A op == 0xab) { //lookupswitch
2668N/A ins = insElems[id];
2668N/A for (int pad = switchBase(pc) - (pc + 1); pad > 0; pad--) {
2668N/A sbuf.append((char) 0);
2668N/A }
2668N/A assert (pc + opnd == insLocs[(int) ins.getAttrLong("lab")]);
2668N/A putInt(sbuf, opnd, 4); // default label
2668N/A if (op == 0xaa) { //tableswitch
2668N/A Element cas0 = (Element) ins.get(0);
2668N/A int lowCase = (int) cas0.getAttrLong("num");
2668N/A Element casN = (Element) ins.get(ins.size() - 1);
2668N/A int highCase = (int) casN.getAttrLong("num");
2668N/A assert (highCase - lowCase + 1 == ins.size());
2668N/A putInt(sbuf, lowCase, 4);
2668N/A putInt(sbuf, highCase, 4);
2668N/A int caseForAssert = lowCase;
2668N/A for (Element cas : ins.elements()) {
2668N/A int target = insLocs[(int) cas.getAttrLong("lab")];
2668N/A assert (cas.getAttrLong("num") == caseForAssert++);
2668N/A putInt(sbuf, target - pc, 4);
2668N/A }
2668N/A } else { //lookupswitch
2668N/A int caseCount = ins.size();
2668N/A putInt(sbuf, caseCount, 4);
2668N/A for (Element cas : ins.elements()) {
2668N/A int target = insLocs[(int) cas.getAttrLong("lab")];
2668N/A putInt(sbuf, (int) cas.getAttrLong("num"), 4);
2668N/A putInt(sbuf, target - pc, 4);
2668N/A }
2668N/A }
2668N/A assert (nextpc == sbuf.length());
2668N/A } else {
2668N/A putInt(sbuf, opnd, -(nextpc - (pc + 1)));
2668N/A }
2668N/A } else if (nextpc == pc + 1) {
2668N/A // a single-byte instruction
2668N/A sbuf.append((char) op);
2668N/A } else {
2668N/A // picky stuff
2668N/A boolean wide = isWide[id];
2668N/A if (wide) {
2668N/A sbuf.append((char) WIDE);
2668N/A pc++;
2668N/A }
2668N/A sbuf.append((char) op);
2668N/A int opnd1;
2668N/A int opnd2 = opnd;
2668N/A switch (op) {
2668N/A case 0x84: //iinc
2668N/A ins = insElems[id];
2668N/A opnd1 = (int) ins.getAttrLong("loc");
2668N/A if (isWide[id]) {
2668N/A putInt(sbuf, opnd1, 2);
2668N/A putInt(sbuf, opnd2, 2);
2668N/A } else {
2668N/A putInt(sbuf, opnd1, 1);
2668N/A putInt(sbuf, opnd2, 1);
2668N/A }
2668N/A break;
2668N/A case 0xc5: //multianewarray
2668N/A ins = insElems[id];
2668N/A opnd1 = getCPIndex(ins, 'c', getCPI);
2668N/A putInt(sbuf, opnd1, 2);
2668N/A putInt(sbuf, opnd2, 1);
2668N/A break;
2668N/A case 0xb9: //invokeinterface
2668N/A ins = insElems[id];
2668N/A opnd1 = getCPIndex(ins, 'n', getCPI);
2668N/A putInt(sbuf, opnd1, 2);
2668N/A opnd2 = (int) ins.getAttrLong("num");
2668N/A if (opnd2 == 0) {
2668N/A opnd2 = ClassSyntax.computeInterfaceNum(ins.getAttr("val"));
2668N/A }
2668N/A putInt(sbuf, opnd2, 2);
2668N/A break;
2668N/A default:
2668N/A // put the single operand and be done
2668N/A putInt(sbuf, opnd, nextpc - (pc + 1));
2668N/A break;
2668N/A }
2668N/A }
2668N/A }
2668N/A assert (sbuf.length() == insLocs[insCount]);
2668N/A
2668N/A return sbuf.toString();
2668N/A }
2668N/A
2668N/A static int getCPIndex(Element ins, char ctype,
2668N/A ClassSyntax.GetCPIndex getCPI) {
2668N/A int x = (int) ins.getAttrLong("ref");
2668N/A if (x == 0 && getCPI != null) {
2668N/A String val = ins.getAttr("val");
2668N/A if (val == null || val.equals("")) {
2668N/A val = ins.getText().toString();
2668N/A }
2668N/A byte tag;
2668N/A switch (ctype) {
2668N/A case 'k':
2668N/A tag = (byte) ins.getAttrLong("tag");
2668N/A break;
2668N/A case 'c':
2668N/A tag = ClassSyntax.CONSTANT_Class;
2668N/A break;
2668N/A case 'f':
2668N/A tag = ClassSyntax.CONSTANT_Fieldref;
2668N/A break;
2668N/A case 'm':
2668N/A tag = ClassSyntax.CONSTANT_Methodref;
2668N/A break;
2668N/A case 'n':
2668N/A tag = ClassSyntax.CONSTANT_InterfaceMethodref;
2668N/A break;
2668N/A default:
2668N/A throw new Error("bad ctype " + ctype + " in " + ins);
2668N/A }
2668N/A x = getCPI.getCPIndex(tag, val);
2668N/A //System.out.println("getCPIndex "+ins+" => "+tag+"/"+val+" => "+x);
2668N/A } else {
2668N/A assert (x > 0);
2668N/A }
2668N/A return x;
2668N/A }
2668N/A
2668N/A static void putInt(StringBuffer sbuf, int x, int len) {
2668N/A //System.out.println("putInt x="+x+" len="+len);
2668N/A boolean isSigned = false;
2668N/A if (len < 0) {
2668N/A len = -len;
2668N/A isSigned = true;
2668N/A }
2668N/A assert (len == 1 || len == 2 || len == 4);
2668N/A int insig = ((4 - len) * 8); // how many insignificant bits?
2668N/A int sx = x << insig;
2668N/A ;
2668N/A assert (x == (isSigned ? (sx >> insig) : (sx >>> insig)));
2668N/A for (int i = 0; i < len; i++) {
2668N/A sbuf.append((char) (sx >>> 24));
2668N/A sx <<= 8;
2668N/A }
2668N/A }
2668N/A}