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.ssa;
014
015 import java.util.Enumeration;
016 import java.util.HashMap;
017 import org.jikesrvm.VM;
018 import org.jikesrvm.compilers.opt.DefUse;
019 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
020 import org.jikesrvm.compilers.opt.ir.ALoad;
021 import org.jikesrvm.compilers.opt.ir.AStore;
022 import org.jikesrvm.compilers.opt.ir.Attempt;
023 import org.jikesrvm.compilers.opt.ir.Binary;
024 import org.jikesrvm.compilers.opt.ir.CacheOp;
025 import org.jikesrvm.compilers.opt.ir.Call;
026 import org.jikesrvm.compilers.opt.ir.GuardedBinary;
027 import org.jikesrvm.compilers.opt.ir.GuardedUnary;
028 import org.jikesrvm.compilers.opt.ir.IfCmp;
029 import org.jikesrvm.compilers.opt.ir.InlineGuard;
030 import org.jikesrvm.compilers.opt.ir.MonitorOp;
031 import org.jikesrvm.compilers.opt.ir.Move;
032 import org.jikesrvm.compilers.opt.ir.New;
033 import org.jikesrvm.compilers.opt.ir.NewArray;
034 import org.jikesrvm.compilers.opt.ir.NullCheck;
035 import org.jikesrvm.compilers.opt.ir.BasicBlock;
036 import org.jikesrvm.compilers.opt.ir.IR;
037 import org.jikesrvm.compilers.opt.ir.Instruction;
038 import static org.jikesrvm.compilers.opt.ir.Operators.IG_PATCH_POINT;
039 import static org.jikesrvm.compilers.opt.ir.Operators.IR_PROLOGUE;
040 import static org.jikesrvm.compilers.opt.ir.Operators.PI;
041 import org.jikesrvm.compilers.opt.ir.Register;
042 import org.jikesrvm.compilers.opt.ir.Phi;
043 import org.jikesrvm.compilers.opt.ir.Prepare;
044 import org.jikesrvm.compilers.opt.ir.PutField;
045 import org.jikesrvm.compilers.opt.ir.PutStatic;
046 import org.jikesrvm.compilers.opt.ir.Unary;
047 import org.jikesrvm.compilers.opt.ir.ZeroCheck;
048 import org.jikesrvm.compilers.opt.ir.operand.ConditionOperand;
049 import org.jikesrvm.compilers.opt.ir.operand.ConstantOperand;
050 import org.jikesrvm.compilers.opt.ir.operand.DoubleConstantOperand;
051 import org.jikesrvm.compilers.opt.ir.operand.FloatConstantOperand;
052 import org.jikesrvm.compilers.opt.ir.operand.IntConstantOperand;
053 import org.jikesrvm.compilers.opt.ir.operand.LongConstantOperand;
054 import org.jikesrvm.compilers.opt.ir.operand.MethodOperand;
055 import org.jikesrvm.compilers.opt.ir.operand.ObjectConstantOperand;
056 import org.jikesrvm.compilers.opt.ir.operand.Operand;
057 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
058 import org.jikesrvm.compilers.opt.ir.operand.TIBConstantOperand;
059 import org.jikesrvm.compilers.opt.ir.operand.TrueGuardOperand;
060 import org.jikesrvm.compilers.opt.ir.operand.TypeOperand;
061 import org.jikesrvm.compilers.opt.ir.operand.UnreachableOperand;
062 import org.jikesrvm.compilers.opt.util.GraphNode;
063 import org.jikesrvm.compilers.opt.util.SpaceEffGraph;
064
065 /**
066 * This class implements the value graph used in global value numbering
067 * a la Alpern, Wegman and Zadeck. See Muchnick p.348 for a nice
068 * discussion.
069 * <p>
070 * From Muchnick, "the <em>value graph</em> of a procedure is a
071 * labeled directed graph whose nodes are labeled with operators,
072 * function symbols, or constants, and whose edges represent
073 * generating assignments and point from an operator or function to
074 * its operands; the edges are labeled with natural numbers that
075 * indicate the operand position that each operand has with respect to
076 * the given operator or function."
077 */
078 final class ValueGraph {
079
080 /**
081 * Internal graph structure of the value graph.
082 */
083 private final SpaceEffGraph graph;
084 /**
085 * A mapping from name to value graph vertex.
086 */
087 private final HashMap<Object, ValueGraphVertex> nameMap;
088
089 /**
090 * Construct a value graph from an IR.
091 *
092 * <p><b> PRECONDITION:</b> The IR <em> must </em> be in SSA form.
093 * @param ir the IR
094 */
095 ValueGraph(IR ir) {
096 graph = new SpaceEffGraph();
097 nameMap = new HashMap<Object, ValueGraphVertex>();
098 // TODO!!: compute register lists incrementally
099 // we need register lists in order to call Register.getFirstDef()
100 DefUse.computeDU(ir);
101 // add value graph nodes for each symbolic register
102 addRegisterNodes(ir);
103 // go through the IR and add nodes and edges to the value graph
104 // for each instruction, as needed
105 for (Enumeration<Instruction> e = ir.forwardInstrEnumerator(); e.hasMoreElements();) {
106 Instruction s = e.nextElement();
107 processInstruction(s);
108 }
109
110 computeClosure();
111 }
112
113 /**
114 * Due to PI nodes and Moves, the initial label for a register may be
115 * another register. Fix up the value graph for cases where the initial
116 * register label was not removed.
117 */
118 private void computeClosure() {
119 for (Enumeration<GraphNode> e = enumerateVertices(); e.hasMoreElements();) {
120 ValueGraphVertex v = (ValueGraphVertex) e.nextElement();
121 if (v.getName() instanceof Register) {
122 if (v.getLabel() instanceof Register) {
123 if (v.getName() != v.getLabel()) {
124 ValueGraphVertex v2 = getVertex(v.getLabel());
125 if (VM.VerifyAssertions) {
126 if (v2.getName() instanceof Register &&
127 v2.getLabel() instanceof Register &&
128 v2.getLabel() != v2.getName()) {
129 VM._assert(VM.NOT_REACHED);
130 }
131 }
132 v.copyVertex(v2);
133 }
134 }
135 }
136 }
137 }
138
139 /**
140 * Enumerate the vertices in the value graph.
141 *
142 * @return an enumeration of the vertices in the value graph
143 */
144 public Enumeration<GraphNode> enumerateVertices() {
145 return graph.enumerateNodes();
146 }
147
148 /**
149 * Return the vertex which has a given name.
150 *
151 * @param name the name of the vertex
152 * @return the vertex with the name. null if none found.
153 */
154 public ValueGraphVertex getVertex(Object name) {
155 if (name instanceof RegisterOperand) {
156 name = ((RegisterOperand) name).asRegister().getRegister();
157 } else if (name instanceof IntConstantOperand) {
158 name = ((IntConstantOperand) name).value;
159 } else if (name instanceof FloatConstantOperand) {
160 name = ((FloatConstantOperand) name).value;
161 } else if (name instanceof LongConstantOperand) {
162 name = ((LongConstantOperand) name).value;
163 } else if (name instanceof DoubleConstantOperand) {
164 name = ((DoubleConstantOperand) name).value;
165 } else if (name instanceof ObjectConstantOperand) {
166 name = ((ObjectConstantOperand) name).value;
167 } else if (name instanceof TIBConstantOperand) {
168 name = ((TIBConstantOperand) name).value;
169 }
170 return nameMap.get(name);
171 }
172
173 /**
174 * Return a String representation of the value graph.
175 *
176 * @return a String representation of the value graph.
177 */
178 @Override
179 public String toString() {
180 // print the nodes
181 StringBuilder s = new StringBuilder("VALUE GRAPH: \n");
182 for (Enumeration<GraphNode> n = graph.enumerateNodes(); n.hasMoreElements();) {
183 ValueGraphVertex node = (ValueGraphVertex) n.nextElement();
184 s.append(node).append("\n");
185 }
186 return s.toString();
187 }
188
189 /**
190 * Add a node to the value graph for every symbolic register.
191 *
192 * <p><b>PRECONDITION:</b> register lists are computed and valid
193 *
194 * @param ir the governing IR
195 */
196 private void addRegisterNodes(IR ir) {
197 for (Register reg = ir.regpool.getFirstSymbolicRegister(); reg != null; reg = reg.getNext()) {
198 findOrCreateVertex(reg);
199 }
200 }
201
202 /**
203 * Update the value graph to account for a given instruction.
204 *
205 * @param s the instruction in question
206 */
207 private void processInstruction(Instruction s) {
208 // TODO: support all necessary types of instructions
209 if (s.isDynamicLinkingPoint()) {
210 processCall(s);
211 } else if (Move.conforms(s)) {
212 processMove(s);
213 } else if (s.operator == PI) {
214 processPi(s);
215 } else if (New.conforms(s)) {
216 processNew(s);
217 } else if (NewArray.conforms(s)) {
218 processNewArray(s);
219 } else if (Unary.conforms(s)) {
220 processUnary(s);
221 } else if (GuardedUnary.conforms(s)) {
222 processGuardedUnary(s);
223 } else if (NullCheck.conforms(s)) {
224 processNullCheck(s);
225 } else if (ZeroCheck.conforms(s)) {
226 processZeroCheck(s);
227 } else if (Binary.conforms(s)) {
228 processBinary(s);
229 } else if (GuardedBinary.conforms(s)) {
230 processGuardedBinary(s);
231 } else if (InlineGuard.conforms(s)) {
232 processInlineGuard(s);
233 } else if (IfCmp.conforms(s)) {
234 processIfCmp(s);
235 } else if (Call.conforms(s)) {
236 processCall(s);
237 } else if (MonitorOp.conforms(s)) {
238 processCall(s);
239 } else if (Prepare.conforms(s)) {
240 processCall(s);
241 } else if (Attempt.conforms(s)) {
242 processCall(s);
243 } else if (CacheOp.conforms(s)) {
244 processCall(s);
245 } else if (ALoad.conforms(s)) {
246 processALoad(s);
247 } else if (PutField.conforms(s)) {
248 processPutField(s);
249 } else if (PutStatic.conforms(s)) {
250 processPutStatic(s);
251 } else if (AStore.conforms(s)) {
252 processAStore(s);
253 } else if (Phi.conforms(s)) {
254 processPhi(s);
255 } else if (s.operator() == IR_PROLOGUE) {
256 processPrologue(s);
257 }
258 }
259
260 /**
261 * Update the value graph to account for a given MOVE instruction.
262 *
263 * <p><b>PRECONDITION:</b> <code> Move.conforms(s); </code>
264 *
265 * @param s the instruction in question
266 */
267 private void processMove(Instruction s) {
268 // ignore instructions that define physical registers
269 for (Enumeration<Operand> e = s.getDefs(); e.hasMoreElements();) {
270 Operand current = e.nextElement();
271 if (current instanceof RegisterOperand && ((RegisterOperand) current).getRegister().isPhysical()) return;
272 }
273
274 Register result = Move.getResult(s).getRegister();
275 ValueGraphVertex v = findOrCreateVertex(result);
276 Operand val = Move.getVal(s);
277 // bypass Move instructions that define the right-hand side
278 val = bypassMoves(val);
279 v.copyVertex(findOrCreateVertex(val));
280 }
281
282 /**
283 * Update the value graph to account for a given PI instruction.
284 *
285 * <p><b>PRECONDITION:</b> <code> s.operator == PI </code>
286 *
287 * @param s the instruction in question
288 */
289 private void processPi(Instruction s) {
290 Register result = GuardedUnary.getResult(s).getRegister();
291 ValueGraphVertex v = findOrCreateVertex(result);
292 Operand val = GuardedUnary.getVal(s);
293 // bypass Move instructions that define the right-hand side
294 val = bypassMoves(val);
295 v.copyVertex(findOrCreateVertex(val));
296 }
297
298 /**
299 * Update the value graph to account for a given NEW instruction.
300 *
301 * <p><b>PRECONDITION:</b> <code> New.conforms(s); </code>
302 *
303 * For a new instruction, we always create a new vertex.
304 *
305 * @param s the instruction in question
306 */
307 private void processNew(Instruction s) {
308 RegisterOperand result = New.getResult(s);
309 ValueGraphVertex v = findOrCreateVertex(result.getRegister());
310 // set the label for a NEW instruction to be the instruction itself
311 // so that no two NEW results get the same value number
312 v.setLabel(s, 0);
313 }
314
315 /**
316 * Update the value graph to account for a given NEWARRAY instruction.
317 *
318 * <p><b>PRECONDITION:</b> <code> NewArray.conforms(s); </code>
319 *
320 * For a newarray instruction, we always create a new vertex.
321 *
322 * @param s the instruction in question
323 */
324 private void processNewArray(Instruction s) {
325 RegisterOperand result = NewArray.getResult(s);
326 ValueGraphVertex v = findOrCreateVertex(result.getRegister());
327 // set the label for a NEW instruction to be the instruction itself
328 // so that no two NEW results get the same value number
329 v.setLabel(s, 0);
330 }
331
332 /**
333 * Update the value graph to account for a given PUTFIELD instruction.
334 *
335 * <p><b>PRECONDITION:</b> <code> PutField.conforms(s); </code>
336 *
337 * Make sure we have value graph nodes for a constant value
338 *
339 * @param s the instruction in question
340 */
341 private void processPutField(Instruction s) {
342 Operand value = PutField.getValue(s);
343 if (value.isConstant()) {
344 findOrCreateVertex((ConstantOperand) value);
345 }
346 }
347
348 /**
349 * Update the value graph to account for a given PUTSTATIC instruction.
350 *
351 * <p><b>PRECONDITION:</b> <code> PutStatic.conforms(s); </code>
352 *
353 * Make sure we have value graph nodes for a constant value
354 *
355 * @param s the instruction in question
356 */
357 private void processPutStatic(Instruction s) {
358 Operand value = PutStatic.getValue(s);
359 if (value.isConstant()) {
360 findOrCreateVertex((ConstantOperand) value);
361 }
362 }
363
364 /**
365 * Update the value graph to account for a given ASTORE instruction.
366 *
367 * <p><b>PRECONDITION:</b> <code> AStore.conforms(s); </code>
368 *
369 * Make sure we have value graph nodes for a constant value
370 *
371 * @param s the instruction in question
372 */
373 private void processAStore(Instruction s) {
374 Operand value = AStore.getValue(s);
375 if (value.isConstant()) {
376 findOrCreateVertex((ConstantOperand) value);
377 }
378 Operand index = AStore.getIndex(s);
379 if (index.isConstant()) {
380 findOrCreateVertex((ConstantOperand) index);
381 }
382 }
383
384 /**
385 * Update the value graph to account for a given ALOAD instruction.
386 *
387 * <p><b>PRECONDITION:</b> <code> ALoad.conforms(s); </code>
388 *
389 * Make sure we have value graph nodes for a constant value
390 *
391 * @param s the instruction in question
392 */
393 private void processALoad(Instruction s) {
394 Operand index = ALoad.getIndex(s);
395 if (index.isConstant()) {
396 findOrCreateVertex((ConstantOperand) index);
397 }
398 }
399
400 /**
401 * Update the value graph to account for a given Unary instruction.
402 *
403 * <p><b>PRECONDITION:</b> <code> Unary.conforms(s); </code>
404 *
405 * @param s the instruction in question
406 */
407 private void processUnary(Instruction s) {
408 // label the vertex corresponding to the result with the operator
409 RegisterOperand result = Unary.getResult(s);
410 ValueGraphVertex v = findOrCreateVertex(result.getRegister());
411 v.setLabel(s.operator(), 1);
412 // link node v to the operand it uses
413 Operand val = Unary.getVal(s);
414 // bypass Move instructions
415 val = bypassMoves(val);
416 link(v, findOrCreateVertex(val), 0);
417 }
418
419 /**
420 * Update the value graph to account for a given GuardedUnary instruction.
421 *
422 * <p><b>PRECONDITION:</b> <code> GuardedUnary.conforms(s); </code>
423 *
424 * Careful: we define two Guarded Unaries to be equivalent regardless of
425 * whether the guards are equivalent!
426 *
427 * @param s the instruction in question
428 */
429 private void processGuardedUnary(Instruction s) {
430 // label the vertex corresponding to the result with the operator
431 RegisterOperand result = GuardedUnary.getResult(s);
432 ValueGraphVertex v = findOrCreateVertex(result.getRegister());
433 v.setLabel(s.operator(), 1);
434 // link node v to the operand it uses
435 Operand val = GuardedUnary.getVal(s);
436 // bypass Move instructions
437 val = bypassMoves(val);
438 link(v, findOrCreateVertex(val), 0);
439 }
440
441 /**
442 * Update the value graph to account for a given NullCheck instruction.
443 *
444 * <p><b>PRECONDITION:</b> <code> NullCheck.conforms(s); </code>
445 *
446 * @param s the instruction in question
447 */
448 private void processNullCheck(Instruction s) {
449 // label the vertex corresponding to the result with the operator
450 RegisterOperand result = NullCheck.getGuardResult(s);
451 ValueGraphVertex v = findOrCreateVertex(result.getRegister());
452 v.setLabel(s.operator(), 1);
453 // link node v to the operand it uses
454 Operand val = NullCheck.getRef(s);
455 // bypass Move instructions
456 val = bypassMoves(val);
457 link(v, findOrCreateVertex(val), 0);
458 }
459
460 /**
461 * Update the value graph to account for a given NullCheck instruction.
462 *
463 * <p><b>PRECONDITION:</b> <code> ZeroCheck.conforms(s); </code>
464 *
465 * @param s the instruction in question
466 */
467 private void processZeroCheck(Instruction s) {
468 // label the vertex corresponding to the result with the operator
469 RegisterOperand result = ZeroCheck.getGuardResult(s);
470 ValueGraphVertex v = findOrCreateVertex(result.getRegister());
471 v.setLabel(s.operator(), 1);
472 // link node v to the operand it uses
473 Operand val = ZeroCheck.getValue(s);
474 // bypass Move instructions
475 val = bypassMoves(val);
476 link(v, findOrCreateVertex(val), 0);
477 }
478
479 /**
480 * Update the value graph to account for a given Binary instruction.
481 *
482 * <p><b>PRECONDITION:</b> <code> Binary.conforms(s); </code>
483 *
484 * @param s the instruction in question
485 */
486 private void processBinary(Instruction s) {
487 // label the vertex corresponding to the result with the operator
488 RegisterOperand result = Binary.getResult(s);
489 ValueGraphVertex v = findOrCreateVertex(result.getRegister());
490 v.setLabel(s.operator(), 2);
491 // link node v to the two operands it uses
492 // first link the first val
493 Operand val = Binary.getVal1(s);
494 val = bypassMoves(val);
495 link(v, findOrCreateVertex(val), 0);
496 Operand val2 = Binary.getVal2(s);
497 val2 = bypassMoves(val2);
498 link(v, findOrCreateVertex(val2), 1);
499 }
500
501 /**
502 * Update the value graph to account for a given GuardedBinary instruction.
503 *
504 * <p><b>PRECONDITION:</b> <code> GuardedBinary.conforms(s); </code>
505 *
506 * Careful: we define two Guarded Binaries to be equivalent regardless of
507 * whether the guards are equivalent!
508 *
509 * @param s the instruction in question
510 */
511 private void processGuardedBinary(Instruction s) {
512 // label the vertex corresponding to the result with the operator
513 RegisterOperand result = GuardedBinary.getResult(s);
514 ValueGraphVertex v = findOrCreateVertex(result.getRegister());
515 v.setLabel(s.operator(), 2);
516 // link node v to the two operands it uses
517 // first link the first val
518 Operand val = GuardedBinary.getVal1(s);
519 val = bypassMoves(val);
520 link(v, findOrCreateVertex(val), 0);
521 Operand val2 = GuardedBinary.getVal2(s);
522 val2 = bypassMoves(val2);
523 link(v, findOrCreateVertex(val2), 1);
524 }
525
526 /**
527 * Update the value graph to account for a given InlineGuard instruction.
528 *
529 * <p><b>PRECONDITION:</b> <code> InlineGuard.conforms(s); </code>
530 *
531 * @param s the instruction in question
532 */
533 private void processInlineGuard(Instruction s) {
534 ValueGraphVertex v = new ValueGraphVertex(s);
535 graph.addGraphNode(v);
536 nameMap.put(s, v);
537 if (s.operator() == IG_PATCH_POINT) {
538 // the 'goal' is irrelevant for patch_point guards.
539 v.setLabel(s.operator(), 1);
540 link(v, findOrCreateVertex(bypassMoves(InlineGuard.getValue(s))), 0);
541 } else {
542 v.setLabel(s.operator(), 2);
543 link(v, findOrCreateVertex(bypassMoves(InlineGuard.getValue(s))), 0);
544 link(v, findOrCreateVertex(InlineGuard.getGoal(s)), 1);
545 }
546 }
547
548 /**
549 * Update the value graph to account for a given IfCmp instruction.
550 *
551 * <p><b>PRECONDITION:</b> <code> IfCmp.conforms(s); </code>
552 *
553 * @param s the instruction in question
554 */
555 private void processIfCmp(Instruction s) {
556 ValueGraphVertex v = new ValueGraphVertex(s);
557 graph.addGraphNode(v);
558 nameMap.put(s, v);
559 v.setLabel(s.operator(), 3);
560 link(v, findOrCreateVertex(bypassMoves(IfCmp.getVal1(s))), 0);
561 link(v, findOrCreateVertex(bypassMoves(IfCmp.getVal2(s))), 1);
562 link(v, findOrCreateVertex(IfCmp.getCond(s)), 2);
563 }
564
565 /**
566 * Update the value graph to account for a given Phi instruction.
567 *
568 * <p><b>PRECONDITION:</b> <code> Phi.conforms(s); </code>
569 *
570 * @param s the instruction in question
571 */
572 private void processPhi(Instruction s) {
573 // the label for a PHI instruction is the basic block
574 // in which it appears
575 Register result = Phi.getResult(s).asRegister().getRegister();
576 ValueGraphVertex v = findOrCreateVertex(result);
577 BasicBlock bb = s.getBasicBlock();
578 v.setLabel(bb, bb.getNumberOfIn());
579 // link node v to all operands it uses
580 for (int i = 0; i < Phi.getNumberOfValues(s); i++) {
581 Operand val = Phi.getValue(s, i);
582 val = bypassMoves(val);
583 ValueGraphVertex target = findOrCreateVertex(val);
584 link(v, target, i);
585 }
586 }
587
588 /**
589 * Update the value graph to account for an IR_PROLOGUE instruction
590 *
591 * <p><b>PRECONDITION:</b> <code> Prologue.conforms(s); </code>
592 *
593 * @param s the instruction in question
594 */
595 private void processPrologue(Instruction s) {
596 int numArgs = 0;
597 for (Enumeration<Operand> e = s.getDefs(); e.hasMoreElements(); numArgs++) {
598 Register formal = ((RegisterOperand) e.nextElement()).getRegister();
599 ValueGraphVertex v = findOrCreateVertex(formal);
600 v.setLabel(new ValueGraphParamLabel(numArgs), 0);
601 }
602 }
603
604 /**
605 * Update the value graph to account for a given Call instruction.
606 *
607 * <p><b>PRECONDITION:</b> <code> Call.conforms(s); </code>
608 *
609 * @param s the instruction in question
610 */
611 private void processCall(Instruction s) {
612 // do nothing.
613 // TODO: someday, maybe exploit interprocedural information
614 }
615
616 /**
617 * Find or create an ValueGraphVertex corresponding to a
618 * given variable.
619 *
620 * @param var The variable
621 * @return A value graph vertex corresponding to this variable
622 */
623 private ValueGraphVertex findOrCreateVertex(Object var) {
624 if (var instanceof Register) {
625 return findOrCreateVertex((Register) var);
626 } else if (var instanceof RegisterOperand) {
627 return findOrCreateVertex(((RegisterOperand) var).getRegister());
628 } else if (var instanceof ConstantOperand) {
629 return findOrCreateVertex((ConstantOperand) var);
630 } else if (var instanceof TypeOperand) {
631 return findOrCreateVertex((TypeOperand) var);
632 } else if (var instanceof MethodOperand) {
633 return findOrCreateVertex((MethodOperand) var);
634 } else if (var instanceof ConditionOperand) {
635 return findOrCreateVertex((ConditionOperand) var);
636 } else {
637 throw new OptimizingCompilerException("ValueGraph.findOrCreateVertex: unexpected type " + var.getClass());
638 }
639 }
640
641 /**
642 * Find or create an ValueGraphVertex corresponding to a
643 * given register
644 *
645 * @param r the register
646 * @return a value graph vertex corresponding to this variable
647 */
648 private ValueGraphVertex findOrCreateVertex(Register r) {
649 ValueGraphVertex v = getVertex(r);
650 if (v == null) {
651 v = new ValueGraphVertex(r);
652 v.setLabel(r, 0);
653 graph.addGraphNode(v);
654 nameMap.put(r, v);
655 }
656 return v;
657 }
658
659 /**
660 * Find or create an ValueGraphVertex corresponding to a
661 * given constant operand
662 *
663 * @param op the constant operand
664 * @return a value graph vertex corresponding to this variable
665 */
666 private ValueGraphVertex findOrCreateVertex(ConstantOperand op) {
667 Object name;
668 if (op.isAddressConstant()) {
669 name = (VM.BuildFor32Addr) ? op.asAddressConstant().value.toInt() : op.asAddressConstant().value.toLong();
670 } else if (op.isIntConstant()) {
671 name = op.asIntConstant().value;
672 } else if (op.isFloatConstant()) {
673 name = op.asFloatConstant().value;
674 } else if (op.isLongConstant()) {
675 name = op.asLongConstant().value;
676 } else if (op.isDoubleConstant()) {
677 name = op.asDoubleConstant().value;
678 } else if (op instanceof ObjectConstantOperand) {
679 name = op.asObjectConstant().value;
680 } else if (op instanceof TIBConstantOperand) {
681 name = op.asTIBConstant().value;
682 } else if (op.isNullConstant()) {
683 name = op;
684 } else if (op instanceof TrueGuardOperand) {
685 name = op;
686 } else if (op instanceof UnreachableOperand) {
687 name = op;
688 } else {
689 throw new OptimizingCompilerException("ValueGraph.findOrCreateVertex: unexpected constant operand: " +
690 op);
691 }
692 ValueGraphVertex v = getVertex(name);
693 if (v == null) {
694 v = new ValueGraphVertex(op);
695 v.setLabel(op, 0);
696 graph.addGraphNode(v);
697 nameMap.put(name, v);
698 }
699 return v;
700 }
701
702 /**
703 * Find or create an ValueGraphVertex corresponding to a
704 * given type operand
705 *
706 * @param op the operand in question
707 * @return a value graph vertex corresponding to this type
708 */
709 private ValueGraphVertex findOrCreateVertex(TypeOperand op) {
710 Object name = op.getTypeRef();
711 ValueGraphVertex v = getVertex(name);
712 if (v == null) {
713 v = new ValueGraphVertex(op);
714 v.setLabel(op, 0);
715 graph.addGraphNode(v);
716 nameMap.put(name, v);
717 }
718 return v;
719 }
720
721 /**
722 * Find or create an ValueGraphVertex corresponding to a
723 * given method operand
724 *
725 * @param op the operand in question
726 * @return a value graph vertex corresponding to this type
727 */
728 private ValueGraphVertex findOrCreateVertex(MethodOperand op) {
729 Object name;
730 if (op.hasTarget()) {
731 name = op.getTarget();
732 } else {
733 name = op.getMemberRef();
734 }
735 ValueGraphVertex v = getVertex(name);
736 if (v == null) {
737 v = new ValueGraphVertex(op);
738 v.setLabel(op, 0);
739 graph.addGraphNode(v);
740 nameMap.put(name, v);
741 }
742 return v;
743 }
744
745 /**
746 * Find or create an ValueGraphVertex corresponding to a
747 * given method operand
748 *
749 * @param op the operand in question
750 * @return a value graph vertex corresponding to this type
751 */
752 private ValueGraphVertex findOrCreateVertex(ConditionOperand op) {
753 Object name = op.value; // kludge.
754 ValueGraphVertex v = getVertex(name);
755 if (v == null) {
756 v = new ValueGraphVertex(op);
757 v.setLabel(op, 0);
758 graph.addGraphNode(v);
759 nameMap.put(name, v);
760 }
761 return v;
762 }
763
764 /**
765 * Link two vertices in the value graph
766 *
767 * @param src the def
768 * @param target the use
769 * @param pos the position of target in the set of uses
770 */
771 private void link(ValueGraphVertex src, ValueGraphVertex target, int pos) {
772 ValueGraphEdge e = new ValueGraphEdge(src, target);
773 src.addTarget(target, pos);
774 graph.addGraphEdge(e);
775 }
776
777 /**
778 * Bypass MOVE instructions that def an operand: return the first def
779 * in the chain that is not the result of a MOVE instruction.
780 * <p>
781 * Note: treat PI instructions like MOVES
782 *
783 * @param op the RegisterOperand
784 */
785 private Operand bypassMoves(Operand op) {
786 if (!op.isRegister()) return op;
787 Register r = op.asRegister().getRegister();
788 Instruction def = r.getFirstDef();
789 if (def == null) {
790 return op;
791 }
792 if (r.isPhysical()) {
793 return op;
794 }
795 if (Move.conforms(def)) {
796 // In a perfect world, this shouldn't happen. Copy propagation
797 // in SSA form should remove all 'normal' moves.
798 // We can't simply bypass this move, since it may lead to
799 // infinite mutual recursion.
800 return op;
801 } else if (def.operator == PI) {
802 return bypassMoves(GuardedUnary.getVal(def));
803 } else {
804 return op;
805 }
806 }
807 }