1 /*

     2  * Copyright (c) 2015, 2019, 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 package org.graalvm.compiler.phases.schedule;

    26 

    27 import java.util.List;

    28 

    29 import jdk.internal.vm.compiler.collections.EconomicSet;

    30 import jdk.internal.vm.compiler.collections.Equivalence;

    31 import org.graalvm.compiler.core.common.cfg.BlockMap;

    32 import org.graalvm.compiler.core.common.cfg.Loop;

    33 import org.graalvm.compiler.debug.DebugContext;

    34 import org.graalvm.compiler.graph.Node;

    35 import org.graalvm.compiler.graph.NodeMap;

    36 import org.graalvm.compiler.nodes.AbstractBeginNode;

    37 import org.graalvm.compiler.nodes.AbstractMergeNode;

    38 import org.graalvm.compiler.nodes.LoopBeginNode;

    39 import org.graalvm.compiler.nodes.LoopExitNode;

    40 import org.graalvm.compiler.nodes.MemoryProxyNode;

    41 import org.graalvm.compiler.nodes.PhiNode;

    42 import org.graalvm.compiler.nodes.ProxyNode;

    43 import org.graalvm.compiler.nodes.StructuredGraph;

    44 import org.graalvm.compiler.nodes.VirtualState;

    45 import org.graalvm.compiler.nodes.cfg.Block;

    46 import org.graalvm.compiler.nodes.cfg.HIRLoop;

    47 import org.graalvm.compiler.nodes.memory.FloatingReadNode;

    48 import org.graalvm.compiler.nodes.memory.MemoryCheckpoint;

    49 import org.graalvm.compiler.nodes.memory.MemoryNode;

    50 import org.graalvm.compiler.nodes.memory.MemoryPhiNode;

    51 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator;

    52 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;

    53 import jdk.internal.vm.compiler.word.LocationIdentity;

    54 

    55 /**

    56  * Verifies that the schedule of the graph is correct. Checks that floating reads are not killed

    57  * between definition and usage. Also checks that there are no usages spanning loop exits without a

    58  * proper proxy node.

    59  */

    60 public final class ScheduleVerification extends BlockIteratorClosure<EconomicSet<FloatingReadNode>> {

    61 

    62     private final BlockMap<List<Node>> blockToNodesMap;

    63     private final NodeMap<Block> nodeMap;

    64     private final StructuredGraph graph;

    65 

    66     public static boolean check(Block startBlock, BlockMap<List<Node>> blockToNodesMap, NodeMap<Block> nodeMap) {

    67         ReentrantBlockIterator.apply(new ScheduleVerification(blockToNodesMap, nodeMap, startBlock.getBeginNode().graph()), startBlock);

    68         return true;

    69     }

    70 

    71     private ScheduleVerification(BlockMap<List<Node>> blockToNodesMap, NodeMap<Block> nodeMap, StructuredGraph graph) {

    72         this.blockToNodesMap = blockToNodesMap;

    73         this.nodeMap = nodeMap;

    74         this.graph = graph;

    75     }

    76 

    77     @Override

    78     protected EconomicSet<FloatingReadNode> getInitialState() {

    79         return EconomicSet.create(Equivalence.IDENTITY);

    80     }

    81 

    82     @Override

    83     protected EconomicSet<FloatingReadNode> processBlock(Block block, EconomicSet<FloatingReadNode> currentState) {

    84         AbstractBeginNode beginNode = block.getBeginNode();

    85         if (beginNode instanceof AbstractMergeNode) {

    86             AbstractMergeNode abstractMergeNode = (AbstractMergeNode) beginNode;

    87             for (PhiNode phi : abstractMergeNode.phis()) {

    88                 if (phi instanceof MemoryPhiNode) {

    89                     MemoryPhiNode memoryPhiNode = (MemoryPhiNode) phi;

    90                     addFloatingReadUsages(currentState, memoryPhiNode);

    91                 }

    92             }

    93         }

    94         if (beginNode instanceof LoopExitNode) {

    95             LoopExitNode loopExitNode = (LoopExitNode) beginNode;

    96             for (ProxyNode proxy : loopExitNode.proxies()) {

    97                 if (proxy instanceof MemoryProxyNode) {

    98                     MemoryProxyNode memoryProxyNode = (MemoryProxyNode) proxy;

    99                     addFloatingReadUsages(currentState, memoryProxyNode);

   100                 }

   101             }

   102         }

   103         for (Node n : blockToNodesMap.get(block)) {

   104             if (n instanceof MemoryCheckpoint) {

   105                 if (n instanceof MemoryCheckpoint.Single) {

   106                     MemoryCheckpoint.Single single = (MemoryCheckpoint.Single) n;

   107                     processLocation(n, single.getKilledLocationIdentity(), currentState);

   108                 } else if (n instanceof MemoryCheckpoint.Multi) {

   109                     MemoryCheckpoint.Multi multi = (MemoryCheckpoint.Multi) n;

   110                     for (LocationIdentity location : multi.getKilledLocationIdentities()) {

   111                         processLocation(n, location, currentState);

   112                     }

   113                 }

   114 

   115                 addFloatingReadUsages(currentState, n);

   116             } else if (n instanceof MemoryNode) {

   117                 addFloatingReadUsages(currentState, n);

   118             } else if (n instanceof FloatingReadNode) {

   119                 FloatingReadNode floatingReadNode = (FloatingReadNode) n;

   120                 if (floatingReadNode.getLastLocationAccess() != null && floatingReadNode.getLocationIdentity().isMutable()) {

   121                     if (currentState.contains(floatingReadNode)) {

   122                         // Floating read was found in the state.

   123                         currentState.remove(floatingReadNode);

   124                     } else {

   125                         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. Block=" +

   126                                         block + ", block begin: " + block.getBeginNode() + " block loop: " + block.getLoop() + ", " + blockToNodesMap.get(block).get(0));

   127                     }

   128                 }

   129             }

   130             assert nodeMap.get(n) == block;

   131             if (graph.hasValueProxies() && block.getLoop() != null && !(n instanceof VirtualState)) {

   132                 for (Node usage : n.usages()) {

   133                     Node usageNode = usage;

   134 

   135                     if (usageNode instanceof PhiNode) {

   136                         PhiNode phiNode = (PhiNode) usage;

   137                         usageNode = phiNode.merge();

   138                     }

   139 

   140                     if (usageNode instanceof LoopExitNode) {

   141                         LoopExitNode loopExitNode = (LoopExitNode) usageNode;

   142                         if (loopExitNode.loopBegin() == n || loopExitNode.stateAfter() == n) {

   143                             continue;

   144                         }

   145                     }

   146                     Block usageBlock = nodeMap.get(usageNode);

   147 

   148                     Loop<Block> usageLoop = null;

   149                     if (usageNode instanceof ProxyNode) {

   150                         ProxyNode proxyNode = (ProxyNode) usageNode;

   151                         usageLoop = nodeMap.get(proxyNode.proxyPoint().loopBegin()).getLoop();

   152                     } else {

   153                         if (usageBlock.getBeginNode() instanceof LoopExitNode) {

   154                             // For nodes in the loop exit node block, we don't know for sure

   155                             // whether they are "in the loop" or not. It depends on whether

   156                             // one of their transient usages is a loop proxy node.

   157                             // For now, let's just assume those nodes are OK, i.e., "in the loop".

   158                             LoopExitNode loopExitNode = (LoopExitNode) usageBlock.getBeginNode();

   159                             usageLoop = nodeMap.get(loopExitNode.loopBegin()).getLoop();

   160                         } else {

   161                             usageLoop = usageBlock.getLoop();

   162                         }

   163                     }

   164 

   165                     assert usageLoop != null : n + ", " + nodeMap.get(n) + " / " + usageNode + ", " + nodeMap.get(usageNode);

   166                     while (usageLoop != block.getLoop() && usageLoop != null) {

   167                         usageLoop = usageLoop.getParent();

   168                     }

   169                     assert usageLoop != null : n + ", " + usageNode + ", " + usageBlock + ", " + usageBlock.getLoop() + ", " + block + ", " + block.getLoop();

   170                 }

   171             }

   172         }

   173         return currentState;

   174     }

   175 

   176     private static void addFloatingReadUsages(EconomicSet<FloatingReadNode> currentState, Node n) {

   177         for (FloatingReadNode read : n.usages().filter(FloatingReadNode.class)) {

   178             if (read.getLastLocationAccess() == n && read.getLocationIdentity().isMutable()) {

   179                 currentState.add(read);

   180             }

   181         }

   182     }

   183 

   184     private void processLocation(Node n, LocationIdentity location, EconomicSet<FloatingReadNode> currentState) {

   185         assert n != null;

   186         if (location.isImmutable()) {

   187             return;

   188         }

   189 

   190         for (FloatingReadNode r : cloneState(currentState)) {

   191             if (r.getLocationIdentity().overlaps(location)) {

   192                 // This read is killed by this location.

   193                 r.getDebug().log(DebugContext.VERBOSE_LEVEL, "%s removing %s from state", n, r);

   194                 currentState.remove(r);

   195             }

   196         }

   197     }

   198 

   199     @Override

   200     protected EconomicSet<FloatingReadNode> merge(Block merge, List<EconomicSet<FloatingReadNode>> states) {

   201         EconomicSet<FloatingReadNode> result = states.get(0);

   202         for (int i = 1; i < states.size(); ++i) {

   203             result.retainAll(states.get(i));

   204         }

   205         return result;

   206     }

   207 

   208     @Override

   209     protected EconomicSet<FloatingReadNode> cloneState(EconomicSet<FloatingReadNode> oldState) {

   210         EconomicSet<FloatingReadNode> result = EconomicSet.create(Equivalence.IDENTITY);

   211         if (oldState != null) {

   212             result.addAll(oldState);

   213         }

   214         return result;

   215     }

   216 

   217     @Override

   218     protected List<EconomicSet<FloatingReadNode>> processLoop(Loop<Block> loop, EconomicSet<FloatingReadNode> initialState) {

   219         HIRLoop l = (HIRLoop) loop;

   220         for (MemoryPhiNode memoryPhi : ((LoopBeginNode) l.getHeader().getBeginNode()).memoryPhis()) {

   221             for (FloatingReadNode r : cloneState(initialState)) {

   222                 if (r.getLocationIdentity().overlaps(memoryPhi.getLocationIdentity())) {

   223                     initialState.remove(r);

   224                 }

   225             }

   226         }

   227         return ReentrantBlockIterator.processLoop(this, loop, initialState).exitStates;

   228     }

   229 }