src/main/java/com/android/tools/r8/debuginfo/DebugRepresentation.java

// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.debuginfo;

import com.android.tools.r8.dex.VirtualFile;
import com.android.tools.r8.dex.code.DexInstruction;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexCode;
import com.android.tools.r8.graph.DexDebugInfo;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.graph.ProgramMethod;
import com.android.tools.r8.utils.CollectionUtils;
import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.IterableUtils;
import com.android.tools.r8.utils.LebUtils;
import com.android.tools.r8.utils.StringUtils;
import com.android.tools.r8.utils.positions.LineNumberOptimizer;
import com.android.tools.r8.utils.positions.PositionUtils;
import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
import it.unimi.dsi.fastutil.ints.IntIterators;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;

public class DebugRepresentation {

  public static final int NO_PC_ENCODING = -1;
  public static final int ALWAYS_PC_ENCODING = Integer.MAX_VALUE;

  public interface DebugRepresentationPredicate {

    int getDexPcEncodingCutoff(ProgramMethod method);
  }

  public static DebugRepresentationPredicate none(InternalOptions options) {
    assert !options.canUseDexPc2PcAsDebugInformation();
    return method -> NO_PC_ENCODING;
  }

  public static DebugRepresentationPredicate fromFiles(
      List<VirtualFile> files, InternalOptions options) {
    if (!options.canUseDexPc2PcAsDebugInformation()) {
      return none(options);
    }
    if (options.canUseNativeDexPcInsteadOfDebugInfo()) {
      return method -> ALWAYS_PC_ENCODING;
    }
    // TODO(b/220999985): Avoid the need to maintain a class-to-file map.
    Map<DexProgramClass, VirtualFile> classMapping = new IdentityHashMap<>();
    for (VirtualFile file : files) {
      if (options.testing.debugRepresentationCallback != null) {
        options.testing.debugRepresentationCallback.accept(file.getDebugRepresentation());
      }
      file.classes().forEach(c -> classMapping.put(c, file));
    }
    return method -> {
      if (!isPcCandidate(method.getDefinition(), options)) {
        return NO_PC_ENCODING;
      }
      VirtualFile file = classMapping.get(method.getHolder());
      DebugRepresentation cutoffs = file.getDebugRepresentation();
      int maxPc = cutoffs.getDexPcEncodingCutoff(method);
      assert maxPc == NO_PC_ENCODING
          || verifyLastExecutableInstructionWithinBound(
              method.getDefinition().getCode().asDexCode(), maxPc);
      return maxPc;
    };
  }

  private final Int2ReferenceMap<ConversionInfo> paramToInfo;

  private DebugRepresentation(Int2ReferenceMap<ConversionInfo> paramToInfo) {
    this.paramToInfo = paramToInfo;
  }

  public static void computeForFile(AppView<?> appView, VirtualFile file) {
    InternalOptions options = appView.options();
    if (!options.canUseDexPc2PcAsDebugInformation()
        || options.canUseNativeDexPcInsteadOfDebugInfo()) {
      return;
    }
    // First collect all of the per-pc costs
    // (the sum of the normal debug info for all methods sharing the same max pc and param count.)
    Int2ReferenceMap<CostSummary> paramCountToCosts = new Int2ReferenceOpenHashMap<>();
    for (DexProgramClass clazz : file.classes()) {
      IdentityHashMap<DexString, List<ProgramMethod>> overloads =
          LineNumberOptimizer.groupMethodsByRenamedName(appView, clazz);
      for (List<ProgramMethod> methods : overloads.values()) {
        if (methods.size() != 1) {
          // Never use PC info for overloaded methods. They need distinct lines to disambiguate.
          continue;
        }
        ProgramMethod method = methods.get(0);
        DexEncodedMethod definition = method.getDefinition();
        if (!isPcCandidate(definition, options)) {
          continue;
        }
        DexCode code = definition.getCode().asDexCode();
        DexDebugInfo debugInfo = code.getDebugInfo();
        if (debugInfo == null) {
          // If debug info is "null" then the cost of representing it as normal events will be a
          // single default event to ensure its source file content is active.
          debugInfo =
              DexDebugInfo.createEventBasedInfoForMethodWithoutDebugInfo(
                  definition, options.dexItemFactory());
        }
        assert debugInfo.getParameterCount() == method.getParameters().size();
        DexInstruction lastInstruction = getLastExecutableInstruction(code);
        if (lastInstruction == null) {
          continue;
        }
        int lastPc = lastInstruction.getOffset();
        int debugInfoCost = estimatedDebugInfoSize(debugInfo);
        paramCountToCosts
            .computeIfAbsent(debugInfo.getParameterCount(), CostSummary::new)
            .addCost(lastPc, debugInfoCost);
      }
    }
    // Second compute the cost of converting to a pc encoding.
    Int2ReferenceMap<ConversionInfo> conversions =
        new Int2ReferenceOpenHashMap<>(paramCountToCosts.size());
    paramCountToCosts.forEach(
        (param, summary) -> conversions.put(param, summary.computeConversionCosts(appView)));
    // The result is stored on the virtual files for thread safety.
    // TODO(b/220999985): Consider just passing this to the line number optimizer once fixed.
    file.setDebugRepresentation(new DebugRepresentation(conversions));
  }

  private int getDexPcEncodingCutoff(ProgramMethod method) {
    if (paramToInfo.isEmpty()) {
      // This should only be the case if the method has overloads and thus *cannot* use pc encoding.
      assert verifyMethodHasOverloads(method);
      return NO_PC_ENCODING;
    }
    DexCode code = method.getDefinition().getCode().asDexCode();
    int paramCount = method.getParameters().size();
    assert code.getDebugInfo() == null || code.getDebugInfo().getParameterCount() == paramCount;
    ConversionInfo conversionInfo = paramToInfo.get(paramCount);
    if (conversionInfo == null || !conversionInfo.hasConversions()) {
      // We expect all methods calling this to have computed conversion info.
      assert conversionInfo != null;
      return NO_PC_ENCODING;
    }
    DexInstruction lastInstruction = getLastExecutableInstruction(code);
    if (lastInstruction == null) {
      return NO_PC_ENCODING;
    }
    int maxPc = lastInstruction.getOffset();
    return conversionInfo.getConversionPointFor(maxPc);
  }

  private boolean verifyMethodHasOverloads(ProgramMethod method) {
    assert 1
        < IterableUtils.size(method.getHolder().methods(m -> m.getName().equals(method.getName())));
    return true;
  }

  @Override
  public String toString() {
    return toString(false);
  }

  public String toString(boolean printCostSummary) {
    List<ConversionInfo> sorted = new ArrayList<>(paramToInfo.values());
    sorted.sort(Comparator.comparing(i -> i.paramCount));
    return StringUtils.join("\n", sorted, c -> c.toString(printCostSummary));
  }

  private static boolean isPcCandidate(DexEncodedMethod method, InternalOptions options) {
    if (!method.hasCode() || !method.getCode().isDexCode()) {
      return false;
    }
    return PositionUtils.mustHaveResidualDebugInfo(options, method);
  }

  /** Cost information for debug info at a given PC. */
  private static class PcCostInfo {
    // PC point for which the information pertains to.
    final int pc;

    // Normal debug-info encoding cost.
    int cost = 0;

    // Number of methods this information pertains to.
    int methods = 0;

    @Override
    public String toString() {
      return "pc="
          + pc
          + ", cost="
          + cost
          + ", methods="
          + methods
          + ", saved="
          + (cost - pc)
          + ", overhead="
          + getExpansionOverhead(pc, methods, cost);
    }

    public PcCostInfo(int pc) {
      assert pc >= 0;
      this.pc = pc;
    }

    void add(int cost) {
      assert cost >= 0;
      methods++;
      this.cost += cost;
    }
  }

  /** Conversion judgment up to a given PC bound (the lower bound is context dependent). */
  private static class PcConversionInfo {
    static final PcConversionInfo NO_CONVERSION = new PcConversionInfo(-1, false, 0, 0);

    // PC bound for which the information pertains to.
    final int pc;

    // Judgment of whether the methods in this grouping should be converted to pc2pc encoding.
    final boolean converted;

    // Info for debugging.
    private final int methods;
    private final int normalCost;

    public PcConversionInfo(int pc, boolean converted, int methods, int normalCost) {
      this.pc = pc;
      this.converted = converted;
      this.methods = methods;
      this.normalCost = normalCost;
    }

    @Override
    public String toString() {
      return "pc="
          + pc
          + ", converted="
          + converted
          + ", cost="
          + normalCost
          + ", methods="
          + methods
          + ", saved="
          + (normalCost - pc)
          + ", overhead="
          + getExpansionOverhead(pc, methods, normalCost);
    }
  }

  // A pc2pc stream is approximately one event more than the pc.
  private static int pcEventCount(int pc) {
    return pc + 1;
  }

  /**
   * Figure for the overhead that the pc2pc encoding can result in.
   *
   * <p>This overhead is not in the encoding size but rather if the encoding is expanded at each
   * method referencing the shared PC encoding.
   */
  private static int getExpansionOverhead(int currentPc, int methodCount, int normalCost) {
    long expansion = ((long) pcEventCount(currentPc)) * methodCount;
    long cost = expansion - normalCost;
    return cost > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) cost;
  }

  private static boolean isWithinExpansionThreshold(
      int threshold, int currentPc, int methodCount, int normalCost) {
    // A negative threshold denotes unbounded.
    if (threshold < 0) {
      return true;
    }
    return getExpansionOverhead(currentPc, methodCount, normalCost) <= threshold;
  }

  /** The summary of normal costs for all debug info with a particular parameter size. */
  private static class CostSummary {
    private final int paramCount;

    // Values for the normal encoding costs per-pc.
    private Int2ReferenceMap<PcCostInfo> pcToCost = new Int2ReferenceOpenHashMap<>();

    private CostSummary(int paramCount) {
      assert paramCount >= 0;
      this.paramCount = paramCount;
    }

    private void addCost(int pc, int cost) {
      assert pc >= 0;
      pcToCost.computeIfAbsent(pc, PcCostInfo::new).add(cost);
    }

    private static class ConversionState {
      Int2ReferenceSortedMap<PcConversionInfo> groups = new Int2ReferenceAVLTreeMap<>();
      PcConversionInfo converted = PcConversionInfo.NO_CONVERSION;
      int flushedPc = 0;
      int unconvertedPc = 0;
      int normalCost = 0;
      int methods = 0;

      void reset() {
        converted = PcConversionInfo.NO_CONVERSION;
        unconvertedPc = 0;
        normalCost = 0;
        methods = 0;
      }

      void add(PcCostInfo costInfo) {
        methods += costInfo.methods;
        normalCost += costInfo.cost;
      }

      void flush() {
        if (flushedPc < converted.pc) {
          groups.put(converted.pc, converted);
          flushedPc = converted.pc;
        }
        if (flushedPc < unconvertedPc) {
          if (0 < flushedPc && !groups.get(flushedPc).converted) {
            groups.remove(flushedPc);
          }
          PcConversionInfo unconverted =
              new PcConversionInfo(unconvertedPc, false, methods, normalCost);
          groups.put(unconvertedPc, unconverted);
          flushedPc = unconvertedPc;
        }
        reset();
      }

      void update(int currentPc, boolean convertToPc) {
        if (convertToPc) {
          converted = new PcConversionInfo(currentPc, true, methods, normalCost);
          unconvertedPc = 0;
        } else {
          unconvertedPc = currentPc;
        }
      }

      public Int2ReferenceSortedMap<PcConversionInfo> getFinalConversions() {
        // If there is only a single group check it is actually a converted range.
        if (groups.size() > 1
            || (groups.size() == 1 && groups.values().iterator().next().converted)) {
          return groups;
        }
        return null;
      }
    }

    private ConversionInfo computeConversionCosts(AppView<?> appView) {
      int threshold = appView.options().testing.pcBasedDebugEncodingOverheadThreshold;
      boolean forcePcBasedEncoding = appView.options().testing.forcePcBasedEncoding;
      assert !pcToCost.isEmpty();
      // Iterate in ascending order as the point conversion cost is the sum of the preceding costs.
      int[] sortedPcs = new int[pcToCost.size()];
      IntIterators.unwrap(pcToCost.keySet().iterator(), sortedPcs);
      Arrays.sort(sortedPcs);
      ConversionState state = new ConversionState();
      for (int currentPc : sortedPcs) {
        PcCostInfo current = pcToCost.get(currentPc);
        assert currentPc == current.pc;
        // Don't extend the conversion group as it could potentially become too large if expanded.
        // Any pending conversion can be flushed now.
        if (!isWithinExpansionThreshold(
            threshold,
            currentPc,
            state.methods + current.methods,
            state.normalCost + current.cost)) {
          state.flush();
        }
        state.add(current);
        int costToConvert = pcEventCount(currentPc);
        boolean canExpand =
            isWithinExpansionThreshold(threshold, currentPc, state.methods, state.normalCost);
        state.update(
            currentPc, canExpand && (forcePcBasedEncoding || state.normalCost > costToConvert));
      }
      state.flush();
      return new ConversionInfo(
          paramCount,
          state.getFinalConversions(),
          appView.options().testing.debugRepresentationCallback != null ? this : null);
    }

    @Override
    public String toString() {
      StringBuilder builder = new StringBuilder();
      builder.append("params:").append(paramCount).append('\n');
      Collection<Integer> keys = CollectionUtils.sort(pcToCost.keySet(), Integer::compareTo);
      for (int key : keys) {
        builder.append(pcToCost.get(key)).append('\n');
      }
      return builder.toString();
    }
  }

  /** The computed conversion points all debug info with a particular parameter size. */
  private static class ConversionInfo {
    private final int paramCount;
    private final Int2ReferenceSortedMap<PcConversionInfo> conversions;

    // For debugging purposes.
    private final CostSummary costSummary;

    private ConversionInfo(
        int paramCount,
        Int2ReferenceSortedMap<PcConversionInfo> conversions,
        CostSummary costSummary) {
      assert paramCount >= 0;
      this.paramCount = paramCount;
      this.conversions = conversions;
      this.costSummary = costSummary;
    }

    boolean hasConversions() {
      return conversions != null;
    }

    int getConversionPointFor(int pc) {
      Int2ReferenceSortedMap<PcConversionInfo> tailMap = conversions.tailMap(pc);
      if (tailMap.isEmpty()) {
        return -1;
      }
      int pcGroupBound = tailMap.firstIntKey();
      PcConversionInfo entryUpToIncludingMax = conversions.get(pcGroupBound);
      if (entryUpToIncludingMax.converted) {
        assert pcGroupBound == entryUpToIncludingMax.pc;
        return pcGroupBound;
      }
      return -1;
    }

    @Override
    public String toString() {
      return toString(false);
    }

    public String toString(boolean printCostSummaries) {
      StringBuilder builder = new StringBuilder();
      builder.append("params:").append(paramCount).append('\n');
      if (conversions != null) {
        for (PcConversionInfo group : conversions.values()) {
          builder.append(group).append('\n');
        }
      } else {
        builder.append(" no conversions").append('\n');
      }
      if (printCostSummaries && costSummary != null) {
        builder.append("Cost summaries:\n");
        builder.append(costSummary);
      }
      return builder.toString();
    }
  }

  public static boolean verifyLastExecutableInstructionWithinBound(DexCode code, int maxPc) {
    DexInstruction lastExecutableInstruction = getLastExecutableInstruction(code);
    int offset = lastExecutableInstruction.getOffset();
    assert offset <= maxPc;
    return true;
  }

  public static DexInstruction getLastExecutableInstruction(DexCode code) {
    return getLastExecutableInstruction(code.instructions);
  }

  public static DexInstruction getLastExecutableInstruction(DexInstruction[] instructions) {
    DexInstruction lastInstruction = null;
    for (DexInstruction instruction : instructions) {
      if (!instruction.isPayload()) {
        lastInstruction = instruction;
      }
    }
    return lastInstruction;
  }

  private static int estimatedDebugInfoSize(DexDebugInfo info) {
    if (info.isPcBasedInfo()) {
      return info.asPcBasedInfo().estimatedWriteSize();
    }
    // Each event is a single byte so we take the event length as the cost of the info.
    // Note that the line number optimizer could reduce the line diffs such that deltas are
    // smaller, but this is likely a very good estimate of the actual cost.
    int parameterCount = info.getParameterCount();
    int eventCount = info.asEventBasedInfo().events.length;
    // Size: startline(0) + paramCount + null-array[paramCount] + eventCount + 1(end-event)
    return LebUtils.sizeAsUleb128(0)
        + LebUtils.sizeAsUleb128(parameterCount)
        + LebUtils.sizeAsUleb128(0) * parameterCount
        + eventCount
        + 1;
  }
}