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