# HG changeset patch
# User Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
# Date 1426294646 -3600
# Node ID 7fdfb533dc7a1712202ab69088e9692bb7f84f93
# Parent  3d0116ec99c5d6519d633f232d53b2ef0fac5e08
Rewrite gathering of loop kill information of FloatingReadPhase to reduce set allocations.

diff -r 3d0116ec99c5 -r 7fdfb533dc7a graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/HIRLoop.java
--- 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()) {
diff -r 3d0116ec99c5 -r 7fdfb533dc7a graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/FloatingReadPhase.java
--- 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);
+        }
     }
 }