1 /*
2 * Copyright (c) 2013, 2018, 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
24
25
26 package org.graalvm.compiler.hotspot.phases;
27
28 import java.util.Iterator;
29
30 import org.graalvm.compiler.debug.GraalError;
31 import org.graalvm.compiler.graph.Node;
32 import org.graalvm.compiler.graph.NodeFlood;
33 import org.graalvm.compiler.hotspot.GraalHotSpotVMConfig;
34 import org.graalvm.compiler.hotspot.nodes.ArrayRangeWriteBarrier;
35 import org.graalvm.compiler.hotspot.nodes.G1PostWriteBarrier;
36 import org.graalvm.compiler.hotspot.nodes.ObjectWriteBarrier;
37 import org.graalvm.compiler.hotspot.nodes.SerialWriteBarrier;
38 import org.graalvm.compiler.nodeinfo.Verbosity;
39 import org.graalvm.compiler.nodes.DeoptimizingNode;
40 import org.graalvm.compiler.nodes.FixedWithNextNode;
41 import org.graalvm.compiler.nodes.LoopBeginNode;
42 import org.graalvm.compiler.nodes.StructuredGraph;
43 import org.graalvm.compiler.nodes.ValueNode;
44 import org.graalvm.compiler.nodes.extended.ArrayRangeWrite;
45 import org.graalvm.compiler.nodes.java.LoweredAtomicReadAndWriteNode;
46 import org.graalvm.compiler.nodes.java.LogicCompareAndSwapNode;
47 import org.graalvm.compiler.nodes.memory.FixedAccessNode;
48 import org.graalvm.compiler.nodes.memory.HeapAccess;
49 import org.graalvm.compiler.nodes.memory.HeapAccess.BarrierType;
50 import org.graalvm.compiler.nodes.memory.ReadNode;
51 import org.graalvm.compiler.nodes.memory.WriteNode;
52 import org.graalvm.compiler.nodes.memory.address.OffsetAddressNode;
53 import org.graalvm.compiler.nodes.type.StampTool;
54 import org.graalvm.compiler.nodes.util.GraphUtil;
55 import org.graalvm.compiler.phases.Phase;
56
57 /**
58 * Verification phase that checks if, for every write, at least one write barrier is present at all
59 * paths leading to the previous safepoint. For every write, necessitating a write barrier, a
60 * bottom-up traversal of the graph is performed up to the previous safepoints via all possible
61 * paths. If, for a certain path, no write barrier satisfying the processed write is found, an
62 * assertion is generated.
63 */
64 public class WriteBarrierVerificationPhase extends Phase {
65
66 private final GraalHotSpotVMConfig config;
67
68 public WriteBarrierVerificationPhase(GraalHotSpotVMConfig config) {
69 this.config = config;
70 }
71
72 @Override
73 protected void run(StructuredGraph graph) {
74 processWrites(graph);
75 }
76
77 private void processWrites(StructuredGraph graph) {
78 for (Node node : graph.getNodes()) {
79 if (isObjectWrite(node) || isObjectArrayRangeWrite(node)) {
80 if (node instanceof WriteNode) {
81 WriteNode writeNode = (WriteNode) node;
82 if (StampTool.isPointerAlwaysNull(writeNode.value())) {
83 continue;
84 }
85 }
86 validateWrite(node);
87 }
88 }
89 }
90
91 private void validateWrite(Node write) {
92 /*
93 * The currently validated write is checked in order to discover if it has an appropriate
94 * attached write barrier.
95 */
96 if (hasAttachedBarrier((FixedWithNextNode) write)) {
97 return;
98 }
99 NodeFlood frontier = write.graph().createNodeFlood();
100 expandFrontier(frontier, write);
101 Iterator<Node> iterator = frontier.iterator();
102 while (iterator.hasNext()) {
103 Node currentNode = iterator.next();
104 if (isSafepoint(currentNode)) {
105 throw new AssertionError("Write barrier must be present " + write.toString(Verbosity.All) + " / " + write.inputs());
106 }
107 if (useG1GC()) {
108 if (!(currentNode instanceof G1PostWriteBarrier) || (!validateBarrier((FixedAccessNode) write, (ObjectWriteBarrier) currentNode))) {
109 expandFrontier(frontier, currentNode);
110 }
111 } else {
112 if (!(currentNode instanceof SerialWriteBarrier) || (!validateBarrier((FixedAccessNode) write, (ObjectWriteBarrier) currentNode)) ||
113 ((currentNode instanceof SerialWriteBarrier) && !validateBarrier((FixedAccessNode) write, (ObjectWriteBarrier) currentNode))) {
114 expandFrontier(frontier, currentNode);
115 }
116 }
117 }
118 }
119
120 private boolean useG1GC() {
121 return config.useG1GC;
122 }
123
124 private boolean hasAttachedBarrier(FixedWithNextNode node) {
125 final Node next = node.next();
126 final Node previous = node.predecessor();
127 boolean validatePreBarrier = useG1GC() && (isObjectWrite(node) || !((ArrayRangeWrite) node).isInitialization());
128 if (node instanceof WriteNode) {
129 WriteNode writeNode = (WriteNode) node;
130 if (writeNode.getLocationIdentity().isInit()) {
131 validatePreBarrier = false;
132 }
133 }
134 if (isObjectWrite(node)) {
135 return (isObjectBarrier(node, next) || StampTool.isPointerAlwaysNull(getValueWritten(node))) && (!validatePreBarrier || isObjectBarrier(node, previous));
136 } else if (isObjectArrayRangeWrite(node)) {
137 return (isArrayBarrier(node, next) || StampTool.isPointerAlwaysNull(getValueWritten(node))) && (!validatePreBarrier || isArrayBarrier(node, previous));
138 } else {
139 return true;
140 }
141 }
142
143 private static boolean isObjectBarrier(FixedWithNextNode node, final Node next) {
144 return next instanceof ObjectWriteBarrier && validateBarrier((FixedAccessNode) node, (ObjectWriteBarrier) next);
145 }
146
147 private static boolean isArrayBarrier(FixedWithNextNode node, final Node next) {
148 return (next instanceof ArrayRangeWriteBarrier) && ((ArrayRangeWrite) node).getAddress() == ((ArrayRangeWriteBarrier) next).getAddress();
149 }
150
151 private static boolean isObjectWrite(Node node) {
152 // Read nodes with barrier attached (G1 Ref field) are not validated yet.
153 return node instanceof FixedAccessNode && ((HeapAccess) node).getBarrierType() != BarrierType.NONE && !(node instanceof ReadNode);
154 }
155
156 private static boolean isObjectArrayRangeWrite(Node node) {
157 return node instanceof ArrayRangeWrite && ((ArrayRangeWrite) node).writesObjectArray();
158 }
159
160 private static void expandFrontier(NodeFlood frontier, Node node) {
161 for (Node previousNode : node.cfgPredecessors()) {
162 if (previousNode != null) {
163 frontier.add(previousNode);
164 }
165 }
166 }
167
168 private static boolean isSafepoint(Node node) {
169 if (node instanceof FixedAccessNode) {
170 // Implicit null checks on reads or writes do not count.
171 return false;
172 }
173 /*
174 * LoopBegin nodes are also treated as safepoints since a bottom-up analysis is performed
175 * and loop safepoints are placed before LoopEnd nodes. Possible elimination of write
176 * barriers inside loops, derived from writes outside loops, can not be permitted.
177 */
178 return ((node instanceof DeoptimizingNode) && ((DeoptimizingNode) node).canDeoptimize()) || (node instanceof LoopBeginNode);
179 }
180
181 private static ValueNode getValueWritten(FixedWithNextNode write) {
182 if (write instanceof WriteNode) {
183 return ((WriteNode) write).value();
184 } else if (write instanceof LogicCompareAndSwapNode) {
185 return ((LogicCompareAndSwapNode) write).getNewValue();
186 } else if (write instanceof LoweredAtomicReadAndWriteNode) {
187 return ((LoweredAtomicReadAndWriteNode) write).getNewValue();
188 } else {
189 throw GraalError.shouldNotReachHere(String.format("unexpected write node %s", write));
190 }
191 }
192
193 private static boolean validateBarrier(FixedAccessNode write, ObjectWriteBarrier barrier) {
194 assert write instanceof WriteNode || write instanceof LogicCompareAndSwapNode || write instanceof LoweredAtomicReadAndWriteNode : "Node must be of type requiring a write barrier " + write;
195 if (!barrier.usePrecise()) {
196 if (barrier.getAddress() instanceof OffsetAddressNode && write.getAddress() instanceof OffsetAddressNode) {
197 return GraphUtil.unproxify(((OffsetAddressNode) barrier.getAddress()).getBase()) == GraphUtil.unproxify(((OffsetAddressNode) write.getAddress()).getBase());
198 }
199 }
200 return barrier.getAddress() == write.getAddress();
201 }
202 }