001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.compilers.baseline;
014
015 /**
016 * Structure to describe the basic blocks of the byte code Used in calculating
017 * stack map and local variable map for the garbage collector.
018 */
019 final class BasicBlock {
020
021 // NOTE: Block number 1 is the epilog block, the only block
022 // that exits from the method. Blocks that end in a return will
023 // have the exit block as their only successor.
024 // NOTE: Block number 0 is NOT used;
025
026 // ------------------- Static Class Fields -----------------
027
028 public static final int NOTBLOCK = 0;
029 public static final int EXITBLOCK = 1;
030 public static final int STARTPREDSIZE = 4;
031 public static final int STARTBBNUMBER = 2;
032
033 static final byte JSRENTRY = 1;
034 static final byte JSREXIT = 2;
035 static final byte METHODENTRY = 4;
036 static final byte TRYSTART = 8;
037 static final byte TRYBLOCK = 16;
038 static final byte INJSR = 32;
039 static final byte TRYHANDLERSTART = 64;
040
041 // --------------------- Instance Fields ---------------------
042
043 /** ID number (index into block array) */
044 private final int blockNumber;
045 /** starting byte in byte code array */
046 private int start;
047 /** ending byte in byte code array */
048 private int end;
049 /** number of preceding basic blocks */
050 private int predcount = 0;
051 // First 2 are listed individually.
052 private short pred1;
053 private short pred2;
054 /** list of rest preceding basic blocks */
055 private short[] restPredecessors;
056 // may be bigger then predcount;
057 /** additional state info for jsr handling, and other flags */
058 private byte state = 0;
059
060 // --------------- Constructor --------------------------------
061
062 /** This should be called only from the factory. */
063 BasicBlock(int startval, int bn) {
064 blockNumber = bn;
065 start = startval;
066 }
067
068 /**
069 * This should be used when building the EXIT block EXIT is likely to have
070 * several predecessors.
071 */
072 BasicBlock(int startval, int endval, int blockNumber) {
073 start = startval;
074 end = endval;
075 this.blockNumber = blockNumber;
076 restPredecessors = new short[STARTPREDSIZE];
077 }
078
079 // ------------------ Static Methods -------------------------
080
081 /** transfer predecessor blocks from one block to another */
082 public static void transferPredecessors(BasicBlock fromBB,
083 BasicBlock toBB) {
084 toBB.predcount = fromBB.predcount;
085 toBB.pred1 = fromBB.pred1;
086 toBB.pred2 = fromBB.pred2;
087 toBB.restPredecessors = fromBB.restPredecessors;
088
089 fromBB.predcount = 0;
090 fromBB.restPredecessors = null;
091 }
092
093 // -------------------------- Instance Methods ----------------
094
095 void setStart(int startval) {
096 start = startval;
097 }
098
099 void setEnd(int endval) {
100 end = endval;
101 }
102
103 void setState(byte stateval) {
104 state |= stateval;
105 }
106
107 public int getStart() {
108 return start;
109 }
110
111 public int getEnd() {
112 return end;
113 }
114
115 public int getBlockNumber() {
116 return blockNumber;
117 }
118
119 public byte getState() {
120 return state;
121 }
122
123 public boolean isJSRExit() {
124 return ((state & JSREXIT) == JSREXIT);
125 }
126
127 public boolean isJSREntry() {
128 return ((state & JSRENTRY) == JSRENTRY);
129 }
130
131 public boolean isInJSR() {
132 return ((state & INJSR) == INJSR);
133 }
134
135 public boolean isMethodEntry() {
136 return ((state & METHODENTRY) == METHODENTRY);
137 }
138
139 public boolean isTryStart() {
140 return ((state & TRYSTART) == TRYSTART);
141 }
142
143 public boolean isTryBlock() {
144 return ((state & TRYBLOCK) == TRYBLOCK);
145 }
146
147 public boolean isTryHandlerStart() {
148 return ((state & TRYHANDLERSTART) == TRYHANDLERSTART);
149 }
150
151 public void addPredecessor(BasicBlock predbb) {
152 predcount++;
153 if (predcount == 1) {
154 pred1 = (short) predbb.getBlockNumber();
155 } else if (predcount == 2) {
156 pred2 = (short) predbb.getBlockNumber();
157 } else if (restPredecessors == null) {
158 restPredecessors = new short[STARTPREDSIZE];
159 restPredecessors[predcount - 3] = (short) predbb.getBlockNumber();
160 } else {
161 if (restPredecessors.length <= predcount - 3) {
162 short[] newpreds = new short[predcount << 1];
163 int restLength = restPredecessors.length;
164 for (int i = 0; i < restLength; i++) {
165 newpreds[i] = restPredecessors[i];
166 }
167 restPredecessors = newpreds;
168 newpreds = null;
169 }
170 restPredecessors[predcount - 3] = (short) predbb.getBlockNumber();
171 // -3 to get it zero-based
172 }
173 }
174
175 /**
176 * This method first checks if a block is already on the predecessor list.
177 * Used with try blocks being added to their catch block as predecessors.
178 */
179 public void addUniquePredecessor(BasicBlock predbb) {
180 boolean dupFound = false, checkMade = false;
181 short predbbNum = (short) predbb.getBlockNumber();
182
183 if (predcount >= 1) {
184 if (pred1 == predbbNum) {
185 return;
186 }
187
188 if (predcount > 1) {
189 if (pred2 == predbbNum) {
190 return;
191 }
192
193 if (predcount > 2) {
194 if (restPredecessors.length <= predcount - 2) {
195 short[] newpreds = new short[predcount << 1];
196 int restLength = restPredecessors.length;
197 for (int i = 0; i < restLength; i++) {
198 if (restPredecessors[i] == predbbNum) {
199 dupFound = true; // finish up the copy anyway.
200 }
201 newpreds[i] = restPredecessors[i];
202 }
203 restPredecessors = newpreds;
204 newpreds = null;
205
206 if (dupFound)
207 return;
208 checkMade = true;
209 }
210
211 if (!checkMade) {
212 for (int i = 0; i < predcount - 2; i++) {
213 if (restPredecessors[i] == predbbNum) {
214 return;
215 }
216 }
217 }
218
219 predcount++;
220 restPredecessors[predcount - 3] = predbbNum;
221 } else { // predcount must be 2
222 restPredecessors = new short[STARTPREDSIZE];
223 predcount++;
224 restPredecessors[predcount - 3] = predbbNum;
225 }
226 } else {
227 // predcount must be 1
228 predcount++;
229 pred2 = predbbNum;
230 }
231 } else { // predcount must be 0
232 predcount++;
233 pred1 = predbbNum;
234 }
235 }
236
237 public int[] getPredecessors() {
238 int[] preds;
239 preds = new int[predcount];
240 if (predcount >= 1) {
241 preds[0] = pred1;
242 }
243 if (predcount > 1) {
244 preds[1] = pred2;
245 }
246 for (int i = 0; i < predcount - 2; i++) {
247 preds[i + 2] = restPredecessors[i];
248 }
249 return preds;
250
251 }
252
253 }