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