# HG changeset patch # User Thomas Wuerthinger # Date 1306519076 -7200 # Node ID c3f64b66fc78b81fb2bb1a42f98416f51a8336cf # Parent 095162a84dcce761f6b581ff58418f27a1c35636 Towards removing the next pointer from Constant and ArithmeticOp diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java --- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java Fri May 27 19:57:56 2011 +0200 @@ -38,6 +38,25 @@ private Block dominator; private final List dominators = new ArrayList(); + private Node firstNode; + private Node lastNode; + + public Node firstNode() { + return firstNode; + } + + public void setFirstNode(Node node) { + this.firstNode = node; + } + + public Node lastNode() { + return lastNode; + } + + public void setLastNode(Node node) { + this.lastNode = node; + } + public List getSuccessors() { return Collections.unmodifiableList(successors); } diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java --- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java Fri May 27 19:57:56 2011 +0200 @@ -68,7 +68,16 @@ private Block assignBlock(Node n, Block b) { assert nodeToBlock.get(n) == null; nodeToBlock.set(n, b); - b.getInstructions().add(n); + if (b.firstNode() == null) { + b.setFirstNode(n); + b.setLastNode(n); + } else { + if (b.lastNode() != null) { + b.getInstructions().add(b.lastNode()); + } + b.setLastNode(n); + } + b.setLastNode(n); return b; } @@ -164,9 +173,23 @@ } } + for (Node n : graph.getNodes()) { + if (n instanceof FrameState) { + FrameState f = (FrameState) n; + if (f.predecessors().size() == 1) { + Block predBlock = nodeToBlock.get(f.predecessors().get(0)); + assert predBlock != null; + nodeToBlock.set(f, predBlock); + predBlock.getInstructions().add(f); + } else { + assert f.predecessors().size() == 0; + } + } + } + computeDominators(); - assignLatestPossibleBlockToNodes(); - sortNodesWithinBlocks(); + + // Add successors of loop end nodes. Makes the graph cyclic. for (Node n : blockBeginNodes) { @@ -177,6 +200,9 @@ } } + assignLatestPossibleBlockToNodes(); + sortNodesWithinBlocks(); + //print(); } @@ -195,16 +221,34 @@ if (prevBlock != null) { return prevBlock; } + TTY.println("handling " + n); Block block = null; for (Node succ : n.successors()) { block = getCommonDominator(block, assignLatestPossibleBlockToNode(succ)); } for (Node usage : n.usages()) { - block = getCommonDominator(block, assignLatestPossibleBlockToNode(usage)); + TTY.println("usaged at: " + usage.id() + ", " + nodeToBlock.get(usage)); + if (usage instanceof Phi) { + Phi phi = (Phi) usage; + Merge merge = phi.block(); + Block mergeBlock = nodeToBlock.get(merge); + assert mergeBlock != null; + for (int i = 0; i < phi.valueCount(); ++i) { + if (phi.valueAt(i) == n) { + block = getCommonDominator(block, mergeBlock.getPredecessors().get(i)); + } + } + } else { + block = getCommonDominator(block, assignLatestPossibleBlockToNode(usage)); + } } + TTY.println("assigning block " + block + " to node " + n); nodeToBlock.set(n, block); + if (block != null) { + block.getInstructions().add(n); + } return block; } @@ -227,22 +271,24 @@ private void sortNodesWithinBlocks(Block b, NodeBitMap map) { List instructions = b.getInstructions(); - - Collections.shuffle(instructions); - List sortedInstructions = new ArrayList(); + assert !map.isMarked(b.firstNode()) && nodeToBlock.get(b.firstNode()) == b; + addToSorting(b, b.firstNode(), sortedInstructions, map); for (Node i : instructions) { addToSorting(b, i, sortedInstructions, map); } + addToSorting(b, b.lastNode(), sortedInstructions, map); + //assert b.firstNode() == sortedInstructions.get(0) : b.firstNode(); + // assert b.lastNode() == sortedInstructions.get(sortedInstructions.size() - 1); b.setInstructions(sortedInstructions); -// TTY.println("Block " + b); -// for (Node n : sortedInstructions) { -// TTY.println("Node: " + n); -// } + TTY.println("Block " + b); + for (Node n : sortedInstructions) { + TTY.println("Node: " + n); + } } private void addToSorting(Block b, Node i, List sortedInstructions, NodeBitMap map) { - if (i == null || map.isMarked(i) || nodeToBlock.get(i) != b || i instanceof Phi || i instanceof FrameState || i instanceof Local) { + if (i == null || map.isMarked(i) || nodeToBlock.get(i) != b || i instanceof Phi || i instanceof Local) { return; } @@ -254,9 +300,18 @@ addToSorting(b, pred, sortedInstructions, map); } + map.mark(i); + + for (Node succ : i.successors()) { + if (succ instanceof FrameState) { + addToSorting(b, succ, sortedInstructions, map); + } + } + // Now predecessors and inputs are scheduled => we can add this node. - sortedInstructions.add(i); - map.mark(i); + if (!(i instanceof FrameState)) { + sortedInstructions.add(i); + } } private void computeDominators() { diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/alloc/EdgeMoveOptimizer.java --- a/graal/GraalCompiler/src/com/sun/c1x/alloc/EdgeMoveOptimizer.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/alloc/EdgeMoveOptimizer.java Fri May 27 19:57:56 2011 +0200 @@ -190,7 +190,7 @@ List instructions = block.lir().instructionsList(); assert numSux == 2 : "method should not be called otherwise"; - assert instructions.get(instructions.size() - 1).code == LIROpcode.Branch : "block with successor must end with branch"; + assert instructions.get(instructions.size() - 1).code == LIROpcode.Branch : "block with successor must end with branch block=B" + block.blockID(); assert instructions.get(instructions.size() - 1) instanceof LIRBranch : "branch must be LIROpBranch"; assert ((LIRBranch) instructions.get(instructions.size() - 1)).cond() == Condition.TRUE : "block must end with unconditional branch"; diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java --- a/graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java Fri May 27 19:57:56 2011 +0200 @@ -1466,12 +1466,12 @@ } } - protected LIRDebugInfo stateFor(Instruction x) { + protected LIRDebugInfo stateFor(Value x) { assert lastState != null : "must have state before instruction for " + x; return stateFor(x, lastState); } - protected LIRDebugInfo stateFor(Instruction x, FrameState state) { + protected LIRDebugInfo stateFor(Value x, FrameState state) { if (compilation.placeholderState != null) { state = compilation.placeholderState; } @@ -1540,7 +1540,7 @@ } } // the value must be a constant or have a valid operand - assert operand.isLegal() : "this root has not been visited yet"; + assert operand.isLegal() : "this root has not been visited yet; instruction=" + instruction; return operand; } diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/graph/CriticalEdgeFinder.java --- a/graal/GraalCompiler/src/com/sun/c1x/graph/CriticalEdgeFinder.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/graph/CriticalEdgeFinder.java Fri May 27 19:57:56 2011 +0200 @@ -105,8 +105,8 @@ // This goto is not a safepoint. Anchor e = new Anchor(null, graph); - Node sourceInstruction = source.getInstructions().get(source.getInstructions().size() - 1); - Node targetInstruction = target.getInstructions().get(0); + Node sourceInstruction = source.lastInstruction(); + Node targetInstruction = target.firstInstruction(); int sourceInstructionPredIndex = targetInstruction.predecessors().indexOf(sourceInstruction); assert sourceInstructionPredIndex != -1 : "must find source instruction " + sourceInstruction + " in predecessor array of target instruction " + targetInstruction; int replacedIndex = targetInstruction.predecessorsIndex().get(sourceInstructionPredIndex); diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java --- a/graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java Fri May 27 19:57:56 2011 +0200 @@ -1031,13 +1031,17 @@ } private Value appendConstant(CiConstant constant) { - return appendWithBCI(new Constant(constant, graph)); + return append(new Constant(constant, graph)); } private Value append(Instruction x) { return appendWithBCI(x); } + private Value append(Value v) { + return v; + } + private Value appendWithBCI(Instruction x) { if (x.isAppended()) { // the instruction has already been added @@ -1093,7 +1097,7 @@ private Value synchronizedObject(FrameStateAccess state, RiMethod target) { if (isStatic(target.accessFlags())) { Constant classConstant = new Constant(target.holder().getEncoding(Representation.JavaClass), graph); - return appendWithBCI(classConstant); + return append(classConstant); } else { return state.localAt(0); } diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/graph/IR.java --- a/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java Fri May 27 19:57:56 2011 +0200 @@ -90,6 +90,9 @@ map.put(b, block); block.setInstructions(b.getInstructions()); block.setLinearScanNumber(b.blockID()); + + block.setFirstInstruction(b.firstNode()); + block.setLastInstruction(b.lastNode()); lirBlocks.add(block); } diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/ir/ArrayLength.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/ArrayLength.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/ArrayLength.java Fri May 27 19:57:56 2011 +0200 @@ -56,7 +56,7 @@ } @Override - public boolean valueEqual(Instruction i) { + public boolean valueEqual(Node i) { if (i instanceof ArrayLength) { ArrayLength o = (ArrayLength) i; return array() == o.array(); diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/ir/CheckCast.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/CheckCast.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/CheckCast.java Fri May 27 19:57:56 2011 +0200 @@ -78,7 +78,7 @@ } @Override - public boolean valueEqual(Instruction i) { + public boolean valueEqual(Node i) { if (i instanceof CheckCast) { CheckCast o = (CheckCast) i; return targetClass == o.targetClass && object() == o.object(); diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/ir/Constant.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/Constant.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Constant.java Fri May 27 19:57:56 2011 +0200 @@ -33,7 +33,7 @@ * The {@code Constant} instruction represents a constant such as an integer value, * long, float, object reference, address, etc. */ -public final class Constant extends Instruction { +public final class Constant extends Value { private static final int INPUT_COUNT = 0; private static final int SUCCESSOR_COUNT = 0; @@ -164,7 +164,7 @@ } @Override - public boolean valueEqual(Instruction i) { + public boolean valueEqual(Node i) { return i instanceof Constant && ((Constant) i).value.equivalent(this.value); } diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/ir/Convert.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/Convert.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Convert.java Fri May 27 19:57:56 2011 +0200 @@ -88,7 +88,7 @@ } @Override - public boolean valueEqual(Instruction i) { + public boolean valueEqual(Node i) { if (i instanceof Convert) { Convert o = (Convert) i; return opcode == o.opcode && value() == o.value(); diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/ir/IfOp.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/IfOp.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/IfOp.java Fri May 27 19:57:56 2011 +0200 @@ -119,7 +119,7 @@ } @Override - public boolean valueEqual(Instruction i) { + public boolean valueEqual(Node i) { if (i instanceof IfOp) { IfOp o = (IfOp) i; return opcode == o.opcode && x() == o.x() && y() == o.y() && trueValue() == o.trueValue() && falseValue() == o.falseValue(); diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/ir/InstanceOf.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/InstanceOf.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/InstanceOf.java Fri May 27 19:57:56 2011 +0200 @@ -59,7 +59,7 @@ } @Override - public boolean valueEqual(Instruction i) { + public boolean valueEqual(Node i) { if (i instanceof InstanceOf) { InstanceOf o = (InstanceOf) i; return targetClass == o.targetClass && object() == o.object(); diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/ir/Instruction.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/Instruction.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Instruction.java Fri May 27 19:57:56 2011 +0200 @@ -145,38 +145,6 @@ return (Instruction) predecessors().get(j); } - @Override - public Merge block() { - Instruction cur = this; - while (!(cur instanceof Merge)) { - List preds = cur.predecessors(); - cur = (Instruction) preds.get(0); - } - return (Merge) cur; - } - - /** - * Compute the value number of this Instruction. Local and global value numbering - * optimizations use a hash map, and the value number provides a hash code. - * If the instruction cannot be value numbered, then this method should return - * {@code 0}. - * @return the hashcode of this instruction - */ - public int valueNumber() { - return 0; - } - - /** - * Checks that this instruction is equal to another instruction for the purposes - * of value numbering. - * @param i the other instruction - * @return {@code true} if this instruction is equivalent to the specified - * instruction w.r.t. value numbering - */ - public boolean valueEqual(Instruction i) { - return false; - } - /** * Gets the state after the instruction, if it is recorded. Typically only * instances of {@link BlockEnd} have a non-null state after. diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/ir/Local.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/Local.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Local.java Fri May 27 19:57:56 2011 +0200 @@ -46,11 +46,6 @@ this.inputs().set(0, graph.start()); } - @Override - public Merge block() { - return null; - } - /** * Gets the index of this local. * @return the index diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/ir/Merge.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/Merge.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Merge.java Fri May 27 19:57:56 2011 +0200 @@ -126,12 +126,12 @@ //} // print predecessors - if (!blockPredecessors().isEmpty()) { - out.print(" pred:"); - for (Instruction pred : blockPredecessors()) { - out.print(pred.block()); - } - } +// if (!blockPredecessors().isEmpty()) { +// out.print(" pred:"); +// for (Instruction pred : blockPredecessors()) { +// out.print(pred.block()); +// } +// } } @Override diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/ir/NegateOp.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/NegateOp.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/NegateOp.java Fri May 27 19:57:56 2011 +0200 @@ -79,7 +79,7 @@ } @Override - public boolean valueEqual(Instruction i) { + public boolean valueEqual(Node i) { if (i instanceof NegateOp) { NegateOp o = (NegateOp) i; return x() == o.x(); diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/ir/NullCheck.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/NullCheck.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/NullCheck.java Fri May 27 19:57:56 2011 +0200 @@ -82,7 +82,7 @@ } @Override - public boolean valueEqual(Instruction i) { + public boolean valueEqual(Node i) { if (i instanceof NullCheck) { NullCheck o = (NullCheck) i; return object() == o.object(); diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/ir/Op2.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/Op2.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Op2.java Fri May 27 19:57:56 2011 +0200 @@ -30,7 +30,7 @@ /** * The {@code Op2} class is the base of arithmetic and logic operations with two inputs. */ -public abstract class Op2 extends Instruction { +public abstract class Op2 extends Value { private static final int INPUT_COUNT = 2; private static final int INPUT_X = 0; @@ -105,7 +105,7 @@ } @Override - public boolean valueEqual(Instruction i) { + public boolean valueEqual(Node i) { if (i instanceof Op2) { Op2 o = (Op2) i; return opcode == o.opcode && x() == o.x() && y() == o.y(); diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/ir/Phi.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/Phi.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Phi.java Fri May 27 19:57:56 2011 +0200 @@ -49,7 +49,6 @@ /** * The join block for this phi. */ - @Override public Merge block() { return (Merge) inputs().get(super.inputCount() + INPUT_BLOCK); } diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/ir/Value.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/Value.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Value.java Fri May 27 19:57:56 2011 +0200 @@ -56,8 +56,6 @@ protected CiValue operand = CiValue.IllegalValue; - public abstract Merge block(); - /** * Creates a new value with the specified kind. * @param kind the type of this value @@ -266,6 +264,28 @@ } /** + * Compute the value number of this Instruction. Local and global value numbering + * optimizations use a hash map, and the value number provides a hash code. + * If the instruction cannot be value numbered, then this method should return + * {@code 0}. + * @return the hashcode of this instruction + */ + public int valueNumber() { + return 0; + } + + /** + * Checks that this instruction is equal to another instruction for the purposes + * of value numbering. + * @param i the other instruction + * @return {@code true} if this instruction is equivalent to the specified + * instruction w.r.t. value numbering + */ + public boolean valueEqual(Node i) { + return false; + } + + /** * This method supports the visitor pattern by accepting a visitor and calling the * appropriate {@code visit()} method. * diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java --- a/graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java Fri May 27 19:57:56 2011 +0200 @@ -277,4 +277,25 @@ public FrameState lastState() { return lastState; } + + private Node first; + private Node last; + + public Node firstInstruction() { + return first; + } + + + public Node lastInstruction() { + return last; + } + + public void setFirstInstruction(Node n) { + first = n; + } + + + public void setLastInstruction(Node n) { + last = n; + } } diff -r 095162a84dcc -r c3f64b66fc78 graal/GraalCompiler/src/com/sun/c1x/value/FrameState.java --- a/graal/GraalCompiler/src/com/sun/c1x/value/FrameState.java Fri May 27 18:44:13 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/value/FrameState.java Fri May 27 19:57:56 2011 +0200 @@ -445,11 +445,6 @@ } @Override - public Merge block() { - return null; - } - - @Override public void accept(ValueVisitor v) { v.visitFrameState(this); }