001/*
002 * Copyright (c) 2013, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023
024package com.oracle.graal.hotspot.phases;
025
026import static com.oracle.graal.hotspot.replacements.HotSpotReplacementsUtil.*;
027
028import java.util.*;
029
030import jdk.internal.jvmci.common.*;
031
032import com.oracle.graal.graph.*;
033import com.oracle.graal.hotspot.nodes.*;
034import com.oracle.graal.hotspot.replacements.*;
035import com.oracle.graal.nodes.*;
036import com.oracle.graal.nodes.extended.*;
037import com.oracle.graal.nodes.java.*;
038import com.oracle.graal.nodes.memory.*;
039import com.oracle.graal.nodes.memory.HeapAccess.BarrierType;
040import com.oracle.graal.nodes.memory.address.*;
041import com.oracle.graal.nodes.type.*;
042import com.oracle.graal.phases.*;
043
044/**
045 * Verification phase that checks if, for every write, at least one write barrier is present at all
046 * paths leading to the previous safepoint. For every write, necessitating a write barrier, a
047 * bottom-up traversal of the graph is performed up to the previous safepoints via all possible
048 * paths. If, for a certain path, no write barrier satisfying the processed write is found, an
049 * assertion is generated.
050 */
051public class WriteBarrierVerificationPhase extends Phase {
052
053    @Override
054    protected void run(StructuredGraph graph) {
055        processWrites(graph);
056    }
057
058    private static void processWrites(StructuredGraph graph) {
059        for (Node node : graph.getNodes()) {
060            if (isObjectWrite(node) || isObjectArrayRangeWrite(node)) {
061                validateWrite(node);
062            }
063        }
064    }
065
066    private static void validateWrite(Node write) {
067        /*
068         * The currently validated write is checked in order to discover if it has an appropriate
069         * attached write barrier.
070         */
071        if (hasAttachedBarrier((FixedWithNextNode) write)) {
072            return;
073        }
074        NodeFlood frontier = write.graph().createNodeFlood();
075        expandFrontier(frontier, write);
076        Iterator<Node> iterator = frontier.iterator();
077        while (iterator.hasNext()) {
078            Node currentNode = iterator.next();
079            if (isSafepoint(currentNode)) {
080                throw new AssertionError("Write barrier must be present " + write);
081            }
082            if (useG1GC()) {
083                if (!(currentNode instanceof G1PostWriteBarrier) || (!validateBarrier((FixedAccessNode) write, (ObjectWriteBarrier) currentNode))) {
084                    expandFrontier(frontier, currentNode);
085                }
086            } else {
087                if (!(currentNode instanceof SerialWriteBarrier) || (!validateBarrier((FixedAccessNode) write, (ObjectWriteBarrier) currentNode)) ||
088                                ((currentNode instanceof SerialWriteBarrier) && !validateBarrier((FixedAccessNode) write, (ObjectWriteBarrier) currentNode))) {
089                    expandFrontier(frontier, currentNode);
090                }
091            }
092        }
093    }
094
095    private static boolean hasAttachedBarrier(FixedWithNextNode node) {
096        final Node next = node.next();
097        final Node previous = node.predecessor();
098        final boolean validatePreBarrier = HotSpotReplacementsUtil.useG1GC() && (isObjectWrite(node) || !((ArrayRangeWriteNode) node).isInitialization());
099        if (isObjectWrite(node)) {
100            return (isObjectBarrier(node, next) || StampTool.isPointerAlwaysNull(getValueWritten(node))) && (!validatePreBarrier || isObjectBarrier(node, previous));
101        } else if (isObjectArrayRangeWrite(node)) {
102            return (isArrayBarrier(node, next) || StampTool.isPointerAlwaysNull(getValueWritten(node))) && (!validatePreBarrier || isArrayBarrier(node, previous));
103        } else {
104            return true;
105        }
106    }
107
108    private static boolean isObjectBarrier(FixedWithNextNode node, final Node next) {
109        return next instanceof ObjectWriteBarrier && validateBarrier((FixedAccessNode) node, (ObjectWriteBarrier) next);
110    }
111
112    private static boolean isArrayBarrier(FixedWithNextNode node, final Node next) {
113        return (next instanceof ArrayRangeWriteBarrier) && ((ArrayRangeWriteNode) node).getArray() == ((ArrayRangeWriteBarrier) next).getObject();
114    }
115
116    private static boolean isObjectWrite(Node node) {
117        // Read nodes with barrier attached (G1 Ref field) are not validated yet.
118        return node instanceof FixedAccessNode && ((HeapAccess) node).getBarrierType() != BarrierType.NONE && !(node instanceof ReadNode);
119    }
120
121    private static boolean isObjectArrayRangeWrite(Node node) {
122        return node instanceof ArrayRangeWriteNode && ((ArrayRangeWriteNode) node).isObjectArray();
123    }
124
125    private static void expandFrontier(NodeFlood frontier, Node node) {
126        for (Node previousNode : node.cfgPredecessors()) {
127            if (previousNode != null) {
128                frontier.add(previousNode);
129            }
130        }
131    }
132
133    private static boolean isSafepoint(Node node) {
134        /*
135         * LoopBegin nodes are also treated as safepoints since a bottom-up analysis is performed
136         * and loop safepoints are placed before LoopEnd nodes. Possible elimination of write
137         * barriers inside loops, derived from writes outside loops, can not be permitted.
138         */
139        return ((node instanceof DeoptimizingNode) && ((DeoptimizingNode) node).canDeoptimize()) || (node instanceof LoopBeginNode);
140    }
141
142    private static ValueNode getValueWritten(FixedWithNextNode write) {
143        if (write instanceof WriteNode) {
144            return ((WriteNode) write).value();
145        } else if (write instanceof LoweredCompareAndSwapNode) {
146            return ((LoweredCompareAndSwapNode) write).getNewValue();
147        } else if (write instanceof LoweredAtomicReadAndWriteNode) {
148            return ((LoweredAtomicReadAndWriteNode) write).getNewValue();
149        } else {
150            throw JVMCIError.shouldNotReachHere(String.format("unexpected write node %s", write));
151        }
152    }
153
154    private static boolean validateBarrier(FixedAccessNode write, ObjectWriteBarrier barrier) {
155        assert write instanceof WriteNode || write instanceof LoweredCompareAndSwapNode || write instanceof LoweredAtomicReadAndWriteNode : "Node must be of type requiring a write barrier " + write;
156        if (!barrier.usePrecise()) {
157            if (barrier.getAddress() instanceof OffsetAddressNode && write.getAddress() instanceof OffsetAddressNode) {
158                return ((OffsetAddressNode) barrier.getAddress()).getBase() == ((OffsetAddressNode) write.getAddress()).getBase();
159            }
160        }
161        return barrier.getAddress() == write.getAddress();
162    }
163}