Home | History | Annotate | Download | only in stackmap 
      1 /*
      2  * Javassist, a Java-bytecode translator toolkit.
      3  * Copyright (C) 1999-2007 Shigeru Chiba. All Rights Reserved.
      4  *
      5  * The contents of this file are subject to the Mozilla Public License Version
      6  * 1.1 (the "License"); you may not use this file except in compliance with
      7  * the License.  Alternatively, the contents of this file may be used under
      8  * the terms of the GNU Lesser General Public License Version 2.1 or later.
      9  *
     10  * Software distributed under the License is distributed on an "AS IS" basis,
     11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
     12  * for the specific language governing rights and limitations under the
     13  * License.
     14  */
     15 
     16  package javassist.bytecode.stackmap;
     17 
     18 import javassist.bytecode.*;
     19 
     20 public class Liveness {
     21     protected static final byte UNKNOWN = 0;
     22     protected static final byte READ = 1;
     23     protected static final byte UPDATED = 2;
     24     protected byte[] localsUsage;
     25 
     26     /**
     27      * If true, all the arguments become alive within the whole method body.
     28      *
     29      * To correctly compute a stack map table, all the arguments must
     30      * be alive (localsUsage[?] must be READ) at least in the first block.
     31      */
     32     public static boolean useArgs = true;
     33 
     34     public void compute(CodeIterator ci, TypedBlock[] blocks, int maxLocals,
     35                         TypeData[] args)
     36         throws BadBytecode
     37     {
     38         computeUsage(ci, blocks, maxLocals);
     39         if (useArgs)
     40             useAllArgs(blocks, args);
     41 
     42         computeLiveness1(blocks[0]);
     43         while (hasChanged(blocks))
     44             computeLiveness2(blocks[0]);
     45     }
     46 
     47     private void useAllArgs(TypedBlock[] blocks, TypeData[] args) {
     48         for (int k = 0; k < blocks.length; k++) {
     49             byte[] usage = blocks[k].localsUsage;
     50             for (int i = 0; i < args.length; i++)
     51                 if (args[i] != TypeTag.TOP)
     52                     usage[i] = READ;
     53         }
     54     }
     55 
     56     static final int NOT_YET = 0;
     57     static final int CHANGED_LAST = 1;
     58     static final int DONE = 2;
     59     static final int CHANGED_NOW = 3;
     60 
     61     private void computeLiveness1(TypedBlock tb) {
     62         if (tb.updating) {
     63             // a loop was detected.
     64             computeLiveness1u(tb);
     65             return;
     66         }
     67 
     68         if (tb.inputs != null)
     69             return;
     70 
     71         tb.updating = true;
     72         byte[] usage = tb.localsUsage;
     73         int n = usage.length;
     74         boolean[] in = new boolean[n];
     75         for (int i = 0; i < n; i++)
     76             in[i] = usage[i] == READ;
     77 
     78         BasicBlock.Catch handlers = tb.toCatch;
     79         while (handlers != null) {
     80             TypedBlock h = (TypedBlock)handlers.body;
     81             computeLiveness1(h);
     82             for (int k = 0; k < n; k++)
     83                 if (h.inputs[k])
     84                     in[k] = true;
     85 
     86             handlers = handlers.next;
     87         }
     88 
     89         if (tb.exit != null) {
     90             for (int i = 0; i < tb.exit.length; i++) {
     91                 TypedBlock e = (TypedBlock)tb.exit[i];
     92                 computeLiveness1(e);
     93                 for (int k = 0; k < n; k++)
     94                     if (!in[k])
     95                         in[k] = usage[k] == UNKNOWN && e.inputs[k];
     96             }
     97         }
     98 
     99         tb.updating = false;
    100         if (tb.inputs == null) {
    101             tb.inputs = in;
    102             tb.status = DONE;
    103         }
    104         else {
    105             for (int i = 0; i < n; i++)
    106                 if (in[i] && !tb.inputs[i]) {
    107                     tb.inputs[i] = true;
    108                     tb.status = CHANGED_NOW;
    109                 }
    110         }
    111     }
    112 
    113     private void computeLiveness1u(TypedBlock tb) {
    114         if (tb.inputs == null) {
    115             byte[] usage = tb.localsUsage;
    116             int n = usage.length;
    117             boolean[] in = new boolean[n];
    118             for (int i = 0; i < n; i++)
    119                 in[i] = usage[i] == READ;
    120 
    121             tb.inputs = in;
    122             tb.status = DONE;
    123         }
    124     }
    125 
    126     private void computeLiveness2(TypedBlock tb) {
    127         if (tb.updating || tb.status >= DONE)
    128             return;
    129 
    130         tb.updating = true;
    131         if (tb.exit == null)
    132             tb.status = DONE;
    133         else {
    134             boolean changed = false;
    135             for (int i = 0; i < tb.exit.length; i++) {
    136                 TypedBlock e = (TypedBlock)tb.exit[i];
    137                 computeLiveness2(e);
    138                 if (e.status != DONE)
    139                     changed = true;
    140             }
    141 
    142             if (changed) {
    143                 changed = false;
    144                 byte[] usage = tb.localsUsage;
    145                 int n = usage.length;
    146                 for (int i = 0; i < tb.exit.length; i++) {
    147                     TypedBlock e = (TypedBlock)tb.exit[i];
    148                     if (e.status != DONE)
    149                         for (int k = 0; k < n; k++)
    150                             if (!tb.inputs[k]) {
    151                                 if (usage[k] == UNKNOWN && e.inputs[k]) {
    152                                     tb.inputs[k] = true;
    153                                     changed = true;
    154                                 }
    155                             }
    156                 }
    157 
    158                 tb.status = changed ? CHANGED_NOW : DONE;
    159             }
    160             else
    161                 tb.status = DONE;
    162         }
    163 
    164         if (computeLiveness2except(tb))
    165             tb.status = CHANGED_NOW;
    166 
    167         tb.updating = false;
    168     }
    169 
    170     private boolean computeLiveness2except(TypedBlock tb) {
    171         BasicBlock.Catch handlers = tb.toCatch;
    172         boolean changed = false;
    173         while (handlers != null) {
    174             TypedBlock h = (TypedBlock)handlers.body;
    175             computeLiveness2(h);
    176             if (h.status != DONE) {
    177                 boolean[] in = tb.inputs;
    178                 int n = in.length;
    179                 for (int k = 0; k < n; k++)
    180                     if (!in[k] && h.inputs[k]) {
    181                         in[k] = true;
    182                         changed = true;
    183                     }
    184             }
    185 
    186             handlers = handlers.next;
    187         }
    188 
    189         return changed;
    190     }
    191 
    192     private boolean hasChanged(TypedBlock[] blocks) {
    193         int n = blocks.length;
    194         boolean changed = false;
    195         for (int i = 0; i < n; i++) {
    196             TypedBlock tb = blocks[i];
    197             if (tb.status == CHANGED_NOW) {
    198                 tb.status = CHANGED_LAST;
    199                 changed = true;
    200             }
    201             else
    202                 tb.status = NOT_YET;
    203         }
    204 
    205         return changed;
    206     }
    207 
    208     private void computeUsage(CodeIterator ci, TypedBlock[] blocks, int maxLocals)
    209         throws BadBytecode
    210     {
    211         int n = blocks.length;
    212         for (int i = 0; i < n; i++) {
    213             TypedBlock tb = blocks[i];
    214             localsUsage = tb.localsUsage = new byte[maxLocals];
    215             int pos = tb.position;
    216             analyze(ci, pos, pos + tb.length);
    217             localsUsage = null;
    218         }
    219     }
    220 
    221     protected final void readLocal(int reg) {
    222         if (localsUsage[reg] == UNKNOWN)
    223             localsUsage[reg] = READ;
    224     }
    225 
    226     protected final void writeLocal(int reg) {
    227         if (localsUsage[reg] == UNKNOWN)
    228             localsUsage[reg] = UPDATED;
    229     }
    230 
    231     protected void analyze(CodeIterator ci, int begin, int end)
    232         throws BadBytecode
    233     {
    234         ci.begin();
    235         ci.move(begin);
    236         while (ci.hasNext()) {
    237             int index = ci.next();
    238             if (index >= end)
    239                 break;
    240 
    241             int op = ci.byteAt(index);
    242             if (op < 96)
    243                 if (op < 54)
    244                     doOpcode0_53(ci, index, op);
    245                 else
    246                     doOpcode54_95(ci, index, op);
    247             else
    248                 if (op == Opcode.IINC) {
    249                     // this does not call writeLocal().
    250                     readLocal(ci.byteAt(index + 1));
    251                 }
    252                 else if (op == Opcode.WIDE)
    253                     doWIDE(ci, index);
    254         }
    255     }
    256 
    257     private void doOpcode0_53(CodeIterator ci, int pos, int op) {
    258         switch (op) {
    259         case Opcode.ILOAD :
    260         case Opcode.LLOAD :
    261         case Opcode.FLOAD :
    262         case Opcode.DLOAD :
    263         case Opcode.ALOAD :
    264             readLocal(ci.byteAt(pos + 1));
    265             break;
    266         case Opcode.ILOAD_0 :
    267         case Opcode.ILOAD_1 :
    268         case Opcode.ILOAD_2 :
    269         case Opcode.ILOAD_3 :
    270             readLocal(op - Opcode.ILOAD_0);
    271             break;
    272         case Opcode.LLOAD_0 :
    273         case Opcode.LLOAD_1 :
    274         case Opcode.LLOAD_2 :
    275         case Opcode.LLOAD_3 :
    276             readLocal(op - Opcode.LLOAD_0);
    277             break;
    278         case Opcode.FLOAD_0 :
    279         case Opcode.FLOAD_1 :
    280         case Opcode.FLOAD_2 :
    281         case Opcode.FLOAD_3 :
    282             readLocal(op - Opcode.FLOAD_0);
    283             break;
    284         case Opcode.DLOAD_0 :
    285         case Opcode.DLOAD_1 :
    286         case Opcode.DLOAD_2 :
    287         case Opcode.DLOAD_3 :
    288             readLocal(op - Opcode.DLOAD_0);
    289             break;
    290         case Opcode.ALOAD_0 :
    291         case Opcode.ALOAD_1 :
    292         case Opcode.ALOAD_2 :
    293         case Opcode.ALOAD_3 :
    294             readLocal(op - Opcode.ALOAD_0);
    295             break;
    296         }
    297     }
    298 
    299     private void doOpcode54_95(CodeIterator ci, int pos, int op) {
    300         switch (op) {
    301         case Opcode.ISTORE :
    302         case Opcode.LSTORE :
    303         case Opcode.FSTORE :
    304         case Opcode.DSTORE :
    305         case Opcode.ASTORE :
    306             writeLocal(ci.byteAt(pos + 1));
    307             break;
    308         case Opcode.ISTORE_0 :
    309         case Opcode.ISTORE_1 :
    310         case Opcode.ISTORE_2 :
    311         case Opcode.ISTORE_3 :
    312             writeLocal(op - Opcode.ISTORE_0);
    313             break;
    314         case Opcode.LSTORE_0 :
    315         case Opcode.LSTORE_1 :
    316         case Opcode.LSTORE_2 :
    317         case Opcode.LSTORE_3 :
    318             writeLocal(op - Opcode.LSTORE_0);
    319             break;
    320         case Opcode.FSTORE_0 :
    321         case Opcode.FSTORE_1 :
    322         case Opcode.FSTORE_2 :
    323         case Opcode.FSTORE_3 :
    324             writeLocal(op - Opcode.FSTORE_0);
    325             break;
    326         case Opcode.DSTORE_0 :
    327         case Opcode.DSTORE_1 :
    328         case Opcode.DSTORE_2 :
    329         case Opcode.DSTORE_3 :
    330             writeLocal(op - Opcode.DSTORE_0);
    331             break;
    332         case Opcode.ASTORE_0 :
    333         case Opcode.ASTORE_1 :
    334         case Opcode.ASTORE_2 :
    335         case Opcode.ASTORE_3 :
    336             writeLocal(op - Opcode.ASTORE_0);
    337             break;
    338         }
    339     }
    340 
    341     private void doWIDE(CodeIterator ci, int pos) throws BadBytecode {
    342         int op = ci.byteAt(pos + 1);
    343         int var = ci.u16bitAt(pos + 2);
    344         switch (op) {
    345         case Opcode.ILOAD :
    346         case Opcode.LLOAD :
    347         case Opcode.FLOAD :
    348         case Opcode.DLOAD :
    349         case Opcode.ALOAD :
    350             readLocal(var);
    351             break;
    352         case Opcode.ISTORE :
    353         case Opcode.LSTORE :
    354         case Opcode.FSTORE :
    355         case Opcode.DSTORE :
    356         case Opcode.ASTORE :
    357             writeLocal(var);
    358             break;
    359         case Opcode.IINC :
    360             readLocal(var);
    361             // this does not call writeLocal().
    362             break;
    363         }
    364     }
    365 }
    366