001/*
002 * Copyright (c) 2014, 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 */
023package com.oracle.graal.compiler.match;
024
025import static com.oracle.graal.debug.GraalDebugConfig.*;
026
027import java.util.*;
028
029import jdk.internal.jvmci.common.*;
030import com.oracle.graal.debug.*;
031
032import com.oracle.graal.compiler.gen.*;
033import com.oracle.graal.compiler.match.MatchPattern.Result;
034import com.oracle.graal.graph.*;
035import com.oracle.graal.nodes.calc.*;
036import com.oracle.graal.nodes.virtual.*;
037
038/**
039 * Container for state captured during a match.
040 */
041public class MatchContext {
042
043    private final Node root;
044
045    private final List<Node> nodes;
046
047    private final MatchStatement rule;
048
049    private Map<String, NamedNode> namedNodes;
050
051    private ArrayList<Node> consumed;
052
053    private int startIndex;
054
055    private int endIndex;
056
057    private final NodeLIRBuilder builder;
058
059    private static class NamedNode {
060        final Class<? extends Node> type;
061        final Node value;
062
063        NamedNode(Class<? extends Node> type, Node value) {
064            this.type = type;
065            this.value = value;
066        }
067    }
068
069    public MatchContext(NodeLIRBuilder builder, MatchStatement rule, int index, Node node, List<Node> nodes) {
070        this.builder = builder;
071        this.rule = rule;
072        this.root = node;
073        this.nodes = nodes;
074        assert index == nodes.indexOf(node);
075        // The root should be the last index since all the inputs must be scheduled before it.
076        startIndex = endIndex = index;
077    }
078
079    public Node getRoot() {
080        return root;
081    }
082
083    public Result captureNamedValue(String name, Class<? extends Node> type, Node value) {
084        if (namedNodes == null) {
085            namedNodes = new HashMap<>(2);
086        }
087        NamedNode current = namedNodes.get(name);
088        if (current == null) {
089            current = new NamedNode(type, value);
090            namedNodes.put(name, current);
091            return Result.OK;
092        } else {
093            if (current.value != value || current.type != type) {
094                return Result.namedValueMismatch(value, rule.getPattern());
095            }
096            return Result.OK;
097        }
098    }
099
100    public Result validate() {
101        // Ensure that there's no unsafe work in between these operations.
102        for (int i = startIndex; i <= endIndex; i++) {
103            Node node = nodes.get(i);
104            if (node instanceof VirtualObjectNode || node instanceof FloatingNode) {
105                // The order of evaluation of these nodes controlled by data dependence so they
106                // don't interfere with this match.
107                continue;
108            } else if ((consumed == null || !consumed.contains(node)) && node != root) {
109                if (LogVerbose.getValue()) {
110                    Debug.log("unexpected node %s", node);
111                    for (int j = startIndex; j <= endIndex; j++) {
112                        Node theNode = nodes.get(j);
113                        Debug.log("%s(%s) %1s", (consumed != null && consumed.contains(theNode) || theNode == root) ? "*" : " ", theNode.getUsageCount(), theNode);
114                    }
115                }
116                return Result.notSafe(node, rule.getPattern());
117            }
118        }
119        return Result.OK;
120    }
121
122    /**
123     * Mark the interior nodes with INTERIOR_MATCH and set the Value of the root to be the result.
124     * During final LIR generation it will be evaluated to produce the actual LIR value.
125     *
126     * @param result
127     */
128    public void setResult(ComplexMatchResult result) {
129        ComplexMatchValue value = new ComplexMatchValue(result);
130        if (Debug.isLogEnabled()) {
131            Debug.log("matched %s %s", rule.getName(), rule.getPattern());
132            Debug.log("with nodes %s", rule.formatMatch(root));
133        }
134        if (consumed != null) {
135            for (Node node : consumed) {
136                // All the interior nodes should be skipped during the normal doRoot calls in
137                // NodeLIRBuilder so mark them as interior matches. The root of the match will get a
138                // closure which will be evaluated to produce the final LIR.
139                builder.setMatchResult(node, ComplexMatchValue.INTERIOR_MATCH);
140            }
141        }
142        builder.setMatchResult(root, value);
143    }
144
145    /**
146     * Mark a node as consumed by the match. Consumed nodes will never be evaluated.
147     *
148     * @return Result.OK if the node can be safely consumed.
149     */
150    public Result consume(Node node) {
151        assert node.getUsageCount() <= 1 : "should have already been checked";
152
153        // Check NOT_IN_BLOCK first since that usually implies ALREADY_USED
154        int index = nodes.indexOf(node);
155        if (index == -1) {
156            return Result.notInBlock(node, rule.getPattern());
157        }
158
159        if (builder.hasOperand(node)) {
160            return Result.alreadyUsed(node, rule.getPattern());
161        }
162
163        startIndex = Math.min(startIndex, index);
164        if (consumed == null) {
165            consumed = new ArrayList<>(2);
166        }
167        consumed.add(node);
168        return Result.OK;
169    }
170
171    /**
172     * Return the named node. It's an error if the
173     *
174     * @param name the name of a node in the match rule
175     * @return the matched node
176     * @throws JVMCIError is the named node doesn't exist.
177     */
178    public Node namedNode(String name) {
179        if (namedNodes != null) {
180            NamedNode value = namedNodes.get(name);
181            if (value != null) {
182                return value.value;
183            }
184        }
185        throw new JVMCIError("missing node %s", name);
186    }
187
188    @Override
189    public String toString() {
190        return String.format("%s %s (%d, %d) consumed %s", rule, root, startIndex, endIndex, consumed != null ? Arrays.toString(consumed.toArray()) : "");
191    }
192}