# HG changeset patch # User Gilles Duboscq # Date 1308592931 -7200 # Node ID 4afbc254f02d2a990988023bd35acc9d691df87d # Parent 5e8f827157904010c563a6b417388e04ca64f026# Parent 3a7043d555e186086159f2b578bf75ac29fbc793 Merge diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompilation.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompilation.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompilation.java Mon Jun 20 20:02:11 2011 +0200 @@ -217,7 +217,7 @@ if (t instanceof RuntimeException) { throw (RuntimeException) t; } else { - throw new RuntimeException(t); + throw new RuntimeException("Exception while compiling: " + method, t); } } } finally { diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Mon Jun 20 20:02:11 2011 +0200 @@ -138,4 +138,5 @@ public static boolean PrintLIRWithAssembly = ____; public static boolean OptCanonicalizer = true; + public static boolean OptLoops = true; } diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/EdgeMoveOptimizer.java diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java Mon Jun 20 20:02:11 2011 +0200 @@ -835,10 +835,10 @@ if (instr instanceof Phi) { Phi phi = (Phi) instr; TTY.println("phi block begin: " + phi.merge()); - TTY.println("pred count on blockbegin: " + phi.merge().predecessors().size()); + TTY.println("pred count on blockbegin: " + phi.merge().phiPredecessorCount()); TTY.println("phi values: " + phi.valueCount()); TTY.println("phi block preds:"); - for (Node n : phi.merge().predecessors()) { + for (Node n : phi.merge().phiPredecessors()) { TTY.println(n.toString()); } } diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java Mon Jun 20 20:02:11 2011 +0200 @@ -28,6 +28,7 @@ import com.oracle.max.graal.compiler.ir.*; import com.oracle.max.graal.compiler.schedule.*; +import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; /** @@ -131,14 +132,14 @@ } stream.println(" "); - stream.println(" "); if (schedule != null) { + stream.println(" "); for (Block block : schedule.getBlocks()) { - printBlock(graph, block); + printBlock(graph, block, schedule.getNodeToBlock()); } + printNoBlock(); + stream.println(" "); } - printNoBlock(); - stream.println(" "); stream.println(" "); flush(); @@ -165,9 +166,13 @@ } stream.printf("

%s

%n", escape(name)); } + stream.printf("

%s

%n", escape(node.getClass().getSimpleName())); Block block = nodeToBlock == null ? null : nodeToBlock.get(node); if (block != null) { stream.printf("

%d

%n", block.blockID()); + if (!(node instanceof Phi || node instanceof FrameState || node instanceof Local) && !block.getInstructions().contains(node)) { + stream.printf("

true

%n"); + } } else { stream.printf("

noBlock

%n"); noBlockNodes.add(node); @@ -206,23 +211,36 @@ stream.printf(" %n", edge.from, edge.fromIndex, edge.to, edge.toIndex); } - private void printBlock(Graph graph, Block block) { + private void printBlock(Graph graph, Block block, NodeMap nodeToBlock) { stream.printf(" %n", block.blockID()); stream.printf(" %n"); for (Block sux : block.getSuccessors()) { - if (sux.firstNode() instanceof LoopBegin && block.lastNode() instanceof LoopEnd) { - // Skip back edges. - } else { +// if (sux.firstNode() instanceof LoopBegin && block.lastNode() instanceof LoopEnd) { //TODO gd +// // Skip back edges. +// } else { stream.printf(" %n", sux.blockID()); - } +// } } stream.printf(" %n"); stream.printf(" %n"); - ArrayList nodes = new ArrayList(block.getInstructions()); + Set nodes = new HashSet(block.getInstructions()); + + if (nodeToBlock != null) { + for (Node n : graph.getNodes()) { + if (n == null) { + continue; + } + Block blk = nodeToBlock.get(n); + if (blk == block) { + nodes.add(n); + } + } + } + if (nodes.size() > 0) { // if this is the first block: add all locals to this block - if (nodes.get(0) == graph.start()) { + if (block.getInstructions().size() > 0 && block.getInstructions().get(0) == graph.start()) { for (Node node : graph.getNodes()) { if (node instanceof Local) { nodes.add(node); @@ -236,8 +254,7 @@ nodes.add(((Instruction) node).stateAfter()); } if (node instanceof Merge) { - Merge merge = (Merge) node; - for (Node usage : merge.usages()) { + for (Node usage : node.usages()) { if (usage instanceof Phi || usage instanceof LoopCounter) { nodes.add(usage); } diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Mon Jun 20 20:02:11 2011 +0200 @@ -33,7 +33,7 @@ import com.oracle.max.asm.*; import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.alloc.*; -import com.oracle.max.graal.compiler.alloc.OperandPool.*; +import com.oracle.max.graal.compiler.alloc.OperandPool.VariableFlag; import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.compiler.globalstub.*; import com.oracle.max.graal.compiler.graph.*; @@ -43,11 +43,17 @@ import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; +import com.sun.cri.bytecode.Bytecodes.MemoryBarriers; import com.sun.cri.ci.*; import com.sun.cri.ri.*; -import com.sun.cri.ri.RiType.*; +import com.sun.cri.ri.RiType.Representation; +import com.sun.cri.xir.CiXirAssembler.XirConstant; +import com.sun.cri.xir.CiXirAssembler.XirInstruction; +import com.sun.cri.xir.CiXirAssembler.XirOperand; +import com.sun.cri.xir.CiXirAssembler.XirParameter; +import com.sun.cri.xir.CiXirAssembler.XirRegister; +import com.sun.cri.xir.CiXirAssembler.XirTemp; import com.sun.cri.xir.*; -import com.sun.cri.xir.CiXirAssembler.*; /** * This class traverses the HIR instructions and generates LIR instructions from them. @@ -255,7 +261,9 @@ } } if (block.blockSuccessors().size() >= 1 && !block.endsWithJump()) { - block.lir().jump(getLIRBlock((FixedNode) block.lastInstruction().successors().get(0))); + NodeArray successors = block.lastInstruction().successors(); + assert successors.size() >= 1 : "should have at least one successor : " + block.lastInstruction(); + block.lir().jump(getLIRBlock((FixedNode) successors.get(0))); } if (GraalOptions.TraceLIRGeneratorLevel >= 1) { @@ -269,7 +277,9 @@ @Override public void visitMerge(Merge x) { - // Nothing to do. + if (x.next() instanceof LoopBegin) { + moveToPhi((LoopBegin) x.next(), x); + } } @Override @@ -1039,7 +1049,7 @@ lastState = fs; } else if (block.blockPredecessors().size() == 1) { FrameState fs = block.blockPredecessors().get(0).lastState(); - assert fs != null; + assert fs != null; //TODO gd maybe this assert should be removed if (GraalOptions.TraceLIRGeneratorLevel >= 2) { TTY.println("STATE CHANGE (singlePred)"); if (GraalOptions.TraceLIRGeneratorLevel >= 3) { @@ -1390,7 +1400,7 @@ } } - void moveToPhi(PhiResolver resolver, Value curVal, Value suxVal, List phis, int predIndex) { + /*void moveToPhi(PhiResolver resolver, Value curVal, Value suxVal, List phis, int predIndex) { // move current value to referenced phi function if (suxVal instanceof Phi) { Phi phi = (Phi) suxVal; @@ -1416,30 +1426,12 @@ resolver.move(operand, operandForPhi(phi)); } } - } - - private List getPhis(LIRBlock block) { - if (block.getInstructions().size() > 0) { - Node i = block.firstInstruction(); - if (i instanceof Merge) { - List result = new ArrayList(); - for (Node n : i.usages()) { - if (n instanceof Phi) { - result.add((Phi) n); - } - } - return result; - } - } - return null; - } + }*/ @Override public void visitEndNode(EndNode end) { setNoResult(end); - Merge merge = end.merge(); - assert merge != null; - moveToPhi(merge, merge.endIndex(end)); + moveToPhi(end.merge(), end); lir.jump(getLIRBlock(end.merge())); } @@ -1458,49 +1450,45 @@ @Override public void visitLoopEnd(LoopEnd x) { setNoResult(x); - moveToPhi(x.loopBegin(), x.loopBegin().endCount()); + moveToPhi(x.loopBegin(), x); lir.jump(getLIRBlock(x.loopBegin())); } - private void moveToPhi(Merge merge, int nextSuccIndex) { + private void moveToPhi(Merge merge, Node pred) { + int nextSuccIndex = merge.phiPredecessorIndex(pred); PhiResolver resolver = new PhiResolver(this); - for (Node n : merge.usages()) { - if (n instanceof Phi) { - Phi phi = (Phi) n; - if (!phi.isDead()) { - Value curVal = phi.valueAt(nextSuccIndex); - if (curVal != null && curVal != phi) { - if (curVal instanceof Phi) { - operandForPhi((Phi) curVal); - } - CiValue operand = curVal.operand(); - if (operand.isIllegal()) { - assert curVal instanceof Constant || curVal instanceof Local : "these can be produced lazily" + curVal + "/" + phi; - operand = operandForInstruction(curVal); - } - resolver.move(operand, operandForPhi(phi)); + for (Phi phi : merge.phis()) { + if (!phi.isDead()) { + Value curVal = phi.valueAt(nextSuccIndex); + if (curVal != null && curVal != phi) { + if (curVal instanceof Phi) { + operandForPhi((Phi) curVal); } + CiValue operand = curVal.operand(); + if (operand.isIllegal()) { + assert curVal instanceof Constant || curVal instanceof Local : "these can be produced lazily" + curVal + "/" + phi; + operand = operandForInstruction(curVal); + } + resolver.move(operand, operandForPhi(phi)); } } } resolver.dispose(); - //TODO (gd) remove that later + //TODO (gd) remove that later ? if (merge instanceof LoopBegin) { - for (Node usage : merge.usages()) { - if (usage instanceof LoopCounter) { - LoopCounter counter = (LoopCounter) usage; - if (counter.operand().isIllegal()) { - createResultVariable(counter); - } - if (nextSuccIndex == 0) { // (gd) nasty - lir.move(operandForInstruction(counter.init()), counter.operand()); + LoopBegin loopBegin = (LoopBegin) merge; + for (LoopCounter counter : loopBegin.counters()) { + if (counter.operand().isIllegal()) { + createResultVariable(counter); + } + if (nextSuccIndex == 0) { + lir.move(operandForInstruction(counter.init()), counter.operand()); + } else { + if (counter.kind == CiKind.Int) { + this.arithmeticOpInt(IADD, counter.operand(), counter.operand(), operandForInstruction(counter.stride()), CiValue.IllegalValue); } else { - if (counter.kind == CiKind.Int) { - this.arithmeticOpInt(IADD, counter.operand(), counter.operand(), operandForInstruction(counter.stride()), CiValue.IllegalValue); - } else { - assert counter.kind == CiKind.Long; - this.arithmeticOpLong(LADD, counter.operand(), counter.operand(), operandForInstruction(counter.stride())); - } + assert counter.kind == CiKind.Long; + this.arithmeticOpLong(LADD, counter.operand(), counter.operand(), operandForInstruction(counter.stride())); } } } diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/BlockMap.java diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Mon Jun 20 20:02:11 2011 +0200 @@ -91,18 +91,18 @@ if (GraalOptions.Inline) { new InliningPhase(compilation, this, GraalOptions.TraceInlining).apply(compilation.graph); - //printGraph("After Ininling", compilation.graph); } Graph graph = compilation.graph; if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase().apply(graph); - new DeadCodeEliminationPhase().apply(compilation.graph); - //printGraph("After Canonicalization", graph); + new DeadCodeEliminationPhase().apply(graph); } - new LoopPhase().apply(graph); + if (GraalOptions.OptLoops) { + new LoopPhase().apply(graph); + } if (GraalOptions.Lower) { new LoweringPhase(compilation.runtime).apply(graph); diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java Mon Jun 20 20:02:11 2011 +0200 @@ -30,6 +30,7 @@ public final class EndNode extends FixedNode { public static final int SUCCESSOR_COUNT = 0; public static final int INPUT_COUNT = 0; + public EndNode(Graph graph) { super(CiKind.Illegal, INPUT_COUNT, SUCCESSOR_COUNT, graph); } diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java Mon Jun 20 20:02:11 2011 +0200 @@ -22,16 +22,16 @@ */ package com.oracle.max.graal.compiler.ir; +import java.util.*; + import com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.graph.*; -public class LoopBegin extends Merge { - - private static final int INPUT_COUNT = 0; - private static final int SUCCESSOR_COUNT = 0; - +public class LoopBegin extends Merge{ public LoopBegin(Graph graph) { - super(INPUT_COUNT, SUCCESSOR_COUNT, graph); + super(graph); + this.addEnd(new EndNode(graph)); } public LoopEnd loopEnd() { @@ -67,4 +67,39 @@ LoopBegin x = new LoopBegin(into); return x; } + + @Override + public int phiPredecessorCount() { + return 2; + } + + @Override + public int phiPredecessorIndex(Node pred) { + if (pred == forwardEdge()) { + return 0; + } else if (pred == this.loopEnd()) { + return 1; + } + throw Util.shouldNotReachHere("unknown pred : " + pred + "(sp=" + forwardEdge() + ", le=" + this.loopEnd() + ")"); + } + + public Collection counters() { + return Util.filter(this.usages(), LoopCounter.class); + } + + @Override + public List phiPredecessors() { + return Arrays.asList(new Node[]{this.forwardEdge(), this.loopEnd()}); + } + + public EndNode forwardEdge() { + return this.endAt(0); + } + + @Override + public boolean verify() { + assertTrue(loopEnd() != null); + assertTrue(forwardEdge() != null); + return true; + } } diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java Mon Jun 20 20:02:11 2011 +0200 @@ -22,6 +22,8 @@ */ package com.oracle.max.graal.compiler.ir; +import java.util.*; + import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.compiler.value.*; @@ -33,7 +35,7 @@ * about the basic block, including the successor and * predecessor blocks, exception handlers, liveness information, etc. */ -public class Merge extends StateSplit { +public class Merge extends StateSplit{ private static final int INPUT_COUNT = 0; @@ -90,6 +92,29 @@ return (EndNode) inputs().variablePart().get(index); } + public Iterable mergePredecessors() { + return new Iterable() { + @Override + public Iterator iterator() { + return new Iterator() { + int i = 0; + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + @Override + public Node next() { + return Merge.this.endAt(i++); + } + @Override + public boolean hasNext() { + return i < Merge.this.endCount(); + } + }; + } + }; + } + @Override public String toString() { StringBuilder builder = new StringBuilder(); @@ -296,4 +321,21 @@ } } } + + public int phiPredecessorCount() { + return endCount(); + } + + public int phiPredecessorIndex(Node pred) { + EndNode end = (EndNode) pred; + return endIndex(end); + } + + public Collection phis() { + return Util.filter(this.usages(), Phi.class); + } + + public List phiPredecessors() { + return Collections.unmodifiableList(inputs().variablePart()); + } } diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java Mon Jun 20 20:02:11 2011 +0200 @@ -58,7 +58,7 @@ return (Merge) inputs().get(super.inputCount() + INPUT_MERGE); } - public void setMerge(Value n) { + public void setMerge(Merge n) { inputs().set(super.inputCount() + INPUT_MERGE, n); } @@ -67,11 +67,15 @@ setMerge(merge); } + Phi(CiKind kind, Graph graph) { + super(kind, INPUT_COUNT, SUCCESSOR_COUNT, graph); + } + @Override public boolean verify() { assertTrue(merge() != null); if (!isDead()) { - assertTrue(merge().endCount() + (merge() instanceof LoopBegin ? 1 : 0) == valueCount()); + assertTrue(merge().phiPredecessorCount() == valueCount()); } return true; } @@ -148,7 +152,7 @@ @Override public Node copy(Graph into) { - Phi x = new Phi(kind, null, into); + Phi x = new Phi(kind, into); x.isDead = isDead; return x; } diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java Mon Jun 20 20:02:11 2011 +0200 @@ -45,7 +45,7 @@ // remove chained Merges for (Merge merge : graph.getNodes(Merge.class)) { - if (merge.endCount() == 1 && merge.usages().size() == 0 && !(merge instanceof LoopEnd) && !(merge instanceof LoopBegin)) { + if (merge.endCount() == 1 && merge.usages().size() == 0 && !(merge instanceof LoopEnd || merge instanceof LoopBegin)) { FixedNode next = merge.next(); EndNode endNode = merge.endAt(0); merge.delete(); diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Mon Jun 20 20:02:11 2011 +0200 @@ -31,8 +31,10 @@ import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.compiler.graph.*; -import com.oracle.max.graal.compiler.graph.BlockMap.*; import com.oracle.max.graal.compiler.graph.BlockMap.Block; +import com.oracle.max.graal.compiler.graph.BlockMap.BranchOverride; +import com.oracle.max.graal.compiler.graph.BlockMap.DeoptBlock; +import com.oracle.max.graal.compiler.graph.BlockMap.ExceptionBlock; import com.oracle.max.graal.compiler.ir.*; import com.oracle.max.graal.compiler.ir.Deoptimize.DeoptAction; import com.oracle.max.graal.compiler.schedule.*; @@ -42,7 +44,7 @@ import com.sun.cri.bytecode.*; import com.sun.cri.ci.*; import com.sun.cri.ri.*; -import com.sun.cri.ri.RiType.*; +import com.sun.cri.ri.RiType.Representation; /** * The {@code GraphBuilder} class parses the bytecode of a method and builds the IR graph. @@ -281,31 +283,31 @@ } public void mergeOrClone(Block target, FrameStateAccess newState) { - Instruction first = target.firstInstruction; + StateSplit first = (StateSplit) target.firstInstruction; + if (target.isLoopHeader && isVisited(target)) { - first = ((LoopBegin) first).loopEnd(); + first = loopBegin(target).loopEnd(); } - assert first instanceof StateSplit; int bci = target.startBci; if (target instanceof ExceptionBlock) { bci = ((ExceptionBlock) target).deoptBci; } - FrameState existingState = ((StateSplit) first).stateAfter(); + FrameState existingState = first.stateAfter(); if (existingState == null) { // copy state because it is modified FrameState duplicate = newState.duplicate(bci); // if the block is a loop header, insert all necessary phis - if (first instanceof LoopBegin && target.isLoopHeader) { - assert first instanceof Merge; - insertLoopPhis((Merge) first, duplicate); - ((Merge) first).setStateAfter(duplicate); - } else { - ((StateSplit) first).setStateAfter(duplicate); + if (target.isLoopHeader && !isVisited(target)) { + LoopBegin loopBegin = loopBegin(target); + assert target.firstInstruction instanceof Placeholder && loopBegin != null; + //System.out.println("insertLoopPhis with " + target.loopHeaderState); + insertLoopPhis(loopBegin, loopBegin.stateAfter()); } + first.setStateAfter(duplicate); } else { if (!GraalOptions.AssumeVerifiedBytecode && !existingState.isCompatibleWith(newState)) { // stacks or locks do not match--bytecodes would not verify @@ -318,14 +320,14 @@ if (first instanceof Placeholder) { Placeholder p = (Placeholder) first; - assert !target.isLoopHeader; if (p.predecessors().size() == 0) { p.setStateAfter(newState.duplicate(bci)); return; } else { Merge merge = new Merge(graph); assert p.predecessors().size() == 1 : "predecessors size: " + p.predecessors().size(); - assert p.next() == null; + merge.setNext(p.next()); + p.setNext(null); EndNode end = new EndNode(graph); p.replace(end); merge.addEnd(end); @@ -339,20 +341,20 @@ } } - private void insertLoopPhis(Merge merge, FrameState newState) { + private void insertLoopPhis(LoopBegin loopBegin, FrameState newState) { int stackSize = newState.stackSize(); for (int i = 0; i < stackSize; i++) { // always insert phis for the stack Value x = newState.stackAt(i); if (x != null) { - newState.setupPhiForStack(merge, i).addInput(x); + newState.setupPhiForStack(loopBegin, i).addInput(x); } } int localsSize = newState.localsSize(); for (int i = 0; i < localsSize; i++) { Value x = newState.localAt(i); if (x != null) { - newState.setupPhiForLocal(merge, i).addInput(x); + newState.setupPhiForLocal(loopBegin, i).addInput(x); } } } @@ -1157,7 +1159,10 @@ LoopBegin loopBegin = new LoopBegin(graph); LoopEnd loopEnd = new LoopEnd(graph); loopEnd.setLoopBegin(loopBegin); - block.firstInstruction = loopBegin; + Placeholder p = new Placeholder(graph); + p.setNext(loopBegin.forwardEdge()); + loopBegin.setStateAfter(stateAfter.duplicate(block.startBci)); + block.firstInstruction = p; } else { block.firstInstruction = new Placeholder(graph); } @@ -1166,8 +1171,8 @@ addToWorkList(block); FixedNode result = null; - if (block.firstInstruction instanceof LoopBegin && isVisited(block)) { - result = ((LoopBegin) block.firstInstruction).loopEnd(); + if (block.isLoopHeader && isVisited(block)) { + result = loopBegin(block).loopEnd(); } else { result = block.firstInstruction; } @@ -1175,11 +1180,15 @@ assert result instanceof Merge || result instanceof Placeholder : result; if (result instanceof Merge) { - EndNode end = new EndNode(graph); - //end.setNext(result); - ((Merge) result).addEnd(end); - result = end; + if (result instanceof LoopBegin) { + result = ((LoopBegin) result).forwardEdge(); + } else { + EndNode end = new EndNode(graph); + ((Merge) result).addEnd(end); + result = end; + } } + assert !(result instanceof LoopBegin || result instanceof Merge); return result; } @@ -1205,9 +1214,13 @@ if (!isVisited(block)) { markVisited(block); // now parse the block - frameState.initializeFrom(((StateSplit) block.firstInstruction).stateAfter()); - lastInstr = block.firstInstruction; - assert block.firstInstruction.next() == null : "instructions already appended at block " + block.blockID; + if (block.isLoopHeader) { + lastInstr = loopBegin(block); + } else { + lastInstr = block.firstInstruction; + } + frameState.initializeFrom(((StateSplit) lastInstr).stateAfter()); + assert lastInstr.next() == null : "instructions already appended at block " + block.blockID; if (block == returnBlock) { createReturnBlock(block); @@ -1224,8 +1237,8 @@ } for (Block b : blocksVisited) { if (b.isLoopHeader) { - LoopBegin begin = (LoopBegin) b.firstInstruction; - LoopEnd end = begin.loopEnd(); + LoopBegin begin = loopBegin(b); + LoopEnd loopEnd = begin.loopEnd(); // This can happen with degenerated loops like this one: // for (;;) { @@ -1234,14 +1247,14 @@ // } catch (UnresolvedException iioe) { // } // } - if (end.stateAfter() != null) { - begin.stateAfter().merge(begin, end.stateAfter()); + if (loopEnd.stateAfter() != null) { + //loopHeaderMerge.stateBefore().merge(begin, end.stateBefore()); + //assert loopHeaderMerge.equals(end.stateBefore()); + begin.stateAfter().merge(begin, loopEnd.stateAfter()); } else { - end.delete(); + loopEnd.delete(); Merge merge = new Merge(graph); - for (int i = 0; i < begin.endCount(); ++i) { - merge.addEnd(begin.endAt(i)); - } + merge.addEnd(begin.forwardEdge()); merge.setNext(begin.next()); merge.setStateAfter(begin.stateAfter()); begin.replace(merge); @@ -1250,6 +1263,12 @@ } } + private static LoopBegin loopBegin(Block block) { + EndNode endNode = (EndNode) block.firstInstruction.next(); + LoopBegin loopBegin = (LoopBegin) endNode.merge(); + return loopBegin; + } + private void createDeoptBlock(DeoptBlock block) { storeResultGraph = false; append(new Deoptimize(DeoptAction.InvalidateReprofile, graph)); diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Mon Jun 20 20:02:11 2011 +0200 @@ -25,6 +25,7 @@ import java.util.*; import com.oracle.max.graal.compiler.ir.*; +import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; @@ -50,6 +51,7 @@ private void mergeLoopCounters(List counters, LoopBegin loopBegin) { Graph graph = loopBegin.graph(); + FrameState stateAfter = loopBegin.stateAfter(); LoopCounter[] acounters = counters.toArray(new LoopCounter[counters.size()]); for (int i = 0; i < acounters.length; i++) { LoopCounter c1 = acounters[i]; @@ -59,16 +61,30 @@ for (int j = i + 1; j < acounters.length; j++) { LoopCounter c2 = acounters[j]; if (c2 != null && c1.stride().valueEqual(c2.stride())) { + boolean c1InCompare = Util.filter(c1.usages(), Compare.class).size() > 0; + boolean c2inCompare = Util.filter(c2.usages(), Compare.class).size() > 0; + if (c2inCompare && !c1InCompare) { + c1 = acounters[j]; + c2 = acounters[i]; + acounters[i] = c2; + acounters[j] = c1; + } + boolean c2InFramestate = stateAfter != null ? stateAfter.inputs().contains(c2) : false; acounters[j] = null; CiKind kind = c1.kind; - IntegerSub sub = new IntegerSub(kind, c2.init(), c1.init(), graph); - IntegerAdd addStride = new IntegerAdd(kind, sub, c1.stride(), graph); - IntegerAdd add = new IntegerAdd(kind, c1, addStride, graph); - Phi phi = new Phi(kind, loopBegin, graph); // TODO (gd) assumes order on loopBegin preds - phi.addInput(c2.init()); - phi.addInput(add); - c2.replace(phi); - //System.out.println("--> merged Loop Counters"); + if (c2InFramestate) { + IntegerSub sub = new IntegerSub(kind, c2.init(), c1.init(), graph); + IntegerAdd addStride = new IntegerAdd(kind, sub, c1.stride(), graph); + IntegerAdd add = new IntegerAdd(kind, c1, addStride, graph); + Phi phi = new Phi(kind, loopBegin, graph); // TODO (gd) assumes order on loopBegin preds + phi.addInput(c2.init()); + phi.addInput(add); + c2.replace(phi); + } else { + IntegerSub sub = new IntegerSub(kind, c2.init(), c1.init(), graph); + IntegerAdd add = new IntegerAdd(kind, c1, sub, graph); + c2.replace(add); + } } } } diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/Phase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/Phase.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/Phase.java Mon Jun 20 20:02:11 2011 +0200 @@ -61,7 +61,9 @@ } GraalTimers.get(getName()).start(); } + //System.out.println("Starting Phase " + getName()); run(graph); + //System.out.println("Finished Phase " + getName()); if (GraalOptions.Time) { GraalTimers.get(getName()).stop(); if (oldCurrentPhase != null) { diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Mon Jun 20 20:02:11 2011 +0200 @@ -92,6 +92,22 @@ return trueSuccessorCount(n) > 1 || n instanceof Return || n instanceof Unwind || n instanceof Deoptimize; } + private void print() { + Block dominatorRoot = nodeToBlock.get(graph.start()); + System.out.println("Root = " + dominatorRoot); + System.out.println("nodeToBlock :"); + System.out.println(nodeToBlock); + System.out.println("Blocks :"); + for (Block b : blocks) { + System.out.println(b + " [S:" + b.getSuccessors() + ", P:" + b.getPredecessors() + ", D:" + b.getDominators()); + System.out.println(" f " + b.firstNode()); + for (Node n : b.getInstructions()) { + System.out.println(" - " + n); + } + System.out.println(" l " + b.lastNode()); + } + } + private void identifyBlocks() { // Identify blocks. @@ -110,8 +126,7 @@ // Either dead code or at a merge node => stop iteration. break; } - assert currentNode.predecessors().size() == 1 : "preds: " + currentNode; - currentNode = currentNode.predecessors().get(0); + currentNode = currentNode.singlePredecessor(); } } } @@ -122,9 +137,8 @@ Node n = block.firstNode(); if (n instanceof Merge) { Merge m = (Merge) n; - for (int i = 0; i < m.endCount(); ++i) { - EndNode end = m.endAt(i); - Block predBlock = nodeToBlock.get(end); + for (Node pred : m.mergePredecessors()) { + Block predBlock = nodeToBlock.get(pred); predBlock.addSuccessor(block); } } else { @@ -144,11 +158,11 @@ // Add successors of loop end nodes. Makes the graph cyclic. for (Block block : blocks) { - Node n = block.firstNode(); - if (n instanceof LoopBegin) { - LoopBegin loopBegin = (LoopBegin) n; - assert loopBegin.loopEnd() != null; - nodeToBlock.get(loopBegin.loopEnd()).addSuccessor(block); + Node n = block.lastNode(); + if (n instanceof LoopEnd) { + LoopEnd loopEnd = (LoopEnd) n; + assert loopEnd.loopBegin() != null; + block.addSuccessor(nodeToBlock.get(loopEnd.loopBegin())); } } @@ -257,7 +271,7 @@ if (mergeBlock.getPredecessors().size() == 0) { TTY.println(merge.toString()); TTY.println(phi.toString()); - TTY.println(merge.predecessors().toString()); + TTY.println(merge.phiPredecessors().toString()); TTY.println("value count: " + phi.valueCount()); } block = getCommonDominator(block, mergeBlock.getPredecessors().get(i)); @@ -265,8 +279,7 @@ } } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) { Merge merge = ((FrameState) usage).block(); - for (int i = 0; i < merge.endCount(); ++i) { - EndNode pred = merge.endAt(i); + for (Node pred : merge.mergePredecessors()) { block = getCommonDominator(block, nodeToBlock.get(pred)); } } else if (usage instanceof LoopCounter) { @@ -321,10 +334,24 @@ addToSorting(b, b.lastNode(), sortedInstructions, map); // Make sure that last node gets really last (i.e. when a frame state successor hangs off it). - sortedInstructions.remove(b.lastNode()); - sortedInstructions.add(b.lastNode()); - - assert sortedInstructions.get(sortedInstructions.size() - 1) == b.lastNode() : " lastNode=" + b.lastNode() + ", firstNode=" + b.firstNode() + ", sorted(sz-1)=" + sortedInstructions.get(sortedInstructions.size() - 1); + Node lastSorted = sortedInstructions.get(sortedInstructions.size() - 1); + if (lastSorted != b.lastNode()) { + int idx = sortedInstructions.indexOf(b.lastNode()); + boolean canNotMove = false; + for (int i = idx + 1; i < sortedInstructions.size(); i++) { + if (sortedInstructions.get(i).inputs().contains(b.lastNode())) { + canNotMove = true; + break; + } + } + if (canNotMove) { + assert !(b.lastNode() instanceof ControlSplit); + //b.setLastNode(lastSorted); + } else { + sortedInstructions.remove(b.lastNode()); + sortedInstructions.add(b.lastNode()); + } + } b.setInstructions(sortedInstructions); } @@ -370,8 +397,11 @@ BitMap visited = new BitMap(blocks.size()); visited.set(dominatorRoot.blockID()); LinkedList workList = new LinkedList(); - workList.add(dominatorRoot); - // TODO: Add all predecessor.size()==0 nodes. + for (Block block : blocks) { + if (block.getPredecessors().size() == 0) { + workList.add(block); + } + } while (!workList.isEmpty()) { Block b = workList.remove(); diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java Mon Jun 20 20:02:11 2011 +0200 @@ -485,7 +485,7 @@ @Override public void visitLoopBegin(LoopBegin x) { - visitMerge(x); + } @Override diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/Util.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/Util.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/Util.java Mon Jun 20 20:02:11 2011 +0200 @@ -27,6 +27,7 @@ import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.compiler.ir.*; +import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; import com.sun.cri.ri.*; @@ -424,4 +425,15 @@ public static String valueString(Value value) { return (value == null) ? "-" : ("" + value.kind.typeChar + value.id()); } + + @SuppressWarnings("unchecked") + public static Collection filter(Collection nodes, Class clazz) { + ArrayList phis = new ArrayList(); + for (Node node : nodes) { + if (clazz.isInstance(node)) { + phis.add((T) node); + } + } + return phis; + } } diff -r 5e8f82715790 -r 4afbc254f02d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java Mon Jun 20 19:46:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java Mon Jun 20 20:02:11 2011 +0200 @@ -183,6 +183,28 @@ return true; } + public boolean equals(FrameStateAccess other) { + if (stackSize() != other.stackSize() || localsSize() != other.localsSize() || locksSize() != other.locksSize()) { + return false; + } + for (int i = 0; i < stackSize(); i++) { + Value x = stackAt(i); + Value y = other.stackAt(i); + if (x != y) { + return false; + } + } + for (int i = 0; i < locksSize(); i++) { + if (lockAt(i) != other.lockAt(i)) { + return false; + } + } + if (other.outerFrameState() != outerFrameState()) { + return false; + } + return true; + } + /** * Gets the size of the local variables. */ @@ -374,7 +396,7 @@ } if (phi.valueCount() == 0) { - int size = block.endCount(); + int size = block.phiPredecessorCount(); for (int j = 0; j < size; ++j) { phi.addInput(x); } @@ -383,11 +405,7 @@ phi.addInput((x == y) ? phi : y); } - if (block instanceof LoopBegin) { -// assert phi.valueCount() == ((LoopBegin) block).loopEnd().predecessors().size() + 1 : "loop, valueCount=" + phi.valueCount() + " predSize= " + ((LoopBegin) block).loopEnd().predecessors().size(); - } else { - assert phi.valueCount() == block.endCount() + 1 : "valueCount=" + phi.valueCount() + " predSize= " + block.endCount(); - } + assert phi.valueCount() == block.phiPredecessorCount() + (block instanceof LoopBegin ? 0 : 1) : "valueCount=" + phi.valueCount() + " predSize= " + block.phiPredecessorCount(); } } } diff -r 5e8f82715790 -r 4afbc254f02d rundacapo.sh diff -r 5e8f82715790 -r 4afbc254f02d runfop.sh diff -r 5e8f82715790 -r 4afbc254f02d runtests.sh --- a/runtests.sh Mon Jun 20 19:46:47 2011 +0200 +++ b/runtests.sh Mon Jun 20 20:02:11 2011 +0200 @@ -12,4 +12,4 @@ exit 1; fi TESTDIR=${MAXINE}/com.oracle.max.vm/test -${JDK7}/bin/java -client -d64 -graal -ea -esa -Xcomp -XX:+PrintCompilation -XX:CompileOnly=jtt -Xbootclasspath/p:"${MAXINE}/com.oracle.max.vm/bin" -Xbootclasspath/p:"${MAXINE}/com.oracle.max.base/bin" $@ test.com.sun.max.vm.compiler.JavaTester -verbose=1 -gen-run-scheme=false -run-scheme-package=all ${TESTDIR}/jtt/bytecode ${TESTDIR}/jtt/except ${TESTDIR}/jtt/hotpath ${TESTDIR}/jtt/jdk ${TESTDIR}/jtt/lang ${TESTDIR}/jtt/loop ${TESTDIR}/jtt/micro ${TESTDIR}/jtt/optimize ${TESTDIR}/jtt/reflect ${TESTDIR}/jtt/threads +${JDK7}/bin/java -client -d64 -graal -ea -esa -Xcomp -XX:+PrintCompilation -XX:CompileOnly=jtt $@ -Xbootclasspath/p:"${MAXINE}/com.oracle.max.vm/bin" -Xbootclasspath/p:"${MAXINE}/com.oracle.max.base/bin" $@ test.com.sun.max.vm.compiler.JavaTester -verbose=1 -gen-run-scheme=false -run-scheme-package=all ${TESTDIR}/jtt/bytecode ${TESTDIR}/jtt/except ${TESTDIR}/jtt/hotpath ${TESTDIR}/jtt/jdk ${TESTDIR}/jtt/lang ${TESTDIR}/jtt/loop ${TESTDIR}/jtt/micro ${TESTDIR}/jtt/optimize ${TESTDIR}/jtt/reflect ${TESTDIR}/jtt/threads