src/main/java/com/android/tools/r8/ir/conversion/StringSwitchRemover.java - r8.git - Git at Google

 // Copyright (c) 2019, 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.conversion;

 import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
 import static com.android.tools.r8.naming.IdentifierNameStringUtils.isClassNameValue;

 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.ir.analysis.type.ClassTypeElement;
 import com.android.tools.r8.ir.analysis.type.PrimitiveTypeElement;
 import com.android.tools.r8.ir.analysis.type.TypeElement;
 import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.ConstString;
 import com.android.tools.r8.ir.code.Goto;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.If;
 import com.android.tools.r8.ir.code.If.Type;
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InstructionListIterator;
 import com.android.tools.r8.ir.code.IntSwitch;
 import com.android.tools.r8.ir.code.InvokeVirtual;
 import com.android.tools.r8.ir.code.Phi;
 import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.ir.code.StringSwitch;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.naming.IdentifierNameStringMarker;
 import com.android.tools.r8.utils.ArrayUtils;
 import com.android.tools.r8.utils.SetUtils;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Sets;
 import com.google.common.collect.Streams;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceRBTreeMap;
 import it.unimi.dsi.fastutil.objects.Reference2IntMap;
 import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
 import java.io.UTFDataFormatException;
 import java.util.LinkedHashMap;
 import java.util.ListIterator;
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.Set;

 public class StringSwitchRemover {

   private final AppView<?> appView;
   private final IdentifierNameStringMarker identifierNameStringMarker;
   private final ClassTypeElement stringType;

   StringSwitchRemover(AppView<?> appView, IdentifierNameStringMarker identifierNameStringMarker) {
     this.appView = appView;
     this.identifierNameStringMarker = identifierNameStringMarker;
     this.stringType = TypeElement.stringClassType(appView, definitelyNotNull());
   }

   void run(IRCode code) {
     if (!code.metadata().mayHaveStringSwitch()) {
       assert Streams.stream(code.instructions()).noneMatch(Instruction::isStringSwitch);
       return;
     }

     if (!prepareForStringSwitchRemoval(code)) {
       return;
     }

     Set<BasicBlock> newBlocksWithStrings = Sets.newIdentityHashSet();

     ListIterator<BasicBlock> blockIterator = code.listIterator();
     while (blockIterator.hasNext()) {
       BasicBlock block = blockIterator.next();
       StringSwitch theSwitch = block.exit().asStringSwitch();
       if (theSwitch != null) {
         try {
           SingleStringSwitchRemover remover;
           if (theSwitch.numberOfKeys() < appView.options().minimumStringSwitchSize
               || hashCodeOfKeysMayChangeAfterMinification(theSwitch)) {
             remover =
                 new SingleEqualityBasedStringSwitchRemover(
                     code, blockIterator, block, theSwitch, newBlocksWithStrings);
           } else {
             remover =
                 new SingleHashBasedStringSwitchRemover(
                     code, blockIterator, block, theSwitch, newBlocksWithStrings);
           }
           remover.removeStringSwitch();
         } catch (UTFDataFormatException e) {
           // The keys of a string-switch should never fail to decode.
           throw new Unreachable();
         }
       }
     }

     if (identifierNameStringMarker != null) {
       identifierNameStringMarker.decoupleIdentifierNameStringsInBlocks(code, newBlocksWithStrings);
     }

     assert code.isConsistentSSA();
   }

   // Returns true if minification is enabled and the switch value is guaranteed to be a class name.
   // In this case, we can't use the hash codes of the keys before minification, because they will
   // (potentially) change as a result of minification. Therefore, we currently emit a sequence of
   // if-equals checks for such switches.
   //
   // TODO(b/154483187): This should also use the hash-based string switch elimination.
   private boolean hashCodeOfKeysMayChangeAfterMinification(StringSwitch theSwitch) {
     return appView.options().isMinifying()
         && isClassNameValue(theSwitch.value(), appView.dexItemFactory());
   }

   private boolean prepareForStringSwitchRemoval(IRCode code) {
     boolean hasStringSwitch = false;
     ListIterator<BasicBlock> blockIterator = code.listIterator();
     while (blockIterator.hasNext()) {
       BasicBlock block = blockIterator.next();
       for (BasicBlock predecessor : block.getNormalPredecessors()) {
         StringSwitch exit = predecessor.exit().asStringSwitch();
         if (exit != null) {
           hasStringSwitch = true;
           if (block == exit.fallthroughBlock()) {
             // After the elimination of this string-switch instruction, there will be two
             // fallthrough blocks: one for the instruction that switches on the hash value and one
             // for the instruction that switches on the string id value.
             //
             // The existing fallthrough block will be the fallthrough block for the switch on the
             // hash value. Note that we can't use this block for the switch on the id value since
             // that would lead to critical edges.
             BasicBlock hashSwitchFallthroughBlock = block;

             // The `hashSwitchFallthroughBlock` will jump to the switch on the string id value.
             // This block will have multiple predecessors, hence the need for the split-edge
             // block.
             BasicBlock idSwitchBlock =
                 hashSwitchFallthroughBlock.listIterator(code).split(code, blockIterator);

             // Split again such that `idSwitchBlock` becomes a block consisting of a single goto
             // instruction that targets a block that is identical to the original fallthrough
             // block of the string-switch instruction.
             BasicBlock idSwitchFallthroughBlock =
                 idSwitchBlock.listIterator(code).split(code, blockIterator);
             break;
           }
         }
       }
     }

     return hasStringSwitch;
   }

   private abstract static class SingleStringSwitchRemover {

     final IRCode code;
     final ListIterator<BasicBlock> blockIterator;
     final Set<BasicBlock> newBlocksWithStrings;

     final Position position;
     final Value stringValue;

     private SingleStringSwitchRemover(
         IRCode code,
         ListIterator<BasicBlock> blockIterator,
         StringSwitch theSwitch,
         Set<BasicBlock> newBlocksWithStrings) {
       this.code = code;
       this.blockIterator = blockIterator;
       this.newBlocksWithStrings = newBlocksWithStrings;
       this.position = theSwitch.getPosition();
       this.stringValue = theSwitch.value();
     }

     abstract void removeStringSwitch();
   }

   private class SingleEqualityBasedStringSwitchRemover extends SingleStringSwitchRemover {

     private final BasicBlock block;
     private final BasicBlock fallthroughBlock;

     private final Map<DexString, BasicBlock> structure;

     private SingleEqualityBasedStringSwitchRemover(
         IRCode code,
         ListIterator<BasicBlock> blockIterator,
         BasicBlock block,
         StringSwitch theSwitch,
         Set<BasicBlock> newBlocksWithStrings) {
       super(code, blockIterator, theSwitch, newBlocksWithStrings);
       this.block = block;
       this.fallthroughBlock = theSwitch.fallthroughBlock();
       this.structure = createStructure(theSwitch);
     }

     private Map<DexString, BasicBlock> createStructure(StringSwitch theSwitch) {
       Map<DexString, BasicBlock> result = new LinkedHashMap<>();
       theSwitch.forEachCase(result::put);
       return result;
     }

     @Override
     void removeStringSwitch() {
       // Remove outgoing control flow edges from the block containing the string switch.
       for (BasicBlock successor : block.getNormalSuccessors()) {
         successor.removePredecessor(block, null);
       }
       block.removeAllNormalSuccessors();
       Set<BasicBlock> blocksTargetedByMultipleSwitchCases = Sets.newIdentityHashSet();
       {
         Set<BasicBlock> seenBefore = SetUtils.newIdentityHashSet(structure.size());
         for (BasicBlock targetBlock : structure.values()) {
           if (!seenBefore.add(targetBlock)) {
             blocksTargetedByMultipleSwitchCases.add(targetBlock);
           }
         }
       }
       // Create a String.equals() check for each case in the string-switch instruction.
       BasicBlock previous = null;
       for (Entry<DexString, BasicBlock> entry : structure.entrySet()) {
         ConstString constStringInstruction =
             new ConstString(code.createValue(stringType), entry.getKey());
         constStringInstruction.setPosition(position);
         InvokeVirtual invokeInstruction =
             new InvokeVirtual(
                 appView.dexItemFactory().stringMembers.equals,
                 code.createValue(PrimitiveTypeElement.getInt()),
                 ImmutableList.of(stringValue, constStringInstruction.outValue()));
         invokeInstruction.setPosition(position);
         If ifInstruction = new If(If.Type.NE, invokeInstruction.outValue());
         ifInstruction.setPosition(Position.none());
         BasicBlock targetBlock = entry.getValue();
         if (blocksTargetedByMultipleSwitchCases.contains(targetBlock)) {
           // Need an intermediate block to avoid critical edges.
           BasicBlock intermediateBlock =
               BasicBlock.createGotoBlock(
                   code.getNextBlockNumber(), Position.none(), code.metadata());
           intermediateBlock.link(targetBlock);
           blockIterator.add(intermediateBlock);
           newBlocksWithStrings.add(intermediateBlock);
           targetBlock = intermediateBlock;
         }
         BasicBlock newBlock =
             BasicBlock.createIfBlock(
                 code.getNextBlockNumber(),
                 ifInstruction,
                 code.metadata(),
                 constStringInstruction,
                 invokeInstruction);
         newBlock.link(targetBlock);
         blockIterator.add(newBlock);
         newBlocksWithStrings.add(newBlock);
         if (previous == null) {
           // Replace the string-switch instruction by a goto instruction.
           block.exit().replace(new Goto(newBlock), code);
           block.link(newBlock);
         } else {
           // Set the fallthrough block for the previously added if-instruction.
           previous.link(newBlock);
         }
         previous = newBlock;
       }
       assert previous != null;
       // Set the fallthrough block for the last if-instruction.
       previous.link(fallthroughBlock);
     }
   }

   private class SingleHashBasedStringSwitchRemover extends SingleStringSwitchRemover {

     private final BasicBlock hashSwitchBlock;
     private final BasicBlock hashSwitchFallthroughBlock;
     private final BasicBlock idSwitchBlock;
     private final BasicBlock idSwitchFallthroughBlock;

     Int2ReferenceMap<Map<DexString, BasicBlock>> structure;

     private int nextStringId;

     private SingleHashBasedStringSwitchRemover(
         IRCode code,
         ListIterator<BasicBlock> blockIterator,
         BasicBlock hashSwitchBlock,
         StringSwitch theSwitch,
         Set<BasicBlock> newBlocksWithStrings)
         throws UTFDataFormatException {
       super(code, blockIterator, theSwitch, newBlocksWithStrings);
       this.hashSwitchBlock = hashSwitchBlock;
       this.hashSwitchFallthroughBlock = theSwitch.fallthroughBlock();
       this.idSwitchBlock = theSwitch.fallthroughBlock().getUniqueNormalSuccessor();
       this.idSwitchFallthroughBlock = idSwitchBlock.getUniqueNormalSuccessor();
       this.structure = createStructure(theSwitch);
     }

     private int getAndIncrementNextBlockNumber() {
       return code.getNextBlockNumber();
     }

     private Int2ReferenceMap<Map<DexString, BasicBlock>> createStructure(StringSwitch theSwitch)
         throws UTFDataFormatException {
       Int2ReferenceMap<Map<DexString, BasicBlock>> result = new Int2ReferenceRBTreeMap<>();
       theSwitch.forEachCase(
           (key, target) -> {
             int hashCode = key.decodedHashCode();
             if (result.containsKey(hashCode)) {
               result.get(hashCode).put(key, target);
             } else {
               Map<DexString, BasicBlock> cases = new LinkedHashMap<>();
               cases.put(key, target);
               result.put(hashCode, cases);
             }
           });
       return result;
     }

     @Override
     void removeStringSwitch() {
       // Remove outgoing control flow edges from the block containing the string switch.
       for (BasicBlock successor : hashSwitchBlock.getNormalSuccessors()) {
         successor.removePredecessor(hashSwitchBlock, null);
       }
       hashSwitchBlock.removeAllNormalSuccessors();

       // 1. Insert `int id = -1`.
       InstructionListIterator instructionIterator =
           hashSwitchBlock.listIterator(code, hashSwitchBlock.size());
       instructionIterator.previous();

       Phi idPhi = code.createPhi(idSwitchBlock, TypeElement.getInt());
       Value notFoundIdValue =
           instructionIterator.insertConstIntInstruction(code, appView.options(), -1);
       idPhi.appendOperand(notFoundIdValue);

       // 2. Insert `int hashCode = stringValue.hashCode()`.
       InvokeVirtual hashInvoke =
           new InvokeVirtual(
               appView.dexItemFactory().stringMembers.hashCode,
               code.createValue(TypeElement.getInt()),
               ImmutableList.of(stringValue));
       hashInvoke.setPosition(position);
       instructionIterator.add(hashInvoke);

       // 3. Create all the target blocks of the hash switch.
       //
       // Say that the string switch instruction contains the keys "X" and "Y" and assume that "X"
       // and "Y" have the same hash code. Then this will create code that looks like:
       //
       //   Block N:
       //     boolean equalsX = stringValue.equals("X")
       //     if equalsX then goto block N+1 else goto block N+2
       //   Block N+1:
       //     id = 0
       //     goto <id-switch-block>
       //   Block N+2:
       //     boolean equalsY = stringValue.equals("Y")
       //     if equalsY then goto block N+3 else goto block N+4
       //   Block N+3:
       //     id = 1
       //     goto <id-switch-block>
       //   Block N+4:
       //     goto <id-switch-block>
       createHashSwitchTargets(idPhi, notFoundIdValue);
       hashSwitchBlock.link(hashSwitchFallthroughBlock);

       // 4. Insert `switch (hashValue)`.
       IntSwitch hashSwitch = createHashSwitch(hashInvoke.outValue());
       instructionIterator.next();
       instructionIterator.replaceCurrentInstruction(hashSwitch);

       // 5. Link `idSwitchBlock` with all of its target blocks.
       Reference2IntMap<BasicBlock> targetBlockIndices = new Reference2IntOpenHashMap<>();
       targetBlockIndices.defaultReturnValue(-1);
       idSwitchBlock.getMutableSuccessors().clear();
       for (Map<DexString, BasicBlock> cases : structure.values()) {
         for (BasicBlock target : cases.values()) {
           int targetIndex = targetBlockIndices.getInt(target);
           if (targetIndex == -1) {
             targetBlockIndices.put(target, idSwitchBlock.getSuccessors().size());
             idSwitchBlock.link(target);
           }
         }
       }
       idSwitchBlock.getMutableSuccessors().add(idSwitchFallthroughBlock);

       // 6. Insert `switch (idValue)`.
       IntSwitch idSwitch = createIdSwitch(idPhi, targetBlockIndices);
       InstructionListIterator idSwitchBlockInstructionIterator = idSwitchBlock.listIterator(code);
       idSwitchBlockInstructionIterator.next();
       idSwitchBlockInstructionIterator.replaceCurrentInstruction(idSwitch);
     }

     private IntSwitch createHashSwitch(Value hashValue) {
       int[] hashSwitchKeys = structure.keySet().toArray(new int[0]);
       int[] hashSwitchTargetIndices = new int[hashSwitchKeys.length];
       for (int i = 0, offset = hashSwitchBlock.numberOfExceptionalSuccessors();
           i < hashSwitchTargetIndices.length;
           i++) {
         hashSwitchTargetIndices[i] = i + offset;
       }
       int hashSwitchFallthroughIndex = hashSwitchBlock.getSuccessors().size() - 1;
       return new IntSwitch(
           hashValue, hashSwitchKeys, hashSwitchTargetIndices, hashSwitchFallthroughIndex);
     }

     private void createHashSwitchTargets(Phi idPhi, Value notFoundIdValue) {
       for (Map<DexString, BasicBlock> cases : structure.values()) {
         // Create the target block for the hash switch.
         BasicBlock hashBlock =
             BasicBlock.createGotoBlock(getAndIncrementNextBlockNumber(), position, code.metadata());
         blockIterator.add(hashBlock);
         hashSwitchBlock.link(hashBlock);

         // Position the block iterator at the newly created block.
         BasicBlock previous = blockIterator.previous();
         assert previous == hashBlock;
         blockIterator.next();

         BasicBlock current = hashBlock;
         for (Entry<DexString, BasicBlock> entry : cases.entrySet()) {
           current.getMutableSuccessors().clear();

           // Insert `String key = <entry.getKey()>`.
           InstructionListIterator instructionIterator = current.listIterator(code);
           Value keyValue =
               instructionIterator.insertConstStringInstruction(appView, code, entry.getKey());
           newBlocksWithStrings.add(current);

           // Insert `boolean equalsKey = stringValue.equals(key)`.
           InvokeVirtual equalsInvoke =
               new InvokeVirtual(
                   appView.dexItemFactory().stringMembers.equals,
                   code.createValue(TypeElement.getInt()),
                   ImmutableList.of(stringValue, keyValue));
           equalsInvoke.setPosition(position);
           instructionIterator.add(equalsInvoke);

           // Create a new block for the success case.
           BasicBlock equalsKeyBlock =
               BasicBlock.createGotoBlock(
                   getAndIncrementNextBlockNumber(), position, code.metadata(), idSwitchBlock);
           idSwitchBlock.getMutablePredecessors().add(equalsKeyBlock);
           blockIterator.add(equalsKeyBlock);
           current.link(equalsKeyBlock);

           // Insert `int id = <nextStringId++>`.
           Value idValue =
               equalsKeyBlock
                   .listIterator(code)
                   .insertConstIntInstruction(code, appView.options(), nextStringId++);
           idPhi.appendOperand(idValue);

           // Create a new block for the failure case.
           BasicBlock continuationBlock =
               BasicBlock.createGotoBlock(
                   getAndIncrementNextBlockNumber(), position, code.metadata(), idSwitchBlock);
           blockIterator.add(continuationBlock);
           current.link(continuationBlock);

           // Insert `if (equalsKey) goto <id-switch-block> else goto <continuation-block>`.
           instructionIterator.next();
           instructionIterator.replaceCurrentInstruction(new If(Type.NE, equalsInvoke.outValue()));

           current = continuationBlock;
         }
         idPhi.appendOperand(notFoundIdValue);
         idSwitchBlock.getMutablePredecessors().add(current);
       }
     }

     private IntSwitch createIdSwitch(Phi idPhi, Reference2IntMap<BasicBlock> targetBlockIndices) {
       int numberOfCases = nextStringId;
       int[] keys = ArrayUtils.createIdentityArray(numberOfCases);
       int[] targetIndices = new int[numberOfCases];
       int i = 0;
       for (Map<DexString, BasicBlock> cases : structure.values()) {
         for (Entry<DexString, BasicBlock> entry : cases.entrySet()) {
           targetIndices[i++] = targetBlockIndices.getInt(entry.getValue());
         }
       }
       int fallthroughIndex = targetBlockIndices.size();
       return new IntSwitch(idPhi, keys, targetIndices, fallthroughIndex);
     }
   }
 }
	// Copyright (c) 2019, 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.conversion;

	import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
	import static com.android.tools.r8.naming.IdentifierNameStringUtils.isClassNameValue;

	import com.android.tools.r8.errors.Unreachable;
	import com.android.tools.r8.graph.AppView;
	import com.android.tools.r8.graph.DexString;
	import com.android.tools.r8.ir.analysis.type.ClassTypeElement;
	import com.android.tools.r8.ir.analysis.type.PrimitiveTypeElement;
	import com.android.tools.r8.ir.analysis.type.TypeElement;
	import com.android.tools.r8.ir.code.BasicBlock;
	import com.android.tools.r8.ir.code.ConstString;
	import com.android.tools.r8.ir.code.Goto;
	import com.android.tools.r8.ir.code.IRCode;
	import com.android.tools.r8.ir.code.If;
	import com.android.tools.r8.ir.code.If.Type;
	import com.android.tools.r8.ir.code.Instruction;
	import com.android.tools.r8.ir.code.InstructionListIterator;
	import com.android.tools.r8.ir.code.IntSwitch;
	import com.android.tools.r8.ir.code.InvokeVirtual;
	import com.android.tools.r8.ir.code.Phi;
	import com.android.tools.r8.ir.code.Position;
	import com.android.tools.r8.ir.code.StringSwitch;
	import com.android.tools.r8.ir.code.Value;
	import com.android.tools.r8.naming.IdentifierNameStringMarker;
	import com.android.tools.r8.utils.ArrayUtils;
	import com.android.tools.r8.utils.SetUtils;
	import com.google.common.collect.ImmutableList;
	import com.google.common.collect.Sets;
	import com.google.common.collect.Streams;
	import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
	import it.unimi.dsi.fastutil.ints.Int2ReferenceRBTreeMap;
	import it.unimi.dsi.fastutil.objects.Reference2IntMap;
	import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
	import java.io.UTFDataFormatException;
	import java.util.LinkedHashMap;
	import java.util.ListIterator;
	import java.util.Map;
	import java.util.Map.Entry;
	import java.util.Set;

	public class StringSwitchRemover {

	private final AppView<?> appView;
	private final IdentifierNameStringMarker identifierNameStringMarker;
	private final ClassTypeElement stringType;

	StringSwitchRemover(AppView<?> appView, IdentifierNameStringMarker identifierNameStringMarker) {
	this.appView = appView;
	this.identifierNameStringMarker = identifierNameStringMarker;
	this.stringType = TypeElement.stringClassType(appView, definitelyNotNull());
	}

	void run(IRCode code) {
	if (!code.metadata().mayHaveStringSwitch()) {
	assert Streams.stream(code.instructions()).noneMatch(Instruction::isStringSwitch);
	return;
	}

	if (!prepareForStringSwitchRemoval(code)) {
	return;
	}

	Set<BasicBlock> newBlocksWithStrings = Sets.newIdentityHashSet();

	ListIterator<BasicBlock> blockIterator = code.listIterator();
	while (blockIterator.hasNext()) {
	BasicBlock block = blockIterator.next();
	StringSwitch theSwitch = block.exit().asStringSwitch();
	if (theSwitch != null) {
	try {
	SingleStringSwitchRemover remover;
	if (theSwitch.numberOfKeys() < appView.options().minimumStringSwitchSize
	\|\| hashCodeOfKeysMayChangeAfterMinification(theSwitch)) {
	remover =
	new SingleEqualityBasedStringSwitchRemover(
	code, blockIterator, block, theSwitch, newBlocksWithStrings);
	} else {
	remover =
	new SingleHashBasedStringSwitchRemover(
	code, blockIterator, block, theSwitch, newBlocksWithStrings);
	}
	remover.removeStringSwitch();
	} catch (UTFDataFormatException e) {
	// The keys of a string-switch should never fail to decode.
	throw new Unreachable();
	}
	}
	}

	if (identifierNameStringMarker != null) {
	identifierNameStringMarker.decoupleIdentifierNameStringsInBlocks(code, newBlocksWithStrings);
	}

	assert code.isConsistentSSA();
	}

	// Returns true if minification is enabled and the switch value is guaranteed to be a class name.
	// In this case, we can't use the hash codes of the keys before minification, because they will
	// (potentially) change as a result of minification. Therefore, we currently emit a sequence of
	// if-equals checks for such switches.
	//
	// TODO(b/154483187): This should also use the hash-based string switch elimination.
	private boolean hashCodeOfKeysMayChangeAfterMinification(StringSwitch theSwitch) {
	return appView.options().isMinifying()
	&& isClassNameValue(theSwitch.value(), appView.dexItemFactory());
	}

	private boolean prepareForStringSwitchRemoval(IRCode code) {
	boolean hasStringSwitch = false;
	ListIterator<BasicBlock> blockIterator = code.listIterator();
	while (blockIterator.hasNext()) {
	BasicBlock block = blockIterator.next();
	for (BasicBlock predecessor : block.getNormalPredecessors()) {
	StringSwitch exit = predecessor.exit().asStringSwitch();
	if (exit != null) {
	hasStringSwitch = true;
	if (block == exit.fallthroughBlock()) {
	// After the elimination of this string-switch instruction, there will be two
	// fallthrough blocks: one for the instruction that switches on the hash value and one
	// for the instruction that switches on the string id value.
	//
	// The existing fallthrough block will be the fallthrough block for the switch on the
	// hash value. Note that we can't use this block for the switch on the id value since
	// that would lead to critical edges.
	BasicBlock hashSwitchFallthroughBlock = block;

	// The `hashSwitchFallthroughBlock` will jump to the switch on the string id value.
	// This block will have multiple predecessors, hence the need for the split-edge
	// block.
	BasicBlock idSwitchBlock =
	hashSwitchFallthroughBlock.listIterator(code).split(code, blockIterator);

	// Split again such that `idSwitchBlock` becomes a block consisting of a single goto
	// instruction that targets a block that is identical to the original fallthrough
	// block of the string-switch instruction.
	BasicBlock idSwitchFallthroughBlock =
	idSwitchBlock.listIterator(code).split(code, blockIterator);
	break;
	}
	}
	}
	}

	return hasStringSwitch;
	}

	private abstract static class SingleStringSwitchRemover {

	final IRCode code;
	final ListIterator<BasicBlock> blockIterator;
	final Set<BasicBlock> newBlocksWithStrings;

	final Position position;
	final Value stringValue;

	private SingleStringSwitchRemover(
	IRCode code,
	ListIterator<BasicBlock> blockIterator,
	StringSwitch theSwitch,
	Set<BasicBlock> newBlocksWithStrings) {
	this.code = code;
	this.blockIterator = blockIterator;
	this.newBlocksWithStrings = newBlocksWithStrings;
	this.position = theSwitch.getPosition();
	this.stringValue = theSwitch.value();
	}

	abstract void removeStringSwitch();
	}

	private class SingleEqualityBasedStringSwitchRemover extends SingleStringSwitchRemover {

	private final BasicBlock block;
	private final BasicBlock fallthroughBlock;

	private final Map<DexString, BasicBlock> structure;

	private SingleEqualityBasedStringSwitchRemover(
	IRCode code,
	ListIterator<BasicBlock> blockIterator,
	BasicBlock block,
	StringSwitch theSwitch,
	Set<BasicBlock> newBlocksWithStrings) {
	super(code, blockIterator, theSwitch, newBlocksWithStrings);
	this.block = block;
	this.fallthroughBlock = theSwitch.fallthroughBlock();
	this.structure = createStructure(theSwitch);
	}

	private Map<DexString, BasicBlock> createStructure(StringSwitch theSwitch) {
	Map<DexString, BasicBlock> result = new LinkedHashMap<>();
	theSwitch.forEachCase(result::put);
	return result;
	}

	@Override
	void removeStringSwitch() {
	// Remove outgoing control flow edges from the block containing the string switch.
	for (BasicBlock successor : block.getNormalSuccessors()) {
	successor.removePredecessor(block, null);
	}
	block.removeAllNormalSuccessors();
	Set<BasicBlock> blocksTargetedByMultipleSwitchCases = Sets.newIdentityHashSet();
	{
	Set<BasicBlock> seenBefore = SetUtils.newIdentityHashSet(structure.size());
	for (BasicBlock targetBlock : structure.values()) {
	if (!seenBefore.add(targetBlock)) {
	blocksTargetedByMultipleSwitchCases.add(targetBlock);
	}
	}
	}
	// Create a String.equals() check for each case in the string-switch instruction.
	BasicBlock previous = null;
	for (Entry<DexString, BasicBlock> entry : structure.entrySet()) {
	ConstString constStringInstruction =
	new ConstString(code.createValue(stringType), entry.getKey());
	constStringInstruction.setPosition(position);
	InvokeVirtual invokeInstruction =
	new InvokeVirtual(
	appView.dexItemFactory().stringMembers.equals,
	code.createValue(PrimitiveTypeElement.getInt()),
	ImmutableList.of(stringValue, constStringInstruction.outValue()));
	invokeInstruction.setPosition(position);
	If ifInstruction = new If(If.Type.NE, invokeInstruction.outValue());
	ifInstruction.setPosition(Position.none());
	BasicBlock targetBlock = entry.getValue();
	if (blocksTargetedByMultipleSwitchCases.contains(targetBlock)) {
	// Need an intermediate block to avoid critical edges.
	BasicBlock intermediateBlock =
	BasicBlock.createGotoBlock(
	code.getNextBlockNumber(), Position.none(), code.metadata());
	intermediateBlock.link(targetBlock);
	blockIterator.add(intermediateBlock);
	newBlocksWithStrings.add(intermediateBlock);
	targetBlock = intermediateBlock;
	}
	BasicBlock newBlock =
	BasicBlock.createIfBlock(
	code.getNextBlockNumber(),
	ifInstruction,
	code.metadata(),
	constStringInstruction,
	invokeInstruction);
	newBlock.link(targetBlock);
	blockIterator.add(newBlock);
	newBlocksWithStrings.add(newBlock);
	if (previous == null) {
	// Replace the string-switch instruction by a goto instruction.
	block.exit().replace(new Goto(newBlock), code);
	block.link(newBlock);
	} else {
	// Set the fallthrough block for the previously added if-instruction.
	previous.link(newBlock);
	}
	previous = newBlock;
	}
	assert previous != null;
	// Set the fallthrough block for the last if-instruction.
	previous.link(fallthroughBlock);
	}
	}

	private class SingleHashBasedStringSwitchRemover extends SingleStringSwitchRemover {

	private final BasicBlock hashSwitchBlock;
	private final BasicBlock hashSwitchFallthroughBlock;
	private final BasicBlock idSwitchBlock;
	private final BasicBlock idSwitchFallthroughBlock;

	Int2ReferenceMap<Map<DexString, BasicBlock>> structure;

	private int nextStringId;

	private SingleHashBasedStringSwitchRemover(
	IRCode code,
	ListIterator<BasicBlock> blockIterator,
	BasicBlock hashSwitchBlock,
	StringSwitch theSwitch,
	Set<BasicBlock> newBlocksWithStrings)
	throws UTFDataFormatException {
	super(code, blockIterator, theSwitch, newBlocksWithStrings);
	this.hashSwitchBlock = hashSwitchBlock;
	this.hashSwitchFallthroughBlock = theSwitch.fallthroughBlock();
	this.idSwitchBlock = theSwitch.fallthroughBlock().getUniqueNormalSuccessor();
	this.idSwitchFallthroughBlock = idSwitchBlock.getUniqueNormalSuccessor();
	this.structure = createStructure(theSwitch);
	}

	private int getAndIncrementNextBlockNumber() {
	return code.getNextBlockNumber();
	}

	private Int2ReferenceMap<Map<DexString, BasicBlock>> createStructure(StringSwitch theSwitch)
	throws UTFDataFormatException {
	Int2ReferenceMap<Map<DexString, BasicBlock>> result = new Int2ReferenceRBTreeMap<>();
	theSwitch.forEachCase(
	(key, target) -> {
	int hashCode = key.decodedHashCode();
	if (result.containsKey(hashCode)) {
	result.get(hashCode).put(key, target);
	} else {
	Map<DexString, BasicBlock> cases = new LinkedHashMap<>();
	cases.put(key, target);
	result.put(hashCode, cases);
	}
	});
	return result;
	}

	@Override
	void removeStringSwitch() {
	// Remove outgoing control flow edges from the block containing the string switch.
	for (BasicBlock successor : hashSwitchBlock.getNormalSuccessors()) {
	successor.removePredecessor(hashSwitchBlock, null);
	}
	hashSwitchBlock.removeAllNormalSuccessors();

	// 1. Insert `int id = -1`.
	InstructionListIterator instructionIterator =
	hashSwitchBlock.listIterator(code, hashSwitchBlock.size());
	instructionIterator.previous();

	Phi idPhi = code.createPhi(idSwitchBlock, TypeElement.getInt());
	Value notFoundIdValue =
	instructionIterator.insertConstIntInstruction(code, appView.options(), -1);
	idPhi.appendOperand(notFoundIdValue);

	// 2. Insert `int hashCode = stringValue.hashCode()`.
	InvokeVirtual hashInvoke =
	new InvokeVirtual(
	appView.dexItemFactory().stringMembers.hashCode,
	code.createValue(TypeElement.getInt()),
	ImmutableList.of(stringValue));
	hashInvoke.setPosition(position);
	instructionIterator.add(hashInvoke);

	// 3. Create all the target blocks of the hash switch.
	//
	// Say that the string switch instruction contains the keys "X" and "Y" and assume that "X"
	// and "Y" have the same hash code. Then this will create code that looks like:
	//
	// Block N:
	// boolean equalsX = stringValue.equals("X")
	// if equalsX then goto block N+1 else goto block N+2
	// Block N+1:
	// id = 0
	// goto <id-switch-block>
	// Block N+2:
	// boolean equalsY = stringValue.equals("Y")
	// if equalsY then goto block N+3 else goto block N+4
	// Block N+3:
	// id = 1
	// goto <id-switch-block>
	// Block N+4:
	// goto <id-switch-block>
	createHashSwitchTargets(idPhi, notFoundIdValue);
	hashSwitchBlock.link(hashSwitchFallthroughBlock);

	// 4. Insert `switch (hashValue)`.
	IntSwitch hashSwitch = createHashSwitch(hashInvoke.outValue());
	instructionIterator.next();
	instructionIterator.replaceCurrentInstruction(hashSwitch);

	// 5. Link `idSwitchBlock` with all of its target blocks.
	Reference2IntMap<BasicBlock> targetBlockIndices = new Reference2IntOpenHashMap<>();
	targetBlockIndices.defaultReturnValue(-1);
	idSwitchBlock.getMutableSuccessors().clear();
	for (Map<DexString, BasicBlock> cases : structure.values()) {
	for (BasicBlock target : cases.values()) {
	int targetIndex = targetBlockIndices.getInt(target);
	if (targetIndex == -1) {
	targetBlockIndices.put(target, idSwitchBlock.getSuccessors().size());
	idSwitchBlock.link(target);
	}
	}
	}
	idSwitchBlock.getMutableSuccessors().add(idSwitchFallthroughBlock);

	// 6. Insert `switch (idValue)`.
	IntSwitch idSwitch = createIdSwitch(idPhi, targetBlockIndices);
	InstructionListIterator idSwitchBlockInstructionIterator = idSwitchBlock.listIterator(code);
	idSwitchBlockInstructionIterator.next();
	idSwitchBlockInstructionIterator.replaceCurrentInstruction(idSwitch);
	}

	private IntSwitch createHashSwitch(Value hashValue) {
	int[] hashSwitchKeys = structure.keySet().toArray(new int[0]);
	int[] hashSwitchTargetIndices = new int[hashSwitchKeys.length];
	for (int i = 0, offset = hashSwitchBlock.numberOfExceptionalSuccessors();
	i < hashSwitchTargetIndices.length;
	i++) {
	hashSwitchTargetIndices[i] = i + offset;
	}
	int hashSwitchFallthroughIndex = hashSwitchBlock.getSuccessors().size() - 1;
	return new IntSwitch(
	hashValue, hashSwitchKeys, hashSwitchTargetIndices, hashSwitchFallthroughIndex);
	}

	private void createHashSwitchTargets(Phi idPhi, Value notFoundIdValue) {
	for (Map<DexString, BasicBlock> cases : structure.values()) {
	// Create the target block for the hash switch.
	BasicBlock hashBlock =
	BasicBlock.createGotoBlock(getAndIncrementNextBlockNumber(), position, code.metadata());
	blockIterator.add(hashBlock);
	hashSwitchBlock.link(hashBlock);

	// Position the block iterator at the newly created block.
	BasicBlock previous = blockIterator.previous();
	assert previous == hashBlock;
	blockIterator.next();

	BasicBlock current = hashBlock;
	for (Entry<DexString, BasicBlock> entry : cases.entrySet()) {
	current.getMutableSuccessors().clear();

	// Insert `String key = <entry.getKey()>`.
	InstructionListIterator instructionIterator = current.listIterator(code);
	Value keyValue =
	instructionIterator.insertConstStringInstruction(appView, code, entry.getKey());
	newBlocksWithStrings.add(current);

	// Insert `boolean equalsKey = stringValue.equals(key)`.
	InvokeVirtual equalsInvoke =
	new InvokeVirtual(
	appView.dexItemFactory().stringMembers.equals,
	code.createValue(TypeElement.getInt()),
	ImmutableList.of(stringValue, keyValue));
	equalsInvoke.setPosition(position);
	instructionIterator.add(equalsInvoke);

	// Create a new block for the success case.
	BasicBlock equalsKeyBlock =
	BasicBlock.createGotoBlock(
	getAndIncrementNextBlockNumber(), position, code.metadata(), idSwitchBlock);
	idSwitchBlock.getMutablePredecessors().add(equalsKeyBlock);
	blockIterator.add(equalsKeyBlock);
	current.link(equalsKeyBlock);

	// Insert `int id = <nextStringId++>`.
	Value idValue =
	equalsKeyBlock
	.listIterator(code)
	.insertConstIntInstruction(code, appView.options(), nextStringId++);
	idPhi.appendOperand(idValue);

	// Create a new block for the failure case.
	BasicBlock continuationBlock =
	BasicBlock.createGotoBlock(
	getAndIncrementNextBlockNumber(), position, code.metadata(), idSwitchBlock);
	blockIterator.add(continuationBlock);
	current.link(continuationBlock);

	// Insert `if (equalsKey) goto <id-switch-block> else goto <continuation-block>`.
	instructionIterator.next();
	instructionIterator.replaceCurrentInstruction(new If(Type.NE, equalsInvoke.outValue()));

	current = continuationBlock;
	}
	idPhi.appendOperand(notFoundIdValue);
	idSwitchBlock.getMutablePredecessors().add(current);
	}
	}

	private IntSwitch createIdSwitch(Phi idPhi, Reference2IntMap<BasicBlock> targetBlockIndices) {
	int numberOfCases = nextStringId;
	int[] keys = ArrayUtils.createIdentityArray(numberOfCases);
	int[] targetIndices = new int[numberOfCases];
	int i = 0;
	for (Map<DexString, BasicBlock> cases : structure.values()) {
	for (Entry<DexString, BasicBlock> entry : cases.entrySet()) {
	targetIndices[i++] = targetBlockIndices.getInt(entry.getValue());
	}
	}
	int fallthroughIndex = targetBlockIndices.size();
	return new IntSwitch(idPhi, keys, targetIndices, fallthroughIndex);
	}
	}
	}