Mercurial > hg > truffle

changeset 19846:7fdfb533dc7a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Rewrite gathering of loop kill information of FloatingReadPhase to reduce set allocations.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Sat, 14 Mar 2015 01:57:26 +0100
parents 3d0116ec99c5
children e17f04731c61
files graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/HIRLoop.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/FloatingReadPhase.java
diffstat 2 files changed, 61 insertions(+), 62 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/HIRLoop.java	Sat Mar 14 01:28:20 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/HIRLoop.java	Sat Mar 14 01:57:26 2015 +0100
@@ -26,7 +26,7 @@
 import com.oracle.graal.compiler.common.cfg.*;
 import com.oracle.graal.nodes.*;
 
-public class HIRLoop extends Loop<Block> {
+public final class HIRLoop extends Loop<Block> {
 
     private LocationSet killLocations;
 
@@ -39,7 +39,7 @@
         return ((LoopBeginNode) getHeader().getBeginNode()).loopEnds().count();
     }
 
-    protected LocationSet getKillLocations() {
+    private LocationSet getKillLocations() {
         if (killLocations == null) {
             killLocations = new LocationSet();
             for (Block b : this.getBlocks()) {
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/FloatingReadPhase.java	Sat Mar 14 01:28:20 2015 +0100
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/FloatingReadPhase.java	Sat Mar 14 01:57:26 2015 +0100
@@ -29,10 +29,12 @@
 
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.common.*;
+import com.oracle.graal.compiler.common.cfg.*;
 import com.oracle.graal.graph.Graph.NodeEventScope;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
+import com.oracle.graal.nodes.cfg.*;
 import com.oracle.graal.nodes.extended.*;
 import com.oracle.graal.nodes.util.*;
 import com.oracle.graal.phases.*;
@@ -125,10 +127,56 @@
         return set;
     }
 
+    protected void processNode(FixedNode node, Set<LocationIdentity> currentState) {
+        if (node instanceof MemoryCheckpoint.Single) {
+            currentState.add(((MemoryCheckpoint.Single) node).getLocationIdentity());
+        } else if (node instanceof MemoryCheckpoint.Multi) {
+            for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
+                currentState.add(identity);
+            }
+        }
+    }
+
+    protected void processBlock(Block b, Set<LocationIdentity> currentState) {
+        for (FixedNode n : b.getNodes()) {
+            processNode(n, currentState);
+        }
+    }
+
+    private Set<LocationIdentity> processLoop(HIRLoop loop, Map<LoopBeginNode, Set<LocationIdentity>> modifiedInLoops) {
+        LoopBeginNode loopBegin = (LoopBeginNode) loop.getHeader().getBeginNode();
+        Set<LocationIdentity> result = modifiedInLoops.get(loopBegin);
+        if (result != null) {
+            return result;
+        }
+
+        result = CollectionsFactory.newSet();
+        for (Loop<Block> inner : loop.getChildren()) {
+            result.addAll(processLoop((HIRLoop) inner, modifiedInLoops));
+        }
+
+        for (Block b : loop.getBlocks()) {
+            if (b.getLoop() == loop) {
+                processBlock(b, result);
+            }
+        }
+
+        modifiedInLoops.put(loopBegin, result);
+        return result;
+    }
+
     @Override
     protected void run(StructuredGraph graph) {
-        Map<LoopBeginNode, Set<LocationIdentity>> modifiedInLoops = Node.newIdentityMap();
-        ReentrantNodeIterator.apply(new CollectMemoryCheckpointsClosure(modifiedInLoops), graph.start(), CollectionsFactory.newSet());
+        Map<LoopBeginNode, Set<LocationIdentity>> modifiedInLoops = null;
+        if (graph.hasLoops()) {
+            modifiedInLoops = new HashMap<>();
+            ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false);
+            for (Loop<?> l : cfg.getLoops()) {
+                HIRLoop loop = (HIRLoop) l;
+                processLoop(loop, modifiedInLoops);
+            }
+        }
+
         HashSetNodeEventListener listener = new HashSetNodeEventListener(EnumSet.of(NODE_ADDED, ZERO_USAGES));
         try (NodeEventScope nes = graph.trackNodeEvents(listener)) {
             ReentrantNodeIterator.apply(new FloatingReadClosure(modifiedInLoops, createFloatingReads, createMemoryMapNodes), graph.start(), new MemoryMapImpl(graph.start()));
@@ -193,58 +241,6 @@
         return true;
     }
 
-    public static class CollectMemoryCheckpointsClosure extends NodeIteratorClosure<Set<LocationIdentity>> {
-
-        private final Map<LoopBeginNode, Set<LocationIdentity>> modifiedInLoops;
-
-        public CollectMemoryCheckpointsClosure(Map<LoopBeginNode, Set<LocationIdentity>> modifiedInLoops) {
-            this.modifiedInLoops = modifiedInLoops;
-        }
-
-        @Override
-        protected Set<LocationIdentity> processNode(FixedNode node, Set<LocationIdentity> currentState) {
-            if (node instanceof MemoryCheckpoint.Single) {
-                currentState.add(((MemoryCheckpoint.Single) node).getLocationIdentity());
-            } else if (node instanceof MemoryCheckpoint.Multi) {
-                for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
-                    currentState.add(identity);
-                }
-            }
-            return currentState;
-        }
-
-        @Override
-        protected Set<LocationIdentity> merge(AbstractMergeNode merge, List<Set<LocationIdentity>> states) {
-            Set<LocationIdentity> result = CollectionsFactory.newSet();
-            for (Set<LocationIdentity> other : states) {
-                result.addAll(other);
-            }
-            return result;
-        }
-
-        @Override
-        protected Set<LocationIdentity> afterSplit(AbstractBeginNode node, Set<LocationIdentity> oldState) {
-            return CollectionsFactory.newSet(oldState);
-        }
-
-        @Override
-        protected Map<LoopExitNode, Set<LocationIdentity>> processLoop(LoopBeginNode loop, Set<LocationIdentity> initialState) {
-            LoopInfo<Set<LocationIdentity>> loopInfo = ReentrantNodeIterator.processLoop(this, loop, CollectionsFactory.newSet());
-            Set<LocationIdentity> modifiedLocations = CollectionsFactory.newSet();
-            for (Set<LocationIdentity> end : loopInfo.endStates.values()) {
-                modifiedLocations.addAll(end);
-            }
-            for (Set<LocationIdentity> exit : loopInfo.exitStates.values()) {
-                exit.addAll(modifiedLocations);
-                exit.addAll(initialState);
-            }
-            assert checkNoImmutableLocations(modifiedLocations);
-            modifiedInLoops.put(loop, modifiedLocations);
-            return loopInfo.exitStates;
-        }
-
-    }
-
     public static class FloatingReadClosure extends NodeIteratorClosure<MemoryMapImpl> {
 
         private final Map<LoopBeginNode, Set<LocationIdentity>> modifiedInLoops;
@@ -345,18 +341,15 @@
         @Override
         protected Map<LoopExitNode, MemoryMapImpl> processLoop(LoopBeginNode loop, MemoryMapImpl initialState) {
             Set<LocationIdentity> modifiedLocations = modifiedInLoops.get(loop);
-            if (modifiedLocations.contains(any())) {
+            Map<LocationIdentity, MemoryPhiNode> phis = CollectionsFactory.newMap();
+            if (modifiedLocations.contains(LocationIdentity.any())) {
                 // create phis for all locations if ANY is modified in the loop
                 modifiedLocations = CollectionsFactory.newSet(modifiedLocations);
                 modifiedLocations.addAll(initialState.lastMemorySnapshot.keySet());
             }
 
-            Map<LocationIdentity, MemoryPhiNode> phis = CollectionsFactory.newMap();
-
             for (LocationIdentity location : modifiedLocations) {
-                MemoryPhiNode phi = loop.graph().addWithoutUnique(new MemoryPhiNode(loop, location));
-                phi.addInput(ValueNodeUtil.asNode(initialState.getLastLocationAccess(location)));
-                phis.put(location, phi);
+                createMemoryPhi(loop, initialState, phis, location);
             }
             for (Map.Entry<LocationIdentity, MemoryPhiNode> entry : phis.entrySet()) {
                 initialState.lastMemorySnapshot.put(entry.getKey(), entry.getValue());
@@ -374,5 +367,11 @@
             }
             return loopInfo.exitStates;
         }
+
+        private static void createMemoryPhi(LoopBeginNode loop, MemoryMapImpl initialState, Map<LocationIdentity, MemoryPhiNode> phis, LocationIdentity location) {
+            MemoryPhiNode phi = loop.graph().addWithoutUnique(new MemoryPhiNode(loop, location));
+            phi.addInput(ValueNodeUtil.asNode(initialState.getLastLocationAccess(location)));
+            phis.put(location, phi);
+        }
     }
 }