# HG changeset patch # User Thomas Wuerthinger # Date 1426605450 -3600 # Node ID bce741b26b84757f643d02f9d962ce1f12bb6c30 # Parent 749b96e8ff901057ad497c09f9adebb10e9f253e Add memory schedule verification pass. Fix a bug in the new schedule implementation. diff -r 749b96e8ff90 -r bce741b26b84 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/MemoryScheduleVerification.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/MemoryScheduleVerification.java Tue Mar 17 16:17:30 2015 +0100 @@ -0,0 +1,147 @@ +/* + * Copyright (c) 2015, 2015, 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.graal.phases.schedule; + +import java.util.*; + +import com.oracle.graal.api.meta.*; +import com.oracle.graal.compiler.common.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.graph.Node; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; +import com.oracle.graal.nodes.extended.*; +import com.oracle.graal.phases.graph.*; +import com.oracle.graal.phases.graph.ReentrantBlockIterator.BlockIteratorClosure; + +public final class MemoryScheduleVerification extends BlockIteratorClosure> { + + private final BlockMap> blockToNodesMap; + + public static boolean check(Block startBlock, BlockMap> blockToNodesMap) { + ReentrantBlockIterator.apply(new MemoryScheduleVerification(blockToNodesMap), startBlock); + return true; + } + + private MemoryScheduleVerification(BlockMap> blockToNodesMap) { + this.blockToNodesMap = blockToNodesMap; + } + + @Override + protected Set getInitialState() { + return CollectionsFactory.newSet(); + } + + @Override + protected Set processBlock(Block block, Set currentState) { + for (Node n : blockToNodesMap.get(block)) { + if (n instanceof AbstractMergeNode) { + AbstractMergeNode abstractMergeNode = (AbstractMergeNode) n; + for (PhiNode phi : abstractMergeNode.phis()) { + if (phi instanceof MemoryPhiNode) { + MemoryPhiNode memoryPhiNode = (MemoryPhiNode) phi; + addFloatingReadUsages(currentState, memoryPhiNode); + } + } + + } + + if (n instanceof MemoryCheckpoint) { + if (n instanceof MemoryCheckpoint.Single) { + MemoryCheckpoint.Single single = (MemoryCheckpoint.Single) n; + processLocation(n, single.getLocationIdentity(), currentState); + } else if (n instanceof MemoryCheckpoint.Multi) { + MemoryCheckpoint.Multi multi = (MemoryCheckpoint.Multi) n; + for (LocationIdentity location : multi.getLocationIdentities()) { + processLocation(n, location, currentState); + } + } + + addFloatingReadUsages(currentState, n); + } else if (n instanceof FloatingReadNode) { + FloatingReadNode floatingReadNode = (FloatingReadNode) n; + if (floatingReadNode.getLastLocationAccess() != null && floatingReadNode.getLocationIdentity().isMutable()) { + if (currentState.contains(floatingReadNode)) { + // Floating read was found in the state. + currentState.remove(floatingReadNode); + } else { + throw new RuntimeException("Floating read node " + n + " was not found in the state, i.e., it was killed by a memory check point before its place in the schedule"); + } + } + + } + } + return currentState; + } + + private static void addFloatingReadUsages(Set currentState, Node n) { + for (FloatingReadNode read : n.usages().filter(FloatingReadNode.class)) { + if (read.getLastLocationAccess() == n && read.getLocationIdentity().isMutable()) { + currentState.add(read); + } + } + } + + private void processLocation(Node n, LocationIdentity location, Set currentState) { + assert n != null; + if (location.isImmutable()) { + return; + } + + for (FloatingReadNode r : cloneState(currentState)) { + if (r.getLocationIdentity().overlaps(location)) { + // This read is killed by this location. + currentState.remove(r); + } + } + } + + @Override + protected Set merge(Block merge, List> states) { + Set result = states.get(0); + for (int i = 1; i < states.size(); ++i) { + result.retainAll(states.get(i)); + } + return result; + } + + @Override + protected Set cloneState(Set oldState) { + Set result = CollectionsFactory.newSet(); + result.addAll(oldState); + return result; + } + + @Override + protected List> processLoop(Loop loop, Set initialState) { + HIRLoop l = (HIRLoop) loop; + for (MemoryPhiNode memoryPhi : ((LoopBeginNode) l.getHeader().getBeginNode()).phis().filter(MemoryPhiNode.class)) { + for (FloatingReadNode r : cloneState(initialState)) { + if (r.getLocationIdentity().overlaps(memoryPhi.getLocationIdentity())) { + initialState.remove(r); + } + } + } + return ReentrantBlockIterator.processLoop(this, loop, initialState).exitStates; + } +} diff -r 749b96e8ff90 -r bce741b26b84 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java --- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Tue Mar 17 13:14:13 2015 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Tue Mar 17 16:17:30 2015 +0100 @@ -115,10 +115,12 @@ BlockMap> watchListMap = calcLatestBlocks(isOutOfLoops, currentNodeMap, earliestBlockToNodesMap, visited, latestBlockToNodesMap); sortNodesLatestWithinBlock(cfg, earliestBlockToNodesMap, latestBlockToNodesMap, currentNodeMap, watchListMap, visited); + assert verifySchedule(cfg, latestBlockToNodesMap, currentNodeMap); + assert MemoryScheduleVerification.check(cfg.getStartBlock(), latestBlockToNodesMap); + this.blockToNodesMap = latestBlockToNodesMap; this.nodeToBlockMap = currentNodeMap; - assert verifySchedule(cfg, latestBlockToNodesMap, currentNodeMap); cfg.setNodeToBlock(currentNodeMap); } } @@ -538,6 +540,8 @@ } } } + + assert MemoryScheduleVerification.check(cfg.getStartBlock(), blockToNodes); } private static void resortEarliestWithinBlock(Block b, BlockMap> blockToNodes, NodeMap nodeToBlock, NodeBitMap unprocessed) { @@ -551,7 +555,7 @@ MemoryNode lastLocationAccess = floatingReadNode.getLastLocationAccess(); if (locationIdentity.isMutable() && lastLocationAccess != null) { ValueNode lastAccessLocation = lastLocationAccess.asNode(); - if (nodeToBlock.get(lastAccessLocation) == b && lastAccessLocation != beginNode) { + if (nodeToBlock.get(lastAccessLocation) == b && lastAccessLocation != beginNode && !(lastAccessLocation instanceof MemoryPhiNode)) { // This node's last access location is within this block. Add to watch list // when processing the last access location. } else {