# HG changeset patch # User Christos Kotselidis # Date 1366830620 -7200 # Node ID 31dc304507e9128215135bdce036a04c3628eeb5 # Parent 159ac409c27a203a9ced9576e9bae35d63880242 New write barrier verification phase diff -r 159ac409c27a -r 31dc304507e9 graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/phases/WriteBarrierVerificationPhase.java --- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/phases/WriteBarrierVerificationPhase.java Wed Apr 24 18:53:06 2013 +0200 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/phases/WriteBarrierVerificationPhase.java Wed Apr 24 21:10:20 2013 +0200 @@ -31,193 +31,98 @@ import com.oracle.graal.nodes.extended.WriteNode.WriteBarrierType; import com.oracle.graal.nodes.java.*; import com.oracle.graal.phases.*; -import com.oracle.graal.phases.graph.*; public class WriteBarrierVerificationPhase extends Phase { - private class MemoryMap implements MergeableState { - - private IdentityHashMap> lastMemorySnapshot; - private IdentityHashMap> lastWriteBarrierSnapshot; - - public MemoryMap(MemoryMap memoryMap) { - lastMemorySnapshot = new IdentityHashMap<>(memoryMap.lastMemorySnapshot); - lastWriteBarrierSnapshot = new IdentityHashMap<>(memoryMap.lastWriteBarrierSnapshot); - } - - public MemoryMap() { - lastMemorySnapshot = new IdentityHashMap<>(); - lastWriteBarrierSnapshot = new IdentityHashMap<>(); - } - - @Override - public String toString() { - return "Map=" + lastMemorySnapshot.toString(); - } - - @Override - public boolean merge(MergeNode merge, List withStates) { - if (withStates.size() == 0) { - return true; - } - - for (MemoryMap other : withStates) { - for (Object otherObject : other.lastMemorySnapshot.keySet()) { - LinkedList currentLocations = lastMemorySnapshot.get(otherObject); - LinkedList otherLocations = other.lastMemorySnapshot.get(otherObject); - if (otherLocations != null) { - if (currentLocations == null) { - currentLocations = new LinkedList<>(); - } - for (LocationNode location : otherLocations) { - if (!currentLocations.contains(location)) { - currentLocations.add(location); - } - } - } - } - for (Object otherObject : other.lastWriteBarrierSnapshot.keySet()) { - LinkedList currentWriteBarriers = lastWriteBarrierSnapshot.get(otherObject); - LinkedList otherWriteBarriers = other.lastWriteBarrierSnapshot.get(otherObject); - if (otherWriteBarriers != null) { - if (currentWriteBarriers == null) { - currentWriteBarriers = new LinkedList<>(); - } - for (SerialWriteBarrier barrier : otherWriteBarriers) { - if (!currentWriteBarriers.contains(barrier)) { - currentWriteBarriers.add(barrier); - } - } - } - } - } - return true; - } - - @Override - public void loopBegin(LoopBeginNode loopBegin) { - } - - @Override - public void loopEnds(LoopBeginNode loopBegin, List loopEndStates) { - } - - @Override - public void afterSplit(BeginNode node) { - } - - @Override - public MemoryMap clone() { - return new MemoryMap(this); - } + @Override + protected void run(StructuredGraph graph) { + processSafepoints(graph); } - @Override - protected void run(StructuredGraph graph) { - new PostOrderNodeIterator(graph.start(), new MemoryMap()) { - - @Override - protected void node(FixedNode node) { - processNode(node, state); - } - }.apply(); - } - - private static void processNode(FixedNode node, MemoryMap state) { - if (node instanceof WriteNode) { - processWriteNode((WriteNode) node, state); - } else if (node instanceof CompareAndSwapNode) { - processCASNode((CompareAndSwapNode) node, state); - } else if (node instanceof SerialWriteBarrier) { - processWriteBarrier((SerialWriteBarrier) node, state); - } else if ((node instanceof DeoptimizingNode)) { - if (((DeoptimizingNode) node).canDeoptimize()) { - validateWriteBarriers(state); - processSafepoint(state); + private static void processSafepoints(StructuredGraph graph) { + for (Node node : graph.getNodes()) { + if (isSafepoint(node)) { + verifyWrites(node); } } } - private static void processWriteNode(WriteNode node, MemoryMap state) { - if (node.getWriteBarrierType() != WriteBarrierType.NONE) { - LinkedList locations = state.lastMemorySnapshot.get(node.object()); - if (locations == null) { - locations = new LinkedList<>(); - locations.add(node.location()); - state.lastMemorySnapshot.put(node.object(), locations); - } else if ((node.getWriteBarrierType() == WriteBarrierType.PRECISE) && !locations.contains(node.location())) { - locations.add(node.location()); + private static void verifyWrites(Node safepoint) { + Deque frontier = new ArrayDeque<>(); + List processedWrites = new LinkedList<>(); + expandFrontier(frontier, safepoint); + while (!frontier.isEmpty()) { + Node currentNode = frontier.removeFirst(); + if (isSafepoint(currentNode)) { + continue; } + if (isObjectWrite(currentNode) && !processedWrites.contains(currentNode)) { + validateWrite(currentNode); + processedWrites.add(currentNode); + } + expandFrontier(frontier, currentNode); } + } - private static void processCASNode(CompareAndSwapNode node, MemoryMap state) { - if (node.getWriteBarrierType() != WriteBarrierType.NONE) { - LinkedList locations = state.lastMemorySnapshot.get(node.object()); - if (locations == null) { - locations = new LinkedList<>(); - locations.add(node.getLocation()); - state.lastMemorySnapshot.put(node.object(), locations); - } else if ((node.getWriteBarrierType() == WriteBarrierType.PRECISE) && !locations.contains(node.getLocation())) { - locations.add(node.getLocation()); + private static void validateWrite(Node write) { + if (hasCorrectAttachedBarrier(write)) { + return; + } + Deque frontier = new ArrayDeque<>(); + expandFrontier(frontier, write); + while (!frontier.isEmpty()) { + Node currentNode = frontier.removeFirst(); + assert !isSafepoint(currentNode) : "Write barrier must be present"; + if (!(currentNode instanceof SerialWriteBarrier) || ((currentNode instanceof SerialWriteBarrier) && !foundCorrectBarrier(write, currentNode))) { + expandFrontier(frontier, currentNode); } } } - private static void processWriteBarrier(SerialWriteBarrier currentBarrier, MemoryMap state) { - LinkedList writeBarriers = state.lastWriteBarrierSnapshot.get(currentBarrier.getObject()); - if (writeBarriers == null) { - writeBarriers = new LinkedList<>(); - writeBarriers.add(currentBarrier); - state.lastWriteBarrierSnapshot.put(currentBarrier.getObject(), writeBarriers); - } else if (currentBarrier.usePrecise()) { - boolean found = false; - for (SerialWriteBarrier barrier : writeBarriers) { - if (barrier.getLocation() == currentBarrier.getLocation()) { - found = true; - break; + private static boolean hasCorrectAttachedBarrier(Node node) { + return (((FixedWithNextNode) node).next() instanceof SerialWriteBarrier) && foundCorrectBarrier(node, ((FixedWithNextNode) node).next()); + } + + private static boolean isObjectWrite(Node node) { + if ((node instanceof WriteNode && (((WriteNode) node).getWriteBarrierType() != WriteBarrierType.NONE)) || + (node instanceof CompareAndSwapNode && (((CompareAndSwapNode) node).getWriteBarrierType() != WriteBarrierType.NONE))) { + return true; + } + return false; + } + + private static void expandFrontier(Deque frontier, Node node) { + for (Node previousNode : node.cfgPredecessors()) { + if (previousNode != null) { + if (previousNode instanceof ControlSplitNode && frontier.contains(previousNode)) { + continue; } - } - if (!found) { - writeBarriers.add(currentBarrier); + frontier.addFirst(previousNode); } } } - private static void validateWriteBarriers(MemoryMap state) { - Set objects = state.lastMemorySnapshot.keySet(); - for (Object write : objects) { - LinkedList writeBarriers = state.lastWriteBarrierSnapshot.get(write); - if (writeBarriers == null) { - throw new GraalInternalError("Failed to find any write barrier at safepoint for written object"); - } - /* - * Check the first write barrier of the object to determine if it is precise or not. If - * it is not, the validation for this object has passed (since we had a hit in the write - * barrier hashmap), otherwise we have to ensure the presence of write barriers for - * every written location. - */ - final boolean precise = writeBarriers.getFirst().usePrecise(); - if (precise) { - LinkedList locations = state.lastMemorySnapshot.get(write); - for (LocationNode location : locations) { - boolean found = false; - for (SerialWriteBarrier barrier : writeBarriers) { - if (location == barrier.getLocation()) { - found = true; - break; - } - } - if (!found) { - throw new GraalInternalError("Failed to find write barrier at safepoint for precise written object"); - } - } - } - } + private static boolean isSafepoint(Node node) { + return (node instanceof DeoptimizingNode) && ((DeoptimizingNode) node).canDeoptimize(); } - private static void processSafepoint(MemoryMap state) { - state.lastMemorySnapshot.clear(); - state.lastWriteBarrierSnapshot.clear(); + private static boolean foundCorrectBarrier(Node write, Node barrier) { + SerialWriteBarrier barrierNode = (SerialWriteBarrier) barrier; + if (write instanceof WriteNode) { + WriteNode writeNode = (WriteNode) write; + if ((barrierNode.getObject() == writeNode.object()) && (!barrierNode.usePrecise() || (barrierNode.usePrecise() && barrierNode.getLocation() == writeNode.location()))) { + return true; + } + return false; + } else if (write instanceof CompareAndSwapNode) { + CompareAndSwapNode casNode = (CompareAndSwapNode) write; + if ((barrierNode.getObject() == casNode.object()) && (!barrierNode.usePrecise() || (barrierNode.usePrecise() && barrierNode.getLocation() == casNode.getLocation()))) { + return true; + } + return false; + } + assert false : "Node must be of type requiring a write barrier"; + return false; } }