1 /*
2 * Copyright (c) 2024, 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. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package jdk.incubator.code.analysis;
27
28 import jdk.incubator.code.Block;
29 import jdk.incubator.code.Op;
30 import jdk.incubator.code.CodeElement;
31 import jdk.incubator.code.Value;
32 import jdk.incubator.code.dialect.core.CoreOp;
33 import java.util.*;
34 import java.util.function.BiFunction;
35 import java.util.function.Predicate;
36
37 /**
38 * A simple and experimental pattern match mechanism on values and operations.
39 * <p>
40 * When the language has support for pattern matching with matcher methods we should be able to express
41 * matching on values and operations more powerfully and concisely.
42 */
43 public final class Patterns {
44
45 private Patterns() {
46 }
47
48
49 /**
50 * Traverses this operation and its descendant operations and returns the set of operations that are unused
51 * (have no uses) and are pure (are instances of {@code Op.Pure} and thus have no side effects).
52 *
53 * @param op the operation to traverse
54 * @return the set of used and pure operations.
55 */
56 public static Set<Op> matchUnusedPureOps(Op op) {
57 return matchUnusedPureOps(op, o -> o instanceof Op.Pure);
58 }
59
60 /**
61 * Traverses this operation and its descendant operations and returns the set of operations that are unused
62 * (have no uses) and are pure (according to the given predicate).
63 *
64 * @param op the operation to traverse
65 * @param testPure the predicate to test if an operation is pure
66 * @return the set of used and pure operations.
67 */
68 public static Set<Op> matchUnusedPureOps(Op op, Predicate<Op> testPure) {
69 return match(
70 new HashSet<>(),
71 op, opP(o -> isDeadOp(o, testPure)),
72 (ms, deadOps) -> {
73 deadOps.add(ms.op());
74
75 // Dependent dead ops
76 matchDependentDeadOps(ms.op(), deadOps, testPure);
77 // @@@ No means to control traversal and only go deeper when
78 // there is only one user
79 // ms.op().traverseOperands(null, (_a, arg) -> {
80 // if (arg.result().users().size() == 1) {
81 // deadOps.add(arg);
82 // }
83 //
84 // return null;
85 // });
86
87 return deadOps;
88 });
89 }
90
91 static boolean isDeadOp(Op op, Predicate<Op> testPure) {
92 if (op instanceof Op.Terminating) {
93 return false;
94 }
95
96 return op.result() != null && op.result().uses().isEmpty() && testPure.test(op);
97 }
98
99 // @@@ this could be made generic with a method traversing up the model tree,
100 // the challenge is controlling when to keep traversing or not, and it may make
101 // it more complex that just writing it like below for specific cases
102 // A better option may be to provide a lazy stream of the values that can be filtered
103 // similar to CodeElement::elements
104 static void matchDependentDeadOps(Op op, Set<Op> deadOps, Predicate<Op> testPure) {
105 for (Value arg : op.operands()) {
106 if (arg instanceof Op.Result or) {
107 if (arg.uses().size() == 1 && testPure.test(or.op())) {
108 deadOps.add(or.op());
109
110 // Traverse only when a single user
111 matchDependentDeadOps(or.op(), deadOps, testPure);
112 }
113 }
114 }
115 }
116
117
118 // Matching of patterns
119
120 /**
121 * The state of a successful match of an operation with matched operands (if any)
122 */
123 public static final class MatchState {
124 final Op op;
125 final List<Value> matchedOperands;
126
127 MatchState(Op op, List<Value> matchedOperands) {
128 this.op = op;
129 this.matchedOperands = matchedOperands;
130 }
131
132 /**
133 * {@return the matched operation}
134 */
135 public Op op() {
136 return op;
137 }
138
139 /**
140 * {@return the matched operands}
141 */
142 public List<Value> matchedOperands() {
143 return matchedOperands;
144 }
145 }
146
147 record PatternAndFunction<R>(OpPattern p, BiFunction<MatchState, R, R> f) {
148 }
149
150 // Visiting op pattern matcher
151 static class OpPatternMatcher<R> implements BiFunction<R, Op, R> {
152 final List<PatternAndFunction<R>> patterns;
153 final PatternState state;
154 final Map<MatchState, BiFunction<MatchState, R, R>> matches;
155
156 OpPatternMatcher(OpPattern p, BiFunction<MatchState, R, R> f) {
157 this(List.of(new PatternAndFunction<>(p, f)));
158 }
159
160 OpPatternMatcher(List<PatternAndFunction<R>> patterns) {
161 this.patterns = patterns;
162 this.state = new PatternState();
163 this.matches = new HashMap<>();
164 }
165
166 @Override
167 public R apply(R r, Op op) {
168 for (PatternAndFunction<R> pf : patterns) {
169 if (pf.p.match(op, state)) {
170 MatchState ms = new MatchState(op, state.resetOnMatch());
171
172 r = pf.f.apply(ms, r);
173 } else {
174 state.resetOnNoMatch();
175 }
176 }
177
178 return r;
179 }
180 }
181
182 /**
183 * A match builder for declaring matching for one or more groups of operation patterns against a given traversable
184 * and descendant operations (in order).
185 * @param <R> the match result type
186 */
187 public static final class MultiMatchBuilder<R> {
188 final CodeElement<?, ?> o;
189 final R r;
190 List<PatternAndFunction<R>> patterns;
191
192 MultiMatchBuilder(CodeElement<?, ?> o, R r) {
193 this.o = o;
194 this.r = r;
195 this.patterns = new ArrayList<>();
196 }
197
198 /**
199 * Declares a first of possibly other operation patterns in a group.
200 *
201 * @param p the operation pattern
202 * @return a builder to declare further patterns in the group.
203 */
204 public MultiMatchCaseBuilder pattern(OpPattern p) {
205 return new MultiMatchCaseBuilder(p);
206 }
207
208 public R matchThenApply() {
209 OpPatternMatcher<R> opm = new OpPatternMatcher<>(patterns);
210 return o.traverse(r, CodeElement.opVisitor(opm));
211 }
212
213 /**
214 * A builder to declare further operation patterns in a group or to associate a
215 * target function to be applied if any of the patterns in the group match.
216 */
217 public final class MultiMatchCaseBuilder {
218 List<OpPattern> patterns;
219
220 MultiMatchCaseBuilder(OpPattern p) {
221 this.patterns = new ArrayList<>();
222 patterns.add(p);
223 }
224
225 /**
226 * Declares an operation pattern in the group.
227 *
228 * @param p the operation pattern
229 * @return this builder.
230 */
231 public MultiMatchCaseBuilder pattern(OpPattern p) {
232 patterns.add(p);
233 return this;
234 }
235
236 /**
237 * Declares the target function to be applied if any of the operation patterns on the group match.
238 *
239 * @param f the target function.
240 * @return the match builder to build further groups.
241 */
242 public MultiMatchBuilder<R> target(BiFunction<MatchState, R, R> f) {
243 patterns.stream().map(p -> new PatternAndFunction<>(p, f)).forEach(MultiMatchBuilder.this.patterns::add);
244 return MultiMatchBuilder.this;
245 }
246 }
247 }
248
249 /**
250 * Constructs a match builder from which to declare matching for one or more groups of operation patterns against a
251 * given traversable and descendant operations (in order).
252 *
253 * @param r the initial match result
254 * @param t the traversable
255 * @param <R> the match result type
256 * @return the match builder
257 */
258 public static <R> MultiMatchBuilder<R> multiMatch(R r, CodeElement<?, ?> t) {
259 return new MultiMatchBuilder<>(t, r);
260 }
261
262 /**
263 * Matches an operation pattern against the given traversable and descendant operations (in order).
264 *
265 * @param r the initial match result
266 * @param t the traversable
267 * @param opPattern the operation pattern
268 * @param matcher the function to be applied with a match state and the current match result when an
269 * encountered operation matches the operation pattern
270 * @param <R> the match result type
271 * @return the match result
272 */
273 public static <R> R match(R r, CodeElement<?, ?> t, OpPattern opPattern,
274 BiFunction<MatchState, R, R> matcher) {
275 OpPatternMatcher<R> opm = new OpPatternMatcher<>(opPattern, matcher);
276 return t.traverse(r, CodeElement.opVisitor(opm));
277 }
278
279
280 // Pattern classes
281
282 static final class PatternState {
283 List<Value> matchedOperands;
284
285 void addOperand(Value v) {
286 if (matchedOperands == null) {
287 matchedOperands = new ArrayList<>();
288 }
289 matchedOperands.add(v);
290 }
291
292 List<Value> resetOnMatch() {
293 if (matchedOperands != null) {
294 List<Value> r = matchedOperands;
295 matchedOperands = null;
296 return r;
297 } else {
298 return List.of();
299 }
300 }
301
302 void resetOnNoMatch() {
303 if (matchedOperands != null) {
304 matchedOperands.clear();
305 }
306 }
307 }
308
309 /**
310 * A pattern matching against a value or operation.
311 */
312 public sealed static abstract class Pattern {
313 Pattern() {
314 }
315
316 abstract boolean match(Value v, PatternState state);
317 }
318
319 /**
320 * A pattern matching against an operation.
321 */
322 public static final class OpPattern extends Pattern {
323 final Predicate<Op> opTest;
324 final List<Pattern> operandPatterns;
325
326 OpPattern(Predicate<Op> opTest, List<Pattern> operandPatterns) {
327 this.opTest = opTest;
328 this.operandPatterns = List.copyOf(operandPatterns);
329 }
330
331 @Override
332 boolean match(Value v, PatternState state) {
333 if (v instanceof Op.Result or) {
334 return match(or.op(), state);
335 } else {
336 return false;
337 }
338 }
339
340 boolean match(Op op, PatternState state) {
341 // Test does not match
342 if (!opTest.test(op)) {
343 return false;
344 }
345
346 if (!operandPatterns.isEmpty()) {
347 // Arity does not match
348 if (op.operands().size() != operandPatterns.size()) {
349 return false;
350 }
351
352 // Match all arguments
353 for (int i = 0; i < operandPatterns.size(); i++) {
354 Pattern p = operandPatterns.get(i);
355 Value v = op.operands().get(i);
356
357 if (!p.match(v, state)) {
358 return false;
359 }
360 }
361 }
362
363 return true;
364 }
365 }
366
367 /**
368 * A pattern that unconditionally matches a value which is captured. If the value is an operation result of an
369 * operation, then an operation pattern (if any) is further matched against the operation.
370 */
371 // @@@ type?
372 static final class ValuePattern extends Pattern {
373 final OpPattern opMatcher;
374
375 ValuePattern() {
376 this(null);
377 }
378
379 public ValuePattern(OpPattern opMatcher) {
380 this.opMatcher = opMatcher;
381 }
382
383 @Override
384 boolean match(Value v, PatternState state) {
385 // Capture the operand
386 state.addOperand(v);
387
388 // Match on operation on nested pattern, if any
389 return opMatcher == null || opMatcher.match(v, state);
390 }
391 }
392
393 /**
394 * A pattern that conditionally matches an operation result which is captured, then an operation pattern (if any)
395 * is further matched against the result's operation.
396 */
397 static final class OpResultPattern extends Pattern {
398 final OpPattern opMatcher;
399
400 OpResultPattern() {
401 this(null);
402 }
403
404 public OpResultPattern(OpPattern opMatcher) {
405 this.opMatcher = opMatcher;
406 }
407
408 @Override
409 boolean match(Value v, PatternState state) {
410 if (!(v instanceof Op.Result)) {
411 return false;
412 }
413
414 // Capture the operand
415 state.addOperand(v);
416
417 // Match on operation on nested pattern, if any
418 return opMatcher == null || opMatcher.match(v, state);
419 }
420 }
421
422 /**
423 * A pattern that conditionally matches a block parameter which is captured.
424 */
425 static final class BlockParameterPattern extends Pattern {
426 BlockParameterPattern() {
427 }
428
429 @Override
430 boolean match(Value v, PatternState state) {
431 if (!(v instanceof Block.Parameter)) {
432 return false;
433 }
434
435 // Capture the operand
436 state.addOperand(v);
437
438 return true;
439 }
440 }
441
442 /**
443 * A pattern matching any value or operation.
444 */
445 static final class AnyPattern extends Pattern {
446 AnyPattern() {
447 }
448
449 @Override
450 boolean match(Value v, PatternState state) {
451 return true;
452 }
453 }
454
455
456 // Pattern factories
457
458 /**
459 * Creates an operation pattern that tests against an operation by applying it to the predicate, and if
460 * {@code true}, matches operand patterns against the operation's operands (in order) .
461 * This operation pattern matches an operation if the test returns {@code true} and all operand patterns match
462 * against the operation's operands.
463 *
464 * @param opTest the predicate
465 * @param patterns the operand patterns
466 * @return the operation pattern
467 */
468 public static OpPattern opP(Predicate<Op> opTest, Pattern... patterns) {
469 return opP(opTest, List.of(patterns));
470 }
471
472 /**
473 * Creates an operation pattern that tests against an operation by applying it to the predicate, and if
474 * {@code true}, matches operand patterns against the operation's operands (in order) .
475 * This operation pattern matches an operation if the test returns {@code true} and all operand patterns match
476 * against the operation's operands.
477 *
478 * @param opTest the predicate
479 * @param patterns the operand patterns
480 * @return the operation pattern
481 */
482 public static OpPattern opP(Predicate<Op> opTest, List<Pattern> patterns) {
483 return new OpPattern(opTest, patterns);
484 }
485
486 /**
487 * Creates an operation pattern that tests if the operation is an instance of the class, and if
488 * {@code true}, matches operand patterns against the operation's operands (in order) .
489 * This operation pattern matches an operation if the test returns {@code true} and all operand patterns match
490 * against the operation's operands.
491 *
492 * @param opClass the operation class
493 * @param patterns the operand patterns
494 * @return the operation pattern
495 */
496 public static OpPattern opP(Class<?> opClass, Pattern... patterns) {
497 return opP(opClass::isInstance, patterns);
498 }
499
500 /**
501 * Creates an operation pattern that tests if the operation is a {@link CoreOp.ConstantOp constant} operation
502 * and whose constant value is equal to the given value.
503 * This operation pattern matches an operation if the test returns {@code true}.
504 *
505 * @param value the value
506 * @return the operation pattern.
507 */
508 public static OpPattern constantP(Object value) {
509 return opP(op -> {
510 if (op instanceof CoreOp.ConstantOp cop) {
511 return Objects.equals(value, cop.value());
512 }
513
514 return false;
515 });
516 }
517
518 /**
519 * Creates a value pattern that unconditionally matches any value and captures the value in match state.
520 *
521 * @return the value pattern.
522 */
523 public static Pattern valueP() {
524 return new ValuePattern();
525 }
526
527 /**
528 * Creates a value pattern that unconditionally matches any value and captures the value in match state, and
529 * if the value is an operation result of an operation, then the operation pattern is matched against that
530 * operation.
531 * This value pattern matches value if value is not an operation result, or otherwise matches if the operation
532 * pattern matches.
533 *
534 * @param opMatcher the operation pattern
535 * @return the value pattern.
536 */
537 public static Pattern valueP(OpPattern opMatcher) {
538 return new ValuePattern(opMatcher);
539 }
540
541 /**
542 * Creates an operation result pattern that conditionally matches an operation result and captures it in match state.
543 *
544 * @return the operation result.
545 */
546 public static Pattern opResultP() {
547 return new OpResultPattern();
548 }
549
550 /**
551 * Creates an operation result pattern that conditionally matches an operation result and captures it in match state,
552 * then the operation pattern is matched against the result's operation.
553 *
554 * @param opMatcher the operation pattern
555 * @return the operation result.
556 */
557 public static Pattern opResultP(OpPattern opMatcher) {
558 return new OpResultPattern(opMatcher);
559 }
560
561 /**
562 * Creates a block parameter result pattern that conditionally matches a block parameter and captures it in match state.
563 *
564 * @return the block parameter.
565 */
566 public static Pattern blockParameterP() {
567 return new BlockParameterPattern();
568 }
569
570 /**
571 * Creates a pattern that unconditionally matches any value or operation.
572 *
573 * @return the value pattern.
574 */
575 public static Pattern _P() {
576 return new AnyPattern();
577 }
578 }