Ropper.java revision 39c5899d0359c386815f5f72991a3a2573135dbd
1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copyright (C) 2007 The Android Open Source Project 3f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * you may not use this file except in compliance with the License. 6f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * You may obtain a copy of the License at 7f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 8f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See the License for the specific language governing permissions and 14f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * limitations under the License. 15f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 16f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpackage com.android.dx.cf.code; 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.*; 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.cst.CstInteger; 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.cst.CstType; 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.type.Prototype; 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.type.StdTypeList; 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.type.Type; 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.type.TypeList; 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.Bits; 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.Hex; 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.IntList; 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.ArrayList; 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.BitSet; 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.HashMap; 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Utility that converts a basic block list into a list of register-oriented 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * blocks. 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic final class Ropper { 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** label offset for the parameter assignment block */ 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int PARAM_ASSIGNMENT = -1; 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** label offset for the return block */ 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int RETURN = -2; 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** label offset for the synchronized method final return block */ 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int SYNCH_RETURN = -3; 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** label offset for the first synchronized method setup block */ 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int SYNCH_SETUP_1 = -4; 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** label offset for the second synchronized method setup block */ 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int SYNCH_SETUP_2 = -5; 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * label offset for the first synchronized method exception 5639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * handler block 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int SYNCH_CATCH_1 = -6; 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * label offset for the second synchronized method exception 6239c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * handler block 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int SYNCH_CATCH_2 = -7; 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** number of special label offsets */ 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int SPECIAL_LABEL_COUNT = 7; 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 6999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} method being converted */ 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ConcreteMethod method; 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 7299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} original block list */ 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ByteBlockList blocks; 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** max locals of the method */ 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final int maxLocals; 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** max label (exclusive) of any original bytecode block */ 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final int maxLabel; 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 8199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} simulation machine to use */ 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final RopperMachine machine; 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 8499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} simulator to use */ 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final Simulator sim; 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 8839c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * {@code non-null;} sparse array mapping block labels to initial frame 8939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * contents, if known 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final Frame[] startFrames; 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 9399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} output block list in-progress */ 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ArrayList<BasicBlock> result; 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 9799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code non-null;} list of subroutine-nest labels 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * (See {@link Frame#getSubroutines} associated with each result block. 9939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Parallel to {@link Ropper#result}. 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ArrayList<IntList> resultSubroutines; 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 10499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code non-null;} for each block (by label) that is used as an exception 10539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * handler, the type of exception it catches 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final Type[] catchTypes; 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * whether an exception-handler block for a synchronized method was 11139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * ever required 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean synchNeedsExceptionHandler; 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 11539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein /** 11639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * {@code non-null;} list of subroutines indexed by label of start 11739c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * address */ 11839c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein private final Subroutine[] subroutines; 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 12099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** true if {@code subroutines} is non-empty */ 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean hasSubroutines; 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Keeps track of subroutines that exist in java form and are inlined in 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Rop form. 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private class Subroutine { 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** list of all blocks that jsr to this subroutine */ 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private BitSet callerBlocks; 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** List of all blocks that return from this subroutine */ 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private BitSet retBlocks; 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** first block in this subroutine */ 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int startBlock; 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs instance. 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param startBlock First block of the subroutine. 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Subroutine(int startBlock) { 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.startBlock = startBlock; 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project retBlocks = new BitSet(maxLabel); 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project callerBlocks = new BitSet(maxLabel); 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project hasSubroutines = true; 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs instance. 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param startBlock First block of the subroutine. 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param retBlock one of the ret blocks (final blocks) of this 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * subroutine. 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Subroutine(int startBlock, int retBlock) { 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this(startBlock); 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addRetBlock(retBlock); 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 16099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the label of the subroutine's start block. 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int getStartBlock() { 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return startBlock; 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds a label to the list of ret blocks (final blocks) for this 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * subroutine. 16939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param retBlock ret block label 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void addRetBlock(int retBlock) { 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project retBlocks.set(retBlock); 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds a label to the list of caller blocks for this subroutine. 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param label a block that invokes this subroutine. 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void addCallerBlock(int label) { 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project callerBlocks.set(label); 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Generates a list of subroutine successors. Note: successor blocks 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * could be listed more than once. This is ok, because this successor 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * list (and the block it's associated with) will be copied and inlined 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * before we leave the ropper. Redundent successors will result in 190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * redundent (no-op) merges. 19139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return all currently known successors 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * (return destinations) for that subroutine 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList getSuccessors() { 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList successors = new IntList(callerBlocks.size()); 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 19941aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein * For each subroutine caller, get it's target. If the 20041aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein * target is us, add the ret target (subroutine successor) 20141aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein * to our list 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 20441aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (int label = callerBlocks.nextSetBit(0); label >= 0; 20541aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein label = callerBlocks.nextSetBit(label+1)) { 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock subCaller = labelToBlock(label); 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.add(subCaller.getSuccessors().get(0)); 208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.setImmutable(); 21139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return successors; 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Merges the specified frame into this subroutine's successors, 21799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * setting {@code workSet} as appropriate. To be called with 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the frame of a subroutine ret block. 219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 22099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param frame {@code non-null;} frame from ret block to merge 22199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param workSet {@code non-null;} workset to update 222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void mergeToSuccessors(Frame frame, int[] workSet) { 22441aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (int label = callerBlocks.nextSetBit(0); label >= 0; 22541aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein label = callerBlocks.nextSetBit(label+1)) { 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock subCaller = labelToBlock(label); 227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int succLabel = subCaller.getSuccessors().get(0); 228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Frame subFrame = frame.subFrameForLabel(startBlock, label); 230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (subFrame != null) { 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mergeAndWorkAsNecessary(succLabel, -1, null, 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subFrame, workSet); 234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Bits.set(workSet, label); 236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Converts a {@link ConcreteMethod} to a {@link RopMethod}. 24339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 24499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param method {@code non-null;} method to convert 24599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param advice {@code non-null;} translation advice to use 24699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the converted instance 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public static RopMethod convert(ConcreteMethod method, 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project TranslationAdvice advice) { 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Ropper r = new Ropper(method, advice); 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project r.doit(); 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return r.getRopMethod(); 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (SimException ex) { 255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ex.addContext("...while working on method " + 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project method.getNat().toHuman()); 257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw ex; 258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs an instance. This class is not publicly instantiable; use 263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * {@link #convert}. 26439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 26599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param method {@code non-null;} method to convert 26699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param advice {@code non-null;} translation advice to use 267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private Ropper(ConcreteMethod method, TranslationAdvice advice) { 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (method == null) { 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException("method == null"); 271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (advice == null) { 274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException("advice == null"); 275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.method = method; 278f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.blocks = BasicBlocker.identifyBlocks(method); 279f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.maxLabel = blocks.getMaxLabel(); 280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.maxLocals = method.getMaxLocals(); 281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.machine = new RopperMachine(this, method, advice); 282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.sim = new Simulator(machine, method); 283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.startFrames = new Frame[maxLabel]; 284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.subroutines = new Subroutine[maxLabel]; 285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The "* 2 + 10" below is to conservatively believe that every 288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * block is an exception handler target and should also 289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * take care of enough other possible extra overhead such that 290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the underlying array is unlikely to need resizing. 291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.result = new ArrayList<BasicBlock>(blocks.size() * 2 + 10); 29339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein this.resultSubroutines = 29439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein new ArrayList<IntList>(blocks.size() * 2 + 10); 295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 296f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.catchTypes = new Type[maxLabel]; 297f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.synchNeedsExceptionHandler = false; 298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Set up the first stack frame with the right limits, but leave it 301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * empty here (to be filled in outside of the constructor). 302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startFrames[0] = new Frame(maxLocals, method.getMaxStack()); 304f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 307f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the first (lowest) register number to use as the temporary 308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * area when unwinding stack manipulation ops. 30939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 31099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the first register to use 311f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 312f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /*package*/ int getFirstTempStackReg() { 313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * We use the register that is just past the deepest possible 315f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * stack element, plus one if the method is synchronized to 316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * avoid overlapping with the synch register. We don't need to 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * do anything else special at this level, since later passes 318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * will merely notice the highest register used by explicit 319f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * inspection. 320f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int regCount = getNormalRegCount(); 322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return isSynchronized() ? regCount + 1 : regCount; 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the label for the exception handler setup block corresponding 327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to the given label. 32839c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 32999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param label {@code >= 0;} the original label 33099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the corresponding exception handler setup label 331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int getExceptionSetupLabel(int label) { 333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return maxLabel + label; 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the label for the given special-purpose block. The given label 338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * should be one of the static constants defined by this class. 33939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 34099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param label {@code < 0;} the special label constant 34199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the actual label value to use 342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int getSpecialLabel(int label) { 344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The label is bitwise-complemented so that mistakes where 346f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * LABEL is used instead of getSpecialLabel(LABEL) cause a 347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * failure at block construction time, since negative labels 348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * are illegal. We multiply maxLabel by 2 since 0..maxLabel 349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * (exclusive) are the original blocks and 350f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * maxLabel..(maxLabel*2) are reserved for exception handler 351f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * setup blocks (see getExceptionSetupLabel(), above). 352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return (maxLabel * 2) + ~label; 354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 357f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the minimum label for unreserved use. 35839c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 35999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the minimum label 360f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 361f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int getMinimumUnreservedLabel() { 362f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 363f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The labels below ((maxLabel * 2) + SPECIAL_LABEL_COUNT) are 364f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * reserved for particular uses. 365f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 366f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 367f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return (maxLabel * 2) + SPECIAL_LABEL_COUNT; 368f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 369f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 370f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 371f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets an arbitrary unreserved and available label. 37239c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 37399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the label 374f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 375f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int getAvailableLabel() { 376f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int candidate = getMinimumUnreservedLabel(); 377f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 378f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (BasicBlock bb : result) { 379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label = bb.getLabel(); 380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (label >= candidate) { 381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project candidate = label + 1; 382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 385f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return candidate; 386f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 387f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 389f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets whether the method being translated is synchronized. 39039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 391f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return whether the method being translated is synchronized 392f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 393f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean isSynchronized() { 394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int accessFlags = method.getAccessFlags(); 395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return (accessFlags & AccessFlags.ACC_SYNCHRONIZED) != 0; 396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 397f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets whether the method being translated is static. 40039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return whether the method being translated is static 402f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 403f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean isStatic() { 404f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int accessFlags = method.getAccessFlags(); 405f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return (accessFlags & AccessFlags.ACC_STATIC) != 0; 406f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 407f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 408f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 409f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the total number of registers used for "normal" purposes (i.e., 410f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * for the straightforward translation from the original Java). 41139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 41299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the total number of registers used 413f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 414f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int getNormalRegCount() { 415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return maxLocals + method.getMaxStack(); 416f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 417f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 418f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 419f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the register spec to use to hold the object to synchronize on, 420f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * for a synchronized method. 42139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 42299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the register spec 423f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 424f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private RegisterSpec getSynchReg() { 425f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 426f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * We use the register that is just past the deepest possible 427f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * stack element. We don't need to do anything else special at 428f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * this level, since later passes will merely notice the 429f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * highest register used by explicit inspection. 430f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 431f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return RegisterSpec.make(getNormalRegCount(), Type.OBJECT); 432f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 433f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 434f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 43539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Searches {@link #result} for a block with the given label. Returns its 43639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * index if found, or returns {@code -1} if there is no such block. 43739c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 438f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param label the label to look for 43999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= -1;} the index for the block with the given label or 44099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code -1} if there is no such block 441f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 442f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int labelToResultIndex(int label) { 443f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = result.size(); 444f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 445f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock one = result.get(i); 446f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (one.getLabel() == label) { 447f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return i; 448f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 449f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 450f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 451f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return -1; 45239c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein } 453f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 454f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 45539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Searches {@link #result} for a block with the given label. Returns it if 45639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * found, or throws an exception if there is no such block. 45739c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 458f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param label the label to look for 45999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the block with the given label 460f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 461f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private BasicBlock labelToBlock(int label) { 462f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int idx = labelToResultIndex(label); 463f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 464f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (idx < 0) { 465f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalArgumentException("no such label " + 466f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Hex.u2(label)); 467f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 468f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 469f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result.get(idx); 470f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 471f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 472f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 473f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds a block to the output result. 47439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 47599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param block {@code non-null;} the block to add 47639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param subroutines {@code non-null;} subroutine label list 47739c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * as described in {@link Frame#getSubroutines} 478f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 479f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void addBlock(BasicBlock block, IntList subroutines) { 480f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (block == null) { 481f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException("block == null"); 482f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 483f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 484f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(block); 485f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutines.throwIfMutable(); 486f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines.add(subroutines); 487f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 488f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 489f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 490f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds or replace a block in the output result. If this is a 491f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * replacement, then any extra blocks that got added with the 492f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * original get removed as a result of calling this method. 49339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 49499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param block {@code non-null;} the block to add or replace 49539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param subroutines {@code non-null;} subroutine label list 49639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * as described in {@link Frame#getSubroutines} 49799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code true} if the block was replaced or 49899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code false} if it was added for the first time 499f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 500f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean addOrReplaceBlock(BasicBlock block, IntList subroutines) { 501f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (block == null) { 502f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException("block == null"); 503f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 504f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 505f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int idx = labelToResultIndex(block.getLabel()); 506f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean ret; 507f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 508f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (idx < 0) { 509f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ret = false; 510f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 511f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 512f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * We are replacing a pre-existing block, so find any 513f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * blocks that got added as part of the original and 514f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * remove those too. Such blocks are (possibly indirect) 515f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * successors of this block which are out of the range of 516f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * normally-translated blocks. 517f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 518f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project removeBlockAndSpecialSuccessors(idx); 519f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ret = true; 520f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 521f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 522f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(block); 523f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutines.throwIfMutable(); 524f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines.add(subroutines); 525f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ret; 526f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 527f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 528f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 529f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds or replaces a block in the output result. Do not delete 530f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * any successors. 531f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 53299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param block {@code non-null;} the block to add or replace 53339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param subroutines {@code non-null;} subroutine label list 53439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * as described in {@link Frame#getSubroutines} 53599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code true} if the block was replaced or 53699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code false} if it was added for the first time 537f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 538f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean addOrReplaceBlockNoDelete(BasicBlock block, 539f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList subroutines) { 540f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (block == null) { 541f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException("block == null"); 542f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 543f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 544f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int idx = labelToResultIndex(block.getLabel()); 545f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean ret; 546f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 547f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (idx < 0) { 548f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ret = false; 549f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 550f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.remove(idx); 551f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines.remove(idx); 552f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ret = true; 553f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 554f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 555f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(block); 556f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutines.throwIfMutable(); 557f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines.add(subroutines); 558f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ret; 559f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 560f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 561f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 562f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #addOrReplaceBlock} which recursively removes 563f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the given block and all blocks that are (direct and indirect) 564f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * successors of it whose labels indicate that they are not in the 565f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * normally-translated range. 56639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 56799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param idx {@code non-null;} block to remove (etc.) 568f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 569f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void removeBlockAndSpecialSuccessors(int idx) { 570f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int minLabel = getMinimumUnreservedLabel(); 571f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock block = result.get(idx); 572f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList successors = block.getSuccessors(); 573f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = successors.size(); 574f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 575f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.remove(idx); 576f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines.remove(idx); 577f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 578f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 579f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label = successors.get(i); 580f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (label >= minLabel) { 581f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project idx = labelToResultIndex(label); 582f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (idx < 0) { 583f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException("Invalid label " 584f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project + Hex.u2(label)); 585f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 586f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project removeBlockAndSpecialSuccessors(idx); 587f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 588f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 589f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 590f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 591f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 592f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Extracts the resulting {@link RopMethod} from the instance. 59339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 59499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the method object 595f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 596f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private RopMethod getRopMethod() { 597f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 598f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Construct the final list of blocks. 599f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 600f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = result.size(); 601f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlockList bbl = new BasicBlockList(sz); 602f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 603f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bbl.set(i, result.get(i)); 604f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 605f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bbl.setImmutable(); 606f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 607f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Construct the method object to wrap it all up. 608f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 609f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 610f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Note: The parameter assignment block is always the first 611f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * that should be executed, hence the second argument to the 612f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * constructor. 613f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 614f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return new RopMethod(bbl, getSpecialLabel(PARAM_ASSIGNMENT)); 615f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 616f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 617f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 618f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Does the conversion. 619f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 620f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void doit() { 621f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int[] workSet = Bits.makeBitSet(maxLabel); 622f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 623f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Bits.set(workSet, 0); 624f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addSetupBlocks(); 625f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project setFirstFrame(); 626f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 627f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (;;) { 628f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int offset = Bits.findFirst(workSet, 0); 629f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (offset < 0) { 630f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 631f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 632f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Bits.clear(workSet, offset); 633f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ByteBlock block = blocks.labelToBlock(offset); 634f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Frame frame = startFrames[offset]; 635f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 636f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processBlock(block, frame, workSet); 637f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (SimException ex) { 638f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ex.addContext("...while working on block " + Hex.u2(offset)); 639f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw ex; 640f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 641f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 642f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 643f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addReturnBlock(); 644f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addSynchExceptionHandlerBlock(); 645f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addExceptionSetupBlocks(); 646f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 647f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (hasSubroutines) { 648f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Subroutines are very rare, so skip this step if it's n/a 649f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project inlineSubroutines(); 650f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 651f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 652f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 653f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 654f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Sets up the first frame to contain all the incoming parameters in 655f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * locals. 656f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 657f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void setFirstFrame() { 658f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Prototype desc = method.getEffectiveDescriptor(); 659f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startFrames[0].initializeWithParameters(desc.getParameterTypes()); 660f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startFrames[0].setImmutable(); 661f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 662f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 663f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 664f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Processes the given block. 66539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 66699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param block {@code non-null;} block to process 66799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param frame {@code non-null;} start frame for the block 66839c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param workSet {@code non-null;} bits representing work to do, 66939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * which this method may add to 670f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 671f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void processBlock(ByteBlock block, Frame frame, int[] workSet) { 672f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Prepare the list of caught exceptions for this block. 673f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ByteCatchList catches = block.getCatches(); 674f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project machine.startBlock(catches.toRopCatchList()); 675f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 676f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 677f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Using a copy of the given frame, simulate each instruction, 678f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * calling into machine for each. 679f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 680f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project frame = frame.copy(); 681f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sim.simulate(block, frame); 682f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project frame.setImmutable(); 683f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 684f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int extraBlockCount = machine.getExtraBlockCount(); 685f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<Insn> insns = machine.getInsns(); 686f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int insnSz = insns.size(); 687f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 688f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 689f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Merge the frame into each possible non-exceptional 690f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * successor. 691f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 692f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 693f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int catchSz = catches.size(); 694f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList successors = block.getSuccessors(); 695f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 696f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int startSuccessorIndex; 697f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 698f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Subroutine calledSubroutine = null; 699f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (machine.hasJsr()) { 700f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 701f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If this frame ends in a JSR, only merge our frame with 702f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the subroutine start, not the subroutine's return target. 703f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 704f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startSuccessorIndex = 1; 705f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 706f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int subroutineLabel = successors.get(1); 707f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 708f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (subroutines[subroutineLabel] == null) { 70939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein subroutines[subroutineLabel] = 71039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein new Subroutine (subroutineLabel); 711f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 71239c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein 713f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutines[subroutineLabel].addCallerBlock(block.getLabel()); 714f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 715f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project calledSubroutine = subroutines[subroutineLabel]; 716f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (machine.hasRet()) { 717f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 718f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This block ends in a ret, which means it's the final block 719f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in some subroutine. Ultimately, this block will be copied 720f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and inlined for each call and then disposed of. 721f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 722f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 723f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ReturnAddress ra = machine.getReturnAddress(); 724f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int subroutineLabel = ra.getSubroutineAddress(); 725f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 726f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (subroutines[subroutineLabel] == null) { 727f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutines[subroutineLabel] 728f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = new Subroutine (subroutineLabel, block.getLabel()); 729f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 730f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutines[subroutineLabel].addRetBlock(block.getLabel()); 731f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 732f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 733f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors = subroutines[subroutineLabel].getSuccessors(); 734f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutines[subroutineLabel] 735f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project .mergeToSuccessors(frame, workSet); 736f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Skip processing below since we just did it. 737f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startSuccessorIndex = successors.size(); 738f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (machine.wereCatchesUsed()) { 739f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 740f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If there are catches, then the first successors 741f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * (which will either be all of them or all but the last one) 742f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * are catch targets. 743f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 744f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startSuccessorIndex = catchSz; 745f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 746f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startSuccessorIndex = 0; 747f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 748f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 749f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int succSz = successors.size(); 750f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = startSuccessorIndex; i < succSz; 751f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i++) { 752f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int succ = successors.get(i); 753f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 754f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mergeAndWorkAsNecessary(succ, block.getLabel(), 755f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project calledSubroutine, frame, workSet); 756f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (SimException ex) { 757f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ex.addContext("...while merging to block " + Hex.u2(succ)); 758f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw ex; 759f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 760f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 761f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 762f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if ((succSz == 0) && machine.returns()) { 763f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 764f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The block originally contained a return, but it has 765f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * been made to instead end with a goto, and we need to 766f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * tell it at this point that its sole successor is the 767f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * return block. This has to happen after the merge loop 768f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * above, since, at this point, the return block doesn't 769f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * actually exist; it gets synthesized at the end of 770f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * processing the original blocks. 771f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 772f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors = IntList.makeImmutable(getSpecialLabel(RETURN)); 773f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project succSz = 1; 774f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 775f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 776f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int primarySucc; 777f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 778f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (succSz == 0) { 779f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySucc = -1; 780f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 781f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySucc = machine.getPrimarySuccessorIndex(); 782f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (primarySucc >= 0) { 783f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySucc = successors.get(primarySucc); 784f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 785f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 786f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 787f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 788f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This variable is true only when the method is synchronized and 789f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the block being processed can possibly throw an exception. 790f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 791f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean synch = isSynchronized() && machine.canThrow(); 792f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 793f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (synch || (catchSz != 0)) { 794f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 795f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Deal with exception handlers: Merge an exception-catch 796f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * frame into each possible exception handler, and 797f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * construct a new set of successors to point at the 798f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * exception handler setup blocks (which get synthesized 799f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * at the very end of processing). 800f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 801f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean catchesAny = false; 802f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList newSucc = new IntList(succSz); 803f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < catchSz; i++) { 804f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ByteCatchList.Item one = catches.get(i); 805f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CstType exceptionClass = one.getExceptionClass(); 806f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int targ = one.getHandlerPc(); 807f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 808f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project catchesAny |= (exceptionClass == CstType.OBJECT); 809f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 810f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Frame f = frame.makeExceptionHandlerStartFrame(exceptionClass); 811f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 812f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 813f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mergeAndWorkAsNecessary(targ, block.getLabel(), 814f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project null, f, workSet); 815f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (SimException ex) { 816f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ex.addContext("...while merging exception to block " + 817f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Hex.u2(targ)); 818f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw ex; 819f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 820f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 821f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 822f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Set up the exception handler type, by setting it if 823f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the given handler has yet to be encountered, or by 824f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * conservatively unioning if it has. 825f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 826f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Type already = catchTypes[targ]; 827f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (already == null) { 828f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project catchTypes[targ] = exceptionClass.getClassType(); 829f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (already != exceptionClass.getClassType()) { 830f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project catchTypes[targ] = Type.OBJECT; 831f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 832f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 833f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 834f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The synthesized exception setup block will have the 835f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * label getExceptionSetupLabel(targ). 836f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 837f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSucc.add(getExceptionSetupLabel(targ)); 838f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 839f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 840f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (synch && !catchesAny) { 841f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 842f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The method is synchronized and this block doesn't 843f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * already have a catch-all handler, so add one to the 844f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * end, both in the successors and in the throwing 845f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction(s) at the end of the block (which is where 846f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the caught classes live). 847f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 848f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSucc.add(getSpecialLabel(SYNCH_CATCH_1)); 849f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project synchNeedsExceptionHandler = true; 850f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 851f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = insnSz - extraBlockCount - 1; i < insnSz; i++) { 852f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn = insns.get(i); 853f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn.canThrow()) { 854f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn = insn.withAddedCatch(Type.OBJECT); 855f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(i, insn); 856f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 857f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 858f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 859f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 860f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (primarySucc >= 0) { 861f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSucc.add(primarySucc); 862f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 863f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 864f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSucc.setImmutable(); 865f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors = newSucc; 866f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 867f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 868f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Construct the final resulting block(s), and store it (them). 869f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 870f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int primarySuccListIndex = successors.indexOf(primarySucc); 871f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 872f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 873f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If there are any extra blocks, work backwards through the 874f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * list of instructions, adding single-instruction blocks, and 875f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * resetting the successors variables as appropriate. 876f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 877f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (/*extraBlockCount*/; extraBlockCount > 0; extraBlockCount--) { 878f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 879f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Some of the blocks that the RopperMachine wants added 880f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * are for move-result insns, and these need goto insns as well. 881f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 882f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn extraInsn = insns.get(--insnSz); 883f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean needsGoto 884f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = extraInsn.getOpcode().getBranchingness() 885f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project == Rop.BRANCH_NONE; 886f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList il = new InsnList(needsGoto ? 2 : 1); 887f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList extraBlockSuccessors = successors; 888f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 889f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project il.set(0, extraInsn); 890f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 891f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (needsGoto) { 892f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project il.set(1, new PlainInsn(Rops.GOTO, 893f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project extraInsn.getPosition(), null, 894f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY)); 895f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 896f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Obviously, this block won't be throwing an exception 897f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * so it should only have one successor. 898f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 899f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project extraBlockSuccessors = IntList.makeImmutable(primarySucc); 900f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 901f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project il.setImmutable(); 902f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 903f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label = getAvailableLabel(); 904f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock bb = new BasicBlock(label, il, extraBlockSuccessors, 905f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySucc); 906f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // All of these extra blocks will be in the same subroutine 907f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock(bb, frame.getSubroutines()); 908f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 909f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors = successors.mutableCopy(); 910f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.set(primarySuccListIndex, label); 911f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.setImmutable(); 912f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySucc = label; 913f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 91439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein 915f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn lastInsn = (insnSz == 0) ? null : insns.get(insnSz - 1); 916f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 917f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 918f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Add a goto to the end of the block if it doesn't already 919f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * end with a branch, to maintain the invariant that all 920f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * blocks end with a branch of some sort or other. Note that 921f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * it is possible for there to be blocks for which no 922f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instructions were ever output (e.g., only consist of pop* 923f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in the original Java bytecode). 924f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 925f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if ((lastInsn == null) || 926f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (lastInsn.getOpcode().getBranchingness() == Rop.BRANCH_NONE)) { 927f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SourcePosition pos = (lastInsn == null) ? SourcePosition.NO_INFO : 928f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project lastInsn.getPosition(); 929f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(new PlainInsn(Rops.GOTO, pos, null, 930f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY)); 931f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insnSz++; 932f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 93339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein 934f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 935f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Construct a block for the remaining instructions (which in 936f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the usual case is all of them). 937f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 938f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 939f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList il = new InsnList(insnSz); 940f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < insnSz; i++) { 941f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project il.set(i, insns.get(i)); 942f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 943f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project il.setImmutable(); 944f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 945f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock bb = 946f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new BasicBlock(block.getLabel(), il, successors, primarySucc); 947f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addOrReplaceBlock(bb, frame.getSubroutines()); 948f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 949f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 950f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 951f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #processBlock}, which merges frames and 952f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * adds to the work set, as necessary. 95339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 95499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param label {@code >= 0;} label to work on 95599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param pred predecessor label; must be {@code >= 0} when 95699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code label} is a subroutine start block and calledSubroutine 957f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is non-null. Otherwise, may be -1. 95899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param calledSubroutine {@code null-ok;} a Subroutine instance if 95999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code label} is the first block in a subroutine. 96099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param frame {@code non-null;} new frame for the labelled block 96139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param workSet {@code non-null;} bits representing work to do, 96239c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * which this method may add to 963f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 964f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void mergeAndWorkAsNecessary(int label, int pred, 965f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Subroutine calledSubroutine, Frame frame, int[] workSet) { 966f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Frame existing = startFrames[label]; 967f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Frame merged; 968f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 969f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (existing != null) { 970f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 971f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Some other block also continues at this label. Merge 972f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the frames, and re-set the bit in the work set if there 973f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * was a change. 974f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 975f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (calledSubroutine != null) { 976f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project merged = existing.mergeWithSubroutineCaller(frame, 977f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project calledSubroutine.getStartBlock(), pred); 978f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 979f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project merged = existing.mergeWith(frame); 980f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 981f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (merged != existing) { 982f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startFrames[label] = merged; 983f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Bits.set(workSet, label); 984f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 985f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 986f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // This is the first time this label has been encountered. 987f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (calledSubroutine != null) { 988f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startFrames[label] 989f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = frame.makeNewSubroutineStartFrame(label, pred); 990f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 991f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project startFrames[label] = frame; 992f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 993f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Bits.set(workSet, label); 994f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 995f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 996f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 997f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 998f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs and adds the blocks that perform setup for the rest of 999f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the method. This includes a first block which merely contains 1000f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * assignments from parameters to the same-numbered registers and 1001f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * a possible second block which deals with synchronization. 1002f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1003f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void addSetupBlocks() { 1004f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalVariableList localVariables = method.getLocalVariables(); 1005f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SourcePosition pos = method.makeSourcePosistion(0); 1006f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Prototype desc = method.getEffectiveDescriptor(); 1007f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StdTypeList params = desc.getParameterTypes(); 1008f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = params.size(); 1009f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList insns = new InsnList(sz + 1); 1010f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int at = 0; 1011f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1012f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 1013f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Type one = params.get(i); 101439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein LocalVariableList.Item local = 101539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein localVariables.pcAndIndexToLocal(0, at); 1016f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec result = (local == null) ? 1017f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec.make(at, one) : 1018f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec.makeLocalOptional(at, one, local.getLocalItem()); 1019f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1020f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn = new PlainCstInsn(Rops.opMoveParam(one), pos, result, 1021f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY, 1022f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CstInteger.make(at)); 1023f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(i, insn); 1024f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project at += one.getCategory(); 1025f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1026f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 102739c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein insns.set(sz, new PlainInsn(Rops.GOTO, pos, null, 1028f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY)); 1029f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.setImmutable(); 1030f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1031f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean synch = isSynchronized(); 1032f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label = synch ? getSpecialLabel(SYNCH_SETUP_1) : 0; 1033f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock bb = 1034f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new BasicBlock(getSpecialLabel(PARAM_ASSIGNMENT), insns, 1035f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList.makeImmutable(label), label); 1036f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock(bb, IntList.EMPTY); 1037f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1038f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (synch) { 1039f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec synchReg = getSynchReg(); 1040f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn; 1041f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (isStatic()) { 1042f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn = new ThrowingCstInsn(Rops.CONST_OBJECT, pos, 1043f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY, 1044f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StdTypeList.EMPTY, 1045f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project method.getDefiningClass()); 1046f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns = new InsnList(1); 1047f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(0, insn); 1048f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 1049f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns = new InsnList(2); 1050f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn = new PlainCstInsn(Rops.MOVE_PARAM_OBJECT, pos, 1051f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project synchReg, RegisterSpecList.EMPTY, 1052f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CstInteger.VALUE_0); 1053f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(0, insn); 1054f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(1, new PlainInsn(Rops.GOTO, pos, null, 1055f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY)); 1056f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1057f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1058f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label2 = getSpecialLabel(SYNCH_SETUP_2); 1059f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.setImmutable(); 1060f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bb = new BasicBlock(label, insns, 1061f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList.makeImmutable(label2), label2); 1062f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock(bb, IntList.EMPTY); 1063f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1064f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns = new InsnList(isStatic() ? 2 : 1); 1065f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1066f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (isStatic()) { 1067f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(0, new PlainInsn(Rops.opMoveResultPseudo(synchReg), 1068f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pos, synchReg, RegisterSpecList.EMPTY)); 1069f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1070f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1071f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn = new ThrowingInsn(Rops.MONITOR_ENTER, pos, 1072f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.make(synchReg), 1073f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StdTypeList.EMPTY); 1074f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(isStatic() ? 1 :0, insn); 1075f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.setImmutable(); 1076f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bb = new BasicBlock(label2, insns, IntList.makeImmutable(0), 0); 1077f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock(bb, IntList.EMPTY); 1078f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1079f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1080f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1081f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1082f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs and adds the return block, if necessary. The return 108399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * block merely contains an appropriate {@code return} 1084f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction. 1085f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1086f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void addReturnBlock() { 1087f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Rop returnOp = machine.getReturnOp(); 1088f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1089f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (returnOp == null) { 1090f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1091f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The method being converted never returns normally, so there's 1092f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * no need for a return block. 1093f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1094f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 1095f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1096f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1097f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SourcePosition returnPos = machine.getReturnPosition(); 1098f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label = getSpecialLabel(RETURN); 1099f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (isSynchronized()) { 1101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList insns = new InsnList(1); 1102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn = new ThrowingInsn(Rops.MONITOR_EXIT, returnPos, 1103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.make(getSynchReg()), 1104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StdTypeList.EMPTY); 1105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(0, insn); 1106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.setImmutable(); 1107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int nextLabel = getSpecialLabel(SYNCH_RETURN); 1109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock bb = 1110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new BasicBlock(label, insns, 1111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList.makeImmutable(nextLabel), nextLabel); 1112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock(bb, IntList.EMPTY); 1113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project label = nextLabel; 1115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList insns = new InsnList(1); 1118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project TypeList sourceTypes = returnOp.getSources(); 1119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources; 1120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (sourceTypes.size() == 0) { 1122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sources = RegisterSpecList.EMPTY; 1123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 1124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec source = RegisterSpec.make(0, sourceTypes.getType(0)); 1125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sources = RegisterSpecList.make(source); 1126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn = new PlainInsn(returnOp, returnPos, null, sources); 1129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(0, insn); 1130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.setImmutable(); 1131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock bb = new BasicBlock(label, insns, IntList.EMPTY, -1); 1133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock(bb, IntList.EMPTY); 1134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs and adds, if necessary, the catch-all exception handler 1138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * block to deal with unwinding the lock taken on entry to a synchronized 1139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * method. 1140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void addSynchExceptionHandlerBlock() { 1142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!synchNeedsExceptionHandler) { 1143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The method being converted either isn't synchronized or 1145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * can't possibly throw exceptions in its main body, so 1146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * there's no need for a synchronized method exception 1147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * handler. 1148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 1150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SourcePosition pos = method.makeSourcePosistion(0); 1153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec exReg = RegisterSpec.make(0, Type.THROWABLE); 1154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock bb; 1155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn; 1156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList insns = new InsnList(2); 1158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn = new PlainInsn(Rops.opMoveException(Type.THROWABLE), pos, 1159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project exReg, RegisterSpecList.EMPTY); 1160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(0, insn); 1161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn = new ThrowingInsn(Rops.MONITOR_EXIT, pos, 1162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.make(getSynchReg()), 1163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StdTypeList.EMPTY); 1164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(1, insn); 1165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.setImmutable(); 1166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label2 = getSpecialLabel(SYNCH_CATCH_2); 1168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bb = new BasicBlock(getSpecialLabel(SYNCH_CATCH_1), insns, 1169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList.makeImmutable(label2), label2); 1170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock(bb, IntList.EMPTY); 1171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns = new InsnList(1); 1173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn = new ThrowingInsn(Rops.THROW, pos, 1174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.make(exReg), 1175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StdTypeList.EMPTY); 1176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(0, insn); 1177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.setImmutable(); 1178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bb = new BasicBlock(label2, insns, IntList.EMPTY, -1); 1180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock(bb, IntList.EMPTY); 1181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Creates the exception handler setup blocks. "maxLocals" 1185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * below is because that's the register number corresponding 1186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to the sole element on a one-deep stack (which is the 1187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * situation at the start of an exception handler block). 1188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void addExceptionSetupBlocks() { 1190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int len = catchTypes.length; 1192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < len; i++) { 1193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Type one = catchTypes[i]; 1194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (one != null) { 1195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn proto = labelToBlock(i).getFirstInsn(); 1196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SourcePosition pos = proto.getPosition(); 1197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList il = new InsnList(2); 1198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn = new PlainInsn(Rops.opMoveException(one), 1200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pos, 1201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec.make(maxLocals, one), 1202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY); 1203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project il.set(0, insn); 1204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn = new PlainInsn(Rops.GOTO, pos, null, 1206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY); 1207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project il.set(1, insn); 1208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project il.setImmutable(); 1209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock bb = new BasicBlock(getExceptionSetupLabel(i), 1211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project il, 1212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList.makeImmutable(i), 1213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i); 1214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock(bb, startFrames[i].getSubroutines()); 1215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Checks to see if the basic block is a subroutine caller block. 1221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 122299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param bb {@code non-null;} the basic block in question 1223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if this block calls a subroutine 1224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean isSubroutineCaller(BasicBlock bb) { 1226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList successors = bb.getSuccessors(); 1227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (successors.size() < 2) return false; 1228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int subLabel = successors.get(1); 1230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return (subLabel < subroutines.length) 1232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && (subroutines[subLabel] != null); 1233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 123639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Inlines any subroutine calls. 1237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void inlineSubroutines() { 1239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final IntList reachableSubroutineCallerLabels = new IntList(4); 1240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Compile a list of all subroutine calls reachable 1243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * through the normal (non-subroutine) flow. We do this first, since 1244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * we'll be affecting the call flow as we go. 124539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 1246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Start at label 0 -- the param assignment block has nothing for us 1247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project forEachNonSubBlockDepthFirst(0, new BasicBlock.Visitor() { 1249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitBlock(BasicBlock b) { 1250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (isSubroutineCaller(b)) { 1251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reachableSubroutineCallerLabels.add(b.getLabel()); 1252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project }); 1255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Convert the resultSubroutines list, indexed by block index, 1258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to a label-to-subroutines mapping used by the inliner. 1259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int largestAllocedLabel = getAvailableLabel(); 1261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<IntList> labelToSubroutines 1262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = new ArrayList<IntList>(largestAllocedLabel); 1263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < largestAllocedLabel; i++) { 1264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToSubroutines.add(null); 1265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < result.size(); i++) { 1268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock b = result.get(i); 1269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (b == null) { 1270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 1271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList subroutineList = resultSubroutines.get(i); 1273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToSubroutines.set(b.getLabel(), subroutineList); 1274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 127739c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Inline all reachable subroutines. 127839c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Inner subroutines will be inlined as they are encountered. 127939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein */ 1280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = reachableSubroutineCallerLabels.size(); 1281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0 ; i < sz ; i++) { 1282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label = reachableSubroutineCallerLabels.get(i); 1283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new SubroutineInliner( 128439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein new LabelAllocator(getAvailableLabel()), 128539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein labelToSubroutines) 1286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project .inlineSubroutineCalledFrom(labelToBlock(label)); 1287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Now find the blocks that aren't reachable and remove them 1290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project deleteUnreachableBlocks(); 1291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Deletes all blocks that cannot be reached. This is run to delete 1295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * original subroutine blocks after subroutine inlining. 1296f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1297f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void deleteUnreachableBlocks() { 1298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final IntList reachableLabels = new IntList(result.size()); 1299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // subroutine inlining is done now and we won't update this list here 1301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultSubroutines.clear(); 1302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project forEachNonSubBlockDepthFirst(getSpecialLabel(PARAM_ASSIGNMENT), 1304f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new BasicBlock.Visitor() { 1305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitBlock(BasicBlock b) { 1307f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reachableLabels.add(b.getLabel()); 1308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project }); 1310f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1311f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reachableLabels.sort(); 1312f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = result.size() - 1 ; i >= 0 ; i--) { 1314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (reachableLabels.indexOf(result.get(i).getLabel()) < 0) { 1315f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.remove(i); 1316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // unnecessary here really, since subroutine inlining is done 1317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project //resultSubroutines.remove(i); 1318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1319f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1320f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Allocates labels, without requiring previously allocated labels 1324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to have been added to the blocks list. 1325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static class LabelAllocator { 1327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int nextAvailableLabel; 1328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1329f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1330f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param startLabel available label to start allocating from 1331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LabelAllocator(int startLabel) { 1333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project nextAvailableLabel = startLabel; 1334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return next available label 1338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int getNextLabel() { 1340f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return nextAvailableLabel++; 1341f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Inlines a subroutine. Start by calling 134639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * {@link #inlineSubroutineCalledFrom}. 1347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private class SubroutineInliner { 1349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 135039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * maps original label to the label that will be used by the 135139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * inlined version 1352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final HashMap<Integer, Integer> origLabelToCopiedLabel; 1354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 135539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein /** set of original labels that need to be copied */ 1356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final BitSet workList; 1357f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 135839c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein /** the label of the original start block for this subroutine */ 1359f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int subroutineStart; 1360f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 136139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein /** the label of the ultimate return block */ 1362f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int subroutineSuccessor; 1363f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 136439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein /** used for generating new labels for copied blocks */ 1365f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final LabelAllocator labelAllocator; 1366f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1367f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1368f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * A mapping, indexed by label, to subroutine nesting list. 1369f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The subroutine nest list is as returned by 1370f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * {@link Frame#getSubroutines}. 1371f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1372f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final ArrayList<IntList> labelToSubroutines; 1373f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1374f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SubroutineInliner(final LabelAllocator labelAllocator, 1375f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<IntList> labelToSubroutines) { 1376f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project origLabelToCopiedLabel = new HashMap<Integer, Integer>(); 1377f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1378f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project workList = new BitSet(maxLabel); 1379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.labelAllocator = labelAllocator; 1381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.labelToSubroutines = labelToSubroutines; 1382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1385f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Inlines a subroutine. 138639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 138739c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param b block where {@code jsr} occurred in the original bytecode 1388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1389f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void inlineSubroutineCalledFrom(final BasicBlock b) { 1390f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1391f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The 0th successor of a subroutine caller block is where 1392f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the subroutine should return to. The 1st successor is 1393f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the start block of the subroutine. 1394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutineSuccessor = b.getSuccessors().get(0); 1396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project subroutineStart = b.getSuccessors().get(1); 1397f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This allocates an initial label and adds the first 1400f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * block to the worklist. 1401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1402f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newSubStartLabel = mapOrAllocateLabel(subroutineStart); 1403f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 140441aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein for (int label = workList.nextSetBit(0); label >= 0; 140541aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein label = workList.nextSetBit(0)) { 1406f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project workList.clear(label); 1407f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newLabel = origLabelToCopiedLabel.get(label); 1408f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1409f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project copyBlock(label, newLabel); 1410f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1411f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (isSubroutineCaller(labelToBlock(label))) { 1412f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new SubroutineInliner(labelAllocator, labelToSubroutines) 1413f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project .inlineSubroutineCalledFrom(labelToBlock(newLabel)); 1414f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1416f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1417f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1418f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Replace the original caller block, since we now have a 1419f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * new successor 1420f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1421f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1422f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addOrReplaceBlockNoDelete( 1423f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new BasicBlock(b.getLabel(), b.getInsns(), 1424f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList.makeImmutable (newSubStartLabel), 142541aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein newSubStartLabel), 142641aecd0a6bfea1e9a6713014b2b3d56fec8c552cDan Bornstein labelToSubroutines.get(b.getLabel())); 1427f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1428f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1429f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1430f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copies a basic block, mapping its successors along the way. 143139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 1432f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param origLabel original block label 1433f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param newLabel label that the new block should have 1434f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1435f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void copyBlock(int origLabel, int newLabel) { 1436f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1437f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock origBlock = labelToBlock(origLabel); 1438f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1439f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final IntList origSuccessors = origBlock.getSuccessors(); 1440f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList successors; 1441f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int primarySuccessor = -1; 1442f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Subroutine subroutine; 1443f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1444f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (isSubroutineCaller(origBlock)) { 1445f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1446f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * A subroutine call inside a subroutine call. 1447f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Set up so we can recurse. The caller block should have 1448f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * it's first successor be a copied block that will be 1449f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the subroutine's return point. It's second successor will 1450f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * be copied when we recurse, and remains as the original 1451f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * label of the start of the inner subroutine. 1452f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1453f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1454f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors = IntList.makeImmutable( 1455f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mapOrAllocateLabel(origSuccessors.get(0)), 1456f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project origSuccessors.get(1)); 1457f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // primary successor will be set when this block is replaced 1458f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (null 1459f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project != (subroutine = subroutineFromRetBlock(origLabel))) { 1460f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1461f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * this is a ret block -- its successor 1462f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * should be subroutineSuccessor 1463f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1464f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1465f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Sanity check 1466f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (subroutine.startBlock != subroutineStart) { 1467f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException ( 1468f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project "ret instruction returns to label " 1469f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project + Hex.u2 (subroutine.startBlock) 1470f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project + " expected: " + Hex.u2(subroutineStart)); 1471f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1472f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1473f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors = IntList.makeImmutable(subroutineSuccessor); 1474f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySuccessor = subroutineSuccessor; 1475f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 1476f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Map all the successor labels 1477f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1478f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int origPrimary = origBlock.getPrimarySuccessor(); 1479f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = origSuccessors.size(); 1480f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1481f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors = new IntList(sz); 1482f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1483f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0 ; i < sz ; i++) { 1484f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int origSuccLabel = origSuccessors.get(i); 1485f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newSuccLabel = mapOrAllocateLabel(origSuccLabel); 1486f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1487f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.add(newSuccLabel); 1488f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1489f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (origPrimary == origSuccLabel) { 1490f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project primarySuccessor = newSuccLabel; 1491f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1492f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1493f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1494f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors.setImmutable(); 1495f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1496f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1497f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addBlock ( 1498f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new BasicBlock(newLabel, 1499f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project filterMoveReturnAddressInsns(origBlock.getInsns()), 1500f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project successors, primarySuccessor), 1501f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToSubroutines.get(newLabel)); 1502f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1503f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1504f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1505f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Checks to see if a specified label is involved in a specified 1506f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * subroutine. 1507f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 150899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param label {@code >= 0;} a basic block label 150939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param subroutineStart {@code >= 0;} a subroutine as identified 151039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * by the label of its start block 151139c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @return true if the block is dominated by the subroutine call 1512f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1513f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean involvedInSubroutine(int label, int subroutineStart) { 1514f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList subroutinesList = labelToSubroutines.get(label); 1515f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return (subroutinesList.size() > 0 1516f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && subroutinesList.top() == subroutineStart); 1517f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1518f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1519f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1520f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Maps the label of a pre-copied block to the label of the inlined 1521f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * block, allocating a new label and adding it to the worklist 1522f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * if necessary. If the origLabel is a "special" label, it 1523f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is returned exactly and not scheduled for duplication: copying 1524f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * never proceeds past a special label, which likely is the function 1525f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * return block or an immediate predecessor. 1526f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1527f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param origLabel label of original, pre-copied block 1528f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return label for new, inlined block 1529f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1530f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int mapOrAllocateLabel(int origLabel) { 1531f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int resultLabel; 1532f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Integer mappedLabel = origLabelToCopiedLabel.get(origLabel); 1533f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1534f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (mappedLabel != null) { 1535f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultLabel = mappedLabel; 1536f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (!involvedInSubroutine(origLabel,subroutineStart)) { 1537f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1538f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * A subroutine has ended by some means other than a "ret" 1539f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * (which really means a throw caught later). 1540f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1541f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultLabel = origLabel; 1542f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 1543f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project resultLabel = labelAllocator.getNextLabel(); 1544f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project workList.set(origLabel); 1545f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project origLabelToCopiedLabel.put(origLabel, resultLabel); 1546f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1547f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // The new label has the same frame as the original label 1548f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (labelToSubroutines.size() <= resultLabel) { 1549f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToSubroutines.add(null); 1550f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1551f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToSubroutines.set(resultLabel, 1552f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToSubroutines.get(origLabel)); 1553f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1554f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1555f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return resultLabel; 1556f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1557f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1558f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1559f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 156039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Finds a {@code Subroutine} that is returned from by a {@code ret} in 1561f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * a given block. 156239c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 156339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param label A block that originally contained a {@code ret} instruction 156439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @return {@code null-ok;} found subroutine or {@code null} if none 156539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * was found 1566f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1567f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private Subroutine subroutineFromRetBlock(int label) { 1568f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = subroutines.length - 1 ; i >= 0 ; i--) { 1569f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (subroutines[i] != null) { 1570f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Subroutine subroutine = subroutines[i]; 1571f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1572f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (subroutine.retBlocks.get(label)) { 1573f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return subroutine; 1574f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1575f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1576f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1577f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1578f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return null; 1579f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1580f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1581f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1582f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 158339c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Removes all {@code move-return-address} instructions, returning a new 158439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * {@code InsnList} if necessary. The {@code move-return-address} 158539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * insns are dead code after subroutines have been inlined. 1586f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 158739c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @param insns {@code InsnList} that may contain 158839c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * {@code move-return-address} insns 158939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * @return {@code InsnList} with {@code move-return-address} removed 1590f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1591f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private InsnList filterMoveReturnAddressInsns(InsnList insns) { 1592f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz; 1593f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newSz = 0; 1594f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1595f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // First see if we need to filter, and if so what the new size will be 1596f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sz = insns.size(); 1597f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 1598f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insns.get(i).getOpcode() != Rops.MOVE_RETURN_ADDRESS) { 1599f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSz++; 1600f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1601f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1602f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1603f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (newSz == sz) { 1604f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return insns; 1605f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1606f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1607f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Make a new list without the MOVE_RETURN_ADDRESS insns 1608f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList newInsns = new InsnList(newSz); 1609f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1610f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newIndex = 0; 1611f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 1612f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn = insns.get(i); 1613f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn.getOpcode() != Rops.MOVE_RETURN_ADDRESS) { 1614f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newInsns.set(newIndex++, insn); 1615f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1616f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1617f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1618f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newInsns.setImmutable(); 1619f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return newInsns; 1620f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1621f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1622f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1623f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Visits each non-subroutine block once in depth-first successor order. 162439c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 1625f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param firstLabel label of start block 1626f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param v callback interface 1627f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 162839c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein private void forEachNonSubBlockDepthFirst(int firstLabel, 162939c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein BasicBlock.Visitor v) { 1630f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project forEachNonSubBlockDepthFirst0(labelToBlock(firstLabel), 1631f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project v, new BitSet(maxLabel)); 1632f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1633f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1634f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 163539c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * Visits each block once in depth-first successor order, ignoring 163639c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * {@code jsr} targets. Worker for {@link #forEachNonSubBlockDepthFirst}. 163739c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein * 1638f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param next next block to visit 1639f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param v callback interface 1640f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param visited set of blocks already visited 1641f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1642f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void forEachNonSubBlockDepthFirst0( 1643f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock next, BasicBlock.Visitor v, BitSet visited) { 1644f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project v.visitBlock(next); 1645f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project visited.set(next.getLabel()); 1646f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1647f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList successors = next.getSuccessors(); 1648f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = successors.size(); 1649f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 165039c5899d0359c386815f5f72991a3a2573135dbdDan Bornstein for (int i = 0; i < sz; i++) { 1651f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int succ = successors.get(i); 1652f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1653f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (visited.get(succ)) { 1654f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 1655f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1656f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1657f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (isSubroutineCaller(next) && i > 0) { 1658f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // ignore jsr targets 1659f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 1660f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1661f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1662f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1663f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Ignore missing labels: they're successors of 1664f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * subroutines that never invoke a ret. 1665f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1666f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int idx = labelToResultIndex(succ); 1667f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (idx >= 0) { 1668f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project forEachNonSubBlockDepthFirst0(result.get(idx), v, visited); 1669f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1670f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1671f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1672f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 1673