1/*
2 * Copyright (c) 2014, 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 */
23package org.graalvm.compiler.core.match;
24
25import static org.graalvm.compiler.debug.DebugOptions.LogVerbose;
26
27import java.util.ArrayList;
28import java.util.Arrays;
29import java.util.List;
30
31import org.graalvm.compiler.core.gen.NodeLIRBuilder;
32import org.graalvm.compiler.core.match.MatchPattern.Result;
33import org.graalvm.compiler.debug.DebugContext;
34import org.graalvm.compiler.debug.GraalError;
35import org.graalvm.compiler.graph.Node;
36import org.graalvm.compiler.nodes.calc.FloatingNode;
37import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
38import org.graalvm.util.EconomicMap;
39import org.graalvm.util.Equivalence;
40
41/**
42 * Container for state captured during a match.
43 */
44public class MatchContext {
45
46    private final Node root;
47
48    private final List<Node> nodes;
49
50    private final MatchStatement rule;
51
52    private EconomicMap<String, NamedNode> namedNodes;
53
54    private ArrayList<Node> consumed;
55
56    private int startIndex;
57
58    private int endIndex;
59
60    private final NodeLIRBuilder builder;
61
62    private static class NamedNode {
63        final Class<? extends Node> type;
64        final Node value;
65
66        NamedNode(Class<? extends Node> type, Node value) {
67            this.type = type;
68            this.value = value;
69        }
70    }
71
72    public MatchContext(NodeLIRBuilder builder, MatchStatement rule, int index, Node node, List<Node> nodes) {
73        this.builder = builder;
74        this.rule = rule;
75        this.root = node;
76        this.nodes = nodes;
77        assert index == nodes.indexOf(node);
78        // The root should be the last index since all the inputs must be scheduled before it.
79        startIndex = endIndex = index;
80    }
81
82    public Node getRoot() {
83        return root;
84    }
85
86    public Result captureNamedValue(String name, Class<? extends Node> type, Node value) {
87        if (namedNodes == null) {
88            namedNodes = EconomicMap.create(Equivalence.DEFAULT);
89        }
90        NamedNode current = namedNodes.get(name);
91        if (current == null) {
92            current = new NamedNode(type, value);
93            namedNodes.put(name, current);
94            return Result.OK;
95        } else {
96            if (current.value != value || current.type != type) {
97                return Result.namedValueMismatch(value, rule.getPattern());
98            }
99            return Result.OK;
100        }
101    }
102
103    public Result validate() {
104        // Ensure that there's no unsafe work in between these operations.
105        for (int i = startIndex; i <= endIndex; i++) {
106            Node node = nodes.get(i);
107            if (node instanceof VirtualObjectNode || node instanceof FloatingNode) {
108                // The order of evaluation of these nodes controlled by data dependence so they
109                // don't interfere with this match.
110                continue;
111            } else if ((consumed == null || !consumed.contains(node)) && node != root) {
112                if (LogVerbose.getValue(root.getOptions())) {
113                    DebugContext debug = root.getDebug();
114                    debug.log("unexpected node %s", node);
115                    for (int j = startIndex; j <= endIndex; j++) {
116                        Node theNode = nodes.get(j);
117                        debug.log("%s(%s) %1s", (consumed != null && consumed.contains(theNode) || theNode == root) ? "*" : " ", theNode.getUsageCount(), theNode);
118                    }
119                }
120                return Result.notSafe(node, rule.getPattern());
121            }
122        }
123        return Result.OK;
124    }
125
126    /**
127     * Mark the interior nodes with INTERIOR_MATCH and set the Value of the root to be the result.
128     * During final LIR generation it will be evaluated to produce the actual LIR value.
129     *
130     * @param result
131     */
132    public void setResult(ComplexMatchResult result) {
133        ComplexMatchValue value = new ComplexMatchValue(result);
134        DebugContext debug = root.getDebug();
135        if (debug.isLogEnabled()) {
136            debug.log("matched %s %s", rule.getName(), rule.getPattern());
137            debug.log("with nodes %s", rule.formatMatch(root));
138        }
139        if (consumed != null) {
140            for (Node node : consumed) {
141                // All the interior nodes should be skipped during the normal doRoot calls in
142                // NodeLIRBuilder so mark them as interior matches. The root of the match will get a
143                // closure which will be evaluated to produce the final LIR.
144                builder.setMatchResult(node, ComplexMatchValue.INTERIOR_MATCH);
145            }
146        }
147        builder.setMatchResult(root, value);
148    }
149
150    /**
151     * Mark a node as consumed by the match. Consumed nodes will never be evaluated.
152     *
153     * @return Result.OK if the node can be safely consumed.
154     */
155    public Result consume(Node node) {
156        assert MatchPattern.isSingleValueUser(node) : "should have already been checked";
157
158        // Check NOT_IN_BLOCK first since that usually implies ALREADY_USED
159        int index = nodes.indexOf(node);
160        if (index == -1) {
161            return Result.notInBlock(node, rule.getPattern());
162        }
163
164        if (builder.hasOperand(node)) {
165            return Result.alreadyUsed(node, rule.getPattern());
166        }
167
168        startIndex = Math.min(startIndex, index);
169        if (consumed == null) {
170            consumed = new ArrayList<>(2);
171        }
172        consumed.add(node);
173        return Result.OK;
174    }
175
176    /**
177     * Return the named node. It's an error if the
178     *
179     * @param name the name of a node in the match rule
180     * @return the matched node
181     * @throws GraalError is the named node doesn't exist.
182     */
183    public Node namedNode(String name) {
184        if (namedNodes != null) {
185            NamedNode value = namedNodes.get(name);
186            if (value != null) {
187                return value.value;
188            }
189        }
190        throw new GraalError("missing node %s", name);
191    }
192
193    @Override
194    public String toString() {
195        return String.format("%s %s (%d, %d) consumed %s", rule, root, startIndex, endIndex, consumed != null ? Arrays.toString(consumed.toArray()) : "");
196    }
197}
198