Source code

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 com.oracle.graal.debug.*;
026
027import com.oracle.graal.graph.*;
028import com.oracle.graal.nodeinfo.*;
029
030/**
031 * A simple recursive pattern matcher for a DAG of nodes.
032 */
033
034public class MatchPattern {
035
036    enum MatchResultCode {
037        OK,
038        WRONG_CLASS,
039        NAMED_VALUE_MISMATCH,
040        TOO_MANY_USERS,
041        NOT_IN_BLOCK,
042        NOT_SAFE,
043        ALREADY_USED,
044    }
045
046    /**
047     * A descriptive result for match failures. This can be helpful for debugging why a match
048     * doesn't work as expected.
049     */
050    static class Result {
051        final MatchResultCode code;
052
053        final Node node;
054
055        final MatchPattern matcher;
056
057        Result(MatchResultCode result, Node node, MatchPattern matcher) {
058            this.code = result;
059            this.node = node;
060            this.matcher = matcher;
061        }
062
063        private static final DebugMetric MatchResult_WRONG_CLASS = Debug.metric("MatchResult_WRONG_CLASS");
064        private static final DebugMetric MatchResult_NAMED_VALUE_MISMATCH = Debug.metric("MatchResult_NAMED_VALUE_MISMATCH");
065        private static final DebugMetric MatchResult_TOO_MANY_USERS = Debug.metric("MatchResult_TOO_MANY_USERS");
066        private static final DebugMetric MatchResult_NOT_IN_BLOCK = Debug.metric("MatchResult_NOT_IN_BLOCK");
067        private static final DebugMetric MatchResult_NOT_SAFE = Debug.metric("MatchResult_NOT_SAFE");
068        private static final DebugMetric MatchResult_ALREADY_USED = Debug.metric("MatchResult_ALREADY_USED");
069
070        static final Result OK = new Result(MatchResultCode.OK, null, null);
071        private static final Result CACHED_WRONG_CLASS = new Result(MatchResultCode.WRONG_CLASS, null, null);
072        private static final Result CACHED_NAMED_VALUE_MISMATCH = new Result(MatchResultCode.NAMED_VALUE_MISMATCH, null, null);
073        private static final Result CACHED_TOO_MANY_USERS = new Result(MatchResultCode.TOO_MANY_USERS, null, null);
074        private static final Result CACHED_NOT_IN_BLOCK = new Result(MatchResultCode.NOT_IN_BLOCK, null, null);
075        private static final Result CACHED_NOT_SAFE = new Result(MatchResultCode.NOT_SAFE, null, null);
076        private static final Result CACHED_ALREADY_USED = new Result(MatchResultCode.ALREADY_USED, null, null);
077
078        static Result wrongClass(Node node, MatchPattern matcher) {
079            MatchResult_WRONG_CLASS.increment();
080            return Debug.isLogEnabled() ? new Result(MatchResultCode.WRONG_CLASS, node, matcher) : CACHED_WRONG_CLASS;
081        }
082
083        static Result namedValueMismatch(Node node, MatchPattern matcher) {
084            MatchResult_NAMED_VALUE_MISMATCH.increment();
085            return Debug.isLogEnabled() ? new Result(MatchResultCode.NAMED_VALUE_MISMATCH, node, matcher) : CACHED_NAMED_VALUE_MISMATCH;
086        }
087
088        static Result tooManyUsers(Node node, MatchPattern matcher) {
089            MatchResult_TOO_MANY_USERS.increment();
090            return Debug.isLogEnabled() ? new Result(MatchResultCode.TOO_MANY_USERS, node, matcher) : CACHED_TOO_MANY_USERS;
091        }
092
093        static Result notInBlock(Node node, MatchPattern matcher) {
094            MatchResult_NOT_IN_BLOCK.increment();
095            return Debug.isLogEnabled() ? new Result(MatchResultCode.NOT_IN_BLOCK, node, matcher) : CACHED_NOT_IN_BLOCK;
096        }
097
098        static Result notSafe(Node node, MatchPattern matcher) {
099            MatchResult_NOT_SAFE.increment();
100            return Debug.isLogEnabled() ? new Result(MatchResultCode.NOT_SAFE, node, matcher) : CACHED_NOT_SAFE;
101        }
102
103        static Result alreadyUsed(Node node, MatchPattern matcher) {
104            MatchResult_ALREADY_USED.increment();
105            return Debug.isLogEnabled() ? new Result(MatchResultCode.ALREADY_USED, node, matcher) : CACHED_ALREADY_USED;
106        }
107
108        @Override
109        public String toString() {
110            if (code == MatchResultCode.OK) {
111                return "OK";
112            }
113            if (node == null) {
114                return code.toString();
115            } else {
116                return code + " " + node.toString(Verbosity.Id) + "|" + node.getClass().getSimpleName() + " " + matcher;
117            }
118        }
119    }
120
121    /**
122     * The expected type of the node. It must match exactly.
123     */
124    private final Class<? extends Node> nodeClass;
125
126    /**
127     * An optional name for this node. A name can occur multiple times in a match and that name must
128     * always refer to the same node of the match will fail.
129     */
130    private final String name;
131
132    /**
133     * Patterns to match the inputs.
134     */
135    private final MatchPattern[] patterns;
136
137    /**
138     * The inputs to match the patterns against.
139     */
140    private final Position[] inputs;
141
142    /**
143     * Can there only be one user of the node. Constant nodes can be matched even if there are other
144     * users.
145     */
146    private final boolean singleUser;
147
148    private static final MatchPattern[] EMPTY_PATTERNS = new MatchPattern[0];
149
150    public MatchPattern(String name, boolean singleUser) {
151        this(null, name, singleUser);
152    }
153
154    public MatchPattern(Class<? extends Node> nodeClass, String name, boolean singleUser) {
155        this.nodeClass = nodeClass;
156        this.name = name;
157        this.singleUser = singleUser;
158        this.patterns = EMPTY_PATTERNS;
159        this.inputs = null;
160    }
161
162    private MatchPattern(Class<? extends Node> nodeClass, String name, boolean singleUser, MatchPattern[] patterns, Position[] inputs) {
163        assert inputs == null || inputs.length == patterns.length;
164        this.nodeClass = nodeClass;
165        this.name = name;
166        this.singleUser = singleUser;
167        this.patterns = patterns;
168        this.inputs = inputs;
169    }
170
171    public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, Position[] inputs, boolean singleUser) {
172        this(nodeClass, name, singleUser, new MatchPattern[]{first}, inputs);
173    }
174
175    public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, MatchPattern second, Position[] inputs, boolean singleUser) {
176        this(nodeClass, name, singleUser, new MatchPattern[]{first, second}, inputs);
177    }
178
179    public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, MatchPattern second, MatchPattern third, Position[] inputs, boolean singleUser) {
180        this(nodeClass, name, singleUser, new MatchPattern[]{first, second, third}, inputs);
181    }
182
183    Class<? extends Node> nodeClass() {
184        return nodeClass;
185    }
186
187    private Result matchType(Node node) {
188        if (nodeClass != null && node.getClass() != nodeClass) {
189            return Result.wrongClass(node, this);
190        }
191        return Result.OK;
192    }
193
194    /**
195     * Match any named nodes and ensure that the consumed nodes can be safely merged.
196     *
197     * @param node
198     * @param context
199     * @return Result.OK is the pattern can be safely matched.
200     */
201    Result matchUsage(Node node, MatchContext context) {
202        Result result = matchUsage(node, context, true);
203        if (result == Result.OK) {
204            result = context.validate();
205        }
206        return result;
207    }
208
209    private Result matchUsage(Node node, MatchContext context, boolean atRoot) {
210        Result result = matchType(node);
211        if (result != Result.OK) {
212            return result;
213        }
214        if (singleUser && !atRoot) {
215            result = context.consume(node);
216            if (result != Result.OK) {
217                return result;
218            }
219        }
220
221        if (name != null) {
222            result = context.captureNamedValue(name, nodeClass, node);
223        }
224
225        for (int input = 0; input < patterns.length; input++) {
226            result = patterns[input].matchUsage(getInput(input, node), context, false);
227            if (result != Result.OK) {
228                return result;
229            }
230        }
231
232        return result;
233    }
234
235    /**
236     * Recursively match the shape of the tree without worry about named values. Most matches fail
237     * at this point so it's performed first.
238     *
239     * @param node
240     * @param statement
241     * @return Result.OK if the shape of the pattern matches.
242     */
243    public Result matchShape(Node node, MatchStatement statement) {
244        return matchShape(node, statement, true);
245    }
246
247    private Result matchShape(Node node, MatchStatement statement, boolean atRoot) {
248        Result result = matchType(node);
249        if (result != Result.OK) {
250            return result;
251        }
252
253        if (singleUser && !atRoot) {
254            if (node.getUsageCount() > 1) {
255                return Result.tooManyUsers(node, statement.getPattern());
256            }
257        }
258
259        for (int input = 0; input < patterns.length; input++) {
260            result = patterns[input].matchShape(getInput(input, node), statement, false);
261            if (result != Result.OK) {
262                return result;
263            }
264        }
265
266        return result;
267    }
268
269    /**
270     * For a node starting at root, produce a String showing the inputs that matched against this
271     * rule. It's assumed that a match has already succeeded against this rule, otherwise the
272     * printing may produce exceptions.
273     */
274    public String formatMatch(Node root) {
275        String result = String.format("%s", root);
276        if (patterns.length == 0) {
277            return result;
278        } else {
279            StringBuilder sb = new StringBuilder();
280            sb.append("(");
281            sb.append(result);
282            for (int input = 0; input < patterns.length; input++) {
283                sb.append(" ");
284                sb.append(patterns[input].formatMatch(getInput(input, root)));
285            }
286            sb.append(")");
287            return sb.toString();
288        }
289    }
290
291    private Node getInput(int index, Node node) {
292        return inputs[index].get(node);
293    }
294
295    @Override
296    public String toString() {
297        if (nodeClass == null) {
298            return name;
299        } else {
300            String nodeName = nodeClass.getSimpleName();
301            if (nodeName.endsWith("Node")) {
302                nodeName = nodeName.substring(0, nodeName.length() - 4);
303            }
304            if (patterns.length == 0) {
305                return nodeName + (name != null ? "=" + name : "");
306            } else {
307                StringBuilder sb = new StringBuilder();
308                sb.append("(");
309                sb.append(nodeName);
310                for (int index = 0; index < patterns.length; index++) {
311                    sb.append(" ");
312                    sb.append(patterns[index].toString());
313                }
314                sb.append(")");
315                return sb.toString();
316            }
317        }
318    }
319}