# HG changeset patch # User Lukas Stadler # Date 1307711530 -7200 # Node ID 3fa0e12d524af7adb054a4999259b15c86098519 # Parent 9b8f30608e62a4b90fd575bcd9fb0b50b9ce5935# Parent e6dd12397b1d7e711ce4cdc40328dde8182ad912 merge diff -r 9b8f30608e62 -r 3fa0e12d524a 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 Fri Jun 10 15:01:14 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java Fri Jun 10 15:12:10 2011 +0200 @@ -2122,7 +2122,7 @@ } if (compilation.compiler.isObserved()) { - compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, label, compilation.graph, hirValid, true)); + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, label, /*compilation.graph*/ null, hirValid, true)); } } diff -r 9b8f30608e62 -r 3fa0e12d524a graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinterObserver.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinterObserver.java Fri Jun 10 15:01:14 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinterObserver.java Fri Jun 10 15:12:10 2011 +0200 @@ -140,7 +140,7 @@ @Override public void compilationEvent(CompilationEvent event) { - if (printer != null && event.getGraph() != null) { + if (printer != null && event.getGraph() != null && event.isHIRValid()) { Graph graph = event.getGraph(); printer.print(graph, event.getLabel(), true); } diff -r 9b8f30608e62 -r 3fa0e12d524a 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 Fri Jun 10 15:01:14 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Fri Jun 10 15:12:10 2011 +0200 @@ -70,7 +70,7 @@ public void build() { new GraphBuilderPhase(compilation, compilation.method, false, false).apply(compilation.graph); printGraph("After GraphBuilding", compilation.graph); - new DuplicationPhase().apply(compilation.graph); + //new DuplicationPhase().apply(compilation.graph); new DeadCodeEliminationPhase().apply(compilation.graph); printGraph("After DeadCodeElimination", compilation.graph); diff -r 9b8f30608e62 -r 3fa0e12d524a graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Negate.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Negate.java Fri Jun 10 15:01:14 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Negate.java Fri Jun 10 15:12:10 2011 +0200 @@ -23,6 +23,7 @@ package com.oracle.max.graal.compiler.ir; import com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.compiler.phases.CanonicalizerPhase.*; import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.graph.*; import com.sun.cri.bytecode.*; @@ -32,6 +33,7 @@ * The {@code NegateOp} instruction negates its operand. */ public final class Negate extends FloatingNode { + private static final NegateCanonicalizerOp CANONICALIZER = new NegateCanonicalizerOp(); private static final int INPUT_COUNT = 2; private static final int INPUT_X = 0; @@ -103,4 +105,31 @@ Negate x = new Negate(kind, into); return x; } + + @SuppressWarnings("unchecked") + @Override + public T lookup(Class clazz) { + if (clazz == CanonicalizerOp.class) { + return (T) CANONICALIZER; + } + return super.lookup(clazz); + } + + private static class NegateCanonicalizerOp implements CanonicalizerOp { + @Override + public Node canonical(Node node) { + Negate negate = (Negate) node; + Value x = negate.x(); + Graph graph = negate.graph(); + if (x.isConstant()) { + switch (x.kind) { + case Int: return Constant.forInt(-x.asConstant().asInt(), graph); + case Long: return Constant.forLong(-x.asConstant().asLong(), graph); + case Float: return Constant.forFloat(-x.asConstant().asFloat(), graph); + case Double: return Constant.forDouble(-x.asConstant().asDouble(), graph); + } + } + return negate; + } + } } diff -r 9b8f30608e62 -r 3fa0e12d524a graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java Fri Jun 10 15:01:14 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java Fri Jun 10 15:12:10 2011 +0200 @@ -22,46 +22,30 @@ */ package com.oracle.max.graal.compiler.phases; -import java.util.*; - import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.graph.*; +/* TODO (gd) Canonicalize : + * - Compare & If + * - InstanceOf (if it's not transformed into a Condition for Compare) + * - Switches + */ public class CanonicalizerPhase extends Phase { - + private static final int MAX_ITERATION_PER_NODE = 10; @Override protected void run(Graph graph) { - NodeBitMap visited = graph.createNodeBitMap(); - List nodes = new ArrayList(graph.getNodes()); - for (Node n : nodes) { - if (n == null) { - continue; - } - if (!n.isDeleted() && !visited.isMarked(n)) { - this.canonicalize(n, visited); - } - } - } - - private void canonicalize(Node n, NodeBitMap visited) { - visited.mark(n); - for (Node input : n.inputs()) { - if (input == null) { - continue; - } - if (!visited.isNew(input) && !visited.isMarked(input)) { - canonicalize(input, visited); - } - } - - CanonicalizerOp op = n.lookup(CanonicalizerOp.class); - if (op != null) { - Node canonical = op.canonical(n); - if (canonical != n) { - n.replace(canonical); - //System.out.println("-->" + n + " canonicalized to " + canonical); - GraalMetrics.NodesCanonicalized++; + NodeWorkList nodeWorkList = graph.createNodeWorkList(true, MAX_ITERATION_PER_NODE); + for (Node node : nodeWorkList) { + CanonicalizerOp op = node.lookup(CanonicalizerOp.class); + if (op != null) { + Node canonical = op.canonical(node); + if (canonical != node) { + node.replace(canonical); + nodeWorkList.replaced(canonical, node, EdgeType.USAGES); + //System.out.println("-->" + n + " canonicalized to " + canonical); + GraalMetrics.NodesCanonicalized++; + } } } } diff -r 9b8f30608e62 -r 3fa0e12d524a graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java --- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java Fri Jun 10 15:01:14 2011 +0200 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java Fri Jun 10 15:12:10 2011 +0200 @@ -84,10 +84,12 @@ } while (nextNode == null || !type.isInstance(nextNode)); } + @Override public boolean hasNext() { return nextNode != null; } + @Override @SuppressWarnings("unchecked") public T next() { try { @@ -97,6 +99,7 @@ } } + @Override public void remove() { throw new UnsupportedOperationException(); } @@ -104,6 +107,7 @@ public Iterable getNodes(final Class type) { return new Iterable() { + @Override public Iterator iterator() { return new TypedNodeIterator(type, nodes.iterator()); } @@ -137,6 +141,14 @@ return new NodeFlood(this); } + public NodeWorkList createNodeWorkList() { + return new NodeWorkList(this); + } + + public NodeWorkList createNodeWorkList(boolean fill, int iterationLimitPerNode) { + return new NodeWorkList(this, fill, iterationLimitPerNode); + } + public Map addDuplicate(Collection nodes, Map replacements) { Map newNodes = new HashMap(); // create node duplicates diff -r 9b8f30608e62 -r 3fa0e12d524a graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeBitMap.java --- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeBitMap.java Fri Jun 10 15:01:14 2011 +0200 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeBitMap.java Fri Jun 10 15:12:10 2011 +0200 @@ -66,6 +66,10 @@ bitMap.clear(node.id()); } + public void grow(Node node) { + bitMap.grow(node.id() + 1); + } + private void check(Node node) { assert node.graph == graph : "this node is not part of the graph"; assert !isNew(node) : "this node (" + node.id() + ") was added to the graph after creating the node bitmap (" + bitMap.length() + ")"; diff -r 9b8f30608e62 -r 3fa0e12d524a graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeWorkList.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeWorkList.java Fri Jun 10 15:12:10 2011 +0200 @@ -0,0 +1,198 @@ +/* + * 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.max.graal.graph; + +import java.util.ArrayDeque; +import java.util.Iterator; +import java.util.NoSuchElementException; +import java.util.Queue; + + +public class NodeWorkList implements Iterable { + private final NodeBitMap visited; + private final NodeBitMap inQueue; + private final Queue worklist; + private int iterationLimit = Integer.MAX_VALUE; + + NodeWorkList(Graph graph) { + this(graph, false, -1); + } + + NodeWorkList(Graph graph, boolean fill, int iterationLimitPerNode) { + visited = graph.createNodeBitMap(); + inQueue = graph.createNodeBitMap(); + if (fill) { + ArrayDeque deque = new ArrayDeque(graph.getNodeCount()); + for (Node node : graph.getNodes()) { + if (node != null) { + deque.add(node); + } + } + worklist = deque; + } else { + worklist = new ArrayDeque(); + } + if (iterationLimitPerNode > 0) { + iterationLimit = iterationLimitPerNode * graph.getNodeCount(); + } + } + + public void add(Node node) { + if (node != null && !visited.isMarked(node)) { + doAdd(node); + } + } + + private void doAdd(Node node) { + if (node != null && !inQueue.isMarked(node)) { + visited.mark(node); + inQueue.mark(node); + worklist.add(node); + } + } + + public void replaced(Node newNode, Node oldNode, EdgeType... edges) { + this.replaced(newNode, oldNode, false, edges); + } + + public void replaced(Node newNode, Node oldNode, boolean add, EdgeType... edges) { + visited.grow(newNode); + worklist.remove(oldNode); + assert !worklist.contains(oldNode); + if (add) { + this.add(newNode); + } + for (EdgeType type : edges) { + switch (type) { + case INPUTS: + for (Node n : newNode.inputs()) { + doAdd(n); + } + break; + case PREDECESSORS: + for (Node n : newNode.predecessors()) { + doAdd(n); + } + break; + case USAGES: + for (Node n : newNode.usages()) { + doAdd(n); + } + break; + case SUCCESSORS: + for (Node n : newNode.successors()) { + doAdd(n); + } + break; + } + } + } + + public boolean isMarked(Node node) { + return visited.isMarked(node); + } + + private class QueueConsumingIterator implements Iterator { + private final Queue queue; + + public QueueConsumingIterator(Queue queue) { + this.queue = queue; + } + + @Override + public boolean hasNext() { + return iterationLimit > 0 && !queue.isEmpty(); + } + + @Override + public Node next() { + if (iterationLimit-- <= 0) { + throw new NoSuchElementException(); + } + Node node = queue.remove(); + inQueue.clear(node); + return node; + } + + @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()); + } + }; + } +}