1 /*

     2  * Copyright (c) 2018, 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 package org.graalvm.compiler.nodes;

    24 

    25 import jdk.vm.ci.code.BytecodePosition;

    26 import jdk.vm.ci.meta.ResolvedJavaMethod;

    27 

    28 import java.util.ArrayList;

    29 import java.util.HashMap;

    30 import java.util.List;

    31 import java.util.Map;

    32 

    33 /**

    34  * This class contains all inlining decisions performed on a graph during the compilation.

    35  *

    36  * Each inlining decision consists of:

    37  *

    38  * <ul>

    39  * <li>a value indicating whether the decision was positive or negative</li>

    40  * <li>the call target method</li>

    41  * <li>the reason for the inlining decision</li>

    42  * <li>the name of the phase in which the inlining decision took place</li>

    43  * <li>the special {@link BytecodePositionWithId} value that describes the position in the bytecode

    44  * together with the callsite-specific unique identifier</li>

    45  * <li>the inlining log of the inlined graph, or {@code null} if the decision was negative</li>

    46  * </ul>

    47  *

    48  * A phase that does inlining should use the instance of this class contained in the

    49  * {@link StructuredGraph} by calling {@link #addDecision} whenever it decides to inline a method.

    50  * If there are invokes in the graph at the end of the respective phase, then that phase must call

    51  * {@link #addDecision} to log negative decisions.

    52  *

    53  * At the end of the compilation, the contents of the inlining log can be converted into a list of

    54  * decisions by calling {@link #formatAsList} or into an inlining tree, by calling

    55  * {@link #formatAsTree}.

    56  */

    57 public class InliningLog {

    58     /**

    59      * A bytecode position with a unique identifier attached.

    60      *

    61      * The purpose of this class is to disambiguate callsites that are duplicated by a

    62      * transformation (such as loop peeling or path duplication).

    63      */

    64     public static final class BytecodePositionWithId extends BytecodePosition implements Comparable<BytecodePositionWithId> {

    65         private final int id;

    66 

    67         public BytecodePositionWithId(BytecodePositionWithId caller, ResolvedJavaMethod method, int bci, int id) {

    68             super(caller, method, bci);

    69             this.id = id;

    70         }

    71 

    72         public BytecodePositionWithId addCallerWithId(BytecodePositionWithId caller) {

    73             if (getCaller() == null) {

    74                 return new BytecodePositionWithId(caller, getMethod(), getBCI(), id);

    75             } else {

    76                 return new BytecodePositionWithId(getCaller().addCallerWithId(caller), getMethod(), getBCI(), id);

    77             }

    78         }

    79 

    80         public static BytecodePositionWithId create(FrameState state) {

    81             return create(state, true);

    82         }

    83 

    84         @SuppressWarnings("deprecation")

    85         private static BytecodePositionWithId create(FrameState state, boolean topLevel) {

    86             if (state == null) {

    87                 return null;

    88             }

    89             ResolvedJavaMethod method = state.getMethod();

    90             int bci = topLevel ? state.bci - 3 : state.bci;

    91             int id = state.getId();

    92             return new BytecodePositionWithId(create(state.outerFrameState(), false), method, bci, id);

    93         }

    94 

    95         @Override

    96         public BytecodePositionWithId getCaller() {

    97             return (BytecodePositionWithId) super.getCaller();

    98         }

    99 

   100         public BytecodePositionWithId withoutCaller() {

   101             return new BytecodePositionWithId(null, getMethod(), getBCI(), id);

   102         }

   103 

   104         public long getId() {

   105             return id;

   106         }

   107 

   108         @Override

   109         public boolean equals(Object that) {

   110             return super.equals(that) && this.id == ((BytecodePositionWithId) that).id;

   111         }

   112 

   113         @Override

   114         public int hashCode() {

   115             return super.hashCode() ^ (id << 16);

   116         }

   117 

   118         @Override

   119         public int compareTo(BytecodePositionWithId that) {

   120             int diff = this.getBCI() - that.getBCI();

   121             if (diff != 0) {

   122                 return diff;

   123             }

   124             diff = (int) (this.getId() - that.getId());

   125             return diff;

   126         }

   127     }

   128 

   129     public static final class Decision {

   130         private final boolean positive;

   131         private final String reason;

   132         private final String phase;

   133         private final ResolvedJavaMethod target;

   134         private final BytecodePositionWithId position;

   135         private final InliningLog childLog;

   136 

   137         private Decision(boolean positive, String reason, String phase, ResolvedJavaMethod target, BytecodePositionWithId position, InliningLog childLog) {

   138             assert position != null;

   139             this.positive = positive;

   140             this.reason = reason;

   141             this.phase = phase;

   142             this.target = target;

   143             this.position = position;

   144             this.childLog = childLog;

   145         }

   146 

   147         public boolean isPositive() {

   148             return positive;

   149         }

   150 

   151         public String getReason() {

   152             return reason;

   153         }

   154 

   155         public String getPhase() {

   156             return phase;

   157         }

   158 

   159         public BytecodePositionWithId getPosition() {

   160             return position;

   161         }

   162 

   163         public InliningLog getChildLog() {

   164             return childLog;

   165         }

   166 

   167         public ResolvedJavaMethod getTarget() {

   168             return target;

   169         }

   170     }

   171 

   172     private static class Callsite {

   173         public final List<String> decisions;

   174         public final Map<BytecodePositionWithId, Callsite> children;

   175         public final BytecodePositionWithId position;

   176 

   177         Callsite(BytecodePositionWithId position) {

   178             this.children = new HashMap<>();

   179             this.position = position;

   180             this.decisions = new ArrayList<>();

   181         }

   182 

   183         public Callsite getOrCreateChild(BytecodePositionWithId fromRootPosition) {

   184             Callsite child = children.get(fromRootPosition.withoutCaller());

   185             if (child == null) {

   186                 child = new Callsite(fromRootPosition);

   187                 children.put(fromRootPosition.withoutCaller(), child);

   188             }

   189             return child;

   190         }

   191 

   192         public Callsite createCallsite(BytecodePositionWithId fromRootPosition, String decision) {

   193             Callsite parent = getOrCreateCallsite(fromRootPosition.getCaller());

   194             Callsite callsite = parent.getOrCreateChild(fromRootPosition);

   195             callsite.decisions.add(decision);

   196             return null;

   197         }

   198 

   199         private Callsite getOrCreateCallsite(BytecodePositionWithId fromRootPosition) {

   200             if (fromRootPosition == null) {

   201                 return this;

   202             } else {

   203                 Callsite parent = getOrCreateCallsite(fromRootPosition.getCaller());

   204                 Callsite callsite = parent.getOrCreateChild(fromRootPosition);

   205                 return callsite;

   206             }

   207         }

   208     }

   209 

   210     private final List<Decision> decisions;

   211 

   212     public InliningLog() {

   213         this.decisions = new ArrayList<>();

   214     }

   215 

   216     public List<Decision> getDecisions() {

   217         return decisions;

   218     }

   219 

   220     public void addDecision(boolean positive, String reason, String phase, ResolvedJavaMethod target, BytecodePositionWithId position,

   221                     InliningLog calleeLog) {

   222         Decision decision = new Decision(positive, reason, phase, target, position, calleeLog);

   223         decisions.add(decision);

   224     }

   225 

   226     public String formatAsList() {

   227         StringBuilder builder = new StringBuilder();

   228         formatAsList("", null, decisions, builder);

   229         return builder.toString();

   230     }

   231 

   232     private void formatAsList(String phasePrefix, BytecodePositionWithId caller, List<Decision> subDecisions, StringBuilder builder) {

   233         for (Decision decision : subDecisions) {

   234             String phaseStack = phasePrefix.equals("") ? decision.getPhase() : phasePrefix + "-" + decision.getPhase();

   235             String target = decision.getTarget().format("%H.%n(%p)");

   236             String positive = decision.isPositive() ? "inline" : "do not inline";

   237             BytecodePositionWithId absolutePosition = decision.getPosition().addCallerWithId(caller);

   238             String position = "  " + decision.getPosition().toString().replaceAll("\n", "\n  ");

   239             String line = String.format("<%s> %s %s: %s\n%s", phaseStack, positive, target, decision.getReason(), position);

   240             builder.append(line).append(System.lineSeparator());

   241             if (decision.getChildLog() != null) {

   242                 formatAsList(phaseStack, absolutePosition, decision.getChildLog().getDecisions(), builder);

   243             }

   244         }

   245     }

   246 

   247     public String formatAsTree() {

   248         Callsite root = new Callsite(null);

   249         createTree("", null, root, decisions);

   250         StringBuilder builder = new StringBuilder();

   251         formatAsTree(root, "", builder);

   252         return builder.toString();

   253     }

   254 

   255     private void createTree(String phasePrefix, BytecodePositionWithId caller, Callsite root, List<Decision> subDecisions) {

   256         for (Decision decision : subDecisions) {

   257             String phaseStack = phasePrefix.equals("") ? decision.getPhase() : phasePrefix + "-" + decision.getPhase();

   258             String target = decision.getTarget().format("%H.%n(%p)");

   259             BytecodePositionWithId absolutePosition = decision.getPosition().addCallerWithId(caller);

   260             String line = String.format("<%s> %s: %s", phaseStack, target, decision.getReason());

   261             root.createCallsite(absolutePosition, line);

   262             if (decision.getChildLog() != null) {

   263                 createTree(phaseStack, absolutePosition, root, decision.getChildLog().getDecisions());

   264             }

   265         }

   266     }

   267 

   268     private void formatAsTree(Callsite site, String indent, StringBuilder builder) {

   269         String position = site.position != null ? site.position.withoutCaller().toString() : "<root>";

   270         String decision = String.join("; ", site.decisions);

   271         String line = String.format("%s%s; %s", indent, position, decision);

   272         builder.append(line).append(System.lineSeparator());

   273         String childIndent = indent + "  ";

   274         site.children.entrySet().stream().sorted((x, y) -> x.getKey().compareTo(y.getKey())).forEach(e -> {

   275             formatAsTree(e.getValue(), childIndent, builder);

   276         });

   277     }

   278 }