1 /*
   2  * Copyright (c) 2009, 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 org.graalvm.compiler.java;
  24 
  25 import org.graalvm.compiler.java.BciBlockMapping.BciBlock;
  26 
  27 public final class SmallLocalLiveness extends LocalLiveness {
  28     /*
  29      * local n is represented by the bit accessible as (1 << n)
  30      */
  31 
  32     private final long[] localsLiveIn;
  33     private final long[] localsLiveOut;
  34     private final long[] localsLiveGen;
  35     private final long[] localsLiveKill;
  36     private final long[] localsChangedInLoop;
  37     private final int maxLocals;
  38 
  39     public SmallLocalLiveness(BciBlock[] blocks, int maxLocals, int loopCount) {
  40         super(blocks);
  41         this.maxLocals = maxLocals;
  42         int blockSize = blocks.length;
  43         localsLiveIn = new long[blockSize];
  44         localsLiveOut = new long[blockSize];
  45         localsLiveGen = new long[blockSize];
  46         localsLiveKill = new long[blockSize];
  47         localsChangedInLoop = new long[loopCount];
  48     }
  49 
  50     private String debugString(long value) {
  51         StringBuilder str = new StringBuilder("{");
  52         long current = value;
  53         for (int i = 0; i < maxLocals; i++) {
  54             if ((current & 1L) == 1L) {
  55                 if (str.length() > 1) {
  56                     str.append(", ");
  57                 }
  58                 str.append(i);
  59             }
  60             current >>= 1;
  61         }
  62         return str.append('}').toString();
  63     }
  64 
  65     @Override
  66     protected String debugLiveIn(int blockID) {
  67         return debugString(localsLiveIn[blockID]);
  68     }
  69 
  70     @Override
  71     protected String debugLiveOut(int blockID) {
  72         return debugString(localsLiveOut[blockID]);
  73     }
  74 
  75     @Override
  76     protected String debugLiveGen(int blockID) {
  77         return debugString(localsLiveGen[blockID]);
  78     }
  79 
  80     @Override
  81     protected String debugLiveKill(int blockID) {
  82         return debugString(localsLiveKill[blockID]);
  83     }
  84 
  85     @Override
  86     protected int liveOutCardinality(int blockID) {
  87         return Long.bitCount(localsLiveOut[blockID]);
  88     }
  89 
  90     @Override
  91     protected void propagateLiveness(int blockID, int successorID) {
  92         localsLiveOut[blockID] |= localsLiveIn[successorID];
  93     }
  94 
  95     @Override
  96     protected void updateLiveness(int blockID) {
  97         localsLiveIn[blockID] = (localsLiveOut[blockID] & ~localsLiveKill[blockID]) | localsLiveGen[blockID];
  98     }
  99 
 100     @Override
 101     protected void loadOne(int blockID, int local) {
 102         long bit = 1L << local;
 103         if ((localsLiveKill[blockID] & bit) == 0L) {
 104             localsLiveGen[blockID] |= bit;
 105         }
 106     }
 107 
 108     @Override
 109     protected void storeOne(int blockID, int local) {
 110         long bit = 1L << local;
 111         if ((localsLiveGen[blockID] & bit) == 0L) {
 112             localsLiveKill[blockID] |= bit;
 113         }
 114 
 115         BciBlock block = blocks[blockID];
 116         long tmp = block.loops;
 117         int pos = 0;
 118         while (tmp != 0) {
 119             if ((tmp & 1L) == 1L) {
 120                 this.localsChangedInLoop[pos] |= bit;
 121             }
 122             tmp >>>= 1;
 123             ++pos;
 124         }
 125     }
 126 
 127     @Override
 128     public boolean localIsLiveIn(BciBlock block, int local) {
 129         int blockID = block.getId();
 130         return blockID >= Integer.MAX_VALUE ? false : (localsLiveIn[blockID] & (1L << local)) != 0L;
 131     }
 132 
 133     @Override
 134     public boolean localIsLiveOut(BciBlock block, int local) {
 135         int blockID = block.getId();
 136         return blockID >= Integer.MAX_VALUE ? false : (localsLiveOut[blockID] & (1L << local)) != 0L;
 137     }
 138 
 139     @Override
 140     public boolean localIsChangedInLoop(int loopId, int local) {
 141         return (localsChangedInLoop[loopId] & (1L << local)) != 0L;
 142     }
 143 }