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 }