WriteBarrierVerificationPhase.java revision 12651:6ef01bd40ce2 
1/*
2 * Copyright (c) 2013, 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24package org.graalvm.compiler.hotspot.phases;
25
26import java.util.Iterator;
27
28import org.graalvm.compiler.debug.GraalError;
29import org.graalvm.compiler.graph.Node;
30import org.graalvm.compiler.graph.NodeFlood;
31import org.graalvm.compiler.hotspot.GraalHotSpotVMConfig;
32import org.graalvm.compiler.hotspot.nodes.ArrayRangeWriteBarrier;
33import org.graalvm.compiler.hotspot.nodes.G1PostWriteBarrier;
34import org.graalvm.compiler.hotspot.nodes.ObjectWriteBarrier;
35import org.graalvm.compiler.hotspot.nodes.SerialWriteBarrier;
36import org.graalvm.compiler.nodes.DeoptimizingNode;
37import org.graalvm.compiler.nodes.FixedWithNextNode;
38import org.graalvm.compiler.nodes.LoopBeginNode;
39import org.graalvm.compiler.nodes.StructuredGraph;
40import org.graalvm.compiler.nodes.ValueNode;
41import org.graalvm.compiler.nodes.extended.ArrayRangeWriteNode;
42import org.graalvm.compiler.nodes.java.LoweredAtomicReadAndWriteNode;
43import org.graalvm.compiler.nodes.java.LoweredCompareAndSwapNode;
44import org.graalvm.compiler.nodes.memory.FixedAccessNode;
45import org.graalvm.compiler.nodes.memory.HeapAccess;
46import org.graalvm.compiler.nodes.memory.HeapAccess.BarrierType;
47import org.graalvm.compiler.nodes.memory.ReadNode;
48import org.graalvm.compiler.nodes.memory.WriteNode;
49import org.graalvm.compiler.nodes.memory.address.OffsetAddressNode;
50import org.graalvm.compiler.nodes.type.StampTool;
51import org.graalvm.compiler.phases.Phase;
52
53/**
54 * Verification phase that checks if, for every write, at least one write barrier is present at all
55 * paths leading to the previous safepoint. For every write, necessitating a write barrier, a
56 * bottom-up traversal of the graph is performed up to the previous safepoints via all possible
57 * paths. If, for a certain path, no write barrier satisfying the processed write is found, an
58 * assertion is generated.
59 */
60public class WriteBarrierVerificationPhase extends Phase {
61
62    private final GraalHotSpotVMConfig config;
63
64    public WriteBarrierVerificationPhase(GraalHotSpotVMConfig config) {
65        this.config = config;
66    }
67
68    @Override
69    protected void run(StructuredGraph graph) {
70        processWrites(graph);
71    }
72
73    private void processWrites(StructuredGraph graph) {
74        for (Node node : graph.getNodes()) {
75            if (isObjectWrite(node) || isObjectArrayRangeWrite(node)) {
76                validateWrite(node);
77            }
78        }
79    }
80
81    private void validateWrite(Node write) {
82        /*
83         * The currently validated write is checked in order to discover if it has an appropriate
84         * attached write barrier.
85         */
86        if (hasAttachedBarrier((FixedWithNextNode) write)) {
87            return;
88        }
89        NodeFlood frontier = write.graph().createNodeFlood();
90        expandFrontier(frontier, write);
91        Iterator<Node> iterator = frontier.iterator();
92        while (iterator.hasNext()) {
93            Node currentNode = iterator.next();
94            if (isSafepoint(currentNode)) {
95                throw new AssertionError("Write barrier must be present " + write);
96            }
97            if (useG1GC()) {
98                if (!(currentNode instanceof G1PostWriteBarrier) || (!validateBarrier((FixedAccessNode) write, (ObjectWriteBarrier) currentNode))) {
99                    expandFrontier(frontier, currentNode);
100                }
101            } else {
102                if (!(currentNode instanceof SerialWriteBarrier) || (!validateBarrier((FixedAccessNode) write, (ObjectWriteBarrier) currentNode)) ||
103                                ((currentNode instanceof SerialWriteBarrier) && !validateBarrier((FixedAccessNode) write, (ObjectWriteBarrier) currentNode))) {
104                    expandFrontier(frontier, currentNode);
105                }
106            }
107        }
108    }
109
110    private boolean useG1GC() {
111        return config.useG1GC;
112    }
113
114    private boolean hasAttachedBarrier(FixedWithNextNode node) {
115        final Node next = node.next();
116        final Node previous = node.predecessor();
117        final boolean validatePreBarrier = useG1GC() && (isObjectWrite(node) || !((ArrayRangeWriteNode) node).isInitialization());
118        if (isObjectWrite(node)) {
119            return (isObjectBarrier(node, next) || StampTool.isPointerAlwaysNull(getValueWritten(node))) && (!validatePreBarrier || isObjectBarrier(node, previous));
120        } else if (isObjectArrayRangeWrite(node)) {
121            return (isArrayBarrier(node, next) || StampTool.isPointerAlwaysNull(getValueWritten(node))) && (!validatePreBarrier || isArrayBarrier(node, previous));
122        } else {
123            return true;
124        }
125    }
126
127    private static boolean isObjectBarrier(FixedWithNextNode node, final Node next) {
128        return next instanceof ObjectWriteBarrier && validateBarrier((FixedAccessNode) node, (ObjectWriteBarrier) next);
129    }
130
131    private static boolean isArrayBarrier(FixedWithNextNode node, final Node next) {
132        return (next instanceof ArrayRangeWriteBarrier) && ((ArrayRangeWriteNode) node).getArray() == ((ArrayRangeWriteBarrier) next).getObject();
133    }
134
135    private static boolean isObjectWrite(Node node) {
136        // Read nodes with barrier attached (G1 Ref field) are not validated yet.
137        return node instanceof FixedAccessNode && ((HeapAccess) node).getBarrierType() != BarrierType.NONE && !(node instanceof ReadNode);
138    }
139
140    private static boolean isObjectArrayRangeWrite(Node node) {
141        return node instanceof ArrayRangeWriteNode && ((ArrayRangeWriteNode) node).isObjectArray();
142    }
143
144    private static void expandFrontier(NodeFlood frontier, Node node) {
145        for (Node previousNode : node.cfgPredecessors()) {
146            if (previousNode != null) {
147                frontier.add(previousNode);
148            }
149        }
150    }
151
152    private static boolean isSafepoint(Node node) {
153        /*
154         * LoopBegin nodes are also treated as safepoints since a bottom-up analysis is performed
155         * and loop safepoints are placed before LoopEnd nodes. Possible elimination of write
156         * barriers inside loops, derived from writes outside loops, can not be permitted.
157         */
158        return ((node instanceof DeoptimizingNode) && ((DeoptimizingNode) node).canDeoptimize()) || (node instanceof LoopBeginNode);
159    }
160
161    private static ValueNode getValueWritten(FixedWithNextNode write) {
162        if (write instanceof WriteNode) {
163            return ((WriteNode) write).value();
164        } else if (write instanceof LoweredCompareAndSwapNode) {
165            return ((LoweredCompareAndSwapNode) write).getNewValue();
166        } else if (write instanceof LoweredAtomicReadAndWriteNode) {
167            return ((LoweredAtomicReadAndWriteNode) write).getNewValue();
168        } else {
169            throw GraalError.shouldNotReachHere(String.format("unexpected write node %s", write));
170        }
171    }
172
173    private static boolean validateBarrier(FixedAccessNode write, ObjectWriteBarrier barrier) {
174        assert write instanceof WriteNode || write instanceof LoweredCompareAndSwapNode || write instanceof LoweredAtomicReadAndWriteNode : "Node must be of type requiring a write barrier " + write;
175        if (!barrier.usePrecise()) {
176            if (barrier.getAddress() instanceof OffsetAddressNode && write.getAddress() instanceof OffsetAddressNode) {
177                return ((OffsetAddressNode) barrier.getAddress()).getBase() == ((OffsetAddressNode) write.getAddress()).getBase();
178            }
179        }
180        return barrier.getAddress() == write.getAddress();
181    }
182}
183