1 /*
   2  * Copyright (c) 2015, 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 package jdk.tools.jlink.internal.plugins.optim;
  26 
  27 import java.util.ArrayList;
  28 import java.util.Collection;
  29 import java.util.Collections;
  30 import java.util.HashMap;
  31 import java.util.HashSet;
  32 import java.util.Iterator;
  33 import java.util.List;
  34 import java.util.Map;
  35 import java.util.Map.Entry;
  36 import java.util.Objects;
  37 import java.util.Set;
  38 import java.util.Stack;
  39 import java.util.TreeSet;
  40 import jdk.internal.org.objectweb.asm.tree.AbstractInsnNode;
  41 import jdk.internal.org.objectweb.asm.tree.MethodNode;
  42 import jdk.internal.org.objectweb.asm.tree.analysis.Analyzer;
  43 import jdk.internal.org.objectweb.asm.tree.analysis.AnalyzerException;
  44 import jdk.internal.org.objectweb.asm.tree.analysis.BasicInterpreter;
  45 import jdk.internal.org.objectweb.asm.tree.analysis.BasicValue;
  46 
  47 /**
  48  * Split Java method onto a control flow.
  49  *
  50  */
  51 public final class ControlFlow {
  52 
  53     /**
  54      * A block of control
  55      */
  56     public static final class Block implements Comparable<Block> {
  57 
  58         private final InstructionNode firstInstruction;
  59         private final List<InstructionNode> instr = new ArrayList<>();
  60         private final List<Block> reachable = new ArrayList<>();
  61         private final List<Block> exceptionHandlers = new ArrayList<>();
  62         private boolean isExceptionHandler;
  63 
  64         private Block(InstructionNode firstInstruction) {
  65             this.firstInstruction = firstInstruction;
  66         }
  67 
  68         @Override
  69         public boolean equals(Object other) {
  70             if (!(other instanceof Block)) {
  71                 return false;
  72             }
  73             Block b = (Block) other;
  74             return firstInstruction.equals(b.firstInstruction);
  75         }
  76 
  77         @Override
  78         public int hashCode() {
  79             return Objects.hashCode(this.firstInstruction);
  80         }
  81 
  82         @Override
  83         public String toString() {
  84             StringBuilder builder = new StringBuilder();
  85             for (InstructionNode in : instr) {
  86                 builder.append(in).append(" ");
  87             }
  88             builder.append(" reachables: ");
  89             for (Block r : reachable) {
  90                 builder.append(r.getFirstInstruction()).append(" ");
  91             }
  92             builder.append(" exception handlers: ");
  93             for (Block r : exceptionHandlers) {
  94                 builder.append(r.getFirstInstruction()).append(" ");
  95             }
  96 
  97             return "block[" + getFirstInstruction() + "],ex:"
  98                     + isExceptionHandler + ",  " + builder.toString();
  99         }
 100 
 101         /**
 102          * @return the firstInstruction
 103          */
 104         public InstructionNode getFirstInstruction() {
 105             return firstInstruction;
 106         }
 107 
 108         /**
 109          * @return the instr
 110          */
 111         public List<InstructionNode> getInstructions() {
 112             return Collections.unmodifiableList(instr);
 113         }
 114 
 115         /**
 116          * @return the reachable
 117          */
 118         public List<Block> getReachableBlocks() {
 119             return Collections.unmodifiableList(reachable);
 120         }
 121 
 122         /**
 123          * @return the exceptionHandlers
 124          */
 125         public List<Block> getExceptionHandlerBlocks() {
 126             return Collections.unmodifiableList(exceptionHandlers);
 127         }
 128 
 129         @Override
 130         public int compareTo(Block t) {
 131             return this.firstInstruction.index - t.firstInstruction.index;
 132         }
 133 
 134         public boolean isExceptionHandler() {
 135             return isExceptionHandler;
 136         }
 137 
 138     }
 139 
 140     private class ClosureBuilder {
 141 
 142         private final Block root;
 143 
 144         private ClosureBuilder(Block root) {
 145             Objects.requireNonNull(root);
 146             this.root = root;
 147         }
 148 
 149         private Set<Block> build() {
 150             Set<Block> allReachable = new TreeSet<>();
 151             addAll(root, allReachable);
 152             // filter out the reachable from outside this graph
 153             Iterator<Block> it = allReachable.iterator();
 154             Set<Block> toExclude = new HashSet<>();
 155             while (it.hasNext()) {
 156                 Block b = it.next();
 157                 for (Block ref : blocks) {
 158                     if (!allReachable.contains(ref) && ref.reachable.contains(b)) {
 159                         addAll(b, toExclude);
 160                         break;
 161                     }
 162                 }
 163             }
 164             //System.err.println("TO EXCLUDE:\n " + toExclude);
 165             allReachable.removeAll(toExclude);
 166             //System.err.println("CLOSURE:\n " + allReachable);
 167             return Collections.unmodifiableSet(allReachable);
 168         }
 169 
 170         // Compute the set of blocks reachable from the current block
 171         private void addAll(Block current, Set<Block> closure) {
 172             Objects.requireNonNull(current);
 173             closure.add(current);
 174             for (Block ex : current.exceptionHandlers) {
 175                 Objects.requireNonNull(ex);
 176                 if (!closure.contains(ex)) {
 177                     addAll(ex, closure);
 178                 }
 179             }
 180             for (Block r : current.reachable) {
 181                 Objects.requireNonNull(r);
 182                 if (!closure.contains(r)) {
 183                     addAll(r, closure);
 184                 }
 185             }
 186 
 187         }
 188     }
 189 
 190     /**
 191      * An instruction
 192      */
 193     public static final class InstructionNode {
 194 
 195         private final int index;
 196         private final List<InstructionNode> next = new ArrayList<>();
 197         private final AbstractInsnNode instr;
 198 
 199         private InstructionNode(int index, AbstractInsnNode instr) {
 200             this.index = index;
 201             this.instr = instr;
 202         }
 203 
 204         @Override
 205         public boolean equals(Object obj) {
 206             if (!(obj instanceof InstructionNode)) {
 207                 return false;
 208             }
 209             final InstructionNode other = (InstructionNode) obj;
 210             return this.getIndex() == other.getIndex();
 211         }
 212 
 213         @Override
 214         public int hashCode() {
 215             return this.getIndex();
 216         }
 217 
 218         @Override
 219         public String toString() {
 220             return getIndex() + "(" + (getInstr().getOpcode() == - 1 ? -1
 221                     : Integer.toHexString(getInstr().getOpcode())) + ")";
 222         }
 223 
 224         /**
 225          * @return the index
 226          */
 227         public int getIndex() {
 228             return index;
 229         }
 230 
 231         /**
 232          * @return the instr
 233          */
 234         public AbstractInsnNode getInstr() {
 235             return instr;
 236         }
 237 
 238     }
 239 
 240     private final Map<Integer, Block> allBlocks;
 241     private final List<Block> blocks = new ArrayList<>();
 242 
 243     private ControlFlow(Map<Integer, Block> allBlocks) {
 244         this.allBlocks = allBlocks;
 245         for (Block b : allBlocks.values()) {
 246             blocks.add(b);
 247         }
 248         Collections.sort(blocks);
 249     }
 250 
 251     public List<Block> getBlocks() {
 252 
 253         return Collections.unmodifiableList(blocks);
 254     }
 255 
 256     public Block getBlock(int firstInstr) {
 257         return allBlocks.get(firstInstr);
 258     }
 259 
 260     public static ControlFlow createControlFlow(String owner,
 261             MethodNode method) throws Exception {
 262 
 263         BlockBuilder bb = new BlockBuilder(owner, method);
 264         return bb.build();
 265     }
 266 
 267     /**
 268      * Return the set of blocks that are only reachable from this block For
 269      * example, if b is an Exception handler, returns all the blocks reachable
 270      * only from this handler
 271      *
 272      * @param b
 273      * @return
 274      */
 275     public Set<Block> getClosure(Block b) {
 276         return new ClosureBuilder(b).build();
 277     }
 278 
 279     private static final class BlockBuilder {
 280 
 281         private InstructionNode root;
 282         private final Map<Integer, InstructionNode> instructions = new HashMap<>();
 283         private final Map<Integer, List<Integer>> handlers = new HashMap<>();
 284         private final Map<Integer, Block> allBlocks = new HashMap<>();
 285 
 286         private final String owner;
 287         private final MethodNode method;
 288 
 289         private BlockBuilder(String owner, MethodNode method) {
 290             this.owner = owner;
 291             this.method = method;
 292         }
 293 
 294         private void analyze() throws AnalyzerException {
 295             Analyzer<BasicValue> analyzer = new Analyzer<BasicValue>(new BasicInterpreter()) {
 296 
 297                 @Override
 298                 protected boolean newControlFlowExceptionEdge(int insn,
 299                         int successor) {
 300                     List<Integer> lst = handlers.get(successor);
 301                     if (lst == null) {
 302                         lst = new ArrayList<>();
 303                         handlers.put(successor, lst);
 304                     }
 305                     lst.add(insn);
 306                     return true;
 307                 }
 308 
 309                 @Override
 310                 protected void newControlFlowEdge(int from,
 311                         int to) {
 312                     if (root == null) {
 313                         root = new InstructionNode(from, method.instructions.get(from));
 314                         instructions.put(from, root);
 315                     }
 316                     InstructionNode fromNode = instructions.get(from);
 317                     if (fromNode == null) {
 318                         fromNode = new InstructionNode(from, method.instructions.get(from));
 319                         instructions.put(from, fromNode);
 320                     }
 321                     InstructionNode toNode = instructions.get(to);
 322                     if (toNode == null) {
 323                         toNode = new InstructionNode(to, method.instructions.get(to));
 324                         instructions.put(to, toNode);
 325                     }
 326                     if (!fromNode.next.contains(toNode)) {
 327                         fromNode.next.add(toNode);
 328                     }
 329 
 330                 }
 331             };
 332             analyzer.analyze(owner, method);
 333         }
 334 
 335         private Block newBlock(InstructionNode firstInstruction) {
 336             Objects.requireNonNull(firstInstruction);
 337             Block b = new Block(firstInstruction);
 338             allBlocks.put(firstInstruction.getIndex(), b);
 339             return b;
 340         }
 341 
 342         private ControlFlow build() throws AnalyzerException {
 343             analyze();
 344             buildBlocks();
 345             return new ControlFlow(allBlocks);
 346         }
 347 
 348         private void buildBlocks() {
 349             List<Block> reachableBlocks = new ArrayList<>();
 350             createBlocks(root, reachableBlocks);
 351             List<Block> handlersBlocks = new ArrayList<>();
 352             for (Entry<Integer, List<Integer>> entry : handlers.entrySet()) {
 353                 InstructionNode node = instructions.get(entry.getKey());
 354                 createBlocks(node, handlersBlocks);
 355             }
 356 
 357             // attach handler to try blocks
 358             for (Entry<Integer, List<Integer>> entry : handlers.entrySet()) {
 359                 Block handlerBlock = allBlocks.get(entry.getKey());
 360                 handlerBlock.isExceptionHandler = true;
 361                 int startTry = entry.getValue().get(0);
 362                 Block tryBlock = allBlocks.get(startTry);
 363                 if (tryBlock == null) {
 364                     // Need to find the block that contains the instruction and
 365                     // make a new block
 366                     Block split = null;
 367                     for (Block b : allBlocks.values()) {
 368                         Iterator<InstructionNode> it = b.instr.iterator();
 369                         while (it.hasNext()) {
 370                             InstructionNode in = it.next();
 371                             if (split == null) {
 372                                 if (in.index == startTry) {
 373                                     split = newBlock(in);
 374                                     split.instr.add(in);
 375                                     it.remove();
 376                                 }
 377                             } else {
 378                                 split.instr.add(in);
 379                                 it.remove();
 380                             }
 381                         }
 382                         if (split != null) {
 383                             Iterator<Block> reachables = b.reachable.iterator();
 384                             while (reachables.hasNext()) {
 385                                 Block r = reachables.next();
 386                                 split.reachable.add(r);
 387                                 reachables.remove();
 388                             }
 389                             b.reachable.add(split);
 390                             break;
 391                         }
 392                     }
 393                     if (split == null) {
 394                         throw new RuntimeException("No try block for handler " + handlerBlock);
 395                     }
 396                     split.exceptionHandlers.add(handlerBlock);
 397                 } else {
 398                     tryBlock.exceptionHandlers.add(handlerBlock);
 399                 }
 400             }
 401 
 402 //            System.err.println("ALL BLOCKS FOUND");
 403 //            Iterator<Entry<Integer, Block>> blockIt0 = allBlocks.entrySet().iterator();
 404 //            while (blockIt0.hasNext()) {
 405 //                Block b = blockIt0.next().getValue();
 406 //                System.err.println(b);
 407 //            }
 408             //compute real exception blocks, if an instruction is in another block, stop.
 409             Iterator<Entry<Integer, Block>> blockIt = allBlocks.entrySet().iterator();
 410             while (blockIt.hasNext()) {
 411                 Block b = blockIt.next().getValue();
 412                 Iterator<InstructionNode> in = b.instr.iterator();
 413                 boolean found = false;
 414                 while (in.hasNext()) {
 415                     int i = in.next().getIndex();
 416                     if (found) {
 417                         in.remove();
 418                     } else {
 419                         if (startsWith(b, i, allBlocks.values())) {
 420                             // Move it to reachable
 421                             Block r = allBlocks.get(i);
 422                             b.reachable.add(r);
 423                             found = true;
 424                             in.remove();
 425                         } else {
 426                         }
 427                     }
 428                 }
 429             }
 430 
 431 //            System.err.println("Reduced blocks");
 432 //            Iterator<Entry<Integer, Block>> blockIt1 = allBlocks.entrySet().iterator();
 433 //            while (blockIt1.hasNext()) {
 434 //                Block b = blockIt1.next().getValue();
 435 //                System.err.println(b);
 436 //            }
 437         }
 438 
 439         private boolean startsWith(Block block, int index, Collection<Block> reachableBlocks) {
 440             for (Block b : reachableBlocks) {
 441                 if (b != block && !b.instr.isEmpty() && b.instr.get(0).getIndex() == index) {
 442                     return true;
 443                 }
 444             }
 445             return false;
 446         }
 447 
 448         private static final class StackItem {
 449 
 450             private final InstructionNode instr;
 451             private final Block currentBlock;
 452 
 453             private StackItem(InstructionNode instr, Block currentBlock) {
 454                 Objects.requireNonNull(instr);
 455                 Objects.requireNonNull(currentBlock);
 456                 this.instr = instr;
 457                 this.currentBlock = currentBlock;
 458             }
 459         }
 460 
 461         /**
 462          * This algorithm can't be recursive, possibly too much instructions in
 463          * methods.
 464          */
 465         private void createBlocks(InstructionNode root, List<Block> blocks) {
 466             final Stack<StackItem> stack = new Stack<>();
 467             stack.push(new StackItem(root, newBlock(root)));
 468             while (!stack.isEmpty()) {
 469                 final StackItem item = stack.pop();
 470                 final Block currentBlock = item.currentBlock;
 471                 final InstructionNode current = item.instr;
 472                 // loop
 473                 if (currentBlock.instr.contains(current)) {
 474                     currentBlock.reachable.add(currentBlock);
 475                     continue;
 476                 }
 477                 Block existing = allBlocks.get(current.index);
 478                 if (existing != null && existing != currentBlock) {
 479                     currentBlock.reachable.add(existing);
 480                     continue;
 481                 }
 482                 int previous = currentBlock.instr.size() > 0
 483                         ? currentBlock.instr.get(currentBlock.instr.size() - 1).getIndex() : -1;
 484                 if (previous == -1 || current.getIndex() == previous + 1) {
 485                     currentBlock.instr.add(current);
 486                     if (current.next.isEmpty()) {
 487                         blocks.add(currentBlock);
 488                     } else {
 489                         if (current.next.size() > 1) {
 490                             blocks.add(currentBlock);
 491                             for (InstructionNode n : current.next) {
 492                                 Block loop = allBlocks.get(n.index);
 493                                 if (loop == null) {
 494                                     Block newBlock = newBlock(n);
 495                                     currentBlock.reachable.add(newBlock);
 496                                     stack.push(new StackItem(n, newBlock));
 497                                 } else { // loop
 498                                     currentBlock.reachable.add(loop);
 499                                 }
 500                             }
 501                         } else {
 502                             stack.push(new StackItem(current.next.get(0),
 503                                     currentBlock));
 504                         }
 505                     }
 506                 } else { // to a new block...
 507                     // Do nothing...
 508                     blocks.add(currentBlock);
 509                     Block newBlock = newBlock(current);
 510                     currentBlock.reachable.add(newBlock);
 511                     stack.push(new StackItem(current, newBlock));
 512                 }
 513             }
 514         }
 515     }
 516 }