1 /*
  2  * Copyright (c) 2024, 2025, 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 import java.lang.invoke.MethodHandles;
 25 import jdk.incubator.code.*;
 26 import jdk.incubator.code.dialect.core.CoreOp;
 27 import jdk.incubator.code.dialect.java.JavaOp;
 28 import jdk.incubator.code.dialect.java.JavaType;
 29 import jdk.incubator.code.dialect.java.MethodRef;
 30 import jdk.incubator.code.extern.OpWriter;
 31 
 32 import java.util.ArrayList;
 33 import java.util.Collections;
 34 import java.util.HashMap;
 35 import java.util.List;
 36 import java.util.Map;
 37 
 38 public final class Verifier {
 39 
 40     public final class VerifyError {
 41 
 42         private final String message;
 43 
 44         public VerifyError(String message) {
 45             this.message = message;
 46         }
 47 
 48         public String getMessage() {
 49             return message;
 50         }
 51 
 52         public String getPrintedContext() {
 53             return toText(rootOp);
 54         }
 55 
 56         @Override
 57         public String toString() {
 58             return getMessage() + " in " + getPrintedContext();
 59         }
 60     }
 61 
 62     public static List<Verifier.VerifyError> verify(Op op) {
 63         return verify(MethodHandles.publicLookup(), op);
 64     }
 65 
 66     public static List<Verifier.VerifyError> verify(MethodHandles.Lookup l, Op op) {
 67         var verifier = new Verifier(l, op);
 68         verifier.verifyOps();
 69         verifier.verifyExceptionRegions();
 70         return verifier.errors == null ? List.of() : Collections.unmodifiableList(verifier.errors);
 71     }
 72 
 73 
 74     private final MethodHandles.Lookup lookup;
 75     private final Op rootOp;
 76     private OpWriter.CodeItemNamerOption namerOption;
 77     private List<Verifier.VerifyError> errors;
 78 
 79     private Verifier(MethodHandles.Lookup lookup, Op rootOp) {
 80         this.lookup = lookup;
 81         this.rootOp = rootOp;
 82     }
 83 
 84     private OpWriter.CodeItemNamerOption getNamer() {
 85         if (namerOption == null) {
 86             namerOption = OpWriter.CodeItemNamerOption.of(OpWriter.computeGlobalNames(rootOp));
 87         }
 88         return namerOption;
 89     }
 90 
 91     private String toText(Op op) {
 92         return OpWriter.toText(op, getNamer());
 93     }
 94 
 95     private String getName(CodeItem codeItem) {
 96         return getNamer().namer().apply(codeItem);
 97     }
 98 
 99     private void error(String message, Object... args) {
100         if (errors == null) {
101             errors = new ArrayList<>();
102         }
103         for (int i = 0; i < args.length; i++) {
104             args[i] = toText(args[i]);
105         }
106         errors.add(new VerifyError(message.formatted(args)));
107     }
108 
109     private String toText(Object arg) {
110         return switch (arg) {
111             case Op op -> toText(op);
112             case Block b -> getName(b);
113             case Value v -> getName(v);
114             case List<?> l -> l.stream().map(this::toText).toList().toString();
115             default -> arg.toString();
116         };
117     }
118 
119     private void verifyOps() {
120         rootOp.traverse(null, CodeElement.opVisitor((_, op) -> {
121             // Verify operands declaration dominannce
122             for (var v : op.operands()) {
123                 if (!op.result().isDominatedBy(v)) {
124                     error("%s %s operand %s is not dominated by its declaration in %s", op.parentBlock(), op, v, v.declaringBlock());
125                 }
126             }
127 
128             // Verify individual Ops
129             switch (op) {
130                 case CoreOp.BranchOp br ->
131                     verifyBlockReferences(op, br.successors());
132                 case CoreOp.ConditionalBranchOp cbr ->
133                     verifyBlockReferences(op, cbr.successors());
134                 case JavaOp.ArithmeticOperation _, JavaOp.TestOperation _ ->
135                     verifyOpHandleExists(op, op.opName());
136                 case JavaOp.ConvOp _ -> {
137                     verifyOpHandleExists(op, op.opName() + "_" + op.opType().returnType());
138                 }
139                 default -> {}
140 
141             }
142             return null;
143         }));
144     }
145 
146     private void verifyBlockReferences(Op op, List<Block.Reference> references) {
147         for (Block.Reference r : references) {
148             Block b = r.targetBlock();
149             List<Value> args = r.arguments();
150             List<Block.Parameter> params = r.targetBlock().parameters();
151             if (args.size() != params.size()) {
152                 error("%s %s block reference arguments size to target block parameters size mismatch", b, op);
153             } else {
154                 Block tb = r.targetBlock();
155                 for (int i = 0; i < args.size(); i++) {
156                     if (!isAssignable(params.get(i).type(), args.get(i), tb, b)) {
157                         error("%s %s %s is not assignable from %s", op.parentBlock(), op, params.get(i).type(), args.get(i).type());
158                     }
159                 }
160             }
161         }
162     }
163 
164     private boolean isAssignable(TypeElement toType, Value fromValue,  Object toContext, Object fromContext) {
165         if (toType.equals(fromValue.type())) return true;
166         var to = resolveToClass(toType, toContext);
167         var from = resolveToClass(fromValue.type(), fromContext);
168         if (from.isPrimitive()) {
169             // Primitive types assignability
170             return to == int.class && (from == byte.class || from == short.class || from == char.class);
171         } else {
172             // Objects assignability
173             return to.isAssignableFrom(from);
174         }
175     }
176 
177     public Class<?> resolveToClass(TypeElement d, Object context) {
178         try {
179             if (d instanceof JavaType jt) {
180                 return (Class<?>)jt.erasure().resolve(lookup);
181             } else {
182                 error("%s %s is not a Java type", context, d);
183             }
184         } catch (ReflectiveOperationException e) {
185             error("%s %s", context, e.getMessage());
186         }
187         return Object.class;
188     }
189 
190     static final Class<?> CLASS_INVOKABLE_LEAF_OPS;
191     static {
192         try {
193             CLASS_INVOKABLE_LEAF_OPS = Class.forName("jdk.incubator.code.interpreter.InvokableLeafOps");
194         } catch (ReflectiveOperationException roe) {
195             throw new InternalError(roe);
196         }
197     }
198 
199     private void verifyOpHandleExists(Op op, String opName) {
200         try {
201             var mt = MethodRef.toNominalDescriptor(op.opType()).resolveConstantDesc(lookup).erase();
202             CLASS_INVOKABLE_LEAF_OPS.getDeclaredMethod(opName, mt.parameterArray());
203         } catch (NoSuchMethodException nsme) {
204             error("%s %s of type %s is not supported", op.parentBlock(), op, op.opType());
205         } catch (ReflectiveOperationException roe) {
206             error("%s %s %s",  op.parentBlock(), op, roe.getMessage());
207         }
208     }
209 
210     private void verifyExceptionRegions() {
211         rootOp.traverse(new HashMap<Block, List<Block>>(), CodeElement.blockVisitor((map, b) -> {
212             List<Block> catchBlocks = map.computeIfAbsent(b, _ -> List.of());
213             switch (b.terminatingOp()) {
214                 case CoreOp.BranchOp br ->
215                     verifyCatchStack(b, br, br.branch(), catchBlocks, map);
216                 case CoreOp.ConditionalBranchOp cbr -> {
217                     verifyCatchStack(b, cbr, cbr.trueBranch(), catchBlocks, map);
218                     verifyCatchStack(b, cbr, cbr.falseBranch(), catchBlocks, map);
219                 }
220                 case JavaOp.ExceptionRegionEnter ere -> {
221                     List<Block> newCatchBlocks = new ArrayList<>();
222                     newCatchBlocks.addAll(catchBlocks);
223                     for (Block.Reference cb : ere.catchBlocks()) {
224                         newCatchBlocks.add(cb.targetBlock());
225                         verifyCatchStack(b, ere, cb, catchBlocks, map);
226                     }
227                     verifyCatchStack(b, ere, ere.start(), newCatchBlocks, map);
228                 }
229                 case JavaOp.ExceptionRegionExit ere -> {
230                     List<Block> exitedCatchBlocks = ere.catchBlocks().stream().map(Block.Reference::targetBlock).toList();
231                     if (exitedCatchBlocks.size() > catchBlocks.size() || !catchBlocks.reversed().subList(0, exitedCatchBlocks.size()).equals(exitedCatchBlocks)) {
232                         error("%s %s exited catch blocks %s does not match actual stack %s", b, ere, exitedCatchBlocks, catchBlocks);
233                     } else {
234                         verifyCatchStack(b, ere, ere.end(), catchBlocks.subList(0, catchBlocks.size() - exitedCatchBlocks.size()), map);
235                     }
236                 }
237                 default -> {}
238             }
239             return map;
240         }));
241     }
242 
243     private void verifyCatchStack(Block b, Op op, Block.Reference target, List<Block> catchBlocks, Map<Block, List<Block>> blockMap) {
244         blockMap.compute(target.targetBlock(), (tb, stored) -> {
245             if (stored != null && !stored.equals(catchBlocks)) {
246                 error("%s %s catch stack mismatch at target %s %s vs %s", b, op, tb, stored, catchBlocks);
247             }
248             return catchBlocks;
249         });
250     }
251 }