# HG changeset patch # User Lukas Stadler # Date 1307467154 -7200 # Node ID 6d24c27902a27017e1e0d6bf86682a99215915d9 # Parent 5c545fef2c81685230eebbb201b39e450d5883f8 turned inlining into a phase, some node cloning fixes, added NodeWorklist diff -r 5c545fef2c81 -r 6d24c27902a2 graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java --- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java Tue Jun 07 16:33:04 2011 +0200 +++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java Tue Jun 07 19:19:14 2011 +0200 @@ -81,7 +81,7 @@ return b; } - public static boolean isCFG(Node n) { + public static boolean isFixed(Node n) { return n != null && ((n instanceof FixedNode) || n == n.graph().start()); } @@ -95,7 +95,7 @@ NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start(), null, new NodeVisitor() { @Override public boolean visit(Node n) { - if (!isCFG(n)) { + if (!isFixed(n)) { return false; } @@ -108,7 +108,7 @@ Node singlePred = null; for (Node pred : n.predecessors()) { - if (isCFG(pred)) { + if (isFixed(pred)) { if (singlePred == null) { singlePred = pred; } else { @@ -141,7 +141,7 @@ for (Node n : blockBeginNodes) { Block block = nodeToBlock.get(n); for (Node pred : n.predecessors()) { - if (isCFG(pred)) { + if (isFixed(pred)) { Block predBlock = nodeToBlock.get(pred); predBlock.addSuccessor(block); } @@ -229,7 +229,7 @@ } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) { Merge merge = ((FrameState) usage).block(); for (Node pred : merge.predecessors()) { - if (isCFG(pred)) { + if (isFixed(pred)) { block = getCommonDominator(block, nodeToBlock.get(pred)); } } @@ -437,7 +437,7 @@ } int i = 0; for (Node s : n.successors()) { - if (isCFG(s)) { + if (isFixed(s)) { i++; } } @@ -450,7 +450,7 @@ } int i = 0; for (Node s : n.predecessors()) { - if (isCFG(s)) { + if (isFixed(s)) { i++; } } diff -r 5c545fef2c81 -r 6d24c27902a2 graal/GraalCompiler/src/com/sun/c1x/C1XOptions.java --- a/graal/GraalCompiler/src/com/sun/c1x/C1XOptions.java Tue Jun 07 16:33:04 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/C1XOptions.java Tue Jun 07 19:19:14 2011 +0200 @@ -45,7 +45,7 @@ public static int MaximumInlineSize = 35; public static int MaximumTrivialSize = 6; public static int MaximumInlineLevel = 9; - public static int MaximumRecursiveInlineLevel = 1; + public static int MaximumRecursiveInlineLevel = 2; public static int MaximumDesiredSize = 8000; public static int MaximumShortLoopSize = 5; diff -r 5c545fef2c81 -r 6d24c27902a2 graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java --- a/graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java Tue Jun 07 16:33:04 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java Tue Jun 07 19:19:14 2011 +0200 @@ -1377,7 +1377,7 @@ } private CiValue operandForPhi(Phi phi) { - assert !phi.isDead(); + assert !phi.isDead() : "dead phi: " + phi.id(); if (phi.operand().isIllegal()) { // allocate a variable for this phi CiVariable operand = newVariable(phi.kind); diff -r 5c545fef2c81 -r 6d24c27902a2 graal/GraalCompiler/src/com/sun/c1x/graph/DeadCodeElimination.java --- a/graal/GraalCompiler/src/com/sun/c1x/graph/DeadCodeElimination.java Tue Jun 07 16:33:04 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/graph/DeadCodeElimination.java Tue Jun 07 19:19:14 2011 +0200 @@ -22,10 +22,7 @@ */ package com.sun.c1x.graph; -import java.util.*; - import com.oracle.graal.graph.*; -import com.oracle.max.graal.schedule.*; import com.sun.c1x.*; import com.sun.c1x.gen.*; import com.sun.c1x.ir.*; @@ -34,7 +31,7 @@ public class DeadCodeElimination extends Phase { private NodeBitMap alive; - private Queue worklist; + private NodeWorklist worklist; private Graph graph; public int deletedNodeCount; @@ -43,9 +40,9 @@ protected void run(Graph graph) { this.graph = graph; this.alive = graph.createNodeBitMap(); - this.worklist = new ArrayDeque(); + this.worklist = graph.createNodeWorklist(); - addToWorklist(graph.start()); + worklist.add(graph.start()); iterateSuccessors(); disconnectCFGNodes(); @@ -63,22 +60,25 @@ } } + private static boolean isCFG(Node n) { + return n != null && ((n instanceof Instruction) || n == n.graph().start()); + } + private void iterateSuccessors() { - Node current; - while ((current = nextNode()) != null) { + for (Node current : worklist) { for (Node successor : current.successors()) { - addToWorklist(successor); + worklist.add(successor); } } } private void disconnectCFGNodes() { for (Node node : graph.getNodes()) { - if (node != Node.Null && !alive.isMarked(node) && Schedule.isCFG(node)) { + if (node != Node.Null && !worklist.isMarked(node) && isCFG(node)) { // iterate backwards so that the predecessor indexes in removePhiPredecessor are correct for (int i = node.successors().size() - 1; i >= 0; i--) { Node successor = node.successors().get(i); - if (successor != Node.Null && alive.isMarked(successor)) { + if (successor != Node.Null && worklist.isMarked(successor)) { if (successor instanceof Merge) { ((Merge) successor).removePhiPredecessor(node); } @@ -92,7 +92,7 @@ private void deleteCFGNodes() { for (Node node : graph.getNodes()) { - if (node != Node.Null && !alive.isMarked(node) && Schedule.isCFG(node)) { + if (node != Node.Null && !worklist.isMarked(node) && isCFG(node)) { node.delete(); deletedNodeCount++; } @@ -101,23 +101,22 @@ private void iterateInputs() { for (Node node : graph.getNodes()) { - if (node != Node.Null && alive.isMarked(node)) { + if (node != Node.Null && worklist.isMarked(node)) { for (Node input : node.inputs()) { - addToWorklist(input); + worklist.add(input); } } } - Node current; - while ((current = nextNode()) != null) { + for (Node current : worklist) { for (Node input : current.inputs()) { - addToWorklist(input); + worklist.add(input); } } } private void disconnectNonCFGNodes() { for (Node node : graph.getNodes()) { - if (node != Node.Null && !alive.isMarked(node) && !Schedule.isCFG(node)) { + if (node != Node.Null && !worklist.isMarked(node) && !isCFG(node)) { node.inputs().clearAll(); } } @@ -125,21 +124,10 @@ private void deleteNonCFGNodes() { for (Node node : graph.getNodes()) { - if (node != Node.Null && !alive.isMarked(node) && !Schedule.isCFG(node)) { + if (node != Node.Null && !worklist.isMarked(node) && !isCFG(node)) { node.delete(); deletedNodeCount++; } } } - - private Node nextNode() { - return worklist.poll(); - } - - private void addToWorklist(Node node) { - if (node != null && !alive.isMarked(node)) { - alive.mark(node); - worklist.add(node); - } - } } diff -r 5c545fef2c81 -r 6d24c27902a2 graal/GraalCompiler/src/com/sun/c1x/graph/IR.java --- a/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java Tue Jun 07 16:33:04 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java Tue Jun 07 19:19:14 2011 +0200 @@ -29,7 +29,6 @@ import com.oracle.max.graal.schedule.*; import com.sun.c1x.*; import com.sun.c1x.debug.*; -import com.sun.c1x.gen.*; import com.sun.c1x.ir.*; import com.sun.c1x.lir.*; import com.sun.c1x.observer.*; @@ -157,6 +156,12 @@ // Graph builder must set the startBlock and the osrEntryBlock new GraphBuilder(compilation, compilation.method, compilation.graph).build(false); +// CompilerGraph duplicate = new CompilerGraph(); +// Map replacements = new HashMap(); +// replacements.put(compilation.graph.start(), duplicate.start()); +// duplicate.addDuplicate(compilation.graph.getNodes(), replacements); +// compilation.graph = duplicate; + verifyAndPrint("After graph building"); DeadCodeElimination dce = new DeadCodeElimination(); @@ -166,7 +171,7 @@ } if (C1XOptions.Inline) { - inlineMethods(); + new Inlining(compilation, this).apply(compilation.graph); } if (C1XOptions.PrintCompilation) { @@ -174,241 +179,6 @@ } } - private void inlineMethods() { - int inliningSize = compilation.method.code().length; - boolean inlined; - int iterations = C1XOptions.MaximumRecursiveInlineLevel; - do { - inlined = false; - - List trivialInline = new ArrayList(); - List deoptInline = new ArrayList(); - List deoptMethods = new ArrayList(); - for (Node node : compilation.graph.getNodes()) { - if (node instanceof Invoke) { - Invoke invoke = (Invoke) node; - RiMethod target = invoke.target; - if (target.isResolved() && !Modifier.isNative(target.accessFlags())) { - if (target.canBeStaticallyBound()) { - trivialInline.add(invoke); - } else { - RiMethod concrete = invoke.target.holder().uniqueConcreteMethod(invoke.target); - if (concrete != null && concrete.isResolved() && !Modifier.isNative(concrete.accessFlags())) { - deoptInline.add(invoke); - deoptMethods.add(concrete); - } - } - } - } - } - - for (Invoke invoke : trivialInline) { - if (inlineMethod(invoke, invoke.target)) { - inlined = true; - inliningSize += invoke.target.code().length; - if (inliningSize > C1XOptions.MaximumInstructionCount) { - break; - } - } - } - - for (int i = 0; i < deoptInline.size(); i++) { - Invoke invoke = deoptInline.get(i); - RiMethod method = deoptMethods.get(i); - if (inlineMethod(invoke, method)) { - if (C1XOptions.TraceInlining) { - System.out.println("registering concrete method assumption..."); - } - compilation.assumptions.recordConcreteMethod(invoke.target, method); - inlined = true; - inliningSize += method.code().length; - if (inliningSize > C1XOptions.MaximumInstructionCount) { - break; - } - } - } - - if (inlined) { - DeadCodeElimination dce = new DeadCodeElimination(); - dce.apply(compilation.graph); - if (dce.deletedNodeCount > 0) { - verifyAndPrint("After dead code elimination"); - } - verifyAndPrint("After inlining iteration"); - } - - if (inliningSize > C1XOptions.MaximumInstructionCount) { - break; - } - } while(inlined && (--iterations > 0)); - } - - private boolean inlineMethod(Invoke invoke, RiMethod method) { - String name = invoke.id() + ": " + CiUtil.format("%H.%n(%p):%r", method, false) + " (" + method.code().length + " bytes)"; - FrameState stateAfter = invoke.stateAfter(); - - if (method.code().length > C1XOptions.MaximumInlineSize) { - if (C1XOptions.TraceInlining) { - System.out.println("not inlining " + name + " because of code size"); - } - return false; - } - - if (invoke.predecessors().size() == 0) { - if (C1XOptions.TraceInlining) { - System.out.println("not inlining " + name + " because the invoke is dead code"); - } - return false; - } - - Instruction exceptionEdge = invoke.exceptionEdge(); -// if (exceptionEdge != null) { -// if (C1XOptions.TraceInlining) { -// System.out.println("not inlining " + name + " because of exceptionEdge"); -// } -// return false; -// } - if (!method.holder().isInitialized()) { - if (C1XOptions.TraceInlining) { - System.out.println("not inlining " + name + " because of non-initialized class"); - } - return false; - } - - if (C1XOptions.TraceInlining) { - System.out.printf("Building graph for %s, locals: %d, stack: %d\n", name, method.maxLocals(), method.maxStackSize()); - } - - CompilerGraph graph = new CompilerGraph(); - new GraphBuilder(compilation, method, graph).build(true); - - boolean withReceiver = !Modifier.isStatic(method.accessFlags()); - - int argumentCount = method.signature().argumentCount(false); - Value[] parameters = new Value[argumentCount + (withReceiver ? 1 : 0)]; - int slot = withReceiver ? 1 : 0; - int param = withReceiver ? 1 : 0; - for (int i = 0; i < argumentCount; i++) { - parameters[param++] = invoke.argument(slot); - slot += method.signature().argumentKindAt(i).sizeInSlots(); - } - if (withReceiver) { - parameters[0] = invoke.argument(0); - } - - HashMap replacements = new HashMap(); - ArrayList nodes = new ArrayList(); - ArrayList frameStates = new ArrayList(); - Return returnNode = null; - Unwind unwindNode = null; - StartNode startNode = graph.start(); - for (Node node : graph.getNodes()) { - if (node != null) { - if (node instanceof StartNode) { - assert startNode == node; - } else if (node instanceof Local) { - replacements.put(node, parameters[((Local) node).index()]); - } else { - nodes.add(node); - if (node instanceof Return) { - returnNode = (Return) node; - } else if (node instanceof Unwind) { - unwindNode = (Unwind) node; - } else if (node instanceof FrameState) { - frameStates.add(node); - } - } - } - } - - if (C1XOptions.TraceInlining) { - printGraph("Subgraph " + CiUtil.format("%H.%n(%p):%r", method, false), graph); - System.out.println("inlining " + name + ": " + frameStates.size() + " frame states, " + nodes.size() + " nodes"); - } - - assert invoke.predecessors().size() == 1 : "size: " + invoke.predecessors().size(); - Instruction pred; - if (withReceiver) { - pred = new NullCheck(parameters[0], compilation.graph); - } else { - pred = new Merge(compilation.graph); - } - invoke.predecessors().get(0).successors().replace(invoke, pred); - replacements.put(startNode, pred); - - Map duplicates = compilation.graph.addDuplicate(nodes, replacements); - - if (returnNode != null) { - List usages = new ArrayList(invoke.usages()); - for (Node usage : usages) { - if (returnNode.result() instanceof Local) { - usage.inputs().replace(invoke, replacements.get(returnNode.result())); - } else { - usage.inputs().replace(invoke, duplicates.get(returnNode.result())); - } - } - Node returnDuplicate = duplicates.get(returnNode); - returnDuplicate.inputs().clearAll(); - - assert returnDuplicate.predecessors().size() == 1; - Node returnPred = returnDuplicate.predecessors().get(0); - int index = returnDuplicate.predecessorsIndex().get(0); - returnPred.successors().setAndClear(index, invoke, 0); - returnDuplicate.delete(); - } - -// if (invoke.next() instanceof Merge) { -// ((Merge) invoke.next()).removePhiPredecessor(invoke); -// } -// invoke.successors().clearAll(); - invoke.inputs().clearAll(); - invoke.setExceptionEdge(null); -// invoke.delete(); - - - if (exceptionEdge != null) { - if (unwindNode != null) { - assert unwindNode.predecessors().size() == 1; - assert exceptionEdge.successors().size() == 1; - ExceptionObject obj = (ExceptionObject) exceptionEdge; - - List usages = new ArrayList(obj.usages()); - for (Node usage : usages) { - if (replacements.containsKey(unwindNode.exception())) { - usage.inputs().replace(obj, replacements.get(unwindNode.exception())); - } else { - usage.inputs().replace(obj, duplicates.get(unwindNode.exception())); - } - } - Node unwindDuplicate = duplicates.get(unwindNode); - unwindDuplicate.inputs().clearAll(); - - assert unwindDuplicate.predecessors().size() == 1; - Node unwindPred = unwindDuplicate.predecessors().get(0); - int index = unwindDuplicate.predecessorsIndex().get(0); - unwindPred.successors().setAndClear(index, obj, 0); - - obj.inputs().clearAll(); - obj.delete(); - unwindDuplicate.delete(); - - } - } - - // adjust all frame states that were copied - if (frameStates.size() > 0) { - FrameState outerFrameState = stateAfter.duplicateModified(invoke.bci, invoke.kind); - for (Node frameState : frameStates) { - ((FrameState) duplicates.get(frameState)).setOuterFrameState(outerFrameState); - } - } - - if (C1XOptions.TraceInlining) { - verifyAndPrint("After inlining " + CiUtil.format("%H.%n(%p):%r", method, false)); - } - return true; - } - /** * Gets the linear scan ordering of blocks as a list. * @return the blocks in linear scan order diff -r 5c545fef2c81 -r 6d24c27902a2 graal/GraalCompiler/src/com/sun/c1x/graph/Inlining.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/GraalCompiler/src/com/sun/c1x/graph/Inlining.java Tue Jun 07 19:19:14 2011 +0200 @@ -0,0 +1,288 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.sun.c1x.graph; + +import java.lang.reflect.*; +import java.util.*; + +import com.oracle.graal.graph.*; +import com.sun.c1x.*; +import com.sun.c1x.ir.*; +import com.sun.c1x.value.*; +import com.sun.cri.ci.*; +import com.sun.cri.ri.*; + + +public class Inlining extends Phase { + + private final C1XCompilation compilation; + private final IR ir; + + private final Queue invokes = new ArrayDeque(); + private final Queue methods = new ArrayDeque(); + private int inliningSize; + + public Inlining(C1XCompilation compilation, IR ir) { + this.compilation = compilation; + this.ir = ir; + } + + private void addToQueue(Invoke invoke, RiMethod method) { + invokes.add(invoke); + methods.add(method); + inliningSize += method.code().length; + } + + @Override + protected void run(Graph graph) { + if (!C1XOptions.Inline) { + return; + } + + inliningSize = compilation.method.code().length; + int iterations = C1XOptions.MaximumRecursiveInlineLevel; + do { + for (Node node : graph.getNodes()) { + if (node instanceof Invoke) { + Invoke invoke = (Invoke) node; + RiMethod target = invoke.target; + if (!checkInliningConditions(invoke) || !target.isResolved() || Modifier.isNative(target.accessFlags())) { + continue; + } + if (target.canBeStaticallyBound()) { + if (checkInliningConditions(invoke.target)) { + addToQueue(invoke, invoke.target); + } + } else { + RiMethod concrete = invoke.target.holder().uniqueConcreteMethod(invoke.target); + if (concrete != null && concrete.isResolved() && !Modifier.isNative(concrete.accessFlags())) { + if (checkInliningConditions(concrete)) { + if (C1XOptions.TraceInlining) { + System.out.println("registering concrete method assumption..."); + } + compilation.assumptions.recordConcreteMethod(invoke.target, concrete); + addToQueue(invoke, concrete); + } + } + } + if (inliningSize > C1XOptions.MaximumInstructionCount) { + break; + } + } + } + + assert invokes.size() == methods.size(); + if (invokes.isEmpty()) { + break; + } + + Invoke invoke; + while ((invoke = invokes.poll()) != null) { + RiMethod method = methods.remove(); + inlineMethod(invoke, method); + } + DeadCodeElimination dce = new DeadCodeElimination(); + dce.apply(graph); + if (dce.deletedNodeCount > 0) { + ir.verifyAndPrint("After dead code elimination"); + } + ir.verifyAndPrint("After inlining iteration"); + + if (inliningSize > C1XOptions.MaximumInstructionCount) { + if (C1XOptions.TraceInlining) { + System.out.println("inlining stopped: MaximumInstructionCount reached"); + } + break; + } + } while(--iterations > 0); + } + + private boolean checkInliningConditions(Invoke invoke) { + String name = invoke.id() + ": " + CiUtil.format("%H.%n(%p):%r", invoke.target, false); + if (invoke.predecessors().size() == 0) { + if (C1XOptions.TraceInlining) { + System.out.println("not inlining " + name + " because the invoke is dead code"); + } + return false; + } + return true; + } + + private boolean checkInliningConditions(RiMethod method) { + String name = null; + if (C1XOptions.TraceInlining) { + name = CiUtil.format("%H.%n(%p):%r", method, false) + " (" + method.code().length + " bytes)"; + } + if (method.code().length > C1XOptions.MaximumInlineSize) { + if (C1XOptions.TraceInlining) { + System.out.println("not inlining " + name + " because of code size"); + } + return false; + } + if (!method.holder().isInitialized()) { + if (C1XOptions.TraceInlining) { + System.out.println("not inlining " + name + " because of non-initialized class"); + } + return false; + } + return true; + } + + private void inlineMethod(Invoke invoke, RiMethod method) { + String name = invoke.id() + ": " + CiUtil.format("%H.%n(%p):%r", method, false) + " (" + method.code().length + " bytes)"; + FrameState stateAfter = invoke.stateAfter(); + Instruction exceptionEdge = invoke.exceptionEdge(); + + if (C1XOptions.TraceInlining) { + System.out.printf("Building graph for %s, locals: %d, stack: %d\n", name, method.maxLocals(), method.maxStackSize()); + } + + CompilerGraph graph = new CompilerGraph(); + new GraphBuilder(compilation, method, graph).build(true); + + boolean withReceiver = !Modifier.isStatic(method.accessFlags()); + + int argumentCount = method.signature().argumentCount(false); + Value[] parameters = new Value[argumentCount + (withReceiver ? 1 : 0)]; + int slot = withReceiver ? 1 : 0; + int param = withReceiver ? 1 : 0; + for (int i = 0; i < argumentCount; i++) { + parameters[param++] = invoke.argument(slot); + slot += method.signature().argumentKindAt(i).sizeInSlots(); + } + if (withReceiver) { + parameters[0] = invoke.argument(0); + } + + HashMap replacements = new HashMap(); + ArrayList nodes = new ArrayList(); + ArrayList frameStates = new ArrayList(); + Return returnNode = null; + Unwind unwindNode = null; + StartNode startNode = graph.start(); + for (Node node : graph.getNodes()) { + if (node != null) { + if (node instanceof StartNode) { + assert startNode == node; + } else if (node instanceof Local) { + replacements.put(node, parameters[((Local) node).index()]); + } else { + nodes.add(node); + if (node instanceof Return) { + returnNode = (Return) node; + } else if (node instanceof Unwind) { + unwindNode = (Unwind) node; + } else if (node instanceof FrameState) { + frameStates.add(node); + } + } + } + } + + if (C1XOptions.TraceInlining) { + ir.printGraph("Subgraph " + CiUtil.format("%H.%n(%p):%r", method, false), graph); + System.out.println("inlining " + name + ": " + frameStates.size() + " frame states, " + nodes.size() + " nodes"); + } + + assert invoke.predecessors().size() == 1 : "size: " + invoke.predecessors().size(); + Instruction pred; + if (withReceiver) { + pred = new NullCheck(parameters[0], compilation.graph); + } else { + pred = new Merge(compilation.graph); + } + invoke.predecessors().get(0).successors().replace(invoke, pred); + replacements.put(startNode, pred); + + Map duplicates = compilation.graph.addDuplicate(nodes, replacements); + + if (returnNode != null) { + List usages = new ArrayList(invoke.usages()); + for (Node usage : usages) { + if (returnNode.result() instanceof Local) { + usage.inputs().replace(invoke, replacements.get(returnNode.result())); + } else { + usage.inputs().replace(invoke, duplicates.get(returnNode.result())); + } + } + Node returnDuplicate = duplicates.get(returnNode); + returnDuplicate.inputs().clearAll(); + + assert returnDuplicate.predecessors().size() == 1; + Node returnPred = returnDuplicate.predecessors().get(0); + int index = returnDuplicate.predecessorsIndex().get(0); + returnPred.successors().setAndClear(index, invoke, 0); + returnDuplicate.delete(); + } + +// if (invoke.next() instanceof Merge) { +// ((Merge) invoke.next()).removePhiPredecessor(invoke); +// } +// invoke.successors().clearAll(); + invoke.inputs().clearAll(); + invoke.setExceptionEdge(null); +// invoke.delete(); + + + if (exceptionEdge != null) { + if (unwindNode != null) { + assert unwindNode.predecessors().size() == 1; + assert exceptionEdge.successors().size() == 1; + ExceptionObject obj = (ExceptionObject) exceptionEdge; + + List usages = new ArrayList(obj.usages()); + for (Node usage : usages) { + if (replacements.containsKey(unwindNode.exception())) { + usage.inputs().replace(obj, replacements.get(unwindNode.exception())); + } else { + usage.inputs().replace(obj, duplicates.get(unwindNode.exception())); + } + } + Node unwindDuplicate = duplicates.get(unwindNode); + unwindDuplicate.inputs().clearAll(); + + assert unwindDuplicate.predecessors().size() == 1; + Node unwindPred = unwindDuplicate.predecessors().get(0); + int index = unwindDuplicate.predecessorsIndex().get(0); + unwindPred.successors().setAndClear(index, obj, 0); + + obj.inputs().clearAll(); + obj.delete(); + unwindDuplicate.delete(); + + } + } + + // adjust all frame states that were copied + if (frameStates.size() > 0) { + FrameState outerFrameState = stateAfter.duplicateModified(invoke.bci, invoke.kind); + for (Node frameState : frameStates) { + ((FrameState) duplicates.get(frameState)).setOuterFrameState(outerFrameState); + } + } + + if (C1XOptions.TraceInlining) { + ir.verifyAndPrint("After inlining " + CiUtil.format("%H.%n(%p):%r", method, false)); + } + } +} diff -r 5c545fef2c81 -r 6d24c27902a2 graal/GraalCompiler/src/com/sun/c1x/ir/And.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/And.java Tue Jun 07 16:33:04 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/And.java Tue Jun 07 19:19:14 2011 +0200 @@ -47,7 +47,7 @@ @Override public Node copy(Graph into) { - And x = new And(kind, null, null, graph()); + And x = new And(kind, null, null, into); return x; } diff -r 5c545fef2c81 -r 6d24c27902a2 graal/GraalCompiler/src/com/sun/c1x/ir/Or.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/Or.java Tue Jun 07 16:33:04 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Or.java Tue Jun 07 19:19:14 2011 +0200 @@ -50,7 +50,7 @@ @Override public Node copy(Graph into) { - Or x = new Or(kind, null, null, graph()); + Or x = new Or(kind, null, null, into); return x; } diff -r 5c545fef2c81 -r 6d24c27902a2 graal/GraalCompiler/src/com/sun/c1x/ir/Xor.java --- a/graal/GraalCompiler/src/com/sun/c1x/ir/Xor.java Tue Jun 07 16:33:04 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Xor.java Tue Jun 07 19:19:14 2011 +0200 @@ -46,7 +46,7 @@ @Override public Node copy(Graph into) { - Xor x = new Xor(kind, null, null, graph()); + Xor x = new Xor(kind, null, null, into); return x; } diff -r 5c545fef2c81 -r 6d24c27902a2 graal/GraalGraph/src/com/oracle/graal/graph/Graph.java --- a/graal/GraalGraph/src/com/oracle/graal/graph/Graph.java Tue Jun 07 16:33:04 2011 +0200 +++ b/graal/GraalGraph/src/com/oracle/graal/graph/Graph.java Tue Jun 07 19:19:14 2011 +0200 @@ -36,6 +36,14 @@ private final StartNode start; int nextId; + static int nextGraphId = 0; + int id = nextGraphId++; + + @Override + public String toString() { + return "Graph " + id; + } + public Graph() { nodes = new ArrayList(); start = new StartNode(this); @@ -67,6 +75,10 @@ return new NodeMap(this); } + public NodeWorklist createNodeWorklist() { + return new NodeWorklist(this); + } + public Map addDuplicate(Collection nodes, Map replacements) { Map newNodes = new HashMap(); // create node duplicates diff -r 5c545fef2c81 -r 6d24c27902a2 graal/GraalGraph/src/com/oracle/graal/graph/NodeArray.java --- a/graal/GraalGraph/src/com/oracle/graal/graph/NodeArray.java Tue Jun 07 16:33:04 2011 +0200 +++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeArray.java Tue Jun 07 19:19:14 2011 +0200 @@ -47,7 +47,7 @@ @Override public Node set(int index, Node node) { - assert node == Node.Null || node.graph == self().graph : "node is from different graph"; + assert node == Node.Null || node.graph == self().graph : "node is from different graph (" + node.graph + " instead of " + self().graph + ")"; assert node == Node.Null || node.id() != Node.DeletedID : "inserted node must not be deleted"; Node old = nodes[index]; diff -r 5c545fef2c81 -r 6d24c27902a2 graal/GraalGraph/src/com/oracle/graal/graph/NodeBitMap.java --- a/graal/GraalGraph/src/com/oracle/graal/graph/NodeBitMap.java Tue Jun 07 16:33:04 2011 +0200 +++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeBitMap.java Tue Jun 07 19:19:14 2011 +0200 @@ -35,6 +35,10 @@ bitMap = new CiBitMap(graph.nextId); } + public Graph graph() { + return graph; + } + public boolean setIntersect(NodeBitMap other) { return bitMap.setIntersect(other.bitMap); } diff -r 5c545fef2c81 -r 6d24c27902a2 graal/GraalGraph/src/com/oracle/graal/graph/NodeWorklist.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeWorklist.java Tue Jun 07 19:19:14 2011 +0200 @@ -0,0 +1,128 @@ +/* + * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.graph; + +import java.util.ArrayDeque; +import java.util.Iterator; +import java.util.Queue; + + +public class NodeWorklist implements Iterable { + private final NodeBitMap visited; + private final Queue worklist; + + NodeWorklist(Graph graph) { + visited = graph.createNodeBitMap(); + worklist = new ArrayDeque(); + } + + public void add(Node node) { + if (node != null && !visited.isMarked(node)) { + visited.mark(node); + worklist.add(node); + } + } + + public boolean isMarked(Node node) { + return visited.isMarked(node); + } + + private static class QueueConsumingIterator implements Iterator { + private final Queue queue; + + public QueueConsumingIterator(Queue queue) { + this.queue = queue; + } + + @Override + public boolean hasNext() { + return !queue.isEmpty(); + } + + @Override + public Node next() { + return queue.remove(); + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + } + + @Override + public Iterator iterator() { + return new QueueConsumingIterator(worklist); + } + + private static class UnmarkedNodeIterator implements Iterator { + private final NodeBitMap visited; + private Iterator nodes; + private Node nextNode; + + public UnmarkedNodeIterator(NodeBitMap visited, Iterator nodes) { + this.visited = visited; + this.nodes = nodes; + forward(); + } + + private void forward() { + do { + if (!nodes.hasNext()) { + nextNode = null; + return; + } + nextNode = nodes.next(); + } while (visited.isMarked(nextNode)); + } + + @Override + public boolean hasNext() { + return nextNode != null; + } + + @Override + public Node next() { + try { + return nextNode; + } finally { + forward(); + } + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + + } + + public Iterable unmarkedNodes() { + return new Iterable() { + @Override + public Iterator iterator() { + return new UnmarkedNodeIterator(visited, visited.graph().getNodes().iterator()); + } + }; + } +} diff -r 5c545fef2c81 -r 6d24c27902a2 graal/GraalGraph/src/com/oracle/graal/graph/Op.java --- a/graal/GraalGraph/src/com/oracle/graal/graph/Op.java Tue Jun 07 16:33:04 2011 +0200 +++ b/graal/GraalGraph/src/com/oracle/graal/graph/Op.java Tue Jun 07 19:19:14 2011 +0200 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it