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.
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 jdk.incubator.code.Block;
25 import jdk.incubator.code.Op;
26 import jdk.incubator.code.Value;
27 import jdk.incubator.code.op.CoreOp;
28 import java.util.*;
29
30 public final class ActiveSet {
31
32 private ActiveSet() {
33 }
34
35 // Create active value set, in order, starting from the given block parameter
36 // following its users and following through block arguments
37 // to block parameters, and so on until the graph is traversed.
38
39 public static Set<Value> activeSet(CoreOp.FuncOp f, Block.Parameter fv) {
40 if (!f.body().blocks().get(0).parameters().contains(fv)) {
41 throw new IllegalArgumentException("Arg is not defined by function");
42 }
43 Deque<Value> q = new ArrayDeque<>();
44 q.push(fv);
45
46 Set<Value> active = new TreeSet<>();
47 while (!q.isEmpty()) {
48 Value v = q.pop();
49 if (active.contains(v)) {
50 continue;
51 }
52 active.add(v);
53
54 // @@@ assume uses are declared in order?
55 // if so can push to queue in reverse order
56 for (Op.Result or : v.uses()) {
57 q.push(or);
58 Op op = or.op();
59
60 if (op instanceof Op.Terminating) {
61 for (Block.Reference s : op.successors()) {
62 for (int i = 0; i < s.arguments().size(); i++) {
63 if (v == s.arguments().get(i)) {
64 Block b = s.targetBlock();
65 Block.Parameter ba = b.parameters().get(i);
66
67 // Processing of block arguments may result in out of order
68 // production of uses if two or more block arguments are added
69 // for the same successor argument
70 q.push(ba);
71 }
72 }
73 }
74 }
75 }
76 }
77
78 // Ensure non-active block arguments of successors are added to the
79 // active set for blocks with corresponding active parameters
80 // Backtracking is not performed on the values as they are not strictly
81 // active set but may be required for initialization purposes.
82 Set<Value> bactive = new LinkedHashSet<>();
83 for (Value v : active) {
84 if (v instanceof Block.Parameter ba) {
85 Block b = ba.declaringBlock();
86 int i = b.parameters().indexOf(ba);
87
88 for (Block p : b.predecessors()) {
89 Op to = p.terminatingOp();
90 for (Block.Reference s : to.successors()) {
91 if (s.targetBlock() == b) {
92 Value arg = s.arguments().get(i);
93 if (!active.contains(arg)) {
94 bactive.add(arg);
95 bactive.add(to.result());
96 }
97 }
98 }
99 }
100 }
101 }
102 active.addAll(bactive);
103
104 return active;
105 }
106 }