src/main/java/com/android/tools/r8/ir/code/IntSwitch.java

// Copyright (c) 2016, 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.ir.code;

import com.android.tools.r8.cf.LoadStoreHelper;
import com.android.tools.r8.cf.code.CfLabel;
import com.android.tools.r8.cf.code.CfSwitch;
import com.android.tools.r8.cf.code.CfSwitch.Kind;
import com.android.tools.r8.code.Nop;
import com.android.tools.r8.code.PackedSwitch;
import com.android.tools.r8.code.PackedSwitchPayload;
import com.android.tools.r8.code.SparseSwitch;
import com.android.tools.r8.code.SparseSwitchPayload;
import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.utils.CfgPrinter;
import com.android.tools.r8.utils.IntObjConsumer;
import com.android.tools.r8.utils.InternalOutputMode;
import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
import java.util.ArrayList;
import java.util.List;

public class IntSwitch extends Switch {

  private final int[] keys;

  public IntSwitch(Value value, int[] keys, int[] targetBlockIndices, int fallthroughBlockIndex) {
    super(value, targetBlockIndices, fallthroughBlockIndex);
    this.keys = keys;
    assert valid();
  }

  @Override
  public int opcode() {
    return Opcodes.INT_SWITCH;
  }

  @Override
  public <T> T accept(InstructionVisitor<T> visitor) {
    return visitor.visit(this);
  }

  public void forEachCase(IntObjConsumer<BasicBlock> fn) {
    for (int i = 0; i < keys.length; i++) {
      fn.accept(getKey(i), targetBlock(i));
    }
  }

  @Override
  public Instruction materializeFirstKey(AppView<?> appView, IRCode code) {
    return code.createIntConstant(getFirstKey());
  }

  @Override
  public boolean valid() {
    assert super.valid();
    assert keys.length >= 1;
    assert keys.length <= Constants.U16BIT_MAX;
    // Keys must be acceding, and cannot target the fallthrough.
    assert keys.length == numberOfKeys();
    for (int i = 1; i < keys.length; i++) {
      assert keys[i - 1] < keys[i];
    }
    return true;
  }

  // Number of targets if this switch is emitted as a packed switch.
  private static long numberOfTargetsIfPacked(int[] keys) {
    return ((long) keys[keys.length - 1]) - ((long) keys[0]) + 1;
  }

  public static boolean canBePacked(InternalOutputMode mode, int[] keys) {
    // The size of a switch payload is stored in an ushort in the Dex file.
    return canBePacked(mode, numberOfTargetsIfPacked(keys));
  }

  public static boolean canBePacked(InternalOutputMode mode, long numberOfTargets) {
    // The size of a switch payload is stored in an ushort in the Dex file.
    return numberOfTargets
        <= (mode.isGeneratingClassFiles() ? Constants.U32BIT_MAX : Constants.U16BIT_MAX);
  }

  // Estimated size of the resulting dex instruction in code units (bytes in CF, 16-bit in Dex).
  public static long estimatedSize(InternalOutputMode mode, int[] keys) {
    long sparseSize = sparsePayloadSize(mode, keys) + baseSparseSize(mode);
    long packedSize = Long.MAX_VALUE;
    if (canBePacked(mode, keys)) {
      long packedPayloadSize = packedPayloadSize(mode, keys);
      packedSize = packedPayloadSize + basePackedSize(mode);
      if (packedSize < packedPayloadSize) {
        packedSize = Integer.MAX_VALUE;
      }
    }
    return Math.min(sparseSize, packedSize);
  }

  public static long estimatedSparseSize(InternalOutputMode mode, long keys) {
    return sparsePayloadSize(mode, keys) + baseSparseSize(mode);
  }

  // Estimated size of the packed/table instructions in code units excluding the payload (bytes in
  // CF, 16-bit in Dex).
  public static int basePackedSize(InternalOutputMode mode) {
    if (mode.isGeneratingClassFiles()) {
      // Table switch: opcode + padding + default + high + low.
      return 1 + 3 + 4 + 4 + 4;
    } else {
      return 3;
    }
  }

  // Estimated size of the sparse/lookup instructions in code units excluding the payload (bytes in
  // CF, 16-bit in Dex).
  public static int baseSparseSize(InternalOutputMode mode) {
    if (mode.isGeneratingClassFiles()) {
      // Lookup switch: opcode + padding + default + number of keys.
      return 1 + 3 + 4 + 4;
    } else {
      return 3;
    }
  }

  // Size of the switch payload if emitted as packed in code units (bytes in CF, 16-bit in Dex).
  public static long packedPayloadSize(InternalOutputMode mode, long numberOfTargets) {
    if (mode.isGeneratingClassFiles()) {
      assert numberOfTargets <= Constants.U32BIT_MAX;
      return numberOfTargets * 4;
    } else {
      // This size can not exceed Constants.U16BIT_MAX * 2 + 4 and can be contained in an 32-bit
      // integer.
      return (numberOfTargets * 2) + 4;
    }
  }

  // Size of the switch payload if emitted as packed in code units (bytes in CF, 16-bit in Dex).
  public static long packedPayloadSize(InternalOutputMode mode, int[] keys) {
    assert canBePacked(mode, keys);
    long numberOfTargets = numberOfTargetsIfPacked(keys);
    return packedPayloadSize(mode, numberOfTargets);
  }

  // Size of the switch payload if emitted as sparse in code units (bytes in CF, 16-bit in Dex).
  public static long sparsePayloadSize(InternalOutputMode mode, int[] keys) {
    return sparsePayloadSize(mode, keys.length);
  }

  // Size of the switch payload if emitted as sparse in code units (bytes in CF, 16-bit in Dex).
  public static long sparsePayloadSize(InternalOutputMode mode, long keys) {
    if (mode.isGeneratingClassFiles()) {
      // Lookup-switch has a 32-bit int key and 32-bit int value for each offset, 8 bytes per entry.
      return keys * 8;
    } else {
      // This size can not exceed Constants.U16BIT_MAX * 4 and can be contained in a
      // 32-bit integer.
      return keys * 4 + 2;
    }
  }

  private boolean canBePacked(InternalOutputMode mode) {
    return canBePacked(mode, keys);
  }

  // Size of the switch payload if emitted as packed in code units (bytes in CF, 16-bit in Dex).
  private long packedPayloadSize(InternalOutputMode mode) {
    return packedPayloadSize(mode, keys);
  }

  // Size of the switch payload if emitted as sparse in code units (bytes in CF, 16-bit in Dex).
  private long sparsePayloadSize(InternalOutputMode mode) {
    return sparsePayloadSize(mode, keys);
  }

  private boolean emitPacked(InternalOutputMode mode) {
    return canBePacked(mode) && packedPayloadSize(mode) <= sparsePayloadSize(mode);
  }

  public int getFirstKey() {
    return keys[0];
  }

  @Override
  public boolean isIntSwitch() {
    return true;
  }

  @Override
  public IntSwitch asIntSwitch() {
    return this;
  }

  @Override
  public boolean identicalNonValueNonPositionParts(Instruction other) {
    return false;
  }

  @Override
  public void buildDex(DexBuilder builder) {
    int value = builder.allocatedRegister(value(), getNumber());
    if (emitPacked(InternalOutputMode.DexIndexed)) {
      builder.addSwitch(this, new PackedSwitch(value));
    } else {
      builder.addSwitch(this, new SparseSwitch(value));
    }
  }

  public int getKey(int index) {
    return keys[index];
  }

  public int[] getKeys() {
    return keys;
  }

  public Int2ReferenceSortedMap<BasicBlock> getKeyToTargetMap() {
    Int2ReferenceSortedMap<BasicBlock> result = new Int2ReferenceAVLTreeMap<>();
    for (int i = 0; i < keys.length; i++) {
      result.put(getKey(i), targetBlock(i));
    }
    return result;
  }

  public Nop buildPayload(int[] targets, int fallthroughTarget, InternalOutputMode mode) {
    assert keys.length == targets.length;
    assert mode.isGeneratingDex();
    if (emitPacked(mode)) {
      int targetsCount = (int) numberOfTargetsIfPacked(keys);
      if (targets.length == targetsCount) {
        // All targets are already present.
        return new PackedSwitchPayload(getFirstKey(), targets);
      } else {
        // Generate the list of targets for all key values. Set the target for keys not present
        // to the fallthrough.
        int[] packedTargets = new int[targetsCount];
        int originalIndex = 0;
        for (int i = 0; i < targetsCount; i++) {
          int key = getFirstKey() + i;
          if (keys[originalIndex] == key) {
            packedTargets[i] = targets[originalIndex];
            originalIndex++;
          } else {
            packedTargets[i] = fallthroughTarget;
          }
        }
        assert originalIndex == keys.length;
        return new PackedSwitchPayload(getFirstKey(), packedTargets);
      }
    } else {
      assert numberOfKeys() == keys.length;
      return new SparseSwitchPayload(keys, targets);
    }
  }

  @Override
  public int maxInValueRegister() {
    return Constants.U8BIT_MAX;
  }

  @Override
  public int maxOutValueRegister() {
    return Constants.U8BIT_MAX;
  }

  @Override
  public String toString() {
    StringBuilder builder = new StringBuilder(super.toString()).append(System.lineSeparator());
    for (int i = 0; i < numberOfKeys(); i++) {
      builder
          .append("          ")
          .append(getKey(i))
          .append(" -> ")
          .append(targetBlock(i).getNumberAsString())
          .append(System.lineSeparator());
    }
    return builder.append("          F -> ").append(fallthroughBlock().getNumber()).toString();
  }

  @Override
  public void print(CfgPrinter printer) {
    super.print(printer);
    for (int index : targetBlockIndices()) {
      BasicBlock target = getBlock().getSuccessors().get(index);
      printer.append(" B").append(target.getNumber());
    }
  }

  @Override
  public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
    helper.loadInValues(this, it);
  }

  @Override
  public void buildCf(CfBuilder builder) {
    CfLabel fallthroughLabel = builder.getLabel(fallthroughBlock());
    List<CfLabel> labels = new ArrayList<>(numberOfKeys());
    List<BasicBlock> successors = getBlock().getSuccessors();
    if (emitPacked(InternalOutputMode.ClassFile)) {
      int min = keys[0];
      int max = keys[keys.length - 1];
      int index = 0;
      for (long i = min; i <= max; i++) {
        if (i == keys[index]) {
          labels.add(builder.getLabel(successors.get(getTargetBlockIndex(index))));
          index++;
        } else {
          labels.add(fallthroughLabel);
        }
      }
      assert index == numberOfKeys();
      builder.add(new CfSwitch(Kind.TABLE, fallthroughLabel, new int[] {min}, labels));
    } else {
      for (int index : targetBlockIndices()) {
        labels.add(builder.getLabel(successors.get(index)));
      }
      builder.add(new CfSwitch(Kind.LOOKUP, fallthroughLabel, this.keys, labels));
    }
  }
}