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 java.lang.reflect.code.Block;
 25 import java.lang.reflect.code.Op;
 26 import java.lang.reflect.code.Value;
 27 import java.lang.reflect.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 }