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;
27
28 import java.util.Collections;
29 import java.util.LinkedHashSet;
30 import java.util.List;
31 import java.util.Set;
32
33 /**
34 * A value, that is the result of an operation or a block parameter.
35 * @sealedGraph
36 */
37 public sealed abstract class Value implements Comparable<Value>, CodeItem
38 permits Block.Parameter, Op.Result {
39 final Block block;
40 final TypeElement type;
41 // @@@ In topological order?
42 // Can the representation be more efficient e.g. an array?
43 final Set<Op.Result> uses;
44
45 Value(Block block, TypeElement type) {
46 this.block = block;
47 this.type = type;
48 this.uses = new LinkedHashSet<>();
49 }
50
51 /**
52 * Returns this value's declaring block.
53 * <p>If the value is an operation result, then the declaring block is the operation's parent block.
54 * If the value is a block parameter then the declaring block is the block declaring the parameter.
55 *
56 * @return the value's declaring block.
57 * @throws IllegalStateException if the declaring block is partially built
58 */
59 public Block declaringBlock() {
60 if (!isBound()) {
61 throw new IllegalStateException("Declaring block is partially constructed");
62 }
63 return block;
64 }
65
66 /**
67 * Returns the type of the value.
68 *
69 * @return the type of the value.
70 */
71 public TypeElement type() {
72 return type;
73 }
74
75 /**
76 * Returns this value as an operation result.
77 *
78 * @return the value as an operation result.
79 * @throws IllegalStateException if the value is not an instance of an operation result.
80 */
81 public Op.Result result() {
82 if (this instanceof Op.Result r) {
83 return r;
84 }
85 throw new IllegalStateException("Value is not an instance of operation result");
86 }
87
88 /**
89 * Returns this value as a block parameter.
90 *
91 * @return the value as a block parameter.
92 * @throws IllegalStateException if the value is not an instance of a block parameter.
93 */
94 public Block.Parameter parameter() {
95 if (this instanceof Block.Parameter p) {
96 return p;
97 }
98 throw new IllegalStateException("Value is not an instance of block parameter");
99 }
100
101 /**
102 * Returns the values this value directly depends on.
103 * <p>
104 * An operation result depends on the set of values whose members are the operation's operands and block arguments
105 * of the operation's successors.
106 * A block parameter does not depend on any values.
107 *
108 * @return the values this value directly depends on, as an unmodifiable set.
109 */
110 // @@@ Consider an additional method that returns a lazy stream of all dependent values, in order.
111 public abstract Set<Value> dependsOn();
112
113 /**
114 * Returns the uses of this value, specifically each operation result of an operation where this value is used as
115 * an operand or as an argument of a block reference that is a successor.
116 *
117 * @return the uses of this value, as an unmodifiable set.
118 * @throws IllegalStateException if the declaring block is partially built
119 */
120 // @@@ Consider an additional method that returns a lazy stream of all uses, in order.
121 public Set<Op.Result> uses() {
122 if (!isBound()) {
123 throw new IllegalStateException("Users are partially constructed");
124 }
125
126 return Collections.unmodifiableSet(uses);
127 }
128
129 /**
130 * Returns {@code true} if this value is dominated by the given value {@code dom}.
131 * <p>
132 * If {@code v} and {@code dom} are in not declared in the same block then, domination is the result of
133 * if the declaring block of {@code v} is dominated by the declaring block of {@code dom}.
134 * <p>
135 * Otherwise, if {@code v} and {@code dom} are declared in the same block then (in order):
136 * <ul>
137 * <li>if {@code dom} is a block parameter, then {@code v} is dominated by {@code dom}.
138 * <li>if {@code v} is a block parameter, then {@code v} is <b>not</b> dominated by {@code dom}.
139 * <li>otherwise, both {@code v} and {@code dom} are operation results, then {@code v} is dominated by {@code dom}
140 * if {@code v} is the same as {@code dom} or {@code v} occurs after {@code dom} in the declaring block.
141 * </ul>
142 *
143 * @param dom the dominating value
144 * @return {@code true} if this value is dominated by the given value {@code dom}.
145 * @throws IllegalStateException if the declaring block is partially built
146 */
147 public boolean isDominatedBy(Value dom) {
148 if (this == dom) {
149 return true;
150 }
151
152 if (declaringBlock() != dom.declaringBlock()) {
153 return declaringBlock().isDominatedBy(dom.declaringBlock());
154 }
155
156 // Any value is dominated by a block parameter
157 if (dom instanceof Block.Parameter) {
158 return true;
159 } else if (this instanceof Block.Parameter) {
160 return false;
161 } else {
162 assert this instanceof Op.Result &&
163 dom instanceof Op.Result;
164 List<Op> ops = declaringBlock().ops();
165 return ops.indexOf(((Op.Result) this).op()) >= ops.indexOf(((Op.Result) dom).op());
166 }
167 }
168
169
170 @Override
171 public int compareTo(Value o) {
172 return compare(this, o);
173 }
174
175 // @@@
176 public static int compare(Value v1, Value v2) {
177 if (v1 == v2) return 0;
178
179 Block b1 = v1.declaringBlock();
180 Block b2 = v2.declaringBlock();
181 if (b1 == b2) {
182 if (v1 instanceof Op.Result or1 && v2 instanceof Op.Result or2) {
183 List<Op> ops = b1.ops();
184 return Integer.compare(ops.indexOf(or1.op()), ops.indexOf(or2.op()));
185 } else if (v1 instanceof Op.Result) {
186 // v2 instanceof BlockParameter
187 return 1;
188 } else if (v2 instanceof Op.Result) {
189 // v1 instanceof BlockParameter
190 return -1;
191 } else { // v1 && v2 instanceof BlockParameter
192 assert v1 instanceof Block.Parameter && v2 instanceof Block.Parameter;
193 List<Block.Parameter> args = b1.parameters();
194 return Integer.compare(args.indexOf(v1), args.indexOf(v2));
195 }
196 }
197
198 Body r1 = b1.ancestorBody();
199 Body r2 = b2.ancestorBody();
200 if (r1 == r2) {
201 // @@@ order should be defined by CFG and dominator relations
202 List<Block> bs = r1.blocks();
203 return Integer.compare(bs.indexOf(b1), bs.indexOf(b2));
204 }
205
206 Op o1 = r1.ancestorOp();
207 Op o2 = r2.ancestorOp();
208 if (o1 == o2) {
209 List<Body> rs = o1.bodies();
210 return Integer.compare(rs.indexOf(r1), rs.indexOf(r2));
211 }
212
213 return compare(o1.result(), o2.result());
214 }
215
216 boolean isBound() {
217 return block.isBound();
218 }
219 }