Mercurial > hg > truffle
changeset 2936:3fa0e12d524a
merge
| author | Lukas Stadler <lukas.stadler@jku.at> |
|---|---|
| date | Fri, 10 Jun 2011 15:12:10 +0200 |
| parents | 9b8f30608e62 (current diff) e6dd12397b1d (diff) |
| children | 2823897b2da2 c7783b6773ea |
| files | graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java |
| diffstat | 8 files changed, 263 insertions(+), 36 deletions(-) [+] |
line wrap: on
line diff
--- 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)); } }
--- 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); }
--- 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);
--- 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 extends Op> T lookup(Class<T> 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; + } + } }
--- 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<Node> nodes = new ArrayList<Node>(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++; + } } } }
--- 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 <T extends Node> Iterable<T> getNodes(final Class<T> type) { return new Iterable<T>() { + @Override public Iterator<T> iterator() { return new TypedNodeIterator<T>(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<Node, Node> addDuplicate(Collection<Node> nodes, Map<Node, Node> replacements) { Map<Node, Node> newNodes = new HashMap<Node, Node>(); // create node duplicates
--- 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() + ")";
--- /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<Node> { + private final NodeBitMap visited; + private final NodeBitMap inQueue; + private final Queue<Node> 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<Node> deque = new ArrayDeque<Node>(graph.getNodeCount()); + for (Node node : graph.getNodes()) { + if (node != null) { + deque.add(node); + } + } + worklist = deque; + } else { + worklist = new ArrayDeque<Node>(); + } + 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<Node> { + private final Queue<Node> queue; + + public QueueConsumingIterator(Queue<Node> 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<Node> iterator() { + return new QueueConsumingIterator(worklist); + } + + private static class UnmarkedNodeIterator implements Iterator<Node> { + private final NodeBitMap visited; + private Iterator<Node> nodes; + private Node nextNode; + + public UnmarkedNodeIterator(NodeBitMap visited, Iterator<Node> 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<Node> unmarkedNodes() { + return new Iterable<Node>() { + @Override + public Iterator<Node> iterator() { + return new UnmarkedNodeIterator(visited, visited.graph().getNodes().iterator()); + } + }; + } +}