Mercurial > hg > truffle

changeset 2910:7eec76f3e39e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
adjust monitor index while inlining, renamed NodeWorklist to NodeFlood
author Lukas Stadler <lukas.stadler@jku.at>
date Wed, 08 Jun 2011 14:30:27 +0200
parents 693e4e92346b
children 241798fa9d34
files graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MonitorAddress.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeFlood.java graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeWorklist.java
diffstat 8 files changed, 270 insertions(+), 175 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java	Wed Jun 08 14:30:27 2011 +0200
@@ -532,7 +532,7 @@
     @Override
     public void visitMonitorAddress(MonitorAddress x) {
         CiValue result = createResultVariable(x);
-        lir.monitorAddress(x.monitor(), result);
+        lir.monitorAddress(x.monitorIndex(), result);
     }
 
     /**
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java	Wed Jun 08 14:30:27 2011 +0200
@@ -202,7 +202,12 @@
         int maxLocks = 0;
         for (Node node : compilation.graph.getNodes()) {
             if (node instanceof FrameState) {
-                int lockCount = ((FrameState) node).locksSize();
+                FrameState current = (FrameState) node;
+                int lockCount = 0;
+                while (current != null) {
+                    lockCount += current.locksSize();
+                    current = current.outerFrameState();
+                }
                 if (lockCount > maxLocks) {
                     maxLocks = lockCount;
                 }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MonitorAddress.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MonitorAddress.java	Wed Jun 08 14:30:27 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.graph.*;
 import com.sun.cri.ci.*;
@@ -34,11 +36,11 @@
     private static final int INPUT_COUNT = 0;
     private static final int SUCCESSOR_COUNT = 0;
 
-    private int monitor;
+    private int monitorIndex;
 
-    public MonitorAddress(int monitor, Graph graph) {
+    public MonitorAddress(int monitorIndex, Graph graph) {
         super(CiKind.Word, INPUT_COUNT, SUCCESSOR_COUNT, graph);
-        this.monitor = monitor;
+        this.monitorIndex = monitorIndex;
     }
 
     @Override
@@ -46,18 +48,31 @@
         v.visitMonitorAddress(this);
     }
 
-    public int monitor() {
-        return monitor;
+    public int monitorIndex() {
+        return monitorIndex;
+    }
+
+    public void setMonitorIndex(int monitorIndex) {
+        this.monitorIndex = monitorIndex;
     }
 
     @Override
     public void print(LogStream out) {
-        out.print("monitor_address (").print(monitor()).print(")");
+        out.print("monitor_address (").print(monitorIndex()).print(")");
+    }
+
+
+
+    @Override
+    public Map<Object, Object> getDebugProperties() {
+        Map<Object, Object> properties = super.getDebugProperties();
+        properties.put("monitorIndex", monitorIndex);
+        return properties;
     }
 
     @Override
     public Node copy(Graph into) {
-        MonitorAddress x = new MonitorAddress(monitor, into);
+        MonitorAddress x = new MonitorAddress(monitorIndex, into);
         return x;
     }
 }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java	Wed Jun 08 14:30:27 2011 +0200
@@ -31,7 +31,7 @@
 public class DeadCodeEliminationPhase extends Phase {
 
     private NodeBitMap alive;
-    private NodeWorklist worklist;
+    private NodeFlood flood;
     private Graph graph;
 
     public int deletedNodeCount;
@@ -40,9 +40,9 @@
     protected void run(Graph graph) {
         this.graph = graph;
         this.alive = graph.createNodeBitMap();
-        this.worklist = graph.createNodeWorklist();
+        this.flood = graph.createNodeFlood();
 
-        worklist.add(graph.start());
+        flood.add(graph.start());
 
         iterateSuccessors();
         disconnectCFGNodes();
@@ -65,20 +65,20 @@
     }
 
     private void iterateSuccessors() {
-        for (Node current : worklist) {
+        for (Node current : flood) {
             for (Node successor : current.successors()) {
-                worklist.add(successor);
+                flood.add(successor);
             }
         }
     }
 
     private void disconnectCFGNodes() {
         for (Node node : graph.getNodes()) {
-            if (node != Node.Null && !worklist.isMarked(node) && isCFG(node)) {
+            if (node != Node.Null && !flood.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 && worklist.isMarked(successor)) {
+                    if (successor != Node.Null && flood.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 && !worklist.isMarked(node) && isCFG(node)) {
+            if (node != Node.Null && !flood.isMarked(node) && isCFG(node)) {
                 node.delete();
                 deletedNodeCount++;
             }
@@ -101,22 +101,22 @@
 
     private void iterateInputs() {
         for (Node node : graph.getNodes()) {
-            if (node != Node.Null && worklist.isMarked(node)) {
+            if (node != Node.Null && flood.isMarked(node)) {
                 for (Node input : node.inputs()) {
-                    worklist.add(input);
+                    flood.add(input);
                 }
             }
         }
-        for (Node current : worklist) {
+        for (Node current : flood) {
             for (Node input : current.inputs()) {
-                worklist.add(input);
+                flood.add(input);
             }
         }
     }
 
     private void disconnectNonCFGNodes() {
         for (Node node : graph.getNodes()) {
-            if (node != Node.Null && !worklist.isMarked(node) && !isCFG(node)) {
+            if (node != Node.Null && !flood.isMarked(node) && !isCFG(node)) {
                 node.inputs().clearAll();
             }
         }
@@ -124,7 +124,7 @@
 
     private void deleteNonCFGNodes() {
         for (Node node : graph.getNodes()) {
-            if (node != Node.Null && !worklist.isMarked(node) && !isCFG(node)) {
+            if (node != Node.Null && !flood.isMarked(node) && !isCFG(node)) {
                 node.delete();
                 deletedNodeCount++;
             }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java	Wed Jun 08 14:30:27 2011 +0200
@@ -54,37 +54,37 @@
         inliningSize += method.code().length;
     }
 
+    static HashMap<RiMethod, Integer> methodCount = new HashMap<RiMethod, Integer>();
     @Override
     protected void run(Graph graph) {
         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;
+            for (Invoke invoke : graph.getNodes(Invoke.class)) {
+                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);
                     }
-                    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);
+                } 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;
-                    }
+                }
+                if (inliningSize > C1XOptions.MaximumInstructionCount) {
+                    break;
                 }
             }
 
@@ -97,6 +97,12 @@
             while ((invoke = invokes.poll()) != null) {
                 RiMethod method = methods.remove();
                 inlineMethod(invoke, method);
+
+                if (methodCount.get(method) == null) {
+                    methodCount.put(method, 1);
+                } else {
+                    methodCount.put(method, methodCount.get(method) + 1);
+                }
             }
             DeadCodeEliminationPhase dce = new DeadCodeEliminationPhase();
             dce.apply(graph);
@@ -112,6 +118,16 @@
                 break;
             }
         } while(--iterations > 0);
+
+        int inlined = 0;
+        int duplicate = 0;
+        for (Map.Entry<RiMethod, Integer> entry : methodCount.entrySet()) {
+            inlined += entry.getValue();
+            duplicate += entry.getValue() - 1;
+        }
+        if (inlined > 0) {
+            System.out.printf("overhead_: %d (%5.3f %%)\n", duplicate, duplicate * 100.0 / inlined);
+        }
     }
 
     private boolean checkInliningConditions(Invoke invoke) {
@@ -213,6 +229,17 @@
 
         Map<Node, Node> duplicates = compilation.graph.addDuplicate(nodes, replacements);
 
+        int monitorIndexDelta = stateAfter.locksSize();
+        if (monitorIndexDelta > 0) {
+            System.out.println("Adjusting locks");
+            for (Map.Entry<Node, Node> entry : duplicates.entrySet()) {
+                if (entry.getValue() instanceof MonitorAddress) {
+                    MonitorAddress address = (MonitorAddress) entry.getValue();
+                    address.setMonitorIndex(address.monitorIndex() + monitorIndexDelta);
+                }
+            }
+        }
+
         if (returnNode != null) {
             List<Node> usages = new ArrayList<Node>(invoke.usages());
             for (Node usage : usages) {
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java	Wed Jun 08 14:30:27 2011 +0200
@@ -26,6 +26,7 @@
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
+import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.Map.Entry;
@@ -53,6 +54,53 @@
         return Collections.unmodifiableList(nodes);
     }
 
+    public static class TypedNodeIterator<T> implements Iterator<T> {
+        private final Class<T> type;
+        private final Iterator<Node> iter;
+        private Node nextNode;
+
+        public TypedNodeIterator(Class<T> type, Iterator<Node> iter) {
+            this.type = type;
+            this.iter = iter;
+            forward();
+        }
+
+        private void forward() {
+            do {
+                if (!iter.hasNext()) {
+                    nextNode = null;
+                    return;
+                }
+                nextNode = iter.next();
+            } while (nextNode == null || !type.isInstance(nextNode));
+        }
+
+        public boolean hasNext() {
+            return nextNode != null;
+        }
+
+        @SuppressWarnings("unchecked")
+        public T next() {
+            try {
+                return (T) nextNode;
+            } finally {
+                forward();
+            }
+        }
+
+        public void remove() {
+            throw new UnsupportedOperationException();
+        }
+    }
+
+    public <T extends Node> Iterable<T> getNodes(final Class<T> type) {
+        return new Iterable<T>() {
+            public Iterator<T> iterator() {
+                return new TypedNodeIterator<T>(type, nodes.iterator());
+            }
+        };
+    }
+
     int register(Node node) {
         int id = nextId++;
         nodes.add(id, node);
@@ -75,8 +123,8 @@
         return new NodeMap<T>(this);
     }
 
-    public NodeWorklist createNodeWorklist() {
-        return new NodeWorklist(this);
+    public NodeFlood createNodeFlood() {
+        return new NodeFlood(this);
     }
 
     public Map<Node, Node> addDuplicate(Collection<Node> nodes, Map<Node, Node> replacements) {
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeFlood.java	Wed Jun 08 14:30:27 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.max.graal.graph;
+
+import java.util.ArrayDeque;
+import java.util.Iterator;
+import java.util.Queue;
+
+
+public class NodeFlood implements Iterable<Node> {
+    private final NodeBitMap visited;
+    private final Queue<Node> worklist;
+
+    NodeFlood(Graph graph) {
+        visited = graph.createNodeBitMap();
+        worklist = new ArrayDeque<Node>();
+    }
+
+    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<Node> {
+        private final Queue<Node> queue;
+
+        public QueueConsumingIterator(Queue<Node> 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<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());
+            }
+        };
+    }
+}
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeWorklist.java	Wed Jun 08 13:06:45 2011 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,128 +0,0 @@
-/*
- * 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.Queue;
-
-
-public class NodeWorklist implements Iterable<Node> {
-    private final NodeBitMap visited;
-    private final Queue<Node> worklist;
-
-    NodeWorklist(Graph graph) {
-        visited = graph.createNodeBitMap();
-        worklist = new ArrayDeque<Node>();
-    }
-
-    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<Node> {
-        private final Queue<Node> queue;
-
-        public QueueConsumingIterator(Queue<Node> 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<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());
-            }
-        };
-    }
-}