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 the values this value directly depends on.
77 * <p>
78 * An operation result depends on the set of values whose members are the operation's operands and block arguments
79 * of the operation's successors.
80 * A block parameter does not depend on any values.
81 *
82 * @return the values this value directly depends on, as an unmodifiable set.
83 */
84 // @@@ Consider an additional method that returns a lazy stream of all dependent values, in order.
85 public abstract Set<Value> dependsOn();
86
87 /**
88 * Returns the uses of this value, specifically each operation result of an operation where this value is used as
89 * an operand or as an argument of a block reference that is a successor.
90 *
91 * @return the uses of this value, as an unmodifiable set.
92 * @throws IllegalStateException if the declaring block is partially built
93 */
94 // @@@ Consider an additional method that returns a lazy stream of all uses, in order.
95 public Set<Op.Result> uses() {
96 if (!isBound()) {
97 throw new IllegalStateException("Users are partially constructed");
98 }
99
100 return Collections.unmodifiableSet(uses);
101 }
102
103 /**
104 * Returns {@code true} if this value is dominated by the given value {@code dom}.
105 * <p>
106 * If {@code v} and {@code dom} are in not declared in the same block then, domination is the result of
107 * if the declaring block of {@code v} is dominated by the declaring block of {@code dom}.
108 * <p>
109 * Otherwise, if {@code v} and {@code dom} are declared in the same block then (in order):
110 * <ul>
111 * <li>if {@code dom} is a block parameter, then {@code v} is dominated by {@code dom}.
112 * <li>if {@code v} is a block parameter, then {@code v} is <b>not</b> dominated by {@code dom}.
113 * <li>otherwise, both {@code v} and {@code dom} are operation results, then {@code v} is dominated by {@code dom}
114 * if {@code v} is the same as {@code dom} or {@code v} occurs after {@code dom} in the declaring block.
115 * </ul>
116 *
117 * @param dom the dominating value
118 * @return {@code true} if this value is dominated by the given value {@code dom}.
119 * @throws IllegalStateException if the declaring block is partially built
120 */
121 public boolean isDominatedBy(Value dom) {
122 if (this == dom) {
123 return true;
124 }
125
126 if (declaringBlock() != dom.declaringBlock()) {
127 return declaringBlock().isDominatedBy(dom.declaringBlock());
128 }
129
130 // Any value is dominated by a block parameter
131 if (dom instanceof Block.Parameter) {
132 return true;
133 } else if (this instanceof Block.Parameter) {
134 return false;
135 } else {
136 assert this instanceof Op.Result &&
137 dom instanceof Op.Result;
138 List<Op> ops = declaringBlock().ops();
139 return ops.indexOf(((Op.Result) this).op()) >= ops.indexOf(((Op.Result) dom).op());
140 }
141 }
142
143
144 @Override
145 public int compareTo(Value o) {
146 return compare(this, o);
147 }
148
149 // @@@
150 public static int compare(Value v1, Value v2) {
151 if (v1 == v2) return 0;
152
153 Block b1 = v1.declaringBlock();
154 Block b2 = v2.declaringBlock();
155 if (b1 == b2) {
156 if (v1 instanceof Op.Result or1 && v2 instanceof Op.Result or2) {
157 List<Op> ops = b1.ops();
158 return Integer.compare(ops.indexOf(or1.op()), ops.indexOf(or2.op()));
159 } else if (v1 instanceof Op.Result) {
160 // v2 instanceof BlockParameter
161 return 1;
162 } else if (v2 instanceof Op.Result) {
163 // v1 instanceof BlockParameter
164 return -1;
165 } else { // v1 && v2 instanceof BlockParameter
166 assert v1 instanceof Block.Parameter && v2 instanceof Block.Parameter;
167 List<Block.Parameter> args = b1.parameters();
168 return Integer.compare(args.indexOf(v1), args.indexOf(v2));
169 }
170 }
171
172 Body r1 = b1.ancestorBody();
173 Body r2 = b2.ancestorBody();
174 if (r1 == r2) {
175 // @@@ order should be defined by CFG and dominator relations
176 List<Block> bs = r1.blocks();
177 return Integer.compare(bs.indexOf(b1), bs.indexOf(b2));
178 }
179
180 Op o1 = r1.ancestorOp();
181 Op o2 = r2.ancestorOp();
182 if (o1 == o2) {
183 List<Body> rs = o1.bodies();
184 return Integer.compare(rs.indexOf(r1), rs.indexOf(r2));
185 }
186
187 return compare(o1.result(), o2.result());
188 }
189
190 boolean isBound() {
191 return block.isBound();
192 }
193 }