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.opt.ir;
014
015 import java.util.Enumeration;
016 import java.util.Iterator;
017 import org.jikesrvm.ArchitectureSpecificOpt;
018 import org.jikesrvm.ArchitectureSpecificOpt.PhysicalDefUse;
019 import org.jikesrvm.classloader.TypeReference;
020 import org.jikesrvm.compilers.opt.ir.operand.HeapOperand;
021 import org.jikesrvm.compilers.opt.ir.operand.Operand;
022 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
023
024 import static org.jikesrvm.compilers.opt.ir.Operators.PHI;
025 import org.vmmagic.pragma.NoInline;
026
027 /**
028 * This class is not meant to be instantiated.<p>
029 * It simply serves as a place to collect the implementation of
030 * primitive IR enumerations.<p>
031 * None of these functions are meant to be called directly from
032 * anywhere except IR, Instruction, and BasicBlock.<p>
033 * General clients should use the higher level interfaces provided
034 * by those classes.
035 */
036 public abstract class IREnumeration {
037
038 /**
039 * Forward intra basic block instruction enumerations from
040 * from start...last inclusive.<p>
041 *
042 * NB: start and last _must_ be in the same basic block
043 * and must be in the proper relative order.
044 * This code does _not_ check this invariant, and will
045 * simply fail by eventually thowing a NoSuchElementException
046 * if it is not met. Caller's must be sure the invariants are met.
047 *
048 * @param start the instruction to start with
049 * @param end the instruction to end with
050 * @return an enumeration of the instructions from start to end
051 */
052 public static Enumeration<Instruction> forwardIntraBlockIE(final Instruction start, final Instruction end) {
053 return new Enumeration<Instruction>() {
054 private Instruction current = start;
055 private final Instruction last = end;
056
057 @Override
058 public boolean hasMoreElements() { return current != null; }
059
060 @Override
061 public Instruction nextElement() {
062 Instruction res = current;
063 if (current == last) {
064 current = null;
065 } else {
066 try {
067 current = current.getNext();
068 } catch (NullPointerException e) {
069 fail("forwardIntraBlockIE");
070 }
071 }
072 return res;
073 }
074 };
075 }
076
077 /**
078 * Reverse intra basic block instruction enumerations from
079 * from start...last inclusive.<p>
080 *
081 * NB: start and last _must_ be in the same basic block
082 * and must be in the proper relative order.
083 * This code does _not_ check this invariant, and will
084 * simply fail by eventually thowing a NoSuchElementException
085 * if it is not met. Caller's must be sure the invariants are met.
086 *
087 * @param start the instruction to start with
088 * @param end the instruction to end with
089 * @return an enumeration of the instructions from start to end
090 */
091 public static Enumeration<Instruction> reverseIntraBlockIE(final Instruction start, final Instruction end) {
092 return new Enumeration<Instruction>() {
093 private Instruction current = start;
094 private final Instruction last = end;
095
096 @Override
097 public boolean hasMoreElements() { return current != null; }
098
099 @Override
100 public Instruction nextElement() {
101 Instruction res = current;
102 if (current == last) {
103 current = null;
104 } else {
105 try {
106 current = current.getPrev();
107 } catch (NullPointerException e) {
108 fail("reverseIntraBlockIE");
109 }
110 }
111 return res;
112 }
113 };
114 }
115
116 /**
117 * A forward enumeration of all the instructions in the IR.
118 *
119 * @param ir the IR to walk over
120 * @return a forward enumeration of the insturctions in ir
121 */
122 public static Enumeration<Instruction> forwardGlobalIE(final IR ir) {
123 return new Enumeration<Instruction>() {
124 private Instruction current = ir.firstInstructionInCodeOrder();
125
126 @Override
127 public boolean hasMoreElements() { return current != null; }
128
129 @Override
130 public Instruction nextElement() {
131 try {
132 Instruction res = current;
133 current = current.nextInstructionInCodeOrder();
134 return res;
135 } catch (NullPointerException e) {
136 fail("forwardGlobalIR");
137 return null; // placate jikes
138 }
139 }
140 };
141 }
142
143 /**
144 * A reverse enumeration of all the instructions in the IR.
145 *
146 * @param ir the IR to walk over
147 * @return a forward enumeration of the insturctions in ir
148 */
149 public static Enumeration<Instruction> reverseGlobalIE(final IR ir) {
150 return new Enumeration<Instruction>() {
151 private Instruction current = ir.lastInstructionInCodeOrder();
152
153 @Override
154 public boolean hasMoreElements() { return current != null; }
155
156 @Override
157 public Instruction nextElement() {
158 try {
159 Instruction res = current;
160 current = current.prevInstructionInCodeOrder();
161 return res;
162 } catch (NullPointerException e) {
163 fail("forwardGlobalIR");
164 return null; // placate jikes
165 }
166 }
167 };
168 }
169
170 /**
171 * A forward enumeration of all the basic blocks in the IR.
172 *
173 * @param ir the IR to walk over
174 * @return a forward enumeration of the basic blocks in ir
175 */
176 public static Enumeration<BasicBlock> forwardBE(final IR ir) {
177 return new Enumeration<BasicBlock>() {
178 private BasicBlock current = ir.firstBasicBlockInCodeOrder();
179
180 @Override
181 public boolean hasMoreElements() { return current != null; }
182
183 @Override
184 public BasicBlock nextElement() {
185 try {
186 BasicBlock res = current;
187 current = current.nextBasicBlockInCodeOrder();
188 return res;
189 } catch (NullPointerException e) {
190 fail("forwardBE");
191 return null; // placate jikes
192 }
193 }
194 };
195 }
196
197 /**
198 * A reverse enumeration of all the basic blocks in the IR.
199 *
200 * @param ir the IR to walk over
201 * @return a reverse enumeration of the basic blocks in ir
202 */
203 public static Enumeration<BasicBlock> reverseBE(final IR ir) {
204 return new Enumeration<BasicBlock>() {
205 private BasicBlock current = ir.lastBasicBlockInCodeOrder();
206
207 @Override
208 public boolean hasMoreElements() { return current != null; }
209
210 @Override
211 public BasicBlock nextElement() {
212 try {
213 BasicBlock res = current;
214 current = current.prevBasicBlockInCodeOrder();
215 return res;
216 } catch (NullPointerException e) {
217 fail("forwardBE");
218 return null; // placate jikes
219 }
220 }
221 };
222 }
223
224 /**
225 * This class implements an enumeration of instructions over
226 * all instructions for a basic block. This enumeration includes
227 * explicit instructions in the IR and implicit phi instructions for
228 * heap variables, which are stored only in this lookaside
229 * structure.
230 * @see org.jikesrvm.compilers.opt.ssa.SSADictionary
231 */
232 public static final class AllInstructionsEnum implements Enumeration<Instruction> {
233 /**
234 * An enumeration of the explicit instructions in the IR for a
235 * basic block
236 */
237 private final Enumeration<Instruction> explicitInstructions;
238
239 /**
240 * An enumeration of the implicit instructions in the IR for a
241 * basic block. These instructions appear only in the SSA
242 * dictionary lookaside structure.
243 */
244 private final Iterator<Instruction> implicitInstructions;
245
246 /**
247 * The label instruction for the basic block - the label is
248 * special as we want it to appear in the enumeration before the
249 * implicit SSA instructions
250 */
251 private Instruction labelInstruction;
252
253 /**
254 * Construct an enumeration for all instructions, both implicit and
255 * explicit in the IR, for a given basic block
256 *
257 * @param block the basic block whose instructions this enumerates
258 */
259 public AllInstructionsEnum(IR ir, BasicBlock block) {
260 explicitInstructions = block.forwardInstrEnumerator();
261 if (ir.inSSAForm()) {
262 implicitInstructions = ir.HIRInfo.dictionary.getHeapPhiInstructions(block);
263 } else {
264 implicitInstructions = null;
265 }
266 labelInstruction = explicitInstructions.nextElement();
267 }
268
269 /**
270 * Are there more elements in the enumeration?
271 *
272 * @return {@code true} or {@code false}
273 */
274 @Override
275 public boolean hasMoreElements() {
276 return (((implicitInstructions != null) && implicitInstructions.hasNext()) ||
277 explicitInstructions.hasMoreElements());
278 }
279
280 @Override
281 public Instruction nextElement() {
282 if (labelInstruction != null) {
283 Instruction temp = labelInstruction;
284 labelInstruction = null;
285 return temp;
286 } else if ((implicitInstructions != null) && implicitInstructions.hasNext()) {
287 return implicitInstructions.next();
288 } else {
289 return explicitInstructions.nextElement();
290 }
291 }
292 }
293
294 /**
295 * This class implements an {@link Enumeration} of {@link Operand}s. It used
296 * for holding the definitions of a particular instruction and being
297 * used as an enumeration for iterating over. It differs from other
298 * enumerations of Operand as it iterates over both implicit
299 * and explicit operands.
300 * @see org.jikesrvm.compilers.opt.ssa.SSADictionary
301 */
302 public static final class AllDefsEnum implements Enumeration<Operand> {
303 /**
304 * Enumeration of non-heap operands defined by the instruction
305 */
306 private final Enumeration<Operand> instructionOperands;
307 /**
308 * Array of heap operands defined by the instruction
309 */
310 private final HeapOperand<?>[] heapOperands;
311 /**
312 * Current heap operand we're upto for the enumeration
313 */
314 private int curHeapOperand;
315 /**
316 * Implicit definitions from the operator
317 */
318 private final ArchitectureSpecificOpt.PhysicalDefUse.PDUEnumeration implicitDefs;
319 /**
320 * Defining instruction
321 */
322 private final Instruction instr;
323
324 /**
325 * Construct/initialize object
326 *
327 * @param ir Containing IR
328 * @param instr Instruction to get definitions for
329 */
330 public AllDefsEnum(IR ir, Instruction instr) {
331 this.instr = instr;
332 instructionOperands = instr.getDefs();
333 if (instr.operator().getNumberOfImplicitDefs() > 0) {
334 implicitDefs = ArchitectureSpecificOpt.PhysicalDefUse.enumerate(instr.operator().implicitDefs, ir);
335 } else {
336 implicitDefs = null;
337 }
338 if (ir.inSSAForm() && (instr.operator != PHI)) {
339 // Phi instructions store the heap SSA in the actual
340 // instruction
341 heapOperands = ir.HIRInfo.dictionary.getHeapDefs(instr);
342 } else {
343 heapOperands = null;
344 }
345 }
346
347 /**
348 * Are there any more elements in the enumeration
349 */
350 @Override
351 public boolean hasMoreElements() {
352 return ((instructionOperands.hasMoreElements()) ||
353 ((heapOperands != null) && (curHeapOperand < heapOperands.length)) ||
354 ((implicitDefs != null) && (implicitDefs.hasMoreElements())));
355 }
356
357 @Override
358 public Operand nextElement() {
359 if (instructionOperands.hasMoreElements()) {
360 return instructionOperands.nextElement();
361 } else {
362 if ((implicitDefs != null) && implicitDefs.hasMoreElements()) {
363 RegisterOperand rop = new RegisterOperand(implicitDefs.nextElement(), TypeReference.Int);
364 rop.instruction = instr;
365 return rop;
366 } else {
367 if (curHeapOperand >= heapOperands.length) {
368 fail("Regular and heap operands exhausted");
369 }
370 HeapOperand<?> result = heapOperands[curHeapOperand];
371 curHeapOperand++;
372 return result;
373 }
374 }
375 }
376 }
377
378 /**
379 * This class implements an {@link Enumeration} of {@link Operand}. It used
380 * for holding the uses of a particular instruction and being used
381 * as an enumeration for iterating over. It differs from other
382 * enumerations of Operand as it iterates over both implicit
383 * and explicit operands.
384 * @see org.jikesrvm.compilers.opt.ssa.SSADictionary
385 */
386 public static final class AllUsesEnum implements Enumeration<Operand> {
387 /**
388 * Enumeration of non-heap operands defined by the instruction
389 */
390 private final Enumeration<Operand> instructionOperands;
391 /**
392 * Array of heap operands defined by the instruction
393 */
394 private final HeapOperand<?>[] heapOperands;
395 /**
396 * Current heap operand we're upto for the enumeration
397 */
398 private int curHeapOperand;
399 /**
400 * Implicit uses from the operator
401 */
402 private final PhysicalDefUse.PDUEnumeration implicitUses;
403 /**
404 * Defining instruction
405 */
406 private final Instruction instr;
407
408 /**
409 * Construct/initialize object
410 *
411 * @param ir Containing IR
412 * @param instr Instruction to get uses for
413 */
414 public AllUsesEnum(IR ir, Instruction instr) {
415 this.instr = instr;
416 instructionOperands = instr.getUses();
417 if (instr.operator().getNumberOfImplicitUses() > 0) {
418 implicitUses = PhysicalDefUse.enumerate(instr.operator().implicitUses, ir);
419 } else {
420 implicitUses = null;
421 }
422 if (ir.inSSAForm() && (instr.operator != PHI)) {
423 // Phi instructions store the heap SSA in the actual
424 // instruction
425 heapOperands = ir.HIRInfo.dictionary.getHeapUses(instr);
426 } else {
427 heapOperands = null;
428 }
429 }
430
431 /**
432 * Are there any more elements in the enumeration
433 */
434 @Override
435 public boolean hasMoreElements() {
436 return ((instructionOperands.hasMoreElements()) ||
437 ((heapOperands != null) && (curHeapOperand < heapOperands.length)) ||
438 ((implicitUses != null) && (implicitUses.hasMoreElements())));
439 }
440
441 @Override
442 public Operand nextElement() {
443 if (instructionOperands.hasMoreElements()) {
444 return instructionOperands.nextElement();
445 } else {
446 if ((implicitUses != null) && implicitUses.hasMoreElements()) {
447 RegisterOperand rop = new RegisterOperand(implicitUses.nextElement(), TypeReference.Int);
448 rop.instruction = instr;
449 return rop;
450 } else {
451 if (curHeapOperand >= heapOperands.length) {
452 fail("Regular and heap operands exhausted");
453 }
454 HeapOperand<?> result = heapOperands[curHeapOperand];
455 curHeapOperand++;
456 return result;
457 }
458 }
459 }
460 }
461
462 @NoInline
463 private static void fail(String msg) throws java.util.NoSuchElementException {
464 throw new java.util.NoSuchElementException(msg);
465 }
466 }