1 /*

     2  * Copyright (c) 2010, 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.  Oracle designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Oracle in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

    25 package xmlkit; // -*- mode: java; indent-tabs-mode: nil -*-

    26 

    27 import xmlkit.XMLKit.Element;

    28 import java.util.HashMap;

    29 /*

    30  * @author jrose

    31  */

    32 abstract class InstructionAssembler extends InstructionSyntax {

    33 

    34     InstructionAssembler() {

    35     }

    36 

    37     public static String assemble(Element instructions, String pcAttrName,

    38             ClassSyntax.GetCPIndex getCPI) {

    39         int insCount = instructions.size();

    40         Element[] insElems = new Element[insCount];

    41         int[] elemToIndexMap;

    42         int[] insLocs;

    43         byte[] ops = new byte[insCount];

    44         int[] operands = new int[insCount];

    45         boolean[] isWide = new boolean[insCount];

    46         int[] branches;

    47         int[] branchInsLocs;

    48         HashMap<String, String> labels = new HashMap<String, String>();

    49 

    50         final int WIDE = 0xc4;

    51         final int GOTO = 0xa7;

    52         final int GOTO_W = 0xc8;

    53         final int GOTO_LEN = 3;

    54         final int GOTO_W_LEN = 5;

    55         assert ("wide".equals(bcNames[WIDE]));

    56         assert ("goto".equals(bcNames[GOTO]));

    57         assert ("goto_w".equals(bcNames[GOTO_W]));

    58         assert (bcFormats[GOTO].length() == GOTO_LEN);

    59         assert (bcFormats[GOTO_W].length() == GOTO_W_LEN);

    60 

    61         // Unpack instructions into temp. arrays, and find branches and labels.

    62         {

    63             elemToIndexMap = (pcAttrName != null) ? new int[insCount] : null;

    64             int[] buffer = operands;

    65             int id = 0;

    66             int branchCount = 0;

    67             for (int i = 0; i < insCount; i++) {

    68                 Element ins = (Element) instructions.get(i);

    69                 if (elemToIndexMap != null) {

    70                     elemToIndexMap[i] = (ins.getAttr(pcAttrName) != null ? id : -1);

    71                 }

    72                 String lab = ins.getAttr("pc");

    73                 if (lab != null) {

    74                     labels.put(lab, String.valueOf(id));

    75                 }

    76                 int op = opCode(ins.getName());

    77                 if (op < 0) {

    78                     assert (ins.getAttr(pcAttrName) != null

    79                             || ins.getName().equals("label"));

    80                     continue;  // delete PC holder element

    81                 }

    82                 if (op == WIDE) { //0xc4

    83                     isWide[id] = true;  // force wide format

    84                     continue;

    85                 }

    86                 if (bcFormats[op].indexOf('o') >= 0) {

    87                     buffer[branchCount++] = id;

    88                 }

    89                 if (bcFormats[op] == bcWideFormats[op]) {

    90                     isWide[id] = false;

    91                 }

    92                 insElems[id] = ins;

    93                 ops[id] = (byte) op;

    94                 id++;

    95             }

    96             insCount = id;  // maybe we deleted some wide prefixes, etc.

    97             branches = new int[branchCount + 1];

    98             System.arraycopy(buffer, 0, branches, 0, branchCount);

    99             branches[branchCount] = -1;  // sentinel

   100         }

   101 

   102         // Compute instruction sizes.  These sizes are final,

   103         // except for branch instructions, which may need lengthening.

   104         // Some instructions (ldc, bipush, iload, iinc) are automagically widened.

   105         insLocs = new int[insCount + 1];

   106         int loc = 0;

   107         for (int bn = 0, id = 0; id < insCount; id++) {

   108             insLocs[id] = loc;

   109             Element ins = insElems[id];

   110             int op = ops[id] & 0xFF;

   111             String format = opFormat(op, isWide[id]);

   112             // Make sure operands fit within the given format.

   113             for (int j = 1, jlimit = format.length(); j < jlimit; j++) {

   114                 char fc = format.charAt(j);

   115                 int x = 0;

   116                 switch (fc) {

   117                     case 'l':

   118                         x = (int) ins.getAttrLong("loc");

   119                         assert (x >= 0);

   120                         if (x > 0xFF && !isWide[id]) {

   121                             isWide[id] = true;

   122                             format = opFormat(op, isWide[id]);

   123                         }

   124                         assert (x <= 0xFFFF);

   125                         break;

   126                     case 'k':

   127                         char fc2 = format.charAt(Math.min(j + 1, format.length() - 1));

   128                         x = getCPIndex(ins, fc2, getCPI);

   129                         if (x > 0xFF && j == jlimit - 1) {

   130                             assert (op == 0x12); //ldc

   131                             ops[id] = (byte) (op = 0x13); //ldc_w

   132                             format = opFormat(op);

   133                         }

   134                         assert (x <= 0xFFFF);

   135                         j++;  // skip type-of-constant marker

   136                         break;

   137                     case 'x':

   138                         x = (int) ins.getAttrLong("num");

   139                         assert (x >= 0 && x <= ((j == jlimit - 1) ? 0xFF : 0xFFFF));

   140                         break;

   141                     case 's':

   142                         x = (int) ins.getAttrLong("num");

   143                         if (x != (byte) x && j == jlimit - 1) {

   144                             switch (op) {

   145                                 case 0x10: //bipush

   146                                     ops[id] = (byte) (op = 0x11); //sipush

   147                                     break;

   148                                 case 0x84: //iinc

   149                                     isWide[id] = true;

   150                                     format = opFormat(op, isWide[id]);

   151                                     break;

   152                                 default:

   153                                     assert (false);  // cannot lengthen

   154                             }

   155                         }

   156                         // unsign the value now, to make later steps clearer

   157                         if (j == jlimit - 1) {

   158                             assert (x == (byte) x);

   159                             x = x & 0xFF;

   160                         } else {

   161                             assert (x == (short) x);

   162                             x = x & 0xFFFF;

   163                         }

   164                         break;

   165                     case 'o':

   166                         assert (branches[bn] == id);

   167                         bn++;

   168                         // make local copies of the branches, and fix up labels

   169                         insElems[id] = ins = new Element(ins);

   170                         String newLab = labels.get(ins.getAttr("lab"));

   171                         assert (newLab != null);

   172                         ins.setAttr("lab", newLab);

   173                         int prevCas = 0;

   174                         int k = 0;

   175                         for (Element cas : ins.elements()) {

   176                             assert (cas.getName().equals("Case"));

   177                             ins.set(k++, cas = new Element(cas));

   178                             newLab = labels.get(cas.getAttr("lab"));

   179                             assert (newLab != null);

   180                             cas.setAttr("lab", newLab);

   181                             int thisCas = (int) cas.getAttrLong("num");

   182                             assert (op == 0xab

   183                                     || op == 0xaa && (k == 0 || thisCas == prevCas + 1));

   184                             prevCas = thisCas;

   185                         }

   186                         break;

   187                     case 't':

   188                         // switch table is represented as Switch.Case sub-elements

   189                         break;

   190                     default:

   191                         assert (false);

   192                 }

   193                 operands[id] = x;  // record operand (last if there are 2)

   194                 // skip redundant chars

   195                 while (j + 1 < jlimit && format.charAt(j + 1) == fc) {

   196                     ++j;

   197                 }

   198             }

   199 

   200             switch (op) {

   201                 case 0xaa: //tableswitch

   202                     loc = switchBase(loc);

   203                     loc += 4 * (3 + ins.size());

   204                     break;

   205                 case 0xab: //lookupswitch

   206                     loc = switchBase(loc);

   207                     loc += 4 * (2 + 2 * ins.size());

   208                     break;

   209                 default:

   210                     if (isWide[id]) {

   211                         loc++;  // 'wide' opcode prefix

   212                     }

   213                     loc += format.length();

   214                     break;

   215             }

   216         }

   217         insLocs[insCount] = loc;

   218 

   219         // compute branch offsets, and see if any branches need expansion

   220         for (int maxTries = 9, tries = 0;; ++tries) {

   221             boolean overflowing = false;

   222             boolean[] branchExpansions = null;

   223             for (int bn = 0; bn < branches.length - 1; bn++) {

   224                 int id = branches[bn];

   225                 Element ins = insElems[id];

   226                 int insSize = insLocs[id + 1] - insLocs[id];

   227                 int origin = insLocs[id];

   228                 int target = insLocs[(int) ins.getAttrLong("lab")];

   229                 int offset = target - origin;

   230                 operands[id] = offset;

   231                 //System.out.println("branch id="+id+" len="+insSize+" to="+target+" offset="+offset);

   232                 assert (insSize == GOTO_LEN || insSize == GOTO_W_LEN || ins.getName().indexOf("switch") > 0);

   233                 boolean thisOverflow = (insSize == GOTO_LEN && (offset != (short) offset));

   234                 if (thisOverflow && !overflowing) {

   235                     overflowing = true;

   236                     branchExpansions = new boolean[branches.length];

   237                 }

   238                 if (thisOverflow || tries == maxTries - 1) {

   239                     // lengthen the branch

   240                     assert (!(thisOverflow && isWide[id]));

   241                     isWide[id] = true;

   242                     branchExpansions[bn] = true;

   243                 }

   244             }

   245             if (!overflowing) {

   246                 break;  // done, usually on first try

   247             }

   248             assert (tries <= maxTries);

   249 

   250             // Walk over all instructions, expanding branches and updating locations.

   251             int fixup = 0;

   252             for (int bn = 0, id = 0; id < insCount; id++) {

   253                 insLocs[id] += fixup;

   254                 if (branches[bn] == id) {

   255                     int op = ops[id] & 0xFF;

   256                     int wop;

   257                     boolean invert;

   258                     if (branchExpansions[bn]) {

   259                         switch (op) {

   260                             case GOTO: //0xa7

   261                                 wop = GOTO_W; //0xc8

   262                                 invert = false;

   263                                 break;

   264                             case 0xa8: //jsr

   265                                 wop = 0xc9; //jsr_w

   266                                 invert = false;

   267                                 break;

   268                             default:

   269                                 wop = invertBranchOp(op);

   270                                 invert = true;

   271                                 break;

   272                         }

   273                         assert (op != wop);

   274                         ops[id] = (byte) wop;

   275                         isWide[id] = invert;

   276                         if (invert) {

   277                             fixup += GOTO_W_LEN;  //branch around a wide goto

   278                         } else {

   279                             fixup += (GOTO_W_LEN - GOTO_LEN);

   280                         }

   281                         // done expanding:  ops and isWide reflect the decision

   282                     }

   283                     bn++;

   284                 }

   285             }

   286             insLocs[insCount] += fixup;

   287         }

   288         // we know the layout now

   289 

   290         // notify the caller of offsets, if requested

   291         if (elemToIndexMap != null) {

   292             for (int i = 0; i < elemToIndexMap.length; i++) {

   293                 int id = elemToIndexMap[i];

   294                 if (id >= 0) {

   295                     Element ins = (Element) instructions.get(i);

   296                     ins.setAttr(pcAttrName, "" + insLocs[id]);

   297                 }

   298             }

   299             elemToIndexMap = null;  // release the pointer

   300         }

   301 

   302         // output the bytes

   303         StringBuffer sbuf = new StringBuffer(insLocs[insCount]);

   304         for (int bn = 0, id = 0; id < insCount; id++) {

   305             //System.out.println("output id="+id+" loc="+insLocs[id]+" len="+(insLocs[id+1]-insLocs[id])+" #sbuf="+sbuf.length());

   306             assert (sbuf.length() == insLocs[id]);

   307             Element ins;

   308             int pc = insLocs[id];

   309             int nextpc = insLocs[id + 1];

   310             int op = ops[id] & 0xFF;

   311             int opnd = operands[id];

   312             String format;

   313             if (branches[bn] == id) {

   314                 bn++;

   315                 sbuf.append((char) op);

   316                 if (isWide[id]) {

   317                     // emit <ifop lab=1f> <goto_w target> <label pc=1f>

   318                     int target = pc + opnd;

   319                     putInt(sbuf, nextpc - pc, -2);

   320                     assert (sbuf.length() == pc + GOTO_LEN);

   321                     sbuf.append((char) GOTO_W);

   322                     putInt(sbuf, target - (pc + GOTO_LEN), 4);

   323                 } else if (op == 0xaa || //tableswitch

   324                         op == 0xab) {  //lookupswitch

   325                     ins = insElems[id];

   326                     for (int pad = switchBase(pc) - (pc + 1); pad > 0; pad--) {

   327                         sbuf.append((char) 0);

   328                     }

   329                     assert (pc + opnd == insLocs[(int) ins.getAttrLong("lab")]);

   330                     putInt(sbuf, opnd, 4); // default label

   331                     if (op == 0xaa) {  //tableswitch

   332                         Element cas0 = (Element) ins.get(0);

   333                         int lowCase = (int) cas0.getAttrLong("num");

   334                         Element casN = (Element) ins.get(ins.size() - 1);

   335                         int highCase = (int) casN.getAttrLong("num");

   336                         assert (highCase - lowCase + 1 == ins.size());

   337                         putInt(sbuf, lowCase, 4);

   338                         putInt(sbuf, highCase, 4);

   339                         int caseForAssert = lowCase;

   340                         for (Element cas : ins.elements()) {

   341                             int target = insLocs[(int) cas.getAttrLong("lab")];

   342                             assert (cas.getAttrLong("num") == caseForAssert++);

   343                             putInt(sbuf, target - pc, 4);

   344                         }

   345                     } else {  //lookupswitch

   346                         int caseCount = ins.size();

   347                         putInt(sbuf, caseCount, 4);

   348                         for (Element cas : ins.elements()) {

   349                             int target = insLocs[(int) cas.getAttrLong("lab")];

   350                             putInt(sbuf, (int) cas.getAttrLong("num"), 4);

   351                             putInt(sbuf, target - pc, 4);

   352                         }

   353                     }

   354                     assert (nextpc == sbuf.length());

   355                 } else {

   356                     putInt(sbuf, opnd, -(nextpc - (pc + 1)));

   357                 }

   358             } else if (nextpc == pc + 1) {

   359                 // a single-byte instruction

   360                 sbuf.append((char) op);

   361             } else {

   362                 // picky stuff

   363                 boolean wide = isWide[id];

   364                 if (wide) {

   365                     sbuf.append((char) WIDE);

   366                     pc++;

   367                 }

   368                 sbuf.append((char) op);

   369                 int opnd1;

   370                 int opnd2 = opnd;

   371                 switch (op) {

   372                     case 0x84:  //iinc

   373                         ins = insElems[id];

   374                         opnd1 = (int) ins.getAttrLong("loc");

   375                         if (isWide[id]) {

   376                             putInt(sbuf, opnd1, 2);

   377                             putInt(sbuf, opnd2, 2);

   378                         } else {

   379                             putInt(sbuf, opnd1, 1);

   380                             putInt(sbuf, opnd2, 1);

   381                         }

   382                         break;

   383                     case 0xc5: //multianewarray

   384                         ins = insElems[id];

   385                         opnd1 = getCPIndex(ins, 'c', getCPI);

   386                         putInt(sbuf, opnd1, 2);

   387                         putInt(sbuf, opnd2, 1);

   388                         break;

   389                     case 0xb9: //invokeinterface

   390                         ins = insElems[id];

   391                         opnd1 = getCPIndex(ins, 'n', getCPI);

   392                         putInt(sbuf, opnd1, 2);

   393                         opnd2 = (int) ins.getAttrLong("num");

   394                         if (opnd2 == 0) {

   395                             opnd2 = ClassSyntax.computeInterfaceNum(ins.getAttr("val"));

   396                         }

   397                         putInt(sbuf, opnd2, 2);

   398                         break;

   399                     default:

   400                         // put the single operand and be done

   401                         putInt(sbuf, opnd, nextpc - (pc + 1));

   402                         break;

   403                 }

   404             }

   405         }

   406         assert (sbuf.length() == insLocs[insCount]);

   407 

   408         return sbuf.toString();

   409     }

   410 

   411     static int getCPIndex(Element ins, char ctype,

   412             ClassSyntax.GetCPIndex getCPI) {

   413         int x = (int) ins.getAttrLong("ref");

   414         if (x == 0 && getCPI != null) {

   415             String val = ins.getAttr("val");

   416             if (val == null || val.equals("")) {

   417                 val = ins.getText().toString();

   418             }

   419             byte tag;

   420             switch (ctype) {

   421                 case 'k':

   422                     tag = (byte) ins.getAttrLong("tag");

   423                     break;

   424                 case 'c':

   425                     tag = ClassSyntax.CONSTANT_Class;

   426                     break;

   427                 case 'f':

   428                     tag = ClassSyntax.CONSTANT_Fieldref;

   429                     break;

   430                 case 'm':

   431                     tag = ClassSyntax.CONSTANT_Methodref;

   432                     break;

   433                 case 'n':

   434                     tag = ClassSyntax.CONSTANT_InterfaceMethodref;

   435                     break;

   436                 default:

   437                     throw new Error("bad ctype " + ctype + " in " + ins);

   438             }

   439             x = getCPI.getCPIndex(tag, val);

   440             //System.out.println("getCPIndex "+ins+" => "+tag+"/"+val+" => "+x);

   441         } else {

   442             assert (x > 0);

   443         }

   444         return x;

   445     }

   446 

   447     static void putInt(StringBuffer sbuf, int x, int len) {

   448         //System.out.println("putInt x="+x+" len="+len);

   449         boolean isSigned = false;

   450         if (len < 0) {

   451             len = -len;

   452             isSigned = true;

   453         }

   454         assert (len == 1 || len == 2 || len == 4);

   455         int insig = ((4 - len) * 8);  // how many insignificant bits?

   456         int sx = x << insig;

   457         ;

   458         assert (x == (isSigned ? (sx >> insig) : (sx >>> insig)));

   459         for (int i = 0; i < len; i++) {

   460             sbuf.append((char) (sx >>> 24));

   461             sx <<= 8;

   462         }

   463     }

   464 }